中堂网站建设,建设银行网站首页打不开,广东新闻联播回看,移动端网站开发 float目录
1.双向链表
2.结构体的定义
3.示意图
3.代码示例
1.双向链表的尾插
示意图
代码
main.c
List.h
List.c
详细分析代码的执行过程
双向链表的初始化
2.双向链表的打印
代码
3.双向链表的尾删 1.双向链表
以一种典型的双向链表为例:带头双向循环链表(带头:带…目录
1.双向链表
2.结构体的定义
3.示意图
3.代码示例
1.双向链表的尾插
示意图
代码
main.c
List.h
List.c
详细分析代码的执行过程
双向链表的初始化
2.双向链表的打印
代码
3.双向链表的尾删 1.双向链表
以一种典型的双向链表为例:带头双向循环链表(带头:带哨兵位的头节点)
2.结构体的定义
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;
3.示意图 head为带哨兵位的头节点,无有效数值,只储存第一个有效节点的地址,负责找到第一个节点
特点:
1.prev指向前一个节点,next指向下一个节点
2.末尾的next指向哨兵位的头
3.哨兵位的头的prev指向末尾(不用像单向链表那样循环找尾节点)
3.代码示例
List.h
#pragma once
#include stdlib.h
#include stdio.h
#include assert.h
typedef int LTDataType;typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;void LTInit();
void LTDestory();
void LTPushBack(LTNode* phead,LTDataType x);
void LTPopBack(LTNode* phead);
用结构体定义节点,节点有三部分构成:next指针,prev指针和数据,符合双向节点的定义 注:prev为previous的缩写
1.双向链表的尾插
示意图
非空链表 空链表
和之前的无头的单向链表有所不同,这里的带哨兵位的头节点
未尾插之前,head-prev指向head-next,head-next指向head-prev(这样可以实现双向循环) 千万不要被箭头的指向所误导!!!!
不是head-prevhead-next;head-nexthead-prev;
箭头指向的是head节点head-prevhead;head-nexthead; 尾插之后 实现过程和非空链表一样
*无论对于空链表还是非空链表,尾插都只需要4步,即修改四个指针*
tail指向尾节点
代码
main.c
#include List.h
void TestList()
{LTNode* plist LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);
}int main()
{TestList();return 0;
}
List.h
#include assert.h
typedef int LTDataType;typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;LTNode* LTInit();
LTNode* BuyListNode(LTDataType x);
void LTPushBack(LTNode* phead, LTDataType x);
List.c
#include List.h
LTNode* LTInit()
{LTNode* phead BuyListNode(-1);phead-next phead;phead-prev phead;return phead;
}LTNode* BuyListNode(LTDataType x)
{LTNode* node (LTNode*)malloc(sizeof(LTNode));if (node NULL){perror(malloc);return NULL;}node-next NULL;node-prev NULL;node-data x;return node;
}void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode BuyListNode(x);LTNode* tail phead-prev;tail-next newnode;newnode-prev tail;newnode-next phead;phead-prev newnode;
}
详细分析代码的执行过程
进入main函数--调用TestList函数--调用LTInit函数--调用BuyListNode函数
在BuyListNode函数中,先为新的节点开辟空间,之后node指向新节点,如果node为NULL,则开辟失败返回NULL,如果开辟成功继续向下执行①prev和next置NULL ②写入节点的data值 返回node指针,BuyListNode函数结束
双向链表的初始化
在LTInit函数中,phead得到node的值 已知phead存储的值为00 c0 a0 98,求phead-next phead;和phead-prev phead;执行完后按小端序计算0x00c0a098~0x00c0a09f处的数据
解:
按照结构体成员变量定义的先后顺序
phead-prev存储在0x00C0A098~0x00C0A09B处,phead-next存储在0x00C0A09C~0x00C0A09F处 因此答案为98 a0 c0 00 98 a0 c0 00 返回phead后,LTInit函数结束
在TestList函数中,plist得到phead的值 调用LTPushBack函数
在LTPushBack函数中,phead得到plist的值(这里没有传二级指针,修改结构体成员变量的值只需要一级指针),断言phead,确保phead不为NULL
调用BuyListNode,返回新节点的地址给newnode
只有带哨兵位的头结点时,LTNode* tail phead-prev;等价为LTNode* tail phead; LTPushBack函数结束
剩下的分析思想一样,略去
2.双向链表的打印
让cur指针指向head节点的下一个节点,循环打印,当cur直到head时,停止打印
代码
void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur phead-next;printf(head);while (cur ! phead){printf(%d, cur-data);cur cur-next;}printf(\n);
} 3.双向链表的尾删
尾删要单独判断是否只有带哨兵位的头节点
写一个LTEmpty函数
bool LTEmpty(LTNode* phead)
{assert(phead);return phead-next phead;
}
直接将phead-next phead结果的真假返回,比if判断要简洁 void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//注意感叹号LTNode* tail phead-prev;LTNode* tailPrev tail-prev;//定义指向tail的前一个节点的指针tailPrev-next phead;phead-prev tailPrev;free(tail);tail NULL;
}
