2022年数据结构线性表应用 .pdf

实验一线性表应用一. 实验目的1、 掌握用 Turbo C 或 VC+ 上机调试线性表的基本方法；2、 掌握线性表的基本操作，如插入、 删除、 查找， 以及线性表合并等运算在顺序存储结构和链式存储结构上的运算；并能够运用线性表基本操作解决问题，实现相应算法。二. 实验学时：课内实验学时：2 学时课外实验学时：4 学时三备选实验题目1 单链表基本操作练习（实验类型：验证型）1）问题描述：在主程序中设计一个简单的菜单，分别调用相应的函数功能： 1建立链表 2连接链表 3输出链表 0结束2）实验要求：在程序中定义下述函数，并实现所要求的函数功能： CreateLinklist( ): 从键盘输入数据，创建一个单链表 ContLinklist( )：将前面建立的两个单链表首尾相连 OutputLinklist( )：输出显示单链表3）实验提示 : 单链表数据类型定义（C 语言） # include typedef int ElemType； /元素类型 typedef struct LNode ElemType data; struct LNode *next; LNode,*LinkList; 为了算法实现简单，最好采用带头结点的单向链表。4）注意问题 : 重点理解链式存储的特点及指针的含义。注意比较顺序存储与链式存储的各自特点。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 21 页 - - - - - - - - - 注意比较带头结点、无头结点链表实现插入、删除算法时的区别。单链表的操作是数据结构的基础，一定要注意对这部分的常见算法的理解。2 顺序表基本操作练习（实验类型：验证型）1）问题描述：从键盘输入一组整型元素序列，建立顺序表。实现该顺序表的遍历。在该顺序表中进行顺序查找某一元素, 查找成功返回1, 否则返回 0。判断该顺序表中元素是否对称, 对称返回1, 否则返回0。2）实验要求：对应问题描述，在程序中定义4 个相应的函数，实现上面要求的函数功能：在主程序中设计一个简单的菜单，调用上述4 个函数3）实验提示 : 顺序表存储数据类型定义（C语言） # define MAXSIZE 100 /表中元素的最大个数 typedef int ElemType； /元素类型 typedef struct list ElemType elemMAXSIZE; /静态线性表 int length; /表的实际长度 SqList; /顺序表的类型名4）注意问题 : 插入、删除时元素的移动原因、方向及先后顺序。理解不同的函数形参与实参的传递关系。3 约瑟夫环问题（实验类型：综合型）1）问题描述：有编号为1, 2 n 的 n 个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始给定一个正整数 m，从第一个人按顺时针方向自1 开始报数，报到m者出列，不再参加报数，这时将出列者的密码作为m ，从出列者顺时针方向的下一人开始重新自1 开始报数。 如此下去，直到所有人都出列。试设计算法，输出出列者的序列。2）实验要求 : 采用顺序和链式两种存储结构实现3) 实现提示：用顺序表来存储围座者的序号和密码( 顺序存储结构). 用 number 和 code 分别表示围座者的序号和密码. 假设围座者人数为 j,当前使用密码为m,开始报数者位置为s, 那么下一出列者位置为s=(s+m-1) mod j. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 21 页 - - - - - - - - - 当我们要在线性表的顺序存储结构上的第i 个位置上插入一个元素时，必须先将线性表的第i 个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若要删除第i 个元素时，也必须把第i 个元素之后的所有元素前移一个位置。用链式存储解决此问题时可以采用循环链表. 4）注意问题 : 顺序存储和链式存储实现此算法时计算出列位置的不同方法，人员出列后所做操作的区别。4 一元稀疏多项式简单的计算器（实验类型：综合型）1）问题描述：用线性表表示一元稀疏多项式，设计一个一元多项式运算器2）实验要求 : 采用单链表存储结构一元稀疏多项式输入并建立多项式输出多项式实现多项式加、减运算3) 实现提示：以两个多项式相加为例结果多项式另存扫描两个相加多项式，若都未检测完：若当前被检测项指数相等，系数相加， 若结果未变成0，则将结果插入到结果多项式。若当前被检测项指数不等，则将指数较小者插入到结果多项式。若有一个多项式已检测完，则将另一个多项式剩余部分直接连接到结果多项式。5 长整数（任意长度）四则运算演示程序（实验类型：综合型）1）问题描述：设计一个实现任意长的整数进行加法运算的演示程序2）实验要求 : 利用双向循环链表实现长整数的存储，给各结点含一个整型变量。任何整型变量的的范围是 - （215-1 ）（215-1 ） 。输入和输出形式：按照中国对长整数的表示习惯，每四位一组，组间用逗号隔开。3) 实现提示：每个结点中可以存放的最大整数为215-1=32767 ， 才能保证两数相加不会溢出。但若这样存，即相当于按32768 进制数存，在十进制数与32768 进制数之间的转换十分不方便。故可以在每个结点中仅存十进制数的4 位，即不超过9999 的非负整数，整个链表视为万进制数。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 21 页 - - - - - - - - - 可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点的树木。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。4）注意问题 : 不能给常整数位数规定上限。程序设计源代码如下：第一题：#include #include #include typedef int ElemType; /元素类型typedef struct LNode ElemType data; struct LNode *next; LNode; typedef LNode *LinkList; LinkList head; LinkList L; /定义单链表头指针L LinkList L1; LinkList L2; LinkList L12; LinkList Creatlist_L() /尾插入法建立单链表 LinkList L,p,r; int x; r=L=(LinkList)malloc(sizeof(LNode); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 21 页 - - - - - - - - - L-next=NULL; cinx; while(x!=0) p=(LinkList)malloc(sizeof(LNode); p-data=x; p-next=NULL; r-next=p; r=p; cinx; return L; LinkList Show_L(LinkList L) LinkList p2; p2=L; while(p2-next!=NULL) coutnext-datanext; 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-next; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 21 页 - - - - - - - - - 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; cout1.建立单链表 :endl; cout2.连接单链表 :endl; cout3.输出单链表 :endl; cout0.程序结束 :endl; coutendl; cout 请选择操作序号:choice; if(choice=0) cout 成绩结束，任意键退出！endl; break; switch(choice) case 1: int choice1; cout 开始建立单链表1:endl; L1=Creatlist_L(); coutendl; cout 表 1 建立完毕 !endl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 21 页 - - - - - - - - - cout 是否继续建立单链表2 ？n 1.继续 2.返回 choice1; if(choice1=1) cout 开始建立单链表2endl; L2=Creatlist_L(); coutendl; cout 表 2 建立完毕 !endl; coutendl; cout 单链表建立完毕!endl; break; case 2: cout 开始连接单链表1，2!endl; L12=Contlist_L(L1,L2); coutasfsdfsagshdfhgdfhjdfhhdfhasdfendl; break; case 3: int choice1; cout 请选择输出哪个表：endl; cout1.表 1 2.表 2 3.联立后的表12 choice1; switch(choice1) case 1: cout 单链表 1 为： endl; Show_L(L1); coutendl; break; case 2: cout 单链表 2 为： endl; Show_L(L2); coutendl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 21 页 - - - - - - - - - break; case 3: cout 联立后的表12 为:endl; Show_L(L12); coutendl; break; break; 第二题：#include #include #include #define Maxsize 100 /表中元素的最大个数typedef int ElemType; /元素类型typedef struct list ElemType dataMaxsize; /静态线性表 int length; /表的实际长度SqList; /顺序表的类型名int m=0; SqList *creat_SqList(SqList *L) /建立线性表，并输入线性表元素 L=(SqList *)malloc(sizeof(SqList); cout请输入线性表数据:x; if(x=0) break; L-datam=x; L-length=m; return L; SqList *all_SqList(SqList *L) cout已建立的线性表为:endl; for(int i=0;ilength;i+) coutdatai ; coutendl; return L; int serch_SqList(SqList *L,int y) /查询元素函数 for(int j=0;jlength;j+) if(L-dataj=y) cout 表中含有此数据，位于表中第 j+1 位!length-1) cout 表中没有此数据!endl; break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 21 页 - - - - - - - - - else continue; void judje_SqList(SqList *L) /判断是否对称函数 if(m%2=0)/线性表元素个数为偶数个 cout 中心元素为 datam/2endl; for(int k=0;k=m/2+1;k+) if(k=m/2+1) cout*该线性表对称!*datak=L-datam-1-k) continue; else cout *该线性表不是对称的!*endl; break; else /线性表元素个数为奇数个 cout 中心元素为 datam/2endl; for(int t=0;t=m/2+1;t+) if(t=m/2+1) cout*该线性表对称!*datat=L-datam-1-t) continue; else cout *该线性表不是对称的!*endl; break; int main() SqList *L1; int choice; for(;) cout+ 主菜单 +endl; cout1.新建线性表 ;endl; cout2.遍历线性表 ;endl; cout3.查找表中元素 ;endl; cout4.判断是否对称 ;endl; cout0.退出程序 ;endl; coutendl; cout 请输入操作序号：choice; if(choice=0) break; switch(choice) case 1: L1=creat_SqList(L1); cout 线性表长度为:mendl; break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 21 页 - - - - - - - - - case 2: cout 开始遍历线性表：endl; all_SqList(L1); break; case 3: int y; cout 请输入要查找的元素：y; serch_SqList(L1,y); break; case 4: cout 正在检测是否对称!endl; judje_SqList(L1); break; return 0; 第三题：#include #include #include # define Maxsize 50 /元素最大容量typedef int ElemType; /元素类型typedef struct list 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 21 页 - - - - - - - - - ElemType numMaxsize; ElemType codeMaxsize; int length; /表的实际长度Juserfu; /顺序表的类型名Juserfu L; /定义一个顺序表L int j=0; /围坐的总人数Juserfu *creat_Juserfu(Juserfu *L) /建立线性表，并输入线性表元素 L=(Juserfu *)malloc(sizeof(Juserfu); cout请分别输入每个人的序号和密码:sm; 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请输入初始密码：x_code; for(j;j0;j-) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 21 页 - - - - - - - - - x_num=(x_num+x_code-1)%j; coutx_num 出列者为 numx_num 号！ codex_num; for(x_num;x_numnumx_num=L-numx_num+1; L-codex_num=L-codex_num+1; return L; void main() /int s; Juserfu *L1; cout请输入每位围坐者的密码!endl; L1=creat_Juserfu(L1); cout共围坐人数为：lengthendl; cout密码分别为：endl; for(int i=0;ij;i+) coutnumi codei ; output_Juserfu(L1); 第四题：#include #include #include typedef struct PolyNode float coef; /系数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 21 页 - - - - - - - - - float exp; /指数 PolyNode *next; /指针域PolyNode; typedef PolyNode *Polynomial; Polynomial A; /定义多项式A Polynomial creat_Poly() Polynomial L,p,r; float x_coef; float x_exp; r=L=(Polynomial)malloc(sizeof(PolyNode); L-next=NULL; cout请依次输入多项式的系数和指数（0,0 为输入结束） ：x_coefx_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; cinx_coefx_exp; return L; Polynomial show_Poly(Polynomial L) Polynomial p1; p1=L; while(p1-next!=NULL) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 21 页 - - - - - - - - - coutnext-coefXnext-expnext; coutnext; p2=B-next; C=(Polynomial)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-expexp) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 21 页 - - - - - - - - - D=(Polynomial)malloc(sizeof(PolyNode); D-coef=p1-coef; D-exp=p1-exp; D-next=NULL; p3-next=D; p3=D; p1=p1-next; else D=(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=(Polynomial)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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 21 页 - - - - - - - - - D-exp=p2-exp; D-next=NULL; p3-next=D; p3=D; p2=p2-next; return C; void main() Polynomial 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 #include #include typedef struct Node int data; Node* next; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 21 页 - - - - - - - - - Node* front; Node; typedef Node *Operation; Operation creat() Operation L; Operation p1,p2; L=(Operation)malloc(sizeof(Node); L-next=NULL; L-front=NULL; p2=L; cout请输入数据 :next=NULL; p1-front=NULL; cinp1-data; if(p1-datanext=p2-next; p2-next=p1; L-front=p1; p1-front=p2; p2=p1; return L; Operation add(Operation A,Operation B) Operation C; Operation a,b; Operation p1,p2; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 21 页 - - - - - - - - - int x,y=0; C=(Operation)malloc(sizeof(Node); C-next=NULL; C-front=NULL; p2=C; a=A-front; b=B-front; while(1) p1=(Operation)malloc(sizeof(Node); x=a-data+b-data+y; if(x9999) x=x%10000; y=x/10000; p1-data=x; p1-next=p2-next; p2-next=p1; C-front=p1; p1-front=p2; p2=p1; a=a-front; b=b-front; if(b=B&a=A) break; return C; void output(Operation A) Operation p; p=A-front; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 21 页 - - - - - - - - - while(1) coutdata; if(p=A-next) break; p=p-front; cout,; void main() Operation A; Operation B; Operation C; cout建立表 A：endl; A=creat(); cout建立表 B： endl; B=creat(); cout运算后 C 为:endl; C=add(A,B); output(C); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 21 页 - - - - - - - - -