線性結構-數組

了解：

線性結構：可以用一根線把所有的結點都串起來。

術語：

線性結構：

1. 有唯一一個第一個元素
2. 有唯一一個最後一個元素
3. 所有元素，除第一個元素外，都有唯一前繼
4. 所有元素，除最後一個元素外，都有唯一後繼

代碼實作：

#include <stdio.h>
#include <stdlib.h>  //包含了exit()
#include <malloc.h>
#include <stdbool.h>
//定義一個資料類型，名字叫struct Arr，有三個成員
struct Arr{
    int * pBase; //存儲數組第一個元素的位址
    int length; //數組所能容納最大元素個數
    int cnt; //目前數組有效元素個數
};

void init_arr(struct Arr * pArr, int length); //初始化一個數組
bool isEmpty(struct Arr * pArr); //判斷數組是否為空
void show_arr(struct Arr * pArr); //列印數組
bool append_arr(struct Arr * pArr,int element); //在數組末尾追加一個元素
bool intsert_arr(struct Arr * pArr,int element,int pos); //在數組中插入一個元素
bool delete_arr(struct Arr * pArr,int *pElement,int pos); //删除數組中的一個元素
int get(struct Arr * pArr,int pos); //擷取數組中的一個元素
bool isFull(struct Arr * pArr); //判斷數組是否滿
void sort_arr(struct Arr * pArr); //對數組進行排序
void inversion_arr(struct Arr * pArr); //倒置數組

/**
    初始化數組
    struct Arr * pArr 用于動态改變變量的值
    int length 自定義數組長度個數
*/
void init_arr(struct Arr * pArr, int length){
    pArr->pBase = (int *)malloc(sizeof(int)*length);
    if(NULL == pArr->pBase){
        printf("動态記憶體配置設定失敗！");
        exit(-1);
    }
    pArr->cnt=0;
    pArr->length=length;
    return;
}

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


/**
    列印數組
*/
void show_arr(struct Arr * pArr){
    if(isEmpty(pArr)){  //如果數組為空，則輸出提示
        printf("數組為空！\n");
    }else{ //如果不為空，則打錢輸出數組
        for(int i=0; i<pArr->cnt; i++){
            printf("%d\t", pArr->pBase[i]);
        }
        printf("\n");
    }
    return;
}

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

/**
    在數組末尾追加元素
    struct Arr * pArr 接收數組第一個元素的位址
    int element 需要追加的元素
*/
bool append_arr(struct Arr * pArr,int element){
    if(isFull(pArr)){
        printf("數組已滿！\n");
        return false;
    }else{
        pArr->pBase[pArr->cnt] = element;
        pArr->cnt++;
        return true;
    }
}

/**
    把元素插入指定的位置
    int pos 表示元素的位置，如果換算成數組下标則為 pos-1
*/
bool intsert_arr(struct Arr * pArr,int element,int pos){
    //判斷數組是否為滿
    if(isFull(pArr))
        return false;
    //判斷插入元素的位置是否合法
    if(pos<1 || pArr->cnt+1<pos)
        return false;
    //移動元素
    for(int i = pArr->cnt-1; i>=pos-1; --i){
        pArr->pBase[i+1] = pArr->pBase[i];
    }
    pArr->pBase[pos-1] = element;
    pArr->cnt++;
    return true;
}

/**
    删除一個元素，并傳回被删除元素的值
*/
bool delete_arr(struct Arr * pArr,int *pElement,int pos){
    if(isEmpty(pArr))
        return false;
    if(pos<1 || pos > pArr->cnt)
        return false;

    //儲存删除的元素
    *pElement = pArr->pBase[pos-1];
    //移動元素
    for(int i=pos; i<pArr->cnt; i++){
        pArr->pBase[i-1] = pArr->pBase[i];
    }
    pArr->cnt--;
    return true;
}

/**
    倒置數組
*/
void inversion_arr(struct Arr * pArr){
    int i=0,t;
    int j=pArr->cnt-1;
    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-1;i++){
        for(j=i+1;j<pArr->cnt-1;j++){
            if(pArr->pBase[i] > pArr->pBase[j]){
                t=pArr->pBase[i];
                pArr->pBase[i] = pArr->pBase[j];
                pArr->pBase[j] = t;
            }
        }
    }
    return;
}

/**
    查找指定位置元素的值，并傳回它的值
*/
int get(struct Arr * pArr,int pos){
    return pArr->pBase[pos-1];
}

int main()
{
    struct Arr arr;  //定義一個結構變量
    int elem; //儲存被删除元素的值
    //測試初始化功能
    init_arr(&arr,6);
    show_arr(&arr);
    //測試追加功能
    append_arr(&arr,1);
    append_arr(&arr,2);
    append_arr(&arr,3);
    append_arr(&arr,4);
   /*append_arr(&arr,5);
    append_arr(&arr,6);
    append_arr(&arr,7);*/
    //測試插入元素功能
    intsert_arr(&arr,22,1);
    //intsert_arr(&arr,22,-1);
    //intsert_arr(&arr,33,6);
    //intsert_arr(&arr,88,7);
    //intsert_arr(&arr,88,0);

    //測試删除元素
    if(delete_arr(&arr,&elem,3)){
        printf("删除成功，你删除的元素是：%d\n",elem);
    }else{
        printf("删除失敗！");
    }
    show_arr(&arr);
    printf("Hello world! \n");

    //測試倒置
    inversion_arr(&arr);
    show_arr(&arr);

    //測試排序
    sort_arr(&arr);
    show_arr(&arr);

    //測試查找指定元素
    printf("你要的元素是：%d ",get(&arr,3));
    return 0;
}