201560140140--袁若飞--实验1：线性表地基本操作及其应用

1、Zhongyuan University of Technology数据结构实验1 ：线性表的基本操作及其应用班级：RB软工移151学号：201560140140:袁若飞实验一线性表一、实验目的1、帮助读者复习C+语言程序设计中的知识。2、熟悉线性表的逻辑结构。3、 熟悉线性表的基本运算在两种存储结构上的实现，其中以 熟悉链表的操作为侧重点。二、实验容本次实验提供4个题目，每个题目都标有难度系数，*越多难 度越大，题目一、二是必做题。题目三、题目四选作。三、实验准备知识1、请简述线性表的基本特性和线性表的几种基本操作的机制 答：线性表的基本特性是：对线性表中某个元素ai来说，称其前面的元素ai

2、-1为ai的直接前驱，称其后前面的元素ai+1为ai的直接后继。显然，线性表中每个元素最多有一个直接前驱和一个直接后继。 答：线性表的几种基本操作的机制有六个：（1）初始化线性表initial_List（L）建立线性表的初始结构，即建空表。 这也是各种结构都可能要用的运算。（2 ）求表长度 List_le ngth（L）即求表中的元素个数。（3） 按序号取元素get_element（L,i）取出表中序号为i的元素。（4） 按值查询List_locate（L,x）取出指定值为x的元素，若存在该元素， 则返回其地址；否则，返回一个能指示其不存在的地址值或标记。（5） 插入元素 List_inser

3、t（L,i,x）在表L的第i个位置上插入值为 x的元素。显然，若表中的元素个数为n，则插入序号i应满足1<=i<=n+1。（6） 删除元素List_delete（ L，i）删除表L中序号为i的元素，显然， 待删除元素的序号应满足1<=i<=n。2、掌握线性表的逻辑结构。3、掌握线性表的链式存储结构。4、熟练掌握线性表的插入、删除等操作。四、实验容题目一：顺序表的基本操作问题描述实现顺序表的建立、求长度，取元素、修改元素、插入、删 除等基本操作。基本要求（1）依次从键盘读入数据，建立顺序表；（2）输出顺序表中的数据元素；（3）求顺序表的长度；（4）根据指定条件能够取元素和

4、修改元素；（5）实现在指定位置插入和删除元素的功能。测试数据由学生任意指定。运行结果如下图：1）实现删除功能' ' D:C+ + Wcrb S缺“ h 吟艸 p 'TTWWW：1 2 3 4 5 & 7 e 911 L2 L3 14 15 IG 17 IS 19 2U输入要刪除的记灵号;LO删徐成功！田际后的幀.序齐力：1 2 3 4 5 6 7 3 y 11 12 L3 14 L& 16 17 13 19 刃 Press ar key to cOTiHrne.2）实现取元素功能12 L3 1417 18 L? 2R鐵A茅取元素的.l¥号m斯取

5、的元秉Lid孤兀壽应剔！取尤茶启的顺序恵邓1 2 3 d b & 7 y ¥11 Id 1J 1< lb lb 17 18 IV 2H frat a 抽丫 koy to cantinuo3）实现查找功能占我叵走罰打师|-吞11H II*誇 1*1 IE 1$ t?If ?H输入叢古7T孝誰H设元素个数最大为100声明一个结构体来存放顺序表定义存储表中元素的数组定义表长度分量按序号求元素运算的子函数 声明按值查询元素的子函数 声明插入元素的子函数 声明删除元素的子函数表结构变量的定义为表分配空间定义整型变量赋值给表中的元素填入删除容定义表的长度杏亓,看咸;功I您元茶尼旳I

