數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)1順序表鏈表

1、浪海工曇浣針篇機(jī)科修系實(shí)驗(yàn)報(bào)告書課程名：數(shù)據(jù)結(jié)構(gòu)線性表數(shù)據(jù)結(jié)構(gòu)試驗(yàn)題目：班級(jí)：軟件112學(xué)號(hào)：姓名：評(píng)語(yǔ):成績(jī)： 指導(dǎo)教師：批閱時(shí)間： 年 月線性表實(shí)驗(yàn)報(bào)告要求1目的與要求：1）掌握線性表數(shù)據(jù)結(jié)構(gòu)的基本概念和抽彖數(shù)據(jù)類型描述；2）熟練掌握線性表數(shù)據(jù)結(jié)構(gòu)的順序和鏈?zhǔn)酱鎯?chǔ)存表示；3）熟練掌握線性表順序存儲(chǔ)結(jié)構(gòu)的基本操作算法實(shí)現(xiàn)；4）熟練掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的基本操作算法實(shí)現(xiàn)；5）掌握線性表在實(shí)際問題中的應(yīng)用和基本編程技巧；6）按照實(shí)驗(yàn)題冃要求獨(dú)立正確地完成實(shí)驗(yàn)內(nèi)容（提交程序清單及相關(guān)實(shí)驗(yàn)數(shù)據(jù)與運(yùn)行結(jié) 果）；7）按照?qǐng)?bào)告格式和內(nèi)容要求，認(rèn)真書寫實(shí)驗(yàn)報(bào)告，并在試驗(yàn)后的第三天提交電子（全班同 學(xué)提交

2、到學(xué)委，再統(tǒng)一打包提交給老師）和紙質(zhì)（每班每次5份，學(xué)委安排，保證每個(gè)同學(xué)至 少提交一次）；8）積極開展實(shí)驗(yàn)組組內(nèi)交流和輔導(dǎo)，嚴(yán)禁復(fù)制和剽竊他人實(shí)驗(yàn)成果，一旦發(fā)現(xiàn)嚴(yán)肅處理;9）上實(shí)驗(yàn)課前，要求每個(gè)同學(xué)基本寫好程序，并存儲(chǔ)在自己的u盤上，用于實(shí)驗(yàn)課堂操 作時(shí)調(diào)試和運(yùn)行。凡不做準(zhǔn)備，沒有提前編寫程序者，拒絕上機(jī)試驗(yàn)。2實(shí)驗(yàn)內(nèi)容或題目一、順序表的基本操作實(shí)現(xiàn)實(shí)驗(yàn)要求：數(shù)據(jù)元素類型elemtype取整型ini。按照順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)如下算法：1）創(chuàng)建任意整數(shù)線性表（即線性表的元素值隨機(jī)在鍵盤上輸入）的順序存儲(chǔ)結(jié)構(gòu)（即順序表）,長(zhǎng)度限定在25之內(nèi)；2）打印/顯示（遍歷）該線性表（依次打印/顯示出表中元素值

3、）；3）在順序表中查找第i個(gè)元素，并返回其值；4）在順序表第i個(gè)元素之前插入一已知元素；5）在順序表中刪除第i個(gè)元素；6）求順序表屮所有元素值（整數(shù)）之和；二、鏈表帶頭結(jié)點(diǎn)基本操作實(shí)驗(yàn)要求：數(shù)據(jù)元素類型elemtype取字符型char。按照動(dòng)態(tài)單鏈表結(jié)構(gòu)實(shí)現(xiàn)如下算法：1）按照頭插法或尾插法創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的字符型單鏈表（鏈表的字符元素從鍵盤輸入），長(zhǎng)度限定在10之內(nèi)；2）打印（遍歷）該鏈表（依次打印出表中元素值，注意字符的輸入順序與鏈表的結(jié)點(diǎn)順序）；3）在鏈表中查找第i個(gè)元素，i合法返回元素值，否則，返回false；4）在鏈表屮查找與一已知字符相同的第一個(gè)結(jié)點(diǎn)，有則返回true,否則，返回fa

4、lse；5）在鏈表中第i個(gè)結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)；6）在線性表屮刪除第i個(gè)結(jié)點(diǎn)；7）計(jì)算鏈表的長(zhǎng)度。3實(shí)驗(yàn)步驟與源程序#inelude <iostream>#define ok 1#define error 0#define true 1#define false 0#define elemtype int#define maxstze 25 /*此處的宏定義常量表示線性表可能達(dá)到的最大長(zhǎng)度*/using namespace std;typedef struct!elemtype elemmaxstze;/*線性表占用的數(shù)組空間*/intlast;/*記錄線性表中最后一個(gè)元素在數(shù)組

5、elem中的位置(下標(biāo)值)，空表置為t*/seqlist;void outputseqlist(seqlist *l)cout<<"順序表如下："<endl;int i;for (i=0;i<=l->last;i+)cout<<l->elemi<<jn ;cout«e ndl;int getdate(seqlist *l)!int t;cout«zz請(qǐng)輸入要查找的元素的序數(shù)："cndl;cin»t;if( t<0) | (t>l->last)cout

6、1;/，輸入錯(cuò)誤! ”;return(error);else return(l->elemtl);int inslist(seqlist *l)int i, e;cout«請(qǐng)輸入要插入的元素插入位置及要插入的元素z/«endl;cin>>i>>e;int k;if(i<l) ii (i>l->last+2) /*首先判斷插入位置是否合法*/!printf (，z插入位置i值不合法")；return(error);if(l->last>= maxsize-1)printf (z，表己滿無(wú)法插入")

