北京邮电大学 数据结构 实验一 带头结点的单链表构造.docx

北京邮电大学 数据结构 实验一 带头结点的单链表构造.docx

《北京邮电大学 数据结构 实验一 带头结点的单链表构造.docx》由会员分享，可在线阅读，更多相关《北京邮电大学 数据结构 实验一 带头结点的单链表构造.docx（26页珍藏版）》请在冰点文库上搜索。

北京邮电大学数据结构实验一带头结点的单链表构造

数据结构实验报告

实验名称：

实验1——单链表的构造

学生姓名：

XXXXNB

班级：

XXXX

班内序号：

学号：

XXXX

日期：

XXXXX

1．实验要求

根据线性表的抽象数据类型的定义，完成带头结点的单链表的基本功能。

单链表的基本功能：

1、构造：

使用头插法、尾插法两种方法

2、插入：

要求建立的链表按照关键字从小到大有序

3、删除

4、查找

5、获取链表长度

6、销毁

7、其他：

可自行定义

编写测试main（）函数测试线性表的正确性。

2.程序分

编程完成单链表的一般性功能如单链表的构造：

使用头插法、尾插法两种方法插入：

要求建立的链表按照关键字从小到大有序，删除，查找，获取链表长度，销毁

用《数据结构》中的相关思想结合C++语言基本知识编写一个单链表结构。

本程序为使用方便，几乎不用特殊的命令，只需按提示输入即可，适合更多的用户使用。

2.1存储结构

单链表的存储结构：

2.2关键算法分析

1.头插法

自然语言描述：

a.在堆中建立新结点

b.将a[i]写入到新结点的数据域

c.修改新结点的指针域

d.修改头结点的指针域,将新结点加入链表中

//在构建之初为了链表的美观性构造，进行了排序

代码描述：

//头插法构造函数

template

LinkList:

:

LinkList（Ta[],intn）

{

for（inti=n-1;i>=1;i--）//冒泡排序，对数组进行从小到大排序

{

for（intj=0;j

{

if（a[j]>a[j+1]）

{

Tt=a[j+1];

a[j+1]=a[j];

a[j]=t;

}

}

}

front=newNode;//为头指针申请堆空间

front->next=NULL;//构造空单链表

for（inti=n-1;i>=0;i--）

{

Node*s=newNode;//建立新结点

s->data=a[i];//将a[i]写入新结点的数据域

s->next=front->next;//修改新结点的指针域

front->next=s;//修改头结点的指针域，将新结点加入到链表中

}

}

2.尾插法

自然语言描述：

a.在堆中建立新结点

b.将a[i]写入到新结点的数据域

c.将新结点加入到链表中

d.修改修改尾指针

代码描述:

//尾插法构造函数

template

LinkList:

:

LinkList（Ta[],intn）

{

front=newNode;

Node*r=front;//命名一个新变量进行转换

for（inti=0;i

{

Node*s=newNode;

s->data=a[i];

r->next=s;

r=s;

}

r->next=NULL;

}

时间复杂度：

O（n）

3.析构函数

自然语言描述：

a.新建立一个指针，指向头结点

b.移动a中建立的指针

c.逐个释放指针

代码描述:

template

LinkList:

:

~LinkList（）//析构函数，销毁链表

{

Node*p=front;

while（p）

{

front=p;

p=p->next;

deletefront;

}

}

4.按位查找函数

自然语言描述:

a.初始化工作指针p和计数器j，p指向第一个结点，j=1

b.循环以下操作，直到p为空或者j等于1

b1：

p指向下一个结点

b2：

j加1

c.若p为空，说明第i个元素不存在，抛出异常

d.否则，说明p指向的元素就是所查找的元素，返回元素地址

代码描述:

template

Node*LinkList:

:

Get（inti）//按位查找

{

Node*p=front;

intj=0;

while（p）

{

if（j

{

p=p->next;

j++;

}

elsebreak;

}

if（!

p）throw"查找位置非法";

elsereturnp;

}

时间复杂度：

O（n）

5.按值查找函数

自然语言描述：

a.初始化工作指针p和计数器j，p指向第一个结点，j=1

b.循环以下操作，找到这个元素或者p指向最后一个结点

b1.判断p指向的结点是不是要查找的值，如果是，返回j;

b2.否则p指向下一个结点,并且j的值加一

c.如果找到最后一个结点还没有找到要查找的元素，返回查找失败信息代码描述:

template

intLinkList:

:

Locate（Tx）//按值查找

