链表排序北邮数据结构实验


数 结 构

实
验
报
告




实验名称：________链表排序___________
学生姓名：_____________________
班 级：________________
班序号：_________________________
学 号：________________
日 期：_______________
1．实验求
链表实现面种排序算法进行较
排序算法：1插入排序
2泡排序
3快速排序
4简单选择排序
5
求：1测试数分成三类：正序逆序机数
2三类数较述排序算法中关键字较次数移动 次数（中关键字交换计3次移动）
3三类数较述排序算法中算法执行时间精 确微秒（选作）
423结果进行分析验证述种算法时间复杂度编写测试main()函数测试排序算法正确性
2 程序分析
21 存储结构
双链表
Data Perior Next


22 程序流程 (程序结构类关系图等表明程序构成容般流程图等)







开始


读取数


选择排序方式



输出排序结果

结束



23 关键算法分析
定义节点：
struct Node{
int data
Node* next
Node* period
}
插入排序：
void InsertionSort(Node*qint n){
Node*firstq
Node*teqq
Node*pq>next
Node*pointp
int wtime0compar0
while(pNULL){
compar+1
if(p>data

period>data){
wp>data
teqp>period
while(teqNULL){
compar+1
if(teq>data>w){
teq>next>datateq>data
time+1
if(teq>periodNULL)
{teq>dataw
time+1}
}
else{
teq>next>dataw
time+1
break}
teqteq>period
}
compar1

}

pp>next

}
cout<<插入排序序列：
while(firstNULL){
cout<data<<
firstfirst>next}
cout<<＼n插入排序较次数< cout<<插入排序移动次数<

}
链表分序区序区分序区元素插入序区相应位置
次首先找序区中链节然摘链表新位置插入
时间复杂度：O(n^n)
空间复杂度：O(n)

泡排序：
void BubblingSort(Node*qint n){
Node* tep
int qu
int time0
int compar0
tepq
for(int k0k tepq
do{ compar+1
if(tep>data>tep>next>data){
qutep>data
tep>datatep>next>data
tep>next>dataqu
time+3}
teptep>next
}while(tep>nextNULL)
}
cout<<泡排序序列：
while(qNULL){
cout<data<<
qq>next
}
cout<<＼n泡排序较次数< cout<<泡排序移动次数<
}
数组实现样进行n1趟趟前面数面数进行交换趟实现趟放面
时间复杂度：O（N^2）
空间复杂度O(n)

选择排序：
void SelectSort(Node*qint n){
Node*i*j*s*first
firstiq
int w0
int time0compar0
while(iNULL){
sji
while(sNULL){
compar+1
if(s>datadata)
js
ss>next}
wi>data
i>dataj>data
j>dataw
if(ij)
time+3
ii>next}
cout<<简单选择排序序列：
while(firstNULL){
cout<data<<
firstfirst>next}
cout<<＼n简单选择排序较次数< cout<<简单选择排序移动次数<
}
轮找数第i趟交换交换n趟泡排序优化交换次数
时间复杂度：O(n^2)
空间复杂度：O(n)

快速排序：
void FastSort(Node*lowNode*high){
Node* beginlow
Node *pivotlow
if(lowhigh){
pivotPartion(lowhigh)
if(pivotlow) FastSort(lowpivot>period)
if(pivothigh) FastSort(pivot>nexthigh)
}

}
Node* Partion(Node*lowNode*high){
Node* Lnew Node
L>datalow>data
while(lowhigh){
while(lowhigh&&high>data>L>data)
{highhigh>period
rcompar+1}
rcompar+1
if(lowhigh)rtime+1
low>datahigh>data

while(lowhigh&&low>datadata)
{lowlow>next
rcompar+1}
rcompar+1
if(lowhigh)rtime+1
high>datalow>data
}
low>dataL>data
return low
}
次第作轴值交换次放左面放右面
接着递轴值左面链表右面链表分做相操作直链结止
时间复杂度：O（nlog n）
空间复杂度：调栈空间O（log2n）




24
总体较种排序性：
排序方法
均情况
情况
坏情况
插入排序
O(n2)
O(n)
O(n2)
泡排序
O(n2)
O(n)
O(n2)
快速排序
O(nlog2n)
O(nlog2n)
O(n2)
简单选择排序
O(n2)
O(n2)
O(n2)


















