順序表

順序表是什么？

順序表是將元素順序地存放在一塊連續的存儲區里，元素間的順序關系由它們的存儲順序自然表示。實現增刪查改的功能。

順序表所需的頭文件：

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

目錄

順序表

靜態順序表

動態順序表

動態順序表

順序表的創建

順序表的初始化

順序表的銷毀

打印順序表

擴容

尾插

頭插

尾刪

頭刪

任意位置刪除

任意位置插入

元素的查找

元素修改

測試代碼和菜單

---

?順序表分為靜態順序表和動態順序表。

靜態順序表

靜態順序表的空間不可改變，使用確定大小的數組來確定元素。

靜態順序表的創建：

typedef struct SeqList {int arr[512];int size; //數組中元素的個數 };

動態順序表

動態順序表的空間可以被改變，使用動態內存函數開辟數組儲存元素

動態順序表的創建：

typedef struct SeqList {int* a;int size; //有多少元素int capaclity; //容量 };

靜態順序表和動態順序表的區別在于容量是否可變。

我們本節介紹動態順序表。

動態順序表

順序表的創建

我們用一個指針開辟一個空間，既順序表元素的空間。由于我們指針不一定是int型，為了嚴謹一定，我們自定義一個數據類型：

typedef int SEQ;

?然后就可以創建一個完整的順序表：

typedef struct SeqLisrt {SEQ* a;int size; //順序表中有多少元素int capaciti; //順序表的空間大小 }SL;

順序表的初始化

順序表第一次使用前需要初始化：

void Init(SL* ps) {ps->a = NULL;ps->size = 0;ps->capaciti = 0; }

順序表的銷毀

順序表在使用完以后需要進行銷毀保障安全：

void Destory(SL* ps) {free(ps->a);ps->a = NULL;ps->size = 0;ps->capaciti = 0; }

使用free函數釋放掉空間，并將其設置為空指針NULL。

打印順序表

為了直觀的看到順序表里的元素，我們需要一個打印順序表的函數：

void Print(SL* ps) {int i = 0;for (i=0;i<ps->size;i++){printf("%d ",ps->a[i]);} }

擴容

當順序表中的size>=capaciti是需要擴容，此時順序表的空間不夠用，那我們怎么進行擴容？

由于，最開始使用數據表順序表被初始化，capaciti為0，將capiaciti的容量賦予在?*2

其次賦予a新的空間，由于此時a為NULL，直接開辟新的空間會報警告，我們用一個中間變量tmp開啟一塊capaciti元素*2的空間，在將這塊空間賦予a。

實現代碼:

void CheckCapacity(SL* ps) {if (ps->size == ps->capaciti){int newcapaciti = ps->capaciti == 0 ? 4 : ps->capaciti * 2; SEQ* tmp = (SEQ*)realloc(ps->a, newcapaciti * sizeof(SEQ)*2);ps->a = tmp;ps->capaciti = newcapaciti;} }

實現以上準備工作后，我們進入順序表重點，增刪查改功能的實現了。

尾插

size為順序表中的元素個數，每當插入一個新元素后size++；

尾插：將新的元素放到順序表最后一個元素的后面：?

代碼實現：

void PushBack(SL* ps, SEQ x) {CheckCapacity(ps); //自定義的擴容函數ps->a[ps->size] = x;ps->size++; }

在對順序表插入新元素的，使用自己寫的擴容函數判斷一下。

頭插

?

頭插：順序表的元素往后移位，將新的元素放到順序表的最前面：

void PushFront(SL* ps, SEQ x) {CheckCapacity(ps);int end = ps->size - 1;while (end >= 0){ps->a[end+1] = ps->a[end];end--;}ps->a[0] = x;ps->size++; }

尾刪

將最后的元素刪去：

操作方法：將size--;

代碼實現：

void PopBack(SL* ps) {ps->size--; }

頭刪

將順序表的第一個元素刪掉。

操作方法：將順序表的第一個元素后面的元素往前移一位，size--;

代碼實現：

void PopFront(SL* ps) {int start = 1;while (start < ps->size){ps->a[start - 1] = ps->a[start];start++;}ps->size--; }

任意位置刪除

pos為下標 既要刪除元素的位置。

?實現方法和頭刪類似后面的元素覆蓋掉前面的元素。

代碼實現：

void Erase(SL* ps, int pos) {int start = pos;while (start < ps->size - 1){ps->a[start] = ps->a[start + 1];start++;}ps->size--; }

任意位置插入

?和頭插類似，將元素往后移動在放入元素。

代碼實現：

void Insert(SL* ps, int pos, SEQ x) {int end = ps->size - 1;while (end > +pos){ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = x;ps->size++; }

元素的查找

使用循環以此查找，直到找到元素或順序表沒有此元素

找到元素返回下標，沒有找到返回-1；

代碼實現：

int Find(SL* ps, int pos) {int i = 0;for (i = 0; i < ps->size; i++){if (ps->a[i] == pos){return i;}}return -1; }

元素修改

找到想修改的位置直接修改即可。

代碼實現：

void At(SL* ps, int pos, SEQ x) {ps->a[pos] = x; }

以上就是增刪查改實現的全過程。

接下來我們來測試代碼

測試代碼和菜單

測試結果：

?測試菜單代碼：

void menu() {printf("********************************\n");printf("1.尾插數據 2.頭插數據\n");printf("3.尾刪數據 4.頭刪數據\n");printf("5.任意插入 6.任意刪除\n");printf("7.修改數據 8.查找數據\n");printf("9.打印數據 -1.退出\n");printf("********************************\n");printf("請輸入你操作的選項>:"); }int main() {int option = 0;int x = 0;int i = 0;int pos = 0;SL s;Init(&s); //使用順序表前先初始化while (option != -1){menu();scanf("%d", &option);switch (option){case 1:printf("請輸入你要尾插的數據,以-1結束\n");do{scanf("%d", &x);if (x != -1){PushBack(&s, x);}} while (x != -1);break;case 2:printf("請輸入你要頭插的數據,以-1結束\n");do{scanf("%d", &x);if (x != -1){PushFront(&s, x);}} while (x != -1);break;case 3:printf("請輸入你要尾刪的元素個數\n");scanf("%d", &x);for (i = 0; i < x; i++){PopBack(&s);}break;case 4:printf("請輸入你要頭刪的元素個數\n");scanf("%d", &x);for (i = 0; i < x; i++){PopFront(&s);}break;case 5:printf("請輸入要插入的位置以及插入的數據\n");scanf("%d%d", &pos, &x);Insert(&s, pos, x);break;case 6:printf("請輸入要刪除的位置\n");scanf("%d", &pos);Erase(&s, pos);break;case 7:printf("請輸入位置以及修改的數據\n");scanf("%d%d", &pos, &x);At(&s, pos, x);break;case 8:printf("請輸入需要查找的數據\n");scanf("%d", &x);int ret = Find(&s, x);if (ret != -1){printf("找到了下標為:>%d\n", ret);}elseprintf("找不到\n");break;case 9:Print(&s);printf("\n");break;default:break;}}Destory(&s);//使用完后銷毀return 0; }

?

以上就是本知識點的內容了。

求點個贊！！！！！！

總結

以上是生活随笔為你收集整理的数据结构C语言实现顺序表——增删查改操作实现详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。