当前位置:首页 » 课程大全 » 排序算法课程设计

排序算法课程设计

发布时间: 2021-02-27 10:03:17

① C语言课程设计:数据排序算法

这是一个模板,好好研究一下就会排序这部分的题了。

② 课程设计 实现拓扑排序算法

#include<stdio.h>
#include<stdlib.h>
#define MAX_VEXTEX_NUM 20
#define M 20
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode
{
int data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VEXTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum, arcnum;
}ALGraph;
typedef struct //构件栈
{
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;
void InitStack(SqStack *); //函数声明
int Pop(SqStack *, ElemType *);
void Push(SqStack *,ElemType );
int StackEmpty(SqStack *);
void CreatGraph(ALGraph *);
void FindInDegree(ALGraph , int * );
void TopologicalSort(ALGraph );
void InitStack(SqStack *S)//初始化栈
{
S->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S->base)
{
printf("memory allocation failed, goodbye");
exit(1);
}
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}
int Pop(SqStack *S,ElemType *e)//出栈操作
{
if(S->top==S->base)
{return ERROR;}
*e=*--S->top;
//printf("%d\n",e);
// return e;
return 0;
}
void Push(SqStack *S,ElemType e)//进栈操作
{if(S->top-S->base>=S->stacksize)
{
S->base = (ElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S->base)
{
printf("memory allocation failed, goodbye");
exit(1);
}
S->top = S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}*S->top++=e;
}
int StackEmpty(SqStack *S)//判断栈是否为空
{
if(S->top==S->base)
return OK;
else
return ERROR;}
void CreatGraph(ALGraph *G)//构件图
{int m, n, i;
ArcNode *p;
printf("请输入顶点数和边数:");
scanf("%d%d",&G->vexnum,&G->arcnum);
for (i = 1; i <= G->vexnum; i++)
{G->vertices[i].data = i;
G->vertices[i].firstarc = NULL;
}
for (i = 1; i <= G->arcnum; i++) //输入存在边的点集合
{
printf("\n请输入存在边的两个顶点的序号:");
scanf("%d%d",&n,&m);
while (n < 0 || n > G->vexnum || m < 0 || m > G->vexnum)
{printf("输入的顶点序号不正确 请重新输入:");
scanf("%d%d",&n,&m);
}
p = (ArcNode*)malloc(sizeof(ArcNode));
if (p == NULL)
{printf("memory allocation failed,goodbey");
exit(1);
}
p->adjvex = m;
p->nextarc = G->vertices[n].firstarc;
G->vertices[n].firstarc = p;
}
printf("建立的邻接表为:\n"); //输出建立好的邻接表
for(i = 1; i <= G->vexnum; i++)
{
printf("%d",G->vertices[i].data);
for(p = G->vertices[i].firstarc; p; p = p->nextarc)
printf("%3d",p->adjvex);
printf("\n");
}}
void FindInDegree(ALGraph G, int indegree[])//求入度操作
{
int i;
for (i = 1; i <= G.vexnum; i++)
{
indegree[i] = 0;
}
for (i = 1; i <= G.vexnum; i++)
{while (G.vertices[i].firstarc)
{indegree[G.vertices[i].firstarc->adjvex]++;
G.vertices[i].firstarc = G.vertices[i].firstarc->nextarc;
}
}
}
void TopologicalSort(ALGraph G) //进行拓扑排序
{
int indegree[M];
int i, k, n;
int count = 0;
ArcNode *p;
SqStack S;
FindInDegree(G, indegree);
InitStack(&S);
for (i = 1; i <= G.vexnum; i++)
{
printf("第%d个点的入度为%d \n", i, indegree[i]);
}
printf("\n");
for ( i = 1; i <= G.vexnum; i++)
{
if (!indegree[i])
Push(&S,i);
}
printf("进行拓扑排序输出顺序为:"); //输出结果
while(!StackEmpty(&S))
{
Pop(&S,&n);
printf("%4d",G.vertices[n].data);
count++;
for (p = G.vertices[n].firstarc; p != NULL; p = p->nextarc)
{
k = p->adjvex;
if (!(--indegree[k]))
{
Push(&S,k);
}
}

}printf("\n");

if (count < G.vexnum)
{
printf("出现错误\n");
}
else
{
printf("排序成功\n");
}
}
int main(void) //主函数
{
ALGraph G;
CreatGraph(&G);
TopologicalSort(G);
system("pause");
return 0;
}

③ 数据结构课程设计:排序算法性能比较 编写程序在运行时产生1000个随机整数,分

#include<stdio.h>
#include<stdlib.h>
#include <math.h>
#define L 8 //排序元素个数
#define FALSE 0
#define TRUE 1

