鏈式存儲結構

鏈式存儲結構，又叫鏈接存儲結構。在計算機中用一組任意的存儲單元存儲線性表的數據元素(這組存儲單元可以是連續的,也可以是不連續的).它不要求邏輯上相鄰的元素在物理位置上也相鄰

單鏈表存儲結構

下面用結構指針來描述單鏈表

typedef struct Node 
{
    ElemType data;      // 數據域
    struct Node* Next   // 指針域
} Node;
typedef struct Node* LinkList;

獲得鏈表第i個數據的算法思路

1.聲明一個結點p指向鏈表第一個結點，初始化j從1開始

2.當j

3.若到鏈表末尾p為空，則說明第i個元素不存在

4.否則查找成功，返回結點p的數據

下面是實現代碼

Status GetElem(linkList L, int i, ElemType *e)
{
    int j;
    LinkList p;    
    p = L->next;
    j = 1;    
    while(p && j<i)
    {
        p = p->next;
        ++j;
    }    
    if(!p || j>i)
    {
        return ERROR;
    }    
    *e = p->data;    
    return OK;
}

單鏈表第i個數據插入結點的算法思路

1.聲明一個結點p指向鏈表頭結點，初始化j從1開始

2.當j

3.若到鏈表末尾p為空，則說明第i個元素不存在

4.否則查找成功，在系統中生成一個空結點s

5.將數據元素e賦值給s->data

6.執行這兩個語句 s->next = p->next ; p->next = s;

下面是實現代碼

Status ListInsert(LinkList *L, int i, ElemType e)
{
    int j;
    LinkList p,s;    
    p = *L;
    j = 1;    
    while(p && j<i)  // 用于尋找第i個結點
    {
        p = p->next;
        j++;
    }    
    if(!p || j>i)
    {
        return ERROR;
    }    
    s = (LinkList)malloc(sizeof(Node)); // 申請一個結點長度空間
    s->data = e;    
    s->next = p->next;  // 將原始指向的指針域賦給插入結點的指針域
    p->next = s;   // 插入結點賦給P的指針域    
    return OK;
}

單鏈表第i個數據刪除結點的算法思路

1.聲明一個結點p指向第一個結點，初始化j=1

2.當j

3.若到鏈表末尾p為空，則說明第i個元素不存在

4.否則查找成功，將欲刪除結點p->next賦值給q

5.執行這個語句 p->next = q->next ;

6.將q結點中的數據賦值給e，作為返回

下面是實現代碼

Status ListDelete(LinkList *L, int i, ElemType *e)
{
    int j;
    LinkList p,q;   
    p = *L;
    j = 1;    
    while(p->next && j<i)  // 用于尋找第i個結點
    {
        p = p->next;
        j++;
    }    
    if(!(p->next) || j>i)
    {
        return ERROR;
    }    
    q = p->next;   // 刪除的結點賦給q
    p->next = q->next;  // 將欲刪除的下一個結點指向p的指針域    
    *e = q->data;   // 作為返回欲刪除的數據
    free(q); // 釋放刪除的結點    
    return OK;
}

順序存儲結構

順序存儲結構是存儲結構類型中的一種，該結構是把邏輯上相鄰的結點存儲在物理位置上相鄰的存儲單元中，結點之間的邏輯關系由存儲單元的鄰接關系來體現。

插入算法的思路：

1.如果插入位置不合理，拋出異常

2.如果線性表長度大于等于數組長度，則拋出異常或動態增加數組容量

3.從最后一個元素開始向前遍歷到第i個位置，分別將它們都向后移動一個位置

4.將要插入元素填入位置i處

5.線性表長+1

下面是實現代碼

Status ListInsert(SqList *L, int i, ElemType e)
{
    int k;   
    if(L->length == MAXSIZE)  // 順序線性表滿了
    {
        return ERROR;
    }
    if(i<1 || i>L->length+1)  // 當i不在范圍內時
    {
        return ERROR;
    }
    if(i <= L->length)   // 若插入數據位置不在表尾  
    {
        /* 將要插入位置后數據元素向后移動一位 */
        for(K=L->length-1; k >= i-1;k--)
        {
            L->data[k+1] = L->data[k];
        }        
        L->data[i-1] = e;  // 將新元素插入
        L->length++;        
        return OK;
    }
}

刪除算法的思路

1.如果刪除位置不合理，拋出異常

2.取出刪除元素

3.從刪除元素位置開始遍歷到最后一個元素位置，分別將它們都向前移動一個位置

4.表長-1

下面是實現代碼

Status ListDelete(SqList *L, int i, ElemType *e)
{
    int k;   
    if(L->length == 0)  // 判斷表長是否為空
    {
        return ERROR;
    }
    if(i<1 || i>L->length)  // 當i不在范圍內時
    {
        return ERROR;
    }    
    *e = L->data[i-1]; // 用e返回刪除的值    
    if(i < L->length) 
    {
        /* 將刪除位置后面的元素全部向前移動 */
        for(K=i; k < L->length;k++)
        {
            L->data[k-1] = L->data[k];
        }        
        L->length--;        
        return OK;
    }
}

線性表的順序存儲結構，在存、讀數據時，不管是哪個位置，時間復雜度都是O(1)。而在插入或刪除時，時間復雜度都是O(n)。線性表作為數據結構中的重要組成成員，線性表的邏輯結構簡單，便于實現和操作，因此，線性表在實際應用中得到了廣泛應用。在本站的數據結構和算法教程中還有對許多的優秀的數據結構全面解析，讓我們能夠快速掌握各種數據結構。