目录
带头节点单链表的结构体
增加节点
算法思路
代码实现
删除节点
算法思路
代码实现
更新节点值
算法思路
代码实现
查找节点值是否存在
算法思路
代码实现
销毁链表
算法思路
代码实现
正文
带头节点单链表的结构体
typedef int ElemType; typedef struct node { ElemType data;//数据域 struct node *next;//指针域 }Node; //头结点：不保存数据 只有两个指针 加一个结点数目 typedef struct linkedlist { Node *first;//指向链表中的第一个数据结点 Node *last;//指向链表中的最后一个数据结点 ElemType NodeNum;//结点的数目 //...根据具体需求 增加其它的成员变量 }List;
增加节点
算法思路
在链表中找到值为x的结点，在它前面插入一个值为a的结点，如果没有找到，就加在最后，将新链表返回。
step1:创建一个新的结点 把数据写进去
step2:找到值为x的点
step3：分情况插入
代码实现
/* add_a_node:在链表中找到值为x的结点 在它前面插入值为a的结点，没有则加到最后。 @list:原来的链表的头结点 @x:遍历要找到的值 @a:要插入的结点值 */ List* add_a_node(List *list, ElemType x, ElemType a) { Node *p = NULL;//遍历指针 Node *pre = NULL;//指向p前面的那个结点 Node *pnew = NULL;//指向新创建的结点 //step1:创建一个新的结点 把数据写进去 pnew = malloc(sizeof(*pnew)); pnew->data = a; pnew->next = NULL; //step2:找到值为x的点 p = list->first; while(p) { if(p->data == x) { break; } pre = p;//pre往后移 p = p->next;//p也往后移 } //step3：分情况插入 if(p != NULL)//找到了 { if(p == list->first)//头插 { pnew->next = list->first; list->first = pnew; } else//中间插入 { pnew->next = p; pre->next = pnew; } } else//没找到 插尾 { if(list->first == NULL) { list->first = pnew; list->last = pnew; } else { list->last->next = pnew; list->last = pnew; } } list->NodeNum++; return list; }
删除节点
算法思路
在链表中找到值为x的结点，将其删除，没有找到，就不删除，将新链表返回。
算法思路：
step1:遍历 找到值为x的结点
step2:分情况删除
代码实现
/* 删：在链表中找到值为x的结点，将其删除，没有找到，就不删除，将新链表返回。 算法思路： step1:遍历 找到值为x的结点 step2:分情况删除 */ List *delete_x(List *list, ElemType x) { Node *p = NULL;//遍历指针 Node *pre = NULL;//指向p前面的那个结点 p = list->first; //step1:遍历 找到值为x的结点 while(p) { if(p->data == x)//找到了 { //step2:分情况删除 if(p == list->first)//要删除的结点为第一个 { list->first = list->first->next; p->next = NULL; free(p); p = list->first; } else if(p == list->last)//要删的结点为最后 { list->last = pre; list->last->next = NULL; free(p); p = NULL; } else//要删除的结点为空间 { pre->next = p->next; p->next = NULL; free(p); p = pre->next; } list->NodeNum--; } else//没找到 接着往后找 { pre = p; p = p->next; } if(list->NodeNum == 0) { list->last = NULL; } } return list; }
更新节点值
算法思路
把list头结点指向的链表，值为x的结点改为a。
算法思路：
遍历找x。
代码实现
/* update_node:更新一个链表的值 把x变为a。 @list: 要更新的链表 @x：要修改的数据结点的值 @a: 要更新后数据结点的值 返回值： 更新完链表C的头结点 */ List *update_node(List *list, ElemType x, ElemType a) { Node *p = list->first; while(p) { if(p->data == x) { p->data = a; } p = p->next; } return list; }
查找节点值是否存在
算法思路
把list头结点指向的链表，找到链表中是否有值为x的结点。
算法思路：
遍历找x。
代码实现
/* find_node:查找一个值是否存在与链表中 @list: 要更新的链表 @x：要查找的数据结点的值 返回值： 1 该值存在与链表中 0 该值不存在与链表中 */ int find_node(List *list,int x) { Node *p = list->first; while(p) { if(p->data == x) { return 1; } p = p->next; } return 0; }
销毁链表
算法思路
s1: 把数据结点一个个摘除 free掉
s2:free掉头结点
代码实现
/* destory_list: 销毁一个链表 @list: 要更新的链表 */ void destory_list(List *list) { Node *p = list->first; //s1: 把数据结点一个个摘除 free掉 while(p) { list->first = list->first->next; p->next = NULL; free(p); p = list->first; } //s2:free掉头结点 list->last = NULL; list->NodeNum = 0; free(list); }
