實驗一順序表與鏈表成品

1、實驗一 順序表與鏈表一、實驗目的1、掌握線性表中元素的前驅、后續(xù)的概念。2、掌握順序表與鏈表的建立、插入元素、刪除表中某元素的算法。3、對線性表相應算法的時間復雜度進行分析。4、理解順序表、鏈表數(shù)據(jù)結構的特點（優(yōu)缺點）。 二、實驗預習說明以下概念1、線性表：線性表是最常用且最簡單的一種數(shù)據(jù)結構。一個線性表是n個數(shù)據(jù)元素的有限序列。2、順序表：線性表的順序存儲結構或順序映像，通常，稱這種存儲結構的線性表為順序表。3、鏈表：指針域中存儲的信息稱作指針或鏈。N個接點連接成一個鏈表，故又稱線性鏈表。三、實驗內容和要求1、閱讀下面程序，在橫線處填寫函數(shù)的基本功能。并運行程序，寫出結果。l #includ

2、el #includel #define ERROR 0l #define OK 1l l #define INIT_SIZE 5 /*初始分配的順序表長度*/l #define INCREM 5 /*溢出時，順序表長度的增量*/l typedef int ElemType; /*定義表元素的類型*/l typedef struct Sqlistl ElemType *slist; /*存儲空間的基地址*/l int length; /*順序表的當前長度*/l int listsize; /*當前分配的存儲空間*/l Sqlist;l l int InitList_sq(Sqlist *L);

3、 /* 構造一個空的線性表L */l int CreateList_sq(Sqlist *L,int n); /* 不斷地插入元素 */l int ListInsert_sq(Sqlist *L,int i,ElemType e);/* 在L中第i個 位置之前插入一個數(shù)據(jù)元素e，L的長度加1 */l int PrintList_sq(Sqlist *L); /*輸出順序表的元素*/l int ListDelete_sq(Sqlist *L,int i); /*刪除第i個元素*/l int ListLocate(Sqlist *L,ElemType e); /*查找值為e的元素*/l l int

