網站首頁 編程語言 正文
線性表
線性表(linear list)是n個具有相同特性的數據元素的有限序列。線性表是一種在實際中廣泛使用的數據結構,常見的線性表有:順序表、鏈表、棧、隊列、字符串等。
線性表在邏輯上是線性結構,也就是連續的一條直線。但在物理結構上并不一定是連續的,線性表在物理上存儲時,通常以數組和鏈式的形式存儲。
順序表
順序表是用一段物理連續地址的存儲單元依次存儲數據元素的線性結構,一般情況采用數組存儲。在數組上面完成數據的增刪查改。
一般情況下,順序表可以分為一下兩種:
1.靜態順序表:使用定長數組存儲元素。
2.動態順序表:使用動態開辟的數組存儲。
順序表接口實現
靜態順序表只適用于確定知道需要存儲多少數據的場景。靜態順序表不夠靈活。所以我們基本都使用動態順序表,根據需要空間的多少來分配大小,所有下面我們實現動態順序表。
先定義一個結構體:
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a;
int size; //存儲數據個數
int capacity; //容量空間大小
}SeqList;
1.順序表初始化
void SeqListInit(SeqList* ps);
void SeqListInit(SeqList* ps)
{
assert(ps); //檢查指針的有效性
ps->a = NULL; //不知道開多大的空間,就先賦值NULL
ps->capacity = ps->size = 0;
}
我們在給ps->a開辟空間的時候,還可以以如下方式開辟,這樣甚至更簡單一點(開辟完空間后需要檢查空間的有效性),但這兩種都可以。
STDataType*tmp=(STDataType*)malloc(sizeof(SeqList)*2);
2.順序表空間增容
//檢查空間,如果滿了,就進行增容
void SeqListCheckCapacity(SeqList* ps);
void SeqListCheckCapacity(SeqList* ps)
{
assert(ps);
if (ps->capacity == ps->size)
{
size_t newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDataType* tmp = realloc(ps->a, sizeof(SLDataType) * newcapacity);
if (tmp == NULL)
{
printf("CheckCapacity::%s\n", strerror(errno));//若空間開辟失敗,則打印開辟失敗的原因
exit(-1);//若空間開辟失敗,則直接終止程序
}
else
{
ps->a = tmp;
ps->capacity = newcapacity;
}
}
}
1.此處realloc空間,如果容量不夠,我們就將容量擴展為原來的兩倍,但是我們一開始初始化的空間有可能是0,所以我們應該把這種情況考慮進去。
2.realloc空間可能因為一些原因而失敗,所以要對開辟的空間進行檢查,即判斷申請的空間是否為空(NULL)。
3.順序表打印
//順序表打印
void SeqListPrint(SeqList* ps);
void SeqListPrint(SeqList* ps)
{
assert(ps);
for (int i = 0;i < ps->size;++i)//依次遍歷,打印出每一個信息
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
4.尾插數據
//順序表尾插
void SeqListPushBack(SeqList* ps, SLDataType x);
void SeqListPushBack(SeqList* ps, SLDataType x)
{
assert(ps);
SeqListCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
5.尾刪數據
//順序表尾刪
void SeqListPopBack(SeqList* ps);
void SeqListPopBack(SeqList* ps)
{
assert(ps);
if (ps->size > 0)//防止尾刪將數據刪完了,size出現負數
{
ps->size--;
}
}
注意:size減的時候一定要加條件限制,防止下標出現負數。
6.頭插數據
//順序表頭插
void SeqListPushFront(SeqList* ps, SLDataType x);
void SeqListPushFront(SeqList* 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++;
}
7.頭刪數據
//順序表頭刪
void SeqListPopFront(SeqList* ps);
void SeqListPopFront(SeqList* ps)
{
assert(ps);
//依次挪動數據覆蓋刪除
if (ps->size > 0)//確保有數據可刪除,防止下標出現負數
{
int begin = 1;
while (begin < ps->size)
{
ps->a[begin - 1] = ps->a[begin];
++begin;
}
ps->size--;
}
}
注意:頭刪一定要保證下標大于0,不然刪掉一個下標減一下,當下標減為負數的時候,程序就會出錯。頭刪的時候數據從前向后數據依次向前覆蓋一位。
8.在pos下標處插入數據
//順序表在pos位置插入數據
void SeqListInsert(SeqList* ps, size_t pos, SLDataType x);
void SeqListInsert(SeqList* ps, size_t pos, SLDataType x)
{
assert(ps);
if (pos > ps->size)
{
printf("pos越界\n");
return;
}
SeqListCheckCapacity(ps);
size_t end = ps->size;
while (end > pos)
{
ps->a[end] = ps->a[end - 1];
--end;
}
ps->a[pos] = x;
ps->size++;
}
這里需要特別注意一下下標的問題,如下圖:
在這里循環有兩種寫法,一種如上,還有一種就是下邊這種。
int end =ps->size-1;
while(end>=(int)pos)
{
ps->a[end+1]=ps->a[end];
--end;
}
注意:對比以上兩種寫法,我們注意到了pos和end的類型。因為坐標不可能為負數,所以pos為size_t類型。對于第二種情況:int end=ps->size-1時,循環執行到最后end的值會變為-1,但pos的類型為size_t,所以當end與pos比較的時候,會發生整形提升,使無符號的end整形提升為有符號的數字和pos比較,所以while條件成立,會繼續循環,導致越界訪問內存。對于這種我們的解決方法是將pos強制轉換為int類型,如上訴代碼。
對于第一種情況: int end=ps->size,循環執行到最后end的值為0,為無符號數,因此剛好完美的進行了移動覆蓋,不會出現越界訪問的情況。所以我們推薦使用第一種方法。
9.刪除pos下標處數據
//順序表刪除pos位置的數據
void SeqListErase(SeqList* ps, size_t pos);
void SeqListErase(SeqList* ps, size_t pos)
{
assert(ps);
if (pos >= ps->size)
{
printf("pos越界\n");
return;
}
size_t begin = pos + 1;
while (begin < ps->size)
{
ps->a[begin - 1] = ps->a[begin];
++begin;
}
ps->size--;
}
10.數據查找
依次遍歷數據查找,若找到了對應的數據,則返回它的下標。若找不到,則返回-1.
//順序表查找
int SeqListFind(SeqList* ps, SLDataType x);
int SeqListFind(SeqList* ps, SLDataType x)
{
assert(ps);
for (int i = 0;i < ps->size;++i)
{
if (ps->a[i] == x)
{
return i;
}
}
return -1;
}
11.順序表摧毀
當我們使用動態申請空間時,使用完后,一定要釋放動態開辟的內存。否則可能會造成內存泄漏。
//順序表銷毀
void SeqListDestroy(SeqList* ps);
void SeqListDestroy(SeqList* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->size = ps->capacity = 0;
}
原文鏈接:https://blog.csdn.net/qq_61939403/article/details/123537631
相關推薦
- 2022-12-07 React元素與組件的區別示例詳解_React
- 2022-09-22 Apriori算法的實現
- 2023-07-16 uniapp 調用拍照組件
- 2022-10-17 C++右值引用與move和forward函數的使用詳解_C 語言
- 2022-07-15 go?GCM?gin中間件的加密解密文件流處理_Golang
- 2023-12-17 eclipse中設置自動補齊代碼
- 2022-10-12 Xshell7遠程連接失敗(connection?failed)的問題解決_Linux
- 2022-06-28 python遞歸實現鏈表快速倒轉_python
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版(
- Linux 中運行的top命令 怎么退出?
- MySQL 中decimal 的用法? 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符,流程控制 Flo
- 1. Int 和Integer 的區別,Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤:Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密?
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串(SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列,發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支