《数据结构》上机实验一资料.docx

《数据结构》上机实验一资料.docx

《《数据结构》上机实验一资料.docx》由会员分享，可在线阅读，更多相关《《数据结构》上机实验一资料.docx（20页珍藏版）》请在冰点文库上搜索。

《数据结构》上机实验一资料

青岛理工大学

数据结构课程实验报告

课程名称

数据结构

班级

软件131

实验日期

4.15

姓名

学号

实验成绩

实验名称

线性表的顺序表示与链式表示

实

验

目

的

及

要

求

实验目的

1.加深理解线性表的顺序表示与链式表示的意义和区别，掌握用它们表示时各基本操作的设计与实现。

2.学会定义线性表的顺序存储类型和链式存储类型，实现C程序的基本结构，对线性表的一些基本操作和具体的函数定义。

3.掌握线性表的基本操作（初始化、建立、插入、删除、遍历等）。

4.掌握对多函数程序的输入、编辑、调试和运行过程。

5.进一步熟练C语言的使用，特别是指针和链表的使用。

能在实际应用背景下恰当选择顺序存储和链式存储。

实验要求

1.预习C语言中的结构的定义和基本操作方法

2.对线性表的每个基本操作用单独的函数实现

3.编写完整程序完成下面的实验内容并上机运行

4.整理并上交实验报告

实

验

环

境

硬件平台：

普通的PC机

软件平台：

Windows2003操作系统

编程环境：

VisualC++

实

验

内

容

1.分别建立包含10个数据元素的顺序线性表和链式线性表；

2.从键盘输入一个数据元素和插入位置k，将元素插入到线性表中第k（包含0号位置）个位置；

3.从键盘输入一个数据元素关键字或位置k（包含1号位置），从线性表中删除相应数据元素；

4.能完成查找功能；

5.给出程序及插入、删除前和插入、删除后线性表结果。

算

法

描

述

及

实

验

步

骤

//创建顺式线性表

structnumber*creat（void）

{

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==0）

printf（"\n没有您所要查找的数据\n"）;

else

printf（"\n找到您所需数据'%ld'在表中第%d个\n",num1,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->num

n++;

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（0）;

}

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;

}

调

试

过

程

及

实

验

结

果

程序运行过程中输入了顺序表，结果输出结果符合情况，程序成功。

程序运行过程中输入了链表，结果输出结果符合情况，程序成功。

总

结

通过此次试验，我理解到线性表的顺序表示和链式表示方法实际存在相当明显的区别，顺序结构的表示方法建立在已存在的固定的空间区域内，数据超过最大存储空间就会溢出并丢失，无法实现添加或删除操作，线性表可以随机存取表中任意一元素，但在插入或删除操作时需要移动大量元素，但表示方式精简、易操作；而链式结构的表示方法虽然不如顺序结构简单，却能动态分配存储空间，可以对数据进行添加、删除和修改等操作，功能更为强大，可以提高存储效率。

附

录

#include

#include

#defineSIZE100

intL=0;

structnumber

{

longnum;

};

//创建顺式线性表

structnumber*creat（void）

{

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==0）

printf（"\n没有您所要查找的数据\n"）;

else

printf（"\n找到您所需数据'%ld'在表中第%d个\n",num1,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->num

n++;

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（0）;

}

else

{

for（;p1<=p2;p1++）

p1->num=（p1+1）->num;

L--;

return（head）;

}

}

voidmain（）

{

structnumber*head,*head1,*head2;

inta;

/*head=creat（）;

print（head）;*/

printf（"\n************************************\n"）;

printf（"*****************\n"）;

printf（"**1创建链表**\n"）;

printf（"**2插入节点**\n"）;

printf（"**3查找数据**\n"）;

printf（"**4删除结点**\n"）;

printf（"**5输出**\n"）;

printf（"**0退出**\n"）;

printf（"*****************\n"）;

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

#include

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（"请输入你所要删除的结点值:

"）;

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）