合工大宣城校区数据结构实验报告——单链表.doc

数据结构实验报告
姓名

学号

专业班级

指导教师

实验时间
11月9日
实验地点
计算中心

实验二 单链表实验

1. 实验目标
① 熟练掌握线性表的链式存储结构。
② 熟练掌握单链表的有关算法设计。
③ 根据具体问题的需要，设计出合理的表示数据的链式存储结构，并设计相关算法。
2. 实验内容和要求
Ⅰ.实验要求
① 本次实验中的链表结构指带头结点的单链表
② 单链表结构和运算定义，算法的实现以库文件方式实现，不得在测试主程序中直接实现；比如存储、算法实现放入文件：linkedList.h
③ 实验程序有较好可读性，各运算和变量的命名直观易懂，符合软件工程要求；
④ 程序有适当的注释。

Ⅱ.实验内容
<1>尾插法创建单链表，打印创建结果。
<2>头插法创建单链表，打印创建结果。
<3>销毁单链表。
<4>求链表长度。
<5>求单链表中第i个元素（函数），若不存在，报错。
<6>在第i个结点前插入值为x的结点
<7>链表中查找元素值为x的结点，成功返回结点指针，失败报错
<8>删除单链表中第i个元素结点
<9>在一个递增有序的单链表L中插入一个值为x的元素，并保持其递增有序特性
<10>将单链表Ｌ中的奇数项和偶数项结点分解开（元素值为奇数、偶数），分别放入新的单链表中，然后原表和新表元素同时输出到屏幕上，以便对照求解结果
<11>求两个递增有序单链表L1和L2中的公共元素，放入新的单链表L3中
<12>删除递增有序单链表中的重复元素，要求时间性能最好
<13>递增有序单链表L1、L2，不申请新结点，利用原表结点对2表进行合并，并使得合并后成为一个集合，合并后用L1的头结点作为头结点，删除L2的头结点，要求时间性能最好
扩展实验：
<1>（递增有序）单链表表示集合A、B，实现：
C=AÇB，C=AÈB，C=A-B
A=AÇB，A=AÈB，A=A-B

<2>（递增有序）单链表表示集合A、B，判定A是否B的子集
<3>已知一个带有表头结点的单链表，结点结构如下图。假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data值，并返回1；否则，只返回0。
<4>(2011)（15 分）一个长度为L（L≥1）的升序序列S，处在第 个位置的数称为S 的中位数。例如，若序列S1=(11, 13, 15, 17, 19)，则S1 的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=(2, 4, 6, 8, 20)，则S1 和S2 的中位数是11。
现有两个等长升序序列A 和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A 和B 的中位数

