实验二 顺序表与链表

实验报告：使用三种存储结构（顺序表、链表、静态链表）求解Josephus问题一、实验目的掌握顺序表、链表和静态链表的基本操作和实现方法。

学习如何使用不同的存储结构解决同一问题，并分析其性能差异。

通过求解Josephus问题，加深对数据结构在实际问题中应用的理解。

二、实验内容问题描述：Josephus问题是著名的理论问题。

在罗马人占领乔塔帕特后，n个犹太人与他们的妻子和孩子被一个圈子所包围，圈中第一个人从1开始报数，每数到m的那个人就被杀死，然后再由他的下一个人从1开始重新报数，直到剩下最后一个人为止，那个人就被称为Josephus。

本实验要求使用顺序表、链表和静态链表三种存储结构求解Josephus问题。

顺序表求解Josephus问题：使用数组作为顺序表存储结构，通过循环遍历数组实现报数和杀人过程。

当杀死某个人时，将其后的人依次向前移动填补空位。

重复此过程直到只剩下一个人为止。

链表求解Josephus问题：使用链表作为存储结构，通过链表的遍历实现报数和杀人过程。

当杀死某个人时，将其从链表中删除。

重复此过程直到链表中只剩下一个节点为止。

静态链表求解Josephus问题：使用静态链表作为存储结构，通过数组模拟链表操作。

在静态链表中，每个节点包含数据域和游标域。

通过游标域实现节点间的链接关系。

通过遍历静态链表实现报数和杀人过程，当杀死某个人时，修改其前后节点的链接关系以删除该节点。

重复此过程直到静态链表中只剩下一个节点为止。

三、实验结果与分析实验结果：使用顺序表求解Josephus问题时，时间复杂度较高，因为每次杀人后都需要移动大量元素来填补空位。

空间复杂度较低，只需一个大小为n的数组。

使用链表求解Josephus问题时，时间复杂度较低，因为删除节点时只需修改相邻节点的指针。

空间复杂度与顺序表相当，但需要额外的指针空间来存储节点间的链接关系。

使用静态链表求解Josephus问题时，时间复杂度和空间复杂度与链表相似。

实验1、2：线性表的应用参考代码一、实验预备知识1．复习C中编写函数的相关内容。

2．复习如何用主函数将多个函数连在一起构成一个C完整程序。

二、实验目的1．掌握线性表的顺序和链式存储结构2．熟练运用线性表在顺序存储方式下的初始化、创建、输出、插入和删除运算3．熟练运用线性表在链式存储方式下的创建、输出、插入和删除运算三、实验要求1．编写初始化并创建线性表和输出线性表的算法。

2．编写对线性表插入和删除运算算法，要判断位置的合法性和溢出问题。

3．编写有序表的插入和删除运算算法。

4．编写一个主函数，将上面函数连在一起，构成一个完整的程序。

5．将实验源程序调试并运行，写出输入、输出结果，并对结果进行分析。

四、实验内容顺序表实验内容：1．给定的线性表为L=（12，25，7，42，19，38），元素由键盘输入。

2．初始化并建立顺序表。

（开辟的存储空间大小为8）3．编写顺序表输出算法。

4．依次插入3、21、15、99四个数，分别插入在第1、8、4和12位置，每插入一次都要输出一次顺序表。

5．删除第1，第9和第12个位置上的元素，每删除一个元素都要输出一次顺序表。

6．编写一个排序算法，对线性表中元素从小到大排列。

7．向有序表分别插入20和50，插入后表仍然有序。

（修改开辟的存储空间大小为15）单链表实验内容：1．给定的线性表为L=（12，25，7，42，19，38），元素由键盘输入。

2．建立一个带表头结点的单链表（前插入法和尾插入法均可）。

3．编写单链表输出算法。

4．依次插入3、21、15、99四个数，分别插入在第1、8、4和12位置，每插入一次都要输出一次单链表。

5．删除第1，第9和第12个位置上的元素，每删除一个元素都要输出一次单链表。

6．编写一个排序算法，对链表中元素从小到大排列。

7．向有序链表分别插入20和50，插入后表仍然有序。

