數(shù)據(jù)結(jié)構(gòu)實驗最全順序表的操作及其應(yīng)用

1、 實驗1 順序表的操作及其應(yīng)用一、實驗?zāi)康?1）掌握線性表的順序存儲結(jié)構(gòu)；2）熟練掌握順序表基本算法的實現(xiàn)；3）掌握利用線性表數(shù)據(jù)結(jié)構(gòu)解決實際問題的方法和基本技巧；4）按照實驗題目要求獨立正確地完成實驗內(nèi)容二、實驗內(nèi)容要求：數(shù)據(jù)元素類型elemtype 取整型int 或者char。順序存儲實現(xiàn)如下算法：1）創(chuàng)建一順序表；2）輸出該順序表；3）在順序表中查找第i 個元素，并返回其值；4）在順序表中第i 個元素之前插入一已知元素；5）在順序表中刪除第i 個元素；6）實現(xiàn)順序表的合并。（選做） 源程序：/a sequential list順序表#include #include #include #

2、include #include #include #define initsize 100 /線性表存儲空間的初始分配量#define listincrement 10 /線性表存儲空間的分配增量typedef int elemtype;typedef struct elemtype *elem; int length; int listsize;sqlist;#define true 1#define false 0#define ok 1#define error 0#define infeasible -1#define overflow -2typedef int status;st

