北邮数据结构实验一线性表及源代码

数据结构实验报告

实验名称：实验------线性表

学生姓名：SECRET

班级：SECRET

班内序号：SECRET

学号：SECRET

日期：2050年5月20日

1.实验要求

根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性

表的基木功能c

线性表存储结构（五选一）：

1、带头结点的单链表

2、不带头结点的单链表

3、循环链表

4、双链表

5、静态链表

线性表的基本功能：

1、构造：使用头插法、尾插法两种方法

2、插入：要求建立的链表按照关键字从小到大有序

3、删除

4、查找

5、获取链表长度

6、销毁

7、其他：可自行定义

编写测试mainO函数测试线性表的正确性。

2.程序分析

2.1存储结构

1000H

1020H

1O8OH

10C0H

2.2关键算法分析

关键算法

1：头插法

自然语言描述：

a:在堆中建立新结点

b:将a|i]写入到新结点的数据域

c:修改新结点的指针域

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

伪代码描述

a:Node<1>*s=newNode<I>

b:s->data=a[i]

c:s->ncxt=front->ncxt;

d:front->next=s

2：尾插法

自然语言描述：

a:在堆中建立新结点：

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

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

d:修改修改尾指针

伪代码描述

a:Node<T>*s=newNode<T>

b:s->data=a[i]

c:r->next=s;

d:r=s

3：析构/删除函数

自然语言描述：

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

b:判断要释放的结点是否存在，

c:暂时保存要释放的结点

d:移动a中建立的指针

e:释放要释放的指针

伪代码描述

a:Node<T>*p=front

b:while(p)

c:front=p

d:p=p->next

e:deletefront

4：按位查找函数

自然语言描述：

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

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

bl：p指向下一个结点

b2：j力口1

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

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

伪代码描述

a:Node<T>*p=front->next;j=l;

b:while(p&&j!=l)

bl:p=p->next

b2:j++

c:iR!p)throw"error”

d:returnp

5：按位查找函数

自然语言描述：

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

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

bl：判断p指向的结点是不是要查找的值，如果是，返回j,否则p指向下

一个结点，并且j的值加一

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

伪代码描述

a:Node<T>*p=front->next;j=I;

b:while(p)

bl:

if(p->next==x)returnj

p=p->next

j++

c:return“error”

6：插入函数

自然语言描述：

a:在堆中建立新结点

c:将temp指针指向头结点

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

c:使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next域为

0,返回n

伪代码描述

inin=0

iffront->next==NULL

n=0

else

