5-1.cpp

一些数据结构的源码

#include <stdio.h>
#include<malloc.h>
#define list_init_size 100
typedef struct
{
	int * elem;
	int length;
}sqlist;

void Initlist_seq(sqlist &l)
{
	int n;
	l.elem=(int*) malloc(list_init_size*sizeof(int));
	if(!l.elem) printf("存储分配失败！");
	l.length=0;
	printf("请输入你要输入数据的个数！\n");
	scanf("%d",&n);
	printf("请输入数据:\n");
	l.length=n;
	for(int i=1;i<=n;i++)
	
		scanf("%d",&l.elem[i]);
}

void maopaosort(sqlist l)
{
	int i,j,t,last;
	t=0;
	i=l.length;
	while(i>1)
	{
		last=1;
		for(j=1;j<i;j++)
			if(l.elem[j+1]<l.elem[j])
			{
				l.elem[0]=l.elem[j];
				l.elem[j]=l.elem[j+1];
				l.elem[j+1]=l.elem[0];
				t++;
				last=j;
			}
		i=last;
		
	}
	printf("冒泡排序后线性表各元素为：\n");
    for(i=1;i<=l.length;i++)
    {
		printf("%d",l.elem[i]);
        printf(" ");
	}
	printf("\n");
    printf("交换次数为：\n");
	printf("%d",t);
	printf("\n");
}

void insertsort(sqlist l)
{
	int i,j,t=0;
	for(i=2;i<=l.length;i++)
	{
		if(l.elem[i]<l.elem[i-1])
		{
			l.elem[0]=l.elem[i];
			l.elem[i]=l.elem[i-1];
			for(j=i-2;l.elem[0]<l.elem[j];--j)
			{
				l.elem[j+1]=l.elem[j];
				t++;
			}
			l.elem[j+1]=l.elem[0];
		}
	}
	printf("插入排序后线性表各元素为：\n");
    for(i=1;i<=l.length;i++)
    {
		printf("%d",l.elem[i]);
        printf(" ");
	} 
    printf("\n");
	printf("交换次数为：\n");
	printf("%d",t);
	printf("\n");
}

void selectsort(sqlist l)
{
	int i,j,t,a=0;
    for(i=1;i<=l.length;i++)
     for(j=i+1;j<=l.length;j++)
	  if(l.elem[j]<l.elem[i])
	  {
		  t=l.elem[i];
		  l.elem[i]=l.elem[j];
		  l.elem[j]=t;
		  a++;
	  }
   printf("简单选择排序后线性表各元素为：\n");
   for(i=1;i<=l.length;i++)
   { 
	  printf("%d",l.elem[i]);
      printf(" ");
   } 
   printf("\n");
   printf("交换次数为：\n");
   printf("%d",t);
   printf("\n");
}

int partition(sqlist l,int low,int high)
{
	int pivotkey;
	l.elem[0]=l.elem[low];
	pivotkey=l.elem[low];
	while(low<high)
	{
		while(low<high&&l.elem[high]>=pivotkey) --high;
		l.elem[low]=l.elem[high];
		//++low;
		while(low<high&&l.elem[low]<=pivotkey) ++low;
		l.elem[high]=l.elem[low];
		//--high;
	}
	l.elem[low]=l.elem[0];
	return low;
}

void qsort(sqlist l,int low,int high)
{ 
	int pivotloc;
	if(low<high)
	{
		pivotloc=partition(l,low,high);
		qsort(l,low,pivotloc-1);
		qsort(l,pivotloc+1,high);
	}
}

void quicksort(sqlist l)
{
	int i;
	qsort(l,1,l.length);
	printf("快速排序后线性表各元素为：\n");
    for(i=1;i<=l.length;i++)
    {
		printf("%d",l.elem[i]);
        printf(" ");
	} 
    printf("\n");
}

void shellinsert(sqlist l,int dk)
{
	int i,j;
	for(i=dk+1;i<=l.length;i++)
		if(l.elem[i]<l.elem[i-dk])
		{
			l.elem[0]=l.elem[i];
			for(j=i-dk;j>0&&l.elem[0]<l.elem[j];j-=dk)
				l.elem[j+dk]=l.elem[j];
			l.elem[j+dk]=l.elem[0];
		}
}

void shellsort(sqlist l,int dlta[],int t)
{
	int k,i;
	for(k=0;k<t;++k)
		shellinsert(l,dlta[k]);
	printf("希尔排序后线性表各元素为：\n");
    for(i=1;i<=l.length;i++)
    {
		printf("%d",l.elem[i]);
        printf(" ");
	} 
    printf("\n");
}

void heapadjust(sqlist l,int s,int m)
{
	int j;
	int rc;
	rc=l.elem[s];
	for(j=2*s;j<=m;j*=2)
	{
		if(j<m&&l.elem[j]<l.elem[j+1]) ++j;
		if(!(l.elem[0]<l.elem[j])) break;
		l.elem[s]=l.elem[j];s=j;
	}
	l.elem[s]=rc;
}

void heapsort(sqlist l)
{
	int i;
	for(i=l.length/2;i>0;--i)
		heapadjust(l,i,l.length);
	for(i=l.length;i>1;--i)
	{
		l.elem[0]=l.elem[1];
		l.elem[1]=l.elem[i];
		l.elem[i]=l.elem[0];
		heapadjust(l,1,i-1);
	}
	printf("堆排序后线性表各元素为：\n");
    for(i=1;i<=l.length;i++)
    {
		printf("%d",l.elem[i]);
        printf(" ");
	} 
    printf("\n");
}

void main()
{
	sqlist l;
	int a,i;
	int dlta[3];
	Initlist_seq(l);
	while(1)
	{
		printf("请输入要执行的操作：1为冒泡排序，2为插入排序，3为简单选择排序，4为快速排序,5为希尔排序，6为堆排序，0为退出\n");
		scanf("%d",&a);
		if(a==1)
			maopaosort(l);
		if(a==2)
			insertsort(l);
		if(a==3)
			selectsort(l);
		if(a==4)
			quicksort(l);
		if(a==5)
		{
			printf("请输入希尔排序3趟排序中各趟的分组数：\n");
	        for(i=0;i<3;i++)
				scanf("%d",&dlta[i]);
        	//printf("\n");
			shellsort(l,dlta,3);
		}
		if(a==6)
			heapsort(l);
		if(a==0) break;
	}
}