1、 課 程 實 驗 報 告 專 業 年 級 2012級軟件工程 課 程 名 稱 數據結構C語言描述 指 導 教 師 申紅婷 學 生 姓 名 王曉霞 學 號 20122205041002 實 驗 日 期 2012.10.31 實 驗 地 點 A3篤行樓A棟306 實 驗 成 績 教務處制 2013年10月31日實驗項目名稱線性表實驗實驗目的及要求一目的： 1使學生對線性表的順序存儲結構、基本操作和應用，能通過實驗達到掌握和應用的目的。 2.使學生對線性表的線性表的鏈式結構、基本操作和應用，能通過實驗達到掌握和應用的目的。二要求： 實驗前認真預習實驗內容。實驗時自覺遵守課堂紀律，嚴格按操作規程操作，

2、既要獨立操作又要與其他同學配合，在實驗過程中必須按照實驗內容認真做完實驗，并認真填寫相關實驗報告。實驗內容線性表的順序存儲結構和線性表的鏈式結構、基本操和應用。實驗步驟1、閱讀下面程序，在橫線處填寫函數的基本功能。并運行程序，寫出結果。#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; /*順序表的當前長度*/int listsize; /*當前分配的存儲空間*/Sqlist;int InitList_sq(Sqlist *L); /* 初始化順序表，為其分配存儲空間 */int CreateList_sq(Sqlist *L,int n); /* 創建一個順序表 */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:"); /*輸入順序表的元素個數*/ 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 運行結果l 算法分析 首先應該選擇順序表的動態存儲方式進行順序表結構的定義，然后在程序的開頭進行順序表各種操作函數的聲明以及預定義命令，接著編寫各種操作函數的函數體，而在主函數中要首先調用InitList_sq(&sl)函數初始化，然后調用InitList_sq()創建順序表，調用PrintList_

12、sq()函數輸出該順序表中元素的值；然后調用ListInsert_sq()函數，進行插入操作，并輸出插入新元素后的狀態。2、為第1題補充刪除和查找功能函數，并在主函數中補充代碼驗證算法的正確性。刪除算法代碼：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 運行結果l

13、 算法分析 當在主函數里面調用刪除功能函數并傳參數進去時，程序將自動跳到函數體里面，利用所傳參數一步步執行，在該函數里面，當把順序表和序號i傳值進去時，程序可以先判斷所傳值是否滿足條件，若滿足，則開始從順序表第一個元素開始依次遍歷，直到找到第i個位置的元素，并將其刪除，后面的元素依次前移，填補。而表的長度則減一，刪除成功。若不滿足，則返回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 運行結果l 算法分析 當在主函數里面調用查找功能函數并傳參數進去時，程序將自動跳到函數體里面，利用所傳參數一步步執行，在該函數里面，當把順序表和要查找的值e傳值進去時，程序開始從順序表第一個元素開始依次遍歷，直到找到值為e的元素，并返回其位置序號，查找成功。若遍歷了順序表所有元素依然沒有符合條件的e的值，則返回0，表示查找失敗。3、閱讀下面程序，在橫線處填寫函數的基本功能。并運行程序，寫出結果。#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); /* 建立帶表頭節點的單鏈表 */void PrintList(LinkList L); /*輸出帶頭結點單鏈表的所有元素*/int GetElem(LinkList L,int i,ElemType *e); /* 在單鏈表中查找第i個節點的值 */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; /*結點指針域置空*/ p->next=q; /*新結點連在表末尾*/ 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:"); /*輸入單鏈表的元素個數*/ 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"); /*調用插入函數*/ printf("input i="); scanf("%d",&i); /*指定插入位置*/ printf("input e="); scanf("%d",&e); /*輸入欲插入元素的值*/ InsertList(L,i,e); PrintList(L); /*輸出調用后的結果*/ printf("n5-Delete from LinkLis

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

23、teList(int n)創建帶頭結點的單鏈表，輸入結點數，然后依次輸入各個結點的值。接著調用打印單鏈表功能函數輸出單鏈表中的值。再調用查找功能函數，輸入查找元素的位置，輸出對應元素的值。然后調用插入功能函數，輸入要插入的位置和元素，打印輸出插入后的新鏈表。同理調用刪除功能函數，輸入要刪除的元素值，最后打印輸出刪除后的單鏈表。 4、為第3題補充插入功能函數和刪除功能函數。并在主函數中補充代碼驗證算法的正確性。插入算法代碼：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 運行結果l 算法分析當在主函數里面調用查找功能函數并傳參數進去時，程序將自動跳到函數體里面，利用所傳參數一步步執行，在該函數里面，當把單鏈表，要插入的位置序號和元素內容傳值進去時，程序開始從單鏈表第一個元素開始依次遍歷，直到找到插入位置的前一個節點，用指針p指向它。然后創建一個以e為值的新節點指針q，修改節點*q的next域指向節點*p的下一個節點，再將節點*p的next域修改為指向新節點*s。返回ok，表示插入成功。最后打印輸出插入后的新鏈表。刪除算法代碼：int DeleteList(LinkList L,ElemType e) LNode *p,*q; p=L->nex