数据结构实验报告实验一线性表

北京邮电大学信息与通信工程学院第1页北京邮电大学电信工程学院第1页数据结构实验报告实验名称：实验一线性表学生姓名：班级：班内序号：学号：日期：2013年11月7日实验要求①实验目的：通过选择下面四个题目之一进行实现，掌握如下内容：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法学习指针、模板类、异常处理的使用掌握线性表的操作的实现方法学习使用线性表解决实际问题的能力②实验要求：线性表存储结构（五选一）：带头结点的单链表不带头结点的单链表循环链表双链表静态链表线性表的基本功能：构造：使用头插法、尾插法两种方法插入：要求建立的链表按照关键字从小到大有序删除查找获取链表长度销毁其他：可自行定义编写测试main()函数测试线性表的正确性。③代码要求：1、必须要有异常处理，比如删除空链表时需要抛出异常；2、保持良好的编程的风格：代码段与段之间要有空行和缩近标识符名称应该与其代表的意义一致函数名之前应该添加注释说明该函数的功能关键代码应说明其功能2.程序分析2.1存储结构存储结构为单链表，示意图：2.2关键算法分析关键算法：头插法每次插入元素都从单链表的第一个结点位置插入，先前插入的结点随着新结点插入而不断后移。执行过程：在堆中建立新结点：Node*s=newNode;②将a[i]写入到新结点的数据域：s->data=a[i];③修改新结点的指针域：s->next=front->next；④修改头结点的指针域，将新结点加入到链表中：front->next=s;尾插法每次新插入的元素都在单链表的表尾。通常尾插法需要一个指针变量保存终端结点的地址，成为尾指针，设为r。每插入一个结点后，r指向新插入的终端结点。步骤：在堆中建立新结点：Node*s=newNode;②将a[i]写入到新结点的数据域：s->data=a[i];③将新结点加入到链表中：r->next=s;④修改尾指针：r=s；按位查找获取单链表第i个位置上的元素其结点地址。时间复杂度：O(n)步骤：=1\*GB3①初始化工作指针p和计数器j，p指向的第一个结点，j=1；=2\*GB3②循环以下操作，直到p为空或j等于i,p指向下一个结点；j加1；=3\*GB3③返回p。(4)按值查找查找单链表中值为x的元素，找到后返回其地址。时间复杂度：O(n)(5)插入在单链表的第i个位置上插入值为x的元素。先进行按位查找操作，即找到第i-1个位置的元素，然后在该元素后插入新元素。时间复杂度：O(1)步骤：=1\*GB3①在堆中建立新结点：Node*s=newNode;②将p结点的数据域写入到新结点的数据域：s->data=p->data;③修改新结点的指针域：s->next=p->next;④修改p结点的指针域，将新结点加入到链表中：p->next=s;⑤将x写入到p结点的数据域：p->data=x;（6）删除删除单链表中的第i个元素，并将该元素的值返回。时间复杂度：O(1)步骤：=1\*GB3①从第一个结点开始，查找第i-1个元素，设为p指向该结点；②设q指向第i个元素：q=p->next;③摘链，即将q元素从链表中摘除：p->next=q->next;④保存q元素的数据：x=q->data;⑤释放q元素：deleteq;2.3其他：注意异常处理3.程序运行结果（1）测试主函数流程（2）本程序最初设定数组最多可以存放1000个数据，但是a[0]用来计算整个数组的长度，故最多可以存999个数据。单链表把数据的数组通过头插法或者尾插法进行链接。因为程序中有异常处理，所以一旦插入以及删除元素的位置超过了单链表的长度范围，会报错。4.总结1.调试时出现的问题：程序中的查找，插入，删除都是按顺序进行的，所以无法同时对多个值进行相关的操作。解决办法：加一个循环，，通过重复多次操作达到与同时操作多个值相同的效果若将主函数定义为void型，将会导致无法返回数据。解决办法：主函数修改为int型。类函数声明与定义的类型不对应.2.心得体会：（1）由于单链表是很多数据连接在一起，有直接前驱和直接后继的概念，所以当查找某一个数据的时候，要从头指针顺着链表进行扫描，平均时间复杂度为O（n），而在进行插入或者删除操作的时候，只需要修改指针即可，平均时间复杂度为O（1）。（2）应用main函数来测试结果时，各种操作一起显示出来，没有做到用户与机器的交互运作，有待进一步改进。3.改进：（1）如果单链表查找第一个元素，那么时间复杂度就是O（1）,但是如果查找最后一个元素，时间复杂度就是O（n），这一点可以用循环链表来改