2022年单链表实验 .pdf

《2022年单链表实验 .pdf》由会员分享，可在线阅读，更多相关《2022年单链表实验 .pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验二单链表实验一、实验目的1、掌握用 Visual C+6.0上机调试单链表的基本方法2、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现二、实现内容1、单链表基本操作的实现 问题描述 要在带头结点的单链表h中第 i 个数据元素之前插入一个数据元素x，首先需要在单链表中寻找到第 i-1 个结点并用指针p指示，然后申请一个由指针s 指示的结点空间，并置 x为其数据域值，最后修改第i-1 个结点，并使 x结点的指针指向第i 个结点，要在带头结点的单链表h中删除第 i 个结点，首先要计数寻找到第i 个结点并使指针p指向其前驱第 i-1 个结点，然后删除第i 个结点并释放被删除结点

2、空间。基本要求 用链式存储结构实现存储 实现提示 链式存储结构不是随机存储结构，即不能直接取到单链表中某个结点，而要从单链表的头结点开始一个一个地计数寻找。2、求表长以及有序单链表的合并算法的实现 问题描述 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并计算表长。要求利用原来两个单链表的结点存放归并后的单链表。基本要求 用链式存储结构实现存储实验代码#include#include#define null 0/-定义节点-typedef struct List int data;struct List*next;L

3、ist;/-构造链表-List*InitList(int n)int i;List*head,*p,*q;head=(List*)malloc(sizeof(List);/构造头结点 if(!head)exit(0);/判断是否成功分配内存 q=head;head-data=0;/记录链表长度 head-next=null;for(i=0;inext=head-next;head-next=p;名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 7 页 -*/-/-尾插-p-next=q-next;q-next=p;q=p;head-data+;/长度自增 printf(输入数据第%

4、d 个数据:n,head-data);scanf(%d,&(p-data);return head;/-插入-void Insert(List*head,int position,int elem)int i;List*p,*q;if(positionhead-data+1)printf(插入位置非法!);exit(0);p=head;for(i=1;inext;q=(List*)malloc(sizeof(List);q-data=elem;q-next=p-next;p-next=q;head-data+;printf(成功将%d 插入到第%d 个位置!n,elem,position);/

5、-删除-void Delete(List*head,int position)int i;List*p,*q;if(!head)printf(链表为空!);exit(0);p=head;q=p-next;名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 7 页 -if(positionhead-data)printf(非法位置!);exit(0);for(i=1;inext;q=p-next;p-next=q-next;printf(成功删除第%d 个位置上的元素:%dn,position,q-data);free(q);head-data-;/-排序（由小到大）-void sor

6、t(List*head)int temp;List*p,*q;for(p=head-next;(p-next)&(head-data1);p=p-next)for(q=p-next;q;q=q-next)if(q-datadata)temp=p-data;p-data=q-data;q-data=temp;/-有序合并-void Unite_List(List*head,List*nhead)int n=0;List*p,*q,*pre;sort(head);sort(nhead);pre=head;p=pre-next;q=nhead-next;while(q)名师资料总结-精品资料欢迎下载

7、-名师精心整理-第 3 页，共 7 页 -if(!p)pre-next=q;head-data+=nhead-data;break;else if(q-datadata)/nhead表中当前元素小于head当前元素,插入其前面 nhead-next=q-next;/nhead链表头指针跳过 q后移nhead-data-;q-next=p;/接入后继 pre-next=q;/接入前驱head-data+;pre=q;p=pre-next;q=nhead-next;else pre=p;p=pre-next;free(nhead);/-查找位置-void Search_Position(List*

8、head,int elem)int i,position;List*p;p=head;if(!head)printf(链表为空!);exit(0);for(i=1;idata;i+)p=p-next;if(elem=p-data)position=i;printf(发现元素%d 在表中的位置:%dn,elem,position);exit(0);名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 7 页 -printf(在表中未发现元素%dn,elem);/-查找元素-void Search_Element(List*head,int position)int i;List*p;p=

9、head;if(!head)printf(链表为空!);exit(0);if(positionhead-data)printf(非法位置!);exit(0);for(i=1;inext;printf(第%d 个位置的元素为:%dn,position,p-data);/return p-data;/-遍历-void ShowMessage(List*head)List*p;int i;p=head;if(!head)/判空 printf(链表为空!);exit(0);for(i=0;idata;i+)if(i%5=0)printf(n);p=p-next;printf(%d,p-data);名师

10、资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 7 页 -printf(n);/-求表长度-int GetLength(List*head)int length;if(!head)printf(链表为空!);exit(0);length=head-data;return length;/-销毁链表-void Destroy(List*head)int i;List*p;/if(!head)printf(链表不存在!);exit(0);/p=head-next;for(i=0;idata;i+)free(head);head=p;p=p-next;free(head);printf(成

11、功销毁链表!n);/-主函数-void main()int length;/记录长度 List*head1,*head2;head1=InitList(7);/构造长度为 7的链表 head2=InitList(9);名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 7 页 -ShowMessage(head1);/遍历链表 length=GetLength(head1);/获取长度printf(表长为:%dn,length);Insert(head1,4,11);/插入一个元素ShowMessage(head1);/遍历链表length=GetLength(head1);/获取新

12、长度printf(表长为:%dn,length);Search_Element(head1,3);/按位置查找元素Delete(head1,2);/删除元素length=GetLength(head1);/获取新长度printf(表长为:%dn,length);ShowMessage(head1);Search_Position(head1,6);/查找元素位置sort(head1);/对链表 head1排序printf(排序后!n);ShowMessage(head1);/输出排序后的数据 Unite_List(head1,head2);/合并printf(合并后!n);length=GetLength(head1);/获取长度printf(表长为:%dn,length);ShowMessage(head1);/显示合并后的数据Search_Position(head1,6);/查找合并后的位置Destroy(head1);/销毁链表 名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 7 页 -