数据结构第三次实验+第二题链表排序

北京邮电大学信息与通信工程学院

数据结构实验报告

实验名称： 实验三——排序 学生姓名： XXX 班 级： xxxxxxxxxxx 班内序号： 学 号：

日 期： 2018年6月3日

1． 实验要求

实验目的：通过选择下面两个题目之一，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。

实验内容：使用链表实现下面各种排序算法，并进行比较。 排序算法：

1、插入排序 2、冒泡排序 3、快速排序 4、简单选择排序 5、其他

要求：

1、测试数据分成三类：正序、逆序、随机数据

2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。

3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）

4、对2和3的结果进行分析，验证上述各种算法的时间复杂度

编写测试main()函数测试线性表的正确性。

2. 程序分析

2.1 存储结构

第1页

北京邮电大学信息与通信工程学院

单链表，储存每个元素值同时，储存该元素的直接后继元素位置信息。即数据域（data），指针域（next）。 struct Node

{

int data;

struct Node *next;

};

2.2 关键算法分析

链表的建立：

Linklist::Linklist (int a[],int n) { }

front = new Node; Node *r = front ;

for(int i=0;i

r->next = NULL;

Node *s = new Node; s->data = a[i]; r->next = s; r=s;

尾插法创建链表：①堆中建立新节点②将a[i]写入新节点data域③新节点加入链表r->next=s.

④修改尾指针r=s.

简单选择排序：

void Linklist ::Link_Selectsort (int n) {

Node *p=front->next ;

int a=0,b=0; //a记载比较次数，b记载移动次数 while(p!=NULL) {

Node *s =p; //s指向最小节点 Node *q=p->next ; while(q!=NULL)

第2页

北京邮电大学信息与通信工程学院

}

}

{ } if(p!=s) { }

p=p->next ;

int t=p->data ;p->data =s->data ;s->data =t; //交换节点值 b=b+3;

if(q->datadata) s=q; a++; q=q->next ;

Print(n,a,b);

建立p节点记载有序区最后节点的下一个节点，s节点则记载无序区的最小节点，q节点用于遍历链表无序区，找出最小值。每次循环中q都找到无序最小节点，用s指向该节点，后

p和s节点值交换。时间复杂度为O（n^2）

直接插入排序：

void Linklist ::Link_Insertsort(int n) {

Node *p=front;

Node *q=front->next ; //q为无序区第一个节点的前驱 int a=0,b=0; //a记录比较次数，b记录移动次数 while(p->next !=NULL) {

p=front; //初始化p为有序区的第一个前驱 while(q->next !=NULL&&p!=q) {

a++;

第3页

北京邮电大学信息与通信工程学院

}

}

}

if(p->next ->data>q->next ->data ) //比较，交换节点顺序 { }

p=p->next ;

Node *s=q->next ;

q->next =s->next ; //摘除s节点 s->next =p->next ; //插到p节点之后 p->next =s; break;

b=b+3;

if(p==q) q=q->next ; //若本躺排序无节点交换，则q点下移 p=q; //当q到链尾时，用于结束循环

Print(n,a,b);

① 指针p指向有序区的待比较节点前驱（初始化时即front节点）②指针q指向无序区第

一个元素的前驱Ⅰ：若无序区的第一个节点值较大，则p下移，直到p=q为止Ⅱ：若无序区第一个元素节点值较小，则用指针s指向该节点，然后摘除s节点，插入到p节点后继位置，即本趟循环结束。

时间复杂程度平均为O(n^2),最好为O(n)，最坏为

p……①q②⑤……x④③O(n^2).

冒泡排序：

void Linklist ::Link_Bubblesort (int n)

第4页

北京邮电大学信息与通信工程学院

{ }

Node *p,*r; p=front->next ;

r=NULL; //尾指针

int a=0,b=0; //a记载比较次数，b记载交换次数 while(p!=NULL&&r!=front->next ) { }

Print(n,a,b);

p=front->next ; //初始化p到链表头部 while(p->next !=r) { }

r=p; //尾指针前移

if(p->data >p->next ->data ) //相邻反序，则交换data域 { }

p=p->next ; a++;

int t=p->data ;

p->data =p->next ->data ; p->next ->data =t; b=b+3;

①每趟排序，指针p指向无序区的待比较的节点，初始化时p指向无序区的第一个节点。②指针r指向有序区的第一个节点，初始化，r=NULL。③从p指针开始，前后两个节点的元素值比较，若反序则交换元素的data，否则p下移，直到计较到r为止，本趟排序完成。④一趟排序后，将尾指针前移一位，即r=p，直到r为第一个元素排序结束。

时间复杂程度平均为O(n^2)，最好为O(n),最坏为O(n^2).

第5页