实验一顺序表与链表.docx
- 文档编号:6963131
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:12
- 大小:133.76KB
实验一顺序表与链表.docx
《实验一顺序表与链表.docx》由会员分享,可在线阅读,更多相关《实验一顺序表与链表.docx(12页珍藏版)》请在冰点文库上搜索。
实验一顺序表与链表
实验一顺序表与链表
一、实验目的
1、掌握线性表中元素的前驱、后续的概念。
2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。
3、对线性表相应算法的时间复杂度进行分析。
4、理解顺序表、链表数据结构的特点(优缺点)。
二、实验预习
说明以下概念
1、线性表:
2、顺序表:
3、链表:
三、实验容和要求
1、阅读下面程序,在横线处填写函数的基本功能。
并运行程序,写出结果。
#include
#include
#defineERROR0
#defineOK1
#defineINIT_SIZE5/*初始分配的顺序表长度*/
#defineINCREM5/*溢出时,顺序表长度的增量*/
typedefintElemType;/*定义表元素的类型*/
typedefstructSqlist{
ElemType*slist;/*存储空间的基地址*/
intlength;/*顺序表的当前长度*/
intlistsize;/*当前分配的存储空间*/
}Sqlist;
intInitList_sq(Sqlist*L);/*构造一个空的线性表L*/
intCreateList_sq(Sqlist*L,intn);/*构造顺序表的长度为n*/
intListInsert_sq(Sqlist*L,inti,ElemTypee);/*在L中第i个位置之前插入新的数据元素e,L的长度加1*/
intPrintList_sq(Sqlist*L);/*输出顺序表的元素*/
intListDelete_sq(Sqlist*L,inti);/*删除第i个元素*/
intListLocate(Sqlist*L,ElemTypee);/*查找值为e的元素*/
intInitList_sq(Sqlist*L){
L->slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));
if(!
L->slist)returnERROR;
L->length=0;
L->listsize=INIT_SIZE;
returnOK;
}/*InitList*/
intCreateList_sq(Sqlist*L,intn){
ElemTypee;
inti;
for(i=0;i printf("inputdata%d",i+1); scanf("%d",&e); if(! ListInsert_sq(L,i+1,e)) returnERROR; } returnOK; }/*CreateList*/ /*输出顺序表中的元素*/ intPrintList_sq(Sqlist*L){ inti; for(i=1;i<=L->length;i++) printf("%5d",L->slist[i-1]); returnOK; }/*PrintList*/ intListInsert_sq(Sqlist*L,inti,ElemTypee){ intk; if(i<1||i>L->length+1) returnERROR; if(L->length>=L->listsize){ L->slist=(ElemType*)realloc(L->slist, (INIT_SIZE+INCREM)*sizeof(ElemType)); if(! L->slist) returnERROR; L->listsize+=INCREM; } for(k=L->length-1;k>=i-1;k--){ L->slist[k+1]=L->slist[k]; } L->slist[i-1]=e; L->length++; returnOK; }/*ListInsert*/ /*在顺序表中删除第i个元素*/ intListDelete_sq(Sqlist*L,inti){ } /*在顺序表中查找指定值元素,返回其序号*/ intListLocate(Sqlist*L,ElemTypee){ } intmain(){ Sqlistsl; intn,m,k; printf("pleaseinputn: ");/*输入顺序表的元素个数*/ scanf("%d",&n); if(n>0){ printf("\n1-CreateSqlist: \n"); InitList_sq(&sl); CreateList_sq(&sl,n); printf("\n2-PrintSqlist: \n"); PrintList_sq(&sl); printf("\npleaseinputinsertlocationanddata: (location,data)\n"); scanf("%d,%d",&m,&k); ListInsert_sq(&sl,m,k); printf("\n3-PrintSqlist: \n"); PrintList_sq(&sl); printf("\n"); } else printf("ERROR"); return0; } ●运行结果 ●算法分析 调用ListInsert_sq()函数,进行插入操作,并输出插入新元素后的状态,时间复杂度,空间复杂度较少, 2、为第1题补充删除和查找功能函数,并在主函数中补充代码验证算法的正确性。 删除算法代码: intListDelete_sq(Sqlist*L,inti){ intp; if(i<1||i>L->length) returnERROR; for(p=i-1;p L->slist[p]=L->slist[p+1]; } L->length--; returnOK; } ●运行结果 ●算法分析 主函数调用ListDelete_sq实现删除操作,在输出删除之后的线性表,时间复杂度低 查找算法代码: intListLocate(Sqlist*L,ElemTypee){ inti=0; while((i<=L->length)&&(L->slist[i]! =e)){ i++; } if(i<=L->length) return(i+1); else return-1; } ●运行结果 ●算法分析 主函数通过调用ListLocate实现查找功能,然后输出查找元素的序号,时间复杂度低 3、阅读下面程序,在横线处填写函数的基本功能。 并运行程序,写出结果。 #include #include #defineERROR0 #defineOK1 typedefintElemType;/*定义表元素的类型*/ typedefstructLNode{/*线性表的单链表存储*/ ElemTypedata; structLNode*next; }LNode,*LinkList; LinkListCreateList(intn);/*构造顺序表的长度为n*/ voidPrintList(LinkListL);/*输出带头结点单链表的所有元素*/ intGetElem(LinkListL,inti,ElemType*e);/*在顺序表L中,将第i个元素存在时,替换成e*/ LinkListCreateList(intn){ LNode*p,*q,*head; inti; head=(LinkList)malloc(sizeof(LNode));head->next=NULL; p=head; for(i=0;i q=(LinkList)malloc(sizeof(LNode));printf("inputdata%i: ",i+1); scanf("%d",&q->data);/*输入元素值*/ q->next=NULL;/*结点指针域置空*/ p->next=q;/*新结点连在表末尾*/ p=q; } returnhead; }/*CreateList*/ voidPrintList(LinkListL){ LNode*p; p=L->next;/*p指向单链表的第1个元素*/ while(p! =NULL){ printf("%5d",p->data); p=p->next; } }/*PrintList*/ intGetElem(LinkListL,inti,ElemType*e){ LNode*p;intj=1; p=L->next; while(p&&j p=p->next;j++; } if(! p||j>i) returnERROR; *e=p->data; returnOK; }/*GetElem*/ intmain(){ intn,i;ElemTypee; LinkListL=NULL;/*定义指向单链表的指针*/ printf("pleaseinputn: ");/*输入单链表的元素个数*/ scanf("%d",&n); if(n>0){ printf("\n1-CreateLinkList: \n"); L=CreateList(n); printf("\n2-PrintLinkList: \n"); PrintList(L); printf("\n3-GetElemfromLinkList: \n"); printf("inputi="); scanf("%d",&i); if(GetElem(L,i,&e)) printf("No%iis%d",i,e); else printf("notexists"); }else printf("ERROR"); return0; } ●运行结果 ●算法分析 主函数调用GetElem函数实现输出序号所对应的元素,时间复杂度低 4、为第3题补充插入功能函数和删除功能函数。 并在主函数中补充代码验证算法的正确性。 插入算法代码: int ListInsert_sq(LNode *L,int i,ElemType e){ int k; if(i<1||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->data[k+1]=L->datak]; } L->slist[i-1]=e; L->length++; returnOK; }/*ListInsert*/ ●运行结果 ●算法分析 调用ListInsert_sq()函数,进行插入操作,并输出插入新元素后的状态,时间复杂度 删除算法代码: int ListInsert_sq(LNode *L,int i,ElemType e){ intp; if(i<1||i>L->length) returnERROR; for(p=i-1;p L->slist[p]=L->slist[p+1]; } L->length--; returnOK; } ●运行结果 ●算法分析 主函数调用ListDelete_sq实现删除操作,在输出删除之后的线性表,时间复杂度低
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验 顺序