数据结构实验报告实验一线性表_图文
更新时间：/2/11 1:23:00浏览量：763手机版
数据结构实验报告
实验名称： 实验一 线性表
学生姓名：
班 级：
班内序号：
学 号：
日 期： 11月7日
1． 实验要求
①实验目的：
通过选择下面四个题目之一进行实现，掌握如下内容：
? 熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法
? 学习指针、模板类、异常处理的使用
? 掌握线性表的操作的实现方法
? 学习使用线性表解决实际问题的能力
②实验要求：
线性表存储结构(五选一)：
1、 带头结点的单链表
2、 不带头结点的单链表
3、 循环链表
4、 双链表
5、 静态链表
线性表的基本功能：
1、 构造：使用头插法、尾插法两种方法
2、 插入：要求建立的链表按照关键字从小到大有序
3、 删除
4、 查找
5、 获取链表长度
6、 销毁
7、 其他：可自行定义
编写测试main()函数测试线性表的正确性。
③代码要求：
1、必须要有异常处理，比如删除空链表时需要抛出异常；
2、保持良好的编程的风格：
? 代码段与段之间要有空行和缩近
? 标识符名称应该与其代表的意义一致
? 函数名之前应该添加注释说明该函数的功能
? 关键代码应说明其功能
2. 程序分析
2.1 存储结构
存储结构为单链表，示意图：
2.2 关键算法分析
关键算法：
(1) 头插法
每次插入元素都从单链表的第一个结点位置插入，先前插入的结点随着新结点插入而不断后移。
执行过程：
①?? 在堆中建立新结点：Node*s=new Node;
②将a[i]写入到新结点的数据域：s->data=a[i];
③修改新结点的指针域：s->next=front->next；
④修改头结点的指针域，将新结点加入到链表中：front->next=s;
(2) 尾插法
每次新插入的元素都在单链表的表尾。通常尾插法需要一个指针变量保存终端结点的地址，成为尾指针，设为r。每插入一个结点后，r指向新插入的终端结点。 步骤：
①?? 在堆中建立新结点：Node*s=new Node;
②将a[i]写入到新结点的数据域：s->data=a[i];
③将新结点加入到链表中：r->next=s;
④修改尾指针：r=s；
(3) 按位查找
获取单链表第i个位置上的元素其结点地址。
时间复杂度：O(n)
步骤：
①初始化工作指针p和计数器j，p指向的第一个结点，j=1；
②循环以下操作，直到p为空或j等于i,
p指向下一个结点；
j加1；
③返回p。
(4) 按值查找
查找单链表中值为x的元素，找到后返回其地址。
时间复杂度：O(n)
(5) 插入
在单链表的第i个位置上插入值为x的元素。先进行按位查找操作，即找到第i-1个位置的元素，然后在该元素后插入新元素。
时间复杂度：O(1)
步骤：
①在堆中建立新结点：Node*s=new Node;
②将p结点的数据域写入到新结点的数据域：s->data=p->data;
③修改新结点的指针域：s->next=p->next;
④修改p结点的指针域，将新结点加入到链表中：p->next=s;
⑤将x写入到p结点的数据域：p->data=x;
(6)删除
删除单链表中的第i个元素，并将该元素的值返回。
时间复杂度：O(1)
步骤：
①从第一个结点开始，查找第i-1个元素，设为p指向该结点；
②设q指向第i个元素：q = p->next;
③摘链，即将q元素从链表中摘除：p->next = q->next; ④保存q元素的数据：x = q->data;
⑤释放q元素：delete q;
2.3 其他：
注意异常处理
3. 程序运行结果
(1)测试主函数流程
