線性表

在數據元素的非空有限集中，（1）存在唯一的一個被稱做“第一個”的數據元素；（2）存在唯一的一個被稱做“最后一個”的數據元素；（3）除第一個之外，集合中的每個數據元素均只有一個前驅；（4）除最后一個之外，集合中每個數據元素均只有一個后繼

線性表的順序實現

線性表的順序表示指的是用一組地址連續的存儲單元依次存儲線性表的數據元素。

結點結構

#define SEQLIST_INIT_SIZE 8typedef struct SeqList {ElemType *base; // 線性表首地址int capacity; // 開辟的內存空間int size; // 有效存儲
} SeqList;

結點初始化

開辟出一段空間（給定空間大小）

void InitSeqList(SeqList *list) {list->base = (ElemType *) malloc(sizeof(ElemType) * SEQLIST_INIT_SIZE);//開辟空間assert(list->base != NULL);list->capacity = SEQLIST_INIT_SIZE;list->size = 0;
}

①malloc動態內存分配函數，用于申請一塊連續的指定大小的內存塊區域以ElementType *類型返回分配的內存區域地址：格式：指針名=(指針類型*）malloc（sizeof（指針類型）*數據數量）

②如果表達式的結果為“假”，assert()會打印出斷言失敗的信息Assertion failed:...，并調用abort()函數終止程序的執行Process finished with exit code 3；如果表達式的結果為“真”，assert()就什么也不做，程序繼續往后執行

增配空間Inc

1.重新開辟內存空間，并判斷是否增配空間成功，失敗則增配失敗返回false

2.更新結點線性表首地址和開辟的內存空間

3.之后每次插入數據操作前，添加判斷條件：分配給表內存是否足夠。不夠則進行增配空間，增配空間失敗時，才是真正的內存不足

#define INC_SIZE 3bool Inc(SeqList *list) {//對已有的空間進行分配，原來表開辟內存8，進行重新分配，即開辟8+3內存ElemType *newbase = (ElemType *) realloc(list->base, sizeof(ElemType) * (list->capacity + INC_SIZE));if (newbase == NULL) {printf("增配空間失敗，內存不足\n");return false;}list->base = newbase;list->capacity += INC_SIZE;return true;
}

①realloc函數指向在堆區重新開辟的內存塊的起始地址:realloc(先前開辟的內存塊的指針--也就是malloc之前申請的那塊內存空間，即需要調整大小的內存空間,新開辟的那塊內存空間的字節數)，返回值為調整之后的內存的起始地址

打印順序表show_list

void show_list(SeqList *list) {for (int i = 0; i < list->size; i++) {printf("%d", list->base[i]);}printf("\n");
}

線性表長度length

int length(SeqList *list) {return list->size;
}

尾部插入push_back

插入6 7 9后順序表中數據順序為：6 7 9

1.判斷有效存儲是否小于開辟的內存空間，即判斷開辟的空間是否已滿，滿了不能插入數據

2.通過下標賦值，即插入數據

3.更新順序表有效存儲長度

void push_back(SeqList *list, ElemType x) {if (list->size >= list->capacity && !Inc(list)) {printf("順序表空間已滿，%d不能尾部插入數據\n", x);return;}list->base[list->size] = x;list->size++;
}

頭部插入push_front

插入6 9 1后順序表中數據順序為：1 9 6

1.判斷有效存儲是否小于開辟的內存空間，即判斷開辟的空間是否已滿，滿了不能插入數據

2.size-1即表中最后一個數據的下標，從最后一個數據開始依次向后移動

3.賦值到下標為0的地址，即插入數據

4.更新順序表有效存儲長度

void push_front(SeqList *list, ElemType x) {if (list->size >= list->capacity && !Inc(list)) {printf("順序表空間已滿，%d不能頭部插入數據\n", x);return;}for (int i = list->size; i > 0; i--) {list->base[i] = list->base[i - 1];}list->base[0] = x;list->size++;
}

尾部刪除pop_back

有順序表1 6 9進行尾部刪除后：1 6

1.判斷size是否為0，即表是否為空，空表不能刪除數據

2.有效長度減1

void pop_back(SeqList *list) {if (list->size == 0) {printf("順序表空間已空，不能尾部刪除數據\n");return;}list->size--;
}

頭部刪除pop_front

有順序表5 6 0進行頭部刪除后：6 0

1.判斷size是否為0，即表是否為空，空表不能刪除數據

2.從第二個數據開始，依次往前移動

3.有效長度減1

void pop_front(SeqList *list) {if (list->size == 0) {printf("順序表空間已空，不能頭部刪除數據\n");return;}for (int i = 0; i < list->size - 1; i++) {list->base[i] = list->base[i + 1];}list->size--;
}

按位置插入insert_pos

在順序表5 3 0下標為2的位置插入數據7為：5 3 7 0

1.判斷pos是否正確并小于有效存儲長度，即判斷插入位置是否合法，位置非法不能插入數據

2.判斷有效存儲是否小于開辟的內存空間，即判斷開辟的空間是否已滿，滿了不能插入數據

