线性表的顺序表示与链式表示讲解.docx
《线性表的顺序表示与链式表示讲解.docx》由会员分享，可在线阅读，更多相关《线性表的顺序表示与链式表示讲解.docx（28页珍藏版）》请在冰点文库上搜索。
线性表的顺序表示与链式表示讲解
数据结构课程实验报告
课程名称
数据结构实验
班级
实验日期
2014.4.2
姓名
学号
实验成绩
实验名称
线性表的顺序表示与链式表示
实验目的及要求
【实验目的】
1.加深理解线性表的顺序表示与链式表示的意义和区别，掌握用它们表示时各基本操作的设计与实现。
2.学会定义线性表的顺序存储类型和链式存储类型，实现C程序的
基本结构，对线性表的一些基本操作和具体的函数定义。
3.掌握线性表的基本操作（初始化、建立、插入、删除、遍历等）。
4.掌握对多函数程序的输入、编辑、调试和运行过程。
5.进一步熟练C语言的使用，特别是指针和链表的使用。
6.能在实际应用背景下恰当选择顺序存储和链式存储。
【实验要求】
1.预习C语言中的结构的定义和基本操作方法
2.对线性表的每个基本操作用单独的函数实现
3.编写完整程序完成下面的实验内容并上机运行
4.整理并上交实验报告
实验环境
硬件平台：
普通PC机
软件平台：
Windows操作系统
编程环境：
VC6.0
实验内容
1.分别建立包含10个数据元素的顺序线性表和链式线性表；
2.从键盘输入一个数据元素和插入位置k,将元素插入到线性表中
第k（包含0号位置）个位置；
3.从键盘输入一个数据元素关键字或位置k（包含1号位置），从线性表中删除相应数据元素；
4.能完成查找功能；
给出程序及插入、删除前和插入、删除后线性表结果。
算法描述及实验步骤
//创建顺式线性表
structnumber*creat（void）
{
structnumber*head,*p1;
p1=head=（structnumber*）malloc（SIZE*sizeof（structnumber））;scanf（"%ld",&p1->num）;
for（;p1->num!
=0;L++）
{
p1++;
seanf（"%ld",&p1->num）;
}return（head）;
}
//输出顺式线性表中的元素
voidprint（structnumber*head）
{
structnumber*p;
ints=L;
p=head;
if（p!
=0）
{
printf（"\n您输入的数据为：
\n"）;
for（;s>0;p++,s--）
printf（"%ld",p->num）;
}
}
//查找顺式线性表中的元素
voidsearch（structnumber*head）
{
structnumber*p;
longnum1;
intn=0,s=0;
p=head;
printf（"\n请输入您要查找的数据：
\n"）;
scanf（"%ld",&num1）;
if（head!
=0）
for（;p->num!
=0;p++）
{
n++;
if（p->num==num1）
{
s=1;
break;
}
}
if（s==O）
printf（"\n没有您所要查找的数据\n"）;
else
printf（"\n找到您所需数据'%ld'在表中第％d（\n",numl,n）;
}
//插入顺式线性表的元素
structnumber*insert（structnumber*head）
{
structnumber*p1,*p2;
intn=1;
longnum1;
p1=p2=head;
p2=p2+L-1;
printf（"\n请输入您要插入的数据：
\n"）;
scanf（"%ld",&num1）;
if（num1num）
{
for（p1=head;p1->numn++;
for（;p2>=p1;p2--）
（p2+1）->num=p2->num;
}
（p2+1）->num=num1;
L++;
return（head）;
}
//删除顺式线性表的元素
structnumber*del（structnumber*head）
{
structnumber*p1,*p2;
longnum1;
intn=1;
p仁p2=head;
printf（"\n请输入要删除的数据：
\n"）;
scanf（"%ld",&num1）;
p2=p2+L-1;
for（;p1->num!
=num1&&n<=L;p1++）
n=n+1;
if（n>L）
{
printf（"\n没有您要删除的数据\n"）;
return（O）;
}
else
{
for（;p1<=p2;p1++）
p1->num=（p1+1）_>num;
L--;
return（head）;
}
}
structlist*creat_n（）//创建有n个元素的链表
{
structlist*q,*p,*head=NULL;
printf（"\n输入你所要创建的结点数
scanf（"%d",&length）;
head=p=（list*）malloc（sizeof（list））;//向它
printf（"输入该结点的值:
"）;
scanf（"%d",&p->data）;
p->next=NULL;
for（inti=length-1;i>=1;i--）
{
q=p;
p=（list*）malloc（sizeof（list））;//
printf（"输入该结点的值:
"）;
:
"）;
创建一个新结点并用头指针指
创建新结点
scanf（"%d",&p->data）;
q_>next=p;
}
printf（"输入完毕\n\n"）;
p->next=NULL;
returnhead;
}
structlist*output。
//输出表长与结点值函数
{
structlist*p;
p=head;
printf（"\n当前链表中存有的兀素:
\n"）;
while（p!
=NULL）
{
printf（"%d\n",p->data）;
p=p->next;
}
printf（"当前的表长是：
%d\n\n",length）;//输出当前表长
returnhead;
}
voidinsert（）//插入结点函数
{
structlist*k,*p,*q;
intx;
printf（"请输入你要在哪个结点值之前插入新结点:
"）;
scanf（"%d",&x）;
k=（list*）malloc（sizeof（list））;〃创建新结点
printf（"请输入新结点的值：
”）；
scanf（"%d",&k->data）;
k->next=NULL;
if（head==NULL）〃若链表为空，则直接入链表
{
head=k;
length=length+1;
printf（”插入成功\n\n"）;
}
elseif（head->data--x）//在第一个结点前插入新结点
{
k->next-head;
head-k;
printf（"插入成功\n\n”）;
length-length+1;
}
else
{
q-head;
p-head->next;
while（（p!
-NULL）&&（p->data!
-x））//找出值为X的结点的位置
{
q-p;
p-p_>next;
}
if（p--NULL）
{
q->next-k;〃在链表末插入新结点
printf（"插入成功\n”）;
length-length+1;
}
elseif（p->data--x）//在要求的X结点前插入新结点
{
k_>next-p;
q_>next-k;
printf（"插入成功\n\n"）;
length=length+1;
}
}
output。
；
}
intdelet（）〃删除结点函数
{
structlist*q,*p;
intx,y;
printf（”请输入你所要删除的结点值:
"）;
scanf（"%d"，&x）;
if（head==NULL）〃表空
{
printf（"表空\n"）;
return0;
}
elseif（x--head->data）〃第一个结点为删除的结点
{
q-head;
head-head->next;
y-q->data;
free（q）;
printf（"删除成功\n\n"）;
length-length-1;
output（）;
return（y）;
}
else
{
q=head;
p=head->next;
while（（p!
=NULL）&&（p->data!
=x））〃找出值为X的结点
{
q=p;
p=p->next;
}
if（p==NULL）
{
printf（”没有删除对象\n"）;
}
if（x==p->data）〃删除值为X的结点
{
q_>next=p->next;
y=p->data;
free（p）;
printf（"删除成功\n\n"）;
length=length-1;
output。
；
return（y）;
}
else
{
printf（"表中没有指定的结点\n"）;
output（）;
return0;
}
}
return0;
}
voidfind（）
{
structlist*p;
intk,x,i=1;
chary,n;
LOOP:
p=head;
printf（”请输入你要查找的结点值：
”）；
scanf（"%d"，&x）;
while（p->data!
=x）
{
p=p->next;
i++;
}
printf（"你所查找的结点是表中第%d个结点!
\n\n",i）;
printf（"是否要继续查找，请输入y/n\n\n"）;
k=getch（）;
if（k=='y'）
{
i=1;
gotoLOOP;
}
else
return;
}
调试过程及实验结果
T占袖空*rs報结一专人我％丄
二
--1S345H
MH耳事MKKMKMM?
CMMMMMHJfKMMKMfCM
1
请也.建I帧序義注365787S60
堆淫轲L请骑、号则谙林退曲
2
情谕入您更话凡的数播，
5
继煤抛作悸俞人.否则晡辭出；
5
您槿入的数踞为’
231G5VU?
^G
继績操作请输人•否则请痢退出|
请包建I慎序表胡^RF；＜»ft7S6F1
继续提作谓输人，否対倩按》退出I
2
请牯扎您要超人的魏际
5
维续操作请辅人”否则谙■按0退出：
E
您梅人的数据为*
继絃操作请鐵人.否则请按《迟討
-KfIL]生I-LI
^q^^^l
的时善A点点点朋结结给垢』甲AAA入入JAlA-”lb-l;EI「■V自n削―.削」削「EI-+」.■l!
*hl,J+.-r+--r"
■■S;S-I;
■''C\U?
er?
\AdnirwstrfftoADe&kfc）p\JfSXf^\Cfebu^\Cppl#w'
j-】一京口点i点
一
--12345-W--
4^
12345
我理解到线性表的顺序表示和链式表示方法实际存
通过此次试验,
在相当明显的区别，顺序结构的表示方法建立在已存在的固定的空间
区域内，数据超过最大存储空间就会溢出并丢失，无法实现添加或删除操作，线性表可以随机存取表中任意一元素，但在插入或删除操作时需要移动大量元素，但表示方式精简、易操作；而链式结构的表示
方法虽然不如顺序结构简单，却能动态分配存储空间，可以对数据进行添加、删除和修改等操作，功能更为强大，可以提高存储效率。
此外，还熟练掌握了线性表的基本操作一一初始化、建立、插入、删除、遍历等。
掌握了对多函数程序的输入、编辑、调试和运行过程，进一步熟练了指针和链表的使用。
#include#include#defineSIZE100intL=0;
structnumber
{
longnum;};
〃创建顺式线性表structnumber*crea
{
structnumber*head,*p1;
p1=head=（structnumber*）malloc（SIZE*sizeof（structnumber））;
scanf（"%ld",&p1->num）;
for（;p1->num!
=0;L++）
{
p1++;
scanf（"%ld",&p1->num）;
}
return（head）;
}
〃输出顺式线性表中的元素
voidprint（structnumber*head）
{
structnumber*p;
ints=L;
p=head;
if（p!
=0）
{
printf（"\n您输入的数据为：
\n"）;for（;s>0;p++,s--）
printf（"%ld",p->num）;
}
}
〃查找顺式线性表中的元素
voidsearch（structnumber*head）
{
structnumber*p;
longnum1;
intn=0,s=0;
p=head;
printf（"\n请输入您要查找的数据：
\n"）;
scanf（"%ld",&num1）;
if（head!
=0）
for（;p->num!
=0;p++）
{
n++;
if（p->num==num1）
{
s=1;
break;
}
}
if（s==O）
printf（"\n没有您所要查找的数据\n"）;else
printf（"\n找到您所需数据'%ld'在表中第%d个\n",numl,n）;
}
〃插入顺式线性表的元素
structnumber*insert（structnumber*head）
{
structnumber*p1,*p2;
intn=1;
longnum1;
p1=p2=head;
p2=p2+L-1;
printf（"\n请输入您要插入的数据：
\n"）;scanf（"%ld",&num1）;
if（num1num）
{
for（p1=head;p1->numn++;
for（;p2>=p1;p2--）
（p2+1）->num=p2->num;
}
（p2+1）->num=num1;
L++;
return（head）;
}
〃删除顺式线性表的元素
structnumber*del（structnumber*head）
{
structnumber*p1,*p2;
longnum1;
intn=1;
p1=p2=head;
printf（"\n请输入要删除的数据：
\n"）;
scanf（"%ld",&num1）;
p2=p2+L-1;
for（;p1->num!
=num1&&n<=L;p1++）
n=n+1;
if（n>l）
printf（"\n没有您要删除的数据\n"）;return（O）;
}
else
{for（;p1<=p2;p1++）
p1->num=（p1+1）->num;
L--;
return（head）;
}
}
voidmain（）
{
structnumber*head,*head1,*head2;inta;
壬（、'\hk*********************************
printf（"
*****************\n"）;
printf（"
**1
创建链表
**\n"）;
printf（"
**2
插入节点
**\n"）;
printf（"
**3
查找数据
**\n"）;
printf（"
**4
删除结点
**\n"）;
printf（"
**5
输出**\n"）;
printf（"
**o
退出**\n"）;
printf（"
*****************\n"）;
**\n"）;
/*head=creat（）;print（head）;*/
printf（'
************************************
**\n"）;
scanf（"%d",&a）;
while（a!
=0）{
switch（a）
{
case1:
printf（"请创建顺序表:
"）;head=creat（）;break;
case2:
head1=insert（head）;break;
case3:
search（head）;break;
case4:
head2=del（head）;break;
case5:
print（head）;
case0:
break;
}
printf（"\n继续操作请输入，否则请按0退出：
\n"）:
scanf（"%d",&a）;
}
}
#include
#include
#includevconio.h>
structlist//结点类型
{intdata;
structlist*next;
};
structlist*head;〃声明结点指针
intstaticlength;〃声明表长变量
structlist*creat_n（）〃创建有n个元素的链表
{
structlist*q,*p,*head=NULL;
printf（"\n输入你所要创建的结点数:
"）;scanf（"%d",&length）;
head=p=（list*）malloc（sizeof（list））;//创建一个新结点并用头指针指向它
printf（"输入该结点的值:
"）;
scanf（"%d",&p->data）;
p->next=NULL;
for（inti=length-1;i>=1;i--）
{
q=p;
p=（list*）malloc（sizeof（list））;//创建新结点
printf（"输入该结点的值:
"）;
scanf（"%d",&p->data）;
q->next=p;
}
printf（"输入完毕\n\n"）;p->next=NULL;
returnhead;
}
structlist*output（）〃输出表长与结点值函数
{
structlist*p;
p=head;
printf（"\n当前链表中存有的兀素:
\n"）;
while（p!
=NULL）
{
printf（"%d\n",p->data）;
p=p->next;
}
printf（"当前的表长是:
%d\n\n",length）;//输出当前表长returnhead;
}
voidinsert（）//插入结点函数
{
structlist*k,*p,*q;
intx;
printf（"请输入你要在哪个结点值之前插入新结点：
"）；
scanf（"%d",&x）;
k=（list*）malloc（sizeof（list））;〃创建新结点
printf（"请输入新结点的值:
"）;
scanf（"%d",&k->data）;
k->next=NULL;
if（head--NULL）//若链表为空，则直接入链表
{
head=k;
length=length+1;
printf（"插入成功\n\n"）;
}
elseif（head->data==x）//在第一个结点前插入新结点
{
k->next=head;
head=k;
printf（"插入成功\n\n"）;
length=length+1;
}
else
{
q=head;p=head->next;
while（（p!
=NULL）&&（p->data!
=x））〃找出值为X的结点的位置{
q=p;
p=p->next;
}
if（p==NULL）
{
q->next=k;〃在链表末插入新结点
printf（"插入成功\n"）;
length=length+1;
}
elseif（p->data==x）//在要求的X结点前插入新结点
{
k->next=p;
q->next=k;
printf（"插入成功\n\n"）;
length=length+1;
}
}
output（）;
}
intdelet（）〃删除结点函数
{
structlist*q,*p;
intx,y;
printf（"请输入你所要删除的结点值:
"）;
seanf（"%d",&x）;
if（head==NULL）〃表空
{
printf（"表空\n"）;
return0;
}
elseif（x==head->data）〃第一个结点为删除的结点{
q=head;
head=head->next;
y=q->data;
free（q）;
printf（"删除成功\n\n"）;
length=length-1;output（）;
return（y）;
}
else
{
q=head;
p=head->next;
while（（p!
=NULL）&&（p->data!
=x））〃找出值为X的结点
{
q=p;
p=p->next;
}
if（p==NULL）
{
printf（"没有删除对象\n"）;
}
if（x==p->data）〃删除值为X的结点
{
q->next=p->next;
y=p->data;
free（p）;
printf（"删除成功\n\n"）;
length=length-1;
output（）;
return（y）;
}
else
{
printf（"表中没有指定的结点\n"）;
output（）;
return
升级会员 