（數(shù)據(jù)結(jié)構(gòu)&C語言）順序表

專業(yè)成都網(wǎng)站建設(shè)公司，做排名好的好網(wǎng)站，排在同行前面，為您帶來客戶和效益!成都創(chuàng)新互聯(lián)為您提供成都網(wǎng)站建設(shè)，五站合一網(wǎng)站設(shè)計(jì)制作，服務(wù)好的網(wǎng)站設(shè)計(jì)公司，成都網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計(jì)負(fù)責(zé)任的成都網(wǎng)站制作公司!文章目錄

• • （數(shù)據(jù)結(jié)構(gòu)&C語言）順序表
  • • 編寫初始化操作
    • 編寫插入操作
    • 編寫刪除操作
    • 獲取指定位置上的元素
    • 查找指定元素的位置
    • 獲取長度
    • 相關(guān)問題

線性表的順序存儲(chǔ)結(jié)構(gòu)，指的是用一段地址連續(xù)的存儲(chǔ)單元一次存儲(chǔ)線性表的數(shù)據(jù)元素。

基于數(shù)組，編寫一些額外的操作來強(qiáng)化為線性表，像這樣底層以惡案采用順序存儲(chǔ)實(shí)現(xiàn)的線性表，稱為順序表。

從上圖不難看出線性表的長度應(yīng)始終小于數(shù)組的長度。

這里我們可以先定義一個(gè)新的結(jié)構(gòu)體類型，將一些需要用到的數(shù)據(jù)保存在一起，這里我們以int類型的線性表為例：

struct List {int * array;
  int capacity;  //表示底層數(shù)組的初始容量
};
typedef struct List * ArrayList;  //為方便

編寫初始化操作

_Bool initList(ArrayList list) {list->array = malloc(sizeof(int) * 10);
  if(list->array == NULL) return 0;  //需要判斷如果申請(qǐng)的結(jié)果為NULL的話表示內(nèi)存空間申請(qǐng)失敗
  list->capacity = 10;  //容量設(shè)定為10
  list->size = 0;  //元素?cái)?shù)量默認(rèn)為0
  return 1
}

編寫插入操作

void insertList(ArrayList list, int element, int index){//index表示插入位序
  if(index< 1 || index >list->size + 1) return 0;   //如果在非法位置插入，返回0表示插入操作執(zhí)行失敗
    for (int i = list->size; i >index - 1; --i)  
        list->array[i] = list->array[i - 1];//先使用for循環(huán)將待插入位置后續(xù)的元素全部挪到后一位
    list->array[index - 1] = element;    //挪完之后，位置就騰出來了，直接設(shè)定即可
    list->size++;  //元素?cái)?shù)量+1
}

如果我們的表已經(jīng)裝滿了，也就是說size已經(jīng)達(dá)到申請(qǐng)的內(nèi)存空間大的大小了，那么此時(shí)我們就需要考慮進(jìn)行擴(kuò)容：

_Bool insertList(ArrayList list, int element, int index){if(index< 1 || index >list->size + 1) return 0;
    if(list->size == list->capacity) {//size已經(jīng)到達(dá)大的容量
        int newCapacity = list->capacity + (list->capacity >>1);   //先計(jì)算一下新的容量大小，這里我取1.5倍原長度，當(dāng)然也可以想擴(kuò)多少擴(kuò)多少
        int * newArray = realloc(list->array, sizeof(int) * newCapacity);  //函數(shù)realloc重新申請(qǐng)更大的內(nèi)存空間
        if(newArray == NULL) return 0;   //如果申請(qǐng)失敗，那么就確實(shí)沒辦法插入了，只能返回0表示插入失敗了
        list->array = newArray;
        list->capacity = newCapacity;
    }
    for (int i = list->size; i >index - 1; --i)
        list->array[i] = list->array[i - 1];
    list->array[index - 1] = element;
    list->size++;
    return 1;
}

realloc函數(shù)可以做到控制動(dòng)態(tài)內(nèi)存開辟的大小，重新申請(qǐng)的內(nèi)存空間大小就是我們指定的新的大小，并且原有的數(shù)據(jù)也會(huì)放到新申請(qǐng)的空間中。當(dāng)然如果因?yàn)閮?nèi)存不足之類的原因?qū)е聝?nèi)存空間申請(qǐng)失敗，那么會(huì)返回NULL，所以也需要進(jìn)行判斷。

編寫刪除操作

