1、数据结构实验线性表基本操作学数据结构课程实验报告实 验 名 称： 线性表基本操作的实现 实验室(中心)： 学 生 信 息： 专 业 班 级： 指 导 教 师 ： 实验完成时间： 2016 实验一 线性表基本操作的实现一、实验目的1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。2.掌握线性表的顺序存储结构的定义及C语言实现。3.掌握线性表的链式存储结构单链表的定义及C语言实现。4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。5.掌握线性表在链式存储结构单链表中的各种基本操作。二、实验内容及要求1.顺序线性表的建立、插入、删除及合并。2.链式线性表的建立、插入、删除及连接。三、实验设备
2、及软件计算机、Microsoft Visual C+ 软件四、设计方案（算法设计） 采用的数据结构本程序顺序表的数据逻辑结构为线性结构，存储结构为顺序存储；链表的数据逻辑结构依然为线性结构，存储结构为链式结构。 设计的主要思路1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度，顺序表的长度和元素由用户输入；2.利用前面建立的顺序表，对顺序表进行插入、删除及合并操作；3.建立一个带头结点的单链表，结点的值域为整型数据，链表的元素由用户输入；4.对前面建立的链表进行插入、删除及连个链表的连接操作； 算法描述1、顺序表void Init(sqlist &);示所有元素n); prin
3、tf(2.插入一个元素n); printf(3.删除一个元素n); printf(4.查找一个元素n); printf(5.线性表的合并n); printf(6.退出程序nn); scanf( %c,&j); switch(j) case 1:print(L1); break; case 2:printf(请输入要插入的元素(一个字符)和插入位置:n); printf(格式：字符，位置；例如:a,2n); scanf(%c,%d,&ch,&loc); temp=Inse(L1,loc,ch); if(temp=False) printf(插入失败!n); else printf(插入成功!n)
4、; print(L1); break; case 3:printf(请输入要删除元素的位置:); scanf(%d,&loc); temp=del(L1,loc,ch); if(temp=True) printf(删除了一个元素:%cn,ch); else printf(该元素不存在!n); printf(删除该元素后的线性表为:); print(L1); break; case 4:printf(请输入要查找的元素:); scanf( %c,&ch); loc=Loc(L1,ch); if(loc!=-1) printf(该元素所在位置:%dn,loc+1); else printf(%c
5、不存在!n,ch); break; case 5:printf(请输入要进行合并的第二个线性表:); Init(L2); combine(L1,L2,L3); printf(合并前的两个线性表如下:n); print(L1); print(L2); printf(输出合并后的线性表如下:n); print(L3); break; default:S=0;printf(程序结束，按任意键退出!n); getch();void Init(sqlist &v)示所有元素n); printf(2.插入一个元素n); printf(3.删除一个元素n); printf(4.按关键字查找元素n); pri
6、ntf(5.按序号查找元素n); printf(6.链表的连接n); printf(7.退出程序n); scanf( %c,&j); switch(j) case 1:LPrint(L); break; case 2:printf(请输入元素(一个字符)和要插入的位置:n); printf(格式:字符，位置；例如:a,3n); scanf( %c,%d,&ch,&loc); temp=LInsert(L,loc,ch); if(temp=False) printf(插入失败!n); else printf(插入成功!n); LPrint(L); break; case 3:printf(请输入
7、要删除的元素所在位置:); scanf(%d,&loc); temp=LDele(L,loc,ch); if(temp=False) printf(删除失败!n); else printf(成功删除了一个元素:%cn,ch); LPrint(L); break; case 4:if(L-next=NULL) printf(链表为空!n); else printf(请输入要查找的元素(一个字符):); scanf( %c,&ch); temp=LFind_key(L,ch,loc); if(temp=False) printf(没有找到该元素!n); else printf(该元素在链表的第%d
8、个位置。n,loc); break; case 5:if(L-next=NULL) printf(链表为空!n); else printf(请输入要查找的位置:); scanf(%d,&loc); temp=LFind_order(L,ch,loc); if(temp=False) printf(该位置不存在!n); else printf(第%d个元素是：%cn,loc,ch); break; case 6:if(L-next=NULL) printf(链表为空!n); else printf(请输入第二个链表的长度:); scanf(%d,&num1); CreaL(T,num1); if
9、(T-next=NULL) printf(第二个链表为空!n); LUnion(L,T,H,num+num1); printf(输出连接后链表中的所有元素:); printf(n); LPrint(H); break; default:flag=0;printf(程序结束，按任意键退出!n); getch();void CreaL(LinkList &v,int n)于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。2.注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。3.单链表
10、的结点结构除数据域外，还含有一个指针域。线性表提升实验（一）、实现顺序表元素的就地逆置一、设计方案 采用的数据结构本程序采用的数据逻辑结构为线性结构，存储结构为顺序结构，算法的总体功能是实现顺序表中元素的逆置。 设计的主要思路由用户确定初始顺序表的长度并输入初始顺序表的元素，然后通过交换元素的方法将初始表中的元素进行逆置处理、输出元素。 算法描述status Initlist_Sq(Sqlist *L) /对顺序表A进行初始化void input(Sqlist *A) /对一个线性表输入数据，是先输入长度，然后再输入数据void print(Sqlist *A) /对一个线性表进行输出 voi
11、d invert(Sqlist *A) /实现一个顺序表的逆置二、主要代码#include #include #include #define SIZE 100#define ListInc 10 #define OK 1 typedef struct int *elem; int length; int listsize; Sqlist; typedef int status; status Initlist_Sq(Sqlist *L) L-elem =(int *)malloc(SIZE*sizeof(status); if(!L-elem) printf(voerflow); else
12、L-length=0; L-listsize=SIZE; return OK; /对一个线性表输入数据，是先输入长度，然后再输入数据void input(Sqlist *A) int i=0; printf(本程序用于实现顺序表的逆置。n); printf(n请输入长度:n); scanf(%d,&A-length); printf(请输入数:n); for(i=0;ilength;i+) scanf(%d,&A-elemi); /对一个线性表进行输出 void print(Sqlist *A) int i; for(i=0;ilength;i+) printf(%dt,A-elemi); p
13、rintf(nn); void invert(Sqlist *A) int n=A-length; int m=(A-length)/2,i; int temp; for(i=0;ielemi;A-elemi=A-elemn-i-1;A-elemn-i-1=temp; void main() Sqlist A; /定义一个线性表A Initlist_Sq(&A); /对A进行初始化 input(&A); /输入数据printf(输入的数据为:n); print(&A);printf(逆序处理后为:n); invert(&A); /对线性表A逆置 print(&A); /输出逆置以后的A 三、测
14、试结果及说明由用户输入初始顺序表的长度以及元素，然后通过程序实现初始顺序表的逆置并输出结果，程序的测试结果完全正确，没有出现任何的错误。（二）、实现单循环链表的逆置一、设计方案 采用的数据结构本程序采用的数据逻辑结构为线性结构，存储结构为链式存储结构，算法的总体功能是实现单循环链表中元素的逆置。 设计的主要思路由用户确定初始链表的长度并输入初始链表的元素，然后通过过交换指针的方法将初始表中的元素进行逆置处理、输出元素。 算法描述void creatlinklist(linklist &l,int n) /建立一个空表，初始化，并对其进行输入值void invert(linklist &l) /
15、对单循环链表中的元素进行逆置处理 二、主要代码#include #include #include #include typedef struct lnode int data; struct lnode *next;lnode ,*linklist;/建立一个空表，初始化，并对其进行输入值void creatlinklist(linklist &l,int n) l=(linklist)malloc(sizeof(lnode); if(!l) exit(OVERFLOW); l-next=l; /循环链表 linklist p,q; int i; q=l; printf(请输入 %d个元素:
16、n,n); for(i=0;idata); p-next=q-next; q-next=p; q=p; /逆置函数void invert(linklist &l) linklist p,q,r; p=l-next; q=p-next; r=q-next; while(p!=l) q-next=p; p=q; q=r; r=r-next; int main() printf(本程序用于实现单循环链表的逆置处理：nn); linklist l,p; int length,i; printf(请输入元素的个数:n); scanf(%d,&length); creatlinklist(l,length
17、); p=l-next; printf(输入的链表为:n); while(p!=l) printf(%d ,p-data); p=p-next; printf(n); printf(逆置后的链表为n); invert(l); p=l-next; i=0; while(p!=l) printf(%d ,p-data); p=p-next; printf(n); return 0;三、测试结果及说明由用户确定输入的元素个数为6个，依次输入16、25、34、43、52、61，逆置处理后输出的结果为61、52、43、32、21、16，程序运行的结果正确，没有出现错误。（三）、解决约瑟夫环的出列问题一、
18、设计方案 采用的数据结构本程序采用的数据逻辑结构为线性结构，存储结构为链式存储结构，算法的总体功能是实现约瑟夫环的出列问题。 设计的主要思路设编号为1，2，3，n的n(n0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。 算法描述static void CreaL(NodeType *, const int); /运行约瑟夫环问题
19、 static void PrintL(const NodeType *); /得到一个结点 static NodeType *GetNode(const int, const int); /测试链表是否为空, 空为True，非空为False static unsigned EmptyL(const NodeType *); static void StatGame(NodeType *ppHead, int iCipher); 二、主要代码#include #include #define Max 30 #define True 1 #define False 0 typedef struc
20、t NodeType int Num; int PassWord; struct NodeType *next; NodeType; static void CreaL(NodeType *, const int); /运行约瑟夫环问题 static void PrintL(const NodeType *); /得到一个结点 static NodeType *GetNode(const int, const int); /测试链表是否为空, 空为True，非空为False static unsigned EmptyL(const NodeType *); static void StatGa
21、me(NodeType *ppHead, int iCipher); int main(void) printf(本程序用于实现约瑟夫环操作nn);int n, m; NodeType *pHead=NULL; while(1) printf(输入总的人数 n(Max) printf(数字太大，请重新输入!n); continue; else break; CreaL(&pHead,n); printf(n打印出原始每个结点的序列号和密码n); PrintL(pHead); printf(n最终每个结点退出的序列号和密码n); StatGame(&pHead,m); return 0; sta
22、tic void CreaL(NodeType *ppHead, const int n) int i,iCipher; NodeType *pNew, *pCur; for(i=1;inext=*ppHead; else pNew-next=pCur-next; pCur-next=pNew; pCur=pNew; printf(已完成结点初始化!n); static void StatGame(NodeType *ppHead, int iCipher) int iCounter, iF=1,i=1; NodeType *pPrv, *pCur, *pDel; pPrv=pCur=*ppH
23、ead; while(pPrv-next!=*ppHead) pPrv=pPrv-next; while(iF) for(iCounter=1;iCounternext; if(pPrv=pCur) iF=0; pDel=pCur; pPrv-next=pCur-next; pCur=pCur-next; iCipher=pDel-PassWord; printf(第%d个退出的是序列号为%d的人,其密码为:%dn,i, pDel-Num,pDel-PassWord);free(pDel); +i; *ppHead=NULL; static void PrintL(const NodeType
24、 *pHead) const NodeType *pCur=pHead; if (EmptyL(pHead) return; do printf(第%d 个人,密码:%dn,pCur-Num,pCur-PassWord); pCur=pCur-next; while(pCur!=pHead); static NodeType *GetNode(const int iId,const int iCipher) NodeType *pNew; pNew=(NodeType *)malloc(sizeof(NodeType); if(!pNew) printf(错误，内存不足!n); exit(-1); pNew-Num=iId; pNew-PassWord=iCipher; pNew-next=NULL; return pNew; static unsigned EmptyL(const NodeType *pHead) if(!pHead) printf(列表为空!n); return True; return False; 三、测试结果及说明由用户确定总的人数为6、每个人持有一个正整数密码,，输入每个人的密码分别为16、25、34、43、52、61，程序处理后输出的结果为第一到第六个人的密码分别为61、52、43、34、25、16，程序的运行结果正确，没有出现任何的错误。
