数据结构线性表应用

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

2、 ContLinklist( )：将前面建立的两个单链表首尾相连 OutputLinklist( )：输出显示单链表3）实验提示:² 单链表数据类型定义（C语言） # include <stdio.h> typedef int ElemType； /元素类型 typedef struct LNode ElemType data; struct LNode *next; LNode,*LinkList;² 为了算法实现简单，最好采用带头结点的单向链表。4）注意问题:² 重点理解链式存储的特点及指针的含义。² 注意比较顺序存储与链式存储的各自特点

3、。² 注意比较带头结点、无头结点链表实现插入、删除算法时的区别。² 单链表的操作是数据结构的基础，一定要注意对这部分的常见算法的理解。2 顺序表基本操作练习（实验类型：验证型）1）问题描述： ² 从键盘输入一组整型元素序列，建立顺序表。² 实现该顺序表的遍历。² 在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。² 判断该顺序表中元素是否对称,对称返回1,否则返回0。2）实验要求：² 对应问题描述，在程序中定义4个相应的函数，实现上面要求的函数功能：² 在主程序中设计一个简单的菜单，调用上述4个函数3）

4、实验提示:² 顺序表存储数据类型定义（C语言） # define MAXSIZE 100 /表中元素的最大个数 typedef int ElemType； /元素类型 typedef struct list ElemType elemMAXSIZE; /静态线性表 int length; /表的实际长度 SqList; /顺序表的类型名4）注意问题:² 插入、删除时元素的移动原因、方向及先后顺序。² 理解不同的函数形参与实参的传递关系。3 约瑟夫环问题（实验类型：综合型）1）问题描述：有编号为1, 2n 的 n 个人按顺时针方向围坐一圈，每人持有一个正整数密码。开

5、始给定一个正整数 m，从第一个人按顺时针方向自1开始报数，报到m者出列，不再参加报数，这时将出列者的密码作为m，从出列者顺时针方向的下一人开始重新自1开始报数。如此下去，直到所有人都出列。试设计算法，输出出列者的序列。2）实验要求: 采用顺序和链式两种存储结构实现3) 实现提示：² 用顺序表来存储围座者的序号和密码(顺序存储结构).n 用number 和code分别表示围座者的序号和密码.假设围座者人数为 j,当前使用密码为m,开始报数者位置为s, 那么下一出列者位置为s=(s+m-1) mod j.n 当我们要在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表的第

6、i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若要删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。² 用链式存储解决此问题时可以采用循环链表.4）注意问题:² 顺序存储和链式存储实现此算法时计算出列位置的不同方法，人员出列后所做操作的区别。4 一元稀疏多项式简单的计算器（实验类型：综合型）1）问题描述：用线性表表示一元稀疏多项式，设计一个一元多项式运算器2）实验要求: ² 采用单链表存储结构一元稀疏多项式² 输入并建立多项式² 输出多项式² 实现多项式加、减运算3) 实现提示：以两个

7、多项式相加为例² 结果多项式另存² 扫描两个相加多项式，若都未检测完：n 若当前被检测项指数相等，系数相加，若结果未变成0，则将结果插入到结果多项式。n 若当前被检测项指数不等，则将指数较小者插入到结果多项式。² 若有一个多项式已检测完，则将另一个多项式剩余部分直接连接到结果多项式。5 长整数（任意长度）四则运算演示程序（实验类型：综合型）1）问题描述：设计一个实现任意长的整数进行加法运算的演示程序2）实验要求:² 利用双向循环链表实现长整数的存储，给各结点含一个整型变量。任何整型变量的的范围是 -（215-1）（215-1）。² 输入和输出形

8、式：按照中国对长整数的表示习惯，每四位一组，组间用逗号隔开。3) 实现提示： ² 每个结点中可以存放的最大整数为215-1=32767，才能保证两数相加不会溢出。但若这样存，即相当于按32768进制数存，在十进制数与32768进制数之间的转换十分不方便。故可以在每个结点中仅存十进制数的4位，即不超过9999的非负整数，整个链表视为万进制数。² 可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点的树木。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。4）注意问题:² 不能给常整数位数规定上限。程序设计源代码如

9、下：第一题：#include <stdio.h>#include <stdlib.h>#include<iostream.h>typedef int ElemType; /元素类型typedef struct LNode ElemType data;struct LNode *next;LNode;typedef LNode *LinkList;LinkList head;LinkList L; /定义单链表头指针LLinkList L1;LinkList L2;LinkList L12;LinkList Creatlist_L() /尾插入法建立单链表Li

