单链表快排

来源：二三四教育网

算法部分

//单链表快排
void QuicKsort_List(ListNode* begin, ListNode* end) {
	if (begin == end || begin->next == NULL) return ;
	ListNode* pmin = Part_List(begin, end);
	QuicKsort_List(begin, pmin);
	QuicKsort_List(pmin->next ,end );

}
//快排分割
ListNode* Part_List(ListNode* begin, ListNode* end) {
	if (begin == end || begin->next == NULL) return begin;
	ListNode* s = begin;
	ListNode* p = begin->next ;
	while (p != end) {
		if (p->data <= begin->data) {
			s = s->next;
			Swap(&s->data, &p->data);
			p = p->next;
		}
		else p = p->next;
	}
	Swap(&begin->data, &s->data);
	return s;
}
//数值交换
void Swap(int* a, int* b) {
	assert(a != NULL && b != NULL);
	int t = *a;
	*a = *b;
	*b = t;
}

全部代码

单链表头文件

#pragma once
typedef  int ElemType;
typedef struct Link_list {
	ElemType data;
	struct Link_list* next;
}ListNode ,*LinkList;

//购买节点
ListNode* BuyNode();

//初始化
ListNode* Init_List();

//打印
void Print_List(ListNode* L);

//查询
ListNode* is_Exist(ListNode* L, ElemType val);

//按值返回前驱结点
ListNode* is_Exist_Pre(ListNode* head, ElemType val);

//按元素位置返回当前结点
ListNode* FindPos(LinkList head, int pos);

//按元素位置返回当前结点的前驱结点
ListNode* FindPos_Prev(LinkList head, int pos);

//在ptr结点后插入一个元素
bool Insert_Next(LinkList head, ListNode* ptr, ElemType val);

//头插
bool Push_Front(LinkList head, ElemType val);

//尾插
bool Push_Back(LinkList head, ElemType val);

//在指定位置插入数据
bool InsertPos(LinkList head, int pos, ElemType val);

//删除元素
bool Erase_Next(LinkList head, ListNode* ptr);

//头删
bool Pop_Front(LinkList head);

//尾删
bool Pop_Back(LinkList head);

//判空
bool Is_Empty(LinkList head);

//获取元素个数
int Get_Size(LinkList head);

//删除val元素
void  Remove(LinkList head, ElemType val);

//删除所有val
void  Remove_All(LinkList head, ElemType val);

//清空
void ClearList(LinkList head);
//摧毁
void Destory_List(LinkList head);
//获取尾部指针
ListNode *Get_Endptr(LinkList head);
//逆置链表
void Inverted(ListNode* head);
//公用一个尾巴
void Union_LinkList(ListNode* La, ListNode* Lb);
//返回当前结点的前驱结点
ListNode* Get_PreNode(ListNode* head, ListNode* ptr);
//打印链表中结点的地址
void Print_List_address(ListNode* La);
//单链表快排
void QuicKsort_List(ListNode* begin, ListNode* end);
//快排分割
ListNode *Part_List(ListNode* begin, ListNode* end);
//数值交换
void Swap(int* a, int* b);

源文件

#include"My_LinkList.h"
#include<iostream>
#include<assert.h>
#include<stdlib.h>
using namespace std;

//购买节点
ListNode* BuyNode() {
	ListNode* s = (ListNode*)malloc(sizeof(ListNode));
	if (s == NULL) {
		cout << "结点申请失败！" << endl;
		return NULL;
	}
	memset(s, 0, sizeof(ListNode));
	s->next = NULL;
	return s;
}

//初始化
ListNode* Init_List() {
	ListNode* s = BuyNode();
	return s;
}

//打印
void Print_List(ListNode* head) {
	assert(head != NULL);
	ListNode *p = head->next ;
	while (p!= NULL) {
		cout << p->data << "	";
		p = p->next;
	}
	cout << endl;
}

//查询
ListNode* is_Exist(ListNode* head, ElemType val) {
	assert(head != NULL);
	ListNode* p = head;
	while (p->next != NULL) {
		p = p->next;
		if (p->data == val) {
			return p;
		}
	}
	return NULL;
}

//按值返回前驱结点
ListNode* is_Exist_Pre(ListNode* head, ElemType val) {
	assert(head != NULL);
	ListNode* s = head;
	ListNode* p = head->next ;
	while (p->next != NULL ) {
		s = p;
		p = p->next;
		if (p->data == val) {
			return s;
		}
	}
	return NULL;
}

//按元素位置返回当前结点
ListNode* FindPos(LinkList head, int pos) {
	assert(head != NULL);
	if (pos < 1) return NULL;
	LinkList p = head;
	int index = 0;
	while (p->next != NULL   &&  index<pos) {
		p=p->next ;
		index++;
	}
	return p;
}