4、 InitList_sq(Sqlist *L)l L-slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType);l if(!L-slist) return ERROR; l L-length=0; l L-listsize=INIT_SIZE; l return OK; l /*InitList*/l l int CreateList_sq(Sqlist *L,int n)l ElemType e;l int i;l for(i=0;in;i+)l printf(input data %d,i+1);l scanf(%d,&e);l if(!List

5、Insert_sq(L,i+1,e)l return ERROR;l l return OK;l /*CreateList*/l l /*輸出順序表中的元素*/l int PrintList_sq(Sqlist *L)l int i;l for(i=1;ilength;i+)l printf(%5d,L-slisti-1);l return OK;l /*PrintList*/l l int ListInsert_sq(Sqlist *L,int i,ElemType e)l int k;l if(iL-length+1) l return ERROR; l if(L-length=L-lis

6、tsize) l L-slist=(ElemType*)realloc(L-slist,l (INIT_SIZE+INCREM)*sizeof(ElemType);l if(!L-slist) l return ERROR; l L-listsize+=INCREM; l l for(k=L-length-1;k=i-1;k-) l L-slistk+1= L-slistk;l l L-slisti-1=e; l L-length+; l return OK;l /*ListInsert*/l l /*在順序表中刪除第i個元素*/l int ListDelete_sq(Sqlist *L,in

7、t i)l int k;l if(iL-length) l return ERROR; l for(k=i-1;klength-1;k+)l l L-slistk=L-slistk+1;l l L-length-; l return 0;l /listDelete_l /*在順序表中查找指定值元素，返回其序號*/l /*int ListLocate(Sqlist *L,ElemType e)l l int n;l int i;l if(iL-length) l return ERROR; l for(n=0;nslistn-1;l l */lll int ListLocate(Sqlist *

8、L,ElemType e)l l int k;l for(k=0;klength-1;k+)l if(e=L-slistk)l l printf(此元素地址為：%dn,k+1);l return OK;l l if(k=L-length)l l printf(不存在!);l return ERROR;l ll l int main()l Sqlist sl;l int n,m,k;l printf(please input n:); /*輸入順序表的元素個數(shù)*/l scanf(%d,&n);l if(n0)l printf(n1-Create Sqlist:n);l InitList_sq(&

9、sl);l CreateList_sq(&sl,n);l printf(n2-Print Sqlist:n);l PrintList_sq(&sl);lll printf(nplease input locate location :(location)n);l scanf(%d,&m);l ListLocate(&sl,m);l l printf(n3-Print Sqlist:n);l PrintList_sq(&sl);llll printf(nplease input insert location and data:(location,data)n);l scanf(%d,%d,&m

10、,&k);l ListInsert_sq(&sl,m,k);l printf(n3-Print Sqlist:n);l PrintList_sq(&sl);l l printf(nplease input Delete location and data:(location)n);l scanf(%d,&m);l ListDelete_sq(&sl,m);l l printf(n3-Print Sqlist:n);l PrintList_sq(&sl);lll l /* printf(nplease input locate location :(location)n);l scanf(%d,

11、&m);l ListLocate(&sl,m);l l printf(n3-Print Sqlist:n);l PrintList_sq(&sl);l */lll l printf(n);l l l elsel printf(ERROR);l return 0;l 運行結果l 算法分析1；輸入線性表的元素個數(shù)，然后構建一個新的線性表，2；連續(xù)用creatlist函數(shù)往性表里插入元素，將其元素輸出，3；在下一步中輸入插入元素的位置和個數(shù)，最后一步，輸出運行后的線性表。2、為第1題補充刪除和查找功能函數(shù)，并在主函數(shù)中補充代碼驗證算法的正確性。刪除算法代碼：l int ListDelete_sq(S

12、qlist *L,int i)l int k;l if(iL-length) l return ERROR; l for(k=i-1;klength-1;k+)l l L-slistk=L-slistk+1;l l L-length-; l return 0;l /listDelete_l 運行結果查找算法代碼：int ListLocate(Sqlist *L,ElemType e) int k;for(k=0;klength-1;k+)if(e=L-slistk) printf(此元素地址為：%dn,k+1); return OK; if(k=L-length)printf(不存在!);re

13、turn ERROR;lll 運行結果l 算法分析l /*在順序表中查找指定值元素，返回其序號*/l int ListLocate(Sqlist *L,ElemType e)l l int k;l for(k=0;klength-1;k+)/*從第一個元素開始查找*/l if(e=L-slistk)l l printf(此元素地址為：%dn,k+1);l return OK;/*若存在與e相等的元素，則輸出其地址，返回OK*/l l if(k=L-length)l l printf(不存在!);l return ERROR;/*不存在*/l 3、閱讀下面程序，在橫線處填寫函數(shù)的基本功能。并運行

14、程序，寫出結果。l #inclull del #includel #define ERROR 0l #define OK 1l typedef int ElemType; /*定義表元素的類型*/l typedef struct LNode /*線性表的單鏈表存儲*/l ElemType data;l struct LNode *next;l LNode,*LinkList;ll LinkList CreateList(int n); /* 不斷的往鏈表中插入元素 */l void PrintList(LinkList L); /*輸出帶頭結點單鏈表的所有元素*/l int GetElem(L

15、inkList L,int i,ElemType *e); /* 當?shù)趇個元素存在時，其值賦給e */ l int ListInsert(LinkList L,int i,ElemType *e);l void ListDelete(LinkList L,int i);lll LinkList CreateList(int n)ll l LNode *p,*q,*head;l int i;l head=(LinkList)malloc(sizeof(LNode); head-next=NULL;l p=head;l for(i=0;idata); /*輸入元素值*/l q-next=NULL;

16、 /*結點指針域置空*/l p-next=q; /*新結點連在表末尾*/l p=q;l l return head;l /*CreateList*/ll void PrintList(LinkList L)l LNode *p;l p=L-next; /*p指向單鏈表的第1個元素*/l while(p!=NULL)l printf(%5d,p-data);l p=p-next;l l /*PrintList*/llll int ListInsert(LinkList L,int i,ElemType *e)l l LNode *p,*s;l int j;l p=L;j=0;ll while(p

17、&jnext;+j;l ll if(!p|ji-1)l return ERROR; l s=(LinkList)malloc(sizeof(LNode);l s-data=*e;l s-next=p-next;l p-next=s;l return e;ll /ListInsertlll void ListDelete(LinkList L,int i)l l LNode *p,*q;l int j;l p=L;j=0;l while(p-next&jnext;+j;l ll if(!(p-next)|ji-1)l return ERROR;l q=p-next;l p-next=q-next

18、;l free(q);lll /ListDeletelllll int GetElem(LinkList L,int i,ElemType *e)l LNode *p;int j=1;l p=L-next;l while(p&jnext;j+;l l if(!p|ji)l return ERROR; l *e=p-data; l return OK;l /*GetElem*/ll int main()l int n,i;ElemType e;l LinkList L=NULL; /*定義指向單鏈表的指針*/l printf(please input n:); /*輸入單鏈表的元素個數(shù)*/l scanf(%d,&n);l if(n0)l printf(n1-Create LinkList:n);l L=CreateList(n); l printf(n2-Print LinkList:n);l PrintList(L); l ll ll printf(n請輸入插入位置和數(shù)據(jù):(location,data)n);l scanf(%d,%d,&i,&e);l ListInsert(L,i,&e);l PrintList(L); ll printf(n請輸入刪除位置:n);l scanf(%d,&i);l ListDelete(L,i);l PrintL