線性表之順序存儲結構實現

一，線性表的概念以及數學定義

1.線性表的概念

　　零個或多個數據元素的有限序列。首先說明這是一個序列，也就是說數據元素之間是有順序的，若元素存在多個，則第一個元素無前驅，最後一個元素無後繼，其他每個元素都有且僅有一個前驅和後繼。

2.數學定義

　　若將線性表記為(a₁...a_i-1,a_i,a_i+1....a_n)，則線性表中，a_i-1領先於a_i，a_i領先於a_i+1，則稱a_i-1是a_i的直接前驅元素，a_i+1是a_i的直接後繼元素，當i=1,2....n-1的時候，a_i有且僅有一個直接後繼元素，當i=2,3...n的時候，a_i有且僅有一個直接前驅元素。

二，線性表的順序存儲結構

1.順序存儲結構的概念

　　線性表的順序存儲結構，指的是利用一段地址連續的存儲單元依次存儲線性表的數據元素。

2.順序存儲方式的實現

　　我們利用數組這個數據類型，來表示一段地址連續的存儲單元。

三，線性表之順序存儲結構的的實現

1.線性表基本功能：

　　1.創建線性表 ==> List * createList(int capacity);

　　2.銷毀線性表 ==> void destoryList(List * list);

　　3.清空線性表 ==> void clearList(List * list);

　　4.獲取線性表長度 ==> int length(List * list);

　　5.獲取線性表容量 ==> int capacity(List * list);

　　6.線性表的插入 ==> void insert(List * list,int pos,Node * node);

　　7.線性表的刪除 ==> Node * delete(List * list,int pos);

　　8.線性表的修改 ==> Node * update(List * list,int pos,Node * node);

　　9.線性表的獲取 ==> Node * get(List * list,int pos);

2.線性表基本功能的代碼實現：

# include<stdio.h>
# include<stdlib.h>
# include<string.h>

typedef void Node;

typedef struct SeqList
{
    int capacity;
    int length;
    int * array;
}List;

/* 創建指定容量大小的線性表 */
List * createList(int capacity)
{
    // 在堆上分配線性表對象
    List * list = (List *)malloc(sizeof(List));
    // 初始化線性表對象的容量
    list->capacity = capacity;
    // 初始化線性表當前長度
    list->length = 0;
    // 初始化線性表的數組
    list->array = malloc(capacity*sizeof(void *));
    // 返回線性表
    return list;
}
/* 銷毀線性表 */
void destoryList(List * list)
{
    if (list != NULL)
    {
        if (list->array != NULL)
        {
            // 釋放線性表中的數組
            free(list->array);
            list->array = NULL;
        }
        // 釋放線性表對象
        free(list);
        list = NULL;
    }
}
/* 清空線性表 */
void clearList(List * list)
{
    if (list != NULL)
    {
        // 線性表的數組清空
        memset(list->array, 0, sizeof(list->array)/list->capacity);
        // 線性表的長度清空
        list->length = 0;
    }
}
/* 線性表的長度 */
int length(List * list)
{
    return list->length;
}
/* 線性表的容量 */
int capacity(List * list)
{
    return list->capacity;
}
/* 線性表的插入 */
void insert(List * list, int pos, Node * node)
{
    if (list == NULL)
    {
        printf("線性表為NULL\n");
        return;
    }
    if (pos > list->capacity)
    {
        printf("插入位置超過線性表的容量\n");
        return;
    }
    if (list->length > list->capacity)
    {
        printf("線性表容量已滿,無法插入\n");
        return;
    }
    // 容錯機制 6個長度，容量20，插入10，則自動插入到7這個位置
    if (pos>list->length)
    {
        list->array[list->length] = node;
        // 線性表長度加一
        list->length++;
        return;
    }
    // 移動pos之後的數據
    for (int i = list->length; i > pos-1; i--)
    {
        list->array[i] = list->array[i-1];
    }
    // 插入數據
    list->array[pos - 1] = node;
    // 線性表長度加一
    list->length++;
}
/* 線性表的刪除 */
Node * delete(List * list, int pos)
{
    if (list == NULL)
    {
        printf("線性表為NULL\n");
        return NULL;
    }
    if (pos > list->length)
    {
        printf("刪除位置不存在\n");
        return NULL;
    }
    // 返回的元素
    Node * node = list->array[pos - 1];;
    // 刪除元素後線性表長度減一
    list->length--;
    // 刪除最後一個
    if (pos == list->length)
    {
        list->array[pos - 1] = NULL;
        return node;
    }
    // 刪除
    for (int i = pos - 1; i < list->length; i++)
    {
        list->array[i] = list->array[i + 1];
    }
    return node;
}
/* 線性表的修改 */
Node * update(List * list, int pos, Node * node)
{
    if (list == NULL)
    {
        printf("線性表為NULL\n");
        return NULL;
    }
    // 返回修改前的對象
    Node * result = list->array[pos - 1];
    // 修改
    list->array[pos - 1] = node;

    return result;
}
/* 線性表的獲取 */
Node * get(List * list, int pos)
{
    if (list == NULL)
    {
        printf("線性表為NULL\n");
        return NULL;
    }
    return list->array[pos - 1];
} 

