鏈式存儲 :用一組任意的存儲單元存儲線性表中的數據元素。用這種方法存儲的線性表簡稱線性鏈表。
存儲鏈表中結點的一組任意的存儲單元可以是連續的,也可以是不連續的,甚至是零散分布在內存中的任意位置上的。 鏈表中結點的邏輯順序和物理順序不一定相同。(即不要求邏輯上相鄰的元素在物理位置上也相鄰)
為了正確表示結點間的邏輯關系,在存儲每個結點值的同時,還必須存儲指示其直接後繼結點的地址(或位置),稱為指針(pointer)或鏈(link),這兩部分組成了數據元素ai的存儲映像
鏈表是通過每個結點的指針域將線性表的n個結點按其邏輯次序鏈接在一起的。
每一個結點只包含一個指針域的鏈表,稱為單鏈表。
為操作方便,總是在鏈表的第一個結點之前附設一個頭結點(頭指針)head指向第一個結點(即頭結點的指針域存放第一個結點的存儲位置)。頭結點的數據域可以不存儲任何信息(或鏈表長度等信息)。
因為最後一個數據元素沒有直接後繼,所以線性鏈表中最後一個結點的指針為空(NULL)。
為操作方便,總是在鏈表的第一個結點之前附設一個頭結點(頭指針)head指向第一個結點(即頭結點的指針域存放第一個結點的存儲位置)。頭結點的數據域可以不存儲任何信息(或鏈表長度等信息)。
因為最後一個數據元素沒有直接後繼,所以線性鏈表中最後一個結點的指針為空(NULL)。
C語言中用帶指針的結構體類型來描述
typedef struct Lnode
{ ElemType data; /*數據域,保存結點的值 */
struct Lnode *next; /*指針域,類型是struct Lnode */
}LNode, *LinkList; /*結點的類型名 */
LNode,結點結構;LinkList:鏈表結構
//LinkList L;L為單鏈表名,同時也可作為表的頭指針名,指向表中第一個結點,即L的指針域存儲第一個結點的地址。
//若L為空,則表示線性表為空表,其長度為0.
結點的實現
結點是通過動態分配和釋放來的實現,即需要時分配,不需要時釋放。實現時是分別使用C語言提供的標准函數:malloc() ,realloc(),sizeof() ,free() 。
動態分配 p=(LNode*)malloc(sizeof(LNode));
函數malloc分配了一個類型為LNode的結點變量的空間,並將其首地址放入指針變量p中。
動態釋放 free(p) ;
系統回收由指針變量p所指向的內存區。p必須是最近一次調用malloc函數時的返回值。
算法描述
LNode *create_LinkList(void)
/* 頭插入法創建單鏈表,鏈表的頭結點head作為返回值 */
{ int data ;
LNode *head, *p;
head= (LNode *) malloc( sizeof(LNode));
head->next=NULL; /* 創建鏈表的表頭結點head */
while (1) //一直執行
{ scanf(“%d”, &data) ;
if (data==32767) break ;
p= (LNode *)malloc(sizeof(LNode));
p->data=data; /* 數據域賦值 */
p->next=head->next ; head->next=p ;
/* 鉤鏈,新創建的結點總是作為第一個結點 */
}
return (head);
}
// 返回值是表頭結點head,實際就是所創建的鏈表。此時主函數中只要建一個LNode *類型的變量,即可調用該函數。如
LNode *head; 或者LinkList head;
head=create_LinkList();
頭插入法建立鏈表雖然算法簡單,但生成的鏈表中結點的次序和輸入的順序相反。若希望二者次序一致,可采用尾插法建表。
該方法是將新結點插入到當前鏈表的表尾,使其成為當前鏈表的尾結點。
算法描述
LNode *create_LinkList(void)
/* 尾插入法創建單鏈表,鏈表的頭結點head作為返回值 */
{ int data ;
LNode *head, *p, *q;
head=p=(LNode *)malloc(sizeof(LNode));
p->next=NULL; /* 創建單鏈表的表頭結點head */
while (1)
{ scanf(“%d”,& data);
if (data==32767) break ;
q= (LNode *)malloc(sizeof(LNode));
q->data=data; /* 數據域賦值 */
q->next=p->next; p->next=q; p=q ;
/*鉤鏈,新創建的結點總是作為最後一個結點*/
}
return (head);
}
無論是哪種插入方法,如果要插入建立單鏈表的結點是n個,算法的時間復雜度均為O(n)。 對於單鏈表,無論是哪種操作,只要涉及到鉤鏈(或重新鉤鏈),如果沒有明確給出直接後繼,鉤鏈(或重新鉤鏈)的次序必須是“先右後左”,否則就會丟掉鏈表中的一些結點。
(1) 按序號查找 取單鏈表中的第i個元素。
對於單鏈表,不能象順序表中那樣直接按序號i訪問結點,而只能從鏈表的頭結點出發,沿鏈域next逐個結點往下搜索,直到搜索到第i個結點為止。因此,鏈表不是隨機存取結構。
設單鏈表的長度為n,要查找表中第i個結點,僅當1≦i≦n時,i的值是合法的。
算法思想如下:
從頭結點開始順鏈掃描,用指針p指向當前掃描到的結點,用j作統計已掃描結點數的計數器,當p掃描下一個結點時,j自動加1。 P的初值指向頭結點,j的初值為1。當j=i時,指針p所指的結點就是第i個結點。
算法描述
ElemType Get_Elem(LNode *L , int i)
{ int j ; LNode *p;
p=L->next; j=1; /* 使p指向第一個結點 */
while (p!=NULL && j<i)
{ p=p–>next; j++; } /* 移動指針p , j計數 */
if ( !p|| j>i) return(ERROR) ;
/* p為NULL 表示i>n; j>i表示i=0 */
else return(p->data);
}
移動指針p的頻度:
i=0時:0次; i∈[1,n]:i-1次;i>n:n次。
∴時間復雜度: O(n)。
按值查找
按值查找是在鏈表中,查找是否有結點值等於給定值key的結點? 若有,則返回首次找到的值為key的結點的存儲位置;否則返回NULL。查找時從開始結點出發,沿鏈表逐個將結點的值和給定值key作比較。
算法描述
LNode *Locate_Node(LNode *L,int key)
/* 在以L為頭結點的單鏈表中查找值為key的第一個結點 */
{ LNode *p=L->next;
while ( p!=NULL&& p->data!=key)
p=p–>next;
if (p->data==key) return p;
else
{ printf(“所要查找的結點不存在!!\n”);
retutn(NULL); }
}
算法的執行與形參key有關,平均時間復雜度為O(n)。