大数据结构--试验报告材料线性表地基本操作.docx

《大数据结构--试验报告材料线性表地基本操作.docx》由会员分享，可在线阅读，更多相关《大数据结构--试验报告材料线性表地基本操作.docx（27页珍藏版）》请在三一文库上搜索。

1、一、实验目的二、实验内容和要求三、源代码1顺序表的代码2单链表的代码四、测试结果1顺序表的测试结果2单链表的测试结果五、心得体会实验一线性表的根本操作及其应用一、实验目的1、帮助读者复习C+语言程序设计中的知识.2、熟悉线性表的逻辑结构.3、熟悉线性表的根本运算在两种存储结构上的实现.4、掌握顺序表的存储结构形式及其描述和根本运算的实现.5、熟练掌握动态链表结构及有关算法的设计二、实验内容题目一：顺序表的根本操作问题描述实现顺序表的建立、求长度,取元素、修改元素、插入、删除等顺序表的基 本操作.根本要求1依次从键盘读入数据,建立带头结点的顺序表；2输出顺序表中的数据元素3求顺序表的长度；4根据

2、指定条件能够取元素和修改元素；5实现在指定位置插入和删除元素的功能.6根据算法,将两个有序的顺序表合并成一个有序顺序表.测试数据由学生任意指定.题目二：单链表的根本操作问题描述实现带头结点的单链表的建立、求长度,取元素、修改元素、插入、删除等 单链表的根本操作.根本要求1依次从键盘读入数据,建立带头结点的单链表；2输出单链表中的数据元素3求单链表的长度；4根据指定条件能够取元素和修改元素；5实现在指定位置插入和删除元素的功能.6根据算法,将两个有序的单链表合并成一个有序单链表 测试数据 由学生任意指定.三、源代码 一 顺序表的根本操作 #include using namespace std;

3、#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef int ElemType;#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct / 结构体ElemType *elem;int length;int listsize;SqList;SqList Lx;Status InitList_SqSqList &L / 分配空间 L.elem=new ElemTypeLIST_

4、INIT_SIZE; if!L.elemexitOVERFLOW;L.length =0;L.listsize=LIST_INIT_SIZE; return OK;27Status ListInsert(SqList &L,int i,ElemType e) / int *q,*p;ElemType *newbase;if(iL.length+1) return ERROR; if(L.length=L.listsize)插入新元素 newbase=new ElemTypeL.listsize+LISTINCREMENT;if(!newbase) exit(OVERFLOW);L.elem=n

5、ewbase;L.listsize+=LISTINCREMENT;q=&(L.elemi-1);for (p=&(L.elemL.length-1);p=q;-p) *(p+1)=*p;*q=e;+L.length;return OK;Status Listlength(SqList L) / int *p=L.elem; /while(p) return (L.length); Status GetElem(SqList L, int i,ElemType &e) if(iL.length)return ERROR;else长度判断线形表是否存在/ 取元素 e=L.elemi-1; retu

