單鏈表

單鏈表
鏈接存儲方法
　　鏈接方式存儲的線性表簡稱為鏈表（Linked List）
　　鏈表的具體存儲表示為
　　① 用一組任意的存儲單元來存放線性表的結點（這組存儲單元既可以是連續的也可以是不連續的）
　　② 鏈表中結點的邏輯次序和物理次序不一定相同為了能正確表示結點間的邏輯關系在存儲每個結點值的同時還必須存儲指示其後繼結點的地址（或位置）信息（稱為指針（pointer）或鏈(link)）
注意
　　鏈式存儲是最常用的存儲方式之一它不僅可用來表示線性表而且可用來表示各種非線性的數據結構

鏈表的結點結構
  ┌──┬──┐
  │data│next│
  └──┴──┘
      　data域存放結點值的數據域
      　next域存放結點的直接後繼的地址（位置）的指針域（鏈域）
注意
   　 ①鏈表通過每個結點的鏈域將線性表的n個結點按其邏輯順序鏈接在一起的
    　②每個結點只有一個鏈域的鏈表稱為單鏈表（Single Linked List）
【例】線性表（batcateatfathatjatlatmat）的單鏈表示如示意圖

頭指針head和終端結點指針域的表示
    　單鏈表中每個結點的存儲地址是存放在其前趨結點next域中而開始結點無前趨故應設頭指針head指向開始結點
注意
    　鏈表由頭指針唯一確定單鏈表可以用頭指針的名字來命名
【例】頭指針名是head的鏈表可稱為表head
　　終端結點無後繼故終端結點的指針域為空即NULL

單鏈表的一般圖示法
    　由於我們常常只注重結點間的邏輯順序不關心每個結點的實際位置可以用箭頭來表示鏈域中的指針線性表（batcatfathatjatlatmat）的單鏈表就可以表示為下圖形式

單鏈表類型描述
  typedef char DataType; //假設結點的數據域類型為字符
  typedef struct node{   //結點類型定義
       DataType data;    //結點的數據域
       struct node *next;//結點的指針域
     }ListNode;
  typedef ListNode *LinkList;
  ListNode *p;
  LinkList head;
  注意
    　①LinkList和ListNode *是不同名字的同一個指針類型（命名的不同是為了概念上更明確）
    　②LinkList類型的指針變量head表示它是單鏈表的頭指針
    　③ListNode *類型的指針變量p表示它是指向某一結點的指針
指針變量和結點變量

┌────┬────────────┬─────────────┐
│　　　　│　　　　指針變量　　　　│　　　　 結點變量  　　　 │
├────┼────────────┼─────────────┤
│  定義  │在變量說明部分顯式定義  │在程序執行時通過標准    │
│        │                        │函數malloc生成            │
├────┼────────────┼─────────────┤
│  取值  │ 非空時存放某類型結點 │實際存放結點各域內容      │
│        │的地址                  │                          │
├────┼────────────┼─────────────┤
│操作方式│ 通過指針變量名訪問     │ 通過指針生成訪問和釋放 │
└────┴────────────┴─────────────┘
  
①生成結點變量的標准函數
    　p=( ListNode *)malloc(sizeof(ListNode))
//函數malloc分配一個類型為ListNode的結點變量的空間並將其首地址放入指針變量p中
②釋放結點變量空間的標准函數
    　free(p)//釋放p所指的結點變量空間
③結點分量的訪問
　    利用結點變量的名字*p訪問結點分量
 方法一(*p)data和(*p)next
 方法二p﹥data和p﹥next
④指針變量p和結點變量*p的關系
　    指針變量p的值——結點地址
    　結點變量*p的值——結點內容
    　(*p)data的值——p指針所指結點的data域的值
    　(*p)next的值——*p後繼結點的地址
　　*((*p)next)——*p後繼結點
注意
   　 ① 若指針變量p的值為空（NULL）則它不指向任何結點此時若通過*p來訪問結點就意味著訪問一個不存在的變量從而引起程序的錯誤
   　 ② 有關指針類型的意義和說明方式的詳細解釋【參考C語言的有關資料】

 

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