3. 数据结构设计
struct Node
{
int value;
Node *next;
Node(int value = 0, Node *pNext = 0)
{
this->value = value;
this->next = pNext;
}
};
class linkedList
{
public :
linkedList()；//构造函数
~linkedList()；//<3>析构函数,销毁单链表
int length()；//<4>求链表长度
Node *listLocateI(int i)；//<5>求单链表中第i个元素
bool listInsert(int i,int x)；//<6>在第i个结点前插入值为x的结点
Node *listLocateX(int x)；//<7>链表中查找元素值为x的结点，成功返回结点指针，失败报错。
bool listDelete(int i)；//<8>删除单链表中第i个元素结点
Node *head;
};
4. 算法设计
<1>~<8>为书中已经给出的基本算法，
<9>.定义一个指针p指向头结点，当p->next != NULL，循环比较p->next->value与x的值之间的大小，若p->next->value<x，就令p = p->next，当申请新结点，存储x，将新结点插入在p之后，完成插入。
<10>.定义两个链表L1，L2， 定义指针*p，*u，*r，分别指向L的首元素结点，L1，L2的头结点上，循环判断，如果p->value%2!=0，就插入到表L1中，否则，就插入到表L2中，然后令p=p->next，直至p!=NULL结束循环，输出L1，L2，其中L1表示奇结点，L2表示偶结点
<11>.定义两个链表L3，定义指针*p，*u，*r，分别指向L3的头结点，L1，L2的首元素结点上，循环判断，如果u->value==r->value，就把该值插入到表L3中，如果u->value>r->value，让r=r->next，否则让u=u->next；当u==NULL或者r==NULL，结束循环，输出L3；
<12>.将元素分为两部分，一部分是已经处理元素，和待处理元素。用r指向最后一个已经处理元素，用u指向还未处理的元素，如果u->value < r->value，就让u->next=r，删除中间的重复元素，否则就令r=r->next，当r==NULL结束循环，令u->next=NULL，输出L
<13>.定义指针*p1,*p2,*u；p1,p2分别指向L1的头结点和L2的首元素结点，判断p1->next->value与p2->value大小，前者大，则将p2插入到p1后面，后者大则让p1=p1->next，相等则p2=p2->next，p1=p1->next，当p1->next ==NULL或p2==NULL结束循环。若p2 !=NULL，直接将其接到p1之后，删除L2.head，输出L1.
扩展实验：
<1>. 对于采用集合C的运算，将符合要求的元素插入到新链表C中，对于不采用链表C的运算，就对链表A中元素进行插入与删除操作。
<2>.使用两个指针*u，*r，分别指向A，B的首元素结点，对A中元素按顺序进行判断，如果出现u->value<r->value，则表示A不为B的子集，如果u->value>r->value，则r = r->next，如果u->value==r->value,则u = u->next，r = r->next，如果对A中每个元素进行判断，均可在B中找到，则A为B的子集。
<3>.采用两个指针*u = L.head，*r = L.head->next，加入一个计数器i，i表示已经经过的结点，r每移动一次，i++，当i>k，u开始移动，当r移动到表尾时，u即指向倒数第k个位置上的结点；若u为头结点，则其未移动，表示无倒数第k个位置上的结点。
<4>.因为两个序列A 和B等长升序，故只需按照递增有序的顺序找到第A.length()即可，可以对A，B元素进行排序，到第A.length()结束即可输出该值为中位数。

5. 运行和测试
菜单：

<9>

<10>

<11>

<12>

<13>

扩展实验：
<1>
C=AÈB，

C=AÇB

C=A-B

A=AÈB

A=AÇB

A=A-B

<2>

<3>

<4>

6. 总结和心得
在此次程序编写的过程中，我总结第一次的经验教训，对程序整体先进行了构建，避免了重复输出的问题。然而，在编写过程中，针对此次实验又出现了不少新的问题，下面进行相关总结：
1. 在重置链表时，开始未将头结点的后继设为NULL，导致输出时出现异常，花费大量时间才找到这一错误；
2. 在完成向新链表中传入元素时，直接采用原来的结点，导致出现原链表异常，影响实验功能，最后采用创建新结点解决；
3. 删除重复元素时，一开始采用逐个删除，时间复杂度过高，后采用两个结点，一次性删除所有重复元素，提高了时间性能；
4. 在处理扩展实验三时，一开始采用先计算表长度，在找结点，过于复杂，之后改为使用两个指针，使二者之间间隔未k，直接在后一结点结束时输出前一结点，提高了时间性能；
5. 在实验中，对于个结点之间的逻辑关系有所混淆，导致花费时间较长，我从中吸取了教训，在以后的实验中，我会先解决逻辑关系的问题，在完成实际的代码。
[7. 附录]
（源代码清单。纸质报告不做要求。电子报告，可直接附源文件，删除编译生成的所有文件）

