数据结构---链式存储总结

单链表

单链表是含有数据信息和结点地址的一个双域链式存储形式。
一个单链表必须有一个首地址指向单链表中的第一个结点。

typedef int datatype;
 typedef struct link_node
{
   datatype info; //信息域
   struct link_node *next; //结点指针域
 }node;

单链表的操作集合

node *init() /*初始化单链表*/
//输出单链表中各个结点的值  
void display(node *head)  
//在单链表中查找第i个结点的存放地址
node *find(node *head,int i)
//单链表第i个结点后插入值为x的新结点 
node *insert(node *head,datatype x,int i)
//在单链表中删除一个值为x的结点  
node *delete(node *head,datatype x)

带头结点的单链表

在单链表中设置一个特殊的结点，由单链表的首指针指示，只要有这个单链表，该结点就永远不会被删除。

带头结点的单链表的插入与删除

node *insert(node *head,datatype x,int i)
 {
   node *p,*q;
   q=find(head,i);/*查找带头结点的单链表中的第i个结点*/
          /*i=0，表示新结点插入在头结点之后，此时q指向的是头结点*/
   if(!q)/*没有找到*/
   {
    printf("\n带头结点的单链表中不存在第%d个结点！不能插入%d！",i,x);
    return head;}
   p=(node*)malloc(sizeof(node));/*为准备插入的新结点分配空间*/
   p->info=x;/*为新结点设置值x*/
   p->next=q->next;/*插入(1)*/
   q->next=p;/*插入(2)，当i=0时，由于q指向的是头结点， 本语句等价于head>next=p */
   return head;
 }

node *delete(node *head,datatype x)
 {
   node *pre=head,*q;/*首先pre指向头结点*/
   q=head->next;/*q从带头结点的第一个实际结点开始找值为x的结点*/
   while(q&&q->info!=x)/*没有查找完并且还没有找到*/
     {pre=q;q=q->next;}/*继续查找，pre指向q的前驱*/
   pre->next=q->next;/*删除*/
   free(q);/*释放空间*/
   return head;
 }

循环单链表

循环单链表是通过设置表中最后一个结点的指针域指向表中第一个结点的链表。
从任意一个结点开始，都可以访问到表中其他结点。将最后一个结点的指针域由原来的NULL改为表中的第一个结点的地址。

循环单链表的操作集合

node *init() /*建立一个空的循环单链表*/
//获得循环单链表的最后一个结点的存储地址
node *rear(node *head)
//输出循环单链表中各个结点的值  
void display(node *head)  
//循环单链表中查找值为x的结点的存储地址
node *find(node *head,datatype x)
//循环单链表第i个结点后插入值为x的新结点 
node *insert(node *head,datatype x,int i)
//在循环单链表中删除一个值为x的结点  
node *delete(node *head,datatype x)

双链表

双链表是每个结点都有两个指针域，一个指向它的后继结点，一个指向它的前驱结点。

typedef int datatype;
 typedef struct dlink_node{
   datatype info;
   struct dlink_node *llink,*rlink;
 }dnode;

双链表的操作集合

dnode *init()//建立一个空的双链表
//输出双链表中各个结点的值   
void display(dnode *head)
//在双链表中查找第i个结点的存储地址
dnode *find(dnode *head,int i)
//双链表第i个结点后插入值为x的新结点
dnode *insert(dnode *head,datatype x,int i)
 //在双链表中删除一个值为x的结点
dnode *dele(dnode *head,datatype x)

链式栈

链式栈是插入和删除操作规定在单链表的同一段进行。

链式栈的操作集合

node *init() /*建立一个空栈*/
//判断链式栈是否为空  
int empty(node *top)
//读链式栈的栈顶结点值   
datatype read(node *top)
//输出链式栈中各个结点的值
void display(node *top)
//向链式栈插入值为x的结点（进栈）
node *push(node *top,datatype x)
//删除链式栈的栈顶结点（出栈）
node *pop(node *top)

链式栈和顺序栈差不多。

链式队列

链式队列是插入和删除操作规定在单链表的不同端进行。
链式队列的队首和队尾指针分别用front和rear表示。

链式队列的操作集合

queue *init() /*建立一个空的链式队列*/
int empty(queue qu)//判断链式队列是否为空 
void display(queue *qu) //输出链式队列中各个结点的值  
datatype read(queue qu)//取得链式队列的队首结点值 
//向链式队列中插入一个值为x的结点 
queue *insert(queue *qu,datatype x)
//删除链式队列中的队首结点
queue *dele(queue *qu)