| 数据结构教程实验二链表基本操作的实现 | 您所在的位置：网站首页 › 插空法讲解 › 数据结构教程实验二链表基本操作的实现 |
数据结构教程实验二链表基本操作的实现
|
出chatgpt独享账号！内含120美元！仅需38元/个！独享永久使用！点击购买！ 实验二 链表基本操作的实现 一、实验目的 1 . 掌握线性表的链式存储结构及基本操作，深入了解链表的基本特性，以便在实际问题背景下灵活运用它们。 2.深入理解和灵活掌握链表的插入、删除等操作。 二、实验环境1.硬件：每个学生需配备计算机一台。 2.软件：Windows操作系统+Visual C++。 三、实验要求1.将建表、遍历、插入、删除分别定义为4个子函数，通过主函数实现对上述子函数的调用。 2.输入数据：链表中每个结点为结构体类型，数据域（data）设定为整型。 四、实验内容1.实现单链表各种基本运算 在实现单链表各种基本运算的基础上，设计主程序，完成如下功能： （1）初始化单链表h。 （2）依次采用尾插法插入12，25，7，9，10共5个元素。 （3）输出单链表h。 （4）输出单链表h的长度。 （5）判断单链表h是否为空。 （6）输出单链表h第4个元素。 （7）输出元素5的位置。 （8）在第4个元素的位置上插入元素100。 （9）输出单链表h。 （10）删除单链表h的第3个元素。 （11）输出单链表h。 （12）释放单链表h。 实现程序： #include #include typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LinkNode; //初始化单链表 void InitList(LinkNode *&L) { L=(LinkNode *)malloc(sizeof(LinkNode)); L->next=NULL; } //头插法建立单链表 void CreateListF(LinkNode *&L,ElemType a[],int n) { LinkNode *s; L=(LinkNode *)malloc(sizeof(LinkNode)); L->next=NULL; for(int i=0;idata=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)); L->next=NULL; r=L; for(int i=0;idata=a[i]; r->next=s; r=s; } r->next=NULL; } //单链表的销毁 void DestryList(LinkNode *&L) { LinkNode *pre=L,*p=pre->next; while(p!=NULL) { free(pre); pre=p; p=pre->next; } free(pre); } //判断单链表是否为空 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("%3d",p->data); p=p->next; } printf("\n"); } //求单链表中某个数据元素值 bool GetElem(LinkNode *L,int i,ElemType &e) { int j=0; LinkNode *p=L; if(idata; return true; } } //按元素值查找 int LocateElem(LinkNode *L,ElemType e) { int i=1; LinkNode *p=L->next; while (p!=NULL && p->data!=e) { p=p->next; i++; } if(p==NULL) return(0); else return(i); } //插入数据元素 bool ListInsert(LinkNode *&L,int i,ElemType e) { int j=0; LinkNode *p=L,*s; if(idata=e; s->next=p->next; p->next=s; return true; } } //删除数据元素 bool ListDelete(LinkNode *&L,int i,ElemType e) { int j=0; LinkNode *p=L,*q; if(inext; if(q==NULL) return false; e = q->data; p->next=q->next; free(q); return true; } } //设计主函数 void main() { LinkNode *h; ElemType e; printf("单链表的基本运算如下；\n"); printf("(1)初始化单链表h\n"); InitList(h); printf("(2)依次采用尾插法插入12，25，7，9，10共5个元素\n"); int i,y; char s; //循环输入，遇到回车停止输入 for(i=1;inext=NULL; } //头插法建立单链表 void CreateListF(LinkNode *&L,ElemType a[],int n) { LinkNode *s; L=(LinkNode *)malloc(sizeof(LinkNode)); L->next=NULL; for(int i=0;idata=a[i]; s->next=L->next; L->next=s; } } //插入数据元素 bool ListInsert(LinkNode *&L,int i,ElemType e) { int j=0; LinkNode *p=L,*s; if(idata=e; s->next=p->next; p->next=s; return true; } } //尾插法建立单链表 void CreateListR(LinkNode *&L,ElemType a[],int n) { LinkNode *s,*r; L=(LinkNode *)malloc(sizeof(LinkNode)); L->next=NULL; r=L; for(int i=0;idata=a[i]; r->next=s; r=s; } r->next=NULL; } //单链表的销毁 void DestryList(LinkNode *&L) { LinkNode *pre=L,*p=pre->next; while(p!=NULL) { free(pre); pre=p; p=pre->next; } free(pre); } //输出单链表 void DispList(LinkNode *L) { LinkNode *p=L->next; while(p!=NULL) { printf("%3d",p->data); p=p->next; } printf("\n"); } //就地逆置函数 void listReserve(LinkNode *L) { if (L == NULL ||L->next == NULL) return; LinkNode* p = L->next->next; L->next->next = NULL; while (p != NULL) { LinkNode* q = p->next; p->next = L->next; L->next = p; p = q; } } void main() { LinkNode *h; InitList(h); printf("依次采用尾插法插入12，25，7，9，10共5个元素\n"); int i,y; char s; //循环输入，遇到回车停止输入 for(i=1;inext=NULL; } //头插法建立单链表 void CreateListF(LinkNode *&L,ElemType a[],int n) { LinkNode *s; L=(LinkNode *)malloc(sizeof(LinkNode)); L->next=NULL; for(int i=0;idata=a[i]; s->next=L->next; L->next=s; } } //插入数据元素 bool ListInsert(LinkNode *&L,int i,ElemType e) { int j=0; LinkNode *p=L,*s; if(idata=e; s->next=p->next; p->next=s; return true; } } //尾插法建立单链表 void CreateListR(LinkNode *&L,ElemType a[],int n) { LinkNode *s,*r; L=(LinkNode *)malloc(sizeof(LinkNode)); L->next=NULL; r=L; for(int i=0;idata=a[i]; r->next=s; r=s; } r->next=NULL; } //单链表的销毁 void DestryList(LinkNode *&L) { LinkNode *pre=L,*p=pre->next; while(p!=NULL) { free(pre); pre=p; p=pre->next; } free(pre); } //排序 void Sort(LinkNode *&L) { LinkNode *p,*pre,*q; p=L->next->next; L->next->next=NULL; while(p!=NULL) { q=p->next; pre=L; while(pre->next!=NULL&&pre->next->datadata) { pre=pre->next; } p->next=pre->next; pre->next=p; p=q; } } //输出单链表 void DispList(LinkNode *L) { LinkNode *p=L->next; while(p!=NULL) { printf("%3d",p->data); p=p->next; } printf("\n"); } void main() { LinkNode *h; InitList(h); printf("依次采用尾插法插入12，25，7，9，10共5个元素\n"); int i,y; char s; //循环输入，遇到回车停止输入 for(i=1;inext=NULL; for(i=0;idata=a[i]; s->next=L->next; L->next=s; } s=L->next; while(s->next!=NULL) s=s->next; s->next=L; } //尾插法建立循环列表 void CreateListR(LinkNode *&L,ElemType a[],int n){ LinkNode *s,*r; int i; L=(LinkNode *)malloc(sizeof(LinkNode)); L->next=NULL; r=L; for(i=0;idata=a[i]; r->next=s; r=s; } r->next=L; } //初始化线性表 void InitList(LinkNode *&L){ L=(LinkNode *)malloc(sizeof(LinkNode)); L->next=L; } //销毁线性表 void DestoyList(LinkNode *&L){ LinkNode *pre=L,*p=pre->next; while(p!=L){ free(pre); pre=p; p=pre->next; } free(pre); } //输出线性表 void DispList(LinkNode *L){ LinkNode *p=L->next; while(p!=L){ printf("%d\t",p->data); p=p->next; } printf("\n"); } //插入元素 bool ListInsert(LinkNode *&L,int i,ElemType e){ int j=1; LinkNode *p=L,*s; if(inext==L || i==1){ s=(LinkNode *)malloc(sizeof(LinkNode)); s->data=e; s->next=p->next; p->next=s; return true; } else{ p=L->next; while(jnext; } if(p==L) 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){ int j=1; LinkNode *p=L,*q; if(inext==L) return false; if(i==1){ q=L->next; e=q->data; L->next=q->next; free(q); return true; } else{ p=L->next; while(jnext; } if(p==L) return false; else{ q=p->next; e=q->data; p->next=q->next; free(q); return true; } } } //主函数 void main(){ LinkNode *h; ElemType e; InitList(h); printf("依次采用尾插法插入12，25，7，9，10共5个元素\n"); int i,y; char s; //循环输入，遇到回车停止输入 for(i=1;inext=NULL; for(int i=0;idata=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)); L->next=NULL; r=L; for(int i=0;idata=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=pre->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){ DLinkNode *p=L; int i=0; while(p->next!=L){ i++; p=p->next; } return(i); } //输出线性表 void DispList(DLinkNode *L){ DLinkNode *p=L->next; while(p!=L){ printf("%d\t",p->data); p=p->next; } printf("\n"); } //求线性表中第i个元素 bool GetElem(DLinkNode *L,int i,ElemType &e){ int j=1; DLinkNode *p=L->next; if(inext==L) return false; if(i==1){ e=L->next->data; return true; } else{ while(jnext; } if(p==L) return false; else{ e=p->data; return true; } } } //插入第i个元素 bool ListInsert(DLinkNode *&L,int i,ElemType e){ int j=1; DLinkNode *p=L,*s; if(inext==L){ 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(jnext; } 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=p; p->next=s; return true; } } } //删除第i个元素 bool ListDelete(DLinkNode *&L,int i,ElemType &e){ int j=1; DLinkNode *p=L,*q; if(inext==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(jnext; } if(p==NULL) 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; } } } //主函数 void main(){ DLinkNode *h; ElemType e; printf("循环双链表的基本运算如下；\n"); printf("(1)初始化循环双表h\n"); InitList(h); printf("(2)依次采用尾插法插入12，25，7，9，10共5个元素\n"); ListInsert(h,1,12); ListInsert(h,2,25); ListInsert(h,3,7); ListInsert(h,4,9); ListInsert(h,5,10); printf("(3)输出循环双链表h:"); DispList(h); printf("(4)循环双链表h的长度:%d\n",ListLength(h)); printf("(5)循环双链表h为%s\n",(ListEmpty(h)?"空":"非空")); GetElem(h,4,e); printf("(6)输出循环双链表h第4个元素%d\n",e); printf("(7)在第4个元素的位置上插入元素100\n"); ListInsert(h,4,100); printf("(8)输出循环双链表h"); DispList(h); printf("(9)删除循环双链表h的第3个元素\n"); ListDelete(h,3,e); printf("(10)输出循环双链表h"); DispList(h); printf("(11)释放循环双链表h"); DestroyList(h); }运行结果：
测试结果： 通过！ 六、实验总结通过本次实验学习了怎样实现单链表各种基本运算和实现单链表h就地逆置的操作以及单链表h中的元素按递增有序排列。同时学习了循环链表，并且实现插入、删除操作和双向循环链表，并实现双向循环链表基本操作。每种列表大致代码相同只是有些子函数和声明列表时不同。在错误中寻找经验，一个程序的顺利完成有很多次错误更改错误也是一种经验。 |
【本文地址】
公司简介
联系我们