6、匝序査.尬：能元素后的哽序表为；券与1_!8 直:！ L2 U 141E；丄吕：17 丄臓 *9 空 匕吕1* k亡屮 匸已 許t： JniiU4）实现插入功能< llUCDUeUCSU.CXE-PUfl ? 3 4 5 6 7 S ? Wil 12 1W 14 IS 1ft 17 18 If喻？'芟桂前亍霍:岀喻入要播旳世营=却恫入元素删t)!：张入元翥辰乩顺带表商：1 Z 3 4 5 6 ? S ? IH 11 12 13 14 15 16 17 1R If ?B 14 Prus *网 “y W mnMnu«J源代码(加注释)#include<stdio.h&

7、gt;#include <iostream.h>#include <malloc.h>#define maxlen 100/typedef struct/ int datamaxlen;/int listlen;/seqlist;void get_element(seqlist *L,int I,int *x); / int List_locate(seqlist L,int I,int x);/bool List_insert(seqlist *L,int I,int x);/bool List_delete(seqlist *L,int I);/void main(

8、) seqlist *L;/L=(seqlist *)malloc(sizeof(seqlist); / int i;/for(i=1;i<=20;i+)/L->datai-1=i;/L->listlen=20;/coutvv"删除前的顺序表:n"for(i=1;i<=L->listlen;i+)/ coutv<L->datai-1vv""cout<v"n输入要删除的纪录号："；cin>>i;/if(List_delete(L,i)/ cout<<"n删

9、除成功！删除后的顺序表为:n"for(i=1;i<=L->listlen;i+)/ cout<<L->datai-1vv""bool List_delete(seqlist *L,int i)/ int j;/if(L->listlen<=0)/ coutvv"下溢出错！"return false;/ if(i>L->listlen|iv=0)/ coutvv"删除位置错！"return false;/else for(j=i;jv=L->listlen-1;j+)

10、 /L->dataj-1=L->dataj;L->listlen-;/return true;/void main() seqlist *L;/L=(seqlist *)malloc(sizeof(seqlist); / int i;/for(i=1;iv=20;i+)/L->datai-1=i;输岀表中元素用户输入删除的记录用删除元素的子函数向前批量移动元素删除元素的子函数定义一个整型变量空表不能删除元素返回false删除元素不存在返回false向前批量移动元素表长度减1返回true表结构变量的定义为表分配空间定义整型变量 赋值给表中的元素L->listlen=

11、20;/coutvv"取元素前的顺序表:n" for(i=1;i<=L->listlen;i+)/ coutv<L->datai-1vv"" cout«"n输入要取元素的序号："定义表的长度输岀表中元素cin>>i;/if(get_element( L, i)/ cout<v"n取元素成功！取元素后的顺序表为for(i=1;i<=L->listlen;i+) cout<<L->datai-1vv""用户输入要取元素的记录 用

12、取元素的子函数:n"bool get_element(seqlist *L,int i)/ int x;if(i<1|i>L->listlen)/ coutvv"下溢出错！"/return false;else x=L->datai-1;/coutvv"n 所取的元素n"coutvvxvv" "/return true;void main()取元素的子函数要取的元素不存在空表无元素取岀相应元素输岀对应元素 seqlist *L;/L=(seqlist *)malloc(sizeof(seqlist);

13、 / int i,x,a;/for(i=1;iv=20;i+)/L->datai-1=i;L->listlen=20;/coutvv"查找元素前的顺序表:n"for(i=1;iv=L->listlen;i+)/ coutvvL->datai-1vv""表结构变量的定义 为表分配空间 定义三个整型变量 赋值给表中的元素定义表的长度输岀表中元素cout<v"n输入要查元素cin»x;a=List_locate(L,x);/用户输入查找的记录if(a!=O) cout<<"n 查元素成功！

14、查元素后的顺序表为：n"coutvvavv""cout<<"n取元素后的顺序表为:n"/for(i=1;iv=L->listlen;i+)/ coutvvL->datai-1vv""取元素后的顺序输岀表中元素else coutvv"n查无此元素成功!int List_locate(seqlist *L,int x)/ int i;/for(i=0;ivL->listlen;i+)/ if(L->datai=x) return(i+1);return(O);/void main()

15、 seqlist *L;/L=(seqlist *)malloc(sizeof(seqlist); / int i,x,a;/for(i=1;iv=20;i+)/L->datai-1=i;/L->listlen=20;/coutvv"插入元素前的顺序表:n" for(i=1;iv=L->listlen;i+)/:n"按值查询元素的子函数定义一个整型变量依次比较各个元素/找到元素X的位置返回其序号未找到则返回0值表结构变量的定义 为表分配空间 定义三个整型变量 赋值给表中的元素 填入插入容定义表的长度输岀表中元素用户输入插入的记录用户输入插入的位置

16、 coutvvL->datai-1vv"coutvv"n输入要插的元素:" cin>>x;/coutvv"n输入要插的位置:" cin>>i;/a=List_insert(L,i,x);if(a=1) cout<<"n插入元素成功！:n"cout<<"n插入元素后的顺序表为:n"for(i=1;i<=L->listlen;i+) coutv<L->datai-1vv""/输岀表中元素else if(a=0)c

17、outvv"溢出，不能插入！coutvv"插入位置错!elseint List_insert(seqlist *L,int i,int x)/溢出，不能插入插入元素的子函数int j;/coutvv"溢出，不能插入！"return 0;/溢出，不能插入返回else if(iv1|i>L->listlen+1) coutvv"插入位置错！"/插入围错return -1 ;/返回并结束elsefor(j=L->listlen-1;j>=i-1;j-)/往后移动元素L->dataj+1= L->dataj

18、;L->datai-1=x;/填入插入的元素L->listlen+;/修改表长度return 1;/返回定义一个整型变量if(L->listlen=maxlen)题目二：单链表的基本操作问题描述实现带头结点的单链表的建立、 插入、删除等单链表的基本操作。 基本要求求长度，取元素、修改元素、（1）依次从键盘读入数据，建立带头结点的单链表;（2）输出单链表中的数据元素（3）求单链表的长度；（4）根据指定条件能够取元素和修改元素；（5）实现在指定位置插入和删除元素的功能。测试数据由学生任意指定。创建单链表读入数据：1 2 3 4 5 4 2输出单链表中数据为：1 2 3 4 5 4

19、 2 返回单链表长度：7在5前面插入数据元素：1 2 3 4 4 5 4 2删除第一个数据元素：2 3 45 4 2 修改最后一个数据元素：1 234 5 4 1设计分析：从上面的问题描述可以知道我们要实现的操作：“依次从 键盘读入数据，建立带头结点的单链表，然后就是对此单链表 的一些基本操作如增删改查等”，对此我们设计出了一个单链 表用于存放数据，所以对数据应该采用的是链式存储结构。每 个元素之间的关系，可通过在每个节点当中设置一个指针来存 放下一个元素的地址来体现。其次就是基本操作就是对此单链 表中数据存储结构的更改，通过调用链表指针操作其存储地址。于是可以声明结构类型为：typedef

20、struct LNodeElemType data;struct LNode *n ext;LNode,*Li nkList;1. 先动态创建一个单向循环链表，每个节点包含数据的地址和 指向下一个节点的地址。2. 查找单链表的头节点并返回其地址，依次从键盘输入数据并 把它们的地址返回。3. 根据单链表的头结点的地址依次输出单链表中数据元素，并 返回单链表的长度。4. 从单链表中删除出数据元素的节点，并返回新的单向循环链 表的头指针的值。5. 利用预定义的指针指向指定位置插入或删除单链表中的数 据元素。运行结果如下图:1）实现建立单链表功能I *D!C+W/orkiparet&stlDe

21、bu.gteEtl .exe*O-iHdJ > 1包建氐谦加，读兀骯5-遍历，&获取扶度，7-修改 你必须先刨建单槌裘車槌妄创建M3.26 8 2 3 65毕槌表创楚咸功请输A像董羅迪郭盍的或置和直 中闾用空格隔尸例如1 22）实现输出功能3）实现链表长度功能'D：C t 十 Wq rkS pa cct-3tlC*cb u. cxc'位人 気話入插 血返必丄整输TE5S输记爭 時A你1单月Y冒厂h期 AK旳核2B期O 教干 4-康元臺5-遍历，7-修改中间用宁格隔开。创如I 1 24）实现取元素功能J |>tCk +Wo斤 KE*TWTrOt 篇也站E萄畫

22、1辽的躁便腐应的STT：-玫i 2-tD，3-靳誦* 4谯元素，5-遍历，&-巒长庫.7-ti1"± 5 1单池入U.：生咸MH 腳护幅霖輕腑于-353-Sij魏W孵翳魁+<p5）实现修改功能 'D：匚+ .¥0七知帀于-茁轼讥>?01冯护社1尸強"I谙苕搔偵避苴亍的操旧上虫工曙亍|卜逋£, 1到也2-JfetD. 3-lf 4请元養逅历&翹玄瓷卡代 你必预先血K单钳表.中间用主格隔开。例如1 2華链表创建咸功！中间用空槪瞭例如1212 5 3源代码(加注释)#include<stdio.h>#i

23、nclude<malloc.h>#define List_lnit_Size 100#define Listincrement 10#define ElemType int#define null 0typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;void main()void Create(LinkList & L);void Insert(LinkList &L,int i,ElemType e);void Delete(LinkList & L,int i);El

24、emType GetElem(LinkList & L,int i);void Output(LinkList & L);int GetLength(LinkList & L);void Modify(LinkList &L,int i,ElemType elem);LinkList l;int choose,location,value,times=O,createTimes=O,insertTimes=O;printf("请选择你要执行的操作对应的数字：n0-退出，1-创建，2-添加，3-删除，4-读元素，5-遍历，6-获取长度，7-修改n&quo

25、t;);printf("你必须先创建单链表n");scanf("%d", &choose);while(choose!=0)if(choose=1)Create(l);else if(choose=2)printf("请输入你要添加元素的位置和值，中间用空格隔开。例如：1 2n");if(insertTimes=0)printf("切记：位置必须为1n");insertTimes+;elseprintf("切记：位置要大于 0，并且小于 %dn",GetLength(l);scanf(&

26、quot;%d %d",&location,&value);Insert(l,location,value);else if(choose=3)printf("请输入你要删除元素的位置：n");printf(" 切记：位置要大于 0，并且小于 %dn",GetLength(l); scanf("%d",&location);Delete(l,location);else if(choose=4)printf("请输入你要读的数据的位置：n");printf(" 切记：位置

27、要大于 0，并且小于 %dn",GetLength(l); scanf("%d",&location);printf("%dn",GetElem(l,location);else if(choose=5)Output(l);else if(choose=6)printf("%dn",GetLength(l);elseprintf("请输入你要修改元素的位置和修改后的值，中间用空格隔开。例如：1 2n");printf("切记：位置要大于0,并且小于 %dn",GetLength

28、(l);ElemType e1=0;scanf("%d %d",location,e1);Modify(l,location,e1);+times;if(times%10=0)printf("请选择你要执行的操作对应的数字：n0-退出，1-创建，2-添加，3-删除，4-读元素，5-遍历，6-获取长度n");printf("请确认你已经创建单链表，如果没有的话，请首先创建！”)；scanf("%d", &choose);void Create(LinkList & L)L=(LinkList)malloc(si

29、zeof(LNode);建立带头节点的单链表L->next=null;printf("单链表创建成功！n");void Insert(LinkList &L,int i,ElemType e)在第 i 个位置插入元素LinkList p,s;p=L;int j=0;while(p&&j<i-1)p=p->next ;/获得位置i处的指针+j;printf("元素插入成功！n");if(p&&(j=i-1)s=(LinkList)malloc(sizeof(LNode);s->data=e;s

30、->next=p->next;p_>next=s;printf(”元素插入成功！n");void Delete(LinkList & L,int i)LinkList p=L,p1=p->next;int j=0;if(p->next&&i >0)while(p1 &&j<i-1)p=p1;p1=p->next;+j;if(j=i-1)p->next=p1->next;printf("元素删除成功！n");else1！ n");printf("元

31、素删除失败，因为你输入的位置小于ElemType GetElem(LinkList & L,int i)LinkList p=L->next;int j=1;ElemType e;while(p&&j<i)p=p->next;+j;if(p&&(j=i)/此单链表有头指针，索引和下标一致e=p->data;printf("成功获取元素！");return e;void Output(LinkList & L)LinkList p=L->next;printf(”单链表中的元素分别为：”)；whil

32、e(p)printf("%d ",p->data);p=p_>next;printf("n");int GetLength(LinkList & L)LinkList p=L;int j=0;while(p)p=p->next;+j;return j;void Modify(LinkList &L,int i,ElemType elem)LinkList p=L->next;int j=1;ElemType e;while(p&&j<i)p=p->next;+j;if(p&&am

33、p;(j=i)/此单链表有头指针，索引和下标一致p->data=elem;printf(" 修改元素成功！ n");elseprintf("修改元素失败!n");题目三：约瑟夫环（*）问题描述约瑟夫（Joseph）问题的一种描述是：编号为 1,2,n的n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开 始任选一个正整数作为报数上限值 m从第一个人开始按顺时针 方向自1开始顺序报数，报到m时停止报数。报m的人出列，将 他的密码作为新的m值，从他在顺时针方向上的下一个人开始重 新从1报数，如此下去，直至所有人全部出列为止。试设计一个 程序求

34、出出列顺序。基本要求利用单向循环链表存储结构模拟此过程，按照出列的顺序印出 各人的编号。测试数据由学生任意指定。女口： m的初值为20; n的值为7;密码：3，1，7，2，4，8,4；（正确的输出结果应为6，1, 4, 7, 2, 3, 5）。（报告上要求写出多批数据测试结果）实现提示程序运行后首先要求用户输入初始报数上限值 m人数n,（设 n< 30）。然后输入各人的密码。选作容向上述程序中添加在顺序结构上实现的部分。运行结果如下图：约瑟夫环实现功能o;2 85lo5_y 2 2 s 2 s ? = 1池迫焉S虫曙囹帀用憩密密密总型雋 “rtlJn/= J -/Tl IJTTJi -1

35、1 JTTJL frw ,JTT r* JfTT JTl f .-l 2 3 4 5 6 7 8- 9 u 1 2 3 4 5 & 孑 p g _u请输入开始位直，请输入幵抬密码：13£516 丄 §717丄丄 2012461415PfeM宫 any Ikey t.口 cont i olie 哄川L；!- R J去亠一源代码(加注释)#include <stdlib.h>#include <stdio.h>#include <Math.h>typedef struct nodeint number;int password;str

36、uct node* next;Node,*Linklist;Linklist CreateLinklist(int amount) int i;Node *s=NULL,*r=NULL;Linklist L=NULL,R=NULL;for(i=0;i<amount;i+)s=(Node*)malloc(sizeof(Node);if(s=NULL)printf(”空间申请失败r);exit(O);s->number=i+1;s->password=rand()%10+1;printf("%4d 的密码 %4dn",s->number,s->pa

37、ssword);if(i=0)L=s;r=s;else r->next=s;r=s; R=r;r->next=L;return(R);void DeleteLinklist(Linklist R,int start,int amount,int num)Node *position=NULL,*p=NULL,*q=NULL;int i,k,secret;position=R;secret=start;for(i=num;i<=amount;i+)p=position;for(k=1;k<secret;k+)p=p->next;q=p->next;p->

38、next=q->next;secret=q->password;printf("%5d",q->number);if(i%10=0)printf("n");position=p;free(q);int main()int amount,start,num;Linklist R=NULL;printf("n 请输入总人数：");scanf("%d", &amount);R=CreateLinklist(amount);printf("n请输入开始位置：");scanf(&

39、quot;%d", &start);printf("n请输入开始密码：");scanf("%d",&num);DeleteLinklist(R,start,amount,num);return(1);题目四：多项式的表示及相加(* )问题描述设计一个算法，以实现一元稀疏多项式的加法运算。基本要求(1) 输入并建立多项式；(2) 输出多项式，输出形式为整数序列：n, c1，e1, c2,e2, , , en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；(3) 多项式a和b相加，建立多项式a+b。测

40、试数据由学生任意指定。实现提示用带表头结点的单链表存储多项式。选作容多项式a和b相减，建立多项式a-b。运行结果如下图：多项式相加实现功能：'D：C + + WorkS p a cetest4.D eb uqtest4.exe'AB*- A E W 镶疇湘 顶多多式 多多项L 2+2.5i+3. 2i 3-2. 5x 5-1. 2+2. 5x3. 2x 3+2. 5x 5+5. -29x342. 5x+l. 25. 4z" 10+2. 5z"5+3- 2i*3+2. 5i5. 4za 10+6.'3+5xtc cantiniie.4kT+102源代码

41、：(加注释)/ 文件名：exp2-7.cpp#include <stdio.h>#include <malloc.h>#define MAX 20/多项式最多项数typedef structdouble coef;/定义存放多项式的数组类型/系数int exp;/指数 PolyArrayMAX;typedef struct pnodedouble coef;/定义单链表结点类型/系数int exp;/指数struct pnode *next; PolyNode;void DispPoly(PolyNode *L)bool first=true;/输岀多项式/first为

42、true表示是第一项PolyNode *p=L->next; while (p!=NULL)if (first) first=false;else if (p->coef>0) printf("+");if (p->exp=0)printf("%g",p->coef);else if (p_>exp=1) printf("%gx",p->coef);elseprintf("%gxA%d",p->coef,p->exp);p=p->next;printf(&

43、quot;n");/销毁单链表void DestroyList(PolyNode *&L) PolyNode *p=L,*q=p->next;while (q!=NULL)free(p);p=q; q=p->next;free(p);尾插法建表 void CreateListR(PolyNode *&L,PolyArray a,int n) / PolyNode *s,*r;int i;L=(PolyNode *)malloc(sizeof(PolyNode);/ 创建头结点L->next=NULL;r=L;for (i=0;i<n;i+)r始

44、终指向终端结点，开始时指向头结点s=(PolyNode *)malloc(sizeof(PolyNode);创建新结点s->coef=ai.coef; s->exp=ai.exp; r->next=s;r=s;r->next=NULL;/将*s插入*r之后/终端结点next域置为NULLvoid Sort(PolyNode *&head)/按exp域递减排序求两有序集合的并/创建头结点/复制结点/复制结点PolyNode *p=head->next,*q,*r;if (p!=NULL)r=p->next; p->next=NULL;p=r;wh

45、ile (p!=NULL) r=p->next; q=head;/若原单链表中有一个或以上的数据结点r保存*p结点后继结点的指针/构造只含一个数据结点的有序表r保存*p结点后继结点的指针while (q->next!=NULL && q->next->exp>p->exp)q=q->next;/在有序表中找插入*p的前驱结点*qp->next=q->next; / 将*p 插入到 *q 之后q->next=p;p=r；void Add(PolyNode *ha,PolyNode *hb,PolyNode *&hc) / PolyNode *pa=ha->next,*pb=hb->next,*s,*tc; double c;hc=(PolyNode *)malloc(sizeof(PolyNode);tc=hc;while (pa!=NULL && pb!=NULL)if (pa->exp>pb->exp)s=(PolyNode *)malloc(sizeof(PolyNode); s_>exp=pa_>exp;s_>coef=pa_>coef; tc-&g