双向带头循环链表
1.顺序表和链表
（1）顺序表
-
优点：
a、支持随机访问，很多算法都需要随机访问（快排、二分）
b、cpu高速缓存命中率更高（cpu读数据时，先去找缓存，如果没有就去内存把数据加载到缓存。在加载时它不是只加载一个数据，而是附近一片数据，所以如果是数组，它的数据是连续的，都会被加载到缓存了）
-
缺点：
a、除了最后位置，其他位置插入删除效率低b、空间增容需要时间和可能会浪费空间
（2）双向带头循环链表
-
优点：
a、任意位置插入删除效率O(1)b、按需申请释放空间，不浪费时间和空间
c、cpu高速缓存命中率更低（还会污染缓存，让缓存有很多无用的数据）
-
缺点：
a、不支持随机访问，一些算法无法使用（快排、二分）b、链表存数据还得存储指针
2.模拟实现
#define _CRT_SECURE_NO_WARNINGS 1
#include"list.h"
struct node* buy_node(type x)
{
struct node* newnode = (struct node*)malloc(sizeof(struct node));
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
struct node* list_init()
{
struct node* newnode = buy_node(-1);
newnode->next = newnode;
newnode->prev = newnode;
return newnode;
}
//不需要二级指针，因为有哨兵，只是改变上一个结点的值
void list_push_back(struct node* head, type x)
{
/*assert(head);
struct node* newnode = buy_node(x);
struct node* tail = head->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = head;
head->prev = newnode;*/
//也可以复用
list_insert(head, x);//在Head的前面插入一个节点就是尾插
}
void list_pop_back(struct node* head)
{
//assert(head);
//assert(head->next != head);//这才是最少有一个节点，而不是assert(head->next)
//struct node* tail = head->prev;
//struct node* newtail = tail->prev;
//free(tail);
//newtail->next = head;
//head->prev = newtail;
//复用
list_erase(head->prev);
}
void list_push_front(struct node* head, type x)
{
/*assert(head);
struct node* newnode = buy_node(x);
struct node* next = head->next;
newnode->prev = head;
head->next = newnode;
newnode->next = next;
next->prev = newnode;*/
//复用
list_insert(head->next, x);
}
void list_pop_front(struct node* head)
{
/*assert(head);
struct node* next = head->next->next;
free(head->next);
head->next = next;
next->prev = head;*/
//复用
list_erase(head->next);
}
void list_print(struct node* head)
{
struct node* t = head->next;
while (t != head)
{
printf("%d ", t->data);
t = t->next;
}
printf("n");
}
struct node* list_find(struct node* head, type x)
{
assert(head);
struct node* t = head->next;
while (t != head)
{
if (t->data == x)
{
return t;
}
t = t->next;
}
return NULL;
}
//插入pos之前的那个结点
void list_insert(struct node* pos, type x)
{
assert(pos);
struct node* newnode = buy_node(x);
struct node* prev = pos->prev;
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
void list_erase(struct node* pos)
{
assert(pos);
struct node* prev = pos->prev;
struct node* next = pos->next;
free(pos);
prev->next = next;
next->prev = prev;
}
void list_destroy(struct node* head)
{
assert(head);
struct node* t = head;
while (t != head)
{
struct node* next = t->next;
free(t);
t = next;
}
free(head);
head = NULL;//没有用其实
//上面这么写无法改变head的值，不能让它变成NULL，用二级指针才可以；但是要保持接口一致性,用一级指针就需要自己写head = NULL
}
/*void list_destroy(struct node** phead)
{
assert(*phead);
struct node* t = *phead;
while (t != *phead)
{
struct node* next = t->next;
free(t);
t = next;
}
free(*phead);
*phead = NULL;
}*/
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
相关推荐: 使用phpdoc/phpDocumentor来生成api文档
phpDocumentor是一个非常强大的文档自动生成工具，利用它可以帮助我们编写规范的注释，生成易于理解，结构清晰的文档， 对我们的代码升级，维护,移交等都有非常大的帮助。 1、网上通常介绍的内容太多，不容易被新手看懂。个人觉得，教程应该本着简单易懂，在能解…
