[数据结构与算法]数据结构——线性表的链式存储

? 通常采用链式存储结构的线性表称为线性链表。从链式方式的角度看，链表可以分为单链表，循环链表和双链表。

1.单链表

? 链表是用一组任意存储单元来存放线性表的结点，这组存储单元可以是连续的，也可以是非连续的，甚至是零散分布在内存的任何位置上。因此，链表中结点的逻辑顺序和物理顺序不一定相同。

? 结点包括两个域：数据域用来存储结点的值，指针域用来存储数据元素的直接后继的地址。线性链表正是通过每个结点的指针域将线性表的n个结点按其逻辑顺序连接在一起。又因为线性链表的每个结点只有一个next指针域，所以这种链表称为单链表。

? 单链表中每个结点的存储地址存放在其前驱结点的指针域中，由于线性表的第一个结点无直接前驱，所以应设置一个头指针指向第一个结点。由于线性表的最后一个结点没有直接后继，则指定单链表的最后一个结点的指针域为null.

? 一般情况下，使用链表，只关心链表中结点的逻辑顺序，并不关心每个结点的实际存储位置。

单链表的存储结构描述：

typedef struct Node{   //结构体类型定义
   ElemType data;
   struct Node * next;
} Node,* LinkList      //* LinkList为结构体指针类型

?LinkList与Node *同为结构指针类型，这两种类型是等价的。通常习惯上用LinkList说明指针变量，强调它是某个单链表的头指针变量。LinkList L ，此时L为单链表的头结点，提高了程序的可读性。用Node *来定义指向单链表中结点的指针，像Node * p,则p为指向单链表中的指针变量。注意一个为头指针变量，一个为单链表中的结点。

L是单链表的头指针，它指向表中第一个结点（对于带头结点的单链表，则指向单链表的头结点），若L == NULL（对于带头结点的单链表为L->next == NULL）表达式为真，则表示单链表为一个空表，长度为0.若是非空表，则可以通过头指针L访问表中结点，从而找到要访问的所有结点的数据信息。例如，对于带头结点的单链表L，令p=L->next，则p指向表中的第一个元素结点，通过p->data就可以访问到表中第一个元素的数据值了。

2.单链表上的基本运算

?2.1初始化单链表

//初始化单链表
InitList(LinkList * L){
   * L = (LinkList)malloc(sizeof(Node));   //建立头结点
   (* L)->next = NULL;   //建立空的单链表L
}

注意：

L是指向单链表的头结点的指针，用来接收主程序中待初始化单链表的头指针变量的地址

* L相当于主程序中待初始化单链表的头指针变量

2.2建立单链表

头插法

思想：

从一个空表开始，每次读入数据，生成新的结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头结点之后，直到读入结束标志为止。

void CreateFromHead(LinkList L){
   //L是带头结点的空链表头指针
   Node * s;
   char c;
   int flag = 1;
   while(flag){
      c = getchar();
      if(c != '$'){
         s = (Node *)malloc(sizeof(Node));
         s->data = c;
         s->next = L->next;
         L->next = s;
      } else {
         flag = 0;
      }
   }
}

尾插法

思想：

头插法生成的链表中结点的次序和输入的顺序相反。尾插法是将新结点插入到前单链表的表尾上。为此需要增加一个尾指针r，使其指向当前单链表的表尾

void CreatFromTail(LinkList L){
   //L是带头结点的空链表头指针
   Node * r,* s;
   int flag = 1;
   r = L;   //r指针动态指向链表的当前表尾，目前指向L
   while(flag){
      c = getchar();
      if(c != '$'){
          s = (Node *)malloc(sizeof(Node));
          s->data = c;
          r->next = s;
          r = s;
       } else {
           flag = 0；
           r->next = NULL;//flag为0时结束循环，说明这是最后一个结点
       }
   }
}

2.3查找

按序号查找

Node * Get(LinkList L,int i){
   //在带头结点的单链表L中查找第i个结点
   int j;
   Node * p;
   if(i < 0) 
      return NULL;//判断i的取值是否合理
   p = L;  //p位于L上
   j = 0;
   while((p->next != NULL) && (j < i)){
      p = p->next;
      j++;
   }
   if(i == j){
      return p;
   } else {
      return NULL;
   }
}

按值查找

