带头链表⾥的头节点,实际为“哨兵位”,哨兵位节点不存储任何有效元素,只是站在这⾥“放哨 的” “哨兵位”存在的意义: 遍历循环链表避免死循环。
- typedef int DataType;
- typedef struct ListNode
- {
- struct ListNode* perv;
- DataType val;
- struct ListNode* next;
- }ListNode;
双向链表有两个方向,所以要定义两个是指针,perv指向前一个节点,next指向后一个节点。
- ListNode* NewNode(DataType x)
- {
- ListNode* note = (ListNode*)malloc(sizeof(ListNode));
- if (note == NULL)
- {
- perror("malloc");
- exit(0);
- }
- note->val = x;
- note->next = note->perv = note;
- return note;
- }
当我们要插入新节点,或者初始化头结点时,需要开辟一个新节点。因为链表要循环,所以新节点的perv和next指针不能只想为NULL,要指向自己。
- void STInit(ListNode** pphead)
- {
- *pphead = NewNode(-1);
- }
双向带头循环链表的初始化就是建立头节点(哨兵位)。随便赋一个值就可以。
- void HeadAdd(ListNode* phead, DataType x)
- {
- assert(phead);
-
- ListNode* newnote = NewNode(x);
- newnote->next = phead->next;
- newnote->perv = phead;
- phead->next->perv = newnote;
- phead->next = newnote;
- }
头插实际上是在头节点之后插入新节点。只需将新节点的perv指针指向phead,next指针指向phead->next节点。然后将phead->next的perv指针指向newnote。头节点的next指针指向新节点。
- void ListPrint(ListNode* phead)
- {
- assert(phead);
- ListNode* pcur = phead->next;
- while (pcur != phead)
- {
- printf("%d->", pcur->val);
- pcur = pcur->next;
- }
- }
双向链表的打印实际上是打印头节点之后的内容。先定义一个指针指向头结点的下一个节点。然后打印,最后让pcur指向下一个节点,重复这个过程,直到pcur指向phead。
- void TailAdd(ListNode* phead, DataType x)
- {
- assert(phead);
- ListNode* newnode = NewNode(x);
-
- newnode->next = phead;
- newnode->perv = phead->perv;
- newnode->perv->next = newnode;
- phead->perv = newnode;
- }
双向链表的尾插,首先要向内存申请一个新节点。新节点的perv指针指向phead->perv节点,next指针指向phead节点。phead->perv的next指针指向新节点。头结点的perv节点指向新节点。
- void TailDel(ListNode* phead)
- {
- assert(phead && phead->next != phead);
- ListNode* del = phead->perv;
- del->perv->next = phead;
- phead->perv = del->perv;
- free(del);
- del = NULL;
- }
先将要删除的节点的地址存起来,否则改完指针指向后就找不到了。改完指针指向后再释放del。
- void HeadDel(ListNode* phead)
- {
- assert(phead && phead->next != phead);
- ListNode* del = phead->next;
- del->next->perv = phead;
- phead->next = del->next;
- free(del);
- del = NULL;
- }
头删即删除头节点之后的节点。同样要先把要删除的节点存起来。在改变指针指向之后把del释放。
- ListNode* Find(ListNode* phead, DataType x)
- {
- assert(phead);
- ListNode* pcur = phead->next;
- while (pcur != phead)
- {
- if (pcur->val == x)
- {
- return pcur;
- }
-
- }
- return -1;
- }
遍历链表,查找某节点是否存在,如果存在则返回该节点的地址,若不存在返回一个小于0的值。
2.10在指定位置指点之后插入节点
- void PosBAdd(ListNode* pop, DataType x)
- {
- ListNode* newnode = NewNode(x);
- newnode->next = pop->next;
- newnode->perv = pop;
- pop->next->perv = newnode;
- pop->next = newnode;
- }
同样也是简单的改变指针的指向。
2.11删除指定位置节点
- void PosDel(ListNode* pop)
- {
- pop->perv->next = pop->next;
- pop->next->perv = pop->perv;
- free(pop);
- pop = NULL;
- }
改变指针指向后在释放掉要删除的节点。
2.12销毁链表
- void ListDesTroy(ListNode* phead)
- {
- ListNode* pcur = phead->next;
- while (pcur != phead)
- {
- ListNode* next = pcur->next;
- free(pcur);
- pcur = next;
- }
- }
销毁链表即逐个节点释放,但是在释放结点之前要先将下一个结点的地址存起来,因为如果不存起来就无法找到下一个节点。