_Bool deleteList(ArrayList list,int index) {if(index< 1 || index >list->size) return 0;
    for (int i = index - 1; i< list->size - 1; ++i)
      list->array[i] = list->array[i + 1]; //依次把后面的元素覆蓋到前一個(gè)
  list->size--;
  return 1;
}

獲取指定位置上的元素

int getList(ArrayList list, int index){if(index< 1 || index >list->size) return NULL;   //如果超出范圍就返回NULL
    return list->array[index - 1];
}

查找指定元素的位置

int findList(ArrayList list, int element){for (int i = 0; i< list->size; ++i) {if(list->array[i] == element) return i + 1;  //直到找到指定元素，返回位序
    }
    return -1;  //如果遍歷完了都沒找到，那么就返回-1
}

獲取長度

int sizeList(ArrayList list){return list->size;   //直接返回size
}

完整代碼如下：

#include#includestruct List {int * array;
    int capacity;
    int size;
};
typedef struct List * ArrayList;

_Bool initList(ArrayList list) {list->array = malloc(sizeof(int) * 10);
    if(list->array == NULL) return 0;
    list->capacity = 10;
    list->size = 0;
    return 1;
}

_Bool insertList(ArrayList list,int element,int index) {if(index< 1 || index >list->size + 1) return 0;
    
    if(list->size == list->capacity) {int newCapacity = list->capacity + (list->capacity >>1);
        int * newArray = realloc(list->array, sizeof(int) * newCapacity);
        if(newArray == NULL) return 0;
        list->capacity = newCapacity;
        list->array = newArray;
    }
    
    for (int i = list->size; i >index - 1; --i)
        list->array[i] = list->array[i - 1];
    list->array[index - 1] = element;
  list->size++;
    return 1;
}

_Bool deleteList(ArrayList list,int index) {if(index< 1 || index >list->size) return 0;
    
    for (int i = index - 1; i< list->size - 1; ++i)
        list->array[i] = list->array[i + 1];
    list->size--;
    return 1;
}

int getList(ArrayList list,int index) {if(index< 1 || index >list->size) return 0;
    return list->array[index - 1];
}

int findList(ArrayList list,int element) {for (int i = 0; i< list->size - 1; ++i)
        if(list->array[i] == element) return i + 1;
    return -1;
}

int sizeList(ArrayList list) {return list->size;
}

void printList(ArrayList list){//用于打印鏈表
    for (int i = 0; i< list->size; ++i)
        printf("%d ", list->array[i]);
    printf("\n");
}

int main() {struct List biao;  //創(chuàng)建一個(gè)結(jié)構(gòu)體變量
    if(initList(&biao)) {//判斷初始化是否成功
        for (int i = 0; i< 30; ++i)
            insertList(&biao, i * 10, i + 1);  //先插入30個(gè)
        deleteList(&biao,3);
        printList(&biao);
        printf("%d\n",getList(&biao,3));
        printf("%d\n",findList(&biao,150));
        printf("%d\n",sizeList(&biao));
    } else {printf("Failed");
    }
}

運(yùn)行后，成功得到結(jié)果：

相關(guān)問題

值得注意的是：

• 插入：因?yàn)橐獙⒑罄m(xù)所有元素都向后移動(dòng)，所以平均時(shí)間復(fù)雜度為 O ( n ) O(n) O(n)
• 刪除：同上，因?yàn)橐獙⑺性叵蚯耙苿?dòng)，所以平均時(shí)間復(fù)雜度為 O ( n ) O(n) O(n)
• 獲取元素：因?yàn)榭梢岳脭?shù)組特性直接通過下標(biāo)訪問到對(duì)應(yīng)元素，所以時(shí)間復(fù)雜度為 O ( 1 ) O(1) O(1)

順序表底層是基于數(shù)組實(shí)現(xiàn)的，那么它肯定是支持隨機(jī)訪問的，因?yàn)槲覀兛梢灾苯邮褂孟聵?biāo)想訪問哪一個(gè)就訪問哪一個(gè)，它并不需要按照順序來進(jìn)行存取，鏈表才是。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站欄目：（數(shù)據(jù)結(jié)構(gòu)&C語言）對(duì)順序表的認(rèn)識(shí)-創(chuàng)新互聯(lián)
當(dāng)前網(wǎng)址：http://www.chinadenli.net/article40/djcceo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制開發(fā)、域名注冊(cè)、營銷型網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)、Google、手機(jī)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)