🎉🎉🎉歡迎蒞臨我的博客空間，我是池央，一個對C++和數據結構懷有無限熱忱的探索者。🙌

🌸🌸🌸這里是我分享C/C++編程、數據結構應用的樂園?

🎈🎈🎈期待與你一同在編程的海洋中遨游，探索未知的技術奧秘💞

📝專欄指路:

📘【C++】專欄：深入解析C++的奧秘，分享編程技巧與實踐。

📘【數據結構】專欄：探索數據結構的魅力，助你提升編程能力。

前言

初步認識了數據結構后，我們一起來探索它的邏輯結構里面的線性結構吧。線性結構是一對一的關系。線性表在邏輯結構上是連續的，在物理結構上不一定是連續的。線性表中的順序表（本篇的主角）在物理結構上是連續的，而線性表中的鏈表在物理結構上卻是不連續的。

一、線性表

線性表是具有相同數據類型的n(n≥0)個數據元素的有限序列，其中n為表長，當n=0時線性表是一個空表。

幾個概念：

1.ai是線性表中的“第i個”元素線性表中的位序（位序從1開始，注意區分數組下標從0開始）

2.a1是表頭元素；an是表尾元素。

3.除第一個元素外，每個元素有且僅有一個直接前驅(前一個元素)；除最后一個元素外，每個元素有且僅有一個直接后繼（后一個元素）

二、順序表

正片開始！

1.概念

順序表——用順序存儲的方式實現線性表順序存儲。把邏輯上相鄰的元素存儲在物理位置上也相鄰的存儲單元中，元素之間的關系由存儲單元的鄰接關系來體現。順序表的底層是數組。

2.靜態順序表

順序表的空間大小固定

補充:為了簡化代碼，我們使用typedef 重命名自定義類型，typedef的優勢是什么?

在C或C++中，typedef 關鍵字用于為已存在的數據類型定義一個新名稱（別名）。這在需要簡化復雜的數據類型聲明，或者為特定的數據類型提供一個更有描述性的名稱時非常有用。

代碼如下:

typedef int SQLDataType;//順序表的數據類型
//靜態順序表
typedef struct SeqList
{SQLDataType arr[100];int size;//有效數據個數int capacity;//空間大小
}SL;

3.動態順序表

順序表的大小空間不固定，可根據需求改變。

當順序表存滿時，用realloc增容。

typedef int SQLDataType;//順序表的數據類型
//動態順序表
typedef struct SeqList
{SQLDataType* arr;int size;//有效數據個數int capacity;//空間大小
}SL;

補充:realloc擴容的規則是什么?

一次擴充一個空間 ，插入一個元素還不會造成空間浪費程序（執行效率低下）

一次擴容固定個大小的空間(10、100…)【小了造成頻繁擴容】【大了造成空間浪費】

最優解：成倍數的增加(1.5倍、2倍)，數據插入的越多擴容的大小越來越大

擴容后會自動把原有空間釋放掉

malloc,realloc,calloc三者區別是什么?

• malloc函數：用于動態分配指定字節數的內存空間，并返回一個指向它的指針。如果分配成功，則返回非空指針；如果內存空間不足，則返回NULL。需要注意的是，malloc分配的內存空間并未初始化，它們的值是未知的。
• calloc函數：也用于動態分配內存空間，與malloc有所不同。calloc在分配內存空間時，會將其初始化為0。它的參數是要分配的元素個數和每個元素的大小，而不是總的字節數。如果分配成功，則返回指向分配的內存的指針；如果失敗，則返回NULL。
• realloc函數：用于調整之前分配的內存空間大小。它接收一個指向已分配內存的指針和一個新的大小，然后嘗試調整內存塊的大小。如果成功，則返回指向新的內存塊的指針；如果失敗，則返回NULL，而原來的內存塊保持不變。

代碼示例

//是否需要申請空間
void SQLcapacity(SL* ps)
{if (ps->capacity == ps->size)//空間已滿，需要申請空間{//realloc增容，一般增加成原本空間大小的二或三倍int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SQLDataType* tmp = (SQLDataType*)realloc(ps->arr, newcapacity * sizeof(SQLDataType));if (tmp == NULL){perror("reacoll fail!");//空間申請失敗exit(1);//退出程序}ps->arr = tmp;ps->capacity = newcapacity;}
}

4.對順序表的操作

（1）初始化

void InitSql(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;
}

（2）尾插

void PushBackSql(SL* ps, SQLDataType x)
{assert(ps);//插入之前先看空間夠不夠SQLcapacity(ps);ps->arr[ps->size++] = x;//size是順序表尾部，后置++插入x后size加一
}

（3）頭插

//頭部插入
void PushHeadSql(SL* ps, SQLDataType x)
{assert(ps);//插入之前先看空間夠不夠SQLcapacity(ps);//讓原本的數據往后移一位for (int i = ps->size;i > 0;i--){ps->arr[i] = ps->arr[i - 1];//arr[1]=arr[0]讓arr[1]的位置放入原本arr[0]的數據}ps->arr[0] = x;ps->size++;
}

（4）查找

//查找指定數據
int FindPosSql(SL* ps, SQLDataType x)
{assert(ps);for (int i = 0;i < ps->size;i++){if (ps->arr[i] == x)return i;}return -1;
}

找到了返回下標，找不到則返回不存在的下標

（5）尾刪

//尾部刪除
void DelBackSql(SL* ps)
{assert(ps);assert(ps->size);//順序表為空時不能執行刪除操作ps->size--;
}

（6）頭刪

//頭部刪除
void DelHeadSql(SL* ps)
{assert(ps);assert(ps->size);//順序表為空時不能執行刪除操作//順序表存放數據整體往前挪一位for (int i = 0;i < (ps->size) - 1;i++){//arr[0]的位置放原本arr[1]的數據，最后是ps->arr[size-2]=ps->arr[size-1]ps->arr[i] = ps->arr[i + 1];//arr[0]的位置放原本arr[1]的數據，最后是ps->arr[size-2]=ps->arr[size-1]}ps->size--;
}

（7）在指定位置之前插入數據

//指定位置前插入
void AddPosSql(SL* ps, int pos, SQLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);//先看看空間夠不夠SQLcapacity(ps);//pos位置上的數和他后面的數整體往后挪一位for (int i = ps->size;i > pos;i--){ps->arr[i] = ps->arr[i - 1];//結束arr[pos+1]=arr[pos];}ps->arr[pos] = x;ps->size++;
}

（8）在指定位置刪除數據

//刪除指定位置數據
void DelPosSql(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];//arr[size-2]=arr[size-1]}ps->size--;
}

（9）銷毀

//銷毀順序表
void DestroySql(SL* ps)
{if (ps->arr)//不是空表才需要釋放{free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}

順序表小結

下一篇預告：線性表之單鏈表

持續更新中...

敬請期待