电脑维护网站模板,40个界面ui外包多少钱,成都网站制作scgckj,怎样做访问外国网站才能不卡目录 认识带头双向循环链表
双向链表
循环链表
带头链表
带头双向循环链表
双向链表的优势和不足#xff1a;
顺序表的优势和不足#xff1a;
实现带头双向循环链表
创建带头双向循环链表 初始化
创建返回链表的头结点
打印链表 尾插
尾删
头插
头删
查找
在…目录 认识带头双向循环链表
双向链表
循环链表
带头链表
带头双向循环链表
双向链表的优势和不足
顺序表的优势和不足
实现带头双向循环链表
创建带头双向循环链表 初始化
创建返回链表的头结点
打印链表 尾插
尾删
头插
头删
查找
在pos位置前插入
删除pos位置
销毁
总代码
ListNode.h
ListNode.c
test.c 认识带头双向循环链表
双向链表 我们之前认学习的单链表是包含一个next指针指向下一个结点而双向链表既有next指针又有一个前指针指向前一个结点
循环链表 循环链表就是最后一个结点的next不指向NULL指向第一个结点
带头链表
带头链表就是带哨兵位的头结点head头结点不存数据 带头双向循环链表 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势实现反而简单 双向链表的优势和不足 双向链表的优势 任意位置插入删除都是O(1)按需申请释放合理利用空间不存在浪费 问题 下标的随机访问不方便O(N) 顺序表的优势和不足 顺序表的优势 支持下标的随机访问O(1) 问题 头插或中间插入的效率低O(N)空间不够需要扩容有一定的消耗且可能存在一定的空间浪费只适合尾插尾删 实现带头双向循环链表
同样我们创建三个文件来实现 创建带头双向循环链表
我们在结构体中定义val存数据prev指向前一个结点next指向下一个结点 初始化
让phead-next和phead-prev都指向phead给phead-val赋值为-1最后返回phead 创建返回链表的头结点 打印链表 尾插 尾删 头插 头删 头结点不能删
所以我们要assert(phead-next ! phead) 查找 在pos位置前插入 特殊情况 LTInsert(phead-next,x)就是头插LTInsert(phead,x)就是尾插 删除pos位置 特殊情况 LTErase(phead-next)就是头删LTErase(phead-prev)就是尾删 销毁 总代码
ListNode.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
typedef int LTDataType;
typedef struct ListNode
{LTDataType val;struct ListNode* prev;struct ListNode* next;
}LTNode;//初始化
LTNode* LTInit();
//创建返回链表的头结点.
LTNode* CreateLTNode(LTDataType x);
//打印
void LTPrint(LTNode* phead);//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置前插入
void LTInsert(LTNode* pos, LTDataType x);
//删除pos位置
void LTErase(LTNode* pos);
//销毁
void LTDestroy(LTNode* phead);
ListNode.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeListNode.h
//初始化
LTNode* LTInit()
{LTNode* phead CreateLTNode(-1);phead-next phead;phead-prev phead;return phead;
}
//创建返回链表的头结点.
LTNode* CreateLTNode(LTDataType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-val x;newnode-next NULL;newnode-prev NULL;return newnode;
}
//打印
void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur phead-next;printf(哨兵位);while (cur ! phead){printf(%d, cur-val);cur cur-next;}printf(哨兵位\n);
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* tail phead-prev;LTNode* newnode CreateLTNode(x);tail-next newnode;newnode-prev tail;phead-prev newnode;newnode-next phead;
}
//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(phead-next ! phead);LTNode* tail phead-prev;LTNode* tailPrev tail-prev;free(tail);tailPrev-next phead;phead-prev tailPrev;
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode CreateLTNode(x);LTNode* first phead-next;newnode-next first;first-prev newnode;phead-next newnode;newnode-prev phead;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead-next ! phead);LTNode* first phead-next;LTNode* second first-next;phead-next second;second-prev phead;free(first);first NULL;
}
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){if (cur-val x){return cur;}cur cur-next;}return NULL;
}
//在pos位置前插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode CreateLTNode(x);LTNode* posprev pos-prev;posprev-next newnode;newnode-prev posprev;newnode-next pos;pos-prev newnode;
}
//删除pos位置
void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev pos-prev;LTNode* posnext pos-next;posprev-next posnext;posnext-prev posprev;free(pos);pos NULL;
}
//销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){LTNode* next cur-next;free(cur);cur next;}free(phead);phead NULL;
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeListNode.h
int main()
{LTNode* plist LTInit();//尾插LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//尾删LTPopBack(plist);LTPrint(plist);//头插LTPushFront(plist, 0);LTPrint(plist);//头删LTPopFront(plist);LTPrint(plist);//查找 pos前插LTNode* pos LTFind(plist, 3);LTInsert(pos, 3);LTPrint(plist);//删除pos位置LTErase(pos);LTPrint(plist);//销毁LTDestroy(plist);return 0;
}