{

Node<T>：1：temp=front->next;

while(temp->next)

n++;

tcmp=tcmp->ncxt;

I

returnn;

二代码详细分析

I：头插法插入链表

四句关键代码

Node<T>*s=newNode<T>;

s->data=a[il;

s->next=front->nexl;

fronl->next=s;

returnn;

示意图

2:尾插法插入链表

四句关键代码

Nodc<T>*s=ncwNode<T>;

s->data=a[i];

r->ncxt=s;

r=s;

示意图

front

r

3：查找算法

四句关键代码

Node<T>*p=front->next;

•ntj=l;

while(p&&j!=i)

p=p->next;

j++；

示意图

front-

P(j=DP(j=2)P(j=i)P(j=n)

4：删除算法

关键代码

Node<T>*p=front;

if(i!=l)p=Get(i-l);

Nodc<T>*q=p->ncxt;

p->next=q->ncxt;

Tx=q->data;

deleteq;

示意图

关键算法的时间、空间复杂度

头插法/尾插法0(n)

按位查找/按值查找0(n)

插入操作O(n)

3.程序运行结果

S1C:\Windows\systern32\cmd.exe2卜百心

利用遍历打印函数输出所有的数值

B1234567891R11121314151617181920212223242526272829

30313233343536373839404142434445464748

利用获取长度获取该楂表的长度为

输查找函数查找15所在的地址为

UW2F8770

利用按位查找函数找到第16个的数据为

需入函数演示•插入后遍历打印结果为

B1823456789101112131415161718192021222324252627282

930313233343536373839404142434445464748

删除某一位后的结果为(演示函数)

B1234567891011121314151617181920212223242526272829

30313233343536373839404142434445464748请按任意键继续...

流程图

开始

4.总结

1、调试时出现的问题及解决的方法

在编写按值查找函数时，由于没有处理好指针类型的原因，导致指针无法正常返回，

屡屡报错。最后意识到C++没有指针强制类型的转换机制，经过细致检查后才改正错误使得

程序正常运行。

2,心得体会

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

3,下一步的改进

可以增加完善报错机制

源代码

#include<ioslream>

usingnamespacestd;

tcmplatc<classT>

structNode

{

Tdata;

structNode*next;

)；

tcmplatc<classT>

classLinkList

(

public:

LinkList(){front=newNode<T>;front->next=NULL;}

voidhLinkList(Ta[J,intn);〃头插法

voidrLinkList(Ta||,intn);〃尾插法

~LinkList();〃析构/删除

intGetLength();//

Node<T>*Get(inti);

intLocale(Tx);

voidInsert(inli,Tx);

TDelete(inti);

voidPrintList();

private:

Node<T>*front;

}；

template<classT>

voidLinkList<T>::hLinkList(Ta[],intn)

{

front=newNode<T>;

front->next=NULL;

for(inti=n-1;i>=0;i—)

{

Node<T>*s=ncwNode<T>;

s->data=a[i];

s->next=front->next;

front->next=s;

)

)

template<classT>

voidLinkList<T>::rLinkList(Ta[],intn)

{

front=newNode<T>;

Node<T>:?r=front;

for(inti=O;i<=n-l;i++)

{

Nodc<T>*s=ncwNode<T>;

s->data=a[i];

r->ncxt=s;

r=s；

1

r->next=NULL;

)

template<classT>

LinkList<T>::-LinkList()

(

Node<T>*tenip=front;

while(temp)

{

front=tcmp;

tcmp=tcmp->ncxt;

deletefront;

I

)

template<classT>

Node<T>*LinkList<T>::Get(inti)

{

Node<T>*p=front->next;

intj=l;

while(p&&j!=i)

(

p=p->ncxt;

j++；

)

if(!p)throw”查找位置非法”；

elsereturnp;

)

template<classT>

intLinkList<T>::Locate(Tx)

(

Node<T>*p=front->next;

in(j=l；

while(p)

|

if(p->data==x)rcturnj;

p=p->next;

j++；

return-1;〃对查找位置错误的异常处理，返回一个-1.此处可以throw异常

tcmplatc<classT>

voidLinkList<T>::Insert(inti,Tx)

|

Node<T>*p=front;

if(i!=l)p=Get(i-l);

if(p)

(

Nodc<T>*s=ncwNodc<T>;

s->data=x;

s->next=p->next;

p->next=s;

)

elsethrow"插入位置错误";

)

template<classT>

TLinkList<T>::Delete(inti)

{

Node<T>*p=front;

if(i!=l)p=Get(i-l);

Nodc<T>*q=p->next;

p->ncxt=q->ncxt;

Tx=q->data;

deleteq;

returnx;

)

tcmplatc<classT>

voidLinkList〈T>::PrintLisi()〃遍历打印链表元素

|

if(front->next==NULL)

coutvv”该链表为空链表'Wendi;

Node<T>*iemp=fron(->next;

whilc(tcmp->ncxt)

(

cout«temp->data«"

temp=temp->next;

)

1

tcmplatc<classT>

intLinkList<T>::GctLength()

{

intn=0;

if(Iront->next==NULL)

n=0;

else

Node<T>*temp=front->next;

while(temp->next)

(

n++;

tcmp=tcmp->ncxt;

)

}

returnn;

)

intmain()

{

LinkList<int>linklistl;

intall[