发布时间 : 星期一 文章链表实现排序算法更新完毕开始阅读737e31f88662caaedd3383c4bb4cf7ec4bfeb624
北京邮电大学信息与通信工程学院
数 据 结 构
实验名称：学生姓名：班 级：班内序号：学 号：日 期： 实 验 报 告
实验三 排序 15 2016.12.19
第1页
北京邮电大学信息与通信工程学院
1． 实验要求 题目2
使用链表实现下面各种排序算法，并进行比较。 排序算法：
1、插入排序 2、冒泡排序 3、快速排序 4、简单选择排序 5、其他
要求：
1、测试数据分成三类：正序、逆序、随机数据
2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。
3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）
4、对2和3的结果进行分析，验证上述各种算法的时间复杂度
编写测试main()函数测试线性表的正确性
2. 程序分析
2.1 存储结构
我使用了线性表的链式存储结构，通过建立双向循环链表进行顺序存取。
每个节点分为data、next、previor。data域称为数据域，数据通过node结构存储待排序的信息；next为指针域，用来储存直接后继的地址；prior为指针域，用来储存直接前继的地址；
struct Node {
int data;
struct Node*next; struct Node*previor; };
第2页
北京邮电大学信息与通信工程学院
2.2 程序流程 (或程序结构、或类关系图等表明程序构成的内容，一般为流程图等)
建立 类对象 显示菜单 插入排序 冒泡排序 快速排序 简单选择排序 否 是否退出
结束 是 class LinkList {
private:
Node* partion(Node*first,Node*end); //快速排序一趟 public:
Node*front;
int comparision; //比较次数 int movement; //移动次数 LinkList() //无参构造 { front = new Node; front->next = NULL; front->previor = NULL; comparision = movement = 0; }
LinkList(int a[],int n); //构造函数:建立双向链表
第3页
北京邮电大学信息与通信工程学院
void insertsort(); //插入排序 void bubblesort(); //冒泡排序 void Qsort(Node*x,Node*y); //快速排序 void selectsort(); //简单选择排序 void show(); //显示排序结果 ~LinkList(); //析构函数 };
2.3 关键算法分析
构造函数：通过使用头插法建立双向链表，其关键是多设一个指针变量用于储
存上一个末节点的地址，这样才能使节点指向其上一个节点。在这次排序实验中，使用双向循环链表更方便进行遍历操作。
LinkList::LinkList(int a[],int n) {
front = new Node; front->next = NULL; front->previor = NULL;
comparision = movement = 0; Node*x = new Node; Node*s = new Node; s->data = a[n - 1]; s->next = front; s->previor = front; front->next = s; front->previor = s; x = s;
for (int i = n - 2; i >= 0; i--) {
Node*s = new Node; s->data = a[i];
s->next = front->next;
s->previor = front; front->next = s;
x->previor = s; x = s; } }
插入排序函数：将front头节点当作哨兵。从第二个有效节点开始进行插入，进
行边查找，边后移的操作。
void LinkList::insertsort() {
Node*p = front->next; Node*s = p->next; while (s!=front)
第4页