数据结构教程实验七链表排序的实现_本章使用顺序表作为存储结构,现请用链表实现第3题。

实验七  链表排序的实现

一、实验目的

掌握链式存储结构下直接插入排序和简单选择排序的基本思想、排序过程、算法实现，并与顺序存储结构下实现进行对比。

二、实验环境

1.硬件：每个学生需配备计算机一台。

2.软件：Windows操作系统+Visual C++。

三、实验要求

1．建立一个先进先出的链表，采用链表实现直接插入排序、简单选择排序算法。

2. 比较各种算法的运行速度。

3. 输入数据：数据域（data）设定为整型。以关键字序列（265，301，751，129，937，863，742，694，76，438）作为输入数据，采用上述方法进行排序。

4．将建表、遍历表、简单选择排序和直接插入排序分别定义一个子函数，在主函数中调用它们。

四、实验内容

1．建表类C函数。

void creat(linklist &L,int n)//创建单链表
{
	L=(linklist)malloc(sizeof(Lnode));
	q=L;
	for(i=1;i<=n;i++)
	{
      p=(linklist)malloc(sizeof(Lnode));
	  scanf(p->data);
	q->next=p;
	  q=p;
	}
q->next=NULL;
	}//创建完毕

2．直接插入排序的基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已排序好的子文件中的适当位置，直到全部记录插入完成为止。

3．简单选择排序的基本思想：第i趟排序开始时，当前有序区和无序区分别为R[1‥i-1]和R[i‥n]（1≤i≤n-1），该趟排序则是从当前无序区中选择出关键字最小的记录R[k]，将它与无序区的的第一个记录R[i]交换，有序区增加一个记录，使R[1‥i],和R[i+1‥n]分别为新的有序区和新的无序区。如此反复进行，直到排序完毕。

#include<stdio.h>
#include<stdlib.h>
//定义存储结构
typedef int KeyType;
typedef int InfoType;
typedef struct{
	KeyType key;
	InfoType data;
}RecType;
//遍历顺序表
void Trabser(RecType R[],int n){
	int i;
	for(i=0;i<n;i++){
		printf("%5d%5d\n",R[i].key,R[i].data);
	}
}

1.直接插入排序子函数

void InsertSort(RecType R[],int n){
	int i,j;
	RecType tmp;
	for(i=1;i<n;i++){
		if(R[i].key<R[i-1].key){
			tmp=R[i];
			j=i-1;
			do{
				R[j+1]=R[j];
				j--;
			}while(j>=0 && R[j].key>tmp.key);
			R[j+1]=tmp;
		}
	}
}

2.折半插入排序

void BinInsertSort(RecType R[],int n){
	int i,j,low,high,mid;
	RecType tmp;
	for(i=1;i<n;i++){
		if(R[i].key<R[i-1].key){
			tmp=R[i];
			low=0;
			high=i-1;
			while(low<=high){
				mid=(low+high)/2;
				if(tmp.key<R[mid].key)
					high=mid-1;
				else
					low=mid+1;
			}
			for(j=i-1;j>=high+1;j--){
				R[j+1]=R[j];
			}
			R[j+1]=tmp;
		}
	}
}

3.希尔排序

void ShellSort(RecType R[],int n){
	int i,j,d;
	RecType tmp;
	d=n/2;
	while(d>0){
		for(i=d;i<n;i++){
			tmp=R[i];
			j=i-d;
			while(j>=0 && tmp.key<R[j].key){
				R[j+d]=R[j];
				j=j-d;
			}
			R[j+d]=tmp;
		}
		d=d/2;
	}
}

4.冒泡排序

void BubbleSort(RecType R[],int n){
	int i,j;
	RecType tmp;
	for(i=0;i<n-1;i++){
		for(j=n-1;j>i;j--){
			if(R[j].key<R[j-1].key){
				tmp=R[j];
				R[j]=R[j-1];
				R[j-1]=tmp;
			}
		}
	}
}

4.1改进的冒泡排序

void BubbleSort1(RecType R[],int n){
	int i,j;
	bool exchange;
	RecType tmp;
	for(i=0;i<n-1;i++){
		exchange=false;
		for(j=n-1;i>i;j--){
			if(R[j].key<R[j-1].key){
				tmp=R[i];
				R[j]=R[j-1];
				R[j-1]=tmp;
				exchange=true;
			}
		}
		if(!exchange) return;
	}
}