五、实验结果顺序表源程序：#include <iostream>using namespace std;const int MAXSIZE=8; //做有序表插入操作时，将8改为15typedef int DataType;typedef struct{DataType data[MAXSIZE];int length;}SeqList;void Init_SeqList(SeqList &L);//创建空顺序表算法void Show_SeqList(SeqList L);//顺序表输出算法void Create_SeqList(SeqList &L);//顺序表创建算法int Insert_SeqList(SeqList &L,DataType x,int i);//顺序表的插入算法int Delete_SeqList(SeqList &L,int i);//顺序表的删除算法int Locate_SeqList(SeqList L,DataType x);//顺序表的按值查找算法void Sort_SeqList(SeqList &L);//顺序表的排序算法int Insert_SeqList_sort(SeqList &L,DataType x);//有序表的插入算法void Merge(SeqList LA,SeqList LB,SeqList &LC);//两个有序顺序表的合并算法void menu(); //菜单算法void main(){ menu(); }void menu()//菜单算法{SeqList L;Init_SeqList(L);int m;while(1){cout<<"\n根据所做操作选择以下数字序号："<<endl;cout<<"1:创建顺序表2:执行插入操作3:执行删除操作"<<endl;cout<<"4:执行输出操作5:执行查找操作6:执行排序操作"<<endl;cout<<"7:执行有序表的插入操作8:执行有序表的合并操作0:退出"<<endl;int n,i,x;cin>>n;switch (n){case 1:{Create_SeqList(L);break;}case 2:{cout<<"请输入插入位置：";cin>>i;cout<<endl<<"请输入插入元素值：";cin>>x;cout<<endl;m=Insert_SeqList(L,x,i);if (m==1)cout<<"插入操作成功！"<<endl;elseif (m==0)cout<<"插入位置不合法！"<<endl;elsecout<<"发生溢出！"<<endl;break;}case 3:{cout<<"请输入删除位置：";cin>>i;cout<<endl;m=Delete_SeqList(L,i);if (m==1)cout<<"删除操作成功！"<<endl;elseif (m==0)cout<<"删除位置不合法！"<<endl;elsecout<<"空表！"<<endl;break;}case 4:{Show_SeqList(L);break;}case 5:{cout<<"请输入所要查找的元素值：";cin>>x;cout<<endl;m=Locate_SeqList(L,x);if (m==0)cout<<"所查找元素不在顺序表中！"<<endl;elsecout<<"所查找元素是顺序表的第"<<m<<"个元素！"<<endl;break;}case 6:{Sort_SeqList(L);cout<<"排序操作完成！"<<endl;break;}case 7:{cout<<endl<<"请输入插入元素值：";cin>>x;cout<<endl;m=Insert_SeqList_sort(L,x);if (m==1)cout<<"插入操作成功！"<<endl;elsecout<<"发生溢出！"<<endl;break;}case 8:{SeqList L1,L2,L3;Init_SeqList(L1);Init_SeqList(L2);Init_SeqList(L3);cout<<"创建有序表1："<<endl;Create_SeqList(L1);Sort_SeqList(L1);cout<<"创建有序表2："<<endl;Create_SeqList(L2);Sort_SeqList(L2);cout<<"有序表1："<<endl;Show_SeqList(L1);cout<<"有序表2："<<endl;Show_SeqList(L2);Merge(L1,L2,L3);cout<<"合并后："<<endl;Show_SeqList(L3);break;}case 0:return;}}void Init_SeqList(SeqList &L)//创建空顺序表算法{L.length=0;}void Show_SeqList(SeqList L)//顺序表输出算法{if(L.length==0)cout<<"空表！"<<endl;elsefor(int i=0;i<L.length;i++)cout<<L.data[i]<<" ";cout<<endl;}void Create_SeqList(SeqList &L)//顺序表创建算法{cout<<"请输入元素个数:";cin>>L.length;cout<<"依次输入各个元素的值:"<<endl;for(int i=0;i<L.length;i++)cin>>L.data[i];}int Insert_SeqList(SeqList &L,DataType x,int i)//顺序表的插入算法{if(MAXSIZE<=L.length)return -1;if(i<1||i>L.length+1)return 0;for(int j=L.length-1;j>=i-1;j--)L.data[j+1]=L.data[j];L.data[i-1]=x;L.length++;return 1;}int Delete_SeqList(SeqList &L,int i)//顺序表的删除算法{if(L.length ==0)return -1;if(i<1||i>L.length)return 0;for(int j=i;j<L.length;j++)L.data[j-1]=L.data[j];L.length--;return 1;int Locate_SeqList(SeqList L,DataType x)//顺序表的按值查找算法{int i=0;while(i<L.length&&L.data[i]!=x)i++;if(i<L.length )return i+1;elsereturn 0;}void Sort_SeqList(SeqList &L) //排序算法{int i,k,j;DataType temp;for(i=0;i<L.length-1;i++){k=i;for(j=i+1;j<=L.length -1;j++)if(L.data [j]<L.data [k])k=j;if(i!=k){temp=L.data [i];L.data [i]=L.data [k];L.data [k]=temp;}}}int Insert_SeqList_sort(SeqList &L,DataType x)//有序表的插入算法{if(MAXSIZE<=L.length)return -1;int i=0;while(i<L.length&&L.data[i]<x)i++;for(int j=L.length-1;j>=i;j--)L.data[j+1]=L.data[j];L.data[i]=x;L.length++;return 1;}void Merge(SeqList LA,SeqList LB,SeqList &LC)//两个有序顺序表的合并算法{int i,j,k;i=j=k=0;while(i<LA.length&&j<LB.length){if(LA.data[i]<LB.data[j]){LC.data[k]=LA.data[i];i++;k++;}else{LC.data[k]=LB.data[j];j++;k++;}}while(i<LA.length){LC.data[k]=LA.data[i];i++;k++;}while(j<LB.length){LC.data[k]=LB.data[j];j++;k++;}LC.length=k;}输入输出结果：图1-1主菜单图1-2顺序表的创建和输出操作图1-3 顺序表的插入操作图1-4顺序表的删除操作图1-5顺序表的排序操作图1-6有序表的插入操作图1-7两个有序表的合并操作单链表的源程序：#include "iostream"using namespace std;typedef int DataType;typedef struct node{DataType data;struct node *next;}LNode,*LinkList;void Init_LinkList(LinkList &L);//创建空单链表void Create1LinkList(LinkList &L,int n);//前插入法创建单链表的算法void Create2LinkList(LinkList &L,int n);//后插入法创建单链表的算法void PrintLinkList(LinkList L);//单链表的输出算法int InsertLinkList(LinkList &L,int i,DataType x);//单链表的插入算法int DeleteLinkList(LinkList &L,int i);//单链表的删除算法void Select_Sort_LinkList(LinkList &L);//链表的排序算法（选择排序）void Insert2(LinkList L,DataType x);//有序表的插入void Merge(LinkList L1,LinkList L2,LinkList &L3);//两个有序表的合并算法void menu();//菜单函数int main(){menu();return 0;}void Init_LinkList(LinkList &L)//创建空单链表{L=new LNode;L->next=NULL;}void Create1LinkList(LinkList &L,int n)//前插入法创建单链表的算法{LNode *s;for(int i=1;i<=n;i++){s=new LNode;cout<<"请输入第"<<i<<"个元素的值：";cin>>s->data;s->next=L->next;L->next=s;}}void Create2LinkList(LinkList &L,int n)//后插入法创建单链表的算法{LNode *s,*r=L;for(int i=1;i<=n;i++){s=new LNode;cout<<"请输入第"<<i<<"个元素的值：";cin>>s->data;r->next=s;r=s;}r->next=NULL;}void PrintLinkList(LinkList L)//单链表的输出算法{if(L->next==NULL){cout<<"空表！"<<endl;return;}cout<<"当前单链表为："<<endl;LNode *p=L->next;while(p){cout<<p->data<<" ";p=p->next;}cout<<endl;}int InsertLinkList(LinkList &L,int i,DataType x)//单链表的插入算法{int j=0;LNode *p=L,*s;while(p&&j<i-1){p=p->next;j++;}if(!p||j>i-1)return 0;s=new LNode;s->data=x;s->next =p->next ;p->next =s;return 1;}int DeleteLinkList(LinkList &L,int i)//单链表的删除算法{if(L->next ==NULL)return -1;int j=0;LNode *p=L,*q;while((p->next !=NULL)&&(j<i-1)){p=p->next ;j++;}if((p->next==NULL)||(j>i-1))return 0;q=p->next ;p->next =q->next ;delete q;return 1;}void Select_Sort_LinkList(LinkList &L)//链表的排序算法（选择排序）{if(L->next ==NULL){cout<<"空表，不需要排序！"<<endl;return;}LNode *p,*q,*s;DataType temp;if(L->next==NULL) return;for(p=L->next;p->next!=NULL;p=p->next){s=p;for(q=p->next;q!=NULL;q=q->next){if(q->data<s->data)s=q;}if(s!=p){temp=s->data; s->data=p->data; p->data=temp;}}cout<<"排序成功！"<<endl;}void Insert2(LinkList L,DataType x)//有序表的插入{LNode *p=L,*s;while(p->next!=NULL&&p->next->data<x)p=p->next;s=new LNode;s->data=x;s->next=p->next;p->next=s;cout<<"插入操作成功！"<<endl;}void Merge(LinkList L1,LinkList L2,LinkList &L3)//两个有序表的合并算法{LNode *p1,*p2,*p3,*s;p1=L1->next ;p2=L2->next ;L3=p3=new LNode;L3->next =NULL;while(p1&&p2){s=new LNode;if(p1->data <p2->data ){s->data =p1->data ;p1=p1->next ;}else{s->data =p2->data ;p2=p2->next ;}p3->next =s;p3=s;}if(p1)p3->next =p1;if(p2)p3->next =p2;}void menu()//菜单函数{LinkList L;Init_LinkList(L);int m;while(1){cout<<"\n根据所做操作选择以下数字序号："<<endl;cout<<"1:前插入创建单链表2:尾插入创建单链表3:执行插入操作"<<endl;cout<<"4:执行删除操作5:执行输出操作6:执行排序操作"<<endl;cout<<"7:执行有序表的插入操作8:执行有序表的合并操作0:退出"<<endl;int n,i,x;cin>>n;switch (n){case 1:{cout<<"请输入结点个数：";cin>>i;Create1LinkList(L,i);PrintLinkList(L);break;}case 2:{cout<<"请输入结点个数：";cin>>i;Create2LinkList(L,i);PrintLinkList(L);break;}case 3:{cout<<"请输入插入位置：";cin>>i;cout<<endl<<"请输入插入元素值：";cin>>x;cout<<endl;if (InsertLinkList(L,i,x)==1)cout<<"插入操作成功！"<<endl;elsecout<<"插入位置不合法！"<<endl;break;}case 4:{cout<<"请输入删除位置：";cin>>i;cout<<endl;m=DeleteLinkList(L,i);if (m==1)cout<<"删除操作成功！"<<endl;elseif(m==-1)cout<<"空表！"<<endl;elsecout<<"删除位置不合法！"<<endl;break;}case 5:{PrintLinkList(L);break;}case 6:{Select_Sort_LinkList(L);break;}case 7:{cout<<endl<<"请输入插入元素值：";cin>>x;cout<<endl;Insert2(L,x);break;}case 8:{LinkList L1,L2,L3;Init_LinkList(L1);Init_LinkList(L2);Init_LinkList(L3);cout<<"创建有序表1："<<endl;cout<<"请输入结点个数：";cin>>i;Create2LinkList(L1,i);Select_Sort_LinkList(L1);cout<<"创建有序表2："<<endl;cout<<"请输入结点个数：";cin>>i;Create2LinkList(L2,i);Select_Sort_LinkList(L2);cout<<"有序表1："<<endl;PrintLinkList(L1);cout<<"有序表2："<<endl;PrintLinkList(L2);Merge(L1,L2,L3);cout<<"合并后："<<endl;PrintLinkList(L3);break;}case 0:return;}}}输入输出结果：图2-1主菜单图2-2创建单链表（用头插入法）图2-3创建单链表（用尾插入法）图2-4单链表的插入操作图2-5单链表的插入操作（插入位置不合法情况）图2-6单链表的删除操作图2-7单链表的删除操作（删除位置不合法情况）图2-8单链表的排序操作图2-9有序表的插入操作图2-10两个有序表的合并操作建议：代码较长，为了方便阅读和调试，可写成多文件结构！。

