线性表链式存储结构及实现

一、目的

掌握线性表的脸是存储结构及运算熟悉循环链表及双链表线性表的基本运算

二、内容

编写一个程序cdlinklist.cpp,实现循环双链表的各种基本运算和整体建表算法（假设循环双链表的元素类型ElemType为char），并在此基础上设计一个主程序，完成如下功能： （1）初始化循环双链表h （2）依次采用尾插法插入a,b,c,d,e元素 （3）输出循环双链表h （4）输出循环双链表h长度 （5）判断顺序表h是否为空 （6）输出循环双链表h的第3个元素 （7）输出元素a的位置 （8）在第4个元素位置上插入f元素 （9）输出循环双链表h （10）删除循环双链表h的第3个元素 （11）输出循环双链表h （12）释放循环双链表h编写一个程序exe2-7.cpp,实现这样的功能：令L1=(x1,x2,…，xn)，L2=（y1，y2，…，ym）是两个线性表，采用带头结点的单链表存储，设计一个算法合并L1、L2，结果放在线性表L3中，要求如下：

L3=（x1，y1，x2，y2，…，xm，ym，xm+1，…，xn）当m<=n时 L3=（x1，y1，x2，y2，…，xn，yn，yn+1，…，yn）当m>n时 L3仍采用单链表存储，算法的空间复杂度为O(1)。

三、源代码

