上机实验报告一.docx

上机实验报告一.docx

《上机实验报告一.docx》由会员分享，可在线阅读，更多相关《上机实验报告一.docx（10页珍藏版）》请在冰点文库上搜索。

上机实验报告一

“数据结构和算法II”课程实验报告

实验名称：

线性表的存储结构定义及基本操作

班级_材料物理姓名孙耀景学号2013700819实验日期：

实验机时：

2学时实验成绩：

-------------------------------------------------------------------------------

一.实验目的：

1、掌握线性表的逻辑特征

2、掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算

3、熟练掌握线性表的链式存储结构定义及基本操作

4、理解循环链表和双链表的特点和基本运算

5、加深对栈结构的理解，培养解决实际问题的编程能力。

6、加深对顺序存储数据结构的理解和链式存储数据结构的理解，

逐步培养解决实际问题的编程能力

二.实验内容：

1、建立顺序表，完成顺序表的基本操作：

初始化、插入、删除、逆转、输出、销毁,置空表、求表长、查找元素、判线性表是否为空；

2、建立单链表，完成链表（带表头结点）的基本操作：

建立链表、插入、删除、查找、输出；其它基本操作还有销毁链表、将链表置为空表、求链表的长度、获取某位置结点的内容、搜索结点；

三.程序及注释：

#include

#include

#include

#include

usingnamespacestd;

structdata{intdata1;

structdata*next;

};

structdata*CreatList（structdata*List,intcount）

{structdata*head,*p,*q;

for（inti=0;i

{

q=（structdata*）malloc（sizeof（structdata））;

cout<<"输入第"<

"<

cin>>q->data1;

if（i==0）p=head=q;

elsep->next=q;

q->next=0;

p=q;

}

returnhead;

}

voidmain（）

