試驗(yàn)一順序表與鏈表

1、、實(shí)驗(yàn)?zāi)康?、掌握線性表中元素的前驅(qū)、后續(xù)的概念。2、掌握順序表與鏈表的建立、插入元素、刪除表中某元素的算法。3、對線性表相應(yīng)算法的時(shí)間復(fù)雜度進(jìn)行分析。4、理解順序表、鏈表數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)（優(yōu)缺點(diǎn)） 。二、實(shí)驗(yàn)預(yù)習(xí)說明以下概念1、線性表：2、順序表：3、鏈表：三、實(shí)驗(yàn)內(nèi)容和要求1、閱讀下面程序，在橫線處填寫函數(shù)的基本功能。并運(yùn)行程序，寫出結(jié)果。#include<>#include<># define ERROR 0# define OK 1初始分配的順序表長度*/溢出時(shí)，順序表長度的增量*/定義表元素的類型*/存儲空間的基地址*/順序表的當(dāng)前長度*/當(dāng)前分配的存儲空間*/

2、# define INIT_SIZE 5 /* #define INCREM 5/*typedef int ElemType; /* typedef struct SqlistElemType *slist; /* int length; /* int listsize; /* Sqlist;int InitList_sq(Sqlist *L); /*構(gòu)造一個(gè)空的線性表L*/int CreateList_sq(Sqlist *L,int n); /*構(gòu)造順序表的長度為n */int ListInsert_sq(Sqlist *L,int i,ElemTypee);/* 在 L 中第 i 個(gè)位置

3、之前插入新的數(shù)據(jù)元素e, L的長度加1*/int PrintList_sq(Sqlist *L); /*輸出順序表的元素 */int ListDelete_sq(Sqlist *L,int i); /*刪除第 i 個(gè)元素 */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->

4、;listsize=INIT_SIZE;return OK;/*InitList*/int CreateList_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<=

5、L->length;i+)printf("%5d",L->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->slis

6、t)return ERROR;L->listsize+=INCREM;for(k=L->length-1;k>=i-1;k-)L->slistk+1= L->slistk;L->slisti-1=e;L->length+;return OK;/*ListInsert*/ /*在順序表中刪除第i個(gè)元素*/ int ListDelete_sq(Sqlist *L,int i)/*在順序表中查找指定值元素，返回其序號 */int ListLocate(Sqlist *L,ElemType e)int main()Sqlist sl;int n,m,k;pri

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

8、");scanf("%d,%d",&m,&k);ListInsert_sq(&sl,m,k);printf("n3-Print Sqlist:n");PrintList_sq(&sl);printf("n");)elseprintf("ERROR");return 0;)運(yùn)行結(jié)果算法分析調(diào)用ListInsert_sq() 函數(shù)，進(jìn)行插入操作，并輸出插入新元素后的狀態(tài)，時(shí)間復(fù)雜度，空間復(fù)雜度較少，2、為第1題補(bǔ)充刪除和查找功能函數(shù)，并在主函數(shù)中補(bǔ)充代碼驗(yàn)證算法的正確性。 刪除

9、算法代碼：int ListDelete_sq(Sqlist *L,int i) int p;if(i<1|i>L->length)return ERROR;for(p=i-1;p<L->length-1;p+)L->slistp=L->slistp+1;L->length -;return OK;運(yùn)行結(jié)果算法分析主函數(shù)調(diào)用ListDelete_sq 實(shí)現(xiàn)刪除操作，在輸出刪除之后的線性表，時(shí)間復(fù)雜度低查找算法代碼：int ListLocate(Sqlist *L,ElemType e)int i=0;while(i<=L->length

10、) && (L->slist i!=e)i+;if(i<=L->length )return (i+1);elsereturn -1;運(yùn)行結(jié)果算法分析主函數(shù)通過調(diào)用ListLocate 實(shí)現(xiàn)查找功能，然后輸出查找元素的序號，時(shí)間復(fù)雜度低3、閱讀下面程序，在橫線處填寫函數(shù)的基本功能。并運(yùn)行程序，寫出結(jié)果。#include<>#include<>#define ERROR 0#define OK 1typedef int ElemType;/*定義表元素的類型 */typedef struct LNode /*線性表的單鏈表存儲 */Ele

11、mType data;struct LNode *next;LNode,*LinkList;LinkList CreateList(int*/void PrintList(LinkList L); /*int GetElem(LinkList L,int替換成e */n);/* 構(gòu)造順序表的長度為 n輸出帶頭結(jié)點(diǎn)單鏈表的所有元素*/i,ElemType *e); /* 在順序表 L中，將第i個(gè)元素存在時(shí)，LinkList CreateList(int n)LNode *p,*q,*head;int i;head=(LinkList)malloc(sizeof(LNode); p=head;fo

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

13、第1個(gè)元素*/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;return OK;/*GetElem*/int main()int n,i;ElemType e;LinkList L=NULL;

14、/*定義指向單鏈表的指針 */printf("please input n:"); /*輸入單鏈表的元素個(gè)數(shù) */scanf("%d",&n);if(n>0)printf("n1-Create LinkList:n");L=CreateList(n);printf("n2-Print LinkList:n");PrintList(L);printf("n3-GetElem from LinkList:n");printf("input i=");scanf(&q

15、uot;%d",&i);if(GetElem(L,i,&e)printf("No%i is %d",i,e);elseprintf("not exists");elseprintf("ERROR");return 0;運(yùn)行結(jié)果算法分析主函數(shù)調(diào)用GetElem函數(shù)實(shí)現(xiàn)輸出序號所對應(yīng)的元素，時(shí)間復(fù)雜度低4、為第3題補(bǔ)充插入功能函數(shù)和刪除功能函數(shù)。并在主函數(shù)中補(bǔ)充代碼驗(yàn)證算法的正確性。插入算法代碼：int ListInsert_sq(LNode *L,int i,ElemType e)int k;if(i<1

16、|i>L->length+1)return ERROR;if(L->length>=L->listsize)L->data =(ElemType*)realloc(L->data, (INIT_SIZE+INCREM)*sizeof(ElemType);if(!L->data)return ERROR;L->listsize+=INCREM;for(k=L->length-1;k>=i-1;k-)L->datak+1= L->datak; L->slisti-1=e;L->length+;return OK;/*ListInsert*/運(yùn)行結(jié)果算法分析調(diào)用ListInsert_sq() 函數(shù)，進(jìn)行插入操