上海公司核名工商官网,seo专业技术培训,广州 网站建设模板,建网站企划书文章目录 1. 双向带头循环链表的结构2. 相关操作2.1 创建节点2.2 尾插2.3 头插2.4 打印2.5 尾删2.6 头删2.7 查找2.8 指定位置前/后插入2.9 删除指定位置的节点2.10 删除指定位置后的节点2.11 销毁链表 3.顺序表与链表区别 1. 双向带头循环链表的结构 与单链表不同的是#xf… 文章目录 1. 双向带头循环链表的结构2. 相关操作2.1 创建节点2.2 尾插2.3 头插2.4 打印2.5 尾删2.6 头删2.7 查找2.8 指定位置前/后插入2.9 删除指定位置的节点2.10 删除指定位置后的节点2.11 销毁链表 3.顺序表与链表区别 1. 双向带头循环链表的结构 与单链表不同的是
双向链表有一个“哨兵位”作为单独的头节点每个节点都可以指向其前驱和后继节点链表是循环的
带头链表里的头节点实际为“哨兵位”哨兵位节点不存储任何有效元素只是站在这里“放哨的” “哨兵位”存在的意义遍历循环链表避免死循环。
typedef int ListDataType;
typedef struct List
{ListDataType data;struct List* prev;//指向前驱节点struct List* next;//指向后继节点
}List;2. 相关操作
2.1 创建节点 创建的每个节点应该自己成环
List* BuyNode(ListDataType x)
{List* newnode (List*)malloc(sizeof(List));if (newnode NULL){perror(malloc);return NULL;}newnode-data x;newnode-next newnode;newnode-prev newnode;
}创建哨兵位
int main()
{//哨兵位List* head BuyNode(-1);return 0;
}2.2 尾插 void ListPushBack(List* phead, ListDataType x)
{assert(phead);List* newnode BuyNode(x);newnode-next phead;newnode-prev phead-prev;//尾节点指向新节点phead-prev-next newnode;phead-prev newnode;
}2.3 头插 void ListPushFront(List* phead, ListDataType x)
{assert(phead);List* newnode BuyNode(x);newnode-next phead-next;newnode-prev phead;phead-next newnode;//只有头节点时就是头节点的prevphead-next-prev newnode;
}2.4 打印
由于是循环链表所以循环停止的条件应该是cur ! head
void ListPrint(List* phead)
{assert(phead);List* cur phead-next;while (cur ! phead){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}2.5 尾删
不能没有节点尾节点的前驱节点指向头节点头节点指向尾节点的前驱节点释放尾节点
void ListPopBack(List* phead)
{assert(phead);//只有头节点assert(phead-next ! phead);List* del phead-prev;del-prev-next phead;phead-prev del-prev;free(del);
}2.6 头删
不能没有节点待删除节点的后继节点的prev指向头节点头节点指向待删除节点的后继节点
void ListPopFront(List* phead)
{assert(phead);assert(phead-next ! phead);List* del phead-next;del-next-prev phead;phead-next del-next;free(del);
}2.7 查找
List* ListFind(List* phead, ListDataType x)
{assert(phead);assert(phead-next ! phead);List* cur phead-next;while (cur ! phead){if (cur-data x){return cur;}cur cur-next;}return NULL;
}2.8 指定位置前/后插入
将新节点与指定位置相连即可
指定位置前
void ListPosFrontInsert(List* pos, ListDataType x)
{assert(pos);List* newnode BuyNode(x);List* prev pos-prev;newnode-prev prev;newnode-next pos;prev-next newnode;pos-prev newnode;
}指定位置后
void ListPosBackInsert(List* pos, ListDataType x)
{assert(pos);List* newnode BuyNode(x);List* next pos-next;newnode-next next;newnode-prev pos;next-prev newnode;pos-next newnode;
}2.9 删除指定位置的节点
将指定位置的前驱节点、后继节点连接即可
void ListPosDel(List* pos)
{assert(pos);List* prev pos-prev;List* next pos-next;prev-next next;next-prev prev;free(pos);pos NULL;
}2.10 删除指定位置后的节点
若指定位置是尾节点则应该执行头删
void ListPosAfterDel(List* phead, List* pos)
{assert(phead);assert(pos);if (pos-next phead){ListPopFront(phead);}else{List* del pos-next;del-next-prev pos;pos-next del-next;free(del);}
}2.11 销毁链表
此接口的参数是一级指针所以并不能将哨兵位销毁因此需要再调用处再将哨兵位置为空
void ListDestroy(List* phead)
{assert(phead);assert(phead-next ! phead);List* cur phead-next;while (cur ! phead){List* next cur-next;free(cur);cur next;}cur NULL;free(phead);phead NULL;
}3.顺序表与链表区别
不同点顺序表链表存储空间上物理上一定连续逻辑上连续物理上不一定连续随机访问O(1)O(N)任意位置插入或删除可能需要搬运元素效率低O(N)只需修改指针指向插入动态顺序表空间不够需要扩容没有容量的概念应用场景元素高效存储频繁访问任意位置频繁插入/删除缓存利用率高低
