數據結構入門-線性結構

把所有的節點用一根直線串起來

連續存儲[數組]

什麼叫做數組：元素類型相同，大小相等

重點看代碼吧，需要註意的都在註釋里，多敲幾遍，當然了，有些功能還沒有實現，以後再實現

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

// 定義了一個數據類型，這個數據類型的名字叫做struct Arr，有三個成員
struct Arr
{
    int * pBase;  // 存儲的是數組第一個元素的地址
    int len;  // 數組所能容納的最大元素的個數
    int cnt; // 當前元素有效元素的個數
};


void init_arr(struct Arr * pArr , int length);
bool append_arr(struct Arr * pArr  , int val); 
bool insert_arr(struct Arr * pArr , int pos , int val); //pos值從1開始
bool delete_arr(struct Arr * pArr , int pos , int *pval); // 這個指針用來接收刪除的那個值
bool is_empty(struct Arr * pArr );
bool is_full(struct Arr * pArr );
void sort_arr(struct Arr * pArr );
void show_arr(struct Arr * pArr );
void inversion_arr(struct Arr * pArr);



int main(void)
{
    struct Arr arr;
    int val;

    // 這裡要傳入地址
    init_arr(&arr , 6);
    append_arr(&arr,2);
    append_arr(&arr,18);
    append_arr(&arr,55);
    append_arr(&arr,99);
    append_arr(&arr,6);
    inversion_arr(&arr);
    // insert_arr(&arr,1,100);
    // show_arr(&arr);
    // if(delete_arr(&arr, 6 , &val))
    //  printf("刪除的元素為：%d\n", val);
    sort_arr(&arr);
    show_arr(&arr);


    

    return 0;
}

// 用於初始化,自己指定長度
void init_arr(struct Arr * pArr , int length)
{
    // 指針變數pArr指向結構體中的pBase成員
    pArr->pBase = (int *)malloc(sizeof(int) * length);
    if (NULL == pArr->pBase)
    {
        printf("動態記憶體分配失敗\n");
        exit(-1);  // 終止整個程式
    }
    else
    {
        pArr->len = length;
        pArr->cnt = 0;
        printf("初始化成功\n");
    }
    return;

}

// 輸出數組
void show_arr(struct Arr * pArr )
{
    if (is_empty(pArr))
    {
        printf("數組為空！\n");
    }
    else
    {
        int i;
        printf("數組中的元素為：\n");
        for (i = 0; i < pArr->cnt; i++)
        {
            // 這裡需要註意，輸出的時候是這樣，根據元素地址來
            printf("%d\n", pArr->pBase[i]);
        }
    }
}

// 判斷數組是否為空
bool is_empty(struct Arr * pArr )
{
    if (pArr->cnt == 0)
        return true;
    else
        return false;
}


// 判斷數組是否滿了
bool is_full(struct Arr * pArr )
{
    if (pArr->cnt == pArr->len) 
        return true;
    else
        return false;
}


// 末尾添加元素
bool append_arr(struct Arr * pArr  , int val)
{

    if (is_full(pArr))
    {
        printf("數組已經滿了\n");
        return false;
    }
    else
    {
        // 這裡需要註意，把用戶傳入的值添加到當前對應的數組有效個數的後面，
        // 由於是數組，這裡直接寫cnt就可以了，完事之後有效個數加1
        pArr->pBase[pArr->cnt] = val;
        (pArr->cnt)++;
        printf("添加成功\n");
        return true;

    }
}



// 指定位置插入指定的元素
bool insert_arr(struct Arr * pArr , int pos , int val)
{

    int i;

    if (is_full(pArr))
        return false;
    if (pos < 1 || pos > pArr->cnt+1)
        return false;

    // 這裡需要註意，畫圖很直接就出來了
    for (i = pArr->cnt - 1; i >= pos-1; i--)
    {
        // 把前面的值往後面移
        pArr->pBase[i+1] = pArr->pBase[i];
    }
    // 把指定元素插入到指定位置就可以了,然後個數加1
    pArr->pBase[pos-1] = val;
    pArr->cnt++;
    printf("插入成功\n");

    return true;
}


// 刪除指定位置的值，並返回刪除的值，用指針
bool delete_arr(struct Arr * pArr , int pos , int *pval)
{
    int i;

    if (is_empty(pArr))
    {
        return false;
    }
    if (pos < 1 || pos > pArr->cnt)
    {
        return false;
    }

    // 把要刪除的那個值先賦值
    *pval = pArr->pBase[pos-1];

    for (i = pos; i <= pArr->cnt; i++)
    {
        pArr->pBase[i-1] = pArr->pBase[i];
    }

    pArr->cnt--;
    printf("刪除成功\n");
    return true;

}


// 進行倒置
void inversion_arr(struct Arr * pArr)
{
    int i = 0;
    int j = pArr->cnt - 1;
    int t;
    while(i < j)
    {
        t = pArr->pBase[i];
        pArr->pBase[i] = pArr->pBase[j];
        pArr->pBase[j] = t;
        ++i;
        --j;
    }
    return;
}


// 排序
void sort_arr(struct Arr * pArr )
{
    int i , j , t;

    for (i = 0; i < pArr->cnt; ++i)
    {
        for (j = i+1; j < pArr->cnt; ++j)
        {
            if (pArr->pBase[i] > pArr->pBase[j])
            {
                t = pArr->pBase[i];
                pArr->pBase[i] = pArr->pBase[j];
                pArr->pBase[j] = t;
            }
        }
    }
}