实验报告课程名称数据结构实验项目实验一线性表的生成与操作题目一顺序表和链表的创建与基本操作系别___ _计算机学院 _ ______专业__ __计算机大类_ __班级/学号__(1406/2014011288)_____学生姓名 _______(孙文学)_________实验日期_（2015年10月19日）成绩_______________________指导教师黄改娟实验题目：实验一线性表的生成与操作------顺序表和链表的创建与基本操作（自己所选择实验题目，必填）一、实验目的1)掌握线性表的顺序存储和链式存储结构；2)验证顺序表及链表的基本操作的实现；(验证)3)理解算法与程序的关系，能够将算法转换为对应程序；4)体会线性表在实际应用中能够解决的问题。

（设计、综合）二、实验内容1)根据实验一题目列表，选定题目，说明题目的主要需求；2)结合所选定的题目，定义存储结构，并完成对应应用的线性表创建、插入、删除、查找等基本操作的算法描述；3)程序编码实现，并获得运行结果。

三、报告内容1)实验题目及主要存储结构定义（提示：请根据所选定题目，描述存储结构）题目：顺序表和链表的创建及基本操作顺序表我是采用数组存储的，链表是采用结构体存储的2)结合题目，说明对相应线性表的基本操作算法描述（提示：可用自然语言、流程图、伪代码等均可，要求对每一个操作，都给出具体的算法描述）基本操作：#顺序表#（1）插入：在线性表中的x位置插入y----将x位置及之后的元素都往后挪一位，将y的值赋给a[x].（2）删除：删除位置为x的元素----另y=a[x],然后x之后的元素都往前挪一位。

