目錄

1.什么是順序表

2.動態(tài)順序表實現(xiàn)

2.1動態(tài)順序表結(jié)構(gòu)體

2.2初始化

2.3打印驗證函數(shù)

2.4判斷是否擴容，按需擴容

2.5頭插/尾插

?2.6頭刪/尾刪

?2.7指定位置插入數(shù)據(jù)/指定位置刪除數(shù)據(jù)

3.動態(tài)順序表代碼

---

1.什么是順序表

線性表是n個具有相同特性的數(shù)據(jù)元素的有限序列。線性表是?種在實際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表：順序表、鏈表、棧、隊列、字符串等，在邏輯結(jié)構(gòu)上呈線性，在物理結(jié)構(gòu)（存儲）上不一定線性。順序表是線性表的一種，在邏輯結(jié)構(gòu)上呈線性，在物理結(jié)構(gòu)（存儲）也是線性的，因為底層結(jié)構(gòu)是數(shù)組，加上增刪查改等功能封裝在一起形成順序表，順序表分成靜態(tài)順序表和動態(tài)順序表。

2.動態(tài)順序表實現(xiàn)

2.1動態(tài)順序表結(jié)構(gòu)體

?SLDataType是類型重命名，便于替換類型；

size是有效數(shù)據(jù)個數(shù)，也是一種重要下標，即為最后一個有效數(shù)據(jù)的下一個下標；

capacity是arr空間容量；

2.2初始化/銷毀

?要初始化后才能后續(xù)使用該結(jié)構(gòu)體，用完后進行銷毀；

2.3打印驗證函數(shù)

?便于后續(xù)驗證直接使用；

2.4判斷是否擴容，按需擴容

?當空間容量不夠時（即空間容量與有效數(shù)據(jù)值相等），就需要擴容，起始空間容量擴容4，后面的擴容按原空間容量的2倍或者1.5倍的原則擴容；

使用中間指針判斷是否擴容成功，失敗退出程序，成功就將原指針更新為中間指針，并更新擴容后的空間容量；

2.5頭插/尾插

?頭插分為三種情況：

?注意后移形式，避免覆蓋到后續(xù)后移數(shù)據(jù)；

尾插分三種情況：

?2.6頭刪/尾刪

?頭刪分兩種情況：

?

?尾刪：

?2.7指定位置插入數(shù)據(jù)/指定位置刪除數(shù)據(jù)

pos是插入下標:

?

?

?2.8查找數(shù)據(jù)

?2.9改變指定下標的數(shù)據(jù)

3.動態(tài)順序表代碼

具體代碼如下：

//頭文件 SeqList.h#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;//便于類型替換//動態(tài)順序表
typedef struct SeqList
{SLDataType* arr;//存儲數(shù)據(jù)的底層結(jié)構(gòu)int size;     //有效數(shù)據(jù)個數(shù)int capacity; //空間容量
}SL;靜態(tài)順序表
//#define N 10
//typedef struct SeqList
//{
//	SLDataType arr[N];//定長數(shù)組
//	int size;       //有效數(shù)據(jù)個數(shù)
//}SL;//初始化和銷毀
void SLInit(SL* ps);
void SLDestory(SL* ps);
//打印驗證
void SLPrint(SL* ps);//順序表頭插
void SLPushFront(SL* ps, SLDataType x);
//順序表尾插
void SLPushBack(SL* ps, SLDataType x);//判斷是否需要擴容，需要進行擴容
void SLCheckCapacity(SL* ps);//順序表的頭刪
void SLPopFront(SL* ps);
//順序表的尾刪
void SLPopBack(SL* ps);//指定位置插入數(shù)據(jù)，后面數(shù)據(jù)存在就后移
void SLInsert(SL* ps, int pos, SLDataType x);
//刪除指定位置數(shù)據(jù),后面數(shù)據(jù)存在就前移
void SLErase(SL* ps, int pos);//改變指定下標的數(shù)據(jù)
void SLChange(SL* ps, int pos, SLDataType x);//查找
int SLFind(SL* ps, SLDataType x);

//SeqList.c#define _CRT_SECURE_NO_WARNINGS 1#include "SeqList.h"//初始化和銷毀
void SLInit(SL* ps)
{ps->arr = NULL;              //初始化為空指針 ps->size = ps->capacity = 0; //初始化什么都沒有，所以為0
}
void SLDestory(SL* ps)
{assert(ps);free(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;
}
//打印驗證
void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}//判斷是否需要擴容，需要進行擴容
void SLCheckCapacity(SL* ps)
{if (ps->size == ps->capacity)//有效數(shù)據(jù)個數(shù)與空間容量相等的時候，要插入需要先擴容{int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//起始空間容量為0，則第一次擴容4個，擴容原則擴容原空間容量的2倍或1.5倍SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//中間指針接收擴容后的地址if (tmp == NULL)//擴容失敗{perror("Realloc Fail!");exit(1);//意外退出}ps->arr = tmp;//擴容成功ps->capacity = newCapacity;//更新擴容后的空間容量}
}//順序表頭插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);//或者if(ps == NULL) { return; }//若空間不夠，需要擴容SLCheckCapacity(ps);for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;ps->size++;
}
//順序表尾插
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//若空間不夠，需要擴容SLCheckCapacity(ps);ps->arr[ps->size] = x;ps->size++;
}//順序表的頭刪
void SLPopFront(SL* ps)
{assert(ps);assert(ps->size);//順序表為空不能再刪了for (int i = 0; i < ps->size - 1; i++)//向前覆蓋{ps->arr[i] = ps->arr[i + 1];}ps->size--;//有效數(shù)據(jù)減1
}
//順序表的尾刪
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size);//順序表為空不能再刪了ps->size--;//直接減去最后一位的有效數(shù)據(jù)
}//指定位置插入數(shù)據(jù)，后面數(shù)據(jù)存在就后移
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}
//刪除指定位置數(shù)據(jù),后面數(shù)據(jù)存在就前移
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}//改變指定下標的數(shù)據(jù)
void SLChange(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos < ps->size);ps->arr[pos] = x;
}//查找
int SLFind(SL* ps, SLDataType x)
{for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){return i;}}return -1;
}

//測試，project.c#define _CRT_SECURE_NO_WARNINGS 1#include "SeqList.h"void test()
{SL ps;SLInit(&ps);SLPushFront(&ps, 5);SLPushFront(&ps, 4);SLPushFront(&ps, 3);SLPushFront(&ps, 2);SLPushFront(&ps, 1);SLPrint(&ps);SLPushBack(&ps, 6);SLPushBack(&ps, 7);SLPushBack(&ps, 8);SLPushBack(&ps, 9);SLPushBack(&ps, 10);SLPrint(&ps);SLPopFront(&ps);SLPopFront(&ps);SLPrint(&ps);SLPopBack(&ps);SLPopBack(&ps);SLPrint(&ps);SLInsert(&ps, 0, 1);SLInsert(&ps, 1, 2);SLInsert(&ps, 8, 9);SLInsert(&ps, 9, 10);SLPrint(&ps);SLErase(&ps, 4);SLErase(&ps, 7);SLPrint(&ps);SLInsert(&ps, 4, 5);SLInsert(&ps, 7, 9);SLChange(&ps, 0, 10);SLChange(&ps, 1, 11);SLPrint(&ps);int ret = SLFind(&ps, 3);if (ret != -1){printf("找到了，在下標為%d的位置\n", ret);}else{printf("不存在數(shù)據(jù)，查找失敗\n");}SLDestory(&ps);
}int main()
{test();return 0;
}