1、淮海工學(xué)院計(jì)算機(jī)科學(xué)系實(shí)驗(yàn)報(bào)告書(shū)課程名：數(shù)據(jù)結(jié)構(gòu)題目：線性表數(shù)據(jù)結(jié)構(gòu)試驗(yàn)班級(jí)：學(xué)號(hào)：姓名：評(píng)語(yǔ)：成績(jī)：指導(dǎo)教師：批閱時(shí)間：年月日數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告- 1 -線性表實(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í)際問(wèn)題中的應(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ū)寫(xiě)實(shí)驗(yàn)報(bào)告，并在試驗(yàn)后的第

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

3、（遍歷）該線性表（依次打印/ 顯示出表中元素值） ；3）在順序表中查找第i 個(gè)元素，并返回其值；4）在順序表第i 個(gè)元素之前插入一已知元素；5）在順序表中刪除第i 個(gè)元素；6）求順序表中所有元素值（整數(shù)）之和；數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告- 2 -二、鏈表（帶頭結(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)的字符型單鏈表（鏈表的字符元素從鍵盤(pán)輸入），長(zhǎng)度限定在 10 之內(nèi)；2）打印（遍歷）該鏈表（依次打印出表中元素值，注意字符的輸入順序與鏈表的結(jié)點(diǎn)順序）；3）在鏈表中查找第i 個(gè)元素， i 合法返回元素值，否則

4、，返回FALSE；4）在鏈表中查找與一已知字符相同的第一個(gè)結(jié)點(diǎn)，有則返回TRUE，否則，返回FALSE；5）在鏈表中第i 個(gè)結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)；6）在線性表中刪除第i 個(gè)結(jié)點(diǎn)； 7）計(jì)算鏈表的長(zhǎng)度。3 實(shí)驗(yàn)步驟與源程序一、 順序表的基本操作實(shí)現(xiàn)實(shí)驗(yàn)Common.h#include #include #include #define OK1#define ERROR0#define TRUE 1#define FALSE 0Seqlist.h#define ElemType int#define MAXSIZE25typedefstructElemTypeelemMAXSIZE;intlas

5、t;SeqList;#include common.h#include seqlist.hintLocate(SeqList L, int n)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告- 3 -int i=0;while (iL.last&i!=n)i+;if(i=L.last)return L.elemi;elsereturn(-1);intInsList(SeqList *L,int i,ElemType e)int k;if(iL-last+2)printf( 插入位置i 值不合法 );return(ERROR);if(L-last= MAXSIZE-1)printf( 表已滿無(wú)法插入);return(ERRO

6、R);for(k=L-last;k=i-1;k-)L-elemk+1=L-elemk;L-elemi-1=e;L-last+;return(OK);intDelList(SeqList *L,int i,ElemType *e)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告- 4 -int k;if(iL-last+1)printf( 刪除位置不合法!);return(ERROR);*e = L-elemi-1;for(k=i; klast; k+)L-elemk-1 = L-elemk;L-last-;return(OK);intAddList(SeqList *L)int k,s=0;for(k=0;klast;k+)

