做中英双语切换的网站,公众号图文模板免费,做乒乓球网站的图片,健身房网站的建设情况1、双向链表的结构 注意#xff1a;这里的 带头 跟前面我们说的 头结点 是两个概念#xff0c;实际前面的在单链表阶段称呼不严谨#xff0c;但是为了同学们更好的理解就直接称为单链表的头结点。
带头链表里的头结点#xff0c;实际为 哨兵…1、双向链表的结构 注意这里的 带头 跟前面我们说的 头结点 是两个概念实际前面的在单链表阶段称呼不严谨但是为了同学们更好的理解就直接称为单链表的头结点。
带头链表里的头结点实际为 哨兵位 哨兵位节点不存储任何有效元素只是站在这里 放哨的。
哨兵位 存在的意义
遍历循环链表避免死循环。
注意双向链表中哨兵位的下一个节点是链表的第一个节点(头结点)。哨兵位的前一个节点是链表的最后一个节点(尾结点)。所以双向链表的头插是在哨兵位的后面插入数据。尾插则是在哨兵位之前插入数据。
哨兵位是作为头结点和尾结点的中点是头结点的起点也是尾节点的终点。这样解释更容易理解。 2、 双向链表的实现
List.h 链表函数和链表节点类型的声明
#pragma once
#include stdio.h
#include stdlib.h
#include assert.htypedef int SLDataType;
typedef struct ListNode
{SLDataType data;//存储数据struct ListNode* prve;//存储前一个节点的地址struct ListNode* next;//存储下一个节点的地址
}SList;
SList* SLInit();void SLPushBack(SList* phead, SLDataType x);//尾插
void SLPrint(SList* phead);//显示链表数据
void SLPustFront(SList* phead, SLDataType x);//头插
void SLPopBack(SList* phead);//尾删
void SLPopFront(SList* phead);//头删
void SLInsert(SList* pos, SLDataType x);//指定位置插入
SList* SLfind(SList* phead, SLDataType x);//查找节点
void SLEarse(SList* pos);//指定位置删除
void SLDestory(SList** pphead);//链表销毁
List.c 链表函数的实现:
#include List.h
//链表初始化
SList* SLInit()
{SList* phead (SList*)malloc(sizeof(SList));if (phead NULL){perror(malloc error);return NULL;}phead-data -1;//因为是循环链表所以初始化要遵循循环格式phead-next phead;phead-prve phead;return phead;
}
//创建链表节点
SList* ListBuyNode(SLDataType x)
{SList* retNode (SList*)malloc(sizeof(SList));if (retNode NULL){perror(malloc error);return NULL;}retNode-data x;retNode-prve retNode;retNode-next retNode;return retNode;
}
//链表尾插
void SLPushBack(SList* phead, SLDataType x)
{assert(phead);SList* Node ListBuyNode(x);Node-prve phead-prve;Node-next phead;phead-prve-next Node;phead-prve Node;
}
//链表数据显示
void SLPrint(SList* phead)
{assert(phead);SList* pcur phead-next;while (pcur ! phead)//哨兵位作为结束标识{printf(%d, pcur-data);if (pcur-next ! phead)printf(-);pcur pcur-next;}printf(\n);
}
//链表头插
void SLPustFront(SList* phead, SLDataType x)
{assert(phead);SList* Node ListBuyNode(x);Node-next phead-next;Node-prve phead;phead-next-prve Node;phead-next Node;
}
//链表尾删
void SLPopBack(SList* phead)
{assert(phead);assert(phead-next ! phead);SList* del phead-prve;del-prve-next phead;phead-prve del-prve;free(del);del NULL;
}
//链表头删
void SLPopFront(SList* phead)
{assert(phead);assert(phead-next ! phead);SList* del phead-next;del-next-prve phead;phead-next del-next;free(del);del NULL;
}
//指定位置插入
void SLInsert(SList* pos, SLDataType x)
{assert(pos);SList* Node ListBuyNode(x);Node-next pos-next;Node-prve pos;pos-next Node;Node-next-prve Node;
}
//查找节点
SList* SLfind(SList* phead, SLDataType x)
{assert(phead);SList* pcur phead-next;while (pcur ! phead){if (pcur-data x){return pcur;}pcur pcur-next;}return NULL;
}
//指定位置删除
void SLEarse(SList* pos)
{assert(pos);pos-prve-next pos-next;pos-next-prve pos-prve;free(pos);pos NULL;
}
//链表销毁
void SLDestory(SList** pphead)
{assert(pphead *pphead);SList* pcur (*pphead)-next;while (pcur ! *pphead){SList* next pcur-next;free(pcur);pcur next;}free(*pphead);*pphead NULL;
}
test.c 函数的调用:
#include List.hvoid SLtest()
{SList* plist NULL;plist SLInit();//尾插SLPushBack(plist, 1);SLPushBack(plist, 2);SLPushBack(plist, 3);SLPushBack(plist, 4);SLPrint(plist);//打印:1-2-3-4//头插SLPustFront(plist, 5);SLPustFront(plist, 6);SLPustFront(plist, 7);SLPrint(plist);//打印:7-6-5-1-2-3-4//尾删SLPopBack(plist);SLPrint(plist);//打印:7-6-5-1-2-3//头删SLPopFront(plist);SLPrint(plist);//打印:6-5-1-2-3//指定位置插入SList* find SLfind(plist, 5);SLInsert(find, 11);SLPrint(plist);//打印:6-5-11-1-2-3//指定位置删除find SLfind(plist, 1);SLEarse(find);SLPrint(plist);//打印:6-5-11-2-3//链表销毁SLDestory(plist);
}
int main()
{SLtest();return 0;
} 3、顺序表和双向链表的优缺点分析
不同点顺序表链表存储空间上物理上一定连续逻辑上连续但物理上不一定连续随机访问支持O(1)不支持O(N)任意位置插入或者删除元素可能需要搬移元素效率低O(N)只需要修改指针指向插入动态顺序表空间不够时需要扩容没有容量的概念应用场景元素高效存储频繁访问任意位置插入和删除频繁 数据结构第3篇笔记到这里也就结束了我们下一篇笔记再见-
