北京邮电大学信息与通信工程学院

数据结构实验报告

实验名称： 实验一 线性表 学生姓名： 班 级： 班内序号： 学 号：

日 期： 2013年11月7日

1． 实验要求

①实验目的：

通过选择下面四个题目之一进行实现，掌握如下内容：

? 熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 ? 学习指针、模板类、异常处理的使用 ? 掌握线性表的操作的实现方法

? 学习使用线性表解决实际问题的能力 ②实验要求：

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

1、 带头结点的单链表 2、 不带头结点的单链表 3、 循环链表 4、 双链表 5、 静态链表

线性表的基本功能：

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

2、 插入：要求建立的链表按照关键字从小到大有序 3、 删除 4、 查找

5、 获取链表长度 6、 销毁

7、 其他：可自行定义

编写测试main()函数测试线性表的正确性。 ③代码要求：

1、必须要有异常处理，比如删除空链表时需要抛出异常；

2、保持良好的编程的风格：

? 代码段与段之间要有空行和缩近 ? 标识符名称应该与其代表的意义一致

? 函数名之前应该添加注释说明该函数的功能

第1页

北京邮电大学信息与通信工程学院

? 关键代码应说明其功能

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)

步骤：

第2页

北京邮电大学信息与通信工程学院

①初始化工作指针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指向该结点；

第3页

北京邮电大学信息与通信工程学院

②设q指向第i个元素：q = p->next;

③摘链，即将q元素从链表中摘除：p->next = q->next; ④保存q元素的数据：x = q->data; ⑤释放q元素：delete q;

2.3 其他：

注意异常处理

3. 程序运行结果

（1）测试主函数流程

第4页

北京邮电大学信息与通信工程学院

（2）本程序最初设定数组最多可以存放1000个数据，但是a[0]用来计算整个数组的长度，故最多可以存999个数据。单链表把数据的数组通过头插法或者尾插法进行链接。因为程序中有异常处理，所以一旦插入以及删除元素的位置超过了单链表的长度范围，会报错。

4. 总结

1.调试时出现的问题：

① 程序中的查找，插入，删除都是按顺序进行的，所以无法同时对多个值进行相关的操作。

解决办法：加一个循环，，通过重复多次操作达到与同时操作多个值相同的效果

② 若将主函数定义为void型，将会导致无法返回数据。 解决办法：主函数修改为int型。

③ 类函数声明与定义的类型不对应. 2.心得体会：

（1）由于单链表是很多数据连接在一起，有直接前驱和直接后继的概念，所以当查找某一个数据的时候，要从头指针顺着链表进行扫描，平均时间复杂度为O（n），而在进行插入或者删除操作的时候，只需要修改指针即可，平均时间复杂度为O（1）。

（2）应用main函数来测试结果时，各种操作一起显示出来，没有做到用户与机器的交互运作，有待进一步改进。 3.改进：

（1）如果单链表查找第一个元素，那么时间复杂度就是O（1）,但是如果查找最后一个元素，时间复杂度就是O（n），这一点可以用循环链表来改进。如果已知一个结点，查找它的直接后继结点很快就可以查到，但如果要是查找它的直接前驱结点，还是得从第一个元素开始遍历，导致时间复杂度为O（n），这一点可以用双向链表改进。 （2）改进main函数，做到交互运行。

第5页