{intn;

cout<<"输入要添加的数据个数:

"<<"";

cin>>n;

cout<

structdata*List,*List_head,*in;

List=（structdata*）malloc（sizeof（structdata））;

List_head=（structdata*）malloc（sizeof（structdata））;

in=（structdata*）malloc（sizeof（structdata））;

List=CreatList（List,n）;

List_head=List;

cout<<"你输入的数据为:

";

for（inti=0;i

{

cout<<""<data1<<"";

List=List->next;

}

List=List_head;

intin1,in2;

charx;

cout<

do

{

cout<<"\n请输入要插入在的位置，首位置为1，尾位置为"<

"<

cin>>in1;

}while（in1<1||in1>n+1）;

cout<<"请输入要插入的数字：

"<

cin>>in2;

if（in1==1）{in->next=List;in->data1=in2;List_head=in;}

else

{

in->data1=in2;

for（inti=1;i

{List=List->next;

}

in->next=List->next;

List->next=in;

}

List=List_head;

cout<<"插入后的数据:

";

for（inti=0;i

{

cout<<""<data1<<"";

List=List->next;

}

List=List_head;

intde_n;

structdata*p,*q;

do{

cout<

cin>>de_n;}while（de_n<1||de_n>n+1）;

if（de_n==1）{List_head=List->next;free（List）;}

else

{

for（inti=1;i

{

List=List->next;

}

p=List;

List=List->next;

q=List;

p->next=q->next;

free（q）;

}

List=List_head;

cout<<"删除后的数据为：

"<

for（inti=0;i

{

cout<data1<<"";

List=List->next;

}

intfind;

charz;

cout<

"<<"";

restart:

List=List_head;

cin>>find;

for（inti=0;i

{

if（List->data1==find）{cout<

if（i==n-1）

{cout<

";

cin>>z;

if（z=='Y'||z=='y'）gotorestart;elseexit（0）;}

List=List->next;

}

system（"pause"）;

四.运行结果：

List=（23,45,100,5,98,73,88）

List=（23,45,5,98,73,88,）

该元素所在的位置为第六号

五.程序及注释

structLNode

{

ElemTypedata；

structLNode*next；

}；

typedefstructLNode*LinkList；/*另一种定义LinkList的方法*/

2．文件linklistAlgo.h是单链表的基本算法描述

/*以下的算法均是针对带表头结点的单链表*/

StatusListInit_Link（LinkList&L）

{/*操作结果：

构造一个空的线性表L*/

L=（LinkList）malloc（sizeof（structLNode））；/*产生头结点,并使L指向此头结点*/if（!

L）/*存储分配失败*/

exit（OVERFLOW）；

L->next=NULL；/*指针域为空*/

returnOK；

}

StatusListDestroy_Link（LinkListL）

{/*初始条件：

线性表L已存在。

*/

/*操作结果：

销毁线性表L*/

LinkListq；

while（L）

{

q=L->next；

free（L）；

L=q；

}

returnOK；

}

StatusListClear_Link（LinkListL）/*不改变L*/

{/*初始条件：

线性表L已存在。

*/

/*操作结果：

将L重置为空表*/

LinkListp,q；

p=L->next；/*p指向第一个结点*/

while（p）/*没到表尾*/

{

q=p->next；

free（p）；

p=q；

}

L->next=NULL；/*头结点指针域为空*/

returnOK；

}

StatusListEmpty_Link（LinkListL）

{/*初始条件：

线性表L已存在。

*/

/*操作结果：

若L为空表，则返回TRUE，否则返回FALSE*/

if（L->next）/*非空*/

returnFALSE；

else

returnTRUE；

}

intListLength_Link（LinkListL）

{/*初始条件：

线性表L已存在。

*/

/*操作结果：

返回L中数据元素个数*/

LinkListp=L->next；/*p指向第一个结点*/

while（p）/*没到表尾*/

{

i++；

p=p->next；

}

returni；

}

StatusGetElem_Link（LinkListL,inti,ElemType&e）/*算法2.8*/

{/*初始条件:

L为带头结点的单链表的头指针*/

/*操作结果：

当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR*/intj=1；/*j为计数器*/

LinkListp=L->next；/*p指向第一个结点*/

while（p&&j

{

p=p->next；

j++；

}

if（!

p||j>i）/*第i个元素不存在*/

returnERROR；

e=p->data；/*取第i个元素*/

returnOK；

}

intLocateElem_Link（LinkListL,ElemTypee,Status（*compare）（ElemType,ElemType））{/*初始条件:

线性表L已存在,compare（）是数据元素判定函数（满足为1,否则为0）*//*操作结果:

返回L中第1个与e满足关系compare（）的数据元素的位序。

*//*若这样的数据元素不存在,则返回值为0*/

inti=0；

LinkListp=L->next；

while（p）

{

i++；

if（compare（p->data,e））/*找到这样的数据元素*/

returni；

p=p->next；

}

return0；

}

StatusListInsert_Link（LinkListL,inti,ElemTypee）/*算法2.9,不改变L*/

{/*在带头结点的单链线性表L中第i个位置之前插入元素e*/

LinkListp=L,s；

while（p&&j

{

p=p->next；

j++；

}

if（!

p||j>i-1）/*i小于1或者大于表长*/

returnERROR；

s=（LinkList）malloc（sizeof（structLNode））；/*生成新结点*/

s->data=e；/*插入L中*/

s->next=p->next；

p->next=s；

returnOK；

}

StatusListDelete_Link（LinkListL,inti,ElemType&e）/*算法2.10,不改变L*/{/*在带头结点的单链线性表L中，删除第i个元素,并由e返回其值*/intj=0；

LinkListp=L,q；

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；

}

StatusListTraverse_Link（LinkListL）

{/*初始条件：

线性表L已存在*/

/*操作结果:

依次对L的每个数据元素的值进行输出*/

LinkListp=L->next；

while（p）

{

printf（"%d",p->data）；

p=p->next；

}

printf（"\n"）；

五.实验心得：

通过本次试验，我学会了顺序表的初始化、插入、删除、逆转、输出、销毁,置空表、求表长、查找元素、判线性表是否为空。

学会了建立单链表，完成链表（带表头结点）的基本操作：

建立链表、插入、删除、查找、输出；其它基本操作还有销毁链表、将链表置为空表、求链表的长度、获取某位置结点的内容、搜索结点；在实验的过程中遇到了困难，但通过努力和请教老师后成功解决了。