家教网站如何做,ipv6做网站,外包网址,wordpress标签页模板目录
一.双向链表的结构
二. 双向链表的实现
1. 在List.h中结构体的定义和各函数的声明
1.1 结构体#xff08;节点#xff09;的定义
1.2 各函数的声明
2. 在List.c中各函数的实现
2.1 初始化 LTInit
2.2 尾插 LTPushBack
2.3 打印 LTPrint
2.4 头插 LTPushFron…目录
一.双向链表的结构
二. 双向链表的实现
1. 在List.h中结构体的定义和各函数的声明
1.1 结构体节点的定义
1.2 各函数的声明
2. 在List.c中各函数的实现
2.1 初始化 LTInit
2.2 尾插 LTPushBack
2.3 打印 LTPrint
2.4 头插 LTPushFront
2.5 尾删 LTPopBack
2.6 头删 LTPopFront
2.7 在指定位置后插入数据 LTInsert
2.8 查找 LTFind
2.9 删除指定位置节点 LTErase
2.10 销毁 LTDestroy
三. 顺序表和双向链表的优缺点分析
四. 参考代码 1. List.h
2. List.c
3. test.c 一.双向链表的结构 注意这里的“带头”跟前面我们说的“头节点”是两个概念实际前面的在单链表阶段称呼不严谨但是为了更好的理解就直接称为单链表的头节点。
带头链表里的头节点实际为“哨兵位”哨兵位节点不存储任何有效元素只是站在这里“放哨的”
“哨兵位”存在的意义
遍历循环链表避免死循环。
二. 双向链表的实现
注本次我们将实现一个双向带头循环链表。
1. 在List.h中结构体的定义和各函数的声明
1.1 结构体节点的定义 //重命名数据类型
typedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNode* prev;//指向前一个节点struct ListNode* next;//指向后一个节点
}LTNode; 1.2 各函数的声明 //初始化
//void LTInit(LTNode** pphead);
LTNode* LTInit(void);//尾插 -- 不改变哨兵位 -- 传一级指针
void LTPushBack(LTNode* phead, LTDataType x);//打印
void LTPrint(LTNode* phead);//头插
void LTPushFront(LTNode* phead, LTDataType x);//尾删
void LTPopBack(LTNode* phead);//头删
void LTPopFront(LTNode* phead);//在指定位置后插入数据
void LTInsert(LTNode* pos, LTDataType x);//查找
LTNode* LTFind(LTNode* phead, LTDataType x);//删除指定位置节点
void LTErase(LTNode* pos);//销毁
void LTDestroy(LTNode* phead); 2. 在List.c中各函数的实现 2.1 初始化 LTInit 既然涉及到插入新节点那我们就需要创建一个新节点由于每次插入都需要创建新节点所以我们设计一个新函数专门来创建新节点。 LTNode* LTBuyNode(LTDataType x)
{LTNode* node (LTNode*)malloc(sizeof(LTNode));if (node NULL){perror(malloc failed);exit(1);}node-data x;node-prev node-next node;return node;
} 注意 1. 每次malloc申请空间后应当检查是否申请成功。 2. 将新申请的节点的前后指针指向自己实现循环。 初始化操作我们需要创建哨兵节点哨兵节点所带的值可以任意。 LTNode* LTInit(void)
{LTNode* node LTBuyNode(EOF);return node;
} 2.2 尾插 LTPushBack 要对链表进行尾插找到链表的哨兵节点然后新节点插入哨兵节点的前一位由于链表循环所以也相当于尾插在链表尾。 void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);//phead ..... phead-prev newnodenewnode-prev phead-prev;newnode-next phead;phead-prev-next newnode;phead-prev newnode;
}2.3 打印 LTPrint 我们创建一个指针pcur指向哨兵节点的下一个节点并沿着链表向后依次打印如果等于哨兵节点就说明已经遍历完成。 void LTPrint(LTNode* phead)
{LTNode* pcur phead-next;while (pcur ! phead){printf(%d-, pcur-data);pcur pcur-next;}printf(\n);
}2.4 头插 LTPushFront 与尾插类似在哨兵节点的下一位进行插入注意连接好前后指针。 void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);//phead newnode phead-next ......newnode-next phead-next;newnode-prev phead;phead-next-prev newnode;phead-next newnode;
}2.5 尾删 LTPopBack 尾删前要注意链表有效且不为空然后断开要释放节点和前后节点的前后指针最后释放该节点。 void LTPopBack(LTNode* phead)
{assert(phead phead-next ! phead);//链表有效且不为空只有一个哨兵位//phead ...... del-prev(phead-prev-prev) del(phead-prev)LTNode* del phead-prev;del-prev-next phead;phead-prev del-prev;//删除del节点free(del);del NULL;
}2.6 头删 LTPopFront 与头删类似在哨兵节点的下一位进行删除注意连接好前后指针。 void LTPopFront(LTNode* phead)
{assert(phead phead-next ! phead);LTNode* del phead-next;//phead del(phead-next) del-next(phead-next-next) ......phead-next del-next;del-next-prev phead;//删除del节点free(del);del NULL;
} 2.7 在指定位置后插入数据 LTInsert 函数参数中提供了插入位置pos连接好前后指针即可。 void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode LTBuyNode(x);//... pos newnode pos-next ...newnode-next pos-next;newnode-prev pos;pos-next-prev newnode;pos-next newnode;
} 2.8 查找 LTFind 与打印类似遍历一次链表查找是否有符合条件的节点如果有返回节点指针如果没有返回空指针。 LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur phead-next;while (pcur ! phead){if (pcur-data x){return pcur;}pcur pcur-next;}return NULL;
}2.9 删除指定位置节点 LTErase 与在打印和查找类似函数参数中提供了删除位置pos处理好前后指针即可。 void LTErase(LTNode* pos)
{//pos理论上不能为phead但是参数有限无法校验assert(pos);//... pos-prev pos pos-next ...pos-prev-next pos-next;pos-next-prev pos-prev;free(pos);pos NULL;
} 2.10 销毁 LTDestroy 与在指定位置后插入数据类似从哨兵节点的下一位遍历一次链表遍历的同时用双指针法依次释放节点最后释放哨兵节点。 void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur phead-next;while(pcur ! phead){LTNode* next pcur-next;free(pcur);pcur next;}//销毁pheadfree(phead);phead NULL;pcur NULL;
} 我们可以发现由于双向链表具有指向前后节点的指针代码量大大减少但是也需要处理好指针之间的关系。
三. 顺序表和双向链表的优缺点分析
顺序表和双向链表的优缺点 不同点 顺序表 链表单链表 存储空间上 物理上一定连续 逻辑上连续但物理上不一定连续 随机访问 支持O(1) 不支持O(N) 任意位置插入或者删除元素 可能需要搬移元素效率低O(N) 只需修改指针指向 插入 动态顺序表空间不够时需要扩容 没有容量的概念 应用场景 元素高效存储频繁访问 任意位置插入和删除频繁
四. 参考代码 1. List.h
#pragma once#include stdio.h
#include stdlib.h
#include assert.h//重命名数据类型
typedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNode* prev;//指向前一个节点struct ListNode* next;//指向后一个节点
}LTNode;//初始化
//void LTInit(LTNode** pphead);
LTNode* LTInit(void);//尾插 -- 不改变哨兵位 -- 传一级指针
void LTPushBack(LTNode* phead, LTDataType x);//打印
void LTPrint(LTNode* phead);//头插
void LTPushFront(LTNode* phead, LTDataType x);//尾删
void LTPopBack(LTNode* phead);//头删
void LTPopFront(LTNode* phead);//在指定位置后插入数据
void LTInsert(LTNode* pos, LTDataType x);//查找
LTNode* LTFind(LTNode* phead, LTDataType x);//删除指定位置节点
void LTErase(LTNode* pos);//销毁
void LTDestroy(LTNode* phead);
2. List.c
#include List.hLTNode* LTBuyNode(LTDataType x)
{LTNode* node (LTNode*)malloc(sizeof(LTNode));if (node NULL){perror(malloc failed);exit(1);}node-data x;node-prev node-next node;return node;
}//void LTInit(LTNode** pphead)
//{
// //给双向链表创建一个哨兵位
// *pphead LTBuyNode(-1);
//}
LTNode* LTInit(void)
{LTNode* node LTBuyNode(EOF);return node;
}void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);//phead ..... phead-prev newnodenewnode-prev phead-prev;newnode-next phead;phead-prev-next newnode;phead-prev newnode;
}void LTPrint(LTNode* phead)
{LTNode* pcur phead-next;while (pcur ! phead){printf(%d-, pcur-data);pcur pcur-next;}printf(\n);
}void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);//phead newnode phead-next ......newnode-next phead-next;newnode-prev phead;phead-next-prev newnode;phead-next newnode;
}void LTPopBack(LTNode* phead)
{assert(phead phead-next ! phead);//链表有效且不为空只有一个哨兵位//phead ...... del-prev(phead-prev-prev) del(phead-prev)LTNode* del phead-prev;del-prev-next phead;phead-prev del-prev;//删除del节点free(del);del NULL;
}void LTPopFront(LTNode* phead)
{assert(phead phead-next ! phead);LTNode* del phead-next;//phead del(phead-next) del-next(phead-next-next) ......phead-next del-next;del-next-prev phead;//删除del节点free(del);del NULL;
}LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur phead-next;while (pcur ! phead){if (pcur-data x){return pcur;}pcur pcur-next;}return NULL;
}void LTErase(LTNode* pos)
{//pos理论上不能为phead但是参数有限无法校验assert(pos);//... pos-prev pos pos-next ...pos-prev-next pos-next;pos-next-prev pos-prev;free(pos);pos NULL;
}void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur phead-next;while(pcur ! phead){LTNode* next pcur-next;free(pcur);pcur next;}//销毁pheadfree(phead);phead NULL;pcur NULL;
}void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode LTBuyNode(x);//... pos newnode pos-next ...newnode-next pos-next;newnode-prev pos;pos-next-prev newnode;pos-next newnode;
}
3. test.c
#include List.hvoid ListTest01()
{LTNode* plist NULL;plist LTInit();//LTPushBack(plist, 1);//LTPushBack(plist, 2);//LTPushBack(plist, 3);//LTPushBack(plist, 4);//LTPushBack(plist, 5);//LTPrint(plist);LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPushFront(plist, 5);LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//LTNode* find NULL;//find LTFind(plist, 2);//if (find)//{// printf(找到了\n);//}//else//{// printf(找不到\n);//}//find LTFind(plist, 7);//if (find)//{// printf(找到了\n);//}//else//{// printf(找不到\n);//}//LTNode* find NULL;//find LTFind(plist, 2);//if (find)//{// printf(找到了\n);//}//else//{// printf(找不到\n);//}//LTInsert(find, 6);//LTPrint(plist);//LTErase(find);//find NULL;//LTPrint(plist);LTDestroy(plist);plist NULL;
}int main()
{ListTest01();return 0;
}
