鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，又叫鏈接存儲(chǔ)結(jié)構(gòu)。在計(jì)算機(jī)中用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素(這組存儲(chǔ)單元可以是連續(xù)的,也可以是不連續(xù)的).它不要求邏輯上相鄰的元素在物理位置上也相鄰

單鏈表存儲(chǔ)結(jié)構(gòu)

下面用結(jié)構(gòu)指針來描述單鏈表

typedef struct Node 
{
    ElemType data;      // 數(shù)據(jù)域
    struct Node* Next   // 指針域
} Node;
typedef struct Node* LinkList;

獲得鏈表第i個(gè)數(shù)據(jù)的算法思路

1.聲明一個(gè)結(jié)點(diǎn)p指向鏈表第一個(gè)結(jié)點(diǎn)，初始化j從1開始

2.當(dāng)j

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

4.否則查找成功，返回結(jié)點(diǎn)p的數(shù)據(jù)

下面是實(shí)現(xiàn)代碼

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個(gè)數(shù)據(jù)插入結(jié)點(diǎn)的算法思路

1.聲明一個(gè)結(jié)點(diǎn)p指向鏈表頭結(jié)點(diǎn)，初始化j從1開始

2.當(dāng)j

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

4.否則查找成功，在系統(tǒng)中生成一個(gè)空結(jié)點(diǎn)s

5.將數(shù)據(jù)元素e賦值給s->data

6.執(zhí)行這兩個(gè)語句 s->next = p->next ; p->next = s;

下面是實(shí)現(xiàn)代碼

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

單鏈表第i個(gè)數(shù)據(jù)刪除結(jié)點(diǎn)的算法思路

1.聲明一個(gè)結(jié)點(diǎn)p指向第一個(gè)結(jié)點(diǎn)，初始化j=1

2.當(dāng)j

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

4.否則查找成功，將欲刪除結(jié)點(diǎn)p->next賦值給q

5.執(zhí)行這個(gè)語句 p->next = q->next ;

6.將q結(jié)點(diǎn)中的數(shù)據(jù)賦值給e，作為返回

下面是實(shí)現(xiàn)代碼

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

順序存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)結(jié)構(gòu)是存儲(chǔ)結(jié)構(gòu)類型中的一種，該結(jié)構(gòu)是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元中，結(jié)點(diǎn)之間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。

插入算法的思路：

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

2.如果線性表長度大于等于數(shù)組長度，則拋出異?；騽?dòng)態(tài)增加數(shù)組容量

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

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

5.線性表長+1

下面是實(shí)現(xiàn)代碼

Status ListInsert(SqList *L, int i, ElemType e)
{
    int k;   
    if(L->length == MAXSIZE)  // 順序線性表滿了
    {
        return ERROR;
    }
    if(i<1 || i>L->length+1)  // 當(dāng)i不在范圍內(nèi)時(shí)
    {
        return ERROR;
    }
    if(i <= L->length)   // 若插入數(shù)據(jù)位置不在表尾  
    {
        /* 將要插入位置后數(shù)據(jù)元素向后移動(dòng)一位 */
        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.從刪除元素位置開始遍歷到最后一個(gè)元素位置，分別將它們都向前移動(dòng)一個(gè)位置

4.表長-1

下面是實(shí)現(xiàn)代碼

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

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