實驗1 線性結(jié)構(gòu)

1、實驗項目名稱： 線性結(jié)構(gòu) 實驗學(xué)時： 8 同組學(xué)生姓名： 孫沛 實驗地點： 1314 實驗日期： 2018.10.18 2018.11.8 實驗成績： 批改教師： 批改時間： 實驗一 線性結(jié)構(gòu)一、實驗?zāi)康暮鸵?、實驗?zāi)康?1) 掌握順序表的定位、插入、刪除等操作。(2) 掌握單鏈表的定位、插入、刪除等操作。(3) 掌握應(yīng)用棧解決問題的方法；掌握利用棧進行表達式求解的算法；掌握隊列的存儲結(jié)構(gòu)及基本操作實現(xiàn)，并能在相應(yīng)的應(yīng)用問題中正確選用它們。(4) 掌握串的存儲及應(yīng)用。2、實驗要求(1) 注意鏈表的空間是動態(tài)分配的，某結(jié)點不用之后要及時進行物理刪除，以便釋放其內(nèi)存空間。(2) 鏈表不能實現(xiàn)直接

2、定位，一定注意指針的保存，防止丟失。二、實驗儀器和設(shè)備Visual C+ 6.0三、實驗內(nèi)容與過程（含程序清單及流程圖）（一）順序表1、必做題(1) 編寫程序建立一個順序表，并逐個輸出順序表中所有數(shù)據(jù)元素的值。編寫主函數(shù)測試結(jié)果。(2) 編寫順序表定位操作子函數(shù)，在順序表中查找是否存在數(shù)據(jù)元素x。如果存在，返回順序表中和x值相等的第1個數(shù)據(jù)元素的序號（序號從0開始編號）；如果不存在，返回1。編寫主函數(shù)測試結(jié)果。(3) 在遞增有序的順序表中插入一個新結(jié)點x，保持順序表的有序性。解題思路：首先查找插入的位置，再移位，最后進行插入操作；從第一個元素開始找到第一個大于該新結(jié)點值x的元素位置i即為插入位

3、置；然后將從表尾開始依次將元素后移一個位置直至元素i；最后將新結(jié)點x插入到i位置。(4) 刪除順序表中所有等于x的數(shù)據(jù)元素。2、選做題：已知兩個順序表A和B按元素值遞增有序排列，要求寫一算法實現(xiàn)將A和B歸并成一個按元素值遞減有序排列的順序表（允許表中含有值相同的元素）。（二）單鏈表1、必做題(1) 編寫程序建立一個單鏈表，并逐個輸出單鏈表中所有數(shù)據(jù)元素。(2) 在遞增有序的單鏈表中插入一個新結(jié)點x，保持單鏈表的有序性。解題思路：首先查找插入的位置然后進行插入操作；從第一個結(jié)點開始找到第一個大于該新結(jié)點值的結(jié)點即為插入位置；然后在找到的此結(jié)點之前插入新結(jié)點；注意保留插入位置之前結(jié)點的指針才能完成

4、插入操作。(3) 編寫實現(xiàn)帶頭結(jié)點單鏈表就地逆置的子函數(shù)，并編寫主函數(shù)測試結(jié)果。2、選做題：已知指針LA和LB分別指向兩個無頭結(jié)點單鏈表的首元結(jié)點。要求編一算法實現(xiàn)，從表LA中刪除自第i個元素起共len個元素后，將它們插入到表LB中第j個元素之前。（三）棧和隊列1、必做題(1) 判斷一個算術(shù)表達式中開括號和閉括號是否配對。(2) 測試“漢諾塔”問題。(3) 假設(shè)稱正讀和反讀都相同的字符序列為”回文”，試寫一個算法判別讀入的一個以為結(jié)束符的字符序列是否是“回文”。2、選做題：在順序存儲結(jié)構(gòu)上實現(xiàn)輸出受限的雙端循環(huán)隊列的入列和出列算法。設(shè)每個元素表示一個待處理的作業(yè)，元素值表示作業(yè)的預(yù)計時間。入隊

