北京邮电大学信息与通信工程学院
数据结构实验报告
实验名称： 实验一 线性表 学生姓名： 班 级： 班内序号： 学 号：
日 期： 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页