課程實(shí)驗(yàn)報告1線性表

1、 課 程 實(shí) 驗(yàn) 報 告 專 業(yè) 年 級 2012級軟件工程 課 程 名 稱 數(shù)據(jù)結(jié)構(gòu)C語言描述 指 導(dǎo) 教 師 申紅婷 學(xué) 生 姓 名 王曉霞 學(xué) 號 20122205041002 實(shí) 驗(yàn) 日 期 2012.10.31 實(shí) 驗(yàn) 地 點(diǎn) A3篤行樓A棟306 實(shí) 驗(yàn) 成 績 教務(wù)處制 2013年10月31日實(shí)驗(yàn)項目名稱線性表實(shí)驗(yàn)實(shí)驗(yàn)?zāi)康募耙笠荒康模?1使學(xué)生對線性表的順序存儲結(jié)構(gòu)、基本操作和應(yīng)用，能通過實(shí)驗(yàn)達(dá)到掌握和應(yīng)用的目的。 2.使學(xué)生對線性表的線性表的鏈?zhǔn)浇Y(jié)構(gòu)、基本操作和應(yīng)用，能通過實(shí)驗(yàn)達(dá)到掌握和應(yīng)用的目的。二要求： 實(shí)驗(yàn)前認(rèn)真預(yù)習(xí)實(shí)驗(yàn)內(nèi)容。實(shí)驗(yàn)時自覺遵守課堂紀(jì)律，嚴(yán)格按操作規(guī)程操作，

2、既要獨(dú)立操作又要與其他同學(xué)配合，在實(shí)驗(yàn)過程中必須按照實(shí)驗(yàn)內(nèi)容認(rèn)真做完實(shí)驗(yàn)，并認(rèn)真填寫相關(guān)實(shí)驗(yàn)報告。實(shí)驗(yàn)內(nèi)容線性表的順序存儲結(jié)構(gòu)和線性表的鏈?zhǔn)浇Y(jié)構(gòu)、基本操和應(yīng)用。實(shí)驗(yàn)步驟1、閱讀下面程序，在橫線處填寫函數(shù)的基本功能。并運(yùn)行程序，寫出結(jié)果。#include<stdio.h>#include<malloc.h>#define ERROR 0#define OK 1#define INIT_SIZE 5 /*初始分配的順序表長度*/#define INCREM 5 /*溢出時，順序表長度的增量*/typedef int ElemType; /*定義表元素的類型*/typedef

3、 struct SqlistElemType *slist; /*存儲空間的基地址*/int length; /*順序表的當(dāng)前長度*/int listsize; /*當(dāng)前分配的存儲空間*/Sqlist;int InitList_sq(Sqlist *L); /* 初始化順序表，為其分配存儲空間 */int CreateList_sq(Sqlist *L,int n); /* 創(chuàng)建一個順序表 */int ListInsert_sq(Sqlist *L,int i,ElemType e);/* 將新元素e插入到順序表第i個位置 */int PrintList_sq(Sqlist *L); /*輸出

4、順序表的元素*/int ListDelete_sq(Sqlist *L,int i); /*刪除第i個元素*/int ListLocate(Sqlist *L,ElemType e); /*查找值為e的元素*/int InitList_sq(Sqlist *L) L->slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType); if(!L->slist) return ERROR; L->length=0; L->listsize=INIT_SIZE; return OK; /*InitList*/int CreateList

