線性表 - 鏈式存儲結構- 單鏈表的運算（三）

　　() 尾插法建帶頭結點的單鏈表

　　①頭結點及作用

　　頭結點是在鏈表的開始結點之前附加一個結點它具有兩個優點:

　　⒈由於開始結點的位置被存放在頭結點的指針域中所以在鏈表的第一個位置上的操作就和在表的其它位置上操作一致無須進行

　　特殊處理;

　　⒉無論鏈表是否為空其頭指針都是指向頭結點的非空指針(空表中頭結點的指針域空)因此空表和非空表的處理也就統一了

　　

　　②帶頭結點的單鏈表

　　注意

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

　　③尾插法建帶頭結點鏈表算法

　　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/23309.html