{

Node*p=front->next;

intj=1;

while（p）

{

if（p->data==x）returnj;

else

{

p=p->next;

j++;

}

}

return-1;

}

时间复杂度：

O（n）

6.插入函数

自然语言描述：

a.在堆中建立新结点

b.将要插入的结点的数据写入到新结点的数据域

c.修改新结点的指针域

d.修改前一个指针的指针域，使其指向新插入的结点的位置

代码描述:

template

voidLinkList:

:

Insert（inti,Tx）//插入函数

{

Node*p=Get（i-1）;

if（p）

{

Node*s=newNode;

s->data=x;

s->next=p->next;

p->next=s;

}

elsethrow"插入位置非法";

}

时间复杂度：

O（n）

7.按位删除函数

自然语言描述：

a.从第一个结点开始，查找要删除的位数i前一个位置i-1的结点

b.设q指向第i个元素

c.将q元素从链表中删除

d.保存q元素的数据

e.释放q元素

代码描述:

template

TLinkList:

:

Delete（inti）//删除函数

{

Node*p=Get（i-1）;

Node*q=p->next;

Tx=q->data;

p->next=q->next;

deleteq;

returnx;

}

8.遍历打印函数

自然语言描述:

a.判断该链表是否为空链表，如果是，报错

b.如果不是空链表，新建立一个temp指针

c.将temp指针指向头结点

d.打印temp指针的data域

e.逐个往后移动temp指针，直到temp指针的指向的指针的next域为空

代码描述:

template

voidLinkList:

:

PrintList（）//打印链表

{

Node*p=front->next;

while（p）

{

cout<data<<'';

p=p->next;

}

cout<

}

9.获取链表长度函数

自然语言描述：

a.判断该链表是否为空链表，如果是，输出长度0

b.如果不是空链表，新建立一个temp指针，初始化整形数n为0

c.将temp指针指向头结点

d.判断temp指针指向的结点的next域是否为空，如果不是，n加一，否则returnn

e.使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next域为0，返回n

代码描述:

template

intLinkList:

:

GetLength（）//分析链表长度

{

Node*p=front;

inti=0;

while（p）

{

p=p->next;

i++;

}

returni-1;

}

2.3其他

异常处理

采用trycatch函数处理异常

如在插入时的异常处理：

template

voidLinkList:

:

Insert（inti,Tx）

{

Node*p=front;

if（i!

=1）p=Get（i-1）;

try

{

if（p）

{

Node*s=newNode;

s->data=x;

s->next=p->next;

p->next=s;

}

elsethrowi;

}

catch（inti）

{

cout<<"插入到位置"<

}

}

3.程序运行结果

主函数流程图：

是

否

是否退出

测试截图：

初始化链表，菜单创建

执行功能：

4.总结

.调试时出现了一些问题如：

异常抛出的处理，书中并未很好的提及异常处理，通过查阅资料，选择用trycatch函数对解决。

2.心得体会

了解了单链表的基本的操作函数实现，对链式存储结构有了较好的认识

3.下一步的改进

可以增加完善报错机制，增强程序的健壮性

完整源代码：

//单链表的构造

#include

usingnamespacestd;

template

structNode

{

Tdata;//数据域

structNode*next;//指针域

};

template

classLinkList

{

public:

LinkList（）{front=newNode;front->next=NULL;}//无参构造函数

LinkList（Ta[],intn）;//有参构造函数，使用含有n个元素的数组a初始化单链表

~LinkList（）;//析构函数,（其在voidmain函数最后一句语句之后自动执行，旨在释放栈空间）

voidPrintList（）;//按次序遍历线性表中的各个数据元素

intGetLength（）;//获取线性表的长度

Node*Get（inti）;//获取线性表第i个位置上的元素结点地址

intLocate（Tx）;//查找线性表中值为x的元素，找到后返回其位置

voidInsert（inti,Tx）;//后插，在线性表的第i个位置上插入值为x的新元素

voidinsert（inti,Tx）;//前插，在线性表的第i个位置上插入值为x的新元素

TDelete（inti）;//删除线性表第i个元素，并将该元素返回

private:

Node*front;//头指针

};

//头插法构造函数

template

LinkList:

:

LinkList（Ta[],intn）

{

for（inti=n-1;i>=1;i--）//冒泡排序，对数组进行从小到大排序

{

for（intj=0;j

{

if（a[j]>a[j+1]）

{

Tt=a[j+1];

a[j+1]=a[j];

a[j]=t;

}

}

}

front=newNode;//为头指针申请堆空间

front->next=NULL;//构造空单链表

for（inti=n-1;i>=0;i--）

{

Node*s=newNode;//建立新结点

s->data=a[i];//将a[i]写入新结点的数据域

s->next=front->next;//修改新结点的指针域

front->next=s;//修改头结点的指针域，将新结点加入到链表中

}

}