7、；return(error);for (k=l->last; k>=i-l; k-)/*為插入元素而移動(dòng)位置*/l->elemk+l=l->elemk;l->elemi-l=e;/*在c語(yǔ)言數(shù)組中，第i個(gè)元素的下標(biāo)為卜1*/l->last+;return(ok);int dellist(seqlist *l, elemtype *m)int w;cout«z/請(qǐng)輸出要?jiǎng)h除的元素位置：endl;cin>>w;int k;i f(w<1) |(w>l->last+l)icout«，z刪除位置不合法!/z«

8、;endl;return(error);二l->elemw-l;/*將刪除的元素存放到e所指向的變量屮*/for(k=w; k<=l->last; k+)l->elemk-l = i->elemk; /*將后面的元素依次前移*/l->last;return(ok);int sum(seqlist *l)int i, n=0;for(i=0;i<l->last+l;i+)n二n+l->elemi;return (n);void main()!int *q, n;seqlist *l;l=(seqli st*)malloc(sizeof(seq

9、li st);q = (int*)malloc(sizeof(int);cout«"請(qǐng)輸入順序表長(zhǎng)度：；cin»n;l->last=n-l;cout«，z請(qǐng)輸入順序表：;for (i=0;i<n;i+)cin»l->elemi;char c=，y"whlie(c!=，n')cout«z，請(qǐng)選擇你要進(jìn)行的操作："endl;cout«，l.輸出順序表；/z«，n «，z2.查找元素；插入元素；n«4.刪除元 素；"«'n

10、9;<<"5.求和"<<endl;int xuanze;cin>>xuanze;swi tch(xuan刁e)case 1:outputseqlist( l);break;case 2:cout«getdate( l)«cndl;break;case 3:inslist ( l);break;case 4:del li st(l, q);break;case 5:cout<<sum( l)<<endl;break;cout«，z是否要繼續(xù)進(jìn)行操作y/n：/z«endl;cin

11、>>c;#include<stdio.h>#include<malloc.h>#define max 15#define ture 1#define false 0typedef char elemtype;typedef struct nodechar date;struct node * next;node,*linklist;void initlist(linklist *l)* l=(linklist)mahoc(sizeof(char);(*l)->next=null;void printflink(linklist l)linklist p

12、;p=l->next;printf(n 鏈表為:”);while(p!二 null)printf("%c ",p->date);p=p->next;void create(linklist l)linklist s,r;char c;int flag= 1;int n;r=l;printf(”元素個(gè)數(shù):”)； scanf(m%d'&n);if(n>max)printfc超出限定長(zhǎng)度! ”);elseprint”輸入字符(以#鍵結(jié)束 while(flag)scanf(” c",&c);if(c !=*#*) s=(no

13、de*)malloc(sizeof(char); s->date=c;r->next=s;r=s;elseflag=o;r->next =null;void order(linklist l)char c;node *r,*q,*p;for(r=l->next;r->next!=null;r=r->next) p=gfor(q=r->next;q;q=q->next) if(q->date)<(p->date)p二q；if(p!=r)c=r->date;r->date=p->date; p->date=c

14、;)printflink(l);void get(linklist l, int i, elemtype *e)int j; node *p;p=l；j=-l；while (p->next! =null)&&(j<i)p=p->next;j+；*e=p->date ;if(i=j)printf(um%d 個(gè)元素為:%c",i,*e); elseprintf(ufalseu);)void locate(linklist l, elemtype e)int i=l;linklist p;p=l->next;while(p&&p

15、->date !=e)i=i+;p=p->next;if(!p)printf(nfalsenh);elseprintf(htruenh);printf（h該元素在第d個(gè)位置!”卜1）;void in$list(linklist l,int i,elemtype e)node *p,*s;int k=0;p 二 l;while(p!=null&&k<i-l)p=p->next;k=k+；if(!p)printf(u插入位置不合理! ”)；s=(node*)malloc(sizeof(char);s->date=e;s->next=p >n

16、ext;p->next=s;order(l);void dellist(linklist l,inl i,elemtype *e)node *p,*r;intj;j 二 0;p=l;while(p->next! =null)&&(j<i-l)p=p->next;j+；iif(p->next!=null)p->next=p->next->next;r=p->next;*e=r->date;printfc刪除第d 個(gè)元素:%cn”,i,*e);elseprintfc刪除結(jié)點(diǎn)的位置i不合理!“)；void listlengt

17、h(linklist l)node *p;int j=0; p=l->next; while(p!=null)p=p->next; j+;printf（h單鏈表的長(zhǎng)度:%dfj）;void menu()printf（nn1.創(chuàng)建任意字符型單循壞鏈表”）；printf（'rn2.打?。ū闅v）該鏈表”）；printf（hn3.查找第i個(gè)元素”）；printfc4查找與一已知字符相同的元素”）;printf（un5.插入元素”）；printf（hn6.刪除第i個(gè)結(jié)點(diǎn)”）；printf（hn7.計(jì)算鏈表的長(zhǎng)度”）；printf（"n&退出”）；void main(

18、)int i;int flag=0;elemtype e;linklist l;l=(linklist)malloc(sizeof(char);initlist(&l);menu();while(!flag)printfcnxn請(qǐng)輸入你的選擇(18):”); scanf(”d”,&i);switch(i)case 1:create(l);break;case 2:order(l);break;case 3:printfc*輸入要查找的第i個(gè)元素:”）; scanf（”d”,&i）;get(ui,&e); break;case 4:printf("輸入査找的元素:”); rewind(stdin);sca