3、atus initlist(sqlist &l) /初始化 l.elem=(elemtype *)malloc(initsize*sizeof(elemtype); if(!l.elem) exit(overflow); l.length=0; l.listsize=initsize; return ok; /求表長int listlength(sqlist &l) return l.length;/輸入元素int datainput(sqlist &l) int i=1,j=1; printf(輸入數(shù)據(jù)后，按“0”結(jié)束輸入n); while(j) scanf(%d,&j); if(j!=0)

4、 l.elemi=j; l.length+; i+; if(iinitsize) break; return false;/輸出順序表status listtraverse(sqlist l) elemtype *p; int i; p=l.elem; for(i=0;il.length;i+) printf(%d ,*p+); printf(n); return ok;/查找元素status getelem(sqlist l,int i,elemtype &e) if(il.length) exit(error); e=l.elemi-1; return ok;/插入元素status lis

5、tinsert(sqlist &l,int i,elemtype e) elemtype *newbase,*q,*p; if(il.length+1) return error; if(l.length=l.listsize) newbase=(elemtype *) realloc(l.elem,(l.listsize+listincrement)*sizeof(elemtype); if(!newbase) exit(overflow); l.elem=newbase; l.listsize=l.listsize+listincrement; q=&(l.elemi-1); for(p=

6、&(l.eleml.length-1);p=q;-p) *(p+1)=*p; *q=e; +l.length; return ok;/刪除元素status listdeletsq(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;/主函數(shù)int main() sqlist l; elemtype e; char ch; i

7、nt t; while(1) system(cls); printf(t-menu-n); printf(t|1.創(chuàng)建一順序表 |n); printf(t|2.輸入數(shù)據(jù) |n); printf(t|3.輸出順序表 |n); printf(t|4.查找表中元素 |n); printf(t|5.于表中插入元素 |n); printf(t|6.刪除表中元素 |n); printf(t|7.退出 |n); printf(t|-n); fflush(stdin); ch=getchar(); if(ch=7) break; switch(ch) case 1: initlist(l); printf(初

8、始化順序表成功！n); printf(按任何鍵繼續(xù)操作n); getch(); break; case 2:datainput(l); printf(數(shù)據(jù)輸入成功！n); printf(按任何鍵繼續(xù)操作n); getch(); break; case 3:listtraverse(l); getch(); break; case 4:printf(你查找是第幾個元素：); fflush(stdin); scanf(%d,&t); getelem(l,t,e); printf(你查找的元素是：%dn,e); printf(按任何鍵繼續(xù)操作n); getch(); break; case 5:pr

9、intf(輸入你要插入的元素：); scanf(%d,&e); listinsert(l,t,e); printf(成功插入！n);printf(按任何鍵繼續(xù)操作n); getch(); break; case 6:printf(你想刪除第幾個數(shù)據(jù)：); scanf(%d,&t); listdeletsq(l,t,e); printf(成功刪除！n); printf(按任何鍵繼續(xù)操作n); getch(); break; default:break; return false;運行截圖： 主菜單：1. 創(chuàng)建順序表;2. 輸入數(shù)據(jù):3. 插入數(shù)據(jù)：三、實驗總結(jié)： 問題:1. 剛開始接觸數(shù)據(jù)結(jié)構(gòu)時

10、，完全不知道這門課程是學(xué)什么的，一臉茫然，通過反復(fù)看書，最后逐漸明白了其中的含義。2. 有些c語言的函數(shù)和c+語言函數(shù)不同。3. 函數(shù)和指針的知識還不夠好，不夠牢固。心得體會； 數(shù)據(jù)結(jié)構(gòu)是一門重要的課程，萬事開頭難，剛開始學(xué)的時候是很難的，需要自己反復(fù)地思考和閱覽書籍，才能解開一個個矛盾。c語言是很基礎(chǔ)的，數(shù)據(jù)結(jié)構(gòu)要想學(xué)好，c語言的最基本，特別是要學(xué)好里面的函數(shù)和指針知識，因為數(shù)據(jù)結(jié)構(gòu)里面很多都是用到指針和函數(shù)的。 實驗二 鏈表的操作及其應(yīng)用一、實驗?zāi)康牧私鈫捂湵淼幕靖拍?、結(jié)構(gòu)的定義及在單鏈表上的基本操作(插入、刪除、查找以及線性表合并)，通過在turbo c實現(xiàn)以上操作更好的了解書本上的內(nèi)

11、容并體會線性表的兩種存儲結(jié)構(gòu)的區(qū)別。二、實驗內(nèi)容 單鏈表的插入算法 單鏈表的刪除算法 循環(huán)鏈表的插入和刪除算法（選做）源程序：#include #include #include #include typedef int elemtype;#define true 1#define false 0#define ok 1#define error 0#define overflow -2typedef int status;typedef struct lnodeelemtype data;struct lnode *next;lnode,*linklist;status createlist

12、(linklist &l,int n)/ 創(chuàng)建鏈表 l=(linklist)malloc(sizeof(lnode);/生成帶頭結(jié)點的鏈表 linklist head,p; int i; if(!l) printf(創(chuàng)建失敗！); return false; l-next=null; head=l; for(i=0;idata);/輸入新結(jié)點值p-next=null;/尾插法，插入新結(jié)點head-next=p;head=p; return true;status getelem_l(linklist l,int i,elemtype &e) int j=1; linklist p; p=l-n

13、ext;/使p指向第一個結(jié)點 while(p&jnext; /后移 +j; if(!p|ji)/第i個元素不存在 printf(取元素失敗！); return error; e=p-data;/取第i個元素 return ok; status listinsert_l(linklist &l,int i,elemtype e)/在帶頭結(jié)點的單鏈表l中的第i個位置之前插入元素e linklist p,s;p=l; int j=0; while(p&jnext; +j; if(!p|ji-1) printf(插入失敗！); return error; s=(linklist)malloc(size

14、of(lnode);/生成新結(jié)點指向要插入的元素 s-data=e; s-next=p-next; p-next=s; return ok;status listdelete_l(linklist l,int i,elemtype &e)/在帶頭結(jié)點的單鏈表l中，刪除第i個元素，并由e返回其值 linklist p,q; int j=0; p=l; while(p-next&jnext; +j; if(!p|ji-1) printf(刪除元素失??！); return error; /刪除位置不合理 q=p-next; /刪除并釋放結(jié)點 p-next=q-next; e=q-data; free

15、(q); return ok;status outputlist(linklist l) linklist p;for(p=l-next;p!=null;p=p-next)printf(%4d,p-data);printf(n);return ok;main() char ch; int n,i; int e; linklist l; while(1) system(cls); printf(ttt-menu-n); printf(ttt|1.創(chuàng)建鏈表 |n); printf(ttt|2.輸出鏈表 |n); printf(ttt|3.插入元素 |n); printf(ttt|4.刪除元素 |n

16、); printf(ttt|5.退出 |n); printf(ttt|-|n); ch=getchar(); if(ch=5) break; switch(ch) case 1: printf(請輸入你要創(chuàng)建的結(jié)點數(shù)：); scanf(%d,&n);printf(每輸入一個值后按enter繼續(xù))n);createlist(l,n);printf(創(chuàng)建成功！n);break; case 2:printf(單鏈表的值是：); outputlist(l); getch(); break; case 3:printf(鏈表是：); outputlist(l); printf(請輸入你要在第幾個元素前插

17、入元素：); scanf(%d,&i); printf(請輸入你要插入的元素值：); scanf(%d,&e); listinsert_l(l,i,e); printf(插入成功！n); printf(新單鏈表是：); outputlist(l); getch(); break; case 4:printf(鏈表是：); outputlist(l); printf(你要刪除第幾個元素：); scanf(%d,&i); listdelete_l(l,i,e); printf(刪除成功！n); printf(新單鏈表是：); outputlist(l); getch(); break; defau

18、lt:break; getch(); return ok;運行截圖：主菜單： 1. 創(chuàng)建鏈表：2. 輸出鏈表：3. 插入元素：4. 刪除鏈表：三、實驗總結(jié)：問題：1. 創(chuàng)建鏈表時，運用前插法，使得最后輸出時是反過來輸出的；2. 在調(diào)用函數(shù)listinsert_l(l,i,e);時忘記寫輸入e的語句scanf(%d,&e); (就是要插入的元素)，使得在最后輸出了一個負數(shù)或者說是亂碼； 解決方法：1.通過看書和上網(wǎng)學(xué)到了尾插法，就是說尾插法的作用是使得最后輸出時的數(shù)值是按照輸入的順序輸出的；3. 第二個問題的解決方法是最后加上了scanf(%d,&e);這個語句，這樣才不會出現(xiàn)亂碼，輸出如我所愿

19、； 心得體會：通過對實驗一的學(xué)習(xí)后，我對數(shù)據(jù)結(jié)構(gòu)有了更深刻的認識，使得我在做實驗的過程中速度加快了很多，掌握了各種函數(shù)的應(yīng)用，能夠更深刻地了解單鏈表的操作及其應(yīng)用。 實驗三 棧的操作及其應(yīng)用一、實驗?zāi)康?了解棧的概念、棧的特性、在兩種存儲結(jié)構(gòu)上如何實現(xiàn)棧的基本操作以及棧在程序設(shè)計中的應(yīng)用。通過在turbo c中實現(xiàn)順序棧的插入和刪除加深理解順序棧的意義。二、實驗內(nèi)容 順序棧的進棧、出棧算法 鏈式棧的進棧、出棧算法（選做）源程序code：#include #include #include typedef int selemtype;#define chushi 100#define zengl

20、iang 10#define true 1#define false 0#define ok 1#define error 0#define overflow -2typedef int status;typedef struct selemtype *base;selemtype *top;int stacksize;sqstack;status initstack(sqstack &s) /初始化棧，構(gòu)造一個空棧； s.base=(selemtype *)malloc(chushi* sizeof(selemtype); if(!s.base) printf(存儲分配失敗n!); retu

21、rn false; s.top=s.base; s.stacksize=chushi; return true;status gettop(sqstack s,selemtype &e)/取棧頂元素if(s.top=s.base)printf(棧為空!n);return false;e=*(s.top-1);return true;status push(sqstack &s,selemtype e)/插入元素 進棧if(s.top-s.base=s.stacksize)/棧滿s.base=(selemtype *)realloc(s.base,(s.stacksize+zengliang)*

22、sizeof(selemtype);if(!s.base)printf(存儲分配失??！);return false;s.top=s.base+s.stacksize;s.stacksize+=zengliang; *s.top+=e;return true;status pop(sqstack &s,selemtype &e)/刪除元素 出棧 if(s.top=s.base) printf(棧為空！); return false; e=*-s.top; return true;stacklength(sqstack &s) /初始條件：棧s已存在 操作結(jié)果：返回s的元素個數(shù)，即棧的長度 ret

23、urn s.top-s.base; status output_stack(sqstack s) selemtype *p;int i;p=s.base;if(s.top=s.base) printf(棧不存在!n); return false;for(i=0;istacklength(s);i+) printf(%4d,*p+);printf(n);return true;status clearstack(sqstack s) s.top=s.base; /s.top = s.base作為順序棧空的標記 return ok; main() sqstack s;char ch;selemty

24、pe e;while(1) system(cls);printf(ttt-menue-n);printf(ttt|1.初始化順序棧 |n);printf(ttt|2.輸入棧的元素 |n);printf(ttt|3.輸出順序棧 |n);printf(ttt|4.進棧 |n);printf(ttt|5.出棧 |n);printf(ttt|6.清空順序棧 |n); printf(ttt|7.退出 |n);printf(ttt|-|n);ch=getchar();if(ch=7)break;switch(ch) case 1:initstack(s) ; printf(初始化成功!n);printf(

25、按任何鍵繼續(xù));getch();break; case 2:printf(順序棧是：);output_stack(s); printf(請逐個輸入數(shù)據(jù))n你要輸入的元素是：); scanf(%d,&e);push(s,e);printf(成功輸入數(shù)據(jù)!n);printf(順序棧是：);output_stack(s);printf(按任何鍵繼續(xù));getch();break; case 3:printf(順序棧的值是：); output_stack(s);printf(按任何鍵繼續(xù));getch();break; case 4:printf(順序棧的值是：); output_stack(s);

26、printf(進棧的元素：); scanf(%d,&e); push(s,e);printf(進棧成功!n); printf(順序棧的值是：); output_stack(s);printf(按任何鍵繼續(xù));getch();break; case 5:printf(順序棧的值是：); output_stack(s); pop(s,e);printf(出棧成功!n); printf(現(xiàn)在順序棧的值是：); output_stack(s);printf(按任何鍵繼續(xù));getch();break; case 6: clearstack(s); printf(清空完畢!n); printf(按任何鍵

27、繼續(xù)); break; return ok;運行截圖： 主菜單： 1 初始化順序表：2.進棧：3.出棧：三、實驗總結(jié)： 問題：（1）：在進棧和輸入的時，忘記了判斷棧是否為滿棧；在輸出和出棧時，忘記判斷棧是否為空。（2）：有時運用了太多的getch（）函數(shù)，使得程序運行的有點慢； 實驗心得： (1) ：掌握了棧這種抽象數(shù)據(jù)類型的特點，并能在相應(yīng)的應(yīng)用任務(wù)中正確選用它； 總的來說，棧是操作受限的線性表，是限定僅在表尾進行插入或刪除操作的線性表。因此，對棧來說，表尾端有其特殊含義，稱為棧頂（top），相應(yīng)地，表頭端稱為棧底（botton）； 棧又稱為后進先出（last in first out）的線

28、性表,簡稱lifo結(jié)構(gòu)，因為它的修改是按后進先出的原則進行的。 （2）： 加上這個實驗，我已經(jīng)學(xué)了線性表（順序表，單鏈表）和棧，知道它們都是線性表，而且對以后的學(xué)習(xí)有很大的作用，可以說這是學(xué)習(xí)以后知識的總要基礎(chǔ)； 實驗四 隊的操作及其應(yīng)用 一.實驗?zāi)康模?了解隊列的概念、隊列的特性、在兩種存儲結(jié)構(gòu)上如何實現(xiàn)隊列的基本操作以及隊列在程序設(shè)計中的應(yīng)用。通過在turbo c中實現(xiàn)隊列的插入和刪除加深理解鏈隊列和循環(huán)隊列的意義。二、實驗內(nèi)容： (1) 鏈隊列的進隊和出隊算法源程序code:#include #include #include #define true 1#define false 0#

29、define ok 1#define error 0#define overflow -2typedef int status;typedef int qelemtype;typedef struct qnode /結(jié)點類型 qelemtype data; struct qnode *next;qnode,*queueptr;typedef struct queueptr front;/隊頭指針 queueptr rear;/對尾指針linkqueue;status initqueue(linkqueue &q)/初始化鏈隊列 構(gòu)造一個空隊列 q.front=q.rear=(queueptr)

30、malloc(sizeof(qnode); if(!q.front) printf(存儲分配失敗!n); exit(overflow); q.front-next=null; return ok;status enqueue(linkqueue &q,qelemtype e)/在隊尾插入元素e qnode *p; p=(queueptr)malloc(sizeof(qnode); if(!p) printf(存儲分配失敗!n); exit(overflow); p-data=e; p-next=null; q.rear-next=p; q.rear=p; return ok;status de

31、queue(linkqueue q,qelemtype &e)/在隊頭刪除元素qnode *p; if(q.front=q.rear) printf(隊列為空!n); return error; p=q.front-next; e=p-data; q.front-next=p-next; if(q.rear=p) q.rear=q.front;/如果被刪的是最后一個元素，則為指針丟失，因此為為指針重新賦值（指向頭結(jié)點） free(p); return ok;status outputqueue(linkqueue q)/輸出元素qnode *p; if(q.front=q.rear) prin

32、tf(隊列為空!n); return error; for(p=q.front-next;p!=null;p=p-next) printf(%4d,p-data); printf(n); return ok;status destroyqueue(linkqueue &q)/銷毀隊列 while(q.front) q.rear=q.front-next; free(q.front); q.front=q.rear; return ok; int main()/注意 char ch; qelemtype e; linkqueue q; while(1) system(cls); printf(t

33、tt-menu-n); printf(ttt|1.創(chuàng)建鏈隊列 |n); printf(ttt|2.輸出鏈隊列 |n); printf(ttt|3.進隊（插入元素） |n); printf(ttt|4.出隊（刪除元素） |n); printf(ttt|5.銷毀隊列 |n); printf(ttt|6.退出 |n); printf(ttt|-|n); ch=getchar(); if(ch=6) break; switch(ch) case 1:initqueue(q); printf(創(chuàng)建成功!n); printf(請輸入隊列的初始數(shù)據(jù)（按0結(jié)束）：n); while(e) scanf(%d,&

34、e); if(!e)break; enqueue(q,e); printf(按任何鍵繼續(xù)n); getch(); break; case 2:printf(此時鏈隊列是：); outputqueue(q); printf(按任何鍵繼續(xù)n); getch(); break; case 3:printf(此時鏈隊列是：); outputqueue(q); printf(請輸入進隊的元素：); scanf(%d,&e); enqueue(q,e); printf(進隊成功!n); printf(此時鏈隊列是：); outputqueue(q); printf(按任何鍵繼續(xù)n); getch(); b

35、reak; case 4:printf(此時鏈隊列是：); outputqueue(q); dequeue(q,e); printf(出隊成功!n); printf(此時鏈隊列是:); outputqueue(q); printf(按任何鍵繼續(xù)n); getch(); break; case 5:destroyqueue(q); printf(銷毀成功!n); printf(按任何鍵繼續(xù)n); getch(); break; getch(); return ok;運行截圖： 主菜單： 1. 2.創(chuàng)建隊列3.輸出原始隊列4.進隊5.出隊6.銷毀隊列三、實驗總結(jié)：問題：1.在寫主函數(shù)面main（）

36、時，總是忘記寫（）； 2.聲明*p時，原來用的是queueptr，但最后改成qnode程序才正確；實驗心得： (1) 掌握了隊列這種抽象數(shù)據(jù)類型的特點，并能在相應(yīng)的應(yīng)用任務(wù)中正確選用它； 隊列是操作受限的線性表，是只允許僅在表的一端進行插入，而在另一端進行刪除操作的線性表。在隊列中，允許插入的一端稱為隊尾（rear），允許刪除的一端稱為對頭（front）； 隊列又稱為先進先出（first in first out）的線性表，簡稱fifo結(jié)構(gòu)。 因為它的修改是按先進先出的原則進行的。 (2) 掌握循環(huán)隊列和鏈隊列的基本操作實現(xiàn)算法，特別注意在循環(huán)隊列中隊滿和隊空的描述方法。 實驗五 串的操作及其

37、應(yīng)用一、實驗?zāi)康?）掌握隊列的基本定義； 2）掌握循環(huán)隊列基本操作的實現(xiàn)； 3）掌握利用棧和循環(huán)隊列進行回文字符串的判定。二、實驗內(nèi)容：問題描述：本題目中的串編輯要求對串實現(xiàn)以下三種功能：插入：把一個字符串插入到給定串的指定位置刪除：將串中某指定位置開始的若干字符從串中刪除置換：用一串字符置換給定串中某指定位置開始的若干字符基本要求輸入要求：首先輸入功能標志符，表明要求實現(xiàn)何種功能，然后再輸入有關(guān)數(shù)據(jù)輸入c, 表示要求根據(jù)用戶輸入的以回車為結(jié)束符的字符串建立順序串輸入i，表示要求輸入；然后輸入插入的起始位置和要插入的字符串輸入d，表示要求刪除；然后輸入刪除的起始位置和刪除長度輸入r，表示要求置

38、換 ；然后輸入置換的起始位置、置換長度和將要換入的字符串輸入e，結(jié)束串編輯。源程序code:#include #include #include #include /包含strlen(s) 返回s的長度，不包括結(jié)束符null,碰到第一個字符串結(jié)束符0停止掃面#define ok 1 #define error 0 #define overflow -1typedef struct char *ch; /若是非空串，則按串長分配儲存區(qū)，否則ch為null int length; /串長度hstring; /建立串 生成一個其值等于chars的串tint strassign(hstring &t,

39、char *chars) int len=strlen(chars); /求串chars的長度len if(t.ch) free(t.ch); /若t存在則釋放t原有的空間 if(!len) /串常量chars為空 printf(所輸入的字符串為空!n); t.ch=null; t.length=0; else if(!(t.ch=(char *)malloc(len+1)*sizeof(char) exit(0); strcpy(t.ch,chars); /調(diào)用系統(tǒng)原有函數(shù)復(fù)制字符串，給t賦值 t.length=len; return 0;/返回串s的長度 int strlength(hstring s)return s.length;/比較字符串/若st，則返回值0，若s=t，則返回值=0，若st，則返回值0int strcompare(hstring s,hstring t) int i;for(i=0;is.length&it.length;+i) if(s.chi!=t.chi) return s