网站建设推广特色,wordpress主体和模板,企业宣传册制作,查企业信息怎么查引言
单链表存在缺陷#xff1a;需要从头开始找前一个节点
解决方法#xff1a;双向链表
链表的结构#xff08;8种#xff09;#xff1a;
1. 单向#xff0c;双向
2. 带头、不带头 带头即为带哨兵位的头节点#xff0c;第一个节点不存储有效数据。带头节点#…引言
单链表存在缺陷需要从头开始找前一个节点
解决方法双向链表
链表的结构8种
1. 单向双向
2. 带头、不带头 带头即为带哨兵位的头节点第一个节点不存储有效数据。带头节点不需要改变传过来的指针也就是意味着不需要传二级指针了因为不管是头删还是尾删都不会改变头结点的位置故不用二级指针进行传参。做好不要用头节点存链表的长度 3. 循环非循环 之前说的链表里最后一个节点指向空指针循环链表里最后一个结点指向第一个结点的地址 链表结构可分为单向带头循环单向不带头循环将以上三类进行排列组合可得2*2*28种链表结构
这里我就说一下带头双向循环链表吧 图示方框为头节点不添加任何有效数据头节点的前驱指向3的位置3的后驱指向头节点图示就是带头双向循环链表了
我们先来简单实现带头双向循环链表吧
带头双向循环链表的初始化
将头节点的前驱和后驱均指向自己。
typedef double LTDataType;
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;int data;
}ListNode;
ListNode* ListInit();
//创建一个结点
ListNode* BuyListNode(LTDataType x)
{ListNode* newnode (ListNode*)malloc(sizeof(ListNode));newnode-data x;newnode-prev NULL;newnode-next NULL;return newnode;
}
初始化链表
ListNode* ListInit()
{ListNode* phead BuyListNode(0);phead-data phead;phead-prev phead;return phead;
}
带头双向循环链表的尾插
双向循环链表可直接通过头节点找到尾节点
将尾节点的next指向新建节点
新建节点prev指向最初尾节点
新建节点的next的指向头节点
头节点的prev指向新建节点。
//尾插
void ListPushBack(ListNode* phead, LTDataType x)
{//无论链表是否为空均可尾插ListNode* tail phead-prev;ListNode* newnode BuyListNode(x);newnode-prevtail;newnode-next phead;phead-prev newnode;} 带头双向链表的输出
遍历整个链表直到遍历到头节点循环
void ListPrint(ListNode* phead)
{assert(phead);//phead不能为空ListNode* cur phead-next;while (cur ! phead){printf(%d , cur-data);cur cur-next;}printf(\n);
}
带头双向链表的头删
记录第一个和第二个节点的位置
将头节点next指向第二个节点
第二个节点的prev指向头节点即可完成头删。
void ListPopFront(ListNode* phead, LTDataType x)
{assert(phead);assert(phead-next!NULL);//保证无结点时不删除ListNode* first phead-next;ListNode* second first-next;phead-next second;second-prev phead;free(first);first NULL;
}
带头双向链表的头插
首先要记录第一个节点的位置以防位置被覆盖
将头节点的next指向新建节点
新建节点的prev指向头节点
新建节点的next指向第一个节点
第一个节点的prev指向新建节点。
void ListPushFront(ListNode* phead, LTDataType x)
{assert(phead);ListNode* first phead-next;ListNode* newnode BuyListNode(x);phead-next newnode;newnode-prev phead;newnode-next first;first-prev newnode;
}
带头双向链表的尾删
记录左后一个节点以及倒数第二个节点的位置。
将倒数第二个节点的next指向头节点
头结点的prev指向倒数第二个节点
释放掉最后一个节点。
//尾删
void ListPopBack(ListNode* phead)
{assert(phead);assert(phead-next ! NULL);//不可把头结构删除ListNode* tail phead-prev;ListNode* prev tail-prev;prev-next phead;phead-prev prev;free(tail);tail NULL;
}
带头双向循环链表的查找 遍历链表直到遍历至头节点若找到要找的值就返回该地址遍历完还没有找到就返回NULL
//查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{assert(phead);ListNode* cur phead-next;while (cur ! phead){if (cur-data x)return cur;curcur-next;}return NULL;
}
在带头双向链表的某个节点前插入新的结点
记录插入位置的前一个位置
新建链表的prev指向前一个链表
前一个链表的next指向新建链表
新建链表的next指向插入位置
插入位置的prev指向前一个位置。
// 在pos之前插入x
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* prev pos-prev;ListNode* newnode BuyListNode(x);newnode-prev prev;prev-next newnode;newnode-next pos;pos-prev newnode;
} 删除带头双向链表的某个结点
记录删除结点位置的前一个节点位置以及后一个节点的位置
前一个节点的next指向后一个节点
后一个节点的prev指向前一个节点
释放要删除节点的指针
//删除pos位置的值
void ListErase(ListNode* pos)
{assert(pos);ListNode* prev pos-prev;ListNode* next pos-next;prev-next next;next-prev-prev;free(pos);posNULL;
}
释放掉整个链表 遍历整个链表注意在释放节点时要先记录下一个节点遍历完之后释放头节点。
//释放链表
void ListDestory(ListNode* phead)
{assert(phead);ListNode* cur phead-next;while (cur ! phead){ListNode* next cur-next;free(cur);cur next;}free(phead);
}
双向带头循环链表的特点结构复杂但操作简单
带头双向循环 -- 最优链表结构任意位置插入删除数据空间复杂度都是0(1)。
