自考数据结构：[7]线性表之 单链表

1、链表（Linked List）的概念：

       采用链接方式存储的线性表称为链表。

      1、ps:链表怎样存储节点？

      链表是用任一一组的存储单元哪里存放线性表的节点，在存储每个节点值（数据域）得同时，还存储了指示后继结点的地址信息（连接域），通过每个节点的链接域将线性表的n个结点按其逻辑顺序链接在一起。如图：

2、单链表的概念：

     链表的每个节点只有一个链域称为单链表。

     1、ps：给个结点的存储地址是放在其前驱结点next域中的，开始结点无前驱，所以设头指针head指向开始节点。终端结点无后继，所以终端节点的指针域为空。如图：

   2、单链表由头指针唯一确定，一般，单链表可以用头指针来命名。

3、单链表c语言描述如图：

4、指针变量与结点变量的区分：

    指针变量： 如单链表c语言描述定义中，变量p的类型为ListNode *的指针变量，若p的值非空（p！=NULL），则它的值类型为ListNode的某一结点的地址。

    结点变量：通常所指的结点变量并非在变量说明部分明显地定义，而是在程序执行过程中，当需要时才产生，故称动态变量。

5、建立单链表的方法之头插法：

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

      // return 单链表的头指针

      LinkList CreateListF(void){

          char ch;

          LinkList head;//头指针

          ListNode *  s ;//指针变量 s   

          head=NULL;  //初始链表开始为空

          ch=getchar();//读取字符

          while(ch!='\n'){//这里以\n 为结束符号。

            s=(ListNode *)malloc(sizeof(ListNode));//生成指针s。

            s->data=ch;//将读入的数据存放到新节点的数据域中。

            s->next=head;//将新节点的指针域指向链表的开始节点。

            head=s;//将新节点s 赋值给 开始节点。

            ch=getchar();//继续读取下一个字符

          }   

             return head;//返回头指针

     }    

      如图顺序：    

6、建立单链表的方法之尾插法

        新节点插入到当前链表的尾上，必须增加一个尾指针r，使其指向该链表的尾节点。

      // return 单链表的头指针

      LinkList CreateListR(void){

          char ch;

          LinkList head;//头指针

          ListNode *  s ,*r;//指针变量 s   ,以及未指针r

          head=NULL;r=NULL  //初始链表开始为空,未指针r

          ch=getchar();//读取字符

          while(ch!='\n'){//这里以\n 为结束符号。

            s=(ListNode *)malloc(sizeof(ListNode));//生成指针s。

            s->data=ch;//将读入的数据存放到新节点的数据域中。

           if(head==NULL)

           head=s;

           else

            r->next=head;//将新节点的指针域指向链表的未节点。

            r=s;//将新节点s 赋值给 尾节点。

            ch=getchar();//继续读取下一个字符

           }  

            if（r->next!=NULL）

                r->next==NULL; 

             return head;//返回头指针

     }   

7、在链表的开始结点之前附加一个结点，称为头结点。

     头结点优点：

      1、链表中第一个位置的操作和其它位置一样，无需做特殊说明

      2、空表与非空表统一。