c语言单链表集合的排序升序去重,单链表的排序

客官°小女子只卖身不卖艺 2022-10-15 00:59 166阅读 0赞

链表的排序

2015/4/17 星期五 下午 18:25:04

一、顺序表的排序

对顺序表的排序其实就是对结构体中的关键字的排序。

c语言版：

自定义结构体： typedef struct node

int age;

int height;

int width;

\}Node;

现在想根据其中的age排序，用c语言实现有两种：

1、自定义交换函数，然后用常用的交换排序的方法进行排序就行了。这里用快速排序排序实现：

快排实现： //自定义结构体交换

void swap(Node \*a, Node \*b) //指定排序的节点

Node t = \*a;

\*a = \*b;

\*b = t;

//快排递归实现

void QuickSort(ElemType \*elem, int left, int right) //注意这里是闭区间

if(left < right)

int temp = elem\[right\].age; //这里要指定是按age排序的

int i = left-1;

int j = left;

while(j < right)

if(elem\[j\].age <= temp) //这里也要指定 <= 可以用

算法平均复杂度：O(nlogn)，最坏情况复杂度：O(n2)。空间复杂度O(n)。

2、 当然c语言中也内置了排序算法qsort，位于stdlib.h头文件中，核心是用快排实现的。

函数原型：

void qsort(void \*base, int nelem, int width, int (\*fcmp)(const void \*,const void \*));

参数含义：1 待排序数组首地址。 2 数组中待排序元素数量。 3 各元素的占用空间大小。 4 指向函数的指针

函数关键的比较函数：

这个函数是自定义对对象如何排序的方法。可以对整数，对字符串，对自定义结构体，都可以排序，从大到小，或者从小到大。比较函数一般这样写: int cmp(const void\* a, const void\* b)

return (\*(Node\*)a).age - (\*(Node\*)b).age;

结构体节点比较就是这样写。返回的是一个整型值，

也可以把减号换为>号，就是从大到小排序的。

比较函数返回大于0，qsort就认为 a>b , 如果比较函数返回等于0

qsort就认为a 和b 这两个元素相等，返回小于零 qsort就认为 a

c++版：

由于c++是包括了c语言，所以上面的快排，在c++中依然能运行通过。

这里，我来介绍一下C++中更好地办法去排序。

1、使用重载运算符，达到给结构体新的比较方法，来实现排序的目的。说白了就是创建结构体，定义两个结构体比较的时候，是按哪个字段比较。直接上代码：

注意：c++中可以不带typedef 来给结构体”披外套.

struct Node

int age;

itn height;

int width;

bool operator

经过上面的定义后，接着写

Node a, b; 并给字段赋过值后，再比较a

这样的话，上面的快速排序的代码，就不用特意指定按age排序了。结构体可以直接赋值，这里就不用重载=号了。

交换代码和上面的一样。改写上面的快速排序代码：

void QuickSort(ElemType \*a, int left, int right)

if(left < right)

ElemType temp = a\[right\]; //这里不用指定是age，具有通用型。

int i = left-1;

int j = left;

while(j < right)

if(a\[j\] < a\[right\])

\++i;

Swap(&a\[j\],&a\[i\]);

j++;

Swap(&a\[i+1\],&a\[right\]);

int r = i+1;

QuickSort(a, left, r-1);

QuickSort(a, r+1, right);

2、使用sort，同样c++中也有特有的排序函数，sort,它的内部是很多高效率的排序算法的整合，根据待排序的数据量选择不同的排序方法，是时间最优。

该函数位于头文件\#include中。

函数原型:使用了模板类， 就是第三个参数(自定义排序方式)是可选的。

template< class RandomIt >

void sort( RandomIt first, RandomIt last ) (1);

template< class RandomIt, class Compare >

void sort( RandomIt first, RandomIt last, Compare comp ); (2)

sort使用的c++中的模板template， 就可以对任何定义了比较关系的集合进行排序了。模板类，相当于纯面向对象语言，如c\#和Java，中的泛型概念。

