數(shù)據(jù)結(jié)構(gòu)實驗線性表的順序存儲結(jié)構(gòu)

1、如有幫助，歡迎下載支持7南昌航空大學(xué)實驗報告課程名稱：數(shù)據(jù)結(jié)構(gòu)班 級：080611指導(dǎo)教師評定：XXX實驗名稱：實驗一線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)學(xué)生姓名：馮武明學(xué)號： 16簽 名：XXX題目：設(shè)計并實現(xiàn)以下算法：給出用單鏈表存儲多項式的結(jié)構(gòu)， 利用后接法生成 多項式的單鏈表結(jié)構(gòu)，實現(xiàn)兩個多項式相加的運算，并就地逆置相加后的 多項式鏈?zhǔn)?。一、需求分?. 先構(gòu)造兩個多項式鏈表，實現(xiàn)兩個多項式的和及刪除值為零元素的操作，不同用戶輸入 的多項式不同。2. 在演示過程序中，用戶需敲擊鍵盤輸入值，即可觀看結(jié)果。3. 程序執(zhí)行的命令包括：(1 )構(gòu)造多項式鏈表 A (2 )構(gòu)造多項式鏈表 B ( 3)求兩張鏈表

2、的和(4)刪除值為零元素，即不創(chuàng)建鏈表。二、概要設(shè)計1為實現(xiàn)上述算法，需要線性表的抽象數(shù)據(jù)類型：ADT Stack 數(shù)據(jù)對象：D=ai :|a i ElemSet,i=1 n,n 0 數(shù)據(jù)關(guān)系：R仁|a i-1 ,a i D,i=2,n 0 基本操作：in it(li nklist *L)操作結(jié)果：destroylist(List *L) clearlist(List *L)初始條件：線性表 L已經(jīng)存在，K i ListLength(&L)操作結(jié)果：用e返回L中第i個數(shù)據(jù)元素的值。in sfirst(l ink h, link s)初始條件：數(shù)據(jù)元素e1,e2存在操作結(jié)果：以e1,e2中的姓名

3、項作為判定e1,e2是否相等的依據(jù)。delfirst(link h,link *q)初始條件：數(shù)據(jù)元素e1,e2存在操作結(jié)果：以e1,e2中的姓名項(為字符串)的w來判定e1,e2是否有 w的關(guān)系。即 pe nd(li nklist *L,li nk s)初始條件：線性表 La 已經(jīng)存在 操作結(jié)果：判斷 La 中是否有與 e 相同的元素。remove(linklist *L,link *q) 初始條件：非遞減線性表La，Lb 已經(jīng)存在操作結(jié)果：合并 La，Lb 得到 Lc ，Lc 仍按非遞減有序排列。UnionList(List *La ,List *Lb)初始條件：線性表 La，Lb 已經(jīng)存