（3）查找：寻找值为y的元素----从a[0]开始，若a[i]==y，则返回i，否则i++。

#链表#（1）插入：当i小于要插入的位置x时，i++，插入p->data------p->next=s->next;s->next=p;（2）删除：当p->data不等于要删除的值x时，p=p->next；q=p->next;p->next=q->next;free(q);（3）查找：当p->data!=x时，p=p->next，找到之后返回p->data3)程序源码（提示：列出所编写程序的代码。

顺序表和链表详解及实现⾸先了解顺序表和链表的概念1.顺序表（类似STL库中的vector）顺序表是在计算机内存中以数组形式保存的线性表，是指⽤⼀组地址连续的存储单元依次存储数据元素的线性结构。

线性表采⽤顺序存储的⽅式称为顺序表。

优点：（1）空间利⽤率⾼（连续存放）（2）存取速度⾼效，通过下标直接存储和读取。

缺点：（1）插⼊和删除⽐较慢。

（插⼊或删除⼀个元素时需要遍历移动元素来重新排⼀次顺序）（2）不可以增长长度，有空间限制，当需要存储的元素个数可能多于顺序表元素时，可能出现“溢出”问题。

当元素个数远远⼩于预先分配的空间是，会造成空间浪费。

2.链表（类似STL库中的list）链表是⼀种物理存储单元上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表由⼀系列的节点组成，节点可以在运⾏时动态⽣成。

