实验一顺序表与链表 成品

1、实验一 顺序表与链表一、实验目的1、掌握线性表中元素的前驱、后续的概念。2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。3、对线性表相应算法的时间复杂度进行分析。4、理解顺序表、链表数据结构的特点（优缺点）。 二、实验预习说明以下概念1、线性表：线性表是最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。2、顺序表：线性表的顺序存储结构或顺序映像，通常，称这种存储结构的线性表为顺序表。3、链表：指针域中存储的信息称作指针或链。N个接点连接成一个链表，故又称线性链表。三、实验内容和要求1、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。l #includ

2、e<stdio.h>l #include<malloc.h>l #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;

3、l l int InitList_sq(Sqlist *L); /* 构造一个空的线性表L */l int CreateList_sq(Sqlist *L,int n); /* 不断地插入元素 */l int ListInsert_sq(Sqlist *L,int i,ElemType e);/* 在L中第i个 位置之前插入一个数据元素e，L的长度加1 */l int PrintList_sq(Sqlist *L); /*输出顺序表的元素*/l int ListDelete_sq(Sqlist *L,int i); /*删除第i个元素*/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个元素*/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 /*在顺序表中查找指定值元素，返回其序号*/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:"); /*输入顺序表的元素个数*/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 运行结果l 算法分析1；输入线性表的元素个数，然后构建一个新的线性表，2；连续用creatlist函数往性表里插入元素，将其元素输出，3；在下一步中输入插入元素的位置和个数，最后一步，输出运行后的线性表。2、为第1题补充删除和查找功能函数，并在主函数中补充代码验证算法的正确性。删除算法代码：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 运行结果查找算法代码：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 运行结果l 算法分析l /*在顺序表中查找指定值元素，返回其序号*/l int ListLocate(Sqlist *L,ElemType e)l l int k;l for(k=0;k<=L->length-1;k+)/*从第一个元素开始查找*/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、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。l #inclull de<stdio.h>l #include<malloc.h>l #define ERROR 0l #define OK 1l typedef int ElemType; /*定义表元素的类型*/l typedef struct LNode /*线性表的单链表存储*/l ElemType data;l struct LNode

17、*next;l LNode,*LinkList;ll LinkList CreateList(int n); /* 不断的往链表中插入元素 */l void PrintList(LinkList L); /*输出带头结点单链表的所有元素*/l int GetElem(LinkList L,int i,ElemType *e); /* 当第i个元素存在时，其值赋给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; /*结点指针域置空*/l p->next=q; /*新结点连在表末

19、尾*/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&&

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:"); /*输入单链表的元素个数*/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请输入插入位置和数据:(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 PrintList(L); ll printf("n3-GetElem from Lin