C語言資料結構(4)--鍊式存儲線性表

1. 順序存儲線性表的缺點

上一篇講了順序存儲線性表，實際上就是用數組的順序來表達一個有順序的一維資料集合。

但是資料這種存儲結構存在一些問題：

容量有限，數組屬于連續存儲空間，不能太大，如果申請太大的連續數組空間，可能會GG，至于具體能申請多大，請大家試試，貓哥比較懶，此處就不試了

插入與删除速度慢。這個是肯定的啦，比如插入一個元素，後面所有的元素都得往後移動，删除一個元素，前面的元素都得往前移動。

咋辦捏，有一個很樸素的想法就是，讓前面一個人記住後面一個人，不用關心整體，隻要前後關聯就OK。這種資料結構即為鍊式存儲線性表。

2. 鍊式存儲線性表的實作原理

因為C語言支援指針啊，讓前面一個記住後面一個，太簡單了啊，直接讓前面一個的指針指向後面一個完事。那第一個咋辦捏，第一個沒有前面一個啊，那也麼事，我們直接定義一個頭部指向第一個元素，也就是說頭部實際上不是線性表的資料部分，但是它能把鍊式線性表關聯出來。

就像火車頭，雖然不拉乘客，但是能帶着乘客去他們想去的地方。這個比喻實在太形象了，厲害炸了~

3. 鍊式存儲線性表的操作

此處跟順序線性表一模一樣，因為都是線性表嘛，功能一樣，隻是存儲結構不一樣。

顯示線性表元素個數

列出線性表的所有元素

擷取指定位置元素

在指定位置插入元素

删除指定位置元素

清空線性表

4. 代碼實作

話不多說，說多了上頭。酒不多喝，喝多了會難受，直接上代碼~

PS：我自己測試沒發現BUG，但是不能保證肯定沒有BUG…保佑我~！

/*
* 鍊式存儲線性表
* 作者:熊貓大大
* 時間:2019-09-25
*/
#include<stdio.h>

// 線性表的節點結構體
typedef struct {
    int data;//儲存節點資料
    struct Node *next;//指向下一個節點
}Node;

// 擷取元素個數
int getCount(Node *head)
{
    int count = 0;
    Node* p = head;//定義一個指針首先指向頭結點
    while (p->next != NULL)//還有資料元素
    {
        count++;
        p = p->next;
    }
    return count;
}

// 顯示所有元素
void printList(Node *head)
{
    int i;
    printf("\n所有元素:");
    Node* p = head;//定義一個指針首先指向頭結點
    while (p->next != NULL)
    {
        p = p->next;
        printf("%d ", p->data);
    }
}

// 擷取指定位置元素，傳回值放入result指向元素，注意位置從0開始
int getData(Node *head, int index, int *result)
{
    int i = 0;//目前位置
    if (index < 0)
    {
        return 0; //位置不存在
    }
    Node* p = head;//定義一個指針首先指向頭結點

    while (p->next != NULL)
    {
        p = p->next;
        if (i == index) {
            *result = p->data;
        }
        i++;
    }
    if (i >= index) //位置超限
    {
        return 0;
    }
    return 1;//1表示成功
}

// 插入元素
int insertData(Node *head, int index, int input)
{
    int i = 0;//目前位置
    Node* temp = (Node*)malloc(sizeof(Node));//臨時節點
    if (index < 0)
    {
        return 0; //位置不存在
    }
    if (index == 0) //第一個位置插入元素
    {
        temp->data = input;
        temp->next = head->next;
        head->next = temp;
        return;
    }
    Node* p = head;//定義一個指針首先指向頭結點
    while (p->next != NULL)
    {
        p = p->next;
        i++;
        if (i == index) {//找到插入位置
            temp->data = input;
            temp->next = p->next;
            p->next = temp;
            return;
        }
    }
    if (i == index) //最後一個後面追加
    {
        return 1;
    }
    else {
        return 0;//位置超限
    }
    return 1;
}

// 删除指定位置元素
int deleteData(Node *head, int index)
{
    int i = 0;//目前位置
    if (index < 0)
    {
        return 0; //位置不存在
    }
    Node* p = head;//定義一個指針首先指向頭結點
    Node* front = head;//記錄前一個元素
    while (p->next != NULL)
    {
        front = p;
        p = p->next;
        if (i == index) {//删除該元素
            front->next = p->next;//跳過被删除元素
            free(p);//釋放
            return;
        }
        i++;
    }
    if (i >= index) //位置超限
    {
        return 0;
    }
    return 1;//1表示成功
}

// 清空所有元素
int clearData(Node *head)
{
    Node* p = head->next;
    Node* temp;
    while (p != NULL)
    {
        temp = p->next;
        free(p);
        p = temp;
    }
    head->next = NULL;
    return 1;
}

// 入口
int main()
{
    Node head;//頭部節點實際上就代表了一個連結清單
    head.data = 0;//頭部節點存儲的資料沒意義
    head.next = NULL;//剛開始沒有資料節點
    int count = getCount(&head);
    printf("初始長度:%d\n", count);
    insertData(&head, 0, 1);
    insertData(&head, 1, 2);
    insertData(&head, 1, 3);
    count = getCount(&head);
    printf("新增後長度:%d\n", count);
    printList(&head);
    int result = 0;
    getData(&head, 2, &result);
    printf("位置2元素:%d\n", result);
    deleteData(&head, 0);
    printList(&head);
    clearData(&head);
    count = getCount(&head);
    printf("清空後長度:%d\n", count);
    return 1;
}