線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告樣例

1、 年南昌航空大學(xué)實(shí)驗(yàn)報(bào)告（用實(shí)驗(yàn)報(bào)告紙，手寫(xiě)）課程名稱(chēng)： 數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)名稱(chēng)： 實(shí)驗(yàn)一 線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu) 班 級(jí)： 080611 學(xué)生姓名： 賴(lài)凌 學(xué)號(hào)： 08061101 指導(dǎo)教師評(píng)定： 簽 名: 題目：有兩張非遞減有序的線(xiàn)性學(xué)生表A，B，采用順序存儲(chǔ)結(jié)構(gòu)，兩張表合并用c表存，要求C仍為非遞減有序的，并刪除C中值相同的表。一、需求分析 本演示程序根據(jù)已有的6位學(xué)生的信息，實(shí)現(xiàn)兩張表的合并及刪除值相同元素的操作，不需要用戶(hù)重新輸入學(xué)生的信息。 在演示過(guò)程序中，用戶(hù)敲擊鍵盤(pán)，即可觀(guān)看演示結(jié)果。 程序執(zhí)行的命令包括：（1）構(gòu)造線(xiàn)性表A （2）構(gòu)造線(xiàn)性表B （3）求兩張表的并 （4）刪除C中值相

2、同的元素二、概要設(shè)計(jì) 為實(shí)現(xiàn)上述算法，需要線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型：ADT Stack 數(shù)據(jù)對(duì)象：D=ai:|aiElemSet,i=1n,n0數(shù)據(jù)關(guān)系：R1=<ai-1,ai>|ai-1,aiD,i=2,n0基本操作:init(list *L)操作結(jié)果：構(gòu)造一個(gè)空的線(xiàn)性表L。ListLength(List *L)初始條件：線(xiàn)性表L已經(jīng)存在操作結(jié)果：返回L中數(shù)據(jù)元素的個(gè)數(shù)。 GetElem(List L, int i, ElemType *e)初始條件：線(xiàn)性表L已經(jīng)存在，1iListLength(&L)操作結(jié)果：用e返回L中第i個(gè)數(shù)據(jù)元素的值。EqualList(ElemTyp

3、e *e1,ElemType *e2)初始條件：數(shù)據(jù)元素e1,e2存在操作結(jié)果：以e1,e2中的姓名項(xiàng)作為判定e1,e2是否相等的依據(jù)。Less_EquaList(ElemType *e1,ElemType *e2)初始條件：數(shù)據(jù)元素e1,e2存在操作結(jié)果：以e1,e2中的姓名項(xiàng)(為字符串)的來(lái)判定e1,e2是否有的關(guān)系。LocateElem(List *La,ElemType e,int type)初始條件：線(xiàn)性表La已經(jīng)存在操作結(jié)果：判斷La中是否有與e相同的元素。MergeList(List *La,List *Lb,List *Lc)初始條件：非遞減線(xiàn)性表La，Lb已經(jīng)存在操作結(jié)果：合

4、并La，Lb得到Lc，Lc仍按非遞減有序排列。UnionList(List *La ,List *Lb)初始條件：線(xiàn)性表La，Lb已經(jīng)存在操作結(jié)果：將所有在Lb而不在La中的元素插入到La中表尾的位置。PrintList(List L)初始條件：線(xiàn)性表L已經(jīng)存在操作結(jié)果：打印出表L。ListInsert(List *L, int i, struct STU e)初始條件：線(xiàn)性表L已經(jīng)存在，1iListLength(&L)+1操作結(jié)果：在表L中第i個(gè)位置前插入元素e，L的長(zhǎng)度加1。 ADT List2. 本程序有三個(gè)模塊： 主程序模塊void main()初始化；接受命令；顯示結(jié)果； 線(xiàn)

5、性表單元模塊：實(shí)現(xiàn)線(xiàn)性表抽象數(shù)據(jù)類(lèi)型； 結(jié)點(diǎn)結(jié)構(gòu)單元模塊：定義線(xiàn)性表中的結(jié)點(diǎn)結(jié)構(gòu)。三、詳細(xì)設(shè)計(jì)元素類(lèi)型，結(jié)點(diǎn)類(lèi)型struct STUchar name20; /學(xué)生名字、學(xué)號(hào)、年齡、分?jǐn)?shù)char stuno10;int age;int score;typedef struct STU ElemType; /元素類(lèi)型struct LISTElemType *elem;int length; /表的長(zhǎng)度、大小int listsize;typedef struct LIST list; /結(jié)點(diǎn)類(lèi)型2.對(duì)抽象數(shù)據(jù)類(lèi)型中的部分基本操作的偽碼算法如下：int init(List *L)Lelem=(Ele

6、mType *)malloc(sizeof(ElemType)*LIST_INIT_SIZE);If(!Lelem) exit (OVERFLOW);Llength=0;Llistsize= LIST_INIT_SIZE;Return OK;/初始化表int ListLength(List *L)return Llength;/返回表長(zhǎng)void GetElem(List L, int i, ElemType *e)*e=L.elemi; /返回元素int locateElem(List *La, ElemType e, int type)int I;switch(type) /確定元素在表中的

