C语言基础 之 链表操作

链表的操作

---

对链表的主要操作有建立链表、结构的查找与输出、结点数据的删除和结点数据的插入
示例

struct slist
{
    int data;
    struct slist* next;
};
typedef struct slist SLIST;

---

动态链表的建立

动态链表的创建有两种方式

• 先进先出单链表
  在建立单链表时，将每次生成的新结点总是插入到当前链表的表尾作为尾结点。
• 后进先出单链表
  在建立单链表时，将每次生成的新结点总是插入到当前链表的表头结点之后作为当前链表的首结点。

区别：对插入结点的前一结点跟踪及对应指针域的处理。

具体创建步骤

• 第一步，创建空表,定义头结点指针域为空。
• 第二步，准备建表，定义两个指针p和 q,约定P恒指向链表末尾结点，q恒指向待插入
  结点。
• 第三步，申请新结点，作为待插入结点。
• 第四步，插入新结点，将新结点插入到链表的末尾，作为当前末尾结点。
• 第五步，只要待插入结点个数小于链表中预定结点个数，则转到第三步继续插入。

参考函数
SLIST *creact slist()
{
      int c;
      SLIST *h,*q,*p;
      h=(SLIST*) malloc (sizeof(SLIST));  //为SLIST型数据生成头结点，其首地址由h表示
      p=h;
      scanf( "%d",&c);       // 读入数据
      while(c!=-1)      //未读到结束标志就循环
      {

           q=(SLIST * )malloc( sizeof(SLIST)); /*生成一个新结点，其首地址由q表示*/
           q->data=c;       /1读入数据存入新节点的data域  
           p->next=q;     //新结点连到表尾
           p=q;              //p指向当前表尾 
           scanf( "%d" ,&c);      //读入数据
      }
      p->next="0';         //置链表结束标志 
      return h;              //返回表头指针
}
int main( )
{
    SLIST *head;
    head=creat_slist();
}

---

顺序访问单链表中各结点的数据域（查找与输出）

利用一个工作指针p，从头到尾依次指向链表中的每个结点；当指针指向某个结点时，就输出该结点数据域中的内容，直到遇到链表的结束标志为止。如果是空链表，就只输出有关信息并返回调用函数。

链表的输出过程有以下几步:

• 第一步，确定表头，并约定指针p恒指向待输出结点。

• 第二步，若待输出结点非空，则输出结点数据域的值；若为空，则退出。

• 第三步，跟踪链表地址域，找到下一个待输出结点。

• 第四步,转到第二步,继续输出。

例如:
下面的程序段是利用前面的SLIST结构类型构成的链表，输出每个结点数据城中的值。

      ...
      SLIST *p;
      p-head->next;      /* head是建立链表的头指针,这里是p指向头结点后的第一个结点*/
      while( p!=NULL)     //未到链表尾继续循环
      {
      printf("%d\n",p->data);       //输出链表中当前数据域中的值
      p-p->next;  //p指向下一个结点
      }
      ...

---

单链表的删除

为了删除单向链表中的某个结点，首先要找到待删除结点的前趋结点，然后将此前趋结点的指针域去指向待删除结点的后续结点(p->next=q->next)，最后释放被删除结点所占存储空间(free(q))即可。

例如:

  SLIST *p,*q,*r;

则将q所指结点从链表中刷除，同时要保持链表的连续，即q->next中存放的是r所指结点的首地址，如果将r所指的结点的首地址存于p->next中，就可以删除q所指的结点，并保持链表的连续（即p所指的结点与r所指的结点相连）。

 p->next=q->next;
 或p->next=r;
 或p->next= p->next->next;

注意：

• ①指针P指向待删第i个结点的前1个结点(第i-1个结点)。
• ②指针q指向待删的第i个结点(q p->next)。1↑
• ③切断第i个结点与其前后两个结点的链接(p->nextq->next)并释放第i个结点所占的内存空间(free(q))。

---

单链表的插入

在单向链表中插入结点，首先要确定插入的位置。当待插结点插在指针p所指结点之前称为前插；待插结点插在指针p所指结点之后称为后插。

当进行前插操作时，需要三个工作指针p、q、s,通常用s指向新开辟的结点；用p指向插入的位置；q指向p的前趋结点，在第i个结点进行前插操作。

注意：

• ①表示将新结点的指针指向第i个结点(s.next=p)。

• ②表示将第i-1个结点的指针指向新结点(q.next=s).

  例7-6编写函数insert_snode, 其功能是:在带头结点单链表中的值为x的结点前，
  插入值为y的结点，若值为x的结点不存在，则插在链表尾。
  
  参考函数:
  insert_snode( SLIST *head，int x，int y)
  {
      SLIST *s,*p,*q;
      s=(SLIST *)malloc(sizeof(SLIST));     //生成一个新结点
      s->data=y;                                 //新结点中，存入y值
      q=head;                                  //q指向头结点
      p=head->next;                         //p指向第一个结点
      while((p!='\0')&&(p->data!=x))   //查找x的位置
      {
       q=p;p=p->next; 
      }
      s->next=p;q->next=s;     //x存在，插在x之前；x不存在，p的值为NULL,插在表尾
  }
  

函数insert_snode中,综合运用了查找和前插的算法。在进行插入操作的过程中，可能遇到以下3种情况。

• 链表非空，值为x的结点存在，新结点应插在x结点之前。
• 链表非空，但值为x的结点不存在，按要求新结点应插在链表尾。
• 链表为空，这种情况相当x的结点不存在，新结点应插在链表尾，即捕在头结点之后，作为链表的第一个结点。

---