typedef struct
{
int key;
char otherinfo;
}RecType;

typedef RecType Seqlist[L+1];
int num; //定义排序趟数的全局变量
Seqlist R;
//直接插入排序
void Insertsort()
{
int i,j,k,m=0;
printf("\n\t\t原始数据为(按回车键开始排序):\n\t\t");
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
for(i=2;i<=L;i++)
{
if(R[i].key<R[i-1].key)
{
R[0]=R[i];
j=i-1;
while(R[0].key<R[j].key)
{
R[j+1]=R[j];
j--;
}
R[j+1]=R[0];
}
m++;
printf("\t\t第%d趟排序结果为(按回车键继续):\n\t\t",m);
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
}
printf("\n\t\t排序的最终结果是:\n\t\t");
for(i=1;i<=L;i++)
{
printf("%5d",R[i].key);
}
printf("\n");
}
//希尔排序
void Shellsort()
{
int i,j,gap,x,m=0,k;
printf("\n\t\t原始数据为(按回车键开始排序):\n\t\t");
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
gap=L/2;
while(gap>0)
{
for(i=gap+1;i<=L;i++)
{
j=i-gap;
while(j>0)
{
if(R[j].key>R[j+gap].key)
{
x=R[j].key;
R[j].key=R[j+gap].key;
R[j+gap].key=x;
j=j-gap;
}
else
{
j=0;
}
}
}
gap=gap/2;
m++;
printf("\t\t第%d趟排序结果为(按回车键开始排序):\n\t\t",m);
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
}
printf("\n\t\t排序的最终结果是:\n\t\t");
for(i=1;i<=L;i++)
{
printf("%5d",R[i].key);
}
printf("\n");
}
//冒泡排序
void Bubblesort()
{
int i,j,k;
int exchange;
printf("\n\t\t原始数据为(按回车键开始排序):\n\t\t");
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
for(i=1;i<L;i++)
{
exchange=FALSE;
for(j=L;j>=i+1;j--)
{
if(R[j].key<R[j-1].key)
{
R[0].key=R[j].key;
R[j].key=R[j-1].key;
R[j-1].key=R[0].key;
exchange=TRUE;
}
}
if(exchange)
{
printf("\t\t第%d趟排序结果为(按回车键开始排序):\n\t\t",i);
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
}
}
printf("\n\t\t排序的最终结果是:\n\t\t");
for(i=1;i<=L;i++)
{
printf("%5d",R[i].key);
}
printf("\n");
}

int Partition(int i,int j) //i和j为形式参数,分别代表low和high
{
RecType pirot=R[i];
while(i<j)
{
while(i<j&&R[j].key>=pirot.key)
{
j--;
}
if(i<j)
{
R[i++]=R[j];
}
while(i<j&&R[j].key<=pirot.key)
{
i++;
}
if(i<j)
{
R[j--]=R[i];
}
}
R[i]=pirot;
return i;
}
//递归形式为快速排序
void Quicksort(int low,int high)
{
int pirotpos,k;
if(low<high)
{
pirotpos=Partition(low,high);
num++;
printf("\t\t第%d趟排序结果为(按回车键开始排序):\n\t\t",num);
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
Quicksort(low,pirotpos-1);
Quicksort(pirotpos+1,high);
}
}
//选择排序
void Selectsort()
{
int i,j,k,h;
printf("\n\t\t原始数据为(按回车键开始排序):\n\t\t");
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
for(i=1;i<L;i++)
{
h=i;
for(j=i+1;j<=L;j++)
{
if(R[j].key<R[h].key)
{
h=j;
}
}
if(h!=j)
{
R[0]=R[i];
R[i]=R[h];
R[h]=R[0];
}
printf("\t\t第%d趟排序结果为(按回车键开始排序):\n\t\t",i);
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
}
printf("\n\t\t排序的最终结果是:\n\t\t");
for(i=1;i<=L;i++)
{
printf("%5d",R[i].key);
}
printf("\n");
}

void Merge(int low,int mm,int high)
{
int i=low,j=mm+1,p=0;
RecType *R1;
R1=new RecType[high-low+1];
if(!R1)
{
printf("内存容量不够!");
}
while(i<=mm&&j<=high)
{
R1[p++]=(R[i].key<=R[j].key)?R[i++]:R[j++];
}
while(i<=mm)
{
R1[p++]=R[i++];
}
while(j<=high)
{
R1[p++]=R[j++];
}
for(p=0,i=low;i<=high;p++,i++)
{
R[i]=R1[p];
}
}

