北邮数据结构线性表

《北邮数据结构线性表》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构实验报告实验名称：实验1线性表学生姓名：邱新龙班级：信通17班班内序号:17号学号：2012210498闩期：2013年11月1日1.实验要求1实验目的通过选择K面网个题目之•-•进行实现，掌握如K内容：>熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法>学习指针、模板类、异常处理的使用>掌握线性表的操作的实现方法>学4使川线性表解决实际问题的能力2实验内容根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。线性表存储结构（五选一）：1、带失结点的单链表2、不带失结点的单链表3、循环链表4、双链表5、静态链表线性表

2、的基木功能：1、构造：使川头插法、尾插法两种方法2、插入：耍求建立的链表按照关键字从小到大有序3、删除4、查找5、获取链表长度6、销毁7、其他：可A行定义编写测试mainO函数测试线性表的正确性。1.程序分析2.1存储结构单链表：每个结点只包含一个链域的链表,空链表:front►非空链表：front

3、:b）带头结点的单链表2.2关键算法分析1、构造（头插法）①在堆屮建立新结点：Node*s=newNode;②将a[i]写入到新结点的数掘域：s->data=a[i];③修改新结的指针域：s->ncxt=front->ncxt;④修改头结点的指针域，将新结点加

4、入到链表中：front->next=s;A时间复杂度为：0（n）2、构造（尾插法）①在堆屮建立新结点：Node*s=newNode;②将a[i]写入到新结点的数掘域：s->data=a[i];③将新结点加入到链表屮：r-〉next=s;④修改尾指针：r=s;吋间复杂度为：0(h)3、插入①在堆中建立新结点：Node*s=newNode;②将P结点的数掘域写入到新结点的数掘域：s-〉data=p-〉data;③修改新结点的抬针域：s-〉next=p-〉next;④修改P结点的指针域，将新结点加入到链表屮：p_〉next=s;⑤将x写入到p结点的数

5、拋域：p->data=x;时间£杂度为：0(1)4、删除①从第一个结点开始，查找第i_l个元素，设为P指向该结点:②设q指向访i个元素：q=p-〉next;③摘链，即将q元素从链表屮摘除：p~>next=q->next;④保存q元素的数拋：x=q-〉data;⑤释放q元素：deleteq;时闯复杂度为：0(n)5、查找(按位査找)①初始化工作指针p和计数器j，p指叫第一个结点，j=l;②循环一下操作，直到P为空或j等于i2.1p指向下一个结点；2.2j加1;③返回P;初始化：p(j=l)pO=2)^=null吋间复杂度为：0(n)査找(按值查找)①初始化工作指针：No

6、de〈T〉*p=front-〉next;②找到被金元素，返回位置：if(p->data==x)returnj;吋间复杂度为：0(n)7、获取链表长度①初始化工作抬针：Node*p=front->next;②if(front==NULL)throw〃链表力空〃；③while循环获取长度:while(p){length++;p=p->next;}returnlength时间复杂度为：0(n)8、析构①初始化工作指针p:Node*p=front;②暂存要释放的结点：fronts;③移动工作指针：p=p-〉next;④释放结点：deletefront;吋间复杂度为

7、••0(n)1.程序运行结果开始输入数裾个数依次输入数据1获取长度在位置为3插入“8”，并遍历一次链丧找到伉为“4”的元素并删除第2个元素，然f遍历一次链表Yz结束4.总结在这次实验中，我挑的是第一个题，为的就是夯实自己的基础，俏在写最基本的链表过程屮依然出现了不少问题。比如，关于结点怎么使用，编译出现数裾类型错误等。在这过程屮,通过百度搜索、问M学、问老师的方法所有问题都得到了解决。这其中耗赀了不少的吋间，不过我认为这个吋间应该花费，在这过程屮不仅解决了问题，也学会了如何去面对编程过程中的问题，如柯去想办法解决这些问题，这些经历很难得。下一步应该在夯实基础上，进一步

8、加强编程能力和解决问题的能力。