dedecms网站制作教程自建站平台
目录
单链表的特性
单链表的所有操作
定义一个单链表
创建一个链表头
插入数据(头插法)
插入数据(尾插法)
查找节点
修改数据节点
删除节点
打印数据
销毁链表
翻转链表
打印链表长度
冒泡排序
快排
堆排
查找倒数第K个节点（双指针法）
完整测试代码
单链表的特性
单链表是一种线性数据结构，它由一系列的节点组成，每个节点包含一个数据域和一个指向下一个节点的指针域。单链表的特性有：
- 单链表的长度是可变的，可以动态地插入和删除节点。
- 单链表的访问是顺序的，要访问某个节点，必须从头节点开始遍历，直到找到该节点或者到达链表尾部。
- 单链表不需要连续的内存空间，可以利用零散的空间存储数据。
- 单链表的优势是：
- 插入和删除操作比较简单，只需要修改指针域即可，不需要移动其他节点。
- 单链表可以实现一些特殊的功能，如栈、队列、循环链表等。
- 单链表的劣势是：
- 访问操作比较慢，需要遍历整个链表，时间复杂度为O(n)。
- 单链表需要额外的空间存储指针域，增加了空间开销。
- 单链表容易产生内存碎片，如果频繁地插入和删除节点，可能导致内存不连续。
单链表的所有操作
定义一个单链表
// 声明并定义个单链表结构体
typedef struct _ListNode
{int val; //数据 成员变量struct _ListNode * next;//结构体调用自己的类型
}ListNode;创建一个链表头
void listCreate(ListNode *node)
{//初始化链表内数据node->val = -1;node->next = NULL;
}插入数据(头插法)
void listInsert(ListNode *node, int data)
{// 创建一个节点,并申请内存ListNode *t_node = (ListNode *)malloc(sizeof(ListNode));// 节点内容赋值t_node->val = data;// 头插法，新数据在前t_node->next = node->next;node->next = t_node;
}插入数据(尾插法)
void listTailInsert(ListNode *node, int data)
{// 创建一个节点ListNode *t_node = (ListNode*)malloc(sizeof(ListNode));// 节点内容赋值t_node->val = data;t_node->next = NULL;// 声明一个尾节点ListNode* t_tail = node;// 获取最后一个节点while(t_tail->next != NULL){// 后移t_tail = t_tail->next;}//添加节点t_tail->next = t_node;
}查找节点
ListNode* listFind(ListNode *node, int data)
{//申明一个空节点ListNode *t_node = NULL;//遍历链表ListNode *t_temp;for(t_temp = node->next; t_temp != NULL; t_temp = t_temp->next){//如果找到该节点if(t_temp->val == data){t_node = t_temp;//跳出循环break;}}return t_node;
}修改数据节点
void listModify(ListNode *node, int oldData, int newData)
{// 查找值是否存在ListNode *t_node = listFind(node, oldData);// 判断值是否存在if(t_node == NULL){printf("该值不存在\n");return;}t_node->val = newData;
}删除节点
void listDelete(ListNode *node, int data)
{// 查找是否存在改制的数据ListNode *t_node = listFind(node, data);// 如果该值对应的节点不存在if(NULL == t_node){printf("该值不存在\n");return;}// 求出被删节点的前一个节点ListNode *t_prev = node;// 遍历链表while(t_prev->next != t_node){t_prev = t_prev->next;}// 前一个节点的next指向被删除节点的下一个节点t_prev->next = t_node->next;// 释放内存free(t_node);// 指针置空t_node = NULL;
}打印数据
void listDisplay(ListNode *node)
{// 遍历链表ListNode *t_temp;for(t_temp = node->next; t_temp != NULL; t_temp = t_temp->next){printf("%d ",t_temp->val);}printf("\n");
}销毁链表
void listDestroy(ListNode *node)
{// 遍历链表ListNode *t_temp = node->next;while(t_temp != NULL){// 先将当前节点保存ListNode *t_node = t_temp;// 移动到下一各节点t_temp = t_temp->next;// 释放保存内容的节点free(t_node);}
}翻转链表
void listReverse(ListNode *node)
{ListNode * head = NULL, *now = NULL, *temp = NULL;head = node->next;// head是来保存我们翻转以后链表中的头节点的now = head->next;// now用来保存我们当前待处理的节点head->next = NULL;// 一定要置为NULL，否则可能导致循环while(now){temp = now->next; // 利用一个临时指针来保存下一个待处理的节点now->next = head; // 将当前节点插入到逆序节点的第一个节点之前，并更改head指向head = now;node->next = head; // 使链表头指针指向逆序后的第一个节点now = temp; // 更新链表到下一个待处理的节点}
}打印链表长度
int listLength(ListNode *node)
{ListNode *t_temp;int t_length = 0;for(t_temp = node->next; t_temp != NULL; t_temp = t_temp->next){t_length++;}return t_length;
}冒泡排序
void listBubbleSort(ListNode *node)
{int t_length = listLength(node);int i,j;ListNode *t_temp;for(i = 0; i < t_length; i++){t_temp = node->next;for(j = 0;j < t_length - i - 1; j++){if(t_temp->val > t_temp->next->val){int t_data = t_temp->val;t_temp->val = t_temp->next->val;t_temp->next->val = t_data;}t_temp = t_temp->next;}}
}快排
void quickSort(struct _ListNode *head, struct _ListNode *tail) {// 如果链表为空或只有一个节点，直接返回if (head == NULL || head == tail) return;// 定义两个指针p和q，用于分割链表struct _ListNode *p = head, *q = head->next;// 选取第一个节点作为基准值int pivot = head->val;// 遍历链表，将小于基准值的节点放到p的后面while (q != tail->next) {if (q->val < pivot) {p = p->next;// 交换p和q指向的节点的值int temp = p->val;p->val = q->val;q->val = temp;}q = q->next;}// 交换head和p指向的节点的值，使得p指向的节点为基准值int temp = head->val;head->val = p->val;p->val = temp;// 对左右两部分递归进行快速排序quickSort(head, p);quickSort(p->next, tail);
}堆排
// 待实现查找倒数第K个节点（双指针法）
ListNode* listFindKthToTail(ListNode *node, int k)
{// 超过长度直接返回空if(node == NULL || k >= listLength(node))return NULL;ListNode *first = node, *second = node;for(int i = 0; i < k; i++){first = first->next;}while (first){first = first->next;second = second->next;}return second;
}完整测试代码
#include <stdio.h>
#include <stdlib.h>// 声明并定义个单链表结构体
typedef struct _ListNode
{int val; //数据 成员变量struct _ListNode * next;//结构体调用自己的类型
}ListNode;/*** 创建链表
*/
void listCreate(ListNode *node)
{//初始化链表内数据node->val = -1;node->next = NULL;
}/*** 插入数据,头插法
*/
void listInsert(ListNode *node, int data)
{// 创建一个节点,并申请内存ListNode *t_node = (ListNode *)malloc(sizeof(ListNode));// 节点内容赋值t_node->val = data;// 头插法，新数据在前t_node->next = node->next;node->next = t_node;
}/*** 插入数据,尾插法
*/
void listTailInsert(ListNode *node, int data)
{// 创建一个节点ListNode *t_node = (ListNode*)malloc(sizeof(ListNode));// 节点内容赋值t_node->val = data;t_node->next = NULL;// 声明一个尾节点ListNode* t_tail = node;// 获取最后一个节点while(t_tail->next != NULL){// 后移t_tail = t_tail->next;}//添加节点t_tail->next = t_node;
}/*** 查找数据
*/
ListNode* listFind(ListNode *node, int data)
{//申明一个空节点ListNode *t_node = NULL;//遍历链表ListNode *t_temp;for(t_temp = node->next; t_temp != NULL; t_temp = t_temp->next){//如果找到该节点if(t_temp->val == data){t_node = t_temp;//跳出循环break;}}return t_node;
}/*** 修改数据
*/
void listModify(ListNode *node, int oldData, int newData)
{// 查找值是否存在ListNode *t_node = listFind(node, oldData);// 判断值是否存在if(t_node == NULL){printf("该值不存在\n");return;}t_node->val = newData;
}/*** 删除数据
*/
void listDelete(ListNode *node, int data)
{// 查找是否存在改制的数据ListNode *t_node = listFind(node, data);// 如果该值对应的节点不存在if(NULL == t_node){printf("该值不存在\n");return;}// 求出被删节点的前一个节点ListNode *t_prev = node;// 遍历链表while(t_prev->next != t_node){t_prev = t_prev->next;}// 前一个节点的next指向被删除节点的下一个节点t_prev->next = t_node->next;// 释放内存free(t_node);// 指针置空t_node = NULL;
}/*** 打印数据
*/
void listDisplay(ListNode *node)
{// 遍历链表ListNode *t_temp;for(t_temp = node->next; t_temp != NULL; t_temp = t_temp->next){printf("%d ",t_temp->val);}printf("\n");
}/*** 销毁链表
*/
void listDestroy(ListNode *node)
{// 遍历链表ListNode *t_temp = node->next;while(t_temp != NULL){// 先将当前节点保存ListNode *t_node = t_temp;// 移动到下一各节点t_temp = t_temp->next;// 释放保存内容的节点free(t_node);}
}/*** 翻转链表
*/
void listReverse(ListNode *node)
{ListNode * head = NULL, *now = NULL, *temp = NULL;head = node->next;// head是来保存我们翻转以后链表中的头节点的now = head->next;// now用来保存我们当前待处理的节点head->next = NULL;// 一定要置为NULL，否则可能导致循环while(now){temp = now->next; // 利用一个临时指针来保存下一个待处理的节点now->next = head; // 将当前节点插入到逆序节点的第一个节点之前，并更改head指向head = now;node->next = head; // 使链表头指针指向逆序后的第一个节点now = temp; // 更新链表到下一个待处理的节点}
}/*** 求长度
*/
int listLength(ListNode *node)
{ListNode *t_temp;int t_length = 0;for(t_temp = node->next; t_temp != NULL; t_temp = t_temp->next){t_length++;}return t_length;
}/*** 冒泡排序
*/
void listBubbleSort(ListNode *node)
{int t_length = listLength(node);int i,j;ListNode *t_temp;for(i = 0; i < t_length; i++){t_temp = node->next;for(j = 0;j < t_length - i - 1; j++){if(t_temp->val > t_temp->next->val){int t_data = t_temp->val;t_temp->val = t_temp->next->val;t_temp->next->val = t_data;}t_temp = t_temp->next;}}
}/*** 定义快速排序算法
*/
void quickSort(struct _ListNode *head, struct _ListNode *tail) {// 如果链表为空或只有一个节点，直接返回if (head == NULL || head == tail) return;// 定义两个指针p和q，用于分割链表struct _ListNode *p = head, *q = head->next;// 选取第一个节点作为基准值int pivot = head->val;// 遍历链表，将小于基准值的节点放到p的后面while (q != tail->next) {if (q->val < pivot) {p = p->next;// 交换p和q指向的节点的值int temp = p->val;p->val = q->val;q->val = temp;}q = q->next;}// 交换head和p指向的节点的值，使得p指向的节点为基准值int temp = head->val;head->val = p->val;p->val = temp;// 对左右两部分递归进行快速排序quickSort(head, p);quickSort(p->next, tail);
}/*** 快速排序
*/
void listQuickSort(ListNode *node)
{ListNode *tail = node->next;while (tail->next){tail = tail->next;}quickSort(node, tail);
}/*** 堆排序
*/
void listHeapSort(ListNode *node)
{}/*** 获取链表倒数第k个节点,双指针方法
*/
ListNode* listFindKthToTail(ListNode *node, int k)
{// 超过长度直接返回空if(node == NULL || k >= listLength(node))return NULL;ListNode *first = node, *second = node;for(int i = 0; i < k; i++){first = first->next;}while (first){first = first->next;second = second->next;}return second;
}/*** 测试所有函数是否正确有效
*/
int main(int argc, char* argv[])
{//创建一个ListNode变量ListNode node;//创建链表listCreate(&node);int i = 0;for(i = 0;i < 10;i++){
#if 0 listInsert(&node,i); // 插入数据头插法
#elselistTailInsert(&node, i); // 插入数据尾插法
#endif}listDisplay(&node);ListNode* nodeFind = listFind(&node, 3);if(nodeFind)printf("listFind:%d\n", nodeFind->val); const int k = 5;ListNode* nodeFindK = listFindKthToTail(&node, k);if(nodeFindK)printf("listFindKthToTail step:%d :%d\n", k, nodeFindK->val); listModify(&node, 1, 999); //修改节点1为999listDisplay(&node);listDelete(&node, 5); // 删除节点5listDisplay(&node);// listBubbleSort(&node); // 冒泡排序listQuickSort(&node); // quick sortlistDisplay(&node); // 打印链表数据listReverse(&node); // 翻转链表listDisplay(&node); // 打印反转后的链表listDestroy(&node); // 销毁链表return 0;
}