7、s=s+L-elemk;return s;void main()SeqList l;int p,q,r,*q1;int i;q1=(int*)malloc(sizeof(int);printf( 請(qǐng)輸入線性表的長(zhǎng)度:);scanf(%d,&r);數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告- 5 -l.last = r-1;printf( 請(qǐng)輸入線性表的各元素值:n);for(i=0; i=l.last; i+)scanf(%d,&l.elemi);printf( 請(qǐng)輸入要查找的元素的位置:n);scanf(%d,&q);p=Locate(l,q);if(p = -1)printf( 在此線性表中沒(méi)有這樣的元素!n);e

8、lseprintf( 該位置的元素為:%dn,p);printf( 請(qǐng)輸入要插入的位置:n);scanf(%d,&p);printf( 請(qǐng)輸入要插入的元素值:n);scanf(%d,&q);InsList(&l,p,q);for(i=0; i=l.last; i+)printf(%d,l.elemi);printf(n);printf( 請(qǐng)輸入要?jiǎng)h除的元素位置:n);scanf(%d,&p);DelList(&l,p,&q);printf( 刪除的元素值為:%dn,q);printf( 刪除后的元素序列:n);for(i=0; i=l.last; i+)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告- 6 -printf(

9、%d,l.elemi);printf(n);printf( 剩余數(shù)字之和為：);printf( n %dn,AddList(&l);二、鏈表（帶頭結(jié)點(diǎn)）基本操作實(shí)驗(yàn)Common.h#include #include #include #define OK1#define ERROR0#define TRUE 1#define FALSELinklist.htypedef char ElemType;typedef struct NodeElemType data;struct Node* next;Node, *LinkList;#include #include #define ElemTy

10、pe chartypedef struct Node數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告- 7 -ElemType data;struct Node* next;Node, *LinkList;LinkListCreateFromHead()LinkListL;Node*s;charc;intflag=1,i=1;L=(LinkList)malloc(sizeof(Node);L-next=NULL;while(flag&idata=c;s-next=L-next;L-next=s;elseflag=0;i+;return L;數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告- 8 -Node *search(LinkList L,int i)

11、int j=0;Node *p;p=L;while(p-next!=NULL&jnext;j+;if(i=j) return p;else return NULL;Node *locate(LinkList L,ElemType key)Node *p;p=L-next;while(p!=NULL)if(p-data!=key)p=p-next;else break;return p;void InsList(LinkList L,int i,ElemType e)Node *p,*s;數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告- 9 -int k;p=L;k=0;while(p!=NULL&knext;k=k+1;i

12、f(k!=i-1)printf(error!);s=(Node *)malloc(sizeof(Node);s-data=e;s-next=p-next;p-next=s;void delLink(LinkList L,int i,ElemType *e)Node *p,*r;int k;p=L;k=0;while(p-next!=NULL&knext;k=k+1;數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告- 10 -if(k!=i-1)printf( 位置不合理 );r=p-next;p-next=p-next-next;*e=r-data;free(r);int Listlength(LinkList L)Node

13、 *p;p=L-next;int j=0;while(p!=NULL)p=p-next;j+;return j;void main()LinkList l;Node *p;char e;數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)報(bào)告-11-char a;int i,n;printf( 用頭插法建立單鏈表,請(qǐng)輸入鏈表數(shù)據(jù) , 以 $結(jié)束 !n);l = CreateFromHead();p = l-next;printf( 輸入的字符依次為:);while(p!=NULL)printf(%c,p-data);p=p-next;printf(%cn);Node *p1;printf( 請(qǐng)輸入要查找的字符的序號(hào):);scanf

14、(%d,&n);printf( 要查找的字符:n);p1=search(l,n);printf(%c,p1-data);printf(%cn);printf( 插入后的字符:n);scanf(%c,&a);InsList(l,3,a);p1=l-next;while(p1!=NULL)printf(%c,p1-data);p1=p1-next;數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告- 12 -printf(%cn);delLink(l,2,&e);p1=l-next;printf( 刪除后的字符為:n);while(p1!=NULL)printf(%c,p1-data);p1=p1-next;printf(%cn);printf( 該字符串的長(zhǎng)度為:n);i=Listlength(l);printf(%dn,i);printf( 輸入要查找的字符:n);scanf(%c,&a);p1=locate(l,a);if(p1!=NULL)printf(true);printf(%cn);elseprintf(flase!);printf(%cn);數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告- 13 -4 測(cè)試數(shù)據(jù)與實(shí)驗(yàn)結(jié)果（可以抓圖粘貼）一 順序表的基本操作實(shí)現(xiàn)實(shí)驗(yàn)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告- 14 -二、鏈表（帶頭結(jié)點(diǎn)）基本操作實(shí)驗(yàn)