个人工作业务总结
本人于2009年7月进入新疆中正鑫磊地矿技术服务有限公司(前身为“西安中正矿业信息咨询有限公司”)，主要从事测量技术工作，至今已有三年。
在这宝贵的三年时间里，我边工作、边学习测绘相专业书籍，遇到不懂得问题积极的请教工程师们，在他们耐心的教授和指导下，我的专业知识水平得到了很到的提高，并在实地测量工作中加以运用、总结，不断的提高自己的专业技术水平。同时积极的参与技术培训学习，加速自身知识的不断更新和自身素质的提高。努力使自己成为一名合格的测绘技术人员。
在这三年中，在公司各领导及同事的帮助带领下，按照岗位职责要求和行为规范，努力做好本职工作，认真完成了领导所交给的各项工作，在思想觉悟及工作能力方面有了很大的提高。
在思想上积极向上，能够认真贯彻党的基本方针政策，积极学习政治理论，坚持四项基本原则，遵纪守法，爱岗敬业，具有强烈的责任感和事业心。积极主动学习专业知识，工作态度端正，认真负责，具有良好的思想政治素质、思想品质和职业道德。
在工作态度方面，勤奋敬业，热爱本职工作，能够正确认真的对待每一项工作，能够主动寻找自己的不足并及时学习补充，始终保持严谨认真的工作态度和一丝不苟的工作作风。
在公司领导的关怀以及同事们的支持和帮助下，我迅速的完成了职业角色的转变。
一、回顾这四年来的职业生涯，我主要做了以下工作：
1、参与了新疆库车县新疆库车县胡同布拉克石灰岩矿的野外测绘和放线工作、点之记的编写工作、1:2000地形地质图修测、1:1000勘探剖面测量、测绘内业资料的编写工作，提交成果《新疆库车县胡同布拉克石灰岩矿普查报告》已通过评审。
2、参与了库车县城北水厂建设项目用地压覆矿产资源评估项目的室内地质资料编写工作，提交成果为《库车县城北水厂建设项目用地压覆矿产资源评估报告》，现已通过评审。
3、参与了《新疆库车县巴西克其克盐矿普查》项目的野外地质勘查工作，参与项目包括：1:2000地质测图、1:1000勘查线剖面测量、测绘内业资料的编写工作；最终提交的《新疆库车县康村盐矿普查报告》已通过评审。
4、参与了新疆哈密市南坡子泉金矿2009年度矿山储量监测工作，项目包括：野外地质测量与室内地质资料的编写，提交成果为《新疆哈密市南坡子泉金矿2009年度矿山储量年报》，现已通过评审。
6、参与了《新疆博乐市五台石灰岩矿9号矿区勘探》项目的野外地质勘查工作，项目包括：1:2000地质测图、1:1000勘探剖面测量、测绘内业资料的编写工作，并绘制相应图件。
7、参与了《新疆博乐市托特克斜花岗岩矿详查报告》项目的野外地质勘查工作，项目包括：1:2000地质测图、1:1000勘探剖面测量、测绘内业资料的编写工作，并绘制相应图件。
通过以上的这些工作，我学习并具备了以下工作能力：
1、通过实习，对测绘这门学科的研究内容及实际意义有了系统的认识。加深对测量学基本理论的理解，能够用有关理论指导作业实践，做到理论与实践相统一，提高分析问题、解决问题的能力，从而对测量学的基本内容得到一次实际应用，使所学知识进一步巩固、深化。
2、熟悉了三、四等控制测量的作业程序及施测方法，并掌握了全站仪、静态GPS、RTK等测量仪器的工作原理和操作方法。
3、掌握了GPS控制测量内业解算软件（南方测绘 Gps数据处理）以及内业成图软件（南方cass）的操作应用。能够将外业测量的数据导入软件进行地形图成图和处理。
4、在项目技术负责的指导下熟悉了测量技术总结的编写要求和方法，并参与了部分项目测量技术总结章节的编写工作。
5、在项目负责的领导下参与整个测量项目的组织运作，对项目的实施过程有了深刻理解。通过在项目组的实习锻炼了自己的组织协调能力，为以后的工作打下了坚实基础。
二、工作中尚存在的问题
从事测绘工作以来，深深感受到工作的繁忙、责任的重大，也因此没能全方位地进行系统地学习实践，主要表现为没有足够的经验，对于地形复杂的地段理解不够深刻；理论知识掌握不够系统，实践能力尚为有限。以上问题，在今后工作中自己将努力做到更好。
三、今后的工作打算
通过总结四年来的工作，我无论从工作技术上，还是从世界观、人生观、价值观等各个方面，都有了很大的提高。今后，我会在此基础上，刻苦钻研，再接再厉，使自己在业务知识水平更上一层楼，为测绘事业的发展，贡献自己的力量。