数据结构实验报告

数据结构实验报告

实验名称： 实验3.5 利用队列结构实现车厢重排问题+

学生姓名： 李思敏

班 级： 2011211108

班内序号： 18

学 号： 2011210233

日 期： 2012年11月13日

1． 实验要求

实验目的：

② 熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法；

②学习指针、模版类、异常处理的使用；

③ 掌握线性表的操作实现方法；

④培养使用线性表解决实际问题的能力。

实验要求：

② 要有异常处理；

②保持良好的编程风格：

· 代码段之间要有空行和缩进；

· 标示符名称应该与其代表的意义一致；

· 函数名之前应该添加注释说明该函数功能；

· 关键代码应说明其功能。

2. 程序分析

2.1 存储结构

采用链式存储结构存储车厢原始信息，利用尾插法构建带尾指针和头指针的单循环链表。

2.2 关键算法分析

关键算法1.建立循环链表

单链表的插入操作

front rear rear

① 若链表中只有一个数据节点，则头指针front和尾指针rear都指向此节点；

② 若链表中不止一个节点，头指针front指向第一个数据节点，使用尾插法构建链表； ③ 生成新节点，指针p指向该节点，p->data为该节点存储的数据，在约瑟夫问题中为节

点的顺序编号；

关键算法2.车厢的重排

本程序的关键算法主要为处理车厢重排问题的函数TrainPermute()，其伪代码如下：

void TrainPermute():

1. 初始化条件:计数器i=0,与非门aa=1

2. 判断是否能入轨while(用i<n判断是否n节车厢都入缓冲轨)&&(用aa=1判断是否有合适的缓冲轨可入)

2.1将aa置空；

2.2用for循环，依次取入入轨中的每一个车厢的编号进入合适的缓冲轨 ；

2.2.1如果缓冲轨中尾指针比进入缓冲轨元素小，则

进入该缓冲轨；

计数器i+1;

有合适缓冲轨，将aa变为真;

跳出for循环并进入while循环；

2.2.2如果缓冲轨中第一个元素为空，则

进入缓冲轨成为第一个元素；

计数器i+1;

有合适缓冲轨，将aa变为真;

跳出for循环并进入while循环；

2.3 用aa判断是否有进入合适的缓冲轨

2.3.1 aa=0即没有合适的缓冲轨，则

输出无法排列；

2.3.2 aa=1即有合适的缓冲轨，则

2.3.2.1遍历缓冲轨，

输出每个缓冲轨按顺序存储的车厢；

2.3.2.2 按从小到大的顺序出轨

for(引入输出轨计数器newOut=1;newOut<n; newOut+1;)

newOut与每个队列的头元素比较若相等，则

元素出队；

输出显示；

2.3 其他

该程序在每次出列一个数据时，都会返回出列的数据和出列顺序，使出列过程较为直观。 其实现在函数getdata（）中。

3. 程序运行结果

4. 总结

在程序调试过程中，曾出现无错误却无法运行的情况，系统提示内存错误，于是逐行检查指针的使用，查找是否出现了指针悬挂或内存泄露。经检查，发现在getdata（）函数中没有将指向出列节点数值的指针p删除，造成了内存泄露，后加入代码delete p，程序依然无法运行，后发现将若delete p移至for循环中，程序皆可运行且结果正确。说明向内存申请空间一定要归还，而且要在正确的位置归还。

通过这次数据结构编程实验，我初步了解了约瑟夫问题的求解方法，并熟悉了带尾指针的单循环链表，练习了利用尾插法构建链表的方法。在约瑟夫问题解决的过程中，复习了链表的出列操作，并通过编译时暴露出的问题，对指针使用方面存在的盲点进行了及时的查漏补缺，有了许多收获。

对于约瑟夫问题的进一步改进，我认为应集中在降低算法时间复杂度上，尝试将时间复杂度降至O（n）。同时可以在该程序基础上结合约瑟夫问题的历史故事，创作出具有娱乐性的小游戏，例如加入画面，计分规则，多人操作等。

总而言之，通过这次试验，我对数据结构第二章所学的内容进行了比较全面的检验，在肯定了学习效果的同时也暴露出来一些问题，还需继续努力。

本文来源：https://www.bwwdw.com/article/5v31.html