程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 數據庫知識 >> DB2數據庫 >> DB2教程 >> 數據結構-線性表鏈式存儲結構

數據結構-線性表鏈式存儲結構

編輯:DB2教程

數據結構-線性表鏈式存儲結構


鏈式存儲

鏈式存儲 :用一組任意的存儲單元存儲線性表中的數據元素。用這種方法存儲的線性表簡稱線性鏈表。

存儲鏈表中結點的一組任意的存儲單元可以是連續的,也可以是不連續的,甚至是零散分布在內存中的任意位置上的。

鏈表中結點的邏輯順序和物理順序不一定相同。(即不要求邏輯上相鄰的元素在物理位置上也相鄰)

為了正確表示結點間的邏輯關系,在存儲每個結點值的同時,還必須存儲指示其直接後繼結點的地址(或位置),稱為指針(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)。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved