[Data Structure]数据结构学习之链表小结[上]:
by EmilMatthew
线性表中的链表是数据结构学习的基础和起点, 虽说看上去比较简单.不过里面所涉及的一些操作及算法还是有相当的深入和实践价值的,把它们搞熟了,是进一步学习的基石.
首先当然是看一下链表的两种基本实现,一种是基于数据的,还有一种是基于指针的:
(这里的数据结构的定义部分的代码风格基于北大的张乃孝的<算法与数据结构>一书)
1基于数组的链表实现:
/*
All these code -------think ,code , test by EmilMatthew,You can modify and use them as you wish, but I do not promise these code can fit all your needs.
05/09/12
*/
/*SeqList*/
struct SeqList;
typedef struct SeqList* PSeqList;
struct SeqList
{
Type element[MAXLENGTH];
int n;
};
线性表相关的操作:
//创建空表:
PSeqList createNullList_Seq(void)
{
PSeqList palist;
palist=(PSeqList)malloc(sizeof(PSeqList));
assertF(palist!=NULL,"in createNullList_Seq,pallist is null\n");
palist->n=-1;
return palist;
}
//在指定位置插入:
void insert_Seq(PSeqList inSeqList,int pos,Type data)
{
int i;
assertF(inSeqList!=NULL,"in insert_Seq,PSeqList is null\n");
assertF(inSeqList->n<MAXLENGTH-1,"in insert_Seq,no more space\n");
assertF(pos>=0&&pos<=inSeqList->n+1,"in insert_Seq ,pos out of range\n");
inSeqList->n++;
for(i=inSeqList->n;i>=pos+1;i--)
inSeqList->element[i+1]=inSeqList->element[i];
assertF(i==pos,"in insert_Seq,i!=pos\n");
inSeqList->element[i]=data;
}
//在指定位置删除节点
void del_ElementP(PSeqList inSeqList,int pos)
{
int i;
assertF(inSeqList!=NULL,"in del_ElementP,PSeqList is null\n");
assertF(pos>=0&&pos<=inSeqList->n,"in del_ElementP ,pos out of range\n");
assertF(inSeqList->n!=-1,"in del_ElementP,PSeqList is null\n");
for(i=pos;i<inSeqList->n;i++)
inSeqList->element[i]=inSeqList->element[i+1];
inSeqList->n--;
inSeqList=NULL;
}
//将链表逆转
void reverseSeqList(PSeqList inSeqList)
{
int l, u;
assertF(inSeqList!=NULL,"in reverseSeqList,pallist is null\n");
/*init data*/
l=0;
u=(inSeqList->n)-1;
while(l<=u)
{
swapArrData(inSeqList->element,l,u);
l++;
u--;
}
}
//遍历链表
void traversalSeqList(PSeqList inSeqList)
{
PSeqList node;
int i;
assertF(inSeqList!=NULL,"in traversalSeqList,pallist is null\n");
node=inSeqList;
/*init*/
i=0;
printf("===starting of traversalYouBiaoNode===\n");
while(i<inSeqList->n)
{
printf("%d->",inSeqList->element[i]);
i++;
}
printf("%d",inSeqList->element[i]);
printf("\n===end of traversalYouBiaoNode===\n");
}
//在某个位置插入元素
int locateData(PSeqList inSeqList,Type searchData)
{
int i=0;
int returnPos=-1;
for(i=0;i<=inSeqList->n;i++)
if(inSeqList->element[i]==searchData)
{
returnPos=i;
break;
}
return returnPos;
}
//得到某个位置的元素值
Type retriveData(PSeqList inSeqList,int pos)
{
assertF(inSeqList!=NULL,"in retriveData,PSeqList is null\n");
assertF(pos>=0&&pos<=inSeqList->n,"in retriveData ,pos out of range\n");
return inSeqList->element[pos];
}
//检测当前链表是否为空
int isNullSeqList(PSeqList inSeqList)
{
return inSeqList==NULL||inSeqList->n==-1;
}
以上操作相对都比较的简单,所以就不做过多的介绍了,重点是下面基于指针来实现的链表上:
2基于指针实现的链表:
/*link_List*/
struct Node;
typedef struct Node* PNode;
typedef struct Node* LinkList;
struct Node
{
Type info;
PNode link;
};
//创建一个空链表
LinkList createNullList_LinkList(void)
{
PNode tmpNode;
tmpNode=(PNode)malloc(sizeof(struct Node));
assertF(tmpNode!=NULL,"in createNullList_Seq,tmpNode is null\n");
tmpNode->info=Undefined;
tmpNode->link=NULL;
return tmpNode;
}
//在指定的位置插入数据
void insert_LinkList(LinkList* inLinkList,int pos,Type data)
{
int i=0;
LinkList* tmpListNode;
LinkList newListNode,head;
assertF(*inLinkList!=NULL,"in insert_LinkList,tmpNode is null\n");
tmpListNode=(LinkList*)malloc(sizeof(struct Node*));
head=(LinkList)malloc(sizeof(struct Node));
head=*inLinkList;
tmpListNode=inLinkList;
//head and rear is insert operation's difficult.
i=0;
while(i<pos-1&&(*tmpListNode)->link)//stop at the insert node's pre node.
{
*tmpListNode=(*tmpListNode)->link;
i++;
}
assertF(i==pos-1||pos==0,"in insert_LinkList,out of iterator error\n");
if(pos==0&&(*inLinkList)->info==Undefined)
{
(*tmpListNode)->info=data;
}
else if(pos==0)
{
newListNode=(LinkList)malloc(sizeof(struct Node));
newListNode->link=*tmpListNode;
newListNode->info=data;
*tmpListNode=newListNode;
}
else
{
newListNode=(LinkList)malloc(sizeof(struct Node));
newListNode->link=(*tmpListNode)->link;
newListNode->info=data;
(*tmpListNode)->link=newListNode;
*tmpListNode=head;//repoint to its head.
}
}
//在指定位置删除元素:
void del_ElementLinkList(LinkList* inLinkList,int pos)
{
int i=0;
LinkList tmpListNode,delNode;
assertF(*inLinkList!=NULL,"in del_ElementLinkList,inLinkList is null\n");
tmpListNode=(LinkList)malloc(sizeof(struct Node));
delNode=(LinkList)malloc(sizeof(struct Node));
tmpListNode=*inLinkList;
i=0;
while(i<pos-1&&tmpListNode->link->link)//stop at the del
node's position.
{
tmpListNode=tmpListNode->link;
i++;
}
assertF(i==pos-1||pos==0,"in insert_LinkList,out of iterator error\n");
if(pos==0&&(*inLinkList)->info==Undefined)
{
*inLinkList=NULL;//because this action have to use 2d pointer.
}
else if(pos==0)
{
delNode=*inLinkList;
*inLinkList=(*inLinkList)->link;
free(delNode);
}
else
{
delNode=tmpListNode->link;
tmpListNode->link=tmpListNode->link->link;
free(delNode);
}
}
//遍历链表
void traversalLinkList(LinkList inLinkList)
{
LinkList tmpListNode;
assertF(inLinkList!=NULL,"in traversalLinkList,tmpNode is null\n");
tmpListNode=(LinkList)malloc(sizeof(struct Node));
tmpListNode=inLinkList;
printf("===starting of traversalLinkList===\n");
while(tmpListNode->link)
{
printf("%d->",tmpListNode->info);
tmpListNode=tmpListNode->link;
}
printf("%d\n",tmpListNode->info);
printf("====end of traversalLinkList====\n");
tmpListNode=NULL;
}
//返回某个值在链表中第一次出现的位置 .
int locateDataInLinkList(LinkList inLinkList,Type searchData)
{
LinkList tmpListNode;
int pos,i;
assertF(inLinkList!=NULL,"in traversalLinkList,tmpNode is null\n");
tmpListNode=(LinkList)malloc(sizeof(struct Node));
tmpListNode=inLinkList;
pos=-1;
i=0;
while(tmpListNode)
{
if(tmpListNode->info==searchData)
{
pos=i;
break;
}
tmpListNode=tmpListNode->link;//move forward.
i++;
}
tmpListNode=NULL;
return pos;
}
//得到链表中指定位置的值
Type retriveDataInLinkList(LinkList inLinkList,int pos)
{
int i=0;
LinkList tmpListNode;
Type reData;
assertF(inLinkList!=NULL,"in retriveDataInLinkList,inLinkList is null\n");
tmpListNode=(LinkList)malloc(sizeof(struct Node));
tmpListNode=inLinkList;
i=0;
//pos just stands for the step the head need to move.
while(i<pos&&tmpListNode->link)//stop at the pos node's position .
{
tmpListNode=tmpListNode->link;
i++;
}
assertF(i==pos||pos==0,"in inLinkList,out of iterator error\n");//the forging steps
reData=tmpListNode->info;
return reData;
}
int isNullLinkList(LinkList inLinkList)
{
return inLinkList==NULL||inLinkList==0;
}
3基于C++模版的链表实现:
#include "Global.h"
#include "MyAssert.h"
#include <stdlib.h>
#include <stdio.h>
#ifndef ELIST_H
#define ELSIT_H
template<class T>
class eNode
{
//friend class eList<T>;
public:
eNode();
T data;
eNode<T>* next;
};
template<class T>
eNode<T>::eNode()
{
next=NULL;
}
template<class T>
class eList
{
public:
eList()
{
head=new eNode<T>;
assertF(head!=NULL,"in eList,head is NUll\n");
head->next=NULL;
head_defined=false;
length=0;
}
eList(T initValue);
~eList();
bool isEmpty() const
{
return !head_defined||head==NULL;
}
bool full() const;
T headData() const;
eList<T>& addAtHead(const T inData);
eList<T>& addAtRear(const T inData);
eList<T>& addAtPos(const T inData,long posIndex);
T deEListAtPos(long posIndex);
T deFromHead();
//ulti operation.
void traverseFloat(char* outputFileName);
long getLength();
T& getDataAtPos(long posIndex);
private:
eNode<T>* head;
bool head_defined;
long length;
};
template<class T>
eList<T>::eList(T initValue)
{
head=new eNode<T>;
assertF(head!=NULL,"in eList,head is NUll\n");
head->next=NULL;
head->data=initValue;
head_defined=true;
length=0;
}
template<class T>
eList<T>::~eList()
{
eNode<T>* tmpNext;
while(head)
{
tmpNext=head->next;
delete head;
head=tmpNext;
}
}
template<class T>
bool eList<T>::full()const
{//So funny a function.
eNode<T>* p=new eNode<T>;
assertF(p!=NULL,"no new mem is omited to be applyed\n");
delete p;
return false;
}
template<class T>
T eList<T>::headData()const
{
assertF(!isEmpty(),"the queue is empty.\n");
return head->data;
}
template<class T>
eList<T>& eList<T>::addAtHead(const T inData)
{
if(!head_defined)
{
head->data=inData;
head_defined=true;
}
else
{
eNode<T>* tmpNode=new eNode<T>;
tmpNode->data=inData;
tmpNode->next=head;
head=tmpNode;
}
return *this;
}
template<class T>
eList<T>& eList<T>::addAtRear(const T inData)
{
eNode<T>* tmpNode=new eNode<T>;
eNode<T>* p=new eNode<T>;
tmpNode->data=inData;
p=head;
while(p->next)
{
p=p->next;
}
assertF(p!=NULL,"in addAtRear p is NULL\n");
p->next=tmpNode;
return *this;
}
template<class T>
eList<T>& eList<T>::addAtPos(const T inData,long posIndex)
{//this pos is just the same as in c lang,start from 0;
long j;
eNode<T>* tmpNode=new eNode<T>;
eNode<T>* p=new eNode<T>;
//data init
tmpNode->data=inData;
p=head;
j=0;
while(p&&j<posIndex-1)
{
p=p->next;
j++;
}
if(!head_defined)
assertF(j==0&&posIndex,"in addAtPos, head is undefined\n");
else if(posIndex==0)
assertF(j==0,"in addAtPos, error happens.\n");
else
assertF(j==posIndex-1,"in addAtPos,j!=posIndex-1\n");
if(!head_defined)
{
head->data=inData;
head_defined=true;
}
else if(posIndex==0)
{
tmpNode->next=head;
head=tmpNode;
}
else
{
tmpNode->next=p->next;
p->next=tmpNode;
}
// cout<<posIndex<<" "<<endl;
return *this;
}
template<class T>
T eList<T>::deFromHead()
{
eNode<T>* p=new eNode<T>;
T tmpData;
assertF(!isEmpty(),"in deFromHead, the list is empty\n");
p=head;
tmpData=head->data;
head=head->next;
delete p;
return tmpData;
}
template<class T>
T eList<T>::deEListAtPos(long posIndex)
{
long j;
eNode<T>* tmpNode=new eNode<T>;
eNode<T>* p=new eNode<T>;
T tmpData;
//data init
p=head;
j=0;
tmpData=head->data;
assertF(head_defined,"in deEListAtPos,the head node is null\n");
while(p&&j<posIndex-1)
{
p=p->next;
j++;
}
assertF(p!=NULL,"in deEListAtPos,the posIndex has been out of bounds.\n");
if(posIndex==0)
assertF(j==0,"in deEListAtPos, head is undefined\n");
else
assertF(j==posIndex-1,"in deEListAtPos,j!=posIndex\n");
if(posIndex==0&&head->next==NULL)
{
tmpNode=p;
p=p->next;
head=p;
head_defined=false;
delete tmpNode;
}
else if(posIndex==0&&head->next!=NULL)
{
tmpNode=p;
p=p->next;
head=p;
delete tmpNode;
}
else
{
tmpNode=p->next;
p->next=tmpNode->next;
delete tmpNode;
}
return tmpData;
}
template<class T>
void eList<T>::traverseFloat(char* outputFileName)
{
FILE* outputFile;
eNode<T>* tmpNode=new eNode<T>;
long count=0;
assertF(outputFileName!=NULL,"in eList.traverse(),listFileName is null\n");
assertF((outputFile=fopen(outputFileName,"wb"))!=NULL,"output file open error");
assertF(!isEmpty(),"Warning,in traverseFloat,the list is null\n");
tmpNode=head;
while(tmpNode)
{
fprintf(outputFile,"\r\n");
fprintf(outputFile,"%f ",tmpNode->data);
cout<<tmpNode->data<<" ";
if((count+1)%50==0)
fprintf(outputFile,"\r\n");
tmpNode=tmpNode->next;
count++;
}
}
template<class T>
long eList<T>::getLength()
{
eNode<T>* tmpNode=new eNode<T>;
long count=0;
tmpNode=head;
while(tmpNode)
{
count++;
tmpNode=tmpNode->next;
}
assertF(tmpNode==NULL,"in getLength,tmpNode not reach to its end.");
return count;
}
template<class T>
T& eList<T>::getDataAtPos(long posIndex)
{
long j;
eNode<T>* p=new eNode<T>;
p=head;
assertF(head_defined,"in getDataAtPos,the head node is null\n");
/*init data*/
j=0;
while(p&&j<posIndex)
{
p=p->next;
j++;
}
assertF(p!=NULL,"in deEListAtPos,the posIndex has been out of bounds.\n");
assertF(j==posIndex,"in deEListAtPos,j!=posIndex\n");
return p->data;
}
#endif
这些操作的实现也是相对简单的,但是难点在于不要使链表断链以及指针的操作上.
C++版本模版的好处在于面向对象的数据结构表示要比面向过程的来得直接,而且数据的操作上相对简单(少去了参数传递(尤其是指针)的麻烦.)
好戏在后头…:
