数据结构-线性表,链表总结教材

1、数据结构线性表#defi ne TRUE1#defi ne FALSE0#defi ne OK1#defi ne ERROR0#defi ne INFEASIBLE-1#defi ne OVERFLOW-2typedef int Status;1线性表的顺序表示和实现#defi ne LIST_INIT_SIZE 100#defi ne LISTINCREMENT 10 typedef structElemType *Elem;intlen gth;intlistsize;SqList;Status In itList_Sq(SqList & L)构造一个空的线性表LL.elem=(E

2、lemType*)malloc(LIST_INIT_SIZ E*sizeof(ElemType);If (L.elem=NULL)exit(OVERFLOW);elseL.le ngth=O;L.listsize=LIST_INIT_SIZE;return OK;Status DestroyList_Sq(SqList &L)/销毁线性表Lif(L.elem=NULL)return ERROR;elsefree(L.elem);return OK;Status ClearList_Sq(Sqlist &L)/将L置为空表if(L.elem=NULL)exit(ERROR);in

3、t i;ElemType *p_elem=L.elem;for(i=0;i<L .len gth;i+)*L.elem=NULL;L.elem+;L.elem=p_elem;return OK;Status ListEmpty_Sq(SqList L)/若L为空表则返回 TRUE，否则返回FALSEint i;ElemType *p_elem=L.elem;for(i=0;i<L .len gth;i+)if(*Elem!=0)L.elem=p_elem;return FALSE;L.elem+;return TRUE;Status ListLength_Sq(SqList L)/

4、返回L中元素个数return L.le ngth;Status GetElem_Sq(SqList &L,int i,ElemType&e)/用e返回L中第i个数据元素的值int j;ElemType *p_elem=L.elem;if(i<1|i>L.le ngth)return OVERFLOW;for(j=1;j<=l;j+)L.elem+;e=*L.elem;L.elem=p_elem;return OK;Status LocateElem_Sq(SqList &L,ElemType e,Status(*compare)(ElemType,El

5、emType)/返回L中第一个与e满足关系compare() 的数据元素的位序，若这个数据元素不存在， 则返回0i=1;p=L.elem;while(i<=L.le ngth&&!(*compare)(*p+,e)+i;if(i<=L.length return i;else return 0;Status PriorElem_Sq(SqList L,ElemType cur_e,ElemType &pre_e)/若cur_e是L的数据元素，且不是第一个， 则用pre_e返回它的前驱，否则操作失败， pre_e无定义p=L.elem;int i,j;i=Lo

6、cati on Elem_Sq(L,cur_e);if(i<=1|i>L.le ngth)exit(OVERFLOW);for(j=1;j<I;j+)if(j=(i-1)pre_e=L.elem;L.elem=p;return OK;elseL.elem+;Status NextElem_Sq(SqList L,ElemType cur_e,ElemType &n ext_e)/若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的前驱，否则操作失败，next_e无定义ElemType *p_elem;int i,j;i=LocateElem_Sq(L,

7、cur_e);if(i<1|i>=L.le ngth)exit(OVERFLOW);for(j=1;j<1;j+)if(j=(i-1)n ext_e=L.elem;L.elem=p_elem;return OK;elseL.elem+;Status ListI nsert_S (List_Sq &L, int i, ElemType e)if(i<1 | i>L.length+1) return ERROR; / 若 i 为无效值，返回错误if(L.length= =L.maxsize) /若存储容量已 满，则增加分配空间n ewbase=(ElemTyp

8、e *) realloc(L .li st,(L.maxsize+LIST_INCREASE)*sizeof(ElemT ype);if(!newbase) exit(OVERFLOW); 若增 加分配空间失败，退出程序L.list= n ewbase; / 新基址L.maxsize +=LIST_INCREASE;/ 存储容量增加/ifq=&(L.listi 1); / 插入位置。q=L.list+i1;也可。for(p =&(L.listL.le ngth - 1); p>=q;- p) / p=L.list+ L.Length 1;也可。*(p+1) = *p; 将

9、插入元素位置之后的元 素依次后移一个位置*q=e; /插入元素e+ L.length; /线性表长度增加 1return OK; II插入操作成功/Listl nsert_SStatus ListDelete_S (List_Sq &L, int i, ElemType &e)if(i<1 | i>L.length) return ERROR; / 若 i 为 无效值，返回错误p=&(L.listi 1); /被删元素的位 置，p=L.list+i 1;也可e=*p; /通过e返回被删除的元素的值q=L.list+ L.length - 1; /线性表的最后

10、一个元素的位置for(+p; p<=q; +p ) *(p 1) =*p; 被删除元素之后的元素依次前移-L.length; /线性表长度减少 1return OK; /删除操作成功/ListDelete_Svoid ListTraverse_Sq(SqList L,visit)/依次对L的每个数据元素调用函数visit(),一旦visit()失败，则操作失败for(i nt i=1;i<Len gth+1;i+)return visit(Elemi-1);2线性表的链式表示和实现2.1带头节点的线性表的单链表存储结构typedef struct LLNodeElemType da

11、ta;struct LLNode *n ext;LLNode,*Li nkList;Status In itList_L(Li nkList &L)L=(Li nkList)malloc(sizeof(structLLNode);if(!L)exit(OVERFLOW);L-> next=NULL;returnOK;Status DestroyList_L(L in kList &L)Lin kList q;while(L)q=L->n ext;free(L);L=q;return OK;Status ClearList_L(Li nkList &L)Lin

12、 kList p,q;while(p)q=p->n ext;free(p);p=q;L-> next=NULL;return OK;Status ListEmpty_L(Li nkList L)if(L->NEXT)return FALSE;elsereturn TRUE;Status ListLe ngth_L(Li nkList L)int i=0;Lin kList p=L->n ext;while(p)i+;p=p->n ext; return I;Status GetElem_L(LinkListL,int I,ElemType&e)int j=

13、1;Lin kList p=L->n ext;while(p&&j<i)p=p->n ext;j+；if(!p|j>i)return ERROR;e=p_>data;return OK;Status LocateElem_L(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType)int i=0;Lin kList p=L->n ext;while(p)i+;if(compare(p->data,e)return i;p=p->n ext; return 0;StatusPri

14、orElem_L(L in kListL,ElemTypecur_e,ElemType &pre_e)Lin kList p,q=L->n ext;while(p-> next)q=p->n ext;if(q->data=cur_e)pre_e=p->data;return OK;p=q;return INFEASIBLE;StatusNextElem_L(L in kListL,ElemTypecur_e,ElemType &n ext_e)Lin kList p=L->n ext;while(p-> next)if(q->da

15、ta=cur_e)n ext_e=p->n ext->data;return OK;p=p->n ext;ruturn INFEASIBLE;StatusListI nsert_L(L in kList& L,i nti,ElemType e)/在L中的第i个位置插入新的数据元素 e,L的长度加1int j=0;Lin kList p=L,s;while(p&&j<i-1)p=p->n ext;j+;if(!p|j>i-1) return ERRORelses=(L in kList)malloc(sizeof(structLLNod

16、e);s->data=e;s->n ext=p->n ext;p_>n ext=s;return OKStatus ListDelete_L(L in kList&L,inti,ElemType &e)/删除L的第i个元素，并用e返回其值，L的长度减1int j=0;Lin kList p=L,q;while(p-> next&&j<i-1)p=p->n ext;j+;if(!p-> next|j>i-1)return ERROR;q=p->n ext;e=q_>data;p_>n ext=

17、q _>n ext;free(q);return OK;Status ListTraverse_L(L in kList L)Lin kList p=L->n ext;while(p)printf( %d ”,p->data);p=p->n ext;printf( 'n”；return OK;2.2不带头结点的单链线性表结构void In itList_L(Li nkList &L)L=(Li nkList)malloc(sizeof(LLNode);L-> next=NULL;struct LLNode *in itlist(void)int n

18、,i;struct LLNode *head,*p,*ph;/*PH 是辅助指针，P向后移动，用PH串联起来*/head=(struct LLNode*)malloc(sizeof(struct LLNode); if(head=NULL)prin tf("malloc error!"); return 0;head-> next=NULL;ph=head;for(i=1;i<=n _1;i+)p=(structLLNode*)malloc(sizeof(struct LLNode); if(p=NULL)prin tf("malloc errror

19、n"); return 0;ph->n ext=p; ph=p;/*用PH将后面的结点连接起来*/p-> next=NULL;retur n head;void typeelem(struct LLNode *head)int i;struct LLNode *p;p=head;/prin tf("%d",head->le ngth);printf("type in your element!as long as it is in it!n");doscan f("%d",&(p-> num)

20、;p=p->n ext;while(p-> next!=NULL); sca nf("%d",&(p-> nu m);void prin tlist(struct LLNode *head)int i;struct LLNode *p;p=head;prin tf("ndoprin tf("%4d",p-> num);p=p->n ext; while(p-> next!=NULL); prin tf("%4d",p-> num);*n");void clearli

21、st(struct LLNode *head) int i;struct LLNode *ph; ph=head;while(ph-> next!=NULL)ph->num=0; ph=ph->n ext;ph->num=0; in t listempty(struct LLNode *head) if(head-> next=NULL) return 1;elsereturn 0; int getelem(struct LLNode *head,i nt n) struct LLNode *ph;int i;ph=head;for(i=1;i<=n _1;

22、i+)ph=ph->n ext;retur n ph->num;int listlength(struct LLNode *head)int k=0;struct LLNode *ph;ph=head;while(ph-> next!=NULL)k+;ph=ph->n ext;k+;return k;int priorelem(struct LLNode *head,i nt num) struct LLNode *ph,*pb;ph=head;if(num=ph->num)printf("no prior n");exit(0);pb=ph;

23、ph=ph->n ext;doif(ph->num=num)retur n pb->num;elsepb=ph;ph=ph->n ext;while(ph-> next!=NULL);return pb->num;prin tf("ca nnot findn");int n extelem(struct LLNode *head,i nt num)struct LLNode *ph,*pf;ph=head;pf=ph->n ext;while(ph-> next!=NULL)if(ph->num=num) retur n

24、 pf->num;elsepf=ph->n ext;ph=ph->n ext;；prin tf("ca nn ot fin d");void list in sert(struct LLNode *head,i nt loc,i nt num)int i;struct LLNode *ph,*p new,*p;ph=head;for(i=1;i<=loc-2;i+)ph=ph->n ext;pn ew=(structLLNode*)malloc(sizeof(struct LLNode);pn ew->num=num;p=ph->n

25、 ext;ph->n ext=p new;pn ew->n ext=p;in t listdelete(struct LLNode*head,i nt loc)in t i, num;struct LLNode *ph,*p;ph=head;for(i=1;i<=loc-2;i+)ph=ph->n ext;p=ph->n ext;num=p->num;ph->n ext=ph->n ext- >n ext;free(p);return num;int compare(i nt a,i nt b) if(a=(b+1)return 1;els

26、ereturn 0;int locateelem(struct LLNode *head,int n,int compare(int a,int b)/*找到表中比输入元素 大一元素的位序*/struct LLNode *p;int k=0;p=head;while(p-> next!=NULL)k+;if(compare(p->num,n)return k+1;p=p->n ext;if(compare(p->num,n)return k+2;return 0;void visit(i nt n)if( n/2.0-n/2)=0)printf("%d 是偶数

27、 n",n);void listtraverse(struct LLNode *head,void visit(i nt n)struct LLNode *p;p=head;while(p-> next!=NULL)visit(p->nu m);p=p->n ext;visit(p->nu m);void destroylist(struct LLNode *head)struct LLNode *p,*ph;p=head;ph=head;while(p-> next!=NULL)ph=p->n ext;free(p);p=ph;free(p);h

28、ead-> next=NULL;3静态链表的基本操作3.1带头节点的静态链表int Malloc(SLinkListspace)/若备用链表不空，则返回分配的结点下标 int i=spaceO.cur;备用链表第1个结点 的位置if(i)备用链表不空spaceO.cur=spacei.cur; 备用链表的头结点指向原备用链表的第2个结点return i;void Free(SL in kList space,i nt k) 将下标为k的空闲结点回收到备用链表中spacek.cur=spaceO.cur; 回收结点的"游标”指向备用链表的第1个结点spaceO.cur=k;备用链

29、表的头结点指向新回收的结点void InitList(SLinkList L) /构造一个空的链表 L，表头为L的最后一 个单元LMAX_SIZE_1,其他单元链成一个 备用链表，表头为 L的第一个单元L0,"0" 表示空指针int i;LMAX_SIZE-1.cur=0;/L的最后一个单元为空链表的表头for(i=0;i<MAX_SIZE-2;i+)将其他单元链接成以L0为表头的备用链表Li.cur=i+1;LMAX_SIZE-2.cur=0;void ClearList(SLinkList L)将表置空int j,k,i=LMAX_SIZE-1.cur;/i 指向

30、链表的第1个结点的位序LMAX_SIZE-1.cur=0; 链表为空k=L0.cur;备用链表第i个结点的位置L0.cur=i;把链表的结点连到备用链表的 表头while(i)/未到表尾j=i;/j指向当前结点的位置i=Li.cur;Lj.cur=k;/备用链表的第i个结点接到链 表的尾部Status ListEmpty(SL in kList L) /判断表是否为空if(LMAX_SIZE-1.cur=0)空表return TRUE;else return FALSE;int ListLength(SLinkList L) /返回表的长度int j=0,i=LMAX_SIZE-1.cur;/

31、i指向链表的第1个结点的位序while(i)/未到链表的表尾 i=Li.cur;/i指向下一个结点j+;/计数器加1return j;Status GetElem(SLinkList L,int i,ElemType&e) /用e返回L中第i个元素的值int m,k=MAX_SIZE-1;/k 指向表头结点的位序if(i<1|i>ListLength(L)/ 不存在第 i 个元素 return ERROR;for(m=1;m<=i;m+)/k 向后移动到第i个元 素k=Lk.cur;指向下一个元素e=Lk.data;return OK;int LocateElem(S

32、LinkList L,ElemType e)/在 静态链表中找第1个值为e的元素，若找到 返回其位序 int i=LMAX_SIZE-1.cur;/i 指向表中的第1个结点的位序while(i &&Li.data!=e) 在表中查找 i=Li.cur;指向下一个元素return i;Status PriorElem(SLi nkList L,ElemType cur_e,ElemType &pre_e)寻找前驱int j,i=LMAX_SIZE-1.cur;/i指向链表第 1个结点的位置do /向后移结点戸;j指向i所指元素i=Li.cur;/i指向下一个元素while

33、(i&&cur_e!=Li.data);if(i)/找到该元素 pre_e=Lj.data;return OK;else return ERROR;StatusNextElem(SLi nkListL,ElemTypecur_e,ElemType &n ext_e) int j,i=LocateElem(L,cur_e);/ 在 L 中查找第1个值为cur_e的元素位置if(i) j=Li.cur;if(j) n ext_e=Lj.data;return OK;return ERROR;Status List In sert(SL in kListL,i nt i,El

34、emTypee) /在L中第i个元素之前插入数据元素eint m,j,k=MAX_SIZE-1;/k 指示表头 结点的位序if(i<1|i>ListLe ngth(L)+1)return ERROR;j=Malloc(L);/申请新单元if(j)/申请成功 Lj.data=e;for(m=1;m<i;m+)/k 向后移 i-1 个结 点，使k指示第i-1个结点k=Lk.cur;指向下一个结点Lj.cur=Lk.cur;/新结点指向第i-1个元素后的元素Lk.cur=j;第i-1个元素指向新单元 return OK;return ERROR;Status ListDelete(

35、SLinkListL,int i,ElemType&e)删除L中第i个元素，并返回其值int j,k=MAX_SIZE-1;/k指示表头结点的位置if(i<1|i>ListLe ngth(L)/return ERROR;for(j=1;j<i;j+)/移动i-1个元素，使k指向第i-1个元素k=Lk.cur;指向下一个元素j=Lk.cur;待删除元素Lk.cur=Lj.cur;/使第i-1个元素指向待删除元素的后继元素e=Lj.data;Free(L,j);return OK;voidListTraverse(SLi nkListL,void(*visit)(Elem

36、Type)/依次对表中的元素调用函数visit()int i=LMAX_SIZE-1.cur;/i指向第一个元素的位序while(i) visit(Li.data); 对当前元素调用visit()i=Li.cur;指向下一个元素prin tf("n");void prin t1(ElemType e) prin tf("%3d",e);3.2不带头结点的静态链表List*delete_list(List*head,int data);int mai n()List*head=NULL;int i;/ for(i=0;i<10;i+)/ head=i

37、n sert_list_2 nd(head,i);/ head=in sert_list_last(head,i);for(i=9;i>=0;i-)head=in sert_list_order(head,i);prin t_list(head);for(i=0;i<9;i+)head=delete_list(head,i);prin t_list(head);List*insert_list_2nd(List*head,int data)List* newLNode=(List*)malloc(sizeof(List);n ewLNode->data=data;/* if(

38、head=NULL)head=newLNode;newLNode->n ext=NULL;elsen ewLNode->n ext=head;head=n ewLNode;*/n ewLNode->n ext=head;head=newLNode;retur n head;List*i nsert_list_last(List*head,i nt data) List*newLNode=(List*)malloc(sizeof(List)5List*temp=head;n ewLNode->data=data;n ewLNode-> next=NULL;if(he

39、ad=NULL) return newLNode;while(temp-> next)temp=temp->n ext;temp->n ext =n ewLNode;retur n head;List*i nsert_list_order(List*head,i nt data)List*temp=head;List* newLNode=(List*)malloc(sizeof(List);n ewLNode->data=data;n ewLNode-> next=NULL;if(head=NULL) /链表为空为空retur n n ewLNode;if(hea

40、d->data>data)/链表第一个节点就是要插入的位置n ewLNode->n ext=head;retur n n ewLNode;while(temp->next&&temp->n ext->data<data)temp=temp->n ext;/* if(temp-> next=NULL)temp->n ext =n ewLNode;elsen ewLNode->n ext=temp->n ext;temp->n ext =n ewLNode;*/n ewLNode->n ext=te

41、mp->n ext;temp->n ext=n ewLNode;retur n head;void prin t_list(List*head)while(head)prin tf("%dn",head->data);head=head->n ext;List*delete_list(List*head,int data) List*temp;List*p;if(head=NULL) return NULL;if(head->data=data)temp=head->n ext;free(head);return temp;temp=he

42、ad;while(temp->n ext&&temp->n ext->data!=data)temp=temp->n ext;p=temp->n ext;if(temp-> next=NULL)printf("no have %dn",data);retur n head;elsetemp->n ext=temp-> next-next;free(p);retur n head;4循环链表的基本操作4.1带头节点的循环链表void In itList(L in kList &L)初始化L=(Li nkL

43、ist)malloc(sizeof(LLNode);结点if(!L)exit(OVERFLOW);L->next=L;头结点的指针指向头结点void ClearList(L in kList &L) Lin kList p,q;L=L->next;/L指向头结点p=L->next;/p指向第1个结点 while(p!=L) q=p->next;/q指向p的后继 free(p);p=q;/p指向q所指结点L->next=L;头结点指针指向自身void DestroyList(L in kList &L) /ClearList(L);Lin kList

44、 p,q;L=L->next;/L指向头结点p=L->next;/p指向第1个结点 while(p!=L) q=p->next;/q指向p的后继 free(p);p=q;/p 指向q所指结点L->next=L;头结点指针指向自身free(L);L=NULL;Status ListEmpty(L in kList L)if(L-> next=L) return TRUE;else return FALSE;int ListLe ngth(L in kList L)int i=0;Li nkList p=L-> next;/p 指向头结点 while(p!=L)

45、i+;计数器加1p=p->n ext;return i;Status GetElem(LinkListL,int i,ElemType&e) /当第i个元素存在时，将其值赋给eint j=1;Lin kList p=L->n ext- >n ext;/p 指向第一 个元素if(i<O|i>ListLe ngth(L)return ERROR;while(j<i)j+;p=p->n ext;e=p_>data;return OK;intLocateElem(Li nkListL,ElemTypee,Status(*compare)(Elem

46、Type,ElemType)/返回第1个与e满足关系compare()的数 据元素的位序int i=0;Lin kList p=L-> next-next;/p 指向第 1 个结点while(p!=L->n ext)if(compare(p->data,e) return i;p=p->n ext;return 0;Status PriorElem(Li nkList L,ElemType cur_e,ElemType &pre_e)返回前驱LinkList q,p=L->next->next;/p 指向第一个元素q=p->next;/q指向p

47、的后继 while(q!=L->n ext)if(q->data=cur_e) pre_e=p->data; return OK;p=q;/p的后继不为cur_e q=q_>n ext; return ERROR;StatusNextElem(Li nkListcur_e,ElemType &n ext_e)/返回后继Lin kList p=L->n ext->n ext;/p 兀素向后移L,ElemType指向第一个while(p!=L)if(p->data=cur_e)next_e=p->next->data;/ 将 P 所指的

48、结点的后继后继的值赋给n ext_ereturn OK;p=p->n ext;return ERROR;Status ListInsert(LinkList &L,int i,ElemTypeLin kList p=L->n ext,s;int j=0;if(i<=O|i>ListLe ngth(L)+1)return ERROR;while(j<i-1)j+;p=p->n ext;s=(L in kList)malloc(sizeof(LLNode); s->data=e;s->n ext=p->n ext;p_>n ext

49、=s;if(P=L)L=s; return OK;Status ListDelete(L in kList &L,i nt i,ElemType&e)Lin kList q,p=L->n ext;int j=0;if(!p|j>i-1)return ERROR;while(j<i-1)j+;计数器加1p=p->n ext;q=p->n ext;p_>n ext=q _>n ext;e=q->data; if(L=q)L=p;free(q); return OK;voidListTraverse(L in kListL,void(*

50、visit)(ElemType)Li nkList p=L-> next-next;/p指向表头结占八、while(p!=L->n ext)visit(p->data);p=p->n ext;prin tf("n");ListTraverse(L,pri nt);printf("前驱判断 n”);for(i=1;i<=10;i+) GetElem(L,i,e);把L中第i个元素的值赋 给ek=PriorElem(L,e,eO); 判断 e 是否有前驱 if(k=0)printf("元素 %d 无前驱 n",e);e

51、lseprintf("元素 %d 的前驱为 %dn",e,eO);printf("后继判断 n");for(i=1;i<=10;i+) GetElem(L,i,e);k=NextElem(L,e,e1);if(k=0)printf("元素 %d 无后继 n",e);elseprintf("元素 %d 的后继为 %dn",e,e1);5双向链表的基本操作5.1带头节点的双向链表void InitList(DuLinkList &L)/产生空间的双向循环链表L=(DuLi nkList)malloc(si

52、zeof(DuLLNode);if(L)L-> next=L->prior=L;elseexit(OVERFLOW);void ClearList(DuLi nkList L) /清空链表DuLi nkList p=L-> next;/p 指向第一个结占八、while(p!=L)p=p->n ext;free(p->prior);L-> next=L->prior=L;头结点的两个指针域指向其身void DestroyList(DuLi nkList &L)ClearList(L);/ 将 L 清空free(L);L=NULL;Status L

53、istEmpty(DuLi nkList L) /判断表是否为空if(L->n ext=L&&L->prior=L)return TRUE;elsereturn FALSE;int ListLe ngth(DuLi nkList L) /返回表的长度int i=0;DuLi nkList p=L-> next;/p 指向第一个结占八、while(p!=L)i+;p=p->n ext; return i;Status GetElem(DuLinkList L,int i,ElemType&e) /当第i个元素存在，将值赋给eint j=1;DuLi

54、 nkList p=L-> next;/p 指向第一个结占八、while(p!=L&&j<i) 顺指针向后查找，直 到p指向第i个元素j+;p=p->n ext;if(p=L|j>i)return ERROR;e=p_>data;return OK;intLocateElem(DuL in kListL,ElemTypee,Status(*compare)(ElemType,ElemType) /返回表中第1个与e满足关系compare() 的数据元素的位序int i=0;DuLin kList p=L->n ext;while(p!=L)/p未指向头结点i+;/计数器加1 if(compare(p->data,e)/ 找到这样的元 素return i;p=p->n ext;return 0;Status PriorElem(DuL in kListL,ElemTypecur_e,ElemType &pre_e)DuLinkList p=L->next-next;/p指向第