5.快速排序

int partition(RecType R[],int s,int t){
	int i=s,j=t;
	RecType tmp=R[i];
	while(i<i){
		while(j>i && R[j].key>=tmp.key) j--;
		R[i]=R[j];
		while(i<j&&R[i].key<=tmp.key) i++;
		R[j]=R[i];
	}
	R[i]=tmp;
	return i;
}
void QuickSort(RecType R[],int s,int t){
	int i;
	if(s<t){
		i=partition(R,s,t);
		QuickSort(R,s,i-1);
		QuickSort(R,i+1,t);
	}
}

6.简单选择排序

void SelectSort(RecType R[],int n){
	int i,j,k;
	RecType tmp;
	for(i=0;i<n-1;i++){
		k=i;
		for(j=i+1;j<n;j++){
			if(R[j].key<R[k].key) k=j;
		}
		if(k!=i){
			tmp=R[i];
			R[i]=R[k];
			R[k]=tmp;
		}
	}
}

7.堆排序

void sift(RecType R[],int low,int high){
	int i=low,j=2*i;
	RecType tmp=R[i];
	while(i<=high){
		if(j<high && R[j].key<R[j+1].key) j++;
		if(tmp.key<R[j].key){
			R[i]=R[j];
			i=j;
			j=2*i;
		}
		else break;
	}
	R[i]=tmp;
}
void HeapSort(RecType R[],int n){
	int i;
	RecType tmp;
	for(i=n/2;i>=1;i--) sift(R,i,n);
	for(i=n;i>=2;i--){
		tmp=R[1];
		R[1]=R[i];
		R[i]=tmp;
		sift(R,1,i-1);
	}
}
 
//二路归并排序
void Merge(RecType R[],int low,int mid,int high){
	RecType *R1;
	int i=low,j=mid+1,k=0;
	R1=(RecType *)malloc((high-low+1)*sizeof(RecType));
	while(i<=mid && j<=high){
		if(R[i].key<=R[j].key){
			R1[k]=R[i];
			i++;
			k++;
		}
		else{
			R1[k]=R[j];
			j++;
			k++;
		}
	}
	while(i<=mid){
		R1[k]=R[i];
		i++;
		k++;
	}
	while(j<=high){
		R1[k]=R[j];
		j++;
		k++;
	}
	for(k=0,i=low;i<=high;k++,i++){
		R[i]=R1[k];
	}
	free(R1);
}
 
//对整个排序序列进行一趟归并
void MergePass(RecType R[],int length,int n){
	int i;
	for(i=0;i+2*length-1<n;i=i+2*length)
		Merge(R,i,i+length-1,i+2*length-1);
	if(i+length-1<n-1)
		Merge(R,i,i+length-1,n-1);
}
 
 
void MergeSort(RecType R[],int n){
	int length;
	for(length=1;length<n;length=2*length)
		MergePass(R,length,n);
}
 
 
void main(){
	RecType a[10]={{3,4},{5,4},{1,2},{6,5},{2,2},{13,4},{0,99},{11,54},{15,23},{7,9}};
	Trabser(a,10);
 
printf("堆排序:\n");
	HeapSort(a,10);
	Trabser(a,10);
	printf("直接插入排序:\n");
	InsertSort( a,10);
	Trabser(a,1);
	printf("折半直接插入排序:\n");
	BinInsertSort(a,10);
	Trabser(a,10);
	printf("希尔排序:\n");
	ShellSort(a,10);
	Trabser(a,10);
	printf("冒泡排序:\n");
	BubbleSort(a,10);
	Trabser(a,10);
	printf("快速排序:\n");
	QuickSort(a,0,9);
	Trabser(a,10);
	printf("简单选择排序:\n");
	SelectSort(a,10);
	Trabser(a,10);
	printf("二路归并排序:\n");
	MergeSort(a,10);
	Trabser(a,10);
	
	printf("堆排序:\n");
	HeapSort(a,10);
	Trabser(a,10);
}

五、思考题

1．在链式存储结构下实现冒泡排序。

实现程序：

#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
 
typedef struct Node
{
	ElemType pData;
	Node* pNext;
}Node,*pList;
 