//按元素位置返回当前结点的前驱结点
ListNode* FindPos_Prev(LinkList head, int pos) {
	assert(head != NULL);
	if (pos < 1) return NULL;
	LinkList s = head;
	LinkList p = head->next; int index = 1;
	while (p->next != NULL && index < pos) {
		s = p;
		p = p->next;
		index++;
	}
	if (p == NULL) {
		s = NULL;
	}
	return s;
}

//在ptr结点后插入一个元素
bool Insert_Next(LinkList head, ListNode* ptr, ElemType val) {
	assert(head != NULL);
	LinkList s = BuyNode();
	if (s == NULL) return false;
	s->data = val;
	s->next = ptr->next;
	ptr->next = s;
	return true;
}

//头插
bool Push_Front(LinkList head, ElemType val) {
	assert(head != NULL);
	return Insert_Next(head, head, val);
}


//获取尾部指针
ListNode* Get_Endptr(LinkList head) {
	assert(head != NULL);
	LinkList p = head;
	while (p->next != NULL) {
		p = p->next;
	}
	return p;
}

//获取尾部指针前驱指针
ListNode* Get_Endptr_Prea(LinkList head) {
	assert(head != NULL);
	LinkList s = head;
	LinkList p = head->next ;
	while (p->next != NULL) {
		s = p;
		p = p->next;
	}

	return s;
}

//获取尾部指针前驱结点
ListNode* Get_Endptr_Pre(LinkList head) {
	assert(head != NULL);
	LinkList p = head;
	LinkList s = head->next ;
	while (s->next != NULL) {
		p = s;
		s = s->next;
	}
	return p;
}


//尾插
bool Push_Back(LinkList head, ElemType val) {
	assert(head != NULL);
	ListNode* p = Get_Endptr(head);
	return Insert_Next(head, p, val);
}

//在指定位置插入数据
bool InsertPos(LinkList head, int pos, ElemType val) {
	assert(head != NULL);
	ListNode* p = FindPos_Prev(head, pos);
	return Insert_Next(head, p, val);
}

//删除元素
bool Erase_Next(LinkList head, ListNode* ptr) {
	assert(head != NULL);
	if (ptr->next == NULL) return false;
	LinkList s = ptr->next ;
	ptr->next = s->next;
	free(s);
	s = NULL;
	return true;
}

//头删
bool Pop_Front(LinkList head) {
	assert(head != NULL);
	return Erase_Next(head, head);
}

//尾删
bool Pop_Back(LinkList head) {
	assert(head != NULL);
	LinkList s = head;
	LinkList p = head->next;
	while (p->next != NULL) {
		s = p;
		p = p->next;
	}
	return Erase_Next(head, s);
}

//判空
bool Is_Empty(LinkList head) {
	assert(head != NULL);
	return NULL == head->next;
}

//获取元素个数
int Get_Size(LinkList head) {
	assert(head != NULL);
	int index = 0;
	LinkList p = head;
	while (p->next != NULL) {
		index++;
		p = p->next;
	}
	return index;
}

//删除val元素
void  Remove(LinkList head, ElemType val) {
	assert(head != NULL);
	ListNode* p = is_Exist_Pre(head, val);
	Erase_Next(head, p);
}

//删除所有val
void  Remove_All(LinkList head, ElemType val) {
	assert(head != NULL);
	LinkList p = NULL;
	while ((p = is_Exist_Pre(head, val))!=NULL) {
		Erase_Next(head, p);
	}
}

//清空
void ClearList(LinkList head) {
	assert(head != NULL);
	while (!Is_Empty(head)) {
		Pop_Back(head);
	}
}

//摧毁
void Destory_List(LinkList head) {
	assert(head != NULL);
	ClearList(head);
	free(head);
	head = NULL;
}



//逆置链表5——递归
ListNode* Reverse(ListNode* ptr) {
	assert(ptr!= NULL);
	if (ptr == NULL || ptr->next == NULL) {
		return ptr;
	}
	ListNode* fn = Reverse(ptr->next );
	ptr->next ->next=ptr;
	ptr->next = NULL;
	return fn;

}
void Inverted(ListNode* head) {
	assert(head != NULL);
	ListNode* haed = Reverse(head);
}

//逆置链表4——栈结构
//void Inverted(ListNode* head) {
//	assert(head != NULL);
//	if (head == NULL || head->next->next == NULL)return;
//	int len = Get_Size(head);
//	ElemType* stack = (ElemType*)malloc(sizeof(ElemType)*len);
//	ListNode* p = head;
//	int pos = -1;
//	while (p->next != NULL) {
//		p = p->next;
//		pos++;
//		stack[pos] = p->data;
//	}
//	p = head;
//	while (p->next != NULL) {
//		p = p->next;
//		p->data = stack[pos];
//		pos--;
//	}
//	free(stack);
//	stack = NULL;
//
//}

