線性表的順序存儲結構-實驗報告樣例

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 年南昌航空大學實驗報告（用實驗報告紙，手寫）課程名稱： 數(shù)據(jù)結構 實驗名稱： 實驗一 線性表的順序存儲結構 班 級： 學生姓名： 賴凌 學號： 指導教師評定： 簽 名: 題目：有兩張非遞減有序的線性學生表A，B，采用順序存儲結構，兩張表合并用c表存，要求C仍為非遞減有序的，并刪除C中值相同的表。一、需求分析 本演示程序根據(jù)已有的6位學生的信息，實現(xiàn)兩張表的合并及刪除值相同元素的操作，不需要用戶重新輸入學生的信息。 在演示過程序中，用戶敲擊鍵盤，即可觀看演示結果。 程序執(zhí)行的命令包括：（1）構造線性表A （2）構造線性表B （3）求兩張表的并 （4）刪除C中值相同的元

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

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

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

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

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

7、ase 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) /將兩個表合并成LcElemType *pa,*pb,*pc,*pa_last,*pb_last;Pa=Laelem;pb=Lbelem; LcListsize=Lclength=Lalength+Lblength;Pc=Lcelem=(ElemType *)malloc(Lclistsize*s

8、izeof(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_len=

9、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;+(Llength);

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

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

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

13、windows xp操作系統(tǒng)，執(zhí)行文件為Exp1Prb1.c； 進入演示程序后，完成編譯，連接（即同時按下Ctrl F9）進入演示界面，用戶鍵入任一符號，都能看完整個演示過程。六、測試結果(1)同時鍵入Ctrl F9，演示為：-List Demo is running-First is InsertList functionname stunoagescorestu1801000stu3801000(2)鍵入任意字符，演示為：name stunoagescorestu1801000stu3801000stu5801000List A length now is 3.(3)鍵入任意字符，演示為：

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

15、st A length now is 6.(5) 鍵入任意字符，退出演示界面，回到編輯狀態(tài)。七、附錄：題一源程序/-頭文件#include<stdio.h>#include<malloc.h>#include<conio.h>/符號常量#define ERROR O#define OK 1#define EQUAL 1#define OVERFLOW -1#define LIST_INIT_SIZE 100/線性表存儲空間的初始分配量#define LISTINCREMENT 10/線性表存儲空間的分配增量/類型聲明struct STU/定義學生結構體類型，

16、包括姓名，學號，年齡，成績char name20;char stuno10;int age;int score;stu50;typedef struct STU ElemType;/用ElemType代替學生struct LIST/定義表LIST為結構體類型ElemType *elem;/存儲空間基址int length;/當前長度int listsize;/當前分配的存儲容量;typedef struct LIST List;/用list代表結構體LISTint init(List *L)/構造一個空的線性表Lelem=(ElemType *)malloc(LIST_INIT_SIZE*si

17、zeof(ElemType);If (!Lelem) exit(OVERFLOW);/ 存儲分配失敗Llength=0;/空表長度為0Llistsize=LIST_INIT_SIZE;/初始存儲容量Return ok;int ListLength(List *L)/求表L的長度return Llength;void GetElem(List L, int i, ElemType *e)*e=L.elemi;int EqualList(ElemType *e1,ElemType *e2)/以元素e1,e2中的姓名項是否相等作為判定e1,e2是否相等的標準if (strcmp(e1name,e2n

18、ame)=0)return 1;elsereturn 0;int Less_EqualList(ElemType *e1,ElemType *e2)/以姓名（字符串）的作為判定e1e2的標準if (strcmp(e1name,e2name)<=0)return 1;elsereturn 0;int LocateElem(List *La,ElemType e,int type)/判斷La中是否有與e符合關系type的元素int i;suitch(type)case EQUAL;for(i=0;i<Lalength;i+)if (EqualList(&Laelemi,&

19、;e)return 1;break;default;break;return 0;void MergeList(List *La,List *Lb,List *Lc)/合并表La,Lb,用Lc存儲。已知La,Lb元素值按非遞減排列，Lc中值也按非遞減排列ElemType *pa,*pb,*pc,*pa_last,*pb_last;pa=Laelem;pb=Lbelem;Lclistsize=Lclength=Lalength+Lblength;Pc=Lcelem=(ElemType *)malloc(Lclistsize*sizeof(ElemType);if (!Lcelem) exit(O

20、VERFLOW);/存儲分配失敗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+;while (pa<=pa_last) *pc+=*pa+ /插入La的剩余元素while (pb<=pb_last) *pc+=*pb+ /插入Lb的剩余元素void UnionList(List *La ,List *Lb)/將

21、所有在Lb中而不在La中的元素插入到La中int La_len,Lb_len;int i;ElemType e;La_len=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 printlist(List L)/輸入表Lint i;printf("name stuno age scoren");for (i=0;i<L.length

22、;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 STU *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=

23、e;+Llength;return ok;mainstruct STU e;/定義結構體變量eList La,Lb,Lc;/定義結構體變量，即表La,Lb,LcClrscr();Printf("nn-List Demo is running -nn");Printf("First is InsertList function.n");init(&La);/創(chuàng)建一個新表Lastrcpy(, "stu1");strcpy(e.stuno, "");e.age=80;e.score=1000;List

24、Insert(&La,1,e);/在La的第1位上插入stu1的數(shù)據(jù)元素strcpy(, "stu3");strcpy(e.stuno, "");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();strcpy(, "stu5");strcpy(e.stuno, "");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();init(&am