void MergePass(int length)
{
int i;
for(i=1;i+2*length-1<=L;i=i+2*length)
{
Merge(i,i+length-1,i+2*length-1);
}
if(i+length-1<L)
{
Merge(i,i+length-1,L);
}
}
//归并排序
void Mergesort()
{
int length,k,m=0,i;
printf("\n\t\t原始数据为(按回车键开始排序):\n\t\t");
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
for(length=1;length<L;length*=2)
{
MergePass(length);
m++;
printf("\t\t第%d趟排序结果为(按回车键开始排序):\n\t\t",m);
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
}
printf("\n\t\t排序的最终结果是:\n\t\t");
for(i=1;i<=L;i++)
{
printf("%5d",R[i].key);
}
printf("\n");
}
//堆建
void CreateHeap(int root,int index)
{
int j,temp,finish;
j=2*root;
temp=R[root].key;
finish=0;
while(j<=index&&finish==0)
{
if(j<index)
{
if(R[j].key<R[j+1].key)
{
j++;
}
}
if(temp>=R[j].key)
{
finish=1;
}
else
{
R[j/2].key=R[j].key;
j=j*2;
}
}
R[j/2].key=temp;
}//堆排序
void Heapsort()
{
int i,j,temp,k;
for(i=(L/2);i>=1;i--)
{
CreateHeap(i,L);
}
for(i=L-1,k=1;i>=1;i--,k++)
{
temp=R[i+1].key;
R[i+1].key=R[1].key;
R[1].key=temp;
CreateHeap(1,i);
printf("\t\t第%d趟排序结果为(按回车键开始排序):\n\t\t",k);
for(j=1;j<=L;j++)
{
printf("%5d",R[j].key);
}
getchar();
printf("\n");
}
}
void Heap()
{
int i;
printf("\n\t\t原始数据为(按回车键开始排序):\n\t\t");
for(i=1;i<=L;i++)
{
printf("%5d",R[i].key);
}
getchar();
printf("\n");
Heapsort();
printf("\n\t\t排序的最终结果是:\n\t\t");
for(i=1;i<=L;i++)
{
printf("%5d",R[i].key);
}
printf("\n");
}

