大数据结构线性表应用

1、实验一线性表应用一.实验目的1、掌握用Turbo C或VC+吐机调试线性表的基本方法；2、 掌握线性表的基本操作，如插入、删除、查找，以及线性表合并等运算在顺序存储结构和 链式存储结构上的运算；并能够运用线性表基本操作解决问题，实现相应算法。二.实验学时：课实验学时：2学时课外实验学时：4学时三备选实验题目1. 单链表基本操作练习（实验类型：验证型）1）问题描述：在主程序中设计一个简单的菜单，分别调用相应的函数功能:1 建立链表2 连接链表3 输出链表0结束2）实验要求：在程序中定义下述函数，并实现所要求的函数功能:CreateLinklist():从键盘输入数据，创建一个单链表ContLin

2、klist():将前面建立的两个单链表首尾相连OutputLi nklist():输出显示单链表3）实验提示：单链表数据类型定义（C语言）# in elude <stdio.h>typedef int ElemType; / 元素类型typedef struct LNode ElemType data;struct LNode *n ext;LNode,*Li nkList;为了算法实现简单，最好采用带头结点的单向链表。4）注意问题重点理解链式存储的特点及指针的含义。 注意比较顺序存储与链式存储的各自特点。注意比较带头结点、无头结点链表实现插入、删除算法时的区别。 单链表的操作是数

3、据结构的基础，一定要注意对这部分的常见算法的理解。2. 顺序表基本操作练习（实验类型：验证型）1）问题描述：从键盘输入一组整型元素序列，建立顺序表。实现该顺序表的遍历。在该顺序表中进行顺序查找某一元素，查找成功返回1,否则返回0。判断该顺序表中元素是否对称，对称返回1,否则返回0。2）实验要求：对应问题描述，在程序中定义4个相应的函数，实现上面要求的函数功能：在主程序中设计一个简单的菜单，调用上述4个函数3）实验提示：顺序表存储数据类型定义（C语言）# define MAXSIZE 100 /表中元素的最大个数typedef int ElemType; / 元素类型typedef struct

4、 listElemType elemMAXSIZE; /静态线性表in t le ngth; II表的实际长度SqList; II顺序表的类型名4）注意问题：插入、删除时元素的移动原因、方向及先后顺序。理解不同的函数形参与实参的传递关系。3. 约瑟夫环问题（实验类型：综合型）1） 问题描述：有编号为1,2n的n个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始给定一个正整数 m,从第一个人按顺时针方向自 1开始报数，报到 m者出列，不再参加报 数，这时将出列者的密码作为 m,从出列者顺时针方向的下一人开始重新自1开始报数。如此下去,直到所有人都出列。试设计算法，输出出列者的序列。2）实验要

5、求：采用顺序和链式两种存储结构实现3）实现提示：用顺序表来存储围座者的序号和密码（顺序存储结构）.用number和code分别表示围座者的序号和密码 .假设围座者人数为j,当前使 用密码为m,开始报数者位置为 s,那么下一出列者位置为 s=（s+m-1） mod j.当我们要在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表的第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到 该位置。若要删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。用链式存储解决此问题时可以采用循环链表4）注意问题：顺序存储和链式存储实现此算法时计算出列位置的不同

6、方法，人员出列后所做操作的区别。4. 一元稀疏多项式简单的计算器（实验类型：综合型）1）问题描述：用线性表表示一元稀疏多项式，设计一个一元多项式运算器2）实验要求：采用单链表存储结构一元稀疏多项式输入并建立多项式输出多项式实现多项式加、减运算3）实现提示：以两个多项式相加为例结果多项式另存扫描两个相加多项式，若都未检测完：若当前被检测项指数相等，系数相加，若结果未变成0,则将结果插入到结果多项式。若当前被检测项指数不等，则将指数较小者插入到结果多项式。若有一个多项式已检测完，则将另一个多项式剩余部分直接连接到结果多项式。5. 长整数（任意长度）四则运算演示程序（实验类型：综合型）1）问题描述：

