找大学生做家教的网站,网站开发与管理学什么,竞争对手网站分析,网站推广哪个平台最好目录 1. 双向链表的结构2. 实现双向链表预先的准备初始化尾插、头插尾删、头删查找在pos位置之后插⼊数据删除pos位置的数据 3. 顺序表和双向链表的分析 1. 双向链表的结构 注意#xff1a;这里的“带头”跟前面我们说的“头结点”是两个概念#xff0c;为了更好的理解直接称… 目录 1. 双向链表的结构2. 实现双向链表预先的准备初始化尾插、头插尾删、头删查找在pos位置之后插⼊数据删除pos位置的数据 3. 顺序表和双向链表的分析 1. 双向链表的结构 注意这里的“带头”跟前面我们说的“头结点”是两个概念为了更好的理解直接称为单链表的头结点
带头链表里的头结点实际为“哨兵位”哨兵位节点不存储任何有效数字知识站在这里“放哨”
“哨兵位”存在的意义 遍历循环链表避免死循环
2. 实现双向链表
预先的准备 typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* prev;struct ListNode* next;
}LTNode;初始化
注意双向链表是带有哨兵位的插入数据之前链表中必须要先初始化一个哨兵位
void LTInit(LTNode** pphead)
{*pphead (LTNode*)malloc(sizeof(LTNode));if (*pphead NULL){perror(malloc);exit(1);}(*pphead)-data -1;(*pphead)-next (*pphead)-prev *pphead;
}当链表中只有哨兵位节点的时候我们称该链为空链表 即哨兵位是不能删除也不能修改的即不能对哨兵位进行任何操作
尾插、头插 //不需要改变哨兵位则不需要传二级指针
//如果需要修稿哨兵位的话则传二级指针
//尾插
LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL){perror(malloc);exit(1);}newnode-data x;newnode-next newnode-prev newnode;
}
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);newnode-next phead;newnode-prev phead-prev;phead-prev-next newnode;phead-prev newnode;
}//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);//phead newnode phead-nextnewnode-next phead-next;newnode-prev phead;phead-next-prev newnode;phead-next newnode;
}单链表中涉及到二级指针单链表中的phead第一个节点可能为空 双向链表中不需要二级指针双向链表中的phead哨兵位不可能为空
尾删、头删 //头删、尾删
void LTPopBack(LTNode* phead)
{assert(phead);//链表为空只有一个哨兵位assert(phead-next ! phead);/*phead-prev-prev-next phead;phead-prev phead - prev-prev*/LTNode* del phead-prev;LTNode* prev del-prev;prev-next phead;phead-prev prev;free(del);del NULL;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead-next ! phead);LTNode* del phead-next;LTNode* next del-next;next-prev phead;phead-next next;free(del);del NULL;
}
查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur phead-next;while (pcur ! phead){if (pcur-data x){return pcur;}pcur pcur-next;}return NULL;
}在pos位置之后插⼊数据 /在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode LTBuyNode(x);//pos newnode pos-nextnewnode-next pos-next;newnode-prev pos;pos-next-prev newnode;pos-next newnode;}删除pos位置的数据 void LTErase(LTNode* pos)
{assert(pos);pos-next-prev pos-prev;pos-prev-next pos-next;free(pos);pos NULL;
}3. 顺序表和双向链表的分析
不同点顺序表链表单链表存储空间上物理上一定连续逻辑上连续但物理上不一定连续随机访问支持O1不支持 ON任意插入或者删除元素可能需要搬移元素效率低只需要修改指针指向插入动态顺序表空间不够时需要扩展没有容量的概念应用场景元素高效存储频繁访问任意位置插入和删除频繁