5、列采取簡化的短作業(yè)優(yōu)先原則，若一個新提交的作業(yè)的預(yù)計執(zhí)行時間小于隊頭和隊尾作業(yè)的平均時間，則插入在隊頭，否則插入在隊尾。（四）串1、必做題(1) 編寫輸出字符串s中值等于字符ch的第一個字符的函數(shù)，并用主函數(shù)測試結(jié)果。(2) 編寫輸出字符串s中值等于字符ch的所有字符的函數(shù)，并用主函數(shù)測試結(jié)果。解題思路：可以將第一題程序改進成一個子函數(shù)，在本題中循環(huán)調(diào)用。(3) 設(shè)字符串采用單字符的鏈?zhǔn)酱鎯Y(jié)構(gòu)，編程刪除串s從位置i開始長度為k的子串。2、選做題：假設(shè)以鏈結(jié)構(gòu)表示串，編寫算法實現(xiàn)將串S插入到串T中某個字符之后，若串T中不存在這個字符，則將串S聯(lián)接在串T的末尾。提示：為提高程序的通用性，插入位置

6、字符應(yīng)設(shè)計為從鍵盤輸入。程序清單：（一）順序表(1) 編寫程序建立一個順序表，并逐個輸出順序表中所有數(shù)據(jù)元素的值。編寫主函數(shù)測試結(jié)果。#includetypedef int datatype;#define maxsize 1024typedef structdatatype datamaxsize;int last;sequenlist;int main()sequenlist L;int i,n;printf(請輸入元素個數(shù)：);scanf(%d,&n);printf(n請輸入元素：);for(i=0;in;i+)scanf(%d,&L.datai);printf( 元素輸出：);for(

7、i=0;in;i+)printf(%dt,L.datai);printf(n);(2) 編寫順序表定位操作子函數(shù)，在順序表中查找是否存在數(shù)據(jù)元素x。如果存在，返回順序表中和x值相等的第1個數(shù)據(jù)元素的序號（序號從0開始編號）；如果不存在，返回1。編寫主函數(shù)測試結(jié)果。（2）#includetypedef int datatype;#define maxsize 1024typedef struct datatype datamaxsize;int last;sequenlist; int fun(sequenlist L,int x,int n) int i;for(i=0;in;i+)if(L.

8、datai=x)return i;return -1; int main() sequenlist L; int i,n,y; int x; printf(輸入元素個數(shù)：);scanf(%d,&n);for(i=0;in;i+)scanf(%d,&L.datai);printf(n 輸入查找元素：); scanf(%d,&x);y=fun(L,x,n);if(y=-1)printf(n數(shù)據(jù)元素%d位置為-1 n,x);elseprintf(n 數(shù)據(jù)元素%d位置為%dn,x,y); (3) 在遞增有序的順序表中插入一個新結(jié)點x，保持順序表的有序性。#include#define maxsize

9、100typedef struct int datamaxsize;int last;sequenlist; main() int i,x,j; sequenlist l=11,12,14,15,16,17,18,6; printf(原數(shù)據(jù)為: ); for(i=0;i=l.last;i+) printf(%2d,l.datai); printf(n插入元素為：); scanf(%d,&x); for(i=1;ix)break; if(il.last) l.datal.last+1=x; else for(j=l.last;j=i-1;j-) l.dataj+1=l.dataj; l.data

10、i-1=x; l.last+; printf(n插入后數(shù)據(jù)為：n); for(j=0;j=l.last;j+) printf(%3d,l.dataj); printf(n); return 0; (4) 刪除順序表中所有等于x的數(shù)據(jù)元素。#include#define maxsize 100typedef struct int datamaxsize;int last;sequenlist;main()int i,j,x=0,k=0;sequenlist L=1,3,5,7,2,4,6,8,2,9,9;printf(n原數(shù)據(jù):);for(i=0;i=L.last;i+)printf(%3d,L

11、.datai);printf(n刪除元素：);scanf(%d,&x);for(i=1;i=L.last+1;i+)if(L.datai-1=x)for(j=i;j=L.last+1;j+)L.dataj-1=L.dataj;L.last-;i-;k=1;if(k=1)printf(刪除后元素為：n);for(j=0;j=L.last;j+)printf(%3d,L.dataj);else printf(Not found!n);printf(n);（二）單鏈表1、必做題(1) 編寫程序建立一個單鏈表，并逐個輸出單鏈表中所有數(shù)據(jù)元素。#include#includetypedef int da

