实验一 顺序表与链表 成品.doc

.实验一 顺序表与链表一、实验目的1、掌握线性表中元素的前驱、后续的概念。2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。3、对线性表相应算法的时间复杂度进行分析。4、理解顺序表、链表数据结构的特点（优缺点）。 二、实验预习说明以下概念1、线性表：线性表是最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。2、顺序表：线性表的顺序存储结构或顺序映像，通常，称这种存储结构的线性表为顺序表。3、链表：指针域中存储的信息称作指针或链。N个接点连接成一个链表，故又称线性链表。三、实验内容和要求1、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。l #includel #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); /* 构造一个空的线性表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,ElemType 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;in;i+)l 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;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-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-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(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 *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:); /*输入顺序表的元素个数*/l scanf(%d,&n);l if(n0)l printf(n1-Create 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 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:(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,&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；输入线性表的元素个数，然后构建一个新的线性表，2；连续用creatlist函数往性表里插入元素，将其元素输出，3；在下一步中输入插入元素的位置和个数，最后一步，输出运行后的线性表。2、为第1题补充删除和查找功能函数，并在主函数中补充代码验证算法的正确性。删除算法代码：l int ListDelete_sq(Sqlist *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(不存在!);return 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、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。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(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)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; /*结点指针域置空*/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&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;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:); /*输入单链表的元素个数*/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请输入插入位置和数据:(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);