北邮数据结构实验一题目一..doc
文本预览下载声明
数据结构实验报告
实验名称： 实验一——题目一
学生姓名：
班 级：
班内序号：
学 号：
日 期： 20年X月X日
实验要求
1.1、试验目的：
通过选择下面四个题目之一进行实现，掌握如下内容：
◎熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法
◎学习指针、模板类、异常处理的使用
◎掌握线性表的操作的实现方法
◎学习使用线性表解决实际问题的能力
1.2、实验内容
根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。
线性表存储结构（五选一）：
带头结点的单链表
不带头结点的单链表
循环链表
双链表
静态链表
线性表的基本功能：
构造：使用头插法、尾插法两种方法
插入：要求建立的链表按照关键字从小到大有序
删除
查找
获取链表长度
销毁
其他：可自行定义
编写测试main()函数测试线性表的正确性。
2. 程序分析
2.1 存储结构
2.2 关键算法分析
1、头插法
自然语言描述：
a:在堆中建立新结点
b:将 a[i]写入到新结点的数据域
c:修改新结点的指针域
d:修改头结点的指针域。将新结点加入链表中
伪代码描述
a:Node T * s=new Node T
b:s-data=a[i]
c:s-next=front-next;
d:front-next=s
2：尾插法
自然语言描述：
a:在堆中建立新结点。
b:将 a[i]写入到新结点的数据域。
c:将新结点加入到链表中。
d:修改修改尾指针。
伪代码描述
a:Node T * s=new Node 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:delete front
4：按位查找函数
自然语言描述：
a:初始化工作指针 p 和计数器 j，p 指向第一个结点，j=1
b:循环以下操作，直到 p 为空或者 j 等于 1
b1：p 指向下一个结点
b2：j 加 1
c:若 p 为空，说明第 i 个元素不存在，抛出异常
d:否则，说明 p 指向的元素就是所查找的元素，返回元素地址
伪代码描述
a:Node T * p=front-next;j=1;
b:while(pj!=1)
b1:p=p-next
b2:j++
c:if(!p) throw ”error”
d:return p
5：按值查找函数
自然语言描述：
a:初始化工作指针 p 和计数器 j，p 指向第一个结点，j=1
b:循环以下操作，找到这个元素或者 p 指向最后一个结点
b1：判断 p 指向的结点是不是要查找的值，如果是，返回 j，否则 p 指向下一个结点，并且 j 的值加一
c:如果找到最后一个结点还没有找到要查找的元素，返回查找失败信息
伪代码描述
a:Node T * p=front-next;j=1;
b:while(p)
b1:
if(p-next==x) return j
p=p-next
j++
c:return “error”
6：插入函数
自然语言描述：
a:在堆中建立新结点
b:将要插入的结点的数据写入到新结点的数据域
c:修改新结点的指针域
d:修改前一个指针的指针域，使其指向新插入的结点的位置
伪代码描述
a:Node T * s=new Node T;
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:delete q
8：遍历打印函数
自然语言描述：
a:判断该链表是否为空链表，如果是，报错
b:如果不是空链表，新建立一个 temp 指针
显示全部