10、nkList L,p,r;int x;r=L=(LinkList)malloc(sizeof(LNode);L->next=NULL;cin>>x;while(x!=0)p=(LinkList)malloc(sizeof(LNode);p->data=x;p->next=NULL;r->next=p;r=p;cin>>x;return L;LinkList Show_L(LinkList L)LinkList p2;p2=L;while(p2->next!=NULL)cout<<p2->next->data<&

11、lt;" "p2=p2->next;return L;LinkList Contlist_L(LinkList A,LinkList B)LinkList C,a,b,e,f;a=A->next;b=B->next;C=A; /C表的头节点f=C=(LinkList)malloc(sizeof(LNode);C->next=NULL; /建立空链表while(a)e=(LinkList)malloc(sizeof(LNode);e->data=a->data;e->next=NULL;f->next=e;f=e;a=a->

12、;next;while(b)e=(LinkList)malloc(sizeof(LNode);e->data=b->data;e->next=NULL;f->next=e;f=e;b=b->next;return C;void main()int choice;for(;)cout<<"+进入菜单+:"<<endl;cout<<"1.建立单链表:"<<endl;cout<<"2.连接单链表:"<<endl;cout<<&q

13、uot;3.输出单链表:"<<endl;cout<<"0.程序结束:"<<endl;cout<<endl;cout<<"请选择操作序号:"<<endl;cin>>choice;if(choice=0)cout<<"成绩结束，任意键退出！"<<endl;break;switch(choice)case 1:int choice1;cout<<"开始建立单链表1:"<<endl;

14、L1=Creatlist_L();cout<<endl;cout<<"表1建立完毕!"<<endl;cout<<"是否继续建立单链表2 ？"<<"n 1.继续 2.返回 "<<endl;cin>>choice1;if(choice1=1)cout<<"开始建立单链表2"<<endl;L2=Creatlist_L();cout<<endl;cout<<"表2建立完毕!"

15、;<<endl;cout<<endl;cout<<"单链表建立完毕!"<<endl;break;case 2:cout<<"开始连接单链表1，2!"<<endl;L12=Contlist_L(L1,L2);cout<<"asfsdfsagshdfhgdfhjdfhhdfhasdf"<<endl;break;case 3:int choice1;cout<<"请选择输出哪个表："<<endl;cou

16、t<<"1.表1 2.表2 3.联立后的表12 "<<endl;cin>>choice1;switch(choice1)case 1:cout<<"单链表1为："<<endl;Show_L(L1);cout<<endl;break;case 2:cout<<"单链表2为："<<endl;Show_L(L2);cout<<endl;break;case 3:cout<<"联立后的表12为:"<

17、<endl;Show_L(L12);cout<<endl;break;break;第二题：#include <stdio.h>#include <stdlib.h>#include<iostream.h>#define Maxsize 100 /表中元素的最大个数typedef int ElemType; /元素类型typedef struct listElemType dataMaxsize; /静态线性表int length; /表的实际长度SqList; /顺序表的类型名int m=0;SqList *creat_SqList(SqL

18、ist *L) /建立线性表，并输入线性表元素L=(SqList *)malloc(sizeof(SqList);cout<<"请输入线性表数据:"<<endl;for(m;m+)ElemType x;cin>>x;if(x=0)break;L->datam=x; L->length=m;return L;SqList *all_SqList(SqList *L)cout<<"已建立的线性表为:"<<endl;for(int i=0;i<L->length;i+)cout

19、<<L->datai<<" "cout<<endl;return L;int serch_SqList(SqList *L,int y) /查询元素函数for(int j=0;j<L->length;j+)if(L->dataj=y)cout<<"表中含有此数据，位于表中第 "<<j+1<<" 位!"<<endl;return 1;break;else if(j=L->length-1)cout<<"

20、表中没有此数据!"<<endl;break;elsecontinue;void judje_SqList(SqList *L) /判断是否对称函数if(m%2=0)/线性表元素个数为偶数个cout<<"中心元素为"<<L->datam/2<<endl;for(int k=0;k<=m/2+1;k+)if(k=m/2+1)cout<<"*该线性表对称!*"<<endl;break;else if(L->datak=L->datam-1-k)contin

21、ue;elsecout<<"*该线性表不是对称的!*"<<endl;break;else /线性表元素个数为奇数个cout<<"中心元素为"<<L->datam/2<<endl;for(int t=0;t<=m/2+1;t+)if(t=m/2+1)cout<<"*该线性表对称!*"<<endl;break;else if(L->datat=L->datam-1-t)continue;elsecout<<"*

22、该线性表不是对称的!*"<<endl;break;int main()SqList *L1;int choice;for(;)cout<<"+主菜单+"<<endl;cout<<"1.新建线性表;"<<endl;cout<<"2.遍历线性表;"<<endl;cout<<"3.查找表中元素;"<<endl;cout<<"4.判断是否对称;"<<endl;co

23、ut<<"0.退出程序;"<<endl;cout<<endl;cout<<"请输入操作序号："<<endl;cin>>choice;if(choice=0)break;switch(choice)case 1:L1=creat_SqList(L1);cout<<"线性表长度为:"<<m<<endl;break;case 2:cout<<"开始遍历线性表："<<endl;all_SqLi

24、st(L1);break;case 3:int y;cout<<"请输入要查找的元素："<<endl;cin>>y;serch_SqList(L1,y);break;case 4:cout<<"正在检测是否对称!"<<endl;judje_SqList(L1);break;return 0;第三题：#include <stdio.h>#include <stdlib.h>#include<iostream.h># define Maxsize 50 /元素最大

25、容量typedef int ElemType; /元素类型typedef struct listElemType numMaxsize; ElemType codeMaxsize;int length; /表的实际长度Juserfu; /顺序表的类型名Juserfu L; /定义一个顺序表Lint j=0; /围坐的总人数Juserfu *creat_Juserfu(Juserfu *L) /建立线性表，并输入线性表元素L=(Juserfu *)malloc(sizeof(Juserfu);cout<<"请分别输入每个人的序号和密码:"<<endl;

26、for(j;j+)ElemType m,s; /定义密码cin>>s>>m;if(m=0)break;L->numj=s;L->codej=m;L->length=j;return L;Juserfu *output_Juserfu(Juserfu *L) /输出出列者的序列int x_num=0;int x_code;cout<<"请输入初始密码："<<endl;cin>>x_code;for(j;j>0;j-)x_num=(x_num+x_code-1)%j;cout<<x_

27、num<<"出列者为"<<L->numx_num<<"号！"<<endl;x_code=L->codex_num;for(x_num;x_num<j;x_num+)L->numx_num=L->numx_num+1;L->codex_num=L->codex_num+1;return L;void main()/int s;Juserfu *L1;cout<<"请输入每位围坐者的密码!"<<endl;L1=creat_Ju

28、serfu(L1);cout<<"共围坐人数为："<<L1->length<<endl;cout<<"密码分别为："<<endl;for(int i=0;i<j;i+)cout<<L1->numi<<" "<<L1->codei<<" "output_Juserfu(L1);第四题：#include <stdio.h>#include <stdlib.h>#in

29、clude<iostream.h>typedef struct PolyNodefloat coef; /系数float exp; /指数PolyNode *next; /指针域PolyNode;typedef PolyNode *Polynomial;Polynomial A; /定义多项式APolynomial creat_Poly()Polynomial L,p,r;float x_coef;float x_exp;r=L=(Polynomial)malloc(sizeof(PolyNode);L->next=NULL;cout<<"请依次输入多项

30、式的系数和指数（0,0为输入结束）："<<endl;cin>>x_coef>>x_exp;while(x_coef!=0 && x_exp!=0)p=(Polynomial)malloc(sizeof(PolyNode);p->coef=x_coef;p->exp=x_exp;p->next=NULL;r->next=p;r=p;cin>>x_coef>>x_exp;return L;Polynomial show_Poly(Polynomial L)Polynomial p1;p1=

31、L;while(p1->next!=NULL)cout<<p1->next->coef<<"X"<<p1->next->exp<<" +"p1=p1->next;cout<<endl;return L;Polynomial add_Poly(Polynomial A,Polynomial B)Polynomial C,D;Polynomial p1,p2,p3;float sum;p1=A->next;p2=B->next;C=(Polynomia

32、l)malloc(sizeof(PolyNode);p3=C;p3->next=NULL;while(p1&&p2)if(p1->exp=p2->exp)sum=p1->coef+p2->coef;if(sum!=0)D=(Polynomial)malloc(sizeof(PolyNode);D->coef=sum;D->exp=p1->exp;D->next=NULL;p3->next=D;p3=D;p1=p1->next;p2=p2->next;else if(p1->exp<p2->

33、exp)D=(Polynomial)malloc(sizeof(PolyNode);D->coef=p1->coef;D->exp=p1->exp;D->next=NULL;p3->next=D;p3=D;p1=p1->next;elseD=(Polynomial)malloc(sizeof(PolyNode);D->coef=p2->coef;D->exp=p2->exp;D->next=NULL;p3->next=D;p3=D;p2=p2->next;while(p1) /多项式A没有处理完D=(Polyn

34、omial)malloc(sizeof(PolyNode);D->coef=p1->coef;D->exp=p1->exp;D->next=NULL;p3->next=D;p3=D;p1=p1->next;while(p2) /多项式B没有处理完D=(Polynomial)malloc(sizeof(PolyNode);D->coef=p2->coef;D->exp=p2->exp;D->next=NULL;p3->next=D;p3=D;p2=p2->next;return C;void main()Poly

35、nomial A;Polynomial B;Polynomial 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);第五题：#include<stdio.h>#include<stdlib.h>#include<iostream.h>typedef struct Nodeint data;Node* next;Node* front;Node;typedef Node *Operation