//尾插法构造函数

//template

//LinkList:

:

LinkList（Ta[],intn）

//{

//front=newNode;

//Node*r=front;//命名一个新变量进行转换

//for（inti=0;i

//{

//Node*s=newNode;

//s->data=a[i];

//r->next=s;

//r=s;

//}

//r->next=NULL;

//}

template

voidLinkList:

:

PrintList（）//遍历线性表元素并打印到屏幕

{

Node*p=front->next;

while（p）

{

cout<data<<"　";

p=p->next;

}

cout<

}

template

LinkList:

:

~LinkList（）//析构函数

{

Node*p=front;//初始化工作指针P

while（p）//要释放的结点存在

{

front=p;

p=p->next;

deletefront;//释放结点

}

}

template

Node*LinkList:

:

Get（inti）//获取线性表第i个位置上的元素结点地址

{

Node*p=front->next;

intk=1;

while（p&&（k!

=i））

{

p=p->next;

k++;

}

returnp;

}

template

intLinkList:

:

Locate（Tx）//按值查找某元素的位置

{

Node*p=front->next;

intk=1;

while（p&&（p->data!

=x））

{

p=p->next;

k++;

}

returnk;

}

//后插

template

voidLinkList:

:

Insert（inti,Tx）

{

Node*p=front;

if（i!

=1）p=Get（i-1）;

try

{

if（p）

{

Node*s=newNode;

s->data=x;

s->next=p->next;

p->next=s;

}

elsethrowi;

}

catch（inti）

{

cout<<"插入到位置"<

}

}

template

TLinkList:

:

Delete（inti）

{

Node*p=front;

if（i!

=1）p=Get（i-1）;//若不是在第一个位置删除，获取第i-1个元素的地址

try

{

if（p&&（p->next））

{

Node*q=p->next;

p->next=q->next;

Tx=q->data;

deleteq;

returnx;

}

elsethrowi;

}

catch（inti）

{

cout<<"删除位置"<

}

}

template

intLinkList:

:

GetLength（）

{

Node*p=front->next;

inti;

for（i=0;p!

=NULL;i++）

{

p=p->next;

}

returni;

}

voidmain（）

{

intm=1;

inta[7]={3,2,1,4,6,5,7};

LinkListlist（a,7）;

cout<<"排序后的链表为:

";

list.PrintList（）;

cout<<"\t\t**************************************************"<

<<"\t\t※※"<

<<"\t\t※对该单链表的操作※"<

<<"\t\t※※"<

<<"\t\t※1.获取线性表的长度※"<

<<"\t\t※※"<

<<"\t\t※2.查找值为x的元素，并返回其位置※"<

<<"\t\t※※"<

<<"\t\t※3.在线性表的第i个位置上插入值为x的新元素※"<

<<"\t\t※※"<

<<"\t\t※4.删除线性表第i个元素，并将该元素返回※"<

<<"\t\t※※"<

<<"\t\t**************************************************"<

while（m!

=0）

{

cout<<"\t\t\t选择你需要的功能:

";

intchoice;

cin>>choice;//输入需要的功能

switch（choice）

{

case1:

cout<<"线性表的长度为:

"<

break;

case2:

//查找值为x的元素，并返回其位置

{

cout<<"请输入想查找的元素的值:

"<

intvalue;

cin>>value;

intlocation=list.Locate（value）;

cout<<"该元素的位置为:

"<

}

break;

case3:

//在线性表的第i个位置上插入值为x的新元素

{

cout<<"请输入想插入的位置值：

"<

intlocation_2;//位置值

cin>>location_2;

cout<<"请输入想插入的新元素的值"<

intvalue_1;//元素值

cin>>value_1;

list.Insert（location_2,value_1）;

cout<<"执行插入操作后的链表为:

"<

list.PrintList（）;

}

break;

case4:

//删除线性表第i个元素，并将该元素返回

{

cout<<"请输入想要删除的元素的位置值:

"<

intlocation_3;

cin>>location_3;

intvalue_2=list.Delete（location_3）;

cout<<"删除的元素值为：

"<

}

break;

default:

cout<<"!

!

无此功能项"<

break;

}

cout<<"※※※那您是否想继续？

继续请输入1不想继续请输入0※※※"<

cin>>m;

}

}