6、rn e;void MergeList(SqList La,SqList Lb,SqList &Lc) / 合并 ElemType ai,bj;InitList_Sq(Lc);int i=1,j=1,k=0;int La_len,Lb_len;La_len=Listlength(La);Lb_len=Listlength(Lb); while(i=La_len)&(j=Lb_len) GetElem(La,i,ai);GetElem(Lb,j,bj); if(ai=bj) ListInsert(Lc,+k,ai);+i; else ListInsert(Lc,+k,bj);+j; while(

7、i=La_len) GetElem(La,i+,ai);ListInsert(Lc,+k,ai);while(j=Lb_len) GetElem(Lb,j+,bj);ListInsert(Lc,+k,bj);显示输入元素void show(SqList L,int i)/ int j;ElemType k;cout 顺序表显示如下 :endl;for(j=0;ji-1;j+) k=L.elemj;coutk; if(j=i-1 & i0) k=L.elemj; coutk; coutendl;void create(SqList &L,int n) / int e;for(int i=0;ie

8、; L.elemi=e; L.length=i+1; 删除修改Status ListDelete_Sq(SqList &L,int i,ElemType &e) / ElemType *p, *q;if(iL.length) return ERROR; p=&(L.elemi-1);e=*p; q=L.elem+L.length-1;for(+p;p=q;+p) *(p-1)=*p;-L.length;return OK;Status Listxiugei(SqList &L,int i,ElemType &e) / if(iL.length) return ERROR;else L.elem

9、i-1=e;return OK; void shuru(SqList &L1) / 顺序表的创立 int a;InitList_Sq(L1);couta;cout请输入顺序表的元素(共a个)endl; create(L1,a);show(L1,a);void chaxun(SqList &L1)/取第 i 个位置的元素 int j;ElemType e1;coutj;while(jListlength(L1) cout 输入有误,请重新输入 endl; coutj; GetElem(L1,j,e1);cout 取出的元素为 :e1endl; void xiugai(SqList &L1) /

10、修改第 i 个位置的元素 int a;int j; ElemType e1;a=L1.length;coutj;while(jListlength(L1) cout 输入有误,请重新输入 endl; coutj; coute1;Listxiugei(L1,j,e1);cout 修改后的顺序表数据 :endl;show(L1,a);void shanchu(SqList &L1) / 删除顺序表里的元素 int a;int j; ElemType e1;a=L1.length;coutj;while(jListlength(L1) cout 输入有误,请重新输入 endl; coutj; Lis

11、tDelete_Sq(L1,j,e1);cout 修改后的顺序表数据 :endl;show(L1,a-1);void charu(SqList &L1) / 插入元素到顺序表里 int a; int j; ElemType e1;a=L1.length;coutj;while(jListlength(L1) cout 输入有误,请重新输入 endl;coutj; coute1;ListInsert(L1,j,e1);cout 修改后的顺序表数据 :endl;show(L1,a+1);void hebing(SqList &L3) / 合并两个顺序表 SqList L1,L2;int a,b;I

12、nitList_Sq(L1); InitList_Sq(L2);couta;coutvv请输入第一个有序表的元素(共a个)endl;create(L1,a);show(L1,a);coutb;coutvv请输入第二个有序表的元素(共vvbvv个)endl;create(L2,b);show(L2,b);MergeList(L1,L2,L3);coutvv 合并后的有序表如下： ; show(L3,a+b);void main()/主菜单 int choice;for(;) cout顺序表的根本操作 endl;cout1.顺序表的创立 endl;cout2.顺序表的显示 endl;cout3.顺

13、序表的长度 endl;cout4.取第 i 个位置的元素 endl;cout5.修改第 i 个位置的元素 endl;cout6.插入元素到顺序表里 endl;cout7.删除顺序表里的元素 endl;cout8.合并两个顺序表 endl;cout9.退出系统 endl;coutchoice;switch(choice) case 1: shuru(Lx);break;case 2:show(Lx,Lx.length);break;case 3:cout 顺序表的长度 :Listlength(Lx)endl;breakcase 4:chaxun(Lx);break;case 5:xiugai(L

14、x);break;case 6:charu(Lx);break;case 7:shanchu(Lx);break;case 8:hebing(Lx);break;case 9:cout退出系统 !endl;exit(0);break;default :cout输入有误,请重新选择 endl;break; 二 单链表的根本操作#include using namespace std;#define true 1#define false 0#define ok 1#define error 0#define overflow -2typedef int Status;typedef int El

15、emType;typedef struct LNode / 存储结构 ElemType data;struct LNode *next;LNode,*LinkList;void CreateList(LinkList &L,int n) / 尾插法创立单链表 LinkList p;L=new LNode;L-next=NULL; / 建立一个带头结点的单链表LinkList q=L; / 使 q 指向表尾 for(int i=1;ip-data; p-next=NULL; q-next=p;q=p; Status GetElem(LinkList L,int i,ElemType &e)/ 取

16、第 i 个元素 LinkList p=L-next;int j=1; while(p&jnext;+j; if(!p|ji) return error; / 第 i 个元素不存在 e=p-data;return ok;Status LinkInsert(LinkList &L,int i,ElemType e)/ LinkList p=L;插入int j=0;while(p&jnext;+j; / if(!p|ji-1)return error; /iLinkList s=new LNode; /寻找第 i-1 个结点小于 1 或者大于表长加 1 生成新结点s-data=e; s-next=p

17、-next; /插入 L 中p-next=s; return ok;Status ListDelete(LinkList &L,int i,ElemType &e) / 删除 LinkList p=L;LinkList q;int j=0;while(p-next&jnext;+j; if(!(p-next)|ji-1) return error; / 删除位置不合理 q=p-next;p-next=q-next; / 删除并释放结点e=q-data; delete(q); return ok;void MergeList(LinkList &La,LinkList &Lb,LinkList

18、&Lc) /合并两个顺序链表LinkList pa,pc,pb;pa=La-next;pb=Lb-next;Lc=pc=La;while(pa&pb) if(pa-datadata) pc-next=pa; pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next; pc-next=pa?pa:pb; delete(Lb);void show(LinkList L) / LinkList p;p=L-next;while(p) coutdata;p=p-next; coutnext;while(p) +i;p=p-next; return i;

19、显示表长void xiugai(LinkList L)/修改 int i,j=1;ElemType k;ElemType e,m;LinkList p=L-next;cout 请输入要修改的元素位置 (0ii;GetElem(L,i,e);cout 该位置的元素 :eendl; coutk; while(p&jnext;+j; m=p-data;p-data=k;cout 修改后的单链表显示如下 :endl;show(L);void hebing() / 合并两个单链表 int a,b;LinkList La,Lb,Lc;cout 请输入第一个有序链表的长度 :a;cout 请输入第一个有序链

20、表的元素共( a 个)： endl; CreateList(La,a);show(La);cout 请输入第二个有序链表的长度 :b;cout 请输入第二个有序链表的元素共( b 个)： endl; CreateList(Lb,b);show (Lb);MergeList(La,Lb,Lc);cout 合并后的有序链表如下： endl;show(Lc);void main() / 主函数 int select;int x;ElemType y;LinkList list;for(;) cout单链表的根本操作 endl;cout1.单链表的创立 endl;cout2.单链表的显示 endl;c

21、out3.单链表的长度 endl;cout4.取第 i 个位置的元素 endl;cout5.修改第 i 个位置的元素 endl;cout6.插入元素到单链表里 endl;cout7.删除单链表里的元素 endl;cout8.合并两个单链表 endl;cout9.退出系统 endl;coutselect;switch(select) case 1:cout 请输入单链表的长度 :x;cout 请输入 x 个元素 endl; CreateList(list,x);break;case 2: cout单链表显示如下 :endl;show(list);break;case 3: int s;cout单

22、链表的长度为 :Length(list,s)endl;break;case 4: coutx;while(xLength(list,s) cout 输入有误,请重新输入 endl; coutx; GetElem(list,x,y);cout 该位置的元素为 :yendl; break;case 5: xiugai(list); break;case 6: coutx; while(xLength(list,s) cout 输入有误,请重新输入 endl; coutx; couty;LinkInsert( list,x,y);cout 插入后单链表显示如下 :endl; show(list);b

23、reak;case 7: coutx;while(xLength(list,s) cout输入有误,请重新输入 endl;coutx; ListDelete(list,x,y);cout 要删除的元素值 :yendl;cout 删除后的单链表显示如下 :endl; show(list);break;case 8: hebing();break;case 9: exit(0);break;default : cout输入有误,请重新输入7-4谢 耳JI航岸衾的长庭 E:c+zuoye3Debug31exeEH E: c + +,izuaye,3Debugi3 exe*価序夷的根本换作M游矣曲利建

24、 的显不4 取第i个位置的元t 轧修改第i个位置用6 馱元P1序夷里 ? 删除顶序宗里的元青 盘合并两个life 久退出系统请选择；3顺序夷的檢便汩顺序表的根本操作i-M再裘的韧建2 顺序表的显示乳顺序耒的长度4 取第i个位置的元素 修改第i个位置的元素 筑帝入元素到顺序表里 霞删除顺序裘里的元素 氛合并两个顺序志 夕-退岀系统请选择：4.甌第士个位置的元素 修改第土个位置的元素 SA兀素到顺序美里 厂删除J顷序表里的元素 & 合井两个顺序表 退出系统请选择=1请輸石顷序表的长度： 请輸7J顷序表的元素成共3个2 7 4顺序表显示如下=2-7-4请选择所要取出元素的位置沁 礙入看误,请重亲H输

25、入 请选怪所要取出元素的位置沢 取出的元素为汐 E:c+ +z u oy e3Deb u g3 ,exe*就 *E:c+ + zu oye3Debug3. exe顺序裘的根本操作 顺序表的创立 2-质库耒的显不 3川页序表的长匡 4-取第丄个盘置的邓素 氣修改第i个位置的元素 插人元素到顺序裘里 厂刑除顺序表里的元素 氛合并两个顺序表 农退出系统请选择* 5谙选择所要修改元素的位置=6 端入看误,请董新输A.请选择所要修改元素的位置泊 耍修改成的元素汐 修改后的顺序克数据：N页序亲皑不如卞：2-7-2顺序耒的根本操作的创立2 -顷序表的显ZF3 -顺序表的长度仏取第土个位置的元素 修改第-个位

26、置的元素 氣插入元素80页序表里I请选择m 6请选择所裝插入元素的位置汚 端入有误,请重薪論入请选择所要插入元素的位置汨 要插入的元素油修改后的顺序恚数据,顺序轰显亦如下：2-7-4-241请选择：8请输入第一个有序表的长唐；3 陰输入第一个有序表的元素坦个4怜#后的有序表如下*顺序表显不如下;2-3-4- 5-5B! ECf+uoyeWebugM 1仁顺蒜的籬2砺表的缶； 对解耒的眾 4取鄴饨置的元素 丄修輝価的元毒I6尿入元諭质序矣里人删剽解表里的元素8 合并两个康 用岀系统青选辭要刪题訓伉置洛 執醮,情鈿欷 謎择碾删除穂的位副除歸吓：7-4-2E l- - L.oyT-.i? l ebu

27、giJ exe顺序表的创立2贡再衰的显7R的长唐4取第讣位管的元素5 修改第:个位置的元章 筑祐入元静顺序裘里 沢删除顶序表里的元素6 合并两个顺序美丫 退岀系统顺序表显7E如下:2-4-S佶输入第二个有序夷的长虧2 修输入第二个有序耒的元盍 5,E:c+Vuoye3Debug3.exe, jkey to continueC：Lii 择系 选出 1alfV /.i.tosai2顺序黜显示3 砺麹能 4趣筋饨訓元素 久修輝饨訓頑6 獻元詡顺軽里 硼緬歸里的元當8冷并齢I療 熠出系统3j E:c + -zuoye3Debug3.exe顺序表的皋本操作 i顺序裘的创立 氛顺序裘的显示 乳顺序表的长唐

28、 4取第i个位置的元雪 乩修改第丄个位置的元素 氣插入元看到顺序表里 八删除顺序耒里的元盍 誤合笄两个顺序夷 9-退出系统j|?i 23蜿入看误,请重新选怪顺序表的根本操作1 顺序夷的创立2 顺序耒的显不 乳顺序表的长唐4 取第i个位置的元老5 -修改第i个佢置的元素 誤插入元焉到顺序表里 人删除顺序謹的元素 誤合笄两个顺序表 匸退出系统请选搔| 2单链表的测试结果EB E： - .e 116-bi.g hQ33 *E：c+zuoyelDebug-,l exe匚单链表的创立 趴单链表的显示 趴单趙表的长唐 4趣第i个位置的元重 畀修改堇匚个位置的元重 6肩入牙畫到单链奏里 7 删除单链表里的元

29、素 R.合并两个单链表 卩退岀系统请选择；1青输入单链表的长虧请输入4个元素单链表的根本操佗1-单链耒的创立趴单链夷的显示养单链裘的长唐4 取第个位置的元素5 修改第i个位置的元素 插入元素到单链表里7 删除单链夷里的元寿 取合并两个单错表 号退出系统请选择汐 单链裏显示如下：13 4 6EB *E:c+zuoyelDebugl.gxg*sj E:c+ *zuoyelDebu：j .,1 exe*单链表的根本操低单链表的创立2 单链裘的显示3 单链表的舞4 取第i个位置的元素 修改第i个位置的元盍 捕入元章至U单链夷里 ?用除单链表更的元素$ 合井两个单链耒 勺退出系统请选择请选怪所要取出元素

30、的位置汚 始入Wi#f请重新始入 请选择所要取出元素的位置假 该位萱的元臺芥却单链表的根本操作1.单链耒的创立氛单链耒的显示m单链裘的长曆4 取第i个位置的元盍 氣修改第i个位置的元憲 插入元素到单链表里7 删除单链耒里的元素 氣合并两个单链裘号退出系统请选择活谙选怪萼插入的位置祥 端入看误,话重新输入 请选怪所要畅人元素的位置江 醪插入的元3?单链表的根本操作1-lgf的创立2 单餐耒的显示史单链耒的长匱4取第i个位置的元素 騷修改第i个位置的元奎6 插入元素到单链耒里7刪除单槌表里的元素 鉄合笄两个单链表9 退出系统请选择汩单链表的长席为沖% 尸 JL_tLJI lt_U单链表的根本操作仁

31、单链耒的创立囂单链耒的显示霊单链耒的长磨札取第i个位置的元素5 -修改第i个位置的元素插入元素至惮错表里 讥删除单链耒里的元素 取合并两个单链表 亠9-退出系统请选择汚_,请输斤夢修改的元素位置i :3 该位置的元素沁 修改后的元素值浦 修改后的单链耒显示如下：136 -6園 *E:c+VuoyelDebugl 八理链表的创立2 難謝显示 輝蘇的爍 仙第i个位置的元素5歸i个位置的元素6擂入冗詡|单链耒里 ?删除单链表里航素 的两个单链表 熠岀系统tew：?輸雨试请董新输入 青选辭艸除元訓位置汙 黒脈的元 副_醮前載奏歸如下：gg E+ + zudye 1Debug单错表的根本操作单链轰的创立

32、2 单链耒的显示氛单带夷的圧庭4 取第i个位置的元素5 修改第i个位置的元素6 插入元素刮单链裘里 ? 删除单樹克里的元素 氛食并两个单链表孕-遇出粢统 青输入第一个有序链表的长胱 醫输入第一个有序链裏的元素共3个；2 4 5弟一个有序链裘的元壽如下24S 信输入第二个有序链表的妖申4惰输入第二个有痒错耒的元素共4个：3 4 6 a第二个有序链耒的元素如下恰并后的有序链表如下;单镑表的根本操作单槌表的创立 茲单锤恚的显示 齐单链表的萇度4-碾第i个位置的元素 石摻改第i个莅豊苗元彖插入元素到单链表里7-WK单链表里加兀拳 睐合并两个单链表退出系统请选择=凰 E;c+tzuoyelDebugl.

33、exe单粽牆巒2 单鯛显示3单蘇般4邇第他I的元當5辭i个跡畫6境人元詡单癡里砒除難翹的元素 跆并两个单歸熠岀系统to：?Press any key to continue.can *Erc+ +VuoylDebugLexe请选七亠端入有误,谙重新输入单镑表的根本操作单链表的创立养单链裘的显示单链表的萇度4-取第丄个位置迫元素 5 修改第i个位置的元素 插入元素到单链表里7 -删除单链裘里的元素 合并两个单链表9-退出系统五、心得体会当听到老师说写数据结构实验报告时,我有点惊讶,才学了不到一个月, 就要写实验报告.记得去年学习 C+寸,学了一个学期,程序设计用了三周,才 完成的,这个实验报告居

34、然要一周完成两个设计, 觉得很难. 但是现在一周过去 了,我也写完了,自我感觉良好.通过这次写实验报告, 我深切的理解了这门课的本质. 刚开始学这门课时, 当时还不清楚这门课程的目的, 现在,我真正的理解了： 数据结构像是身体的骨 骼,而C+是填充这骨骼的肉体,二者相结合才能使整个程序更加完整,健全. 数据结构是个框架,模型,抽象数据类型中列举了各种操作,而所用的C+语言, 将各种操作描述出来构成算法.数据结构 +算法 =程序设计.在这次设计的过程中,我还遇到了,很多的问题.顺序表是按顺序存储的, 用了一维数组来存储,又结合 C+的程序设计,我又用了类,但是,在执行时出 现了问题.后来问同学,

35、指出我的错误,不过获益不少.我又重新整理思路,把 顺序表的根本操作写好了.虽然走了很多弯路,但是让我熟悉到,一定要创新, 大胆,不能根据旧的思路去干新的事情.单链表写起来简单多了,这个很快就搞定了.但是细节上出了问题.比方 说,有些变量的重复定义, 有些变量又没有定义, 在调用函数, 就直接复制过来, 没有改参数通过修改,我深刻理解到：细节决定成败,在以后,不管做任何 事情都要认真,细心.这次的实验报告,让我受益匪浅,不仅有知识方面的,还有生活和精神上 的.总之,我会继续我的兴趣编程,相信在编程的过程中,能不断的提升自己.raw E:c - +zuoye3Debu g3顺序表的根本操作 I质岸衾的剖建