void Init(pList* ihead)
{
	*ihead = (pList)malloc(sizeof(Node));
	if (*ihead == NULL)exit(0);
	(*ihead)->pNext = NULL;
	(*ihead)->pData = 0;
}
void Insert(pList head, ElemType val)
{
	pList pCur = head;
	for (int i = 0; i < head->pData; ++i)
	{
		pCur = pCur->pNext;
	}
	pList newNode = (pList)malloc(sizeof(Node));
	newNode->pData = val;
	newNode->pNext = NULL;
	pCur->pNext = newNode;
	head->pData++;
}
void Show(pList head)
{
	pList pCur = head->pNext;
	for (int i = 0; i < head->pData; ++i)
	{
		printf("%d  ", pCur->pData);
		pCur = pCur->pNext;
	}
	printf("\n");
}
 
void ListSort(pList head)
{
	pList pCur = head->pNext;
	pList pAfter = pCur;
	for (int i = 0; i < head->pData - 1; ++i)
	{
		pCur = head->pNext;
		pAfter = pCur->pNext;
		for (int j = 0; j < head->pData - i-1; ++j)
		{
			if (pAfter->pData < pCur->pData)
			{
				ElemType tmp = pAfter->pData;
				pAfter->pData = pCur->pData;
				pCur->pData = tmp;
			}
			pCur = pCur->pNext;
			pAfter = pAfter->pNext;
		}
	}
}
void Destroy(pList head)
{
	pList pCur = head;//->pNext;
	for(int i=0;i<head->pData-1;i++)
	{
		head->pNext = pCur ->pNext;
		free(pCur);
	}
}
//主函数
void main()
{
	pList head;
	Init(&head);
	for (int i = 0; i < 10; ++i)
	{
		Insert(head, rand()%10+1);
	}
	Show(head);
	ListSort(head);
	Show(head);
    Destroy(head);
}

运行结果：

测试结果：

通过！

2.在链式存储结构下快速排序。

实现程序：

#include <iostream>
#include <ctime>
#define LEN 20
#define MAX_VAL 100
using namespace std;
// 链式结构元素
struct elem
{
	elem()
	{
		value = 0;
		next = NULL;
	}
	int value;
	elem * next;
};
// 链式结构
struct node
{
	node()
	{
		head = tail = NULL;
	}
	elem* head;
	elem* tail;
};
// 比较函数
int compare_node(elem* elem_1, elem* elem_2)
{
	if(elem_1->value < elem_2->value)
	{
		return -1;
	}
	else if(elem_1->value == elem_2->value)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}
elem* partition(elem** head, elem* tail, int sort_type)
{
	elem* newHead = *head;       
	elem* headPtr = *head;       
	elem* curPtr = (*head)->next;  
	elem* prePtr = *head;
	while(curPtr != tail)         
	{
		if(compare_node(headPtr, curPtr) == sort_type)
		{
			prePtr->next = curPtr->next;
			curPtr->next = newHead;
			newHead = curPtr;
			curPtr = prePtr->next;
		}
		else
		{
			prePtr = curPtr;
			curPtr = curPtr->next;
		}
	}
	*head = newHead;
	return headPtr;
}
void quickSort(elem** head, elem* tail, int sort_type)
{
	if(*head == tail) return;
	elem* mid = partition(head, tail, sort_type);
	elem** head_1 = head;
	elem** head_2 = &mid->next;
	quickSort(head_1, mid, sort_type);
	quickSort(head_2, tail, sort_type);
	mid->next = *head_2;
	*head = *head_1;
}
//主函数
void main()
{
	node* nptr = new node();
	srand(time(NULL));
	for(int i = LEN; i >= 1; i--)
	{
		int value = rand() % MAX_VAL + 1;
		if(nptr->head == NULL)
		{
			nptr->head = nptr->tail = new elem();
			nptr->head->value = value;
		}
		else
		{
			elem* tempPtr = new elem();
			tempPtr->value = value;
			nptr->tail->next = tempPtr;
			nptr->tail = nptr->tail->next;
		}
	}
	
	elem** tempHead = &(nptr->head);
	quickSort(tempHead, NULL, -1);
	nptr->head = *tempHead;
	elem* tempPtr = nptr->head;
	while(tempPtr)
	{
		cout<<tempPtr->value<<" ";
		tempPtr = tempPtr->next;
	}
	printf("\n");
}

运行结果：

测试结果：

通过！

六、实验总结

通过本次实验学习了练习了链式存储的直接插入排序、简单选择排序、快速排序、冒泡排序等几种排序方式，对排序又有了新的认识。