3.測試程序實現

/* 測試程序 */
typedef struct Student
{
    char name[64];
    int age;
}Student;

int main()
{
    // 創建線性表
    List * list = createList(20);
    // 創建學生對象並初始化
    Student s1 = { "劉備",42 };
    Student s2 = { "關羽",38 };
    Student s3 = { "張飛",32 };
    Student s4 = { "趙雲",36 };
    Student s5 = { "馬超",26 };
    Student s6 = { "黃忠",59 };
    // 頭插法插入
    insert(list, 1, &s1);
    insert(list, 2, &s2);
    insert(list, 3, &s3);
    insert(list, 4, &s4);
    insert(list, 5, &s5);
    insert(list, 19, &s6);
    // 獲取長度
    printf("############線性表長度############\n");
    printf("length = %d\n", length(list));
    // 獲取容量
    printf("############線性表容量############\n");
    printf("capacity = %d\n", capacity(list));
    // 遍歷
    printf("############線性表遍歷############\n");
    for (int i = 1; i <= length(list); i++)
    {
        Student * s = get(list, i);
        printf("name = %s,age = %d\n", s->name, s->age);
    }
    // 刪除第一個元素
    delete(list, 3);
    printf("############刪除第三個元素############\n");
    // 遍歷
    for (int i = 1; i <= length(list); i++)
    {
        Student * s = get(list, i);
        printf("name = %s,age = %d\n", s->name, s->age);
    }
    // 修改第一個元素
    printf("############修改第一個元素############\n");
    Student sss = { "劉備-漢中王",50 };
    update(list, 1, &sss);
    // 遍歷
    for (int i = 1; i <= length(list); i++)
    {
        Student * s = get(list, i);
        printf("name = %s,age = %d\n", s->name, s->age);
    }
    // 清空線性表
    printf("############清空線性表############\n");
    clearList(list);
    // 遍歷
    for (int i = 1; i <= length(list); i++)
    {
        Student * s = get(list, i);
        printf("name = %s,age = %d\n", s->name, s->age);
    }
    // 銷毀線性表
    printf("############銷毀線性表############\n");
    destoryList(list);

    return 0;
}

四，線性表順序存儲結構的總結

1.順序存儲結構的優點

　　1.無需為線性表中的邏輯關系增加額外的空間。

　　2.可以快速獲取線性表中合法位置的數據元素。

2.順序存儲結構的缺點

　　1.插入和刪除操作需要移動大量元素。

　　2.當線性表長度變化較大時難以確定存儲空間的容量。

3.總結

　　線性表順序存儲結構適用於查詢多，增刪少，數據長度變化小的場景。

更多詳情見請繼續閱讀下一頁的精彩內容： http://www.linuxidc.com/Linux/2017-01/139260p2.htm