每个节点由两部分组成：数据域（存储数据元素）和指针域（存放下⼀个节点的地址）。

链表的种类：单链表、双向链表、循环链表优点：（1）插⼊和删除的速度快，保留原有的物理顺序（插⼊或删除时，只需要改变指针指向即可）。

（2）没有空间限制，存储元素的个数⽆上限，基本只与内存空间⼤⼩有关。

缺点：（1）存取元素⽐较慢（不能进⾏索引访问，只能从头结点开始顺序查找）（2）占⽤额外的空间⽤来存储指针（不连续存放，空间碎⽚多）总结：频繁查找却很少插⼊和删除操作可以⽤顺序表存储，堆排序，⼆分查找适宜⽤顺序表。

频繁插⼊和删除却很少查找可以使⽤链表存储。

若线性表长度变化不⼤，事先知道线性表的⼤致长度，且主要操作时查找，则采⽤顺序表。

若线性表长度变化较⼤或根本不知道多⼤时，且主要操作是插⼊、删除，则采⽤链表。

顺序表：顺序存储，随机读取。

链表：随机存储，顺序读取。

顺序表与链表的比较全套资料(全套资料，可以直接使用，可编辑优秀版资料，欢迎下载）顺序表与链表的比较一、顺序表的特点是逻辑上相邻的数据元素,物理存储位置也相邻,并且，顺序表的存储空间需要预先分配.它的优点是：（1）方法简单，各种高级语言中都有数组，容易实现.（2）不用为表示节点间的逻辑关系而增加额外的存储开销。

(3）顺序表具有按元素序号随机访问的特点。

缺点：（1）在顺序表中做插入、删除操作时，平均移动表中的一半元素，因此对n较大的顺序表效率低。

（2）需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。

二、在链表中逻辑上相邻的数据元素，物理存储位置不一定相邻，它使用指针实现元素之间的逻辑关系。

并且，链表的存储空间是动态分配的。

链表的最大特点是：插入、删除运算方便。

缺点：（1）要占用额外的存储空间存储元素之间的关系，存储密度降低.存储密度是指一个节点中数据元素所占的存储单元和整个节点所占的存储单元之比。

（2)链表不是一种随机存储结构,不能随机存取元素。

三、顺序表与链表的优缺点切好相反，那么在实践应用中怎样选取存储结构呢?通常有以下几点考虑：（1）顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模,也就是说事先对“MaxSize"要有合适的设定，设定过大会造成存储空间的浪费,过小造成溢出。

因此，当对线性表的长度或存储规模难以估计时，不宜采用顺序表。

然而，链表的动态分配则可以克服这个缺点.链表不需要预留存储空间，也不需要知道表长如何变化，只要内存空间尚有空闲，就可以再程序运行时随时地动态分配空间，不需要时还可以动态回收。

因此，当线性表的长度变化较大或者难以估计其存储规模时，宜采用动态链表作为存储结构。

但在链表中，除数据域外海需要在每个节点上附加指针。

如果节点的数据占据的空间小，则链表的结构性开销就占去了整个存储空间的大部分。

当顺序表被填满时，则没有结构开销.在这种情况下，顺序表的空间效率更高。

顺序表与链表的比较一、顺序表的特点是逻辑上相邻的数据元素，物理存储位置也相邻，并且，顺序表的存储空间需要预先分配。

它的优点是：（1）方法简单，各种高级语言中都有数组，容易实现。

（2）不用为表示节点间的逻辑关系而增加额外的存储开销。

（3）顺序表具有按元素序号随机访问的特点。

缺点：（1）在顺序表中做插入、删除操作时，平均移动表中的一半元素，因此对n较大的顺序表效率低。

（2）需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。

二、在链表中逻辑上相邻的数据元素，物理存储位置不一定相邻，它使用指针实现元素之间的逻辑关系。

并且，链表的存储空间是动态分配的。

链表的最大特点是：插入、删除运算方便。

缺点：（1）要占用额外的存储空间存储元素之间的关系，存储密度降低。

存储密度是指一个节点中数据元素所占的存储单元和整个节点所占的存储单元之比。

（2）链表不是一种随机存储结构，不能随机存取元素。

三、顺序表与链表的优缺点切好相反，那么在实践应用中怎样选取存储结构呢？通常有以下几点考虑：（1）顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对“MaxSize”要有合适的设定，设定过大会造成存储空间的浪费，过小造成溢出。

因此，当对线性表的长度或存储规模难以估计时，不宜采用顺序表。

然而，链表的动态分配则可以克服这个缺点。

链表不需要预留存储空间，也不需要知道表长如何变化，只要内存空间尚有空闲，就可以再程序运行时随时地动态分配空间，不需要时还可以动态回收。

因此，当线性表的长度变化较大或者难以估计其存储规模时，宜采用动态链表作为存储结构。

但在链表中，除数据域外海需要在每个节点上附加指针。

如果节点的数据占据的空间小，则链表的结构性开销就占去了整个存储空间的大部分。

当顺序表被填满时，则没有结构开销。

在这种情况下，顺序表的空间效率更高。

由于设置指针域额外地开销了一定的存储空间，从存储密度的角度来讲，链表的存储密度小于1.因此，当线性表的长度变化不大而且事先容易确定其大小时，为节省存储空间，则采用顺序表作为存储结构比较适宜。

数据结构顺序表链表试验报告数据结构试验报告一、引言数据结构是计算机科学中非常重要的一个概念，它用于组织和存储数据，以便能够高效地进行检索和操作。

顺序表和链表是两种常见的数据结构，它们在实际应用中都有各自的优势和局限性。

本报告将对顺序表和链表进行试验比较，以评估它们在不同场景下的性能和适合性。

二、实验目的本次试验的目的是比较顺序表和链表在插入、删除和查找操作上的性能差异，并分析其时间复杂度和空间复杂度。

通过实验结果，可以对不同场景下选择合适的数据结构提供参考。

三、实验内容1. 顺序表实验a. 创建一个包含100个元素的顺序表；b. 在表尾插入一个元素；c. 在表头插入一个元素；d. 在表的中间位置插入一个元素；e. 删除表尾的一个元素；f. 删除表头的一个元素；g. 删除表的中间位置的一个元素；h. 查找一个元素；i. 遍历整个顺序表。

2. 链表实验a. 创建一个包含100个节点的链表；b. 在链表尾部插入一个节点；c. 在链表头部插入一个节点；d. 在链表的中间位置插入一个节点；e. 删除链表尾部的一个节点；f. 删除链表头部的一个节点；g. 删除链表的中间位置的一个节点；h. 查找一个节点；i. 遍历整个链表。

四、实验结果与分析1. 顺序表实验结果a. 在表尾插入一个元素的平均时间为0.1ms；b. 在表头插入一个元素的平均时间为0.2ms；c. 在表的中间位置插入一个元素的平均时间为0.5ms；d. 删除表尾的一个元素的平均时间为0.1ms；e. 删除表头的一个元素的平均时间为0.2ms；f. 删除表的中间位置的一个元素的平均时间为0.5ms；g. 查找一个元素的平均时间为1ms；h. 遍历整个顺序表的平均时间为10ms。

2. 链表实验结果a. 在链表尾部插入一个节点的平均时间为0.2ms；b. 在链表头部插入一个节点的平均时间为0.1ms；c. 在链表的中间位置插入一个节点的平均时间为0.5ms；d. 删除链表尾部的一个节点的平均时间为0.2ms；e. 删除链表头部的一个节点的平均时间为0.1ms；f. 删除链表的中间位置的一个节点的平均时间为0.5ms；g. 查找一个节点的平均时间为2ms；h. 遍历整个链表的平均时间为5ms。

数据结构第二章实验报告一、实验目的数据结构第二章主要涉及线性表的相关知识，本次实验的目的在于通过实际操作和编程实现，深入理解线性表的概念、存储结构以及基本操作，巩固所学的理论知识，并提高编程能力和问题解决能力。

二、实验环境本次实验使用的编程语言为C+＋，编程环境为Visual Studio 2019。

三、实验内容（一）顺序表的实现顺序表是一种用顺序存储方式实现的线性表。

在实验中，我们定义了一个结构体来表示顺序表，包括存储数据的数组和表示表长度的变量。

实现了顺序表的初始化、插入、删除、查找等基本操作。

（二）链表的实现链表是一种通过指针链接实现的线性表。

我们分别实现了单向链表和双向链表。

在单向链表中，每个节点包含数据和指向下一个节点的指针；双向链表则在此基础上增加了指向前一个节点的指针，使得链表的操作更加灵活。

（三）线性表的应用运用实现的线性表解决了一些实际问题，如数据排序、查找特定元素等。

四、实验步骤（一）顺序表的实现步骤1、定义顺序表结构体，包括数据数组和长度变量。

2、实现顺序表的初始化函数，将长度初始化为 0。

3、插入操作：首先判断表是否已满，如果未满，在指定位置插入元素，并将后续元素后移。

4、删除操作：首先判断指定位置是否合法，然后将该位置元素删除，并将后续元素前移。

5、查找操作：遍历表中的元素，找到目标元素返回其位置，否则返回－1。

（二）链表的实现步骤1、单向链表定义单向链表节点结构体，包含数据和指向下一个节点的指针。

实现链表的初始化函数，创建头节点。

插入操作：分为头插法和尾插法，根据插入位置的不同选择相应的方法。

删除操作：找到要删除的节点，将其前后节点连接起来，释放删除节点的内存。

查找操作：遍历链表，找到目标元素返回节点指针，否则返回NULL。

2、双向链表定义双向链表节点结构体，包含数据、指向前一个节点和指向下一个节点的指针。

初始化函数与单向链表类似，但需要同时处理前后指针。

插入和删除操作：在单向链表的基础上，同时更新前后节点的指针。

数据结构实验二1、实验目的∙熟练掌握线性表的链式存储结构定义及基本操作∙理解循环链表和双链表的特点和基本运算2、实验内容：建立单链表，完成链表（带表头结点）的基本操作：建立链表、插入、删除、查找、输出、求前驱、求后继、两个有序链表的合并操作。

其他基本操作还有销毁链表、将链表置为空表、求链表的长度、获取某位置结点的内容、搜索结点。

1．问题描述：利用线性表的链式存储结构,设计一组输入数据（假定为一组整数），能够对单链表进行如下操作：∙初始化一个带表头结点的空链表;∙创建一个单链表是从无到有地建立起一个链表，即一个一个地输入各结点数据，并建立起前后相互链接的关系。

又分为逆位序(插在表头)输入n 个元素的值和正位序(插在表尾)输入n 个元素的值;∙插入结点可以根据给定位置进行插入（位置插入），也可以根据结点的值插入到已知的链表中（值插入），且保持结点的数据按原来的递增次序排列，形成有序链表。

∙删除结点可以根据给定位置进行删除（位置删除），也可以把链表中查找结点的值为搜索对象的结点全部删除（值删除）;∙输出单链表的内容是将链表中各结点的数据依次显示，直到链表尾结点;∙求前驱结点是根据给定结点的值，在单链表中搜索其当前结点的后继结点值为给定的值，将当前结点返回;∙求后继结点是根据给定结点的值，在单链表中搜索其当前结点的值为给定的值，将后继结点返回;∙两个有序链表的合并是分别将两个单链表的结点依次插入到第3 个单链表中，继续保持结点有序;编写主程序，实现对各不同的算法调用。

其它的操作算法描述略。

2．实现要求：对链表的各项操作一定要编写成为C（C++）语言函数，组合成模块化的形式，还要针对每个算法的实现从时间复杂度和空间复杂度上进行评价。

∙“初始化算法”的操作结果：构造一个空的线性表L，产生头结点,并使L 指向此头结点;∙“建立链表算法”初始条件：空链存在;操作结果：选择逆位序或正位序的方法，建立一个单链表，并且返回完成的结果;∙“链表（位置）插入算法”初始条件：已知单链表L 存在;操作结果：在带头结点的单链线性表L 中第i 个位置之前插入元素e;∙“链表（位置）删除算法”初始条件：已知单链表L 存在;操作结果：在带头结点的单链线性表L 中，删除第i 个元素,并由e 返回其值;∙“输出算法”初始条件：链表L 已存在;操作结果：依次输出链表的各个结点的值;∙“求前驱算法”初始条件: 线性表L 已存在;操作结果: 若cur_e 是L 的数据元素,且不是第一个,则用pre_e 返回它的前驱;∙“求后继算法”初始条件: 线性表L 已存在;操作结果: 若cur_e 是L 的数据元素,且不是最后一个,则用next_e 返回它的后继;∙“两个有序链表的合并算法”初始条件: 线性表单链线性表La 和Lb 的元素按值非递减排列;操作结果:归并La 和Lb 得到新的单链表。