发布时间 : 星期五 文章北邮数据结构实验四链表排序更新完毕开始阅读83475fd64431b90d6d85c720
数据结构实验报告
实验名称: 学生姓名: 班 级: 班内序号: 学 号: 日 期:
实验描述:使用链表实现下面各种排序算法,并进行比较。
排序算法: 1、插入排序 2、冒泡排序 3、快速排序 4、简单选择排序 5、其他 一.程序分析
1.存储结构:双向链表
2.关键算法分析:
a)插入排序:⒈从有序数列和无序数列{a2,a3,…,an}开始进行排序;
⒉处理第i个元素时(i=2,3,…,n),数列{a1,a2,…,ai-1}是已有序的,而数列{ai,ai+1,…,an}是无序的。用ai与ai-1,a i-2,…,a1进行比较,找出合适的位置将ai插入;
⒊重复第二步,共进行n-i次插入处理,数列全部有序。 b)冒泡排序:
1.比较相邻的元素。如果第一个比第二个大,就交换他们两个。
2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤,除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
c)快速排序:一趟快速排序的算法是:
1.设置两个变量i、j,排序开始的时候:i=0,j=N-1;
2.以第一个数组元素作为关键数据,赋值给key,即key=A[0]; 3.从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将A[j]和A[i]互换;
4.从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换;
5.重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。
d)简单选择排序:设所排序序列的记录个数为n。i取1,2,…,n-1,从所有n-i+1个记录(Ri,Ri+1,…,Rn)中找出排序码最小的记录,与第i个记录交换。执行n-1趟 后就完成了记录序列的排序。 3.代码详细分析: #include
struct Node //建立节点 { int data; Node* last; Node* next; Node() { last=NULL; next=NULL; } };
class List //建立链表 {
private: Node* front; Node* rear; int length; public: List(); List(int a[],int n); void Insert(int x,Node* p); //在p后面插入节点 void Delete(Node* p); //删除p节点 void Print(); //打印 void SeqSort(); //插入排序 void BubSort(); //冒泡排序 void QuiSort(); //快速排序 void Qui(Node* first,Node* end,int* c); //快速排序的递归函数 void SelSort(); //简单选择排序 }; List::List(int a[],int n) //构造函数
{ front=new Node; length=n; rear=front; int i; Node* s; for(i=0;i
void List::Insert(int x,Node* p) { Node* s=new Node; s->data=x; s->last=p->last; p->last->next=s; p->last=s; s->next=p; }
void List::Print() { Node* p=front->next; while(p!=NULL) { cout< void List::Delete(Node* p) { Node* De=p; if(p==rear) { rear=p->last; p->last->next=NULL; delete De; } else //插入函数 //打印函数 //删除函数 { p->last->next=p->next; p->next->last=p->last; delete De; } } void List::SeqSort() //插入排序 { LARGE_INTEGER large_interger; double dff; __int64 c1, c2; QueryPerformanceFrequency(&large_interger); dff = large_interger.QuadPart; QueryPerformanceCounter(&large_interger); c1 = large_interger.QuadPart; int ccom=0; int cmove=0; Node* p=front->next->next; Node* q; Node* De; bool ifdelete; while(p!=NULL) { ifdelete=0; q=front->next; while(q!=p) { ccom++; if(q->data>=p->data) { De=p; Insert(p->data,q); ifdelete=1; break; } q=q->next; } p=p->next; if(ifdelete==1) { Delete(De); } }