网站权限怎么设置,九斗云网络推广营销数据,wordpress找回密码,全国领先网站制作目录 双向链表
双向链表的初始化#xff08;与单链表类似#xff09;
增#xff1a;
Ⅰ#xff09;头插法
Ⅱ#xff09;尾插法
Ⅲ#xff09;中间插入
删
改
查
整体代码示例#xff1a; 循环链表
循环单链表
编辑 循环双链表 双向链表
不同于单链表与单链表类似
增
Ⅰ头插法
Ⅱ尾插法
Ⅲ中间插入
删
改
查
整体代码示例 循环链表
循环单链表
编辑 循环双链表 双向链表
不同于单链表双向链表不仅可以往后指向还可以往前指向则双向链表是在单链表的基础上每个结点增加一个指针域这个指针域保存上一个结点的地址 pre指针域 保存前一个结点的地址 数据域 data next指针域 保存后一个结点的地址 //双向链表的结构体
typedef struct Node {struct Node* pre;int data;struct Node* next;
}Node,*LinkList; 由003——单链表可知单链表分为带头结点的不带头结点的双向链表也是同理上图的是带头结点的
双向链表的初始化 与单链表类似
LinkList InitLinkList() {Node* p (Node*)malloc(sizeof(Node));//申请头结点if (p NULL) {printf(空间分配失败\n);}else {//p-data 脏数据不用管p-prep-next NULL;//注意该语句的执行方向是从右往左/*p-pre NULL;p-next NULL;*/}return p;
}
int main() {LinkList L InitLinkList();
}
增
双向链表中增加一个结点数据
Ⅰ头插法
固定在头结点和首元结点之间插入一个结点头结点之后如下图的例子 为了方便分析我们为示意图进行编号 注意在这里对数据进行处理时我们不能使得这个线单向的无论是正向还是负向断掉比如像下面这种情况就是错误的 正确的顺序应该是先处理③和④然后再处理①和②顺序并不唯一 下面代码并不完整
//头插法
LinkList HeadInsert(LinkList L, int k) {//先申请一个新的结点用来保存数据kNode* s (Node*)malloc(sizeof(Node));if (s NULL) {printf(空间分配失败/n);}else {s-data k;//将数据传给新申请的结点ss-pre L;//3s-next L-next;//4L-next s;//1s-next-pre s;//2}return L;
}或者可以写成3421还有其他写法 s-pre L; s-next L-next; L-next-pre s; L-next s;
此时还要考虑L为空的情况因为这个时候的②是不存在的 所以在我们更改②这条线之前需要进行一个判断
//头插法
LinkList HeadInsert(LinkList L, int k) {//先申请一个新的结点用来保存数据kNode* s (Node*)malloc(sizeof(Node));if (s NULL) {printf(空间分配失败/n);}else {s-data k;//将数据传给新申请的结点ss-pre L;//3s-nextL-next;//4L-next s;//1if (s-next ! NULL) {s-next-pre s;//2}}return L;
} Ⅱ尾插法
从头结点开始遍历找到尾结点在尾结点的后面插入新的结点需要多维护一个pre
//尾插法
LinkList RearInsert(LinkList L, int k) {Node* p L; //指针指p向头结点while (p-next ! NULL) {p p-next;}//循环结束后指针p指向最后一个结点//先申请一个新的结点用来保存数据kNode* s (Node*)malloc(sizeof(Node));if (s NULL) {printf(空间分配失败\n);return L;}else {s-data k;//将数据传给新申请的结点ss-next p-next;s-pre p;p-next s;}return L;
}Ⅲ中间插入 //中间插入
//首先需要一个查找函数,并且返回该结点的地址
Node* find(LinkList L, int k) {Node* p L-next;while (p ! NULL p-data ! k) {//出现NULL-data!k会报错所以这两项的顺序不可以颠倒p p-next;}return p;//要么为空要么保存所要数据
}
//中间插入的函数
Node* MidInsert(LinkList L, int x, int k) {//在元素x后面插入数据kNode* p find(L, x);if (p NULL) {printf(数据%d不存在,无法找到插入位置插入失败\n, x);return L;}Node* s (Node*)malloc(sizeof(Node));if (s NULL) {printf(空间分配失败插入失败\n);return L;}else {s-data k;s-next p-next;p-next s;if (s-next ! NULL) {s-next-pre s;}}return L;
}
删
删除如下面图示 修改后的结果 //删除
LinkList Delete(LinkList L, int k) {if (L-next NULL) {printf(空链表删除失败\n);return L;}//找到k所在的结点pNode* p find(L, k);if (p NULL) {printf(数据%d不存在删除失败\n);return L;}//删除p-pre-next p-next;if (p-next ! NULL) {p-next-pre p-pre;}//防止p成为空指针free(p);p NULL;return L;}改
修改代码与单链表是相同的
//修改
LinkList Replace(LinkList L, int x, int k) {Node* p find(L, x);if (p NULL) {printf(数据%d不存在无法找到修改位置修改失败\n, x);return L;}else {p-data k;}return L;
}
查
查找代码与单链表是相同的
Node* find(LinkList L, int k) {Node* p L-next;while (p ! NULL p-data ! k) {//出现NULL-data!k会报错所以这两项的顺序不可以颠倒p p-next;}return p;//要么为空要么保存所要数据
}
整体代码示例
#includestdio.h
#includestdlib.h
//双向链表的结构体
typedef struct Node {struct Node* pre;int data;struct Node* next;
}Node,*LinkList;LinkList InitLinkList() {Node* p (Node*)malloc(sizeof(Node));//申请头结点if (p NULL) {printf(空间分配失败\n);}else {//p-data 脏数据不用管p-prep-next NULL;//注意该语句的执行方向是从右往左/*p-pre NULL;p-next NULL;*/}return p;
}//头插法
LinkList HeadInsert(LinkList L, int k) {//先申请一个新的结点用来保存数据kNode* s (Node*)malloc(sizeof(Node));if (s NULL) {printf(空间分配失败/n);}else {s-data k;//将数据传给新申请的结点ss-pre L;//3s-nextL-next;//4L-next s;//1if (s-next ! NULL) {s-next-pre s;//2}}return L;
}//尾插法
LinkList RearInsert(LinkList L, int k) {Node* p L; //指针指p向头结点while (p-next ! NULL) {p p-next;}//循环结束后指针p指向最后一个结点//先申请一个新的结点用来保存数据kNode* s (Node*)malloc(sizeof(Node));if (s NULL) {printf(空间分配失败\n);return L;}else {s-data k;//将数据传给新申请的结点ss-pre p;//3s-next p-next;//4p-next s;//1if (s-next ! NULL) {s-next-pre s;//2}}return L;
}//中间插入
//首先需要一个查找函数,并且返回该结点的地址
Node* find(LinkList L, int k) {Node* p L-next;while (p ! NULL p-data ! k) {//出现NULL-data!k会报错所以这两项的顺序不可以颠倒p p-next;}return p;//要么为空要么保存所要数据
}
//中间插入的函数
Node* MidInsert(LinkList L, int x, int k) {//在元素x后面插入数据kNode* p find(L, x);if (p NULL) {printf(数据%d不存在,无法找到插入位置插入失败\n, x);return L;}Node* s (Node*)malloc(sizeof(Node));if (s NULL) {printf(空间分配失败插入失败\n);return L;}else {s-data k;s-next p-next;p-next s;if (s-next ! NULL) {s-next-pre s;}}return L;
}//修改
LinkList Replace(LinkList L, int x, int k) {Node* p find(L, x);if (p NULL) {printf(数据%d不存在无法找到修改位置修改失败\n, x);return L;}else {p-data k;}return L;
}//删除
LinkList Delete(LinkList L, int k) {if (L-next NULL) {printf(空链表删除失败\n);return L;}//找到k所在的结点pNode* p find(L, k);if (p NULL) {printf(数据%d不存在删除失败\n);return L;}//删除p-pre-next p-next;if (p-next ! NULL) {p-next-pre p-pre;}//防止p成为空指针free(p);p NULL;return L;}void show(LinkList L) {Node* p L-next;while (p ! NULL){printf(%d\t, p-data);p p-next;}
}int main() {LinkList L InitLinkList();L HeadInsert(L, 10);L HeadInsert(L, 22);L HeadInsert(L, 16);L HeadInsert(L, 45);L RearInsert(L, 77);L MidInsert(L, 77,99);L Delete(L, 10);show(L);return 0;}
运行结果 循环链表
循环单链表
循环链表只需要让最后一个结点的指针域指向头结点 那么循环链表和单链表几乎没有太大差异,只是在为空的一些位置改成头结点
#includestdio.h
#includestdlib.h
typedef struct Node {int data; //该节点的数据struct Node* next;
}Node,*LinkList;//初始化一个带头结点的空的循环链表
LinkList InitLinkList() {Node* s (Node*)malloc(sizeof(Node));//申请头结点if (s NULL) {printf(空间分配失败\n);}else {//s-data 脏数据不用管s-next s;//改变。。。。。。。。。。。。}return s;
}//头插法
LinkList HeadInsert(LinkList L, int k) {//先申请一个新的结点用来保存数据kNode* s (Node*)malloc(sizeof(Node));if (s NULL) {printf(空间分配失败/n);}else {s-data k;//将数据传给新申请的结点ss-next L-next;L-next s;}return L;
}//尾插法
LinkList RearInsert(LinkList L, int k) {Node* p L; //指针指p向头结点while (p-next ! L) {//改变。。。。。。。。。。。。p p-next;}//循环结束后指针p指向最后一个结点//先申请一个新的结点用来保存数据kNode* s (Node*)malloc(sizeof(Node));if (s NULL) {printf(空间分配失败\n);return L;}else {s-data k;//将数据传给新申请的结点ss-next p-next;//改变。。。。。。。。。。。。p-next s;}return L;
}//中间插入
//首先需要一个查找函数,并且返回该结点的地址
Node* find(LinkList L, int k) {Node* p L-next;while (p!L p-data ! k) {//改变。。。。。。。。。。。。
//出现NULL-data!k会报错所以这两项的顺序不可以颠倒p p-next;}return p;//要么为空要么保存所要数据
}
//中间插入的函数
Node* MidInsert(LinkList L, int x, int k) {//在元素x后面插入数据kNode* p find(L, x);if (p L) {//改变。。。。。。。。。。。。printf(数据%d不存在,无法找到插入位置插入失败\n,x);return L;}Node* s (Node*)malloc(sizeof(Node));if (s NULL) {printf(空间分配失败插入失败\n);return L;}else {s-data k;s-next p-next;p-next s;}return L;
}//修改
LinkList Replace(LinkList L, int x, int k) {Node* p find(L, x);if (p L) {//改变。。。。。。。。。。。。printf(数据%d不存在无法找到修改位置修改失败\n, x);return L;}else {p-data k;}return L;
}//删除
LinkList Delete(LinkList L, int k) {if (L-next L) {//改变。。。。。。。。。。。。printf(数据%d不存在删除失败\n, k);return L;}//找到k所在的结点p和上一个结点Node* pre L;Node* p L-next;while (p!Lp-data!k)//改变。。。。。。。。。。。。{pre p;p p-next;}if (p L) {//改变。。。。。。。。。。。。printf(数据%d不存在删除失败\n, k);return L;}pre-next p-next;free(p);p NULL;//防止p成为野指针return L;
}void show(LinkList L) {Node* p L-next;while (p! L)//改变。。。。。。。。。。。。{printf(%d\t, p-data);p p-next;}
}
int main() {LinkList L NULL;L InitLinkList();LHeadInsert(L,10);L HeadInsert(L, 8);L RearInsert(L, 15);L MidInsert(L, 5, 55);LReplace(L, 8, 88);L Delete(L, 8);show(L);return 0;
}
运行结果 循环双链表
循环双链表与之同理 #includestdio.h
#includestdlib.h
//双向链表的结构体
typedef struct Node {struct Node* pre;int data;struct Node* next;
}Node, * LinkList;LinkList InitLinkList() {Node* p (Node*)malloc(sizeof(Node));//申请头结点if (p NULL) {printf(空间分配失败\n);}else {//p-data 脏数据不用管// p-nextp-prep;p-next p;p-pre p;}return p;
}//头插法
LinkList HeadInsert(LinkList L, int k) {//先申请一个新的结点用来保存数据kNode* s (Node*)malloc(sizeof(Node));if (s NULL) {printf(空间分配失败/n);}else {s-data k;//将数据传给新申请的结点ss-pre L;//3s-next L-next;//4L-next s;//1s-next-pre s;//2}return L;
}//尾插法
LinkList RearInsert(LinkList L, int k) {Node* s (Node*)malloc(sizeof(Node));if (s NULL){printf(空间分配失败\n);return L;}s-data k;//找尾节点Node* p L;while (p-next ! L){p p-next;}s-next p-next;s-pre p;p-next s;s-next-pre s;return L;
}//中间插入
//首先需要一个查找函数,并且返回该结点的地址
Node* find(LinkList L, int k) {//查找数据k所在的节点并且返回该节点的地址 Node* p L-next;while (p ! L p-data ! k){p p-next;}return p;
}
//中间插入的函数
Node* MidInsert(LinkList L, int x, int k) {//数据x后插入数据k Node* s (Node*)malloc(sizeof(Node));if (s NULL){printf(空间分配失败\n);return L;}s-data k;//找x所在节点 Node* p find(L, x);if (p L){printf(数据%d不存在插入失败\n, x);return L;}s-pre p;//3s-next p-next;//4p-next s;//1s-next-pre s;//2return L;}//修改
LinkList Replace(LinkList L, int x, int k) {Node* p find(L, x);if (p L) {printf(数据%d不存在无法找到修改位置修改失败\n, x);return L;}else {p-data k;}return L;
}//删除
LinkList Delete(LinkList L, int k) {if (L-next L){printf(空链表删除失败\n);return L;}//找k所在的节点pNode* p find(L, k);if (p L){printf(数据%d不存在删除失败\n, k);return L;}//删除p-pre-next p-next;p-next-pre p-pre;free(p);p NULL;return L;
}void show(LinkList L) {Node* p L-next;while (p ! L){printf(%d\t, p-data);p p-next;}
}int main() {LinkList L InitLinkList();L HeadInsert(L, 10);L HeadInsert(L, 22);L HeadInsert(L, 16);L HeadInsert(L, 45);L RearInsert(L, 77);L MidInsert(L, 77, 99);L Delete(L, 10);show(L);return 0;} 运行结果
