實(shí)驗(yàn)一順序表與鏈表 成品

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

2、e<stdio.h>l #include<malloc.h>l #define ERROR 0l #define OK 1l l #define INIT_SIZE 5 /*初始分配的順序表長(zhǎng)度*/l #define INCREM 5 /*溢出時(shí)，順序表長(zhǎng)度的增量*/l typedef int ElemType; /*定義表元素的類型*/l typedef struct Sqlistl ElemType *slist; /*存儲(chǔ)空間的基地址*/l int length; /*順序表的當(dāng)前長(zhǎng)度*/l int listsize; /*當(dāng)前分配的存儲(chǔ)空間*/l Sqlist;

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

4、lemType e); /*查找值為e的元素*/l l int 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;i<n;i+)l

5、printf("input data %d",i+1);l scanf("%d",&e);l if(!ListInsert_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;i<=L->length;i+)l printf("%5d",L->slisti-1);l return OK;l /*PrintList*/l l

6、int ListInsert_sq(Sqlist *L,int i,ElemType e)l int k;l if(i<1|i>L->length+1) l return ERROR; l if(L->length>=L->listsize) 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->

7、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個(gè)元素*/l int ListDelete_sq(Sqlist *L,int i)l int k;l if(i<1|i>L->length) l return ERROR; l for(k=i-1;k<=L->length-1;k+)l l L->slistk=L->slistk+1;

8、l l L->length-; l return 0;l /listDelete_l /*在順序表中查找指定值元素，返回其序號(hào)*/l /*int ListLocate(Sqlist *L,ElemType e)l l int n;l int i;l if(i<1|i>L->length) l return ERROR; l for(n=0;n<i;n+)l l l e=L->slistn-1;l l */lll int ListLocate(Sqlist *L,ElemType e)l l int k;l for(k=0;k<=L->length

9、-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:"); /*輸入順序表的元素個(gè)數(shù)*/l scanf("%d",&n);l if(n>0)l printf("n1-Cr

10、eate Sqlist:n");l InitList_sq(&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

11、 PrintList_sq(&sl);llll printf("nplease input insert location and data:(location,data)n");l scanf("%d,%d",&m,&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:(locat

12、ion)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",&m);l ListLocate(&sl,m);l l printf("n3-Print Sqlist:n&q

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

14、 k;l if(i<1|i>L->length) l return ERROR; l for(k=i-1;k<=L->length-1;k+)l l L->slistk=L->slistk+1;l l L->length-; l return 0;l /listDelete_l 運(yùn)行結(jié)果查找算法代碼：int ListLocate(Sqlist *L,ElemType e) int k;for(k=0;k<=L->length-1;k+)if(e=L->slistk) printf("此元素地址為：%dn",k

15、+1); return OK; if(k=L->length)printf("不存在!");return ERROR;lll 運(yùn)行結(jié)果l 算法分析l /*在順序表中查找指定值元素，返回其序號(hào)*/l int ListLocate(Sqlist *L,ElemType e)l l int k;l for(k=0;k<=L->length-1;k+)/*從第一個(gè)元素開(kāi)始查找*/l if(e=L->slistk)l l printf("此元素地址為：%dn",k+1);l return OK;/*若存在與e相等的元素，則輸出其地址，返回O

16、K*/l l if(k=L->length)l l printf("不存在!");l return ERROR;/*不存在*/l 3、閱讀下面程序，在橫線處填寫(xiě)函數(shù)的基本功能。并運(yùn)行程序，寫(xiě)出結(jié)果。l #inclull de<stdio.h>l #include<malloc.h>l #define ERROR 0l #define OK 1l typedef int ElemType; /*定義表元素的類型*/l typedef struct LNode /*線性表的單鏈表存儲(chǔ)*/l ElemType data;l struct LNode

17、*next;l LNode,*LinkList;ll LinkList CreateList(int n); /* 不斷的往鏈表中插入元素 */l void PrintList(LinkList L); /*輸出帶頭結(jié)點(diǎn)單鏈表的所有元素*/l int GetElem(LinkList L,int i,ElemType *e); /* 當(dāng)?shù)趇個(gè)元素存在時(shí)，其值賦給e */ l int ListInsert(LinkList L,int i,ElemType *e);l void ListDelete(LinkList L,int i);lll LinkList CreateList(int n)

18、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;i<n;i+)l l q=(LinkList)malloc(sizeof(LNode); printf("input data %i:",i+1);l scanf("%d",&q->data); /*輸入元素值*/l q->next=NULL; /*結(jié)點(diǎn)指針域置空*/l p->next=q; /*新結(jié)點(diǎn)連在表末

19、尾*/l p=q;l l return head;l /*CreateList*/ll void PrintList(LinkList L)l LNode *p;l p=L->next; /*p指向單鏈表的第1個(gè)元素*/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&&

20、;j<i-1)l l p=p->next;+j;l ll if(!p|j>i-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&&j<i-1)l l p=p->

21、;next;+j;l ll if(!(p->next)|j>i-1)l return ERROR;l q=p->next;l p->next=q->next;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&&j<i) l p=p->next;j+;l l if(!p|j>i)l return ERROR; l *e=p->data; l ret

22、urn OK;l /*GetElem*/ll int main()l int n,i;ElemType e;l LinkList L=NULL; /*定義指向單鏈表的指針*/l printf("please input n:"); /*輸入單鏈表的元素個(gè)數(shù)*/l scanf("%d",&n);l if(n>0)l printf("n1-Create LinkList:n");l L=CreateList(n); l printf("n2-Print LinkList:n");l PrintList(L); l ll ll printf("n請(qǐng)輸入插入位置和數(shù)據(jù):(location,data)n");l scanf("%d,%d",&i,&e);l ListInsert(L,i,&e);l PrintList(L); ll printf("n請(qǐng)輸入刪除位置:n");l scanf("%d",&i);l ListDelete(L,i);l PrintList(L); ll printf("n3-GetElem from Lin