7、设计一个实现任意长的整数进行加法运算的演示程序2）实验要求：利用双向循环链表实现长整数的存储，给各结点含一个整型变量。任何整型变量的的围是-（215-1 ） （215-1 ）。输入和输出形式：按照中国对长整数的表示习惯，每四位一组，组间用逗号隔开。3）实现提示：每个结点中可以存放的最大整数为215-1=32767,才能保证两数相加不会溢出。但若这样存，即相当于按 32768进制数存，在十进制数与 32768进制数之间的转换十分不方便。故可以在 每个结点中仅存十进制数的4位，即不超过9999的非负整数，整个链表视为万进制数。可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点的树木

8、。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。4）注意问题：不能给常整数位数规定上限。程序设计源代码如下:第一题：#in elude <stdio.h>#in elude <stdlib.h>#in elude<iostream.h>typedef int ElemType;Illi元素类型typedef struct LNodeElemType data;struct LNode *n ext;LNode;typedef LNode *Lin kList;Lin kList head;Lin kList L;

9、Illi定义单链表头指针 LLin kList L1;Lin kList L2;Lin kList L12;尾插入法建立单链表Lin kList Creatlist_L()llliiliLin kList L,p,r;int x;r=L=(L in kList)malloc(sizeof(LNode);L-> next=NULL;cin> >x;while(x!=O)p=(L in kList)malloc(sizeof(LNode);p_>data=x;p-> next=NULL;r->n ext=p;r=p;cin> >x;return L;

10、LinkList Show_L(LinkList L)Lin kList p2;p2=L;while(p2-> next!=NULL)cout<<p2->n ext->data<<"" p2=p2->n ext;return L;Lin kList Con tlist_L(Li nkList A,Li nkList B)Li nkList C,a,b,e,f;a=A->n ext;b=B->n ext;C=A;/C表的头节点f=C=(Li nkList)malloc(sizeof(LNode);C-> nex

11、t=NULL;/建立空链表while(a)e=(L in kList)malloc(sizeof(LNode); e->data=a->data;e-> next=NULL;f->n ext=e;f=e;a=a->n ext;while(b)e=(L in kList)malloc(sizeof(LNode); e->data=b->data;e-> next=NULL;f->n ext=e;f=e;b=b->n ext;return C; void mai n()int choice;for(;)cout<<"

12、+ 进入菜单 +："<<e ndl; cout<<"1.建立单链表:"<<endl;cout<<"2.连接单链表:"<<endl;cout<<"3.输出单链表:"<<endl;cout<<"0.程序结束:"<<endl;cout<<e ndl;cout<<"请选择操作序号:"<<endl;cin> >choice;if(choice

13、=0)cout<<"成绩结束，任意键退出！"<<endl;break;switch(choice)case 1:int choice1;cout<<"开始建立单链表 1:"<<endl;L仁 Creatlist_L();cout<<e ndl;cout<<"表 1 建立完毕!"<<endl;"<<e ndl;cout<<"是否继续建立单链表2 ? "<<"n 1. 继续 2.

14、返回cin> >choice1;if(choice1=1)cout<<"开始建立单链表 2"<<endl;L2=Creatlist_L();cout<<e ndl;cout<<"表 2 建立完毕!"<<endl;cout<<e ndl;cout<<"单链表建立完毕！!"<<endl;break;case 2:cout<<" 开始连接单链表 1, 2!"<<endl;L12=Co ntl

15、ist_L(L1 ,L 2);cout<<"asfsdfsagshdfhgdfhjdfhhdfhasdf'<<e ndl;break;case 3:int choice1;cout<<"请选择输出哪个表："<<endl;cout<<"1.表 12. 表 23.联立后的表 12 "<<endl;cin> >choice1;switch(choice1)case 1:cout<<"单链表 1 为："<<endl;S

16、how_L(L1);cout<<e ndl;break;case 2:cout<<"单链表 2 为："<<endl;Show_L(L2);cout<<e ndl;break;case 3:cout<<"联立后的表12为:"<<endl;Show_L(L12);cout<<e ndl;break; break;第二题:#in clude <stdio.h>#in clude <stdlib.h>#in clude<iostream.h>#

17、defi ne Maxsize 100/表中元素的最大个数typedef int ElemType; /typedef struct listElemType dataMaxsize; / in t le ngth;/SqList;/int m=0;元素类型静态线性表表的实际长度顺序表的类型名SqList *creat_SqList(SqList *L) /L=(SqList *)malloc(sizeof(SqList); cout<<"请输入线性表数据:"<<endl;建立线性表，并输入线性表元素for(m;m+)ElemType x;cin&g

18、t; >x;if(x=O) break;L->datam=x; L->le ngth=m; return L;SqList *all_SqList(SqList *L)cout<<"已建立的线性表为:"<<endl;for(i nt i=0;i<L->le ngth;i+)cout<<L->datai<<""cout<<e ndl;return L;查询元素函数"<<j+1<<"位!"<<e n

19、dl;int serch_SqList(SqList *L,i nt y) Illifor(i nt j=O;j<L->le ngth;j+)if(L->dataj=y)cout<<"表中含有此数据，位于表中第return 1;break;else if(j=L->le ngth-1)cout<<"表中没有此数据!"<<endl;break;elsecon ti nue;void judje_SqList(SqList *L)Illi判断是否对称函数if(m%2=0)lllll线性表元素个数为偶数个cou

20、t<<"中心元素为"<<L->datam/2<<endl;for(i nt k=0;k<=m/2+1;k+)if(k=m/2+1)cout<<"*该线性表对称!*"<<endl;break;else if(L->datak=L->datam-1-k)con ti nue;elsecout<<" *该线性表不是对称的!*"<<e ndl;break;else lllllllllllll线性表元素个数为奇数个cout<<

21、"中心元素为"<<L->dataml2<<endl;for(i nt t=0;t<=ml2+1;t+)if(t=ml2+1)cout<<"*该线性表对称!*"<<endl;break;else if(L->datat=L->datam-1-t)con ti nue;elsecout<<" *该线性表不是对称的!*"<<e ndl;break;int mai n()SqList *L1;int choice;for(;)cout<<

22、;"+ 主菜单 +"<<e ndl;cout<<"1.新建线性表;"<<endl;cout<<"2.遍历线性表;"<<endl;cout<<"3.查找表中元素;"<<endl;cout<<"4.判断是否对称;"<<endl;cout<<"0.退出程序;"<<endl;cout<<e ndl;cout<<"请输入操

23、作序号："<<endl;cin> >choice;if(choice=0) break;switch(choice)case 1:L1=creat_SqList(L1);cout<<"线性表长度为:"<<m<<endl;break;case 2:cout<<"开始遍历线性表："<<endl;all_SqList(L1);break;case 3:int y;cout<<"请输入要查找的元素："<<endl;cin

24、87;y;serch_SqList(L1,y);break;case 4:cout<<"正在检测是否对称!"<<endl;judje_SqList(L1);break;return 0;第三题：#in clude <stdio.h>#in clude <stdlib.h>#in clude<iostream.h># define Maxsize 50 /元素最大容量typedef int ElemType; /元素类型typedef struct listElemType num Maxsize;ElemType

25、codeMaxsize; in t le ngth;/表的实际长度顺序表的类型名Juserfu L;/定义一个顺序表Lint j=0;/围坐的总人数Juserfu *creat_Juserfu(Juserfu *L)/L=(Juserfu *)malloc(sizeof(Juserfu);cout<<"请分别输入每个人的序号和密码:"<<endl;for(j;j+)建立线性表，并输入线性表元素ElemType m,s; /定义密码cin> >s»m;if(m=0) break;L_>nu mj=s;L->codej=

26、m;L->le ngth=j;return L;Juserfu *output_Juserfu(Juserfu *L)/int x_num=O;int x_code;cout<<"请输入初始密码："<<endl;cin>> x_code;for(j;j>0;j-)输出出列者的序列Juserfu;/x_nu m=(x_ nu m+x_code-1)%j;"<<e ndl;cout<<x_num<<"出歹U者为"<<L->numx_num<&

27、lt;"号!x_code=L->codex_ nu m;for(x_ num;x_nu m<j;x_ nu m+)L->numx_num =L->numx_nu m+1;L->codex_ nu m=L->codex_ nu m+1;return L;void mai n()int s;Juserfu *L1;cout<<"请输入每位围坐者的密码!"<<endl;L1=creat_Juserfu(L1);cout<<"共围坐人数为："<<L1->lengt

28、h<<endl;cout<<"密码分别为："<<endl;for(i nt i=0;i<j;i+)cout<<L1->numi<<" "<<L1->codei<<""output_Juserfu(L1);第四题：#in clude <stdio.h>#in clude <stdlib.h> #in clude<iostream.h>typedef struct PolyNode系数float coe

29、f;/float exp; /指数PolyNode *n ext;/指针域PolyNode;typedef PolyNode *Po lyn omial;Polynomial A;/定义多项式APolyno mial creat_Poly()Pol yno mial L,p,r;float x_coef;float x_exp;r=L=(Po lyno mial)malloc(sizeof(PolyNode);L-> next=NULL;cout<<"请依次输入多项式的系数和指数(0,0为输入结束)："<<endl;cin>> x_

30、coef»x_exp;while(x_coef!=0 && x_exp!=0)p=(Po lyno mial)malloc(sizeof(PolyNode);p->coef=x_coef;p->exp=x_exp;p-> next=NULL;r->n ext=p;r=p;cin>> x_coef>>x_exp;return L;Polyno mial show_Poly(Po lyno mial L)Polyno mial p1;p1=L;while(p1-> next!=NULL)cout<<p1-

31、>n ext->coef<<"X"<<p1- >n ext->exp<<" +" p1=p1- >n ext;cout<<e ndl;return L;Poly nomial add_Poly(Poly nomial A,Poly nomial B)Pol yno mial C,D;Poly nomial p1,p2,p3;float sum;p1=A->n ext;p2=B->n ext;C=(Poly nomial)malloc(sizeof(PolyNode)

32、;p3=C;p3-> next=NULL;while(p1 &&p2)if(p1_>exp=p2_>exp)sum=p1->coef+p2->coef;if(sum!=0)D=(Poly nomial)malloc(sizeof(PolyNode);D->coef=sum;D->exp=p1->exp;D-> next=NULL;p3-> next=D;p3=D;p1=p1- >n ext;p2=p2->n ext;else if(p1->exp<p2->exp)D=(Poly nomia

33、l)malloc(sizeof(PolyNode);D->coef=p1->coef;D_>exp=p1_>exp;D-> next=NULL;p3-> next=D;p3=D;p1=p1- >n ext;elseD=(Poly nomial)malloc(sizeof(PolyNode);D->coef=p2->coef;D_>exp=p2_>exp;D-> next=NULL;p3-> next=D;p3=D;p2=p2->n ext;while(p1) / 多项式A没有处理完D=(Poly nomial)

34、malloc(sizeof(PolyNode);D->coef=p1->coef;D->exp=p1->exp;D-> next=NULL;p3-> next=D;p3=D;p1=p1- >n ext; while(p2) / 多项式B没有处理完D=(Poly no mial)malloc(sizeof(PolyNode);D->coef=p2->coef;D_>exp=p2_>exp;D-> next=NULL;p3-> next=D;p3=D;p2=p2->n ext;return C;void mai n

35、()Poly no mial A;Polyno mial B;Poly nomial C;cout<<"开始建立多项式 A:"<<endl;A=creat_Poly();cout<<"多项式 A 为:"<<endl;show_Poly(A);cout<<"开始建立多项式 B:"<<endl;B=creat_Poly();cout<<"多项式 B 为:"<<endl;show_Poly(B);C=add_Poly(A,B);cout<<"相加之后得到的多项式C为:"<<endl;show_Poly(C);第五题：#in clude<stdio.h>#in clude<stdlib.h>#in clude<iostream.h> typedef struct Nodeint data;Node* next;Node* front;Node;typedef Node *Operati on;Operatio n creat()Operati on L;Operati on p1,p2;L=(