深圳网站建设号,信息化管理系统软件,宁波网站开发建设,中企网络科技建站数据结构–双链表
单链表 VS 双链表 单链表#xff1a;无法逆向检索#xff0c;有时候不太方便 双链表#xff1a;可进可退#xff0c;存储密度更低一丢丢 双链表的定义
typedef struct DNode
{ElemType data;struct DNode *prior, *next;
}DNode, *DLinkList;双链表的初…数据结构–双链表
单链表 VS 双链表 单链表无法逆向检索有时候不太方便 双链表可进可退存储密度更低一丢丢 双链表的定义
typedef struct DNode
{ElemType data;struct DNode *prior, *next;
}DNode, *DLinkList;双链表的初始化 bool InitDLinkList(DLinkList L)
{L (DNode*)malloc(sizeof(DNode));if (L NULL) return false;L-prior NULL;L-next NULL;return true;
}判断双链表是否为空
bool Empty(DLinkList L)
{return L-next NULL;
}双链表的插入
在p结点之后插入s结点 特殊处理p是最后一个结点 bool InsertNextDNode(DNode* p, DNode* s)
{if (p NULL || s NULL) return false;s-next p-next;if (p-next ! NULL)p-next-prior s;s-prior p;p-next s;return true;
}
用后插操作实现结点的插入有什么好处 按位序插入前插操作 找到前一个结点进行后插操作
双链表的删除
####删除p的后继结点q 特殊处理q是最后一个结点 bool DeleteNextDNode(DNode* p)
{if (p NULL) return false;DNode* q p-next;if (q NULL) return false;p-next q-next;if (q-next ! NULL)q-next-prior p;free(q);return true;
}销毁双链表
void DestoryList(DLinkList L)
{while (L-next ! NULL)DeleteNextDNode(L);free(L);L NULL;
}将指针L置为NULL的意义是将其指向空地址表示该指针不再指向任何有效的内存空间。这样做的目的是为了防止出现野指针的问题即指针指向已被释放的内存空间避免在后续代码中误用该指针导致程序崩溃或产生不可预料的结果。
双链表的遍历
后向遍历
while (p ! NULL)p p-next;前向遍历
while (p ! NULL)p p-prior;前向遍历 (跳过头结点)
while (p-prior ! NULL)p p-prior;时间复杂度 双链表不可随机存取按位查找、按值查找操作都只能用遍历的方式实现。时间复杂度 O(n)
知识点回顾与重要考点