3 程序运行结果分析




4 总结
41实验难点关键点
1通数组排序较链表排序花时间更长增加指针移动
2递调排序算法时间较长涉函数调进栈出栈问题



42心体会
通次试验进步链表应进步解时排序种基数操作较深刻认识时排序方式链表排序代码编写时明白情况处理方式养成更严谨编写代码思维方式


附：程序代码
#include
#include
using namespace std
int rtime0rcompar0
struct Node{
int data
Node* next
Node* period
}
void InsertionSort(Node*qint n)
void BubblingSort(Node*qint n)
void FastSort(Node*lowNode*high)
void SelectSort(Node*qint n)
Node* Partion(Node*lowNode*high)
void main(){
int data[200]
int k1
Node* q*first
ifstream ifile(DTESTdatatxt)
int i0n0
cout<<文件读入数：< while(ifile>>data[i]){
cout< i++
n++
}
Node* pnew Node
p>datadata[0]
p>nextNULL
p>periodNULL
firstp
while(k qnew Node
q>datadata[k]
q>periodp
p>nextq
pq
k++
}
q>nextNULL
Node*lastq
qfirst
cout<<选择排序方式：<cout<<1插入排序＼n2泡排序＼n3快速排序＼n4简单选择排序＼n5退出<int choice
cin>>choice
while((choice1)&(choice2)&(choice3)&(choice4)&(choice5)){
cout<<选项请重新输入
cin>>choice}
switch(choice){
case 1InsertionSort(firstn)
break
case 2BubblingSort(firstn)
break
case 3FastSort(firstlast)
cout<<快速排序序列：
while(firstNULL){
cout<data<<
firstfirst>next
}
cout<<＼n快速排序较次数< cout<<快速排序移动次数< break
case 4SelectSort(firstn)
break
case 5return
}

system(pause)
}
void BubblingSort(Node*qint n){
Node* tep
int qu
int time0
int compar0
tepq
for(int k0k tepq
do{ compar+1
if(tep>data>tep>next>data){
qutep>data
tep>datatep>next>data
tep>next>dataqu
time+3}
teptep>next
}while(tep>nextNULL)
}
cout<<泡排序序列：
while(qNULL){
cout<data<<
qq>next
}
cout<<＼n泡排序较次数< cout<<泡排序移动次数<
}
void SelectSort(Node*qint n){
Node*i*j*s*first
firstiq
int w0
int time0compar0
while(iNULL){
sji
while(sNULL){
compar+1
if(s>datadata)
js
ss>next}
wi>data
i>dataj>data
j>dataw
if(ij)
time+3
ii>next}
cout<<简单选择排序序列：
while(firstNULL){
cout<data<<
firstfirst>next}
cout<<＼n简单选择排序较次数< cout<<简单选择排序移动次数<
}
void InsertionSort(Node*qint n){
Node*firstq
Node*teqq
Node*pq>next
Node*pointp
int wtime0compar0
while(pNULL){
compar+1
if(p>data

period>data){
wp>data
teqp>period
while(teqNULL){
compar+1
if(teq>data>w){
teq>next>datateq>data
time+1
if(teq>periodNULL)
{teq>dataw
time+1}
}
else{
teq>next>dataw
time+1
break}
teqteq>period
}
compar1

}

pp>next

}
cout<<插入排序序列：
while(firstNULL){
cout<data<<
firstfirst>next}
cout<<＼n插入排序较次数< cout<<插入排序移动次数<

}
void FastSort(Node*lowNode*high){
Node* beginlow
Node *pivotlow
if(lowhigh){
pivotPartion(lowhigh)
if(pivotlow) FastSort(lowpivot>period)
if(pivothigh) FastSort(pivot>nexthigh)
}

}
Node* Partion(Node*lowNode*high){
Node* Lnew Node
L>datalow>data
while(lowhigh){
while(lowhigh&&high>data>L>data)
{highhigh>period
rcompar+1}
rcompar+1
if(lowhigh)rtime+1
low>datahigh>data

while(lowhigh&&low>datadata)
{lowlow>next
rcompar+1}
rcompar+1
if(lowhigh)rtime+1
high>datalow>data
}
low>dataL>data
return low
}






文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档