文章目錄
- 0. 線性表概念
- 1. 順序表概念及結構
- 2. 順序表的增刪查改
- 2.0 初始化、銷毀、列印基本介面
- 2.0.1 初始化
- 2.0.2 列印
- 2.0.3 銷毀
- 2.1 尾插尾刪
- 2.1.1 擴容介面
- 2.1.2 尾插
- 2.1.3 尾刪
- 2.2 頭插頭刪
- 2.2.1 頭插
- 2.2.2 頭刪
- 2.3 指定位置插入、洗掉指定位置資料、查找
- 2.3.1 查找
- 2.3.2 指定位置插入
- 2.3.3 洗掉指定位置資料
- 2.3.4 復用
- 3. 順序表的問題及思考
- 附:源代碼
- `SeqList.h`
- `SeqList.c`
- `test.c`
0. 線性表概念
線性表(linear list)是n個具有相同特性的資料元素的有限序列, 線性表是一種在實際中廣泛使用的資料結構,常見的線性表:順序表、鏈表、堆疊、佇列、字串…
-
線性表在邏輯上是線性結構,也就說是連續的一條直線,
-
但是在物理結構上并不一定是連續的,線性表在物理上存盤時,通常以陣列(順序表)和鏈式結構(鏈表)的形式存盤,

1. 順序表概念及結構
🔑順序表就是陣列,在陣列的基礎上要求從頭開始,要求資料挨著挨著連續存盤,沒有跳躍間隔,
順序表一般可以分為:
- 靜態順序表:使用定長陣列存盤元素,
#define N 1000
typedef int SLDataType;
//靜態順序表
typedef struct SeqList
{
SLDataType data[N];
int size;//表示陣列中存盤多少個資料
}SL;
靜態順序表的缺點:
??1. 如果滿了,就無法再插入,
??2. 陣列大小給多少合適?這個很難確定,N給小了不夠用,N給大了浪費,
因此現實中我們基本都是使用動態順序表,動態分配記憶體空間,所以下面我們實作動態順序表,
- 動態順序表:使用動態開辟的陣列存盤,
typedef int SLDataType;
//動態順序表
typedef struct SeqList
{
SLDataType* a;
int size;//表示陣列中存盤多少個有效資料
int capacity;//陣列實際能存資料的容量
}SL;
2. 順序表的增刪查改
函式介面 —— SeqList.h
本文希望展現一套自然而然又理所當然的思路,都配了圖,建議復制所有函式介面自己寫自己調,感受會很好,至于完整代碼也附在后面了,
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//條件為真--沒事,條件為假--終止程式
typedef int SLDataType;
//動態順序表
typedef struct SeqList
{
SLDataType* a;
int size;//表示陣列中存盤多少個有效資料
int capacity;//陣列實際能存資料的容量
}SL;
//介面函式--命名風格跟著STL走,方便后續學習STL
void SeqListInit(SL* ps);
void SeqListPrint(SL* ps);
void SeqListCeckCapacity(SL* ps);
void SeqListDestroy(SL* ps);
//尾插
void SeqListPushBack(SL* ps, SLDataType x);
//尾刪
void SeqListPopBack(SL* ps);
//頭插
void SeqListPushFront(SL* ps, SLDataType x);
//頭刪
void SeqListPopFront(SL* ps);
//指定位置插入
void SeqListInsert(SL* ps,int pos,SLDataType x);
//洗掉指定位置資料
void SeqListErase(SL* ps,int pos);
//查找
int SeqListFind(SL* ps, SLDataType x);
//若找到--則回傳下標
//找不到--回傳-1
int SeqListFind(SL* ps, SLDataType x);
2.0 初始化、銷毀、列印基本介面
2.0.1 初始化
初始化很有必要,開始時,順序表中什么資料也沒有,甚至也還沒有為它動態申請一段空間,
因此,ps->a要置NULL,標識它是野指標,ps->size和ps->capacity都要置0,否則就是隨機值了,
void SeqListInit(SL* ps)
{
assert(ps);
ps->a = NULL;
ps->size = ps->capacity = 0;
}
注意:為什么傳的是這個順序表的地址?這是因為函式傳參,形參是實參的拷貝,形參的改變不會影響實參,
2.0.2 列印
我們要寫一點,就列印出來驗證一下正確性,就寫一個列印函式,遍歷即可很簡單,
void SeqListPrint(SL* ps)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
2.0.3 銷毀
現在我們寫的是動態順序表,那么malloc/realloc動態申請的空間,要記得釋放,否則會發生記憶體泄漏,
關于此,可以復習一下這篇文章 動態記憶體函式,我順便也復習了一下,發現有些東西用慣了之后,對于它們是怎么來的會有點淡忘,
void SeqListDestroy(SL* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->size = ps->capacity = 0;
}
2.1 尾插尾刪
2.1.1 擴容介面
🔑但凡插入資料就要考慮,空間夠不夠用是否需要增容的問題
void SeqListCeckCapacity(SL* ps)
{
assert(ps);
if (ps->size == ps->capacity)
{
//1.沒有空間 —— 申請空間
//2.空間不夠 —— 擴容
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity*sizeof(SLDataType));
if (tmp == NULL)
{
printf("擴容失敗\n");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
}
這里可能唯一要注意一下的,就是realloc函式,檔案中如是寫——

因此我們把 第一次申請空間 與 后期的調整空間 完美融合寫在一起了,同時處理了沒有空間和空間不夠兩種情況,
2.1.2 尾插

void SeqListPushBack(SL* ps, SLDataType x)
{
assert(ps);
SeqListCheckCapacity(ps);
ps->a[ps ->size] = x;
ps->size++;
}
2.1.3 尾刪
🔑 洗掉資料就要考慮是不是刪空了,沒的刪了,卻還在呼叫這個函式,那就不對了
推薦直接斷言暴力終止掉程式,畢竟,就是你用錯了,

void SeqListPopBack(SL* ps)
{
assert(ps);
assert(ps->size);//斷言暴力終止掉程式,若出現刪多了的情況,就蹦出視窗終止程式
ps->size--;
}
斷言效果 ——

2.2 頭插頭刪
2.2.1 頭插
- 插入資料依然要考慮擴容問題
- 無論是頭插還是頭刪,為了保證順序表從開始位置連續,都需要挪動資料 —— 想好是從尾 還是 從頭 開始挪動,保證資料不會被覆寫丟失,
- 畫好圖,時刻注意邊界

void SeqListPushFront(SL* ps, SLDataType x)
{
assert(ps);
SeqListCheckCapacity(ps);
int end = ps->size - 1;
while (end >= 0)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[0] = x;
ps->size++;
}
2.2.2 頭刪
- 洗掉資料依然要考慮刪空時,越界訪問的情況
- 畫圖注意邊界

void SeqListPushFront(SL* ps, SLDataType x)
{
assert(ps);
SeqListCheckCapacity(ps);
int end = ps->size - 1;
while (end >= 0)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[0] = x;
ps->size++;
}
2.3 指定位置插入、洗掉指定位置資料、查找
查找常和指定位置插入、指定位置洗掉搭配使用,
2.3.1 查找
//查找--找到了則回傳x位置下標,沒有找到則回傳-1
int SeqListFind(SL* ps, SLDataType x)
{
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
{
return i;
}
}
return -1;
}
2.3.2 指定位置插入
與頭插完全類似

void SeqListInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
SeqListCheckCapacity(ps);
int end = ps->size - 1;
while (end >= pos)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[pos] = x;
ps->size++;
}
2.3.3 洗掉指定位置資料
與頭刪完全類似

void SeqListErase(SL* ps, int pos)
{
assert(ps);
assert(ps->size);
int start = pos + 1;
while (start < ps->size)
{
ps->a[start - 1] = ps->a[start];
start++;
}
ps->size--;
}
2.3.4 復用
有了指定位置插入和指定位置洗掉,就可以復用這些介面,完成頭插頭刪尾插尾刪 ——
//尾插
void SeqListPushBack(SL* ps, SLDataType x)
{
SeqListInsert(ps, ps->size, x);
}
//尾刪
void SeqListPopBack(SL* ps)
{
SeqListErase(ps, ps->size - 1);
}
//頭插
void SeqListPushFront(SL* ps, SLDataType x)
{
SeqListInsert(ps, 0, x);
}
//頭刪
void SeqListPopFront(SL* ps)
{
SeqListErase(ps, 0);
}
分分鐘搞定,
3. 順序表的問題及思考
-
順序表優點 ——
支持隨機訪問,方便做查找,
-
順序表缺陷 ——
- 空間不夠需要增容,增容是要付出代價的,
- 為了避免頻繁擴容,我們基本都是按倍數去擴(擴2倍),可能會造成一定的空間浪費,
- 順序表要求資料從開始位置保持連續,那么中間和頭部的插入,就需要挪動資料,時間復雜度為O(N),效率不高,
針對順序表的缺陷,引出了下一節 —— 鏈表
未完待續@邊通書
附:源代碼
SeqList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//條件為真-沒事,條件為假-終止程式
typedef int SLDataType;
//動態順序表
typedef struct SeqList
{
SLDataType* a;
int size; //表示陣列中存盤多少個資料
int capacity; //陣列實際能存資料的容量
}SL;
//介面函式--命名風格跟著STL走,方便后續學習STL
void SeqListInit(SL* ps);
void SeqListPrint(SL* ps);
void SeqListDestroy(SL* ps);
void SeqListCheckCapacity(SL* ps);
//尾插
void SeqListPushBack(SL* ps, SLDataType x);
//尾刪
void SeqListPopBack(SL* ps);
//頭插
void SeqListPushFront(SL* ps, SLDataType x);
//頭刪
void SeqListPopFront(SL* ps);
//指定位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x);
//洗掉指定位置的資料
void SeqListErase(SL* ps, int pos);
//查找--找到了則回傳x位置下標,沒有找到則回傳-1
int SeqListFind(SL* ps, SLDataType x);
SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
void SeqListInit(SL* ps)
{
assert(ps);
ps->a = NULL;
ps->size = ps->capacity = 0;
}
void SeqListPrint(SL* ps)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
void SeqListDestroy(SL* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
}
void SeqListCheckCapacity(SL* ps)
{
assert(ps);
if (ps->size == ps->capacity)
{
int newcapacity = (ps->capacity == 0) ? 4 : ps->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(ps->a,sizeof(SLDataType)*newcapacity);
if (tmp == NULL)
{
printf("realloc failed\n");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
}
void SeqListPushBack(SL* ps, SLDataType x)
{
SeqListInsert(ps, ps->size, x);
//assert(ps);
//SeqListCheckCapacity(ps);
//ps->a[ps->size] = x;
//ps->size++;
}
void SeqListPopBack(SL* ps)
{
SeqListErase(ps, ps->size - 1);
//assert(ps);
//assert(ps->size);
//ps->size--;
}
void SeqListPushFront(SL* ps, SLDataType x)
{
SeqListInsert(ps, 0, x);
/*assert(ps);
SeqListCheckCapacity(ps);
int end = ps->size - 1;
while (end >= 0)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[0] = x;
ps->size++;*/
}
void SeqListPopFront(SL* ps)
{
SeqListErase(ps, 0);
//assert(ps);
//assert(ps->size);
//int start = 1;
//while (start < ps->size)
//{
// ps->a[start - 1] = ps->a[start];
// start++;
//}
//ps->size--;
}
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
SeqListCheckCapacity(ps);
int end = ps->size - 1;
while (end >= pos)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[pos] = x;
ps->size++;
}
void SeqListErase(SL* ps, int pos)
{
assert(ps);
assert(ps->size);
int start = pos + 1;
while (start < ps->size )
{
ps->a[start - 1] = ps->a[start];
start++;
}
ps->size--;
}
int SeqListFind(SL* ps, SLDataType x)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
return i;
}
return -1;
}
test.c
關于測驗檔案,就是隨寫隨測,把每種情況都測到,這里主要是增容呀,刪空時的越界訪問呀,還有就是基本的邏輯,把我自己的貼出來
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
//測驗尾插尾刪
void TestSeqList1()
{
SL sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
SeqListPrint(&sl);
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPopBack(&sl);
//SeqListPopBack(&sl);
//SeqListPopBack(&sl);
SeqListPrint(&sl);
SeqListDestroy(&sl);
}
//測驗頭插頭刪
void TestSeqList2()
{
SL sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
SeqListPrint(&sl);
SeqListPushFront(&sl, 0);
SeqListPushFront(&sl, -1);
SeqListPushFront(&sl, -2);
SeqListPrint(&sl);
SeqListPopFront(&sl);
SeqListPopFront(&sl);
SeqListPrint(&sl);
printf("%d\n", SeqListFind(&sl,3));
SeqListDestroy(&sl);
}
//測驗指定位置的插入洗掉
void TestSeqList3()
{
SL sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
SeqListInsert(&sl, 2, 30);
SeqListInsert(&sl, 0, 0);
SeqListInsert(&sl, sl.size, 80);
SeqListPrint(&sl);
//配合使用
int pos = SeqListFind(&sl, 4);
if (pos != -1)
{
SeqListInsert(&sl, pos, 40);
}
SeqListPrint(&sl);
SeqListDestroy(&sl);
}
//復用SeqListInsert測驗頭插尾插
void TestSeqList4()
{
SL sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
SeqListPushFront(&sl, 1);
SeqListPushFront(&sl, 2);
SeqListPushFront(&sl, 3);
SeqListPushFront(&sl, 4);
SeqListPushFront(&sl, 5);
SeqListPrint(&sl);
SeqListPopFront(&sl);
SeqListPopFront(&sl);
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPrint(&sl);
//假如我要刪3
int pos = SeqListFind(&sl, 3);
if (pos != -1)
{
SeqListErase(&sl, pos);
}
SeqListPrint(&sl);
SeqListDestroy(&sl);
}
int main()
{
//TestSeqList1();
//TestSeqList2();
//TestSeqList3();
TestSeqList4();
return 0;
}
轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/403968.html
標籤:其他
上一篇:【初階】帶你看懂二叉樹(附圖解)