//逆置链表3
//void Inverted(ListNode* head) {
//	assert(head != NULL);
//	
//	ListNode* p = head->next;
//	ListNode* s = head;
//	while (p->next != NULL) {
//		ListNode* p_endPre = Get_Endptr_Prea(head);
//		ListNode* p_end = Get_Endptr(head);
//		p_end->next = s->next;
//		s->next = p_end;
//		p_endPre->next = NULL;
//		s = s->next;
//	}
//}

//逆置链表2
//void Inverted(ListNode* head) {
//	assert(head != NULL);
//	int left = 1, right = Get_Size(head);
//	while (left <= right) {
//		ListNode* p = FindPos(head, left);
//		ListNode* ptr = FindPos(head, right);
//		int tmp = p->data;
//		p->data = ptr->data;
//		ptr->data = tmp;
//		left++;
//		right--;
//	}
//}



//ListNode* FindPos(LinkList head, int pos)
//逆置链表
//void Inverted(ListNode* head) {
//	assert(head != NULL);
//	ListNode* p = head->next ;
//	ListNode* s = head;
//	int index = 0;
//	while (p->next !=NULL) {
//		ListNode* ptr = Get_Endptr(head);
//		Insert_Next(head, s, ptr->data);
//		s = s->next;
//		Pop_Back(head);
//		index++;
//	}
//}

//返回当前结点的前驱结点
ListNode* Get_PreNode(ListNode* head, ListNode* ptr)
{
	assert(head != NULL && ptr != NULL);
	if (ptr == head || head->next == ptr) return NULL;
	ListNode* p = head;
	while (p->next != NULL){
		if (p->next == ptr) {
			return p;
		}
		p = p->next;
	}
	return NULL;
}



//公用一个尾巴
void Union_LinkList(ListNode* La, ListNode* Lb) {
	assert(La->next != NULL&&Lb->next !=NULL);
	ListNode* pEnd_a = Get_Endptr( La);
	ListNode* pEnd_b = Get_Endptr(Lb);
	while (pEnd_a->data == pEnd_b->data) {
		pEnd_a = Get_PreNode(La, pEnd_a);
		pEnd_b = Get_PreNode(Lb, pEnd_b);

	}
	while (pEnd_b->next != NULL)Pop_Back(Lb);
	pEnd_b->next = pEnd_a->next;
}


//打印链表中结点的地址
void Print_List_address(ListNode* La) {
	assert(La != NULL);
	while (La->next != NULL) {
		cout << La->next << endl;
		La = La->next;
	}
}

//单链表快排
void QuicKsort_List(ListNode* begin, ListNode* end) {
	if (begin == end || begin->next == NULL) return ;
	ListNode* pmin = Part_List(begin, end);
	QuicKsort_List(begin, pmin);
	QuicKsort_List(pmin->next ,end );

}
//快排分割
ListNode* Part_List(ListNode* begin, ListNode* end) {
	if (begin == end || begin->next == NULL) return begin;
	ListNode* s = begin;
	ListNode* p = begin->next ;
	while (p != end) {
		if (p->data <= begin->data) {
			s = s->next;
			Swap(&s->data, &p->data);
			p = p->next;
		}
		else p = p->next;
	}
	Swap(&begin->data, &s->data);
	return s;
}
//数值交换
void Swap(int* a, int* b) {
	assert(a != NULL && b != NULL);
	int t = *a;
	*a = *b;
	*b = t;
}

主函数

#include"My_LinkList.h"
#include<iostream>
#include<stdio.h>
using namespace std;
int main() {
	ListNode* head = Init_List();
	int arr[8] = { 2,5,3,9,7,5,3,2 };
	for (int i = 0; i < 8; i++) {
		Push_Back(head, arr[i]);
	}
	Print_List(head);
	cout << "__________" << endl;
	QuicKsort_List(head->next , NULL);
	Print_List(head);
	cout << "__________" << endl;

}
//
//int main() {
//	ListNode* La = Init_List();
//	ListNode* Lb = Init_List();
//	int arr[] = { 2,3,4,5,6,6 };
//	int len_a = sizeof(arr) / sizeof(arr[0]);
//	int brr[] = { 1,6,3,5,6,6 };
//	int len_b = sizeof(arr) / sizeof(arr[0]);
//
//	for (int i = 0; i < len_a; i++) {
//		Push_Back(La, arr[i]);
//	}
//	for (int i = 0; i < len_b; i++) {
//		Push_Back(Lb, brr[i]);
//	}
//	Print_List(La);
//	Print_List(Lb);
//
//	Union_LinkList(La, Lb);
//	Print_List_address(La);
//	Print_List_address(Lb);
//}

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文