北京信息科技大学 数据结构实验一顺序表和单链表的操作.docx
《北京信息科技大学 数据结构实验一顺序表和单链表的操作.docx》由会员分享，可在线阅读，更多相关《北京信息科技大学 数据结构实验一顺序表和单链表的操作.docx（15页珍藏版）》请在冰点文库上搜索。
北京信息科技大学数据结构实验一顺序表和单链表的操作
实验报告
课程名称数据结构
实验项目顺序表和单链表的操作
实验仪器计算机
系别计算机学院学院
专业
班级/学号
学生姓名
实验日期
成绩
指导教师
一 、实验目的
（1）熟悉顺序表的操作方法。
（2）熟悉单链表的操作方法。
（3）了解这两者间的区别和各自的优缺点。
二、 实验内容
（1）用顺序表实现数据的增、删、查功能
（2）用单链表实现数据的增、删、查、改等功能
三、实验课时
4课时
四、实验步骤
1.仔细分析并理解数据结构这本书上提供的部分程序伪代码
2.根据所给的代码编写出主函数和一些需要用到的函数
3.将伪代码翻译为程序能用的代码
4．充分理解每段代码的含义以及它所起到的作用
5.编译调试，纠正错误并分析出错的原因
6.运行并测试
五、程序源代码
1.顺序表：
#include
#include
#include
#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量
#defineLISTINCREMENT10//线性表存储空间的分配增量
#defineOK1
#defineOVERFLOW-2
#defineERROR0
typedefintElemType;
typedefintStatus;
typedefstruct//用户自定义结构体SqList
{
ElemType*elem;//指针指向存储空间基址
intlength;
intlistsize;
}SqList;
StatusPut（SqList&L,intn）
{
printf（"向线性表中输入这n个数据:
"）;
for（inti=0;iscanf（"%d",&L.elem[i]）;
L.length=L.length+n;
returnOK;
}
StatusOut（SqList&L,intn）
{
printf（"该线性表为:
"）;
for（inti=0;iprintf（"%d",L.elem[i]）;
returnOK;
}
StatusInitlist_Sq（SqList&L）
{
L.elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType））;
if（!
L.elem）exit（OVERFLOW）;
L.length=0;//空表长度为0
L.listsize=LIST_INIT_SIZE;//初始存储容量
returnOK;
}
int*p,*q,*e;
StatusListInsert_Sq（SqList&L,inti,ElemTypee）
{
ElemType*newbase;
printf（"请输入要插入的位置：
"）;
scanf（"%d",&i）;
printf（"请输入要插入的数据：
"）;
scanf（"%d",&e）;
if（i<1||i>L.length+1）returnERROR;//i的值不合法
if（L.length>=L.listsize）
{//存储空间已满，增加分配
newbase=（ElemType*）realloc（L.elem,
（L.listsize+LISTINCREMENT）*sizeof（ElemType））;
if（!
newbase）exit（OVERFLOW）;//重新分配失败
L.elem=newbase;
L.listsize+=LISTINCREMENT;//增加分配容量
}
q=&（L.elem[i-1]）;//q为插入地址
for（p=&（L.elem[L.length-1]）;p>=q;--p）*（p+1）=*p;//插入元素后移
*q=e;
++L.length;
Out（L,L.length）;
returnOK;
}
StatusListDelete_Sq（SqList&L,inti,ElemType&e）
{
printf（"请输入要删除的位置：
"）;
scanf（"%d",&i）;
printf（"请输入要删除的数据：
"）;
scanf（"%d",&e）;
if（（i<1）||（i>=L.length））returnERROR;
p=&（L.elem[i-1]）;
e=*p;
q=L.elem+L.length-1;
for（++p;p<=q;++p）*（p-1）=*p;
--L.length;
Out（L,L.length）;
returnOK;
}
intLocateElem_Sq（SqListL,ElemTypef）
{
inti=1;
p=L.elem;
printf（"请输入要查找的元素：
"）;
scanf（"%d",&f）;
while（（i<=L.length）&&!
（（*p++）==f））i++;
if（i<=L.length）
printf（"该元素在表中位置为%d",i）;
else
printf（"该元素不在表中"）;
returnOK;
}
intmain（）
{
intn=0,b=0,i=0,e=0,f=0;
SqListL;
Initlist_Sq（L）;
printf（"请指定该顺序表有n个元素个数：
"）;
scanf（"%d",&n）;
Put（L,n）;
Out（L,n）;
do
{
printf（"\n请输入以下指令来进行操作：
1.插入2.删除3.查找\n"）;
scanf（"%d",&b）;
switch（b）
{
case1:
ListInsert_Sq（L,i,e）;break;
case2:
ListDelete_Sq（L,i,e）;break;
case3:
LocateElem_Sq（L,f）;break;
default:
printf（"输入指令有误!
"）;break;
}
}
while（b!
=0）;
return0;
}
2.单链表：
#include
usingnamespacestd;
#definetrue1
#definefalse0
#defineok1
#defineerror0
#defineoverflow-1
typedefintStatus;
typedefintElemType;
typedefstructLNode
{ElemTypedata;
structLNode*next;
}LNode,*LinkList;
voidshow（LinkListL）
{LinkListp;
p=L->next;
while（p）
{printf（"%d",p->data）;
p=p->next;}
printf（"\n"）;}
intLength（LinkListL,inti）
{i=0;
LinkListp=L->next;
while（p）
{++i;
p=p->next;}
returni;
}
voidchange（LinkListL）
{inti,j=1;
ElemTypek;
ElemTypee,m;
LinkListp=L->next;
printf（"请输入要修改的元素位置:
\n"）;
scanf（"%d",&i）;
GetElem（L,i,e）;
printf（"该位置的元素:
%d\n",e）;
printf（"修改后的元素值:
\n"）;
scanf（"%d",&k）;
while（p&&j{p=p->next;
++j;}
m=p->data;
p->data=k;
printf（"修改后的单链表显示如下:
\n"）;
show（L）;
}
voidCreateList（LinkList&L,intn）
{LinkListp;
L=newLNode;
L->next=NULL;
LinkListq=L;
for（inti=1;i<=n;i++）
{p=newLNode;
scanf（"%d",&p->data）;
p->next=NULL;
q->next=p;
q=p;}
}
StatusGetElem（LinkListL,inti,ElemType&e）
{LinkListp=L->next;
intj=1;
while（p&&j{p=p->next;
++j;}
if（!
p||j>i）returnerror;
e=p->data;
returnok;
}
StatusLinkInsert（LinkList&L,inti,ElemTypee）
{LinkListp=L;
intj=0;
while（p&&j{p=p->next;
++j;}
if（!
p||j>i-1）
returnerror;
LinkLists=newLNode;
s->data=e;
s->next=p->next;
p->next=s;
returnok;}
StatusListDelete（LinkList&L,inti,ElemType&e）
{LinkListp=L;
LinkListq;
intj=0;
while（p->next&&j{
p=p->next;
++j;}
if（!
（p->next）||j>i-1）returnerror;
q=p->next;
p->next=q->next;
e=q->data;
free（q）;
returnok;
}
voidmain（）
{ints;
inta;
ElemTypey;
LinkListlist;
for（;;）
{printf（"单链表操作\n"）;
printf（"1.创建\n"）;
printf（"2.显示\n"）;
printf（"3.表的长度\n"）;
printf（"4.查找\n"）;
printf（"5.修改\n"）;
printf（"6.插入\n"）;
printf（"7.删除\n"）;
printf（"8.结束\n"）;
printf（"请选择:
"）;
scanf（"%d",&s）;
switch（s）
{case1:
printf（"请输入单链表的长度:
\n"）;
scanf（"%d",&a）;
printf（"请输入%d个元素\n",a）;
CreateList（list,a）;
break;
case2:
printf（"该单链表为:
\n"）;
show（list）;
break;
case3:
//ints;
printf（"单链表的长度为:
%d\n",Length（list,s））;
break;
case4:
printf（"请选择所要取出元素的位置:
\n"）;
scanf（"%d",&x）;
while（a<0||a>Length（list,s））
{printf（"输入有误，请重新输入\n"）;
printf（"请选择所要取出元素的位置:
\n"）;
scanf（"%d",&a）;
}
GetElem（list,a,y）;
printf（"该位置的元素为%d:
\n",y）;
break;
case5:
change（list）;break;
case6:
printf（"请选择要插入的位置:
"）;
scanf（"%d",&a）;
while（a<0||a>Length（list,s））
{printf（"输入有误，请重新输入"）;
printf（"请选择所要插入元素的位置:
"）;
scanf（"%d",&a）;
}
printf（"要插入的元素值:
"）;
scanf（"%d",&y）;
LinkInsert（list,a,y）;
printf（"插入后的单链表:
\n"）;
show（list）;
break;
case7:
printf（"请选择要删除的元素位置（0",Length（list,s））;
scanf（"%d",&a）;
while（a<0||a>Length（list,s））
{printf（"输入有误，请重新输入"）;
printf（"请选择所要删除元素的位置（0",Length（list,s））;
scanf（"%d",&a）;
}
ListDelete（list,a,y）;
printf（"要删除的元素值:
%d",y）;
printf（"删除后的单链表:
\n"）;
show（list）;
break;
case8:
exit（0）;
break;
default:
printf（"输入有误，请重新输入"）;
break;
}
}
}
六、实验截图
（1）顺序表：
a）创建新链表：
b）插入数据：
3．删除数据：
4.查找数据：
（2）单链表：
初始化：
1.创建单链表：
2.显示单链表：
3.表长：
4.查找：
5.修改：
6.插入：
7.删除：
七、实验心得
1.通过这次实验让我充分了解了以前虽然学过但其实还不是很理解的顺序表和单链表的一些具体操作和原理。
2.在实际操作中，会出现很多问题，从这些问题中会反映出一大堆自己本身所存在的不足，让我认识到自己在编程中会经常出现的错误，下定决心在以后中不犯这种在别人看来是低级的错误
3.要学会经常拿别人的程序进行比较，看看谁的相对较好一些，学习一些别人程序中的亮点以及反思自己为什么没有做到
升级会员 