5、_sq(Sqlist *L,int n) ElemType e; int i; for(i=0;i<n;i+) printf("input data %d",i+1); scanf("%d",&e); if(!ListInsert_sq(L,i+1,e) return ERROR; return OK;/*CreateList*/*輸出順序表中的元素*/int PrintList_sq(Sqlist *L) int i; for(i=1;i<=L->length;i+) printf("%5d",L->

6、slisti-1); return OK;/*PrintList*/int ListInsert_sq(Sqlist *L,int i,ElemType e) int k;if(i<1|i>L->length+1) return ERROR; if(L->length>=L->listsize) L->slist=(ElemType*)realloc(L->slist,(INIT_SIZE+INCREM)*sizeof(ElemType); if(!L->slist) return ERROR; L->listsize+=INCREM

7、; for(k=L->length-1;k>=i-1;k-) L->slistk+1= L->slistk; L->slisti-1=e; L->length+; return OK;/*ListInsert*/*在順序表中刪除第i個元素*/int ListDelete_sq(Sqlist *L,int i)if (L->length=0) return 0;if(i<1|i>L->length) return 0;for(int j;j<L->length;j+) L->slistj-1=L->slistj;

8、 L->length-; return 1; /*在順序表中查找指定值元素，返回其序號*/int ListLocate(Sqlist *L,ElemType e) for(int i=1; i<=L->length;i+)if(L->slisti-1=e) return i;return 0;int main() Sqlist sl; int n,m,k; printf("please input n:"); /*輸入順序表的元素個數(shù)*/ scanf("%d",&n); if(n>0) printf("n1

9、-Create Sqlist:n"); InitList_sq(&sl); CreateList_sq(&sl,n); printf("n2-Print Sqlist:n"); PrintList_sq(&sl); printf("nplease input insert location and data:(location,data)n"); scanf("%d,%d",&m,&k); ListInsert_sq(&sl,m,k); printf("n3-Prin

10、t Sqlist:n"); PrintList_sq(&sl); printf("nplease input delete location: locationn"); scanf("%d",&m); ListDelete_sq(&sl,m); printf("n4-Print Sqlistn"); PrintList_sq(&sl); printf("nplease input data datan"); scanf("%d",&m); Lis

11、tLocate(&sl,m);printf("n5-Print Sqlistn"); PrintList_sq(&sl);printf("n"); else printf("ERROR"); return 0;l 運(yùn)行結(jié)果l 算法分析 首先應(yīng)該選擇順序表的動態(tài)存儲方式進(jìn)行順序表結(jié)構(gòu)的定義，然后在程序的開頭進(jìn)行順序表各種操作函數(shù)的聲明以及預(yù)定義命令，接著編寫各種操作函數(shù)的函數(shù)體，而在主函數(shù)中要首先調(diào)用InitList_sq(&sl)函數(shù)初始化，然后調(diào)用InitList_sq()創(chuàng)建順序表，調(diào)用PrintList_

12、sq()函數(shù)輸出該順序表中元素的值；然后調(diào)用ListInsert_sq()函數(shù)，進(jìn)行插入操作，并輸出插入新元素后的狀態(tài)。2、為第1題補(bǔ)充刪除和查找功能函數(shù)，并在主函數(shù)中補(bǔ)充代碼驗(yàn)證算法的正確性。刪除算法代碼：int ListDelete_sq(Sqlist *L,int i)if (L->length=0) return 0;if(i<1|i>L->length) return 0;for(int j=i;j<L->length;j+) L->slistj-1=L->slistj; L->length-; return 1; l 運(yùn)行結(jié)果l

13、 算法分析 當(dāng)在主函數(shù)里面調(diào)用刪除功能函數(shù)并傳參數(shù)進(jìn)去時，程序?qū)⒆詣犹胶瘮?shù)體里面，利用所傳參數(shù)一步步執(zhí)行，在該函數(shù)里面，當(dāng)把順序表和序號i傳值進(jìn)去時，程序可以先判斷所傳值是否滿足條件，若滿足，則開始從順序表第一個元素開始依次遍歷，直到找到第i個位置的元素，并將其刪除，后面的元素依次前移，填補(bǔ)。而表的長度則減一，刪除成功。若不滿足，則返回0，表示刪除失敗。查找算法代碼： int ListLocate(Sqlist *L,ElemType e) for(int i=1; i<=L->length;i+)if(L->slisti-1=e) return i; return 0;

14、l 運(yùn)行結(jié)果l 算法分析 當(dāng)在主函數(shù)里面調(diào)用查找功能函數(shù)并傳參數(shù)進(jìn)去時，程序?qū)⒆詣犹胶瘮?shù)體里面，利用所傳參數(shù)一步步執(zhí)行，在該函數(shù)里面，當(dāng)把順序表和要查找的值e傳值進(jìn)去時，程序開始從順序表第一個元素開始依次遍歷，直到找到值為e的元素，并返回其位置序號，查找成功。若遍歷了順序表所有元素依然沒有符合條件的e的值，則返回0，表示查找失敗。3、閱讀下面程序，在橫線處填寫函數(shù)的基本功能。并運(yùn)行程序，寫出結(jié)果。#include<stdio.h>#include<malloc.h>#define ERROR 0#define OK 1typedef int ElemType; /*定

15、義表元素的類型*/typedef struct LNode /*線性表的單鏈表存儲*/ ElemType data; struct LNode *next;LNode,*LinkList;LinkList CreateList(int n); /* 建立帶表頭節(jié)點(diǎn)的單鏈表 */void PrintList(LinkList L); /*輸出帶頭結(jié)點(diǎn)單鏈表的所有元素*/int GetElem(LinkList L,int i,ElemType *e); /* 在單鏈表中查找第i個節(jié)點(diǎn)的值 */LinkList CreateList(int n) LNode *p,*q,*head; int i;