main()
{
Seqlist S;
int i,k;
char ch1,ch2,q;
printf("\n\t\t1000个随机数产生:\n\t\t");
for(i=1;i<=1000;i++)
{

S[i].key = rand() % 999 + 1; //产生1-1000的随机数
//printf("%d\n", number); // 去掉注释显示随机数的输出}
printf("\n\t\t排序数据已经输入完毕!");
ch1='y';
while(ch1=='y'||ch1=='Y')
{
printf("\n");
printf("\n\t\t 排 序 子 系 统 \n");
printf("\n\t\t*******************************************\n");
printf("\n\t\t* 1--------更新排序数据 *\n");
printf("\n\t\t* 2--------直接插入排序 *\n");
printf("\n\t\t* 3--------希 尔 排 序 *\n");
printf("\n\t\t* 4--------冒 泡 排 序 *\n");
printf("\n\t\t* 5--------快 速 排 序 *\n");
printf("\n\t\t* 6--------选 择 排 序 *\n");
printf("\n\t\t* 7--------归 并 排 序 *\n");
printf("\n\t\t* 8--------堆 排 序 *\n");
printf("\n\t\t* 0--------返 回 *\n");
printf("\n\t\t*******************************************\n");
printf("\n\t\t 请选择菜单号(0--8):");
scanf("%c",&ch2);
getchar();
for(i=1;i<=L;i++)
{
R[i].key=S[i].key;
}
switch(ch2)
{
case '1':
printf("\n\t\t请输入%d个待排序数据(按回车键分隔):\n\t\t",L);
for(i=1;i<=L;i++)
{
scanf("%d",&S[i].key);
getchar();
printf("\t\t");
}
printf("\n\t\t排序数据已经输入完毕!");
break;
case '2':
Insertsort();
break;
case '3':
Shellsort();
break;
case '4':
Bubblesort();
break;
case '5':
printf("\n\t\t原始数据为(按回车键开始排序):\n\t\t");
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
num=0;
Quicksort(1,L);
printf("\n\t\t排序的最终结果是:\n\t\t");
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
printf("\n");
break;
case '6':
Selectsort();
break;
case '7':
Mergesort();
break;
case '8':
Heap();
break;
case '0':
ch1='n';
break;
default:
system("cls");
printf("\n\t\t 对不起,您的输入有误,请重新输入!\n");
break;
}
if(ch2!='0')
{
if(ch2=='2'||ch2=='3'||ch2=='4'||ch2=='5'||ch2=='6'||ch2=='7'||ch2=='8')
{
printf("\n\n\t\t排序输出完毕!");
printf("\n\t\t按回车键返回。");
q=getchar();
if(q!='\xA')
{
getchar();
ch1='n';
}
}
}
}
}

④ C++课程设计源代码 题目 数据排序算法

是这个把

⑤ 数据结构课程设计 排序算法分析该怎么写

CSDN 去这个网站吧,毕业论文,各种算法,反正是与计算机有关的,都可以在上面找到!

⑥ 排序算法课程设计

// 各种排序算法汇总.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;

#include <stack>
#include <time.h>
#include <stdlib.h>

template < typename T >
class SqList
{
private:
int length;
T * r;
public://接口
SqList(int n = 0);//构造长度为n的数组
~SqList()
{
length = 0;
delete r;
r = NULL;
}
void InsertSort();//顺序插入排序
void DisPlay();//输出元素
void BInsertSort();//折半插入排序
void ShellSort(int dlta[],int t);//希尔排序
void QuickSort();//快速排序
void SelectSort();//简单选择排序
void BubbleSort();//改进冒泡排序
void Bubble_Sort2();//相邻两趟是反方向起泡的冒泡排序算法
void Bubble_Sort3();//对相邻两趟反方向算法进行化简,循环体中只包含一次冒泡
void HeapSort();//堆排序
void Build_Heap_Sort();//堆排序由小到大序号建立大根堆
void MergeSort();//归并排序
void OE_Sort();//奇偶交换排序的算法

void Q_Sort_NotRecurre();//非递归快速排序
void HeapSort_3();//三叉堆排序

public://调用
void ShellInsert(int dk);//一趟希尔排序
void QSort(int low,int high);//快速排序
int Partition(int low,int high);//一趟快速排序
int SelectMinKey(int i);//从i到length中选择最小值下标
void HeapAdjust(int s,int m);//调整s的位置,其中s+1~m有序
void HeapAdjust_3(int s,int m);//三叉堆****调整s的位置,其中s+1~m有序
void Merge(T SR[],T TR[],int i,int m,int n);//归并
void MSort(T SR[],T TR1[],int s,int t);//归并
void Easy_Sort(int low,int high);//3个数直接排序
void Build_Heap(int len);//从低下标到高下标逐个插入建堆的算法***建立大根堆**但为排序

};
template < typename T >
SqList<T>::SqList(int n = 0)
{
//srand( time(0) );
length = n;
r=new T[length+1];
T t;
cout<<"随机生成"<<n<<"个值:"<<endl;
for (int i=1;i<=length;i++)
{
//cin>>t;
r[i] = rand()%1000;
//r[i] = t;
}
for (int i=1; i<=length;i++)
cout<<r[i]<<",";
cout<<endl;
}
template < typename T >
void SqList<T>::InsertSort()
{
int i,j;
for (i=2;i<=length;i++)
{
if (r[i]<r[i-1])
{
r[0]=r[i];
r[i]=r[i-1];
for (j=i-2;r[0]<r[i-2];j--)
r[j+1]=r[j];
r[j+1]=r[0];
}
}
}
template < typename T >
void SqList<T>::DisPlay()
{
int i;
cout<<length<<" 元素为:"<<endl;
for (i = 1;i < length+1;i++ )
{
cout<<r[i]<<" ,";
}
cout<<endl;
}
template < typename T >
void SqList<T>::BInsertSort()
{
int i, j, m;
int low,high;
for (i = 2;i<= length;i++)
{
r[0]=r[i];
low=1;
high=i-1;
while (low<=high)
{
m = (low+high)/2;
if ( r[0] < r[m] )
high=m-1;
else
low=m+1;
}
for ( j=i-1;j >=high+1; j--)
{
r[j+1] = r[j];
}
r[high+1] = r[0];
}
}

template < typename T >
void SqList<T>::ShellInsert(int dk)
{
int i,j;
for (i=dk+1;i<=length;i++)
if (r[i] < r[i-dk])
{
r[0] = r[i];
for ( j=i-dk; j>0 && r[0] < r[j]; j-=dk)
{
r[j+dk]=r[j];
}
r[j+dk] = r[0];
}
}
template < typename T >
void SqList<T>::ShellSort(int dlta[],int t)
{
int k=0;
for (;k<t;k++)
{
ShellInsert(dlta[k]);
}
}
template < typename T >
int SqList<T>::Partition(int low,int high)
{
int pivotkey;
r[0] = r[low];//记录枢轴值
pivotkey = r[low];
while (low < high)
{
while (low < high&& r[high] >= pivotkey)
high--;
r[low] = r[high];
while (low < high&& r[low] <= pivotkey)
low++;
r[high] = r[low];
}
r[low] = r[0];//枢轴记录到位
return low;//返回枢轴位置
}
template < typename T >
void SqList<T>::QSort(int low,int high)
{
int pivotloc;
if (low < high)
{
pivotloc = Partition(low,high);
QSort(low,pivotloc-1);
QSort(pivotloc+1,high);
}
}
template < typename T >
void SqList<T>::QuickSort()
{
QSort(1,length);
}
template < typename T >
int SqList<T>::SelectMinKey(int i)
{
int j,min=i;
for (j=i;j <= length;j++)
{
if (r[min] > r[j])
{
min = j;
}
}
return min;
}
template < typename T >
void SqList<T>::SelectSort()
{
int i,j;
T t;
for (i=1;i < length;i++)//循环length-1次不是length次
{
j=SelectMinKey(i);
if (i != j)
{
t= r[j];
r[j]=r[i];
r[i]=t;
}
}
}
template < typename T >
void SqList<T>::BubbleSort()
{
int i,j;
int flag=1;//标识位,如果出现0,则没有交换,立即停止
T t;
for (i=1;i < length && flag;i++)
{
flag = 0;
for (j=length-1;j>=i;j--)
if (r[j]>r[j+1])
{
t=r[j];
r[j]=r[j+1];
r[j+1]=t;
flag=1;
}
}
}
template < typename T >
void SqList<T>::Bubble_Sort2()
{
bool change = true;
int low = 1, high = length;
int i;
T t;
while ( (low < high) && change )
{
change = false;
for ( i = low; i < high; i++ )
{
if ( r[i] > r[i+1] )
{
t = r[i];
r[i] = r[i+1];
r[i+1] = t;
change = true;
}
}
high-=1;
for ( i = high; i > low; i-- )
{
if ( r[i] < r[i-1] )
{
t = r[i];
r[i] = r[i-1];
r[i-1] = t;
change = true;
}
}
low+=1;
}
}

template < typename T >
void SqList<T>::Bubble_Sort3()
{
int i,d=1;
bool change = true;
int b[3] = {1,0,length};//b[0]为冒泡的下界,b[ 2 ]为上界,b[1]无用
T t;
while (change)//如果一趟无交换,则停止
{
change = false;
for ( i=b[1-d]; i!=b[1+d]; i=i+d )//统一的冒泡算法
{
if ( (r[i]-r[i+d])*d > 0 )///注意这个交换条件
{
t = r[i];
r[i] = r[i+d];
r[i+d] = t;
change = true;
}
}
d = d*(-1);//换个方向
}
}
template < typename T >
void SqList<T>::HeapAdjust(int s,int m)
{
/* 已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义,本函数 */
/* 调整H.r[s]的关键字,使H.r[s..m]成为一个大顶堆(对其中记录的关键字而言) */
int j;
T rc = r[s];
for (j=2*s;j <= m;j*=2)
{
/* 沿key较大的孩子结点向下筛选 */
if (j < m && r[j] < r[j+1])
j++;/* j为key较大的记录的下标 */
if (rc >= r[j])
break;/* rc应插入在位置s上 ,无需移动*/
r[s]=r[j];
s=j;
}
r[s]=rc;/* 插入 */
}
template < typename T >
void SqList<T>::HeapSort()
{
/* 对顺序表H进行堆排序。算法10.11 */
T t;
int i;
for (i=length/2;i>0;i--)/* 把H.r[1..H.length]建成大顶堆 */
HeapAdjust(i,length);
for (i=length;i>1;i--)
{
/* 将堆顶记录和当前未经排序子序列H.r[1..i]中最后一个记录相互交换 */
t=r[1];
r[1]=r[i];
r[i]=t;
HeapAdjust(1,i-1);/* 将H.r[1..i-1]重新调整为大顶堆 */
}
}
template < typename T >
void SqList<T>::Build_Heap_Sort()
{
int i;
Build_Heap(length);
for ( i = length; i > 1; i-- )
{
T t;
t = r[i];
r[i] = r[1];
r[1] = t;
Build_Heap(i-1);
}

}
template < typename T >
void SqList<T>::Build_Heap(int len)
{
T t;
for (int i=2; i <= len; i++ )
{
int j = i;
while ( j != 1 )
{
int k = j/2;
if ( r[j] > r[k] )
{
t = r[j];
r[j] = r[k];
r[k] = t;
}
j = k;
}
}

}
template < typename T >
void SqList<T>::Merge(T SR[],T TR[],int i,int m,int n)
{
/* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] 算法10.12 */
int j,k,x;
for (j=m+1,k=i;j<=n&&i<=m;k++)/* 将SR中记录由小到大地并入TR */
{
if (SR[i]<SR[j])
TR[k]=SR[i++];
else
TR[k]=SR[j++];
}
if (i<=m)
for (x=0;x<=m-i;x++)
TR[k+x]=SR[i+x];/* 将剩余的SR[i..m]复制到TR */
if (j<=n)
for (x=0;x<=n-j;x++)
TR[k+x]=SR[j+x];/* 将剩余的SR[j..n]复制到TR */
}
template < typename T >
void SqList<T>::MSort(T SR[],T TR1[],int s,int t)
{
/* 将SR[s..t]归并排序为TR1[s..t]。算法10.13 */
int m;
T *TR2=new T[length+1];
if (s==t)
TR1[s]=SR[s];
else
{
m=(s+t)/2;/* 将SR[s..t]平分为SR[s..m]和SR[m+1..t] */
MSort(SR,TR2,s,m);/* 递归地将SR[s..m]归并为有序的TR2[s..m] */
MSort(SR,TR2,m+1,t);/* 递归地将SR[m+1..t]归并为有序的TR2[m+1..t] */
Merge(TR2,TR1,s,m,t);/* 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] */
}
}
template < typename T >
void SqList<T>::MergeSort()
{
MSort(r,r,1,length);
}
template < typename T >
void SqList<T>::OE_Sort()
{
int i;
T t;
bool change = true;
while ( change )
{
change = false;
for ( i=1;i<length;i+=2 )
{
if (r[i] > r[i+1])
{
t = r[i];
r[i] = r[i+1];
r[i+1] = t;
change = true;
}
}
for ( i=2;i<length;i+=2 )
{
if ( r[i] > r[i+1] )
{
t = r[i];
r[i] = r[i+1];
r[i+1] = t;
change = true;
}
}

}

}
typedef struct
{
int low;
int high;
}boundary;
template <typename T >
void SqList<T>::Q_Sort_NotRecurre()
{
int low=1,high=length;
int piv;
boundary bo1,bo2;
stack<boundary> st;
while (low < high)
{
piv = Partition(low,high);
if ( (piv-low < high-piv) && (high-piv > 2) )
{
bo1.low = piv+1;
bo1.high = high;
st.push(bo1);
high = piv-1;
}
else if ( (piv-low > high-piv) && (piv-low >2) )
{
bo1.low = low;
bo1.high = piv-1;
st.push(bo1);
low = piv+1;
}
else
{
Easy_Sort(low,high);
high = low;
}
}
while ( !st.empty() )
{
bo2 = st.top();
st.pop();
low = bo2.low;
high = bo2.high;
piv = Partition(low, high);
if ( (piv-low < high-piv) && (high-piv > 2) )
{
bo1.low = piv+1;
bo1.high = high;
st.push(bo1);
high = piv-1;
}
else if ( (piv-low > high-piv) && (piv-low >2) )
{
bo1.low = low;
bo1.high = piv-1;
st.push(bo1);
low = piv+1;
}
else
{
Easy_Sort(low,high);
}
}

}
template < typename T >
void SqList<T>::Easy_Sort(int low,int high)
{
T t;
if ( (high-low) == 1 )
{
if ( r[low] > r[high] )
{
t = r[low];
r[low] = r[high];
r[high] = t;
}
}
else
{
if ( r[low] > r[low+1] )
{
t = r[low];
r[low] = r[low+1];
r[low+1] = t;
}
if ( r[low+1] > r[high] )
{
t = r[low+1];
r[low+1] = r[high];
r[high] = t;
}
if ( r[low] > r[low+1] )
{
t = r[low];
r[low] = r[low+1];
r[low+1] = t;
}
}

}

template < typename T >
void SqList<T>::HeapAdjust_3(int s,int m)
{
T rc = r[s];
for (int j = 3*s-1; j <= m;j=j*3-1)
{
if (j+1<m)//有3个孩子结点
{
if ( rc>=r[j] && rc>=r[j+1] && rc>=r[j+2] )
break;
else
{
if ( r[j] > r[j+1] )
{
if ( r[j] > r[j+2] )
{
r[s]=r[j];
s=j;
}
else//r[j]<=r[j+2]
{
r[s]=r[j+2];
s=j+2;
}
}
else//r[j]<=r[j+1]
{
if ( r[j+1] > r[j+2] )
{
r[s]=r[j+1];
s=j+1;
}
else//r[j+1]<=r[j+2]
{
r[s]=r[j+2];
s=j+2;
}
}
}
}
if ( j+1==m )//有2个孩子结点
{
if ( rc>=r[j] && rc>=r[j+1] )
break;
else
{
if ( r[j] > r[j+1] )
{
r[s]=r[j];
s=j;
}
else//r[j]<=r[j+1]
{
r[s]=r[j+1];
s=j+1;
}
}
}
if (j==m)//有1个孩子结点
{
if ( rc>=r[j] )
break;
else
{
r[s]=r[j];
s=j;
}
}
}
r[s]=rc;
}

template <typename T >
void SqList<T>::HeapSort_3()
{
int i;
T t;
for (i=length/3; i>0; i--)
HeapAdjust_3(i,length);
for ( i=length; i > 1; i-- )
{
t = r[i];
r[i] = r[1];
r[1] = t;
HeapAdjust_3(1,i-1);
}
}

int _tmain(int argc, _TCHAR* argv[])
{
SqList<int> Sq(15);
//Sq.InsertSort();
//Sq.BInsertSort();
/* 希尔排序*/
// int a[5]={5,4,3,2,1};
// Sq.ShellSort(a,5);

/* Sq.QuickSort();*/

// Sq.SelectSort();

/* Sq.BubbleSort();*/

/* Sq.HeapSort();*/

/* Sq.MergeSort();*/

/* Sq.Q_Sort_NotRecurre();*/

/* Sq.Bubble_Sort2();*/
/* Sq.OE_Sort();*/
/* Sq.Bubble_Sort3();*/

/* Sq.Build_Heap_Sort();*/

Sq.HeapSort_3();

Sq.DisPlay();
system("pause");
return 1;
}

⑦ 二叉树排序算法实现(数据结构课程设计)

#include <malloc.h>
#include<stdio.h>
#define NUM 7 //宏定义
int i; //变量类型定义
typedef struct Node{
int data ; //数据域
struct Node *next; //指针域
}Node,*LNode; //用结构体构造结点及相应的指针

typedef struct Tree{
int data ;
struct Tree *left ;
struct Tree *right ;
}Tree,*LTree ; //用结构体构造树及相应的指针

CreateList( LNode Head ) //创建单链表
{
for(int i=1 ; i <=NUM ; i++) //创建循环,依次输入NUM个数据
{
LNode temp ; //中间结点
temp = (LNode) malloc( sizeof( Node ) ); //动态存储分配

temp-> next = NULL; //中间结点初始化
scanf("%2d",&temp-> data); //输入赋值到结点temp数据域
temp-> next = Head-> next ;
Head-> next = temp ; //将temp结点插入链表

}
return 1 ;//返回1
}

InsertSqTree( LTree &root , LNode temp ) //二叉树排序原则的设定
{
if(!root) //root为NULL时执行
{
root = (LTree)malloc(sizeof(Tree)); //动态存储分配

root-> left =NULL;
root-> right=NULL; //初始化
root-> data = temp-> data ; //赋值插入
return 1 ; //函数正常执行,返回1
}
else
{
if(root-> data>= temp-> data)
return InsertSqTree( root-> left , temp ) ; //比较插入左子树
else if(root-> data <temp-> data)
return InsertSqTree( root-> right , temp ); //比较插入右子树
}
return 1 ; //如果满足,就不做处理,返回1
}

void BianLiTree(LTree root) //采用中序遍历,实现将所有数字按从左向右递增的顺序排序
{
if(root) //root不为空执行
{BianLiTree(root-> left); //左递归处理至叶子结点,当root-> left为NULL时不执行
printf("%4d ",root-> data); //输出
BianLiTree(root-> right); //处理右结点
}
}

int main()
{
LNode Head = NULL;
LTree root = NULL ; //初始化
Head = (LNode) malloc(sizeof(Node)); //动态存储分配

Head-> next = NULL ; //初始化
printf("please input numbers:\n");//输入提示语句
if(!CreateList( Head )) //建单链表成功返回1不执行下一语句
return 0; //结束函数,返回0
LNode temp = Head-> next ; //将头指针的指针域赋值予中间结点
while( temp ) //temp为NULL时停止执行
{
if(!InsertSqTree( root ,temp )) //排序正常执行,返回1不执行下一语句
return 0 ; //结束函数,返回0
Head-> next = temp-> next ; //将中间指针的指针域赋值予头结点指针域
free(temp); //释放空间
temp = Head-> next ; //将头指针的指针域赋值予中间结点,以上三句实现了temp指针后移
}
printf("the result is:\n");//输出提示语句
BianLiTree(root); //采用中序遍历,输出并观察树结点
return 1; //函数正常结,返回1
}

⑧ 数据结构课程设计的各种排序算法的综合比较 哪位大神帮写一下~

排序法 平均时间 最差情形 稳定度 额外空间 备注
冒泡 O(n2) O(n2) 稳定 O(1) n小时较好
交换 O(n2) O(n2) 不稳定 O(1) n小时较好
选择 O(n2) O(n2) 不稳定 O(1) n小时较好
插入 O(n2) O(n2) 稳定 O(1) 大部分已排序时较好
基数 O(logRB) O(logRB) 稳定 O(n) B是真数(0-9),R是基数(个十百)
Shell O(nlogn) O(ns) 1<s<2 不稳定 O(1) s是所选分组
快速 O(nlogn) O(n2) 不稳定 O(nlogn) n大时较好
归并 O(nlogn) O(nlogn) 稳定 O(1) n大时较好
堆 O(nlogn) O(nlogn) 不稳定 O(1) n大时较好

⑨ 排序算法的实现与比较的课程设计

;
#include<stdio.h>
#define NUM 7 //宏定义
int i; //变量类型定义
typedef struct Node{
int data ; //数据域
struct Node *next; //指针域
}Node,*LNode; //用结构体构造结点及相应的指针

typedef struct Tree{
int data ;
struct Tree *left ;
struct Tree *right ;
}Tree,*LTree ; //用结构体构造树及相应的指针

CreateList( LNode Head ) //创建单链表
{
for(int i=1 ; i <=NUM ; i++) //创建循环,依次输入NUM个数据
{
LNode temp ; //中间结点
temp = (LNode) malloc( sizeof( Node ) ); //动态存储分配

temp-> next = NULL; //中间结点初始化
scanf("%2d",&temp-> data); //输入赋值到结点temp数据域
temp-> next = Head-> next ;
Head-> next = temp ; //将temp结点插入链表

}
return 1 ;//返回1
}

InsertSqTree( LTree &root , LNode temp ) //二叉树排序原则的设定
{
if(!root) //root为NULL时执行
{
root = (LTree)malloc(sizeof(Tree)); //动态存储分配

root-> left =NULL;
root-> right=NULL; //初始化
root-> data = temp-> data ; //赋值插入
return 1 ; //函数正常执行,返回1
}
else
{
if(root-> data>= temp-> data)
return InsertSqTree( root-> left , temp ) ; //比较插入左子树
else if(root-> data <temp-> data)
return InsertSqTree( root-> right , temp ); //比较插入右子树
}
return 1 ; //如果满足,就不做处理,返回1
}

void BianLiTree(LTree root) //采用中序遍历,实现将所有数字按从左向右递增的顺序排序
{
if(root) //root不为空执行
{BianLiTree(root-> left); //左递归处理至叶子结点,当root-> left为NULL时不执行
printf("%4d ",root-> data); //输出
BianLiTree(root-> right); //处理右结点
}
}

int main()
{
LNode Head = NULL;
LTree root = NULL ; //初始化
Head = (LNode) malloc(sizeof(Node)); //动态存储分配

Head-> next = NULL ; //初始化
printf("please input numbers:\n");//输入提示语句
if(!CreateList( Head )) //建单链表成功返回1不执行下一语句
return 0; //结束函数,返回0
LNode temp = Head-> next ; //将头指针的指针域赋值予中间结点
while( temp ) //temp为NULL时停止执行
{
if(!InsertSqTree( root ,temp )) //排序正常执行,返回1不执行下一语句
return 0 ; //结束函数,返回0
Head-> next = temp-> next ; //将中间指针的指针域赋值予头结点指针域
free(temp); //释放空间
temp = Head-> next ; //将头指针的指针域赋值予中间结点,以上三句实现了temp指针后移
}
printf("the result is:\n");//输出提示语句
BianLiTree(root); //采用中序遍历,输出并观察树结点
return 1; //函数正常结,返回1
}

热点内容
武汉大学学生会辅导员寄语 发布:2021-03-16 21:44:16 浏览:612
七年级学生作文辅导学案 发布:2021-03-16 21:42:09 浏览:1
不屑弟高考成绩 发布:2021-03-16 21:40:59 浏览:754
大学毕业证会有成绩单 发布:2021-03-16 21:40:07 浏览:756
2017信阳学院辅导员招聘名单 发布:2021-03-16 21:40:02 浏览:800
查询重庆2018中考成绩查询 发布:2021-03-16 21:39:58 浏览:21
结业考试成绩怎么查询 发布:2021-03-16 21:28:40 浏览:679
14中医医师资格笔试考试成绩查分 发布:2021-03-16 21:28:39 浏览:655
名著赏析课程标准 发布:2021-03-16 21:27:57 浏览:881
北京大学商业领袖高端培训课程 发布:2021-03-16 21:27:41 浏览:919