网站开发具体问题,中铁建设集团公司门户,乌克兰网站设计,如何免费注册一个网站目录
数据结构之双向链表#xff1a;#xff1a; List.h List.c 1.创建返回链表的头结点 2.双向链表初始化 3.双向链表打印 4.双向链表销毁 5.双向链表尾插 6.双向链表尾删 7.双向链表头插 8.双向链表头删 9.双向链表查找 10.双向链表在pos前插入 11.双向链表删除pos位置 12…目录
数据结构之双向链表 List.h List.c 1.创建返回链表的头结点 2.双向链表初始化 3.双向链表打印 4.双向链表销毁 5.双向链表尾插 6.双向链表尾删 7.双向链表头插 8.双向链表头删 9.双向链表查找 10.双向链表在pos前插入 11.双向链表删除pos位置 12.双向链表判空 13.双向链表长度 14.顺序表与链表的区别 数据结构之双向链表
List.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h
typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;
LTNode* ListInit();
void ListPrint(LTNode* phead);
void ListPushBack(LTNode* phead, LTDataType x);
void ListPushFront(LTNode* phead, LTDataType x);
void ListPopBack(LTNode* phead);
void ListPopFront(LTNode* phead);
bool ListEmpty(LTNode* phead);
size_t ListSize(LTNode* phead);
LTNode* ListFind(LTNode* phead, LTDataType x);
//在pos之前插入
void ListInsert(LTNode* pos, LTDataType x);
//删除pos位置
void ListErase(LTNode* pos);
void ListDestory(LTNode* phead);
List.c
1.创建返回链表的头结点
LTNode* BuyListNode(LTDataType x)
{LTNode* node (LTNode*)malloc(sizeof(LTNode));if (node NULL){perror(malloc fail);exit(-1);}node-next NULL;node-prev NULL;
}
2.双向链表初始化
LTNode* ListInit()
{LTNode* guard (LTNode*)malloc(sizeof(LTNode));if (guard NULL){perror(malloc fail);exit(-1);}guard-next guard;guard-prev guard;return guard;
}
3.双向链表打印
void ListPrint(LTNode* phead)
{assert(phead);printf(guard);LTNode* cur phead-next;while (cur ! phead){printf(%d, cur-data);cur cur-next;}printf(\n);
}
4.双向链表销毁
//可以传二级 内部置空头结点
//建议:也可以考虑使用一级指针 让调用ListDestory的人将其置空 保持接口的一致性
void ListDestory(LTNode* phead)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){LTNode* next cur-next;free(cur);cur next;}free(phead);//phead NULL;
}5.双向链表尾插
void ListPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode BuyListNode(x);LTNode* tail phead-prev;tail-next newnode;newnode-prev tail;newnode-next phead;phead-prev newnode;
}
6.双向链表尾删
void ListPopBack(LTNode* phead)
{assert(phead);//链表为空返回true 取反为假就报错assert(!ListEmpty(phead));//删掉最后一个结点 哨兵位变成自己指向自己 代码依然成立LTNode* tail phead-prev;LTNode* prev tail-prev;prev-next phead;phead-prev prev;free(tail);tail NULL;
}
7.双向链表头插
void ListPushFront(LTNode* phead, LTDataType x)
{assert(phead);//先链接newnode和phead-next结点之间的关系/*LTNode* newnode BuyListNode(x);newnode-next phead-next;phead-next-prev newnode;phead-next newnode;newnode-prev phead;*///不关心先后顺序LTNode* newnode BuyListNode(x);LTNode* first phead-next;phead-next newnode;newnode-prev phead;newnode-next first;first-prev newnode;
}
8.双向链表头删
void ListPopFront(LTNode* phead)
{assert(phead);//链表为空返回true 取反为假就报错assert(!ListEmpty(phead));//删到剩最后一个结点时 first指向最后一个结点 second指向哨兵位结点 删到最后哨兵位自己指向自己 代码依然成立LTNode* first phead-next;LTNode* second first-next;phead-next second;second-prev phead;free(first);first NULL;
}
9.双向链表查找
//双向链表的查找可以替代其修改函数
LTNode* ListFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){if (cur-data x){return cur;}cur cur-next;}return NULL;
}
10.双向链表在pos前插入
//在pos之前插入
void ListInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* prev pos-prev;LTNode* newnode BuyListNode(x);//prev newnode posprev-next newnode;newnode-prev prev;newnode-next pos;pos-prev newnode;
}
//ListInsert(phead,x)代替尾插
//ListInsert(phead-next,x)代替头插
11.双向链表删除pos位置
//删除pos位置
void ListErase(LTNode* pos)
{assert(pos);LTNode* prev pos-prev;LTNode* next pos-next;prev-next next;next-prev prev;free(pos);//pos NULL;置空并不起作用
}
//ListErase(phead-prev)代替尾删
//ListErase(phead-next)代替头删
12.双向链表判空
bool ListEmpty(LTNode* phead)
{assert(phead);return phead-next phead;
}
13.双向链表长度
size_t ListSize(LTNode* phead)
{assert(phead);size_t n 0;LTNode* cur phead-next;while (cur ! phead){n;cur cur-next;}return n;
}
14.顺序表与链表的区别
不同点顺序表链表存储空间上物理上一定连续逻辑上连续但是物理上不一定连续随机访问支持O(1)不支持O(N)任意位置插入或者删除元素可能需要搬移元素效率低O(N)只需修改指针指向插入动态顺序表空间不够时需要扩容没有容量的概念应用场景元素高效存储频繁访问任意位置插入和删除频繁缓存利用率高低
备注缓存利用率参考存储体系结构以及局部原理性
顺序表的优点 1.尾插尾删的效率很高 2.可以用下标随机访问 3.相比链表结构 CPU高速缓存命中率更高顺序表的缺点 1.头部和中部插入效率低——O(N) 2.扩容时的性能消耗扩容时的空间浪费链表的优点 1.任意位置插入删除效率很高——O(1) 2.按需申请释放链表的缺点 1.不支持随机访问 注三级缓存被称为CPU周围的禁卫军CPU执行指令不会直接访问内存 1.先看数据在不在三级缓存在(命中)直接访问 2.不在(不命中)先加载到缓存再访问 注加载到缓存时会将需要加载的位置开始的一段都加载进缓存,(加载多少取决于硬件) 由于顺序表的数据彼此之间的地址紧密联系 所以加载到高速缓存时命中率高 但链表不然 更可能会导致缓存污染