Node * Locate(LinkList L,ElemType key){
   //在带头结点的单链表L中查找结点等于key的第一个结点
   Node * p;
   p = L->next;   //p指向第一个结点
   while(p != null){     //判断当前结点是否为空，不为空继续进行循环
      if(p->data != key){    //判断数据域是否等于key
          p = p->next;    //不等于继续查找下一个结点
      } else {
          break;   //找到结点key退出循环
      }
   }
   return p;    //找到返回结点p
}

2.4求单链表长度的操作

int ListLength(LinkList L){
   Node * p;   //定义指针p
   p = L->next;   //p指向第一个结点
   int j = 0;     //j赋初始值
   while(p != NULL){   //判断p是否为空，不为空则继续循环
      p = p->next;    //查找下一个结点
      j++;            
   }
   return j;
}

2.5单链表的插入

void InsertList(LinkList L,int i,ElemType e){
    //在带头结点的单链表L中第i个位置插入元素e
    Node * pre,*s;
    int k;
    if(i < 0) return NULL;
    pre = L;
    k = 0;
    while(pre != NULL && k < i - 1){   //此时找到的为第i - 1个元素
       pre = pre->next;
       k = k + 1; 
   }
   if(pre == NULL){    //如果当前位置pre为空表示已经查完，但还未查找到第i个，说明插入位置不合适
      printf("插入位置不合理");
      return error;
   }
   s = (Node *)malloc(sizeof(Node));
   s->data = e;
   s->next = pre->next;   //新结点指向第i个元素
   pre->next = s;    //i - 1个元素指向新结点
   return OK;
}

2.6单链表的删除

int DelList(LinkList L,int i,ElemType e){
   Node *pre,*r;
   int k;
   pre = L;
   k = 0;
   //寻找被删除结点的前驱结点i - 1,使p指向它
   while(p->next != NULL && k < i - 1){
      pre = p-> next;
      k = k + 1;
   }
   //查找第i - 1个结点
   //pre->next为空，没有找到合法的前驱位置，说明删除位置i不合法
   if(pre->next == NULL){
      printf("删除结点的位置不合理");
      return ERROR;
   }
   r = pre->next;   //将r放到第i个位置上
   pre->next = r->next;    //i-1指向i + 1
   *e = r->data;   //删除的数据保存到e上
   free(r);    //释放r
   return OK;
}

3.循环链表

循环链表（Circular Linked List）是一个首尾相连的链表，将单链表最后一个结点的指针域由NULL改为指向表头结点，得到了单链的循环链表。

单链表中判别条件为p != NULL或p->next != NULL,而单循环链表的判别条件使p != L或p->next != L

?3.1初始化循环单链表

InitCLinkList(LinkList *CL){
   //CL用来接收待初始化的循环单链表的头指针变量的地址
   *CL = (LinkList)malloc(sizeof(Node));
   (*CL)->next = *CL;
}

3.2建立循环单链表

void CreatCLinkList(LinkList CL){
   Node *rear,*s;
   char c;
   rear = CL;   //rear指针动态指向链表的当前表尾，其初值指向头结点
   c = getchar();
   while(c != '$'){
      s = (Node *)malloc(sizeof(Node));    //创建新的结点
      s->data = c;     //c赋值到s的数据域
      rear->next = s;   //rear指向新结点
      rear = s;   //rear后移
      c = getchar();
   }
      rear->next = CL;   //最后一个结点的next链域指向头结点
}

4.双向链表

如果希望从表中快速确定某一个结点的前驱，一个解决办法就是在这个单链表的每个结点里再增加一个指向前驱的指针域。这样形成的链表就有两条方向不同的链，称为双向循环链表（Double Linked List）。

双链表的结构定义

typedef struct DNode{
   ElemType data;
   struct DNode *prior,*next;
}DNode,* DoubleList;

4.1双向链表的前插操作

int DlinkIns(DoubleList L,int i,ElemType e){
   DNode *s,*p;
   //省略一些过滤条件
   
   s = (DNode *)malloc(sizeof(Node));
   if(s){
      s->data = e;
      s->prior = p->prior;
      p->prior->next = s;
      s->next = p;
      p->prior = s;
      return TRUE;
   } else {
      return FALSE;
   }
}

4.2双向链表的删除操作

int DlinkDel(DoubleList L,int i,ElemType *e){
   DNode *p;   
   //省略过滤
   
   *e = p->data;
   p->prior->next = p->next;
   p->next->prior= p->prior;
   free(p);
   return TRUE;
}