如何使用sort?

1、配合结构体中的重载一起使用：

我们在上面定义了重载’ 直接sort(node,node+n);两个参数，相当于数组的始末指针。

不过注意，这里是按从小到大的顺序排的，因为上面重载的时候是age>b.age,结果就是从大到小排序了。

2、不使用结构体运算符的重载，使用sort的第三个参数(自定义排序方法)来实现排序的效果。 bool cmp(ElemType a, ElemType b)

return a.age > b.age;

这样的话主函数里用的时候写sort(a,a+n,cmp);就能排序了。

二、链式表的排序

单链表不适合快速排序，双向链表才适合快速排序，这里我们用选择排序法排序单链表，用快速排序法，排序双向链表：

单链表

定义单链表： typedef struct LinkNode

DataType data;

struct LinkNode \*next; //指向后继节点

\}Linknode;

有关选择排序的知识，请看这里：wikipedia:选择排序；

直接上代码： void Sort(LinkNode \*L)

LinkNode \*p = L->next;

LinkNode \*min = p;

while(p)

min = p;

LinkNode \*q = L->next;

while(q)

if(q->data < min->data)

min = q;

q = q->next;

Swap(p, min); //这里很关键，如何交换两个节点的值，而不改变节点的指针指向？

p = p->next;

下面画图来解释：

实际代码：

inline void Swap(LinkNode \*p, Linknode \*q)

LinkNode temp = \*p;

temp.next = q->next;

q->next = p->next;

\*p = \*q;

\*q = temp;

\* 双向链表实现快速排序

1、双向链表定义：

struct Node

int data;

struct Node \*pri, \*next;

\};

2、新建双链表

Node\* CreateDulNode(int \*a, int n) //将数组元素存到链表中

Node \*head = (Node\*)malloc(sizeof(Node));

head->next = NULL;

head->pri = NULL;

Node \*p = head;

int i = 0;

Node \*q = NULL;

while (idata = a\[i\];

q->next = p->next;

q->pri = p;

p->next = q;

p = q;

i++;

q->next = head;

head->pri = q;

return head;

3、快速排序 //其实就是数组的排序原理，有些小细节要注意

//调用QuickSort(L->next, L->pri);

void QuickSort(Node \*Left, Node\* right) //闭区间

if (Left->pri != right) //这里当right在left左边是结束

Node \*temp = right;

Node \*p = Left->pri;

Node \*q = Left;

while (q != right)

if (q->data < temp->data)

p = p->next;

Swap(p, q);

q = q->next;

p = p->next;

Swap(p, temp);

// OutPut2(Left,right); //测试输出函数

QuickSort(Left, p->pri);

QuickSort(p->next, right);

4、关键的交换函数，不过也和单链表的交换差不多了

void Swap(Node \*p, Node \*q)

Node temp = \*p;

temp.next = q->next;

temp.pri = q->pri;

q->next = p->next;

q->pri = p->pri;

\*p = \*q;

\*q = temp;

5、测试输出函数

void OutPut2(Node \*Left, Node \*right)

Node \*p = Left;

while (p!=right)

cout << p->data << " ";

p = p->next;

cout << right->data << " "; //单独输出最后一个

cout << endl;

实验结果：

!\[\](http://i.imgur.com/BW6Bg6N.png)

总结: 以前排序都是在数组上排序，现在学了链表，也想实现快速排序。总之，本质上没啥区别，算法流程都差不多，只是操作上的不同。

c语言单链表集合的排序升序去重,单链表的排序

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 C语言实现无序单链表去重

相关 c语言单链表集合的排序升序去重,单链表的排序

相关单链表排序

相关单链表排序

相关 12.单链表排序

相关单链表的排序

相关单链表排序

相关【数据结构】（单链表）单链表选择排序

相关【数据结构】（单链表）单链表冒泡排序

相关【数据结构】（单链表）单链表插入排序