数据结构实验一试题目一线性表实验报告表.docx

该【数据结构实验一试题目一线性表实验报告表 】是由【大于振】上传分享，文档一共【20】页，该文档可以免费在线阅读，需要了解更多关于【数据结构实验一试题目一线性表实验报告表 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据构造实验一试题目一线性表实验报告表
北京邮电大学电信工程学院
数据构造实验报告
实验名称:实验1——线性表
学生姓名:
班级:
班内序号:
学号:
日期:

1、实验目的:熟悉C++语言的根本编程方法,掌握集成编译环境的调试方法
学习指针、模板类、异常办理的使用
掌握线性表的操作的实现方法
学习使用线性表解决实责问题的能力
、实验内容:题目1:
线性表的根本功能:
1、构造:使用头插法、尾插法两种方法
2、插入:要求建立的链表依照要点字从小到大有序
3、删除
4、查找
5、获取链表长度
6、销毁
7、其他:可自行定义
编写测试main()函数测试线性表的正确性。
程序解析
储藏构造
带头结点的单链表
第1页
数据构造实验一试题目一线性表实验报告表
-
要点算法解析
头插法
a、伪代码实现:在堆中建立新结点
将x写入到新结点的数据域更正新结点的指针域
更正头结点的指针域,将新结点参加链表中
b、代码实现:
Linklist::Linklist(inta[],intn)//头插法
{front=newNode;
front->next=NULL;
for(inti=n-1;i>=0;i--)
{Node*s=newNode;
s->data=a[i];
s->next=front->next;
front->next=s;
}
}
2、尾插法
欢送下载2
数据构造实验一试题目一线性表实验报告表
-
a、伪代码实现:
[i]写入到新结点的数据域


b、代码实现:
Linklist::Linklist(inta[],intn,intm)//尾插法
{front=newNode;
Node*r=front;
for(inti=0;i<n;i++)
{Node*s=newNode;
s->data=a[i];
r->next=s;
r=s;
}
r->next=NULL;
}
时间复杂度:O(n)
3、按位查找
a、伪代码实现:初始化工作指针p和计数器j,p指向第一个结点,j=1
循环以下操作,直到p为空也许j等于1
b1:p指向下一个结点
b2:j加1
假设p为空,说明第i个元素不存在,抛出异常
否那么,说明p指向的元素就是所查找的元素,返回元素地
址b、代码实现
Node*Linklist::Get(inti)//获取指向第i个数的指针
{Node*p=front->next;
intj=1;
while(p&&j!=i)//p非空且j不等于i,指针后移
{p=p->next;
j++;
欢送下载3
数据构造实验一试题目一线性表实验报告表
-
}
returnp;
}
4、插入操作
a、伪代码实现:若是链表为空,直接插入
判断p的下一个结点的值大于x且p的值小于x
在堆中建立新结点
将要插入的结点的数据写入到新结点的数据域
更正新结点的指针域
更正前一个指针的指针域,使其指向新插入的结点的地址
b、代码实现
voidLinklist::Insert(intx)//将x按序次插入
{Node*p=front->next;
if(!p)//若是链表为空,直接插入
{Node*s=newNode;
s->data=x;
s->next=front->next;
front->next=s;
}
else
while(!((p->next->data>x)&&(p->data<x)))//判断p的下一个结点的值大于x且p的值
小于x
{p=p->next;}
Node*s=newNode;//将x插入到p此后
s->data=x;
s->next=p->next;
p->next=s;
}
5、删除操作
a、伪代码实现:从第一个结点开始,查找要删除的位数i前一个地址i-1的结点
设q指向第i个元素将q元素从链表中删除保存q元素的数据
释放q元素
b、代码实现
intLinklist::Delete(inti)//删除第i个地址的结点
{Node*p=front;
if(i!=1)
欢送下载4
数据构造实验一试题目一线性表实验报告表
-
p=Get(i-1);//获取第i-1个地址的指针
Node*q=p->next;
p->next=q->next;
intx=q->data;
deleteq;
returnx;
}
遍历打印函数
a、伪代码实现:判断该链表可否为空链表,若是是,报错
若是不是空链表,新建立一个temp指针
将temp指针指向头结点打印temp指针的data域
逐个此后搬动temp指针,直到temp指针的指向的指针的next域为空
b、代码实现
voidLinklist::show()//打印数组元素
{Node*p=front->next;
while(p)
{
cout<<p->data<<"";
p=p->next;
}
}
获取链表长度函数
a、伪代码实现:判断该链表可否为空链表,若是是,输出长度0
若是不是空链表,新建立一个temp指针,初始化整形数n为0
将temp指针指向头结点
判断temp指针指向的结点的next域可否为空,若是不是,n加一,否
则returnn
使temp指针逐个后移,重复d操作,直到temp指针指向的结点的next域为0,返回n
、代码实现
voidLinklist::Getlength()//获取数组长度
{Node*p=front->next;
intj=0;
while(p)
{p=p->next;
j++;}
欢送下载5