一、链表
线性表的优点是可以方便的随机读取线性表中的任一元素，且读取任一元素所用的时间相同。但是当随机插入或删除一个元素时，常常需要移动大量的元素。
（1）单链表：链式的存储结构，链表中的结构节点包含两部分，数据域DATA和指针NEXT指向后继节点。head是单链表的头指针，指向开始节点。链表的特点是只要知道了头指针，所有的数据都可以找到哦。
（2）单链表的一些运算：
遍历（traversal）:
void length(head) //得到链表的长度，这个时候就需要遍历。
{
node *p=NUll;
p = head；
while(p != NULL)
{
P = P->next;
n++;
}
free(p);
return (n);
}
插入（insert）
void insert(head,i,X)
{
node *p = NULL;
node *s = (node *) macllos( sizeof(node));
int j=1;
s->data = X;
if(i == 0)
{
s->next = NULL;
head= s;
}
else
{
p = head;
while( p!=NULL && j < i)
{
j++;
p=p->next;
}
if(p != NULL)
{
s-next = p->next;
p->next = s;
}
else{printf("not find");}
}
删除（delete）
void delete(head,X)
{
node *p = head;
node *q = p;
if( p->data == X)
{
head = p->next;
free(q);
free(p);
}
else
{
p= p->next;
while(p != NULL && p->data != X)
{
q = p;
p = p->next;
}
if(p == NULL){ printf("error");free(q);free(p);}
else
{
q->next = p->next;
free(q);
free(p);
}
}
}
(3)循环链表：
单链表只能进行从表头到表尾的访问，而且，当插入或删除的是表头节点时，头指针需要改变。循环链表就是对单链表的一个改进，循环链表首尾相接，将表尾节点由原来的空指针，改变为表头节点。通常在表头节点的前面再加一个空节点，用于防止遍历时循环不止。空节点的数据域通常赋予特别的数据，以与一般的节点相区别。
对循环节点的另一种改进是，只有一个尾指针rear，指向尾节点，则头节点的位置是rear->next->next。（循环链表，没怎么见过有人用这种结构哦，呵呵）
（4）双链表：头指针prior+数据域data+尾指针next（也有双向循环链表哦，记得得有个空表头节点。）
指针P = (p->prior)->next = (p->next)->prior;
插入的主要步骤如下：
设要在P所指向的节点前面，插入一个节点*q。
q->prior = p->prior;
q->next = p;
p->prior ->next = q;
p->prior = q;（这几个步骤是有一定的顺序的，这句应该是最后执行的。）
删除的主要步骤如下：
设P指向要被删除的节点。
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);(这个貌似很简单唉)
（5）链表的应用：
链堆栈：
入栈的操作
void push(TOP,X)
{
node *s;
s = (node*) malloc(sizeof(node));
s->data = X;
s->next = TOP;
TOP =S;
}
出栈的操作
void pop(TOP,X)
{
node *p=NULL; //为什么多用了个节点P呢？我一开始就没想到唉
if(TOP == NULL)
{
printf("empty linklist");
free(p);
}
else
{
X = TOP->data;
p=TOP;
TOP = TOP->next;
free(p);
}
}
链队列：队首指针front 队尾指针rear
插入：
void insert(front,rear,X)
{
node *s = (node*) malloc(sizeof(node));
s->data = X;
s->next = NULL;
if(rear == NULL)
{
front = rear = s;
}
else
{
rear->next = s;
rear = s;
}
}
删除：
void delete(front,rear，X)
{
node *p=NULL; //知道这个用来干吗的了吧？
if(front == NULL){printf("empty queue");free(p);}
else
{
X = front->data;
p=front;
if(front == rear){front = rear = NULL;}
else{front = front->next;}
free(p);
}
}
哎呀呀，发现删除的时候，都要记得free(p)啊，书上就忘记了。
一元多项式的算术运算：
用何种数据结构来表示一元多项式呢？数组？有点浪费空间。单链表，还不错。数据域 分为 系数+幂。按这种数据结构可以实现两个多项式的加减哦。你能想到吗？想不到的话，就去看书吧。
（6）表示稀疏矩阵的十字链表：
矩阵一般可用M*N维数组来表示，但如果零值很多的情况下，则有点浪费了，这里我们用十字链表（orthogonal linkedlist）。
在十字链表中，矩阵的每个非零元素对应着一个含有5个域的节点。行号+列号+元素的数值+指向同一列的下一个非零元素节点的指针+指向同一行的右边一个非零元素节点的指针。（挺好理解的，难怪叫十字，谁想出来的，貌似有个问题，从一个节点可以找出所有的非零节点来吗？）
别人给出了解决方法，将每行的非零元素节点连接成循环列表，将每列的非零元素点连接成循环列表，空表头指针的行号列号都是0，并且元素的值的位置存的是一个指针。（恩这样的话，肯定可以找出所有的非零元素了）
用这种稀疏矩阵可以实现简单的加减，还可以实现更复杂的矩阵运算（转置，乘法，求逆等）
