湘潭大学数据结构实验1实验报告源代码线性表基本操作课案.docx
《湘潭大学数据结构实验1实验报告源代码线性表基本操作课案.docx》由会员分享，可在线阅读，更多相关《湘潭大学数据结构实验1实验报告源代码线性表基本操作课案.docx（20页珍藏版）》请在冰点文库上搜索。
湘潭大学数据结构实验1实验报告源代码线性表基本操作课案
“数据结构和算法II”课程实验报告
实验名称：
线性表的存储结构定义及基本操作
班级姓名学号实验日期：
实验机时：
2学时实验成绩：
-------------------------------------------------------------------------------
一.实验目的：
1.掌握线性表的逻辑特征
2.掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算
3.熟练掌握线性表的链式存储结构定义及基本操作
4.理解循环链表和双链表的特点和基本运算
5.加深对栈结构的理解，培养解决实际问题的编程能力。
6.加深对顺序存储数据结构的理解和链式存储数据结构的理解，逐步培养解决实际问题的编程能力
二.实验内容：
（1）基本实验内容：
建立顺序表，完成顺序表的基本操作：
初始化、插入、删除、逆转、输出、销毁,置空表、求表长、查找元素、判线性表是否为空；
建立单链表，完成链表（带表头结点）的基本操作：
建立链表、插入、删除、查找、输出；其它基本操作还有销毁链表、将链表置为空表、求链表的长度、获取某位置结点的内容、搜索结点。
（2）扩展实验内容：
查前驱元素、查后继元素、顺序表合并，两个有序单链表的合并操作等。
三.程序及注释：
1.顺序表：
#include
#include
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineOVERFLOW-2
#defineLIST_INIT_SIZE100
#defineLISTINCREMENT10
typedefintstatus;
typedefintElemType;
typedefstruct{
ElemType*elem;
intlength,listsize;}SqList;
statusInitList（SqList&L）//初始化
{L.elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType））;
if（!
L.elem）exit（OVERFLOW）;
L.listsize=LIST_INIT_SIZE;
L.length=0;
returnOK;}
statusBuild（SqList&L）//建立表
{inti,n;
printf（"请输入元素个数n和n个元素\n"）;
scanf（"%d",&n）;
if（n>LIST_INIT_SIZE）//如果n大于当前空间
{L.elem=（ElemType*）realloc（L.elem,（n+LISTINCREMENT）*sizeof（ElemType））;
if（!
L.elem）exit（OVERFLOW）;
L.listsize=n+LISTINCREMENT;}
for（i=0;iscanf（"%d",L.elem+i）;
L.length=n;
returnOK;}
voidPrint（SqList&L）//输出表中元素和长度
{inti;
for（i=0;iprintf（"%d",*（L.elem+i））;
printf（"\n长度为:
%d\n\n",L.length）;}
voidTips（）//提示函数
{printf（"请选择你的想要的操作：
\n"）;
printf（"<1>输出顺序表及顺序表的长度\n"）;
printf（"<2>删除值为x的结点\n"）;
printf（"<3>删除给定位置i的结点\n"）;
printf（"<4>将顺序表逆置\n"）;
printf（"<5>将顺序表按升序排序\n"）;
printf（"<6>将x插入到顺序表的适当位置上\n"）;
printf（"<7>将两个有序表合并\n"）;
printf（"<0>退出\n\n"）;}
statusListDelete1（SqList&L,intx）//删除值为X的元素
{inti;
for（i=0;iif（*（L.elem+i）==x）
break;
if（i==L.length）
returnERROR;
for（i++;i*（L.elem+i-1）=*（L.elem+i）;
L.length--;
returnOK;}
statusListDelete2（SqList&L,intx）//删除第X个元素
{inti;
if（x<0||x>=L.length）
returnERROR;
for（i=x+1;i*（L.elem+i-1）=*（L.elem+i）;
L.length--;
returnOK;}
voidInverse（SqList&L）//逆置函数
{inti,t;
for（i=0;i{t=*（L.elem+i）;
*（L.elem+i）=*（L.elem+L.length-i-1）;
*（L.elem+L.length-i-1）=t;}}
voidSort（SqList&L）//冒泡排序（升序）
{inti,j,t;
for（i=1;ifor（j=0;j{if（*（L.elem+j）>*（L.elem+j+1））
{t=*（L.elem+j）;
*（L.elem+j）=*（L.elem+j+1）;
*（L.elem+j+1）=t;}}
printf（"已按升序排列\n\n"）;}
statusListInsert（SqList&L,intx）//将X插入，使仍然有序
{inti,k;
if（L.length>=L.listsize）
{L.elem=（ElemType*）realloc（L.elem,（L.listsize+LISTINCREMENT）*sizeof（ElemType））;
if（!
L.elem）exit（OVERFLOW）;
L.listsize+=LISTINCREMENT;}
for（i=0;iif（x<*（L.elem+i））
break;
k=i;
for（i=L.length;i>k;i--）
*（L.elem+i）=*（L.elem+i-1）;
*（L.elem+k）=x;
L.length++;
returnOK;}
statusMerger（SqList&L,SqList&Lb）//合并两个线性表
{inti,j,k;
SqListLc;
InitList（Lc）;
if（Lc.listsize{Lc.elem=（ElemType*）realloc（Lc.elem,（L.length+Lb.length+LISTINCREMENT）*sizeof（ElemType））;
if（!
L.elem）exit（OVERFLOW）;
Lc.listsize=L.length+Lb.length+LISTINCREMENT;}
i=j=k=0;
while（i{if（*（L.elem+i）<*（Lb.elem+j））
{*（Lc.elem+k）=*（L.elem+i）;
k++;i++;}
else
{*（Lc.elem+k）=*（Lb.elem+j）;
k++;j++;}}
while（i{*（Lc.elem+k）=*（L.elem+i）;
k++;i++;}
while（j{*（Lc.elem+k）=*（Lb.elem+j）;
k++;j++;}
Lc.length=L.length+Lb.length;
L=Lc;
returnOK;}
intmain（）
{intop,x,flag;
SqListL,Lb;
InitList（L）;
Build（L）;
Tips（）;
scanf（"%d",&op）;
while（op）
{switch（op）
{case1:
Print（L）;
break;
case2:
printf（"请输入要删除的数据X:
\n"）;
scanf（"%d",&x）;
flag=ListDelete1（L,x）;
if（flag）
printf（"删除成功!
!
\n\n"）;
else
printf（"元素不存在,删除失败!
!
\n\n"）;
break;
case3:
printf（"请输入要删除的位置i:
\n"）;
scanf（"%d",&x）;
flag=ListDelete2（L,x-1）;//第i个元素对应的下标为i-1
if（flag）
printf（"删除成功!
!
\n\n"）;
else
printf（"元素不存在,删除失败!
!
\n\n"）;
break;
case4:
Inverse（L）;
break;
case5:
Sort（L）;
break;
case6:
printf（"请输入要插入的数据X:
\n"）;
scanf（"%d",&x）;
flag=ListInsert（L,x）;
if（flag）
printf（"插入成功!
!
\n\n"）;
else
printf（"插入失败!
!
\n\n"）;
break;
case7:
printf（"请输入Lb的内容:
\n"）;
InitList（Lb）;
Build（Lb）;
flag=Merger（L,Lb）;
if（flag）
printf（"合并成功!
!
\n\n"）;
break;}
Tips（）;
scanf（"%d",&op）;}
return0;}
2.单链表
typedefintElementType;
#ifndef_List_H
#define_List_H
structNode;
typedefstructNode*PtrToNode;
typedefPtrToNodeList;
typedefPtrToNodePosition;
ListMakeEmpty（ListL）;
intIsEmpty（ListL）;
intIsLast（PositionP,ListL）;
PositionFind（ElementTypeX,ListL）;
voidDelete（ElementTypeX,ListL）;
PositionFindPrevious（ElementTypeX,ListL）;
voidInsert（ElementTypeX,ListL,PositionP）;
voidDeleteList（ListL）;
PositionHeader（ListL）;
PositionFirst（ListL）;
PositionAdvance（PositionP）;
ElementTypeRetrieve（PositionP）;
#endif
#include
#include
#defineError（Str）FatalError（Str）
#defineFatalError（Str）fprintf（stderr,"%s\n",Str）,exit
（1）
structNode
{ElementTypeElement;
PositionNext;};
ListMakeEmpty（ListL）//创建空链表
{if（L!
=NULL）
DeleteList（L）;
L=malloc（sizeof（structNode））;
if（L==NULL）
FatalError（"Outofmemory!
"）;
L->Next=NULL;
returnL;}
intIsEmpty（ListL）//判断链表是否为空
{returnL->Next==NULL;}
intIsLast（PositionP,ListL）
{returnP->Next==NULL;}
PositionFind（ElementTypeX,ListL）//精确查找函数
{PositionP;
intn=1;
P=L->Next;
while（P!
=NULL&&P->Element!
=X）
{P=P->Next;n++;}
if（P==NULL）
printf（"查找的成员不存在！
！
\n\n"）;
else
printf（"查找的成员位于链表第%d位\n\n",n）;}
voidDelete（ElementTypeX,ListL）//精确删除函数
{PositionP,TmpCell;
P=FindPrevious（X,L）;
if（!
IsLast（P,L））
{TmpCell=P->Next;
P->Next=TmpCell->Next;
free（TmpCell）;}}
PositionFindPrevious（ElementTypeX,ListL）//前驱查找函数
{PositionP;
P=L;
while（P->Next!
=NULL&&P->Next->Element!
=X）
P=P->Next;
returnP;}
voidInsert（ElementTypeX,ListL,PositionP）//元素插入函数
{PositionTmpCell;
TmpCell=malloc（sizeof（structNode））;
if（TmpCell==NULL）
FatalError（"Outofspace!
!
!
"）;
TmpCell->Element=X;
TmpCell->Next=P->Next;
P->Next=TmpCell;}
voidDeleteList（ListL）//清空链表函数
{PositionP,Tmp;
P=L->Next;
L->Next=NULL;
while（P!
=NULL）
{Tmp=P->Next;
free（P）;
P=Tmp;}
if（IsEmpty（L））
printf（"链表清空成功！
\n\n"）;}
PositionHeader（ListL）//表头调用函数
{returnL;}
PositionFirst（ListL）//首元素调用函数
{returnL->Next;}
PositionAdvance（PositionP）//元素递进函数
{returnP->Next;}
voidshow（ListL）//显示链表函数
{if（!
IsEmpty（L））
{Positionp;
p=First（L）;
printf（"当前链表成员如下：
\n"）;
while（p!
=NULL）
{printf（"%d",p->Element）;
if（Advance（p））
p=Advance（p）;
else
{printf（"\n\n"）;break;}}}
else
printf（"当前链表为空！
！
\n\n"）;}
voidjoin（ListL）//插入函数调用函数
{intx,n,i;
Positionp=Header（L）;
printf（"请输入需要插入的成员：
\n"）;
scanf（"%d",&x）;
printf（"需要将成员插入到第几位呢？
\n"）;
scanf（"%d",&n）;
for（i=1;i{p=p->Next;}
Insert（x,L,p）;
show（L）;}
voidfind（ListL）//查找函数调用函数
{printf（"请输入需要查找的成员：
\n"）;
intx;
scanf（"%d",&x）;
Find（x,L）;}
voidcount（ListL）//链表长度统计函数
{Positionp;
p=First（L）;
intn=0;
while（p!
=NULL）
{n++;
if（Advance（p））
p=Advance（p）;
else
break;}
printf（"当前链表长度为：
%d\n\n",n）;}
voiddirection（ListL）//位置访问函数
{intn,i;
Positionp=Header（L）;
printf（"请输入n的值：
\n"）;
scanf（"%d",&n）;
for（i=0;i{p=p->Next;}
printf（"第%d位成员为：
%d\n\n",n,p->Element）;}
voidchange（ListL）//修改元素函数
{printf（"请输入n的值：
\n"）;
intx,n,i;
scanf（"%d",&n）;
printf（"请输入修改后的值：
\n"）;
scanf（"%d",&x）;
Positionp=Header（L）;
for（i=0;i{p=p->Next;}
p->Element=x;
show（L）;}
voiddeletion（ListL）//删除函数调用函数
{printf（"你要删除的成员是：
\n"）;
intx;
scanf（"%d",&x）;
Delete（x,L）;
show（L）;}
voidmain（）
{ListL;
L=MakeEmpty（NULL）;
printf（"请输入需要插入的成员个数：
\n"）;
intn;
scanf（"%d",&n）;
printf（"请输入需要插入的成员以空格隔开：
\n"）;
inti;
Positionp;
p=Header（L）;
for（i=0;i{intx;
scanf（"%d",&x）;
Insert（x,L,p）;
p=Advance（p）;}
show（L）;
printf（"请选择需要进行的操作：
\n1.计算链表长度\n2.取第n个位置成员\n3.修改第n个位置成员\n4.在第n位插入新成员\n5.删除成员\n6.搜索成员\n7.销毁链表\n8.退出\n你输入的选项是：
"）;
scanf（"%d",&n）;
while（n!
=8）
{switch（n）
{case1:
count（L）;break;
case2:
direction（L）;break;
case3:
change（L）;break;
case4:
join（L）;break;
case5:
deletion（L）;break;
case6:
find（L）;break;
case7:
DeleteList（L）;break;}
printf（"请选择需要进行的操作：
\n1.计算链表长度\n2.取第n个位置成员\n3.修改第n个位置成员\n4.在第n位插入新成员\n5.删除成员\n6.搜索成员\n7.销毁链表\n8.退出\n你输入的选项是：
"）;
scanf（"%d",&n）;}}
四.运行结果：
1.顺序表：
3.单链表：
五.实验心得：
通过这次写实验报告，我深切的理解了这门课的本质。
刚开始学这门课时，当时还不清楚这门课程的目的，现在，我真正的理解了：
数据结构像是身体的骨骼，而C是填充这骨骼的肉体，二者相结合才能使整个程序更加完整，健全。
数据结构是个框架，模型，抽象数据类型中列举了各种操作，而所用的C语言，将各种操作描述出来构成算法。
数据结构+算法=程序设计。
这次的实验报告，让我受益匪浅，不仅有知识方面的，还有生活和精神上的。
总之，我会继续我的兴趣编程，相信在编程的过程中，能不断的提高自己。
升级会员 