單鏈表
鏈接方式存儲的線性表簡稱為鏈表(Linked List)
鏈表的具體存儲表示為
① 用一組任意的存儲單元來存放線性表的結點(這組存儲單元既可以是連續的
② 鏈表中結點的邏輯次序和物理次序不一定相同
結點的地址(或位置)信息(稱為指針(pointer)或鏈(link))
注意
鏈式存儲是最常用的存儲方式之一
┌──┬──┐
│data│next│
└──┴──┘
data域
next域
注意
①鏈表通過每個結點的鏈域將線性表的n個結點按其邏輯順序鏈接在一起的
②每個結點只有一個鏈域的鏈表稱為單鏈表(Single Linked List)
【例】線性表(bat
單鏈表中每個結點的存儲地址是存放在其前趨結點next域中
注意
鏈表由頭指針唯一確定
【例】頭指針名是head的鏈表可稱為表head
終端結點無後繼
由於我們常常只注重結點間的邏輯順序
jat
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的結點變量的空間
②釋放結點變量空間的標准函數
free(p);//釋放p所指的結點變量空間
③結點分量的訪問
利用結點變量的名字*p訪問結點分量
方法一
方法二
④指針變量p和結點變量*p的關系
指針變量p的值——結點地址
結點變量*p的值——結點內容
(*p)
(*p)
*((*p)
注意
① 若指針變量p的值為空(NULL)
誤
② 有關指針類型的意義和說明方式的詳細解釋
From:http://tw.wingwit.com/Article/program/sjjg/201311/23313.html