7、位置case EQVAL;for(i=0;i<Lalength;i+)if(EqualList(&Laelemi,&e)return 1;break;default;break;return 0;void MergeList(List *La, List *Lb, List *Lc) /將兩個(gè)表合并成LcElemType *pa,*pb,*pc,*pa_last,*pb_last;Pa=Laelem;pb=Lbelem; LcListsize=Lclength=Lalength+Lblength;Pc=Lcelem=(ElemType *)malloc(Lclistsiz

8、e*sizeof(ElemType);if (!Lcelem) exit(OVERFLOW);pa_last=Laelem+Lalength-1;pb_last=Lbelem+Lblength-1;while (pa<=pa_last&&pb<=pb_last)if (Less_EqualList(pa,pb) *pc+=*pa+;else *pc+=*pb+;while (pa<=pa_last) *pc+=*pa+;while (pb<=pb_last) *pc+=*pb+;void UnionList(List *La, List *Lb)La_l

9、en=ListLength(La);Lb_len=ListLength(Lb);For(i=0;i<Lb_len;i+)GetElem(*Lb,i,&e);If (!LocateElem(La,e,EQUAL)ListInsert(La,+La_len,e);int ListInset(List *L,int i,struct STU e) /將元素插入表中if(i<1|i>Llength+1) return ERROR; q=&(Lelemi-1);for(p=LelemLlength-1;p>=q;p-)*(p+1)=*p;*q=e;+(Llengt

10、h);return OK;/ListInsert Before i3.主函數(shù)和其他函數(shù)的偽碼算法void main()Initialization();/初始化ReadCommand(cmd);/讀入一個(gè)操作符MakeList(La);printList(La);/產(chǎn)生并打印LaMakeList(Lb);printList(Lb);/ 產(chǎn)生并打印LbOperateList(La,Lb);void Initialization()/系統(tǒng)初始化clrscr();int ReadCommand(cmd)/任意鍵入一個(gè)字符cmd=getch();return 1;void MakeList(La)Li

11、stInsert(&La,i,e);void OperateList(La,Lb)MergeList(&La,&Lb,&Lc);UnionList(&La,&Lb);4 函數(shù)調(diào)用關(guān)系mainInitialization MakeList OperateList ReadCommand printList UnionList MergeListLess_EqualListInit ListInsert LocateElemEqualList四、調(diào)試分析 剛開(kāi)始輸入時(shí)，漏掉了一些變量參數(shù)的標(biāo)記"&"，有的則錯(cuò)加了"

12、;&"，使得程序運(yùn)行出來(lái)的結(jié)果不正確，使調(diào)試程序時(shí)費(fèi)時(shí)不少。 程序采用逐個(gè)輸入的方法創(chuàng)建La,Lb,在元素較多時(shí)，會(huì)使得程序很龐大，不利于檢查錯(cuò)誤等。 算法的時(shí)空分析各操作的算法時(shí)間復(fù)雜度比較合理init,ListLength,GetElem,EqualList,Less_EqualList為O(1)LocateElem,ListInsert,printList為O(n),UnionList為O(mn),MergeList為O(n)。4.本次實(shí)驗(yàn)采用數(shù)據(jù)抽象的程序設(shè)計(jì)方法，將程序化為三層次結(jié)構(gòu)，設(shè)計(jì)時(shí)思路清晰，使調(diào)試也較順利，各模塊有較好的可重用性。五、用戶(hù)手冊(cè) 本程序的運(yùn)行

13、環(huán)境為windows xp操作系統(tǒng)，執(zhí)行文件為Exp1Prb1.c； 進(jìn)入演示程序后，完成編譯，連接（即同時(shí)按下Ctrl F9）進(jìn)入演示界面，用戶(hù)鍵入任一符號(hào)，都能看完整個(gè)演示過(guò)程。六、測(cè)試結(jié)果(1)同時(shí)鍵入Ctrl F9，演示為：-List Demo is running-First is InsertList functionname stunoagescorestu1100001801000stu3100002801000(2)鍵入任意字符，演示為：name stunoagescorestu1100001801000stu3100002801000stu5100003801000List

14、 A length now is 3.(3)鍵入任意字符，演示為：name stunoagescorestu2100001801000stu4100002801000stu6100001801000List B length now is 3.(4)鍵入任意字符，演示為：name stunoagescorestu1100001801000stu2100001801000stu3100002801000stu4100002801000stu5100003801000stu6100001801000Second is UnionList function.Now union List A and

15、List B.name stunoagescorestu1100001801000stu2100002801000stu3100003801000stu4100001801000stu5100002801000stu6100001801000List A length now is 6.(5) 鍵入任意字符，退出演示界面，回到編輯狀態(tài)。七、附錄：題一源程序/-頭文件#include<stdio.h>#include<malloc.h>#include<conio.h>/符號(hào)常量#define ERROR O#define OK 1#define EQUAL

16、1#define OVERFLOW -1#define LIST_INIT_SIZE 100/線(xiàn)性表存儲(chǔ)空間的初始分配量#define LISTINCREMENT 10/線(xiàn)性表存儲(chǔ)空間的分配增量/類(lèi)型聲明struct STU/定義學(xué)生結(jié)構(gòu)體類(lèi)型，包括姓名，學(xué)號(hào)，年齡，成績(jī)char name20;char stuno10;int age;int score;stu50;typedef struct STU ElemType;/用ElemType代替學(xué)生struct LIST/定義表LIST為結(jié)構(gòu)體類(lèi)型ElemType *elem;/存儲(chǔ)空間基址int length;/當(dāng)前長(zhǎng)度int listsi

17、ze;/當(dāng)前分配的存儲(chǔ)容量;typedef struct LIST List;/用list代表結(jié)構(gòu)體LISTint init(List *L)/構(gòu)造一個(gè)空的線(xiàn)性表Lelem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType);If (!Lelem) exit(OVERFLOW);/ 存儲(chǔ)分配失敗Llength=0;/空表長(zhǎng)度為0Llistsize=LIST_INIT_SIZE;/初始存儲(chǔ)容量Return ok;int ListLength(List *L)/求表L的長(zhǎng)度return Llength;void GetElem(List L, in

18、t i, ElemType *e)*e=L.elemi;int EqualList(ElemType *e1,ElemType *e2)/以元素e1,e2中的姓名項(xiàng)是否相等作為判定e1,e2是否相等的標(biāo)準(zhǔn)if (strcmp(e1name,e2name)=0)return 1;elsereturn 0;int Less_EqualList(ElemType *e1,ElemType *e2)/以姓名（字符串）的作為判定e1e2的標(biāo)準(zhǔn)if (strcmp(e1name,e2name)<=0)return 1;elsereturn 0;int LocateElem(List *La,Elem

19、Type e,int type)/判斷La中是否有與e符合關(guān)系type的元素int i;suitch(type)case EQUAL;for(i=0;i<Lalength;i+)if (EqualList(&Laelemi,&e)return 1;break;default;break;return 0;void MergeList(List *La,List *Lb,List *Lc)/合并表La,Lb,用Lc存儲(chǔ)。已知La,Lb元素值按非遞減排列，Lc中值也按非遞減排列ElemType *pa,*pb,*pc,*pa_last,*pb_last;pa=Laelem;p

20、b=Lbelem;Lclistsize=Lclength=Lalength+Lblength;Pc=Lcelem=(ElemType *)malloc(Lclistsize*sizeof(ElemType);if (!Lcelem) exit(OVERFLOW);/存儲(chǔ)分配失敗pa_last=Laelem+Lalength-1;pb_last=Lbelem+Lblength-1;while(pa<=pa_last&&pb<=pb_last)/合并，Lc元素按非遞減排列if (Less_EqualList(pa,pb) *pc+=*pa+;else *pc+=*pb+

21、;while (pa<=pa_last) *pc+=*pa+ /插入La的剩余元素while (pb<=pb_last) *pc+=*pb+ /插入Lb的剩余元素void UnionList(List *La ,List *Lb)/將所有在Lb中而不在La中的元素插入到La中int La_len,Lb_len;int i;ElemType e;La_len=Listlength(La);Lb_len=Listlength(Lb);/求線(xiàn)性表長(zhǎng)度f(wàn)or(i=0;i<Lb_len;i+)GetElem(*Lb,I,&e);If (!LocateElem(La,e,EQUA

22、L)ListInsert(La,+La_len,e);int printlist(List L)/輸入表Lint i;printf("name stuno age scoren");for (i=0;i<L.length;i+)printf("%-cos%st%dt%dn",L.,L.elemi.stuno,L.elemi.age,L.elemi.score);printf("n");int ListInsert(List *L,int i,struct STU e)/在表L中第i位上插入estruct ST

23、U *p,*q;if (*i<1|i>Llength+1) return ERROR;/i值不合法q=&(Lelemi-1);for(p=&LelemLlength-1;p>=q;-p)*(p+1)=*p;*q=e;+Llength;return ok;mainstruct STU e;/定義結(jié)構(gòu)體變量eList La,Lb,Lc;/定義結(jié)構(gòu)體變量，即表La,Lb,LcClrscr();Printf("nn-List Demo is running -nn");Printf("First is InsertList functio

24、n.n");init(&La);/創(chuàng)建一個(gè)新表Lastrcp, "stu1");strcpy(e.stuno, "100001");e.age=80;e.score=1000;ListInsert(&La,1,e);/在La的第1位上插入stu1的數(shù)據(jù)元素strcp, "stu3");strcpy(e.stuno, "100002");e.age=80;e.score=1000;ListInsert(&La,2,e);/在La的第2位上插入stu3的數(shù)據(jù)元素Printlist(La);/輸出LaPrintf("List A length now is %d.nn",La.length);Getch();strcp, "stu5");strcpy(e.stuno, "100003");e.age=80;e.score=1000;ListInsert(&La,3,e);/在表La的第3位上插入stu5的數(shù)據(jù)表printlist(La);/輸出表Laprintf("List A length now is %d.nn",La.length);getch(