3.從最后一個數據開始依次向后移動，直到要插入數據的位置移動結束

4.通過下標賦值，即插入數據

5.更新順序表有效存儲長度

void insert_pos(SeqList *list, int pos, ElemType x) {if (pos < 0 || pos > list->size) {printf("插入數據的位置非法，不能插入數據\n");}if (list->size >= list->capacity && !Inc(list)) {printf("順序表空間已滿，%d不能按位置插入數據\n", x);return;}for (int i = list->size; i > pos; i--) {list->base[i] = list->base[i - 1];}list->base[pos] = x;list->size++;
}

特殊情況：當要插入數據的位置==有效存儲長度時，即尾部插入時，不影響效率[特別注意]

按值查找find

（第一個符合條件的）

1.從順序表第一個數據開始向后遍歷

2.每次遍歷判斷該數據是否是要查找的數據，查找成功返回當前下標

3.遍歷結束，即沒查到數據，返回-1

int find(SeqList *list, ElemType key) {for (int i = 0; i < list->size; i++) {if (list->base[i] == key)return i;}return -1;
}

按位置刪除delete_pos

順序表5 3 0刪除位置為1的數據后：5 0

1.判斷pos是否正確并小于有效存儲長度，即判斷刪除位置是否合法，位置非法不能刪除數據

2.從要刪除的位置開始，依次將后一個數據前移

3.更新順序表有效存儲長度

void delete_pos(SeqList *list, int pos) {if (pos < 0 || pos >= list->size)printf("刪除數據的位置非法，不能刪除數據\n");for (int i = pos; i < list->size - 1; i++) {list->base[i] = list->base[i + 1];}list->size--;
}

按值刪除delete_val

順序表5 3 0刪除值為0的數據后：5 3

1.判斷要刪除的數據是否存在，即按值查找，存在得到查找到的數據下標，不存在得到-1

2.判斷返回值是否是-1，是則數據不存在無法刪除，否則按位置刪除

void delete_val(SeqList *list, ElemType key) {int pos = find(list, key);if (pos == -1) {printf("要刪除的數據不存在\n");return;}delete_pos(list, pos);
}

排序sort(冒泡；升序)

順序表5 3 0 1 9 4排序后：0 1 3 4 5 9

1.兩層遍歷，依次比較兩個數據，前面數據大于后面數據則交換

void sort(SeqList *list) {for (int i = 0; i < list->size; i++) {for (int j = 0; j < list->size - i - 1; j++) {if (list->base[j] > list->base[j + 1]) {ElemType tmp = list->base[j];list->base[j] = list->base[j + 1];list->base[j + 1] = tmp;}}}
}

逆置resver

順序表5 3 0 1 9 4逆置后：4 9 1 0 3 5

1.判斷順序表長度是否可進行逆置操作操作，長度為1或0時不需要

2.設置兩個整型指針low和high，分別指向第一個數據和最后一個數據，low指針后移，high指針前移，每次將兩個指針指向的數據對換，直到low指針大于或等于high指針為止

void resver(SeqList *list) {if (list->size == 0 || list->size == 1)return;int low = 0;int high = list->size - 1;ElemType tmp;while (low < high) {tmp = list->base[low];list->base[low] = list->base[high];list->base[high] = tmp;low++;high--;}
}

清除表clear

void clear(SeqList *list) {list->size = 0;
}

銷毀表destroy

void destroy(SeqList *list) {free(list->base);list->base = NULL;list->capacity = 0;list->size = 0;
}

①free函數必須和malloc函數同時使用

②free只能釋放由malloc動態分配在堆內存的內存，直接在主函數定義結構體變量是分配在棧內存里的內存，所以釋放不了

合并表merge

表A1 2 5 6，表B3 4 7 9，合并后：1 2 3 4 5 6 9

1.設置ia、ib、ic三個整型指針，分別用來遍歷表A、B、合并表，開辟存放合并表的內存空間，并判斷是否開辟成功

2.同時遍歷表A和表B，依次判斷指針指向的A、B表的數據大小，將較小的數據放入合并表，每存入一個數據，合并表和被存入的數據所在表的整型指針都向后移一次，直到A、B有一個表遍歷完

3.如果其中一個表遍歷結束，另一個表還有遍歷完的數據，則直接將剩余數據依次存入合并表

4.更新合并表有效存儲長度

void merge(SeqList *lt, SeqList *la, SeqList *lb) {lt->capacity = la->size + la->size;lt->base = (ElemType *) malloc(sizeof(ElemType)*lt->capacity);assert(lt->base != NULL);int ia = 0;int ib = 0;int ic = 0;while(ia<la->size && ib<lb->size){if(la->base[ia] < lb->base[ib])lt->base[ic++] = la->base[ia++];elselt->base[ic++] = lb->base[ib++];}while(ia < la->size){lt->base[ic++] = la->base[ia++];}while(ib < lb->size){lt->base[ic++] = lb->base[ib++];}lt->size = la->size + lb->size;
}