线性表及其实现实验二.docx
- 文档编号:17444856
- 上传时间:2023-07-25
- 格式:DOCX
- 页数:30
- 大小:91.97KB
线性表及其实现实验二.docx
《线性表及其实现实验二.docx》由会员分享,可在线阅读,更多相关《线性表及其实现实验二.docx(30页珍藏版)》请在冰点文库上搜索。
线性表及其实现实验二
实验二线性表及其实现
一.实验目的及要求
(1)熟悉线性表的基本运算在两种存储结构(顺序结构和链式结构)上的实现,以线性表的各种操作(建立、插入、删除等)的实现为实验重点;
(2)通过本次实验帮助学生加深对顺序表、链表的理解,并加以应用;
(3)掌握循环链表和双链表的定义和构造方法
二.实验内容:
(1)编程实现线性表两种存储结构(顺序存储、链式存储)中的基本操作的实现(线性表的创建、插入、删除和查找等),并设计一个菜单调用线性表的基本操作。
(2)建立一个按元素递增有序的单链表L,并编写程序实现:
a)将x插入其中后仍保持L的有序性;
b)将数据值介于min和max之间的结点删除,并保持L的有序性;
c)将单链表L逆置并输出;
(3)编程实现将两个按元素递增有序的单链表合并为一个新的按元素递增的单链表。
三.实验主要流程、基本操作或核心代码、算法片段(该部分如不够填写,请另加附页)
(1)编程实现线性表两种存储结构(顺序存储、链式存储)中的基本操作的实现(线性表的创建、插入、删除和查找等),并设计一个菜单调用线性表的基本操作。
Ø程序代码:
顺序存储:
头文件:
#defineINIT_SIZE100
#defineINCREMENT10
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
#defineINFEASIBLE-1
#defineOVERFLOW-2
typedefintStatus;
typedefintElemType;
typedefstruct
{
ElemType*elem;
intlength;
intlistsize;
}Sq;
StatusInit_Sq(Sq&L);
StatusInsert_Sq(Sq&L,inti,ElemTypee);
StatusDelete_Sq(Sq&L,inti,ElemType&e);
主函数:
#include"stdio.h"
#include"1.h"
#include"stdlib.h"
intmain()
{
SqL;
printf("是否建立顺序表?
\n");
printf("1、建立\n");
printf("2、退出程序\n");
inta;//选择是否建立
scanf("%d",&a);
switch(a)
{
case1:
Init_Sq(L);
break;
case2:
printf("程序结束!
\n");
exit(OVERFLOW);
default:
printf("输入错误!
\n");
}
printf("请输入要放入顺序表中的元素个数(不要超过100)\n");
scanf("%d",&L.length);
inti;//进行用户输入循环
printf("请输入具体元素\n");
for(i=0;i { scanf("%d",&L.elem[i]); } intb;//选择操作 do{ printf("请选择下列操作\n"); printf("1、向表中添加元素\n"); printf("2、删除表中某一元素\n"); printf("3、退出程序\n"); scanf("%d",&b); switch(b) { case1: ElemTypex;//新元素 intc;//新元素位置 printf("请输入要添加的元素,和添加的位置(空格隔开)\n"); scanf("%d%d",&x,&c); Insert_Sq(L,c,x); intj;//新表输出循环 printf("新表为: \n"); for(j=0;j { printf("%d",L.elem[j]); } printf("\n"); break; case2: intd;//需要删除元素的位置 ElemTypey;//被删除的元素 printf("请输入删除元素的位置\n"); scanf("%d",&d); Delete_Sq(L,d,y); printf("被删除的元素是%d\n",y); printf("剩下的元素为: \n"); intf;//输出循环 for(f=0;f { printf("%d",*(L.elem+f)); } printf("\n"); break; case3: printf("程序结束! \n"); exit(OVERFLOW); default: printf("输入出错! \n"); } }while(b! =3); return0; } 功能函数: #include"stdio.h" #include"stdlib.h" #include"1.h" StatusInit_Sq(Sq&L) { L.elem=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType)); if(! L.elem)exit(OVERFLOW); L.length=0; L.listsize=INIT_SIZE; returnOK; } StatusInsert_Sq(Sq&L,inti,ElemTypee) { if(L.length==100) { int*newpase; newpase=(ElemType*)realloc(L.elem,(L.length+INCREMENT)*sizeof(ElemType)); if(! newpase)exit(OVERFLOW); L.elem=newpase; L.listsize+=INCREMENT; } if(i<1||i>L.length+1) { returnERROR; } L.length+=1; intb=L.length;//用于循环 while(i<=b) { L.elem[b]=L.elem[b-1]; b--; } L.elem[i-1]=e; returnOK; } StatusDelete_Sq(Sq&L,inti,ElemType&e) { if(i<1||i>L.length+1) { returnERROR; } e=L.elem[i-1]; intj; for(j=i-1;j { L.elem[j]=L.elem[j+1]; } L.length-=1; returnOK; } 链式存储: 头文件: #defineOK1 #defineERROR0 #defineTRUE1 #defineFALSE0 #defineINFEASIBLE-1 #defineOVERFLOW-2 typedefintStatus; typedefintElemType; typedefstructLNode{ ElemTypedata; structLNode*next; }LNode,*LinkList; voidCreate_L(intn,LinkList&L); StatusInsert_L(LinkList&L,inti,ElemTypee); StatusDelete_L(LinkList&L,inti,ElemType&e); StatusGetElem_L(LinkListL,inti,ElemType&e); 主函数: #include"stdio.h" #include"1.h" intmain() { printf("是否建立链表\n"); inta;//选择 printf("1、建立\n"); printf("2、退出程序\n"); scanf("%d",&a); switch(a) { case1: LinkListL; printf("请输入链表长度(不计算头结点)\n"); intn;//数据容纳度 scanf("%d",&n); Create_L(n,L); intb;//选择功能 printf("请选择以下功能: \n"); do { printf("1、查找某位置元素\n"); printf("2、在某位置插入元素\n"); printf("3、删除某位置元素\n"); printf("4、结束程序\n"); scanf("%d",&b); switch(b) { case1: { printf("请输入查找位置\n"); intc;//查找位置 ElemTyped;//数据容器 scanf("%d",&c); if(c>n) { printf("该位置大于数据个数,请重新选择\n"); break; } GetElem_L(L,c,d); printf("第%d个数据为: %d\n",c,d); break; } case2: { printf("请输入在什么位置插入什么数据(空格隔开)\n"); intf,g;//位置、数据 scanf("%d%d",&f,&g); Insert_L(L,f,g); printf("此时的数据为: \n"); inth; n=n+1; LinkListl=L; for(h=0;h { printf("%d",l->next->data); l=l->next; } printf("\n"); break; } case3: { printf("请输入需要删除的位置\n"); intm; ElemTypeo; scanf("%d",&m); Delete_L(L,m,o); n=n-1; printf("此时的数据还有: \n"); intq; LinkListr=L; for(q=0;q { printf("%d",r->next->data); r=r->next; } printf("\n"); break; } case4: printf("程序结束\n"); break; default: printf("输入出错\n"); } }while(b! =4); break; case2: printf("程序退出\n"); break; default: printf("输入错误\n"); } } 功能函数: #include"1.h" #include"stdio.h" #include"stdlib.h" voidCreate_L(intn,LinkList&L) { L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; printf("请逆序输入相应个数的数据\n"); inti;//用于循环 LinkListp; for(i=n;i>0;i--) { p=(LinkList)malloc(sizeof(LNode)); scanf("%d",&p->data); p->next=L->next; L->next=p; } } StatusGetElem_L(LinkListL,inti,ElemType&e) { intj;//用于循环 LinkListp=L; if(p) { for(j=0;j { p=p->next; } e=p->data; } returnOK; } StatusInsert_L(LinkList&L,inti,ElemTypee) { LinkListp; p=L; intj=0; while(p&&j { p=p->next; j++; } if(! p||j>i-1) returnERROR; LinkLists; s=(LinkList)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; returnOK; } StatusDelete_L(LinkList&L,inti,ElemType&e) { LinkListp=L; intj=0; while(p->next&&j { p=p->next; j++; } if(! (p->next)||j>i-1) returnERROR; LinkListq; q=p->next; p->next=q->next; e=q->data; printf("被删除的元素为: %d\n",e); free(q); returnOK; } Ø运行结果: (2)建立一个按元素递增有序的单链表L,并编写程序实现: a)将x插入其中后仍保持L的有序性; b)将数据值介于min和max之间的结点删除,并保持L的有序性; c)将单链表L逆置并输出; 程序代码部分: 头文件: #defineOK1 #defineERROR0 #defineTRUE1 #defineFALSE0 #defineOVERFLOW-1 #defineINFEASIBLE-2 typedefintElemType; typedefintStatus; typedefstructLNode{ ElemTypedata; structLNode*next; }LNode,*LinkList; StatusCreate(LinkList&L,intn); StatusInsert(LinkList&L,ElemTypee,intn); StatusDelete(LinkList&L,intmin,intmax,int&n); StatusReverse(LinkListL,intn); 主函数: #include"stdio.h" #include"1.h" intmain() { printf("是否建立单链表? \n"); printf("1、建立\n"); printf("2、不建立并结束程序\n"); inta;//判断是否建立链表 scanf("%d",&a); switch(a) { case1: { LinkListL,p; printf("请确定单链表的节点个数\n"); intnode_num;//节点个数 scanf("%d",&node_num); Create(L,node_num); p=L; printf("现在的单链表为: \n"); for(inti=0;i { p=p->next; printf("%d",p->data); } printf("\n"); printf("请选择下列操作\n"); intb;//选择操作 do { printf("1、插入一个元素\n"); printf("2、删除某个范围内的元素(不删除上下限)\n"); printf("3、逆置单链表中的元素\n"); printf("4、结束程序\n"); scanf("%d",&b); switch(b) { case1: { intinsert;//插入的元素 printf("请输入要插入的元素\n"); scanf("%d",&insert); Insert(L,insert,node_num); LinkListp=L; printf("此时单链表中的元素为: \n"); for(inti=0;i { printf("%d",p->next->data); p=p->next; } printf("\n"); } node_num+=1; break; case2: { printf("请输入删除范围的上下限(空格隔开)\n"); intmin,max; scanf("%d%d",&min,&max); printf("被删除的元素有: \n"); Delete(L,min,max,node_num); printf("此时的单链表元素有: \n"); LinkListp=L; for(inti=0;i { printf("%d",p->next->data); p=p->next; } printf("\n"); } break; case3: { Reverse(L,node_num); } break; case4: printf("程序结束! \n"); break; default: printf("输入错误! \n"); } }while(b! =4); } break; case2: printf("程序结束! \n"); break; default: printf("输入错误! \n"); } } 功能函数: #include"stdio.h" #include"stdlib.h" #include"1.h" //顺序输入N个元素建立单链表与书上30页的2.10是不同的方法 StatusCreate(LinkList&L,intn) { L=(LinkList)malloc(sizeof(LNode)); if(! L)exit(OVERFLOW); L->next=NULL; LinkListq=L; printf("请输入具体元素\n"); for(inti=0;i { LinkListp=(LinkList)malloc(sizeof(LNode)); scanf("%d",&p->data); //与30页不同之处 q->next=p; p->next=NULL; q=q->next; } returnOK; } StatusInsert(LinkList&L,ElemTypee,intn) { LinkListp; p=L; LinkLists=(LinkList)malloc(sizeof(LNode)); if(! s)exit(OVERFLOW); s->data=e; for(inti=0;i { if(e<=p->next->data) { s->next=p->next; p->next=s; break; } p=p->next; } if(p->next==NULL) { p->next=s; s->next=NULL; } returnOK; } StatusDelete(LinkList&L,intmin,intmax,int&n) { ElemTypee;//显示被删除的元素 inta=n;//判别n是否变化 LinkListp=L;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性 及其 实现 实验