数据结构之单链表的排序

一、 实现的步骤

1、生成一个单链表 2、对生成的链表排序

二、实现代码

#include <stdio.h> #include <malloc.h> //包含malloc函数，用来实现动态内存的分配 #include <stdlib.h> //包含exit函数，用来退出整个程序 typedef struct Node //定义一个结构体变量 ，并进行类型定义 { int data; //数据域 struct Node * pNext; //指针域 }NODE,*PNODE ; //NODE 等价于struct Node;PNODE 等价于struct Node * //注意不要忘记“;” //函数前置声明 PNODE creat_list(void); //函数的作用：创建一个链表并返回该链表的头指针（头指针是指向头节点的一个指针）,函数不传参 void traverse_list(PNODE); //函数的作用：遍历一个链表,函数的参数为链表的头指针 bool is_empty(PNODE); //函数的作用：判断一个函数是否为空，函数的参数为链表的头指针 int length_list(PNODE); //函数的作用：计算一个链表的长度，函数的参数为链表的头指针 void sort_list(PNODE); //函数的作用：对一个链表进行排序，函数的参数为链表的头指针 int main (void) { PNODE pHead = NULL; pHead = creat_list(); printf("链表的内容是："); traverse_list(pHead); sort_list(pHead); printf("排序后链表的内容是："); traverse_list(pHead); return 0; } //创建一个链表 /* 定义一个链表需要什么？ 1、有效节点的个数 2、每个节点存放的数据 */ PNODE creat_list(void) { int len; //用来存放有效节点的个数 int val; //用来存放用户临时输入的数据 int i; //用来控制循环 PNODE pHead = (PNODE)malloc(sizeof(NODE)); //定义一个头节点，并将这个头节点的地址赋值给pHead //分配完成后首先要确定内存是否分配成功 if(NULL == pHead) { printf("内存分配失败，程序结束!!!\n"); exit(-1); } printf("请输入您要生成的节点个数：\nlen ="); scanf("%d",&len); PNODE pTail = pHead; //定义一个尾节点。当只有一个头节点时这个头节点就是尾节点 for(i=0;i<len;i++) { printf("您输入的第%d个节点的数为：",i+1); scanf("%d",&val); PNODE pNew = (PNODE) malloc(sizeof(NODE)); //定义一个临时节点,并将临时节点的地址赋值给pNew //判断内存是否分配成功 if(NULL == pNew) { printf("内存分配失败，程序结束！！！\n"); exit(-1); } pNew->data = val; pNew->pNext = NULL; pTail->pNext = pNew; //将新节点挂到尾节点的后面 pTail = pNew; } printf("\n"); return pHead; } //遍历一个链表 void traverse_list(PNODE pHead) { PNODE p = pHead->pNext; //定义一个结构体指针变量p，并赋值为链表头节点的指针域，也就是说指向了第一个有效节点 while(p != NULL) { printf("%d ",p->data); p = p->pNext; } printf("\n\n"); return; } //判断一个函数是否为空 /* 注意注意注意，重要的事说三遍 C语言没有bool函数，bool函数是C++里面添加的 如果文件的类型是.c，编译器会报错 [Error] unknown type name 'bool' 若文件的扩展类型是.cpp，则可正常编译通过 若一定要用纯C的话，可以在程序开头进行宏定义或类型定义 */ //判断函数是否为空 bool is_empty(PNODE pHead) { if(pHead->pNext == NULL) return true; //若函数为空，返回真，否则返回假 else return false; } //计算一个链表的长度(有效节点的个数) int length_list(PNODE pHead) { int length = 0; PNODE p = pHead->pNext; //定义一个结构体指针变量p，并赋值为链表头节点的指针域，也就是说指向了第一个有效节点 while(p != NULL) { length++; p = p->pNext; } return length; } //对链表进行排序 （升序排列） void sort_list(PNODE pHead) { int i,j,t; int len = length_list(pHead); PNODE p,q; for(i=0,p = pHead->pNext; i<len-1; i++,p = p->pNext ) { for(j = i+1,q = p->pNext;j<len;++j,q=q->pNext) { if(p->data>q->data) //类似于数组中的 a[i]>a[j] { t = p->data; //类似于数组中的 t=a[i]; p->data = q->data; //类似于数组中的 a[i]=a[j]; q->data = t; //类似于数组中的 a[j]=t; } } } return; }

三、程序说明

1、这是我第二次在写博客，也是刚开始学习数据结构这门课，肯定在一些名词上说的不准确，但我也尽量在注意这个问题，请碰巧看到这篇博客的前辈们能指出不足，必定感激不尽。 2、程序在dev C++中可以通过编译并运行。 3、程序需要注意的问题都在注释里面解释清楚了。