北京邮电大学数据结构实验第一次实验线性表.docx
- 文档编号:17307123
- 上传时间:2023-07-24
- 格式:DOCX
- 页数:17
- 大小:103.88KB
北京邮电大学数据结构实验第一次实验线性表.docx
《北京邮电大学数据结构实验第一次实验线性表.docx》由会员分享,可在线阅读,更多相关《北京邮电大学数据结构实验第一次实验线性表.docx(17页珍藏版)》请在冰点文库上搜索。
北京邮电大学数据结构实验第一次实验线性表
数据结构实验报告
实验名称:
实验1——线性表
学生姓名:
班级:
班内序号:
学号:
日期:
1.实验要求
根据线性表的抽象数据类型的定义,选择下面任一种链式结构实现线性表,并完成线性表的基本功能。
线性表存储结构(五选一):
1、带头结点的单链表2、不带头结点的单链表3、循环链表4、双链表5、静态链表
线性表的基本功能:
1、构造:
使用头插法、尾插法两种方法
2、插入:
要求建立的链表按照关键字从小到大有序
3、删除
4、查找
5、获取链表长度
6、销毁
7、其他:
可自行定义
编写测试main()函数测试线性表的正确性。
2.程序分析
2.1存储结构
2.2关键算法分析
1:
头插法
自然语言描述:
a:
在堆中建立新结点
b:
将a[i]写入到新结点的数据域
c:
修改新结点的指针域
d:
修改头结点的指针域。
将新结点加入链表中
伪代码描述
a:
Node
b:
s->data=a[i]
c:
s->next=front->next;
d:
front->next=s
2:
尾插法
自然语言描述:
a:
在堆中建立新结点:
b:
将a[i]写入到新结点的数据域:
c:
将新结点加入到链表中
d:
修改修改尾指针
伪代码描述
a:
Node
b:
s->data=a[i]
c:
r->next=s;
d:
r=s
3:
析构/删除函数
自然语言描述:
a:
新建立一个指针,指向头结点
b:
判断要释放的结点是否存在,
c:
暂时保存要释放的结点
d:
移动a中建立的指针
e:
释放要释放的指针
伪代码描述
a:
Node
b:
while(p)
c:
front=p
d:
p=p->next
e:
deletefront
4:
按位查找函数
自然语言描述:
a:
初始化工作指针p和计数器j,p指向第一个结点,j=1
b:
循环以下操作,直到p为空或者j等于1
b1:
p指向下一个结点
b2:
j加1
c:
若p为空,说明第i个元素不存在,抛出异常
d:
否则,说明p指向的元素就是所查找的元素,返回元素地址
伪代码描述
a:
Node
b:
while(p&&j!
=1)
b1:
p=p->next
b2:
j++
c:
if(!
p)throw-1
d:
returnp
5:
按值查找函数
自然语言描述:
a:
初始化工作指针p和计数器j,p指向第一个结点,j=1
b:
循环以下操作,找到这个元素或者p指向最后一个结点
c:
判断p指向的结点是不是要查找的值,如果是,返回j,否则p指向下
一个结点,并且j的值加一
d:
如果找到最后一个结点还没有找到要查找的元素,返回查找失败信息
伪代码描述
a:
Node
b:
while(p)
c:
if(p->next==x)returnjp=p->nextj++
d:
return-1
6:
插入函数
自然语言描述:
a:
在堆中建立新结点
b:
将要插入的结点的数据写入到新结点的数据域
c:
修改新结点的指针域
d:
修改前一个指针的指针域,使其指向新插入的结点的位置
伪代码描述
a:
Node
b:
s-data=p->data
c:
s->next=p->next
d:
p->next=s
e:
p->data=x
7:
删除函数
自然语言描述:
a:
从第一个结点开始,查找要删除的位数i前一个位置i-1的结点
b:
设q指向第i个元素
c:
将q元素从链表中删除
d:
保存q元素的数据
e:
释放q元素
伪代码描述
a:
q=p->next
b:
p->next=q->next
c:
x=q->data
d:
deleteq
8:
遍历打印函数
自然语言描述:
a:
判断该链表是否为空链表,如果是,报错
b:
如果不是空链表,新建立一个temp指针
c:
将temp指针指向头结点
d:
打印temp指针的data域
e:
逐个往后移动temp指针,直到temp指针的指向的指针的next域为空
伪代码描述
Iffront->next==NULL
Throw”anemptylist”
Node
while(temp->next)
{
cout<
temp=temp->next;
}
8:
获取链表长度函数
自然语言描述:
a:
判断该链表是否为空链表,如果是,输出长度0
b:
如果不是空链表,新建立一个temp指针,初始化整形数n为0
c:
将temp指针指向头结点
d:
判断temp指针指向的结点的next域是否为空,如果不是,n加一,否则returnn
e:
使temp指针逐个后移,重复d操作,直到temp指针指向的结点的next域为0,返回n
伪代码描述
intn=0
iffront->next==NULL
n=0
else
{
Node
while(temp->next)
n++;
temp=temp->next;
}
returnn;
1:
头插法插入链表
Node
s->data=a[i];
s->next=front->next;
front->next=s;
2:
尾插法插入链表
Node
s->data=a[i];
r->next=s;
r=s;
3:
查找算法
Node
intj=1;
while(p&&j!
=i)
{
p=p->next;
j++;
4:
删除算法
Node
if(i!
=1)p=Get(i-1);
Node
p->next=q->next;
Tx=q->data;
deleteq;}
头插法/尾插法O(n)按位查找/按值查找O(n)插入操作O(n)
3.程序运行结果
截图
流程图
开始
初始化对象
初始化整形数组
利用头插法和尾插法初始化,用遍历打印函数来显示数值
执行删除函数,然后用遍历打印函数来检测删除结果
执行插入函数,然后用遍历打印函数来检测插入结果
按位查找和按值查找
结束
4.总结
对链表的掌握不够扎实,对类的掌握不全面。
代码:
#include
usingnamespacestd;
classNode
{
public:
intdata;
Node*next;
};
classLinkList
{
public:
LinkList()
{};
LinkList(inta[],intn);
Node*Get(intj);
intLocate(intx);
voidInsert(intj,intx);
intDelete(intj);
intGetlength();
voidPrint();
~LinkList();
private:
Node*front;
intlength;
};
LinkList:
:
LinkList(inta[],intn)
{
front=newNode;
front->next=NULL;
for(intj=n-1;j>=0;j--)
{
Node*s=newNode;
s->data=a[j];
s->next=front->next;
front->next=s;
}
}
/*LinkList
:
LinkList(inta[],intn)
{
front=newNode
Node
for(intj=0;j { Node s->data=a[j]; s->next=s; r=s; } r->next=NULL; }*/ Node*LinkList: : Get(inti) { Node*p=front->next; intj=1; while(p&&j! =i) { p=p->next; j++; } returnp; } intLinkList: : Locate(intx) { Node*p=front->next; intj=1; while(p) { if(p->data==x) returnj; p=p->next; j++; } return-888; } voidLinkList: : Insert(inti,intx) { Node*p=front; if(i! =1) p=Get(i-1); if(p) { Node*s=newNode; s->data=x; s->next=p->next; p->next=s; } elsethrow"error"; } intLinkList: : Delete(inti) { Node*p=front; if(i! =1) p=Get(i-1); Node*q=p->next; p->next=q->next; intx=q->data; deleteq; returnx; } LinkList: : ~LinkList() { Node*p=front; while(p) { front=p; p=p->next; deletefront; } } intLinkList: : Getlength() { length=0; Node*n=front->next; while(NULL! =n) { length++; n=n->next; } returnlength; } voidLinkList: : Print() { Node*n=front->next; while(NULL! =n) { cout< n=n->next; } cout< } voidmain() { inta[10]={7,9,10,11,22,8,33,2,21,80}; LinkList*Lin=newLinkList(a,10); cout< cout< cout< cout< cout< Lin->Print(); Lin->Insert(3,20); Lin->Print(); Lin->Delete(5); Lin->Print(); Lin->~LinkList; Lin->Print(); }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 北京邮电 大学 数据结构 实验 第一次 线性