2024.11.29（单链表）

思维导图

声明文件

#ifndef __LINKLIST_H__
#define __LINKLIST_H__#include <myhead.h>typedef char datatype; 	//数据元素类型
//定义节点类型
typedef struct Node
{union{int len; 		//头节点数据域datatype data; 	//普通节点数据域};struct Node *next; //指针域}Node ,*Node_ptr;//创建链表
Node_ptr list_create();//链表判空操作
int list_empty(Node_ptr L);//定义申请节点封装数据函数
static Node_ptr node_apply(datatype e);//单向链表头插
int list_insert_head(Node_ptr L,datatype e);//单向链表的按位置查找返回节点
Node_ptr list_find_node(Node_ptr L,int pos);//单链表遍历
void list_show(Node_ptr L);//单向链表任意位置插入
int list_insert_anypos(Node_ptr L,int pos,datatype e);//单链表头删
int  list_head_delete(Node_ptr L);//任意位置删除
int list_delete_anywhere(Node_ptr L,int pos);//按位置进行修改
int list_update_pos(Node_ptr L,int pos,datatype e);//单向链表翻转
int list_reverse(Node_ptr L);//销毁单链表
void list_destroy(Node_ptr L);//单链表尾插
int list_insert_tail(Node_ptr L,datatype e);//单链表的尾删
int list_delete_tail(Node_ptr L);//单链表按值查找返回位置
int list_find_value(Node_ptr L,int e);//单链表按值修改
int list_edit_value(Node_ptr L,int w,datatype e);//单链表的排序
int list_sort(Node_ptr L);//单链表的去重
int list_duplicate_removal(Node_ptr L);//清空单链表
int list_clear(Node_ptr L);//返回单链表的长度
int list_len(Node_ptr L);#endif

测试文件

#include "linklist.h"
int main(int argc, const char *argv[])
{//调用链表创建函数Node_ptr L = list_create();if(NULL == L){return -1;}//调用头插函数list_insert_head(L,'A');list_insert_head(L,'B');list_insert_head(L,'C');list_insert_head(L,'D');list_insert_head(L,'A');list_insert_head(L,'B');list_insert_head(L,'C');list_insert_head(L,'D');//调用遍历函数list_show(L);/*	//调用任意插入函数list_insert_anypos(L,1,'u');list_show(L);list_insert_anypos(L,L->len+1,'P');list_show(L);list_insert_anypos(L,3,'9');list_show(L);//调用头删函数list_head_delete(L);list_show(L);//调用任意位置删除list_delete_anywhere(L,3);list_show(L);list_delete_anywhere(L,2);list_show(L);//调用按位置修改函数list_update_pos(L,2,'H');list_show(L);//调用翻转函数list_reverse(L);list_show(L);//调用尾插法list_insert_tail(L,'e');list_show(L);//调用尾删除list_delete_tail(L);list_show(L);//调用按值查找函数int a = list_find_value(L,'H');printf("位置为%d\n",a);//调用单链表按值修改list_edit_value(L,'H','A');	list_show(L);//调用排序函数list_sort(L);list_show(L);//调用去重函数list_duplicate_removal(L);list_show(L);printf("%d",L->len);//调用清空函数list_clear(L);list_show(L);
printf("%d",L->len);//调用销毁函数list_destroy(L);L = NULL;list_show(L);*/printf("链表长度为：%d\n",list_len(L));return 0;
}

功能函数文件

#include "linklist.h"
//创建链表
Node_ptr list_create()
{//在堆区申请一个头结点的空间Node_ptr L = (Node_ptr)malloc(sizeof(Node));if(L == NULL){printf("创建失败\n");return NULL;}//程序执行至此，一个头结点就申请成功//有了头结点就有了一条2链表//初始化操作L->len = 0; 		//表示链表长度为0L->next = NULL; 	//防止野指针printf("链表创建成功\n");return L;}//链表判空操作
//如果链表为空，返回1，非空返回0
int list_empty(Node_ptr L)
{//判断逻辑if(NULL == L){printf("链表不合法\n");return -1;}return 0;}//定义申请节点封装数据函数
static Node_ptr node_apply(datatype e)
{//在堆区申请一个节点的空间Node_ptr P = (Node_ptr)malloc(sizeof(Node));if(NULL == P){printf("节点申请失败\n");return NULL;}//将数据封装进节点的数据域P->data = e;P->next = NULL; 	//防止野指针return P; 			//将封装好的节点地址返回
}//单向链表头插
int list_insert_head(Node_ptr L,datatype e)
{//判断逻辑if(NULL == L){printf("链表不合法\n");return -1;}//申请节点封装数据Node_ptr P = node_apply(e);if(NULL ==P ){return -1;}//程序执行至此，表示节点申请成功//头插逻辑P->next = L->next;L->next = P;//表长变化L->len++;printf("插入成功\n");}//单向链表的按位置查找返回节点
Node_ptr list_find_node(Node_ptr L,int pos)
{//判断逻辑、if( NULL == L||pos <0||pos>L->len){printf("查找失败\n");return NULL;}//查找逻辑Node_ptr Q = L; 		//定义遍历指针for(int i=0;i<pos;i++){Q = Q->next; 		//将指针偏移到下一个节点位置}//返回节点return Q;}//单链表遍历
void list_show(Node_ptr L)
{//判断逻辑if(list_empty(L)){printf("遍历失败\n");return ;}/*遍历所有节点printf("链表中的元素分别是：");for(int i=1;i<L->len;i++){Node_ptr Q = list_find_node(L,i); //找到第i个节点printf("%c\t",Q->data);}*/printf("链表中的元素分别是：");Node_ptr Q = L->next; //定义遍历指针从第一个节点出发/*for(int i=0;i<L->len;i++){Q = Q->next;printf("%c\t",Q->data);}*/while(Q){//当前节点不为空，输出数据域printf("%c\t",Q->data);Q = Q->next; 	//继续遍历下一个节点}printf("输出完成\n");
}//单向链表任意位置插入
int list_insert_anypos(Node_ptr L,int pos,datatype e)
{//判断逻辑if(pos>L->len+1||pos<1||NULL == L){printf("插入失败\n");return -1;}//判断逻辑//找到要插入位置的前一个节点Node_ptr Q = list_find_node(L,pos-1);//插入逻辑Node_ptr W = node_apply(e);if(NULL == W){return -1;}W->next = Q->next;Q->next = W;//表长变化L->len++;printf("插入成功\n");
}//单链表头删
int  list_head_delete(Node_ptr L)
{//判断逻辑if(NULL == L||list_empty(L)){printf("删除失败\n");return -1;}Node_ptr Q = L->next;L->next = Q->next;free(Q);Q = NULL;//表长变化L->len--;printf("删除成功\n");return 0;
}//任意位置删除
int list_delete_anywhere(Node_ptr L,int pos)
{//判断逻辑if(NULL==L||list_empty(L)||pos<1||pos>L->len){printf("删除失败\n");return -1;}//删除逻辑Node_ptr Q = list_find_node(L,pos-1); 	//找到前驱Node_ptr W = Q->next; 	//标记要删除的节点Q->next = W->next; 		//孤立要删除的节点free(W); 				//释放要删除的节点W = NULL;//表长变化L->len--;printf("删除成功\n");return 0;
}//按位置进行修改
int list_update_pos(Node_ptr L,int pos,datatype e)
{//判断逻辑	if(NULL==L||list_empty(L)||pos<1||pos>L->len){printf("删除失败\n");return -1;}//查找指定节点Node_ptr Q = list_find_node(L,pos-1); 	//找到前驱//进行修改Q->data = e;printf("修改成功\n");return 0;
}//单向链表翻转
int list_reverse(Node_ptr L)
{//判断逻辑	if(NULL==L||list_empty(L)||L->len == 1){printf("翻转失败\n");return -1;}//翻转逻辑Node_ptr H = L->next; 	//用头指针托管链表L->next = NULL; 		//清空当前链表while(H!=NULL){Node_ptr Q = H; 	//挖墙脚H= H->next; 		//管理下一位//以头插法的形式将Q插入到L中Q->next = L->next;L->next = Q;}printf("翻转成功\n");return 0;
}//销毁单链表
void list_destroy(Node_ptr L)
{//判断逻辑if(NULL == L||L->next == NULL){printf("销毁失败\n");return ;}Node_ptr Q = L->next;while(Q!=NULL){Node_ptr temp = Q;Q = Q->next;free(temp);}L->next = NULL;printf("销毁成功\n");/*//释放逻辑//将所有普通节点释放while(!list_empty(L)){//调用头删除函数list_head_delete(L);}//释放头节点free(L);L = NULL;printf("销毁成功\n");*/
}//单链表尾插
int list_insert_tail(Node_ptr L,datatype e)
{//判断逻辑if(NULL == L){printf("单链表不合法\n");return -1;}//插入逻辑Node_ptr Q = list_find_node(L,L->len);Node_ptr W = node_apply(e);Q->next = W;//长度变化L->len++;printf("添加成功\n");return 0;
}//单链表的尾删
int list_delete_tail(Node_ptr L)
{if(NULL == L||L->len<1){printf("删除失败\n");return -1;}//删除逻辑Node_ptr Q = list_find_node(L,L->len-1);Node_ptr W = Q->next;Q->next = NULL;free(W);W = NULL;//长度变化L->len--;printf("删除成功\n");return 0;}//单链表按值查找返回位置
int list_find_value(Node_ptr L,int e)
{//判断逻辑if(NULL == L||list_empty(L)){printf("查找失败\n");return -1;}//查找逻辑Node_ptr Q = L->next;for(int i=0;i<L->len;i++){if(Q->data == e){printf("查找成功\n");return i+1;}Q = Q->next;}printf("未查找到该值\n");return 0;
}//单链表按值修改
int list_edit_value(Node_ptr L,int w,datatype e)
{//判断逻辑if(NULL == L||list_empty(L)){printf("查找失败\n");return -1;}//修改逻辑int flag = 0; 		//检测是否修改Node_ptr Q = L->next;for(int i=0;i<L->len;i++){if(Q->data == w){flag = 1;Q->data = e;}Q = Q->next;}if(flag == 0){printf("未查找到该值\n");return 0;}else{printf("修改成功\n");return 0;}}//单链表的排序
int list_sort(Node_ptr L)
{if(NULL == L||list_empty(L)){printf("排序失败\n");return -1;}//排序逻辑Node_ptr Q = NULL;Node_ptr T = NULL;Node_ptr W = NULL;//冒泡排序for(int i=1;i<L->len;i++){Q = L;T = Q->next;W = T->next;for(int j=0;j<L->len-i;j++){//升序if(T->data > W->data){T->next = W->next;//链接后面节点W->next = Q->next;Q->next = W;//便于下次交换Q=Q->next;//p已经被交换到后面W = T->next;}else{//不满足条件继续后移比较Q = Q->next;T = T->next;W = W->next;}}}return 0;
}//单链表的去重
/*
int list_duplicate_removal(Node_ptr L)
{if(NULL == L||L->len<2||list_empty(L)){printf("去重失败\n");return -1;}//去重逻辑Node_ptr Q = L;Node_ptr T = NULL;Node_ptr W = NULL;//外层循环避免多个重复元素，控制趟数
for(int i=1;i<L->len-1;i++)//for(int i=1;Q!=NULL||Q->next !=NULL;i++){T = Q;//内层循环结束，重新指向W = Q->next;for(int j=0;j<L->len-2-i;j++)//for(int j=0;W!=NULL;j++){if(T->data == W->data){Node_ptr Temp = W->next;free(W);//删除重复部分,释放内存T->next = Temp;//长度变化L->len--;printf("%d\n",L->len);}else{W = W->next; //移动到下一个节点}}Q = Q->next;//内层循环结束向前移动一次}printf("去重成功\n");return 0;
}
*/
int list_duplicate_removal(Node_ptr L) {if (NULL == L || L->len < 2 || list_empty(L)) {printf("去重失败\n");return -1;}Node_ptr T, W, prev;int i;// 遍历链表，T为当前节点，W为T的下一个节点for (T = L->next, prev = L; T != NULL && T->next != NULL; ) {W = T->next; // W指向T的下一个节点// 检查W是否与T之后的节点有重复while (W != NULL) {if (T->data == W->data) {Node_ptr temp = W->next; // 保存W的下一个节点prev->next = temp; // 跳过W节点free(W); // 释放W节点的内存L->len--; // 更新链表长度W = temp; // W更新为新的节点，继续检查} else {prev = W; // 更新prev为W，W移动到下一个节点W = W->next;}}T = T->next; // T移动到下一个节点}printf("去重成功\n");return 0;
}//清空单链表
int list_clear(Node_ptr L)
{if(NULL == L||list_empty(L)){printf("单链表不存在或为空\n");return -1;}while(L->next!=NULL){list_head_delete(L);}printf("清空完成\n");return 0;
}
//返回单链表的长度
int list_len(Node_ptr L)
{if(NULL == L){printf("该链表不存在\n");return -1;}Node_ptr Q = L->next;int num = 0;while(Q){Q = Q->next;num++;}return num;
}