目录
单链表回顾
带头结点的单链表
带头节点的意义
什么是头节点
头节点与数据节点定义
创建带头节点的单链表的步骤与详细代码
创建有序带头节点单链表的步骤与码源
正文
带头结点的单链表
带头节点的意义
很多时候我们可能经常需要知道一个链表有多少个结点，或者求一个链表的最后一个结点...
=> 我们都要通过第一个结点的指针，遍历整个链表。
而一个头节点就能很好的帮我们解决这个问题，而且只需要知道单链表的第一个结点的指针，first 对单链表的基本操作 “增删改查”就可以完成了
例如：
find_x p = h; while（p） { if(p->data == x) { break; } p = p->next; } find_last p = h; while（p） { if(p->next == NULL) { reak; } p = p->next; }
什么是头节点
头结点是用来管理链表的结点，这个结点一般包括常用的管理链表的数据对象：
eq: 指向链表的第一个结点指针 ，指向链表最后一个结点的指针...
什么是数据结点？
原来用来保存数据的结点 就称为数据结点
头结点是唯一一个标识一个链表存在与否的标志。
带头结点的单链表：
一个链表可以没有数据结点，但是必须要有头结点。
没有数据结点，表示“空链表”
没有头结点，表明这个链表不存在
头节点与数据节点定义
提示：简单描述算法知识点相关题目题意
//数据结点： typedef int ElemType; typedef struct node { ElemType data;//数据域 struct node *next;//指针域 }Node; //头结点：不保存数据 只有两个指针 加一个结点数目 typedef struct linkedlist { Node *first;//指向链表中的第一个数据结点 Node *last;//指向链表中的最后一个数据结点 ElemType NodeNum;//结点的数目 //...//根据具体需求 增加其它的成员变量 }List;
创建带头节点的单链表的步骤与详细代码
根据用户的输入数据 创建一个单链表
step1:创建一个头结点
step2:每获得一个数据就创建一个数据结点
step3：把获得的数据 写入到数据结点中
step4:把数据结点加入到链表中去。
List *create_list() { ElemType d;//用来保存获取的数据 Node *pnew = NULL;//指向新创建的数据结点 //step1:创建一个头结点 List *list = malloc(sizeof(*list)); list->first = NULL; list->last = NULL; list->NodeNum = 0; //step2 :每获得一个数据就创建一个数据结点 while(1) { scanf("%d",&d); if(d == 0) { break; } pnew = malloc(sizeof(*pnew)); //step3：把获得的数据 写入到数据结点中 pnew->data = d; pnew->next = NULL; //step4:把数据结点加入到链表中去。 if(list->first == NULL)//从无都有 { list->first = pnew; list->last = pnew; } else//从少到多 { //尾插 #if 1 list->last->next = pnew; list->last = pnew; #endif //头插 #if 0 pnew->next = list->first; list->first = pnew; #endif } list->NodeNum++; } return list; }
创建有序带头节点单链表的步骤与码源
创建一条带头结点的有序列表 升序
step1:创建一个头结点
step2:每获得一个数据就创建一个数据结点
step3：把获得的数据 写入到数据结点中
step4:把数据结点加入到链表中去。
从无到有
从少到多 --》找到第一个比pnew大的数据
1.第一个就比pnew大 pnew头插
2.找一了遍 没有找
/* create_sort_list:创建一条带头结点的有序单链表 返回值： 创建好的单链表的头结点 */ List *create_sort_list() { ElemType d;//用来保存获取的数据 Node *pnew= NULL;//指向新创建的数据结点 //step1:创建一个头结点 List *list = malloc(sizeof(*list)); list->first = NULL; list->last = NULL; list->NodeNum = 0; while(1) { //step2:每获得一个数据就创建一个数据结点 scanf("%d",&d); if(d == 0) { break; } pnew = malloc(sizeof(*pnew)); //step3：把获得的数据 写入到数据结点中 pnew->data = d; pnew->next = NULL; //step4:把数据结点加入到链表中去。 if(list->first == NULL)//从无到有 { list->first = pnew; list->last = pnew; } else//从少到多 { Node *p = list->first;//遍历指针 要找到第一个比pnew大的值 Node *pre = NULL;//指向p前面的那个结点 while(p) { if(p->data > pnew->data)//找到了 { break; } pre = p; p = p->next; } if(p != NULL) { if(p == list->first)//头插 第一个数就比我的Pnew大 { pnew->next = list->first; list->first = pnew; } else { pre->next = pnew; pnew->next = p; } } else//p为null pnew最大 { //pre->next = pnew; list->last->next = pnew; list->last = pnew; } } list->NodeNum++; } return list;//返回头结点 代表整个链表 }
