乡土文化网站怎么做,网络营销的应用,如何优化wordpress网站,WordPress分类ID能修改吗目录 单链表的特性
单链表的所有操作
定义一个单链表
创建一个链表头
插入数据(头插法)
插入数据(尾插法)
查找节点
修改数据节点
删除节点
打印数据
销毁链表
翻转链表
打印链表长度
冒泡排序
快排
堆排
查找倒数第K个节点#xff08;双指针法#xff09;
…目录 单链表的特性
单链表的所有操作
定义一个单链表
创建一个链表头
插入数据(头插法)
插入数据(尾插法)
查找节点
修改数据节点
删除节点
打印数据
销毁链表
翻转链表
打印链表长度
冒泡排序
快排
堆排
查找倒数第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;
}
