單鏈表的運算之建立單鏈表

單鏈表的運算
建立單鏈表
　　假設線性表中結點的數據類型是字符我們逐個輸入這些字符型的結點並以換行符\n為輸入條件結束標志符動態地建立單鏈表的常用方法有如下兩種

（） 頭插法建表
① 算法思路
　　從一個空表開始重復讀入數據生成新結點將讀入數據存放在新結點的數據域中然後將新結點插入到當前鏈表的表頭上直到讀入結束標志為止
具體方法

注意
    　該方法生成的鏈表的結點次序與輸入順序相反

② 具體算法實現
    LinkList CreatListF(void)
      {//返回單鏈表的頭指針
          char ch;
          LinkList head;//頭指針
          ListNode *s;  //工作指針
          head=NULL;    //鏈表開始為空
          ch=getchar(); //讀入第個字符
          while(ch!=\n){
              s=(ListNode *)malloc(sizeof(ListNode));//生成新結點
              s>data=ch;   //將讀入的數據放入新結點的數據域中
              s>next=head;
              head=s;
              ch=getchar();  //讀入下一字符
            }
          return head;
       }

（） 尾插法建表
① 算法思路
　　從一個空表開始重復讀入數據生成新結點將讀入數據存放在新結點的數據域中然後將新結點插入到當前鏈表的表尾上直到讀入結束標志為止
　　具體方法

注意
　　⒈采用尾插法建表生成的鏈表中結點的次序和輸入順序一致
　　⒉必須增加一個尾指針r使其始終指向當前鏈表的尾結點

② 具體算法實現
    LinkList CreatListR(void)
      {//返回單鏈表的頭指針
          char ch;
          LinkList head;//頭指針
          ListNode *s*r;  //工作指針
          head=NULL;    //鏈表開始為空
          r=NULL;//尾指針初值為空
          ch=getchar(); //讀入第個字符
          while(ch!=\n){
              s=(ListNode *)malloc(sizeof(ListNode));//生成新結點
              s>data=ch;   //將讀入的數據放入新結點的數據域中
           if (head!=NULL)
               head=s;//新結點插入空表
           else
               r>next=s;//將新結點插到*r之後
              r=s;//尾指針指向新表尾
           ch=getchar();  //讀入下一字符
         }//endwhile
        if (r!=NULL)
             r>next=NULL;//對於非空表將尾結點指針域置空head=s;
         return head;
    }
注意
⒈開始結點插入的特殊處理
　　由於開始結點的位置是存放在頭指針(指針變量)中而其余結點的位置是在其前趨結點的指針域中插入開始結點時要將頭指針指向開始結點
⒉空表和非空表的不同處理
　　若讀入的第一個字符就是結束標志符則鏈表head是空表尾指針r亦為空結點*r不存在;否則鏈表head非空最後一個尾結點*r是終端結點應將其指針域置空

（） 尾插法建帶頭結點的單鏈表
①頭結點及作用
　　頭結點是在鏈表的開始結點之前附加一個結點它具有兩個優點:
　　⒈由於開始結點的位置被存放在頭結點的指針域中所以在鏈表的第一個位置上的操作就和在表的其它位置上操作一致無須進行特殊處理;
　　⒉無論鏈表是否為空其頭指針都是指向頭結點的非空指針（空表中頭結點的指針域空）因此空表和非空表的處理也就統一了

②帶頭結點的單鏈表

注意
　　頭結點數據域的陰影表示該部分不存儲信息在有的應用中可用於存放表長等附加信息

③尾插法建帶頭結點鏈表算法
  LinkList CreatListR(void)
      {//用尾插法建立帶頭結點的單鏈表
          char ch;
          LinkList head=(ListNode *)malloc(sizeof(ListNode));//生成頭結點
          ListNode *s*r;  //工作指針
          r=head;    // 尾指針初值也指向頭結點
          while((ch=getchar())!=\n){
              s=(ListNode *)malloc(sizeof(ListNode));//生成新結點
              s>data=ch;   //將讀入的數據放入新結點的數據域中
              r>next=s;
              r=s;
            }
          r>next=NULL;//終端結點的指針域置空或空表的頭結點指針域置空
          return head;
       }
注意
　　上述算法裡動態申請新結點空間時未加錯誤處理這對申請空間極少的程序而言不會出問題但在實用程序裡尤其是對空間需求較大的程序凡是涉及動態申請空間一定要加入錯誤處理以防系統無空間可供分配

（） 算法時間復雜度
    　以上三個算法的時間復雜度均為(n)

From:http://tw.wingwit.com/Article/program/sjjg/201311/23278.html