线性表（链式结构）

  

(1) 单链表!

1. 定义：下面有一个空链表，表头叫head，并且表内没有任何元素。

struct node

{

int value;

node *next;

} arr[MAX]; int top=-1; node *head = NULL;

2. 内存分配：在竞赛中不要用new，也不要用malloc、calloc——像下面一样做吧。

#define NEW(p)	p=&arr[++top];p->value=0;p->next=NULL
node *p; NEW(head);	// 初始化表头
NEW(p);	// 新建结点

3. 插入：把q插入到p的后面。时间复杂度O(1)。

if (p!=NULL && q!=NULL)   { q->next=p->next;  p->next=q; }

// 先判定是否为空指针。如果不是，继续。

4. 删除：把p的下一元素删除。时间复杂度O(1)。

if (p!=NULL && p->next!=NULL)	// 先判定是否为空指针。如果不是，继续。
{ node *q=p->next;  p->next=q->next; // delete(q);       }	// 如果使用动态内存分配，最好将它的空间释放。

5. 查找或遍历：时间复杂度O(n)。

node *p=first; while (p!=NULL)

{

// 处理value

// cout<<p->value<<'\t';  p=p->next;

}

(2) 静态链表

指针的作用就是存储地址。如果我们找到了替代品，就可以放弃指针了。

需要把上面的定义改一下：

struct node {  int value;  int next;   } arr[MAX];

// 表示下一元素在arr中的下标

(3) 循环链表

和单链表有一个重大区别：单链表最后一个元素的next指向NULL，而循环链表最后一个元素的next

指向first。

遍历时要留心，不要让程序陷入死循环。

一个小技巧：如果维护一个表尾指针last，那么就可以在O(1)的时间内查找最后一个元素。同时可以防止遍历时陷入死循环。

(4) 双链表

1. 定义：下面有一个空链表，表头叫first。

struct node {  int value;  node *next, *prev; } arr[MAX]; int top=-1; node *first = NULL; // 根据实际需要可以维护一个表尾指针last。

2. 内存分配：最好不要使用new运算符或malloc、calloc函数。

#define NEW(p)	p=arr+(++top);p->value=0;p->next=NULL;p->prev=NULL
node *p; NEW(head);	// 初始化表头
NEW(p);	// 新建结点

3. 插入：把q插入到p的后面。时间复杂度O(1)。

if (p==NULL||q==NULL)    {  q->prev=p;  q->next=p->next;  q->next->prev=q;  p->next=q; }

// 先判定是否为空指针。如果不是，继续。

4. 删除：把p的下一元素删除。时间复杂度O(1)。

if (p==NULL||p->next==NULL) {				// 先判定是否为空指针。如果不是，继续。
node *q=p->next;  p->next=q->next;  q->next->prev=p; // delete(q);    }				// 如果使用动态内存分配，最好将它的空间释放。

5. 查找或遍历：从两个方向开始都是可以的。

(5) 将元素插入到有序链表中*

void insert(const node *head, node *p) {  node *x, *y;  y=head;  do  {   x=y;   y=x->next; } while ((y!=NULL) && (y->value < p->value);  x->next=p;  p->next=y; }