12、tattype;typedef struct nodechar data;struct node *next;linklist; main()char ch;linklist *head,*s,*r,*p;head=(linklist*)malloc(sizeof(linklist);r=head;scanf(%c,&ch);while(ch!=$)s=(linklist*)malloc(sizeof(linklist);s-data=ch;r-next=s;r=s;scanf(%c,&ch);r-next=NULL;r=head-next;while(r!=NULL)printf(%c,r-

13、data);r=r-next;(2) 在遞增有序的單鏈表中插入一個新結(jié)點x，保持單鏈表的有序性。#include#includetypedef int datattype;typedef struct nodeint data;struct node *next;linklist;main()int x,y;linklist *head ,*s,*r,*p,*q,*m,*n;head=(linklist*)malloc(sizeof(linklist);r=head;printf(輸入：);scanf(%d,&x);while(x!=0)s=(linklist*)malloc(sizeof(l

14、inklist);s-data=x;r-next=s;r=s;scanf(%d,&x); r-next=NULL;printf(插入：);scanf(%d,&y);p=head-next;while(p!=NULL)if(p-datanext;else break;q=(linklist*)malloc(sizeof(linklist);q-data=y;m=head;while(m-next!=p)m=m-next;q-next=p;m-next=q; n=head-next;printf(序列為：);while(n!=NULL)printf(%3d,n-data);n=n-next;(3)

15、 編寫實現(xiàn)帶頭結(jié)點單鏈表就地逆置的子函數(shù)，并編寫主函數(shù)測試結(jié)果。#include#includetypedef int datattype;typedef struct nodeint data;struct node *next;linklist;main()int a;linklist *head,*s,*r,*p,*q,*t;head=(linklist*)malloc(sizeof(linklist);r=head;printf(輸入：);scanf(%d,&a);while(a!=0)s=(linklist*)malloc(sizeof(linklist);s-data=a;r-ne

16、xt=s;r=s;scanf(%d,&a);r-next=NULL;printf(n序列為：n);p=head-next;while(p)printf(%d ,p-data);p=p-next;p=head-next;q=p-next;while(q!=NULL)t=q-next;q-next=p;p=q;q=t;head-next-next=NULL;head-next=p;printf(n轉(zhuǎn)換后：n);p=head-next;while(p!=NULL)printf(%d ,p-data);p=p-next;（三）棧和隊列(1) 判斷一個算術(shù)表達式中開括號和閉括號是否配對。#include

17、 #include typedef char datatype;#define maxsize 64typedef struct datatype datamaxsize; int top; seqstack;int match(char exp,int n)char stmaxsize; int top=-1,i=0,tag=1; while(i=0) tag=0; return tag;main()int tag,i; char exp7; for(i=0;i=6;i+) scanf(%c,&expi); tag=match(exp,7); if(tag) printf(算式表達式中的開括

18、號和閉括號配對。); else printf(算式表達式中的開括號和閉括號不配對！);getchar();getchar();(2) 測試“漢諾塔”問題。#include void move(char x,char z)printf(%c-,x); printf(%cn,z);void Hanoi(int n,char x, char y,char z) if(n=1) move(x,z); else Hanoi(n-1,x,z,y); move(x,z); Hanoi(n-1,y,x,z); main() int m; printf(請你輸入A上面的碟子總數(shù)：); scanf(%d,&m);

19、 Hanoi(m,A,B,C);(3) 假設(shè)稱正讀和反讀都相同的字符序列為”回文”，試寫一個算法判別讀入的一個以為結(jié)束符的字符序列是否是“回文”。#include #include #include typedef struct char data10; int top; seqstack;main()int i; char a9,b9; int m=0; seqstack *s; s=(seqstack*)malloc(sizeof(seqstack); s-top=-1; printf(請你輸入8位的字符串：n); for(i=0;itop+; s-datas-top=ai; i+; i=0; while(s-top=0) bi=s-datas-top; s-top-; i+; bi=; for(i=0;i=8;i+) if(ai!=bi) m=1; if(m=0) printf(你所輸入的字符串為回文！); else printf(你所輸入的字符串不是回文！);（四）串1、必做題(1) 編寫輸出字符串s中值等于字符ch的第一個字符的函數(shù)，并用主函數(shù)測試結(jié)果。#include #include int a(char a,char