4、在操作結(jié)果：將所有在Lb而不在La中的元素插入到La中表尾的位置。PrintList(List L)初始條件：線性表 L 已經(jīng)存在操作結(jié)果：打印出表 L。ListInsert(List *L, int i, struct STU e)初始條件：線性表 L已經(jīng)存在，K i elem=(int*)malloc(listinitsize*sizeof(int);L-length=0;L-listsize=listinitsize; / 初始化表void add(sqlist *La,sqlist *Lb,sqlist *Lc)int *pa,*pb,*pc,*pa_last,*pb_last; pa

5、=La-elem; pb=Lb-elem;Lc-listsize=Lc-length=La-length+Lb-length; pc=Lc-elem=(int*)malloc(Lc-listsize)*sizeof(int);pa_last=La-elem+(La-length-1);pb_last=Lb-elem+(Lb-length-1); while(pa=pa_last&pb=pb_last)if(*pa_last*pb_last)*pc+=*pb_last-;else*pc=*pa_last; pc+; pa_last-; pb_last-;while(pa=pa_last)*pc=

6、*pa_last-;while(pb=pb_last)*pc=*pb_last-;/ 將兩個表合并成 Lc3. 主函數(shù)void main()void initlist(sqlist *L);void add(sqlist *La,sqlist *Lb,sqlist *Lc);sqlist *La,*Lb,*Lc;int i,p,num;initlist(La);initlist(Lb);initlist(Lc);printf(please input the numbers of you want about La:n); scanf(%d,&num);printf(n);for(i=0;ie

7、lemi=p;La-length+;printf(please input the numbers of you want about Lb:n); scanf(%d,&num);printf(n);for(i=0;ielemi=p;Lb-length+;printf(nnnnthe list of La:n); for(i=0;ilength;i+)printf(%6d,La-elemi);printf(nnnnthe list of La:n);for(i=0;ilength;i+)printf(%6d,Lb-elemi);prin tf(nnn);add(La,Lb,Lc);prin t

8、f(nnnthe list of Lc:n);for(i=0;ile ngth+Lb-le ngth;i+)prin tf(%6d,Lc-elemi);getch();4. 函數(shù)調(diào)用關(guān)系mai nIn itializati onMakeListOperateListReadComma ndprin tListi raddListTin i tlist1 !in itlist四、調(diào)試分析1. 調(diào)試程序時，因為沒有注意到指針變量與普通變量對成員的引用所用符號不同，將指針變量引用所用符號寫成導(dǎo)致程序出現(xiàn)大量錯誤，耽誤了大量的調(diào)試時間。警告shunxu1.c 18:可能在La定義以前使用了它在 mai

9、n函數(shù)中，將La放在main前即 可消除警告。注意定義各線性表變量為指針變量，這樣可以返回函數(shù)。2. 程序采用逐個輸入的方法創(chuàng)建La,Lb,在元素較多時，會使得程序很龐大，不利于檢查錯 誤等。3. 算法的時空分析各操作的算法時間復(fù)雜度比較合理In it ()為 0(1), void add() 為 O(m n)。4. 本次實驗采用數(shù)據(jù)抽象的程序設(shè)計方法，將程序化為三層次結(jié)構(gòu)，設(shè)計時思路清晰，使 調(diào)試也較順利，各模塊有較好的可重用性。五、用戶手冊1. 本程序的運行環(huán)境為 windows xp操作系統(tǒng)，執(zhí)行文件為 shunxubiao.c ;2. 進入演示程序后，按規(guī)定輸入數(shù)值后便可看到結(jié)果，按任

10、意鍵退出。六、測試結(jié)果1、鍵入數(shù)值CAin put 七 hf nunbe rs of you want ctbout La:3please input the nsobers of you. want about Lb：32、輸出結(jié)果the list: of6Gthelist9list13、鍵入任意字符，退出演示界面，回到編輯狀態(tài)。七、附錄：題一源程序如有幫助，歡迎下載支持#include#define listinitsize 20#define listincrement 10typedef structint *elem;int length;int listsize;sqlist;ma

11、in()void initlist(sqlist *L);void add(sqlist *La,sqlist *Lb,sqlist *Lc);sqlist *La,*Lb,*Lc;int i,p,num;initlist(La);initlist(Lb);initlist(Lc);printf(please input the numbers of you want about La:n); scanf(%d,&num);printf(n); for(i=0;ielemi=p; La-length+;printf(please input the numbers of you want ab

12、out Lb:n); scanf(%d,&num);printf(n); for(i=0;ielemi=p; Lb-length+;printf(nnnnthe list of La:n); for(i=0;ilength;i+) printf(%6d,La-elemi);printf(nnnnthe list of La:n); for(i=0;ilength;i+) printf(%6d,Lb-elemi);printf(nnn);add(La,Lb,Lc);printf(nnnthe list of Lc:n); for(i=0;ilength+Lb-length;i+) printf(%6d,Lc-elemi); getch();void add(sqlist *La,sqlist *Lb,sqlist *Lc)int *pa,*pb,*pc,*pa_last,*pb_last; pa=La-elem; pb=Lb-elem;Lc-listsize=Lc-length=La-length+Lb-length; pc=Lc-elem=(int*)malloc(Lc-listsize)*sizeof(int);pa_last=La-elem+(La-length-1); pb_last=Lb-elem+(Lb-length-1); while(pa=pa_last&pb