循环双链表 #include<stdio.h> #include<malloc.h> typedef char ElemType; typedef struct DNode { ElemType data; struct DNode *prior; struct DNode *next; }DLinkNode; void CreateListF(DLinkNode *&L,ElemType a[],int n) { DLinkNode *s; L=(DLinkNode *)malloc(sizeof(DLinkNode)); L->next=NULL; for(int i=0;i<n;i++) { s=(DLinkNode *)malloc(sizeof(DLinkNode)); s->data=a[i]; s->next=L->next; if(L->next!=NULL) L->next->prior=s; L->next=s;s->prior=L; } s=L->next; while(s->next!=NULL) s=s->next; s->next=L; L->prior=s; } void CreateListR(DLinkNode *&L,ElemType a[],int n) { DLinkNode *s,*r; L=(DLinkNode *)malloc(sizeof(DLinkNode)); r=L; for(int i=0;i<n;i++) { s=(DLinkNode *)malloc(sizeof(DLinkNode)); s->data=a[i]; r->next=s;s->prior=r; r=s; } r->next=L; L->prior=r; } void InitList(DLinkNode *&L) { L=(DLinkNode *)malloc(sizeof(DLinkNode)); L->prior=L->next=L; } void DestroyList(DLinkNode *&L) { DLinkNode *pre=L,*p=L->next; while(p!=L) { free(pre); pre=p; p=pre->next; } free(pre); } bool ListEmpty(DLinkNode *L) { return(L->next==L); } int ListLength(DLinkNode *L) { int i=0; DLinkNode *p=L; while(p->next!=L) { i++; p=p->next; } return(i); } void DispList(DLinkNode *L) { DLinkNode *p=L->next; while(p!=L) { printf("%c ",p->data); p=p->next; } printf("\n"); } bool GetElem(DLinkNode *L,int i,ElemType &e) { int j=1; DLinkNode *p=L->next; if(i<=0||L->next==L) return false; if(i==1) { e=L->next->data; return true; } else { while(j<i&&p!=L) { j++; p=p->next; } if(p==NULL) return false; else { e=p->data; return true; } } } int LocateElem(DLinkNode *L,ElemType e) { int i=1; DLinkNode *p=L->next; while(p!=L&&p->data!=e) { i++; p=p->next; } if(p==L) return 0; else return i; } bool ListInsert(DLinkNode *&L,int i,ElemType e) { DLinkNode *p=L,*s; int j=1; if(i<=0)return false; if(p->next==NULL||i==1) { s=(DLinkNode *)malloc(sizeof(DLinkNode)); s->data=e; p->next=s;s->next=p; p->prior=s;s->prior=p; return true; } else if (i==1) { s=(DLinkNode *)malloc(sizeof(DLinkNode)); s->data=e; s->next=p->next;p->next=s; s->next->prior=s;s->prior=p; return true; } else { p=L->next; while(j<i-2&&p!=L) { j++; p=p->next; } if(p==L) return false; else { s=(DLinkNode *)malloc(sizeof(DLinkNode)); s->data=e; s->next=p->next; if(p->next!=NULL)p->next->prior=s; s->prior=s; p->next=s; return true; } } } bool ListDelete(DLinkNode *&L,int i,ElemType &e) { DLinkNode *p=L,*q; int j=1; if(i<=0||L->next==L) return false; if(i==1) { q=L->next; e=q->data; L->next=q->next; q->next->prior=L; free(q); return true; } else { p=L->next; while(j<=i-2&&p!=L) { j++; p=p->next; } if(p==L) return false; else { q=p->next; if(q==NULL)return 0; e=q->data; p->next=q->next; if(p->next!=NULL)p->next->prior=p; free(q); return true; } } } int main() { DLinkNode *h; ElemType e; printf("循环双链表的基本运算如下：\n"); printf(" (1)初始化循环双链表h\n"); InitList(h); printf(" (2)依次插入a、b、c、d、e元素\n"); ListInsert(h,1,'a'); ListInsert(h,2,'b'); ListInsert(h,3,'c'); ListInsert(h,4,'d'); ListInsert(h,5,'e'); printf(" (3)输出循环双链表h:"); DispList(h); printf(" (4)循环双链表h长度：%d\n",ListLength(h)); printf(" (5)循环双链表h为%s\n",(ListEmpty(h)?"空":"非空")); GetElem(h,3,e); printf(" (6)循环双链表h的第3个元素:%c\n",e); printf(" (7)元素a的位置:%d\n",LocateElem(h,'a')); printf(" (8)在第4个元素位置上插入f元素\n"); ListInsert(h,4,'f'); printf(" (9)输出循环双链表h：");DispList(h); printf(" (10)删除h的第3个元素\n"); ListDelete(h,3,e); printf(" (11)输出循环双链表h：");DispList(h); printf(" (12)释放循环双链表h\n"); DestroyList(h); return 0; } 单链表合并 #include<stdio.h> #include<malloc.h> typedef char ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LinkNode; void CreateListF(LinkNode *&L,ElemType a[],int n) { LinkNode *s; L=(LinkNode *)malloc(sizeof(LinkNode)); L->next=NULL; for(int i=0;i<n;i++) { s=(LinkNode *)malloc(sizeof(LinkNode)); s->data=a[i]; s->next=L->next; L->next=s; } } void CreateListR(LinkNode *&L,ElemType a[],int n) { LinkNode *s,*r; L=(LinkNode *)malloc(sizeof(LinkNode)); r=L; for(int i=0;i<n;i++) { s=(LinkNode *)malloc(sizeof(LinkNode)); s->data=a[i]; r->next=s; r=s; } r->next=NULL; } void InitList(LinkNode *&L) { L=(LinkNode *)malloc(sizeof(LinkNode)); L->next=NULL; } void DestroyList(LinkNode *&L) { LinkNode *pre=L,*p=L->next; while(p!=NULL) { free(pre); pre=p; p=p->next; } free(p); } bool ListEmpty(LinkNode *L) { return(L->next==NULL); } int ListLength(LinkNode *L) { int i=0; LinkNode *p=L; while(p->next!=NULL) { i++; p=p->next; } return(i); } void DispList(LinkNode *L) { LinkNode *p=L->next; while(p!=NULL) { printf("%c ",p->data); p=p->next; } printf("\n"); } bool GetElem(LinkNode *L,int i,ElemType &e) { int j=0; LinkNode *p=L; if(i<=0)return false; while(j<i&&p!=NULL) { j++; p=p->next; } if(p==NULL) return false; else { e=p->data; return true; } } int LocateElem(LinkNode *L,ElemType e) { int i=1; LinkNode *p=L; while(p!=NULL&&p->data!=e) { i++; p=p->next; } if(p==NULL) return 0; else return i; } bool ListInsert(LinkNode *&L,int i,ElemType e) { LinkNode *p=L,*s; int j=0; if(i<=0)return false; while(j<i-1&&p!=NULL) { j++; p=p->next; } if(p==NULL) return false; else { s=(LinkNode *)malloc(sizeof(LinkNode)); s->data=e; s->next=p->next; p->next=s; return true; } } bool ListDelete(LinkNode *&L,int i,ElemType &e) { LinkNode *p=L,*q; int j=0; if(i<=0)return false; while(j<i-1&&p!=NULL) { j++; p=p->next; } if(p==NULL) return false; else { q=p->next; if(q==NULL) return false; e=p->next->data; p->next=q->next; free(q); return true; } } void Merge(LinkNode *L1,LinkNode *L2,LinkNode *&L3) { LinkNode *p=L1->next,*q=L2->next,*r; L3=L1; r=L3; free(L2); while(p!=NULL&&q!=NULL) { r->next=p;r=p;p=p->next; r->next=q;r=q;q=q->next; } r->next=NULL; if(q!=NULL)p=q; r->next=p; } int main() { LinkNode *L1,*L2,*L3; ElemType a[]="abcdefgh"; int n=8; CreateListR(L1,a,n); printf("L1:");DispList(L1); ElemType b[]="12345"; n=5; CreateListR(L2,b,n); printf("L2:");DispList(L2); printf("L1和L2合并产生L3\n"); Merge(L1,L2,L3); printf("L3:");DispList(L3); DestroyList(L3); return 0; }

备注： 有问题可以评论，看到后我会尽力及时回复的，谢谢！