16、 head=(LinkList)malloc(sizeof(LNode); head->next=NULL; p=head; for(i=0;i<n;i+) q=(LinkList)malloc(sizeof(LNode); printf("input data %i:",i+1); scanf("%d",&q->data); /*輸入元素值*/ q->next=NULL; /*結(jié)點(diǎn)指針域置空*/ p->next=q; /*新結(jié)點(diǎn)連在表末尾*/ p=q; return head;/*CreateList*/void

17、PrintList(LinkList L) LNode *p; p=L->next; /*p指向單鏈表的第1個元素*/ while(p!=NULL) printf("%5d",p->data); p=p->next; /*PrintList*/int GetElem(LinkList L,int i,ElemType *e) LNode *p;int j=1; p=L->next; while(p&&j<i) p=p->next;j+; if(!p|j>i) return ERROR; *e=p->data;

18、return OK;/*GetElem*/int InsertList(LinkList L,int i,ElemType e) int j=1; LNode *p,*q; p=L->next; while(p&&j<i-1) p=p->next;j+; if(!p) return ERROR; q=(LNode *)malloc(sizeof(LNode); q->data=e; q->next=p->next; p->next=q; return OK;int DeleteList(LinkList L,ElemType e) LN

19、ode *p,*q; p=L->next; while(p&&p->data!=e) q=p;p=p->next; if(!p) return ERROR; else q->next=p->next;free(p); return OK; int main() int n,i;ElemType e; LinkList L=NULL; /*定義指向單鏈表的指針*/ printf("please input n:"); /*輸入單鏈表的元素個數(shù)*/ scanf("%d",&n); if(n>0) p

20、rintf("n1-Create LinkList:n"); L=CreateList(n); printf("n2-Print LinkList:n"); PrintList(L); printf("n3-GetElem from LinkList:n"); printf("input i="); scanf("%d",&i); if(GetElem(L,i,&e) printf("No%i is %d",i,e); else printf("no

21、t exists");printf("n4-Insert from LinkList:n"); /*調(diào)用插入函數(shù)*/ printf("input i="); scanf("%d",&i); /*指定插入位置*/ printf("input e="); scanf("%d",&e); /*輸入欲插入元素的值*/ InsertList(L,i,e); PrintList(L); /*輸出調(diào)用后的結(jié)果*/ printf("n5-Delete from LinkLis

22、t:n");/*調(diào)用刪除函數(shù)*/ printf("input e="); scanf("%d",&e); /*輸入欲刪除元素的值*/ DeleteList(L,e); PrintList(L); /*輸出調(diào)用后的結(jié)果*/printf("n"); else printf("ERROR"); return 0;l 運(yùn)行結(jié)果l 算法分析 首先應(yīng)該進(jìn)行單鏈表結(jié)構(gòu)的定義，然后在程序的開頭進(jìn)行順序表各種操作函數(shù)的聲明以及預(yù)定義命令，接著編寫各種操作函數(shù)的函數(shù)體，而在主函數(shù)中要首先調(diào)用LinkList Crea

23、teList(int n)創(chuàng)建帶頭結(jié)點(diǎn)的單鏈表，輸入結(jié)點(diǎn)數(shù)，然后依次輸入各個結(jié)點(diǎn)的值。接著調(diào)用打印單鏈表功能函數(shù)輸出單鏈表中的值。再調(diào)用查找功能函數(shù)，輸入查找元素的位置，輸出對應(yīng)元素的值。然后調(diào)用插入功能函數(shù)，輸入要插入的位置和元素，打印輸出插入后的新鏈表。同理調(diào)用刪除功能函數(shù)，輸入要刪除的元素值，最后打印輸出刪除后的單鏈表。 4、為第3題補(bǔ)充插入功能函數(shù)和刪除功能函數(shù)。并在主函數(shù)中補(bǔ)充代碼驗(yàn)證算法的正確性。插入算法代碼：int InsertList(LinkList L,int i,ElemType e) int j=1; LNode *p,*q; p=L->next; while(p

24、&&j<i-1) p=p->next;j+; if(!p) return ERROR; q=(LNode *)malloc(sizeof(LNode); q->data=e; q->next=p->next; p->next=q; return OK;l 運(yùn)行結(jié)果l 算法分析當(dāng)在主函數(shù)里面調(diào)用查找功能函數(shù)并傳參數(shù)進(jìn)去時，程序?qū)⒆詣犹胶瘮?shù)體里面，利用所傳參數(shù)一步步執(zhí)行，在該函數(shù)里面，當(dāng)把單鏈表，要插入的位置序號和元素內(nèi)容傳值進(jìn)去時，程序開始從單鏈表第一個元素開始依次遍歷，直到找到插入位置的前一個節(jié)點(diǎn)，用指針p指向它。然后創(chuàng)建一個以e為值的新節(jié)點(diǎn)指針q，修改節(jié)點(diǎn)*q的next域指向節(jié)點(diǎn)*p的下一個節(jié)點(diǎn)，再將節(jié)點(diǎn)*p的next域修改為指向新節(jié)點(diǎn)*s。返回ok，表示插入成功。最后打印輸出插入后的新鏈表。刪除算法代碼：int DeleteList(LinkList L,ElemType e) LNode *p,*q; p=L->nex