網站首頁 編程語言 正文
1.線性表
線性表（linear list）是n個具有相同特性的數據元素的有限序列。 線性表是一種在實際中廣泛使用的數據結構，常見的線性表：順序表、鏈表、棧、隊列、字符串…
線性表在邏輯上是線性結構，也就說是連續的一條直線。但是在物理結構上并不一定是連續的，線性表在物理上存儲時，通常以數組和鏈式結構的形式存儲
2.順序表
2.1概念及結構
順序表是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構，一般情況下采用數組存儲。在數組上完成數據的增刪查改。
順序表一般可以分為：
靜態順序表：使用定長數組存儲元素。
動態順序表：使用動態開辟的數組存儲
2.2 接口實現
靜態順序表只適用于確定知道需要存多少數據的場景。靜態順序表的定長數組導致N定大了，空間開多了浪費，開少了不夠用。所以現實中基本都是使用動態順序表，根據需要動態的分配空間大小，所以下面我們實現動態順序表。
#pragma once
#include<stdio.h>
#include<assert.h>
typedef int SLDataType;
typedef struct SeqList
{
int* a;
int size; //存儲數據個數
int capacity;//存儲空間大小
}SeqList;
void SeqListInit(SeqList* psl);//初始化
void SeqListDestroy(SeqList* psl);//銷毀
void SeqListPrint(SeqList* psl);//打印
void SeqListCheckCapacity(SeqList* psl);//檢查容量
int SeqListFind(SeqList* psl, SLDataType x);//查找
//時間復雜度是O（1）
void SeqListPushBack(SeqList* psl, SLDataType x);//尾插
void SeqListPopBack(SeqList* psl);//尾刪
//時間復雜度是O（N）
void SeqListPushFront(SeqList* psl, SLDataType x);//頭插
void SeqListPopFront(SeqList* psl);//頭刪
//時間復雜度是O（N）
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);//在pos位置插入
void SeqListErase(SeqList* psl, size_t pos);//在pos位置刪除
2.2.1初始化
就是將元素分別初始化。
//初始化
void SeqListInit(SeqList* psl)
{
assert(psl);
psl->a = NULL;
psl->size = 0;
psl->capacity = 0;
}
2.2.2 檢查容量
初始化時容量為0，想要放數據得增加容量，每次插入數據也得保證容量充足，為了方便，我們先寫一個用于檢查容量并增容的函數。
//檢查容量
void SeqListCheckCapacity(SeqList* psl)
{
assert(psl);
//如果滿了，就要擴容
if (psl->size == psl->capacity)
{
size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;//防止一開始capacity=0無法*2增容
SLDataType* tmp = realloc(psl->a, sizeof(SLDataType) * newCapacity);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
psl->a = tmp;
psl->capacity = newCapacity;
}
}
}
2.2.3 順序表打印
就是遍歷一次把所有元素打印出來，這樣可以檢查函數寫的是否正確，及時訂正。
//打印
void SeqListPrint(SeqList* psl)
{
assert(psl);
for (int i = 0; i < psl->size; i++)
{
printf("%d ", psl->a[i]);
}
printf("\n");
}
2.2.4 順序表尾插
//尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
assert(psl);
//如果滿了，就要擴容
SeqListCheckCapacity(psl);
psl->a[psl->size] = x;
psl->size++;
}
2.2.5 順序表尾刪
只需要把size-1這樣的話下一個數據就會把尾部數據覆蓋掉，達到刪除的效果。
//尾刪
void SeqListPopBack(SeqList* psl)
{
assert(psl);
if (psl->size > 0)
{
psl->size--;
}
}
2.2.6 順序表頭插
//頭插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
assert(psl);
//如果滿了，就要擴容
SeqListCheckCapacity(psl);
//挪動數據,騰出頭部位置
int end = psl->size - 1;
while (end >= 0)
{
psl->a[end + 1] = psl->a[end];
end--;
}
psl->a[0] = x;
psl->size++;
}
2.2.7 順序表頭刪
將第一個位置覆蓋掉，然后用尾刪的思路將最后一個數據刪除。
//頭刪
void SeqListPopFront(SeqList* psl)
{
assert(psl);
//挪動數據覆蓋第一個
if(psl->size>0)
{
int begin = 1;
while (begin < psl->size)
{
psl->a[begin - 1] = psl->a[begin];
begin++;
}
}
psl->size--;
}
2.2.8 順序表在pos位置插入x
思路跟頭插很像,但內含陷阱！
//在pos位置插入
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
assert(psl);
//如果滿了，就要擴容
SeqListCheckCapacity(psl);
溫和檢測
//if (pos > psl->size)
//{
// printf("pos越界：%d\n", pos);
// return;
//}
//暴力檢測
assert(pos <= psl->size);
//pos=0的時候由于無符號整型判斷時的整型提升，會出問題
//size_t end = psl->size - 1;
//while (end >= pos)
//{
// psl->a[end + 1] = psl->a[end];
// end--;
//}
//psl->a[pos] = x;
//psl->size++;
//這樣寫才不會有問題
size_t end = psl->size;
while (end > pos)
{
psl->a[end] = psl->a[end - 1];
--end;
}
psl->a[pos] = x;
psl->size++;
}
2.2.9 順序表刪除pos位置的值
思路跟頭刪很像
//在pos位置刪除
void SeqListErase(SeqList* psl, size_t pos)
{
assert(psl);
assert(pos < psl->size);
size_t begin = pos + 1;
while (begin < psl->size)
{
psl->a[begin - 1] = psl->a[begin];
++begin;
}
psl->size--;
}
2.2.10 尾插、尾刪、頭插、頭刪的改進
有了上面兩個通常情況下的增刪函數，我們就能改進尾插、尾刪、頭插、頭刪。這樣能夠快速寫完順序表
//尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
assert(psl);
SeqListCheckCapacity(psl);
SeqListInsert(psl, psl->size, x);//在size位置插入數據
}
//尾刪
void SeqListPopBack(SeqList* psl)
{
assert(psl);
SeqListErase(psl, psl->size-1);//在size-1位置刪除數據
}
//頭插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
assert(psl);
SeqListCheckCapacity(psl);
SeqListInsert(psl, 0, x);//在0位置插入數據
}
//頭刪
void SeqListPopFront(SeqList* psl)
{
assert(psl);
SeqListErase(psl, 0);//在0位置刪除數據
}
2.2.11 順序表查找
遍歷一遍，一個個找
int SeqListFind(SeqList* psl, SLDataType x)
{
assert(psl);
for (int i = 0; i < psl->size; ++i)
{
if (psl->a[i] == x)
{
return i;
}
}
return -1;
}
2.2.12 順序表銷毀
最后的最后，一定要養成好習慣，不要忘記銷毀之前申請的空間，防止內存泄漏。
//銷毀
void SeqListDestroy(SeqList* psl)
{
free(psl->a);
psl->a = NULL;
psl->capacity = 0;
psl->size = 0;
}
2.3 數組相關面試題
刪除排序數組中的重復項。26. 刪除有序數組中的重復項.
原地移除數組中所有的元素val，要求時間復雜度為O(N)，空間復雜度為O(1)。27. 移除元素.
合并兩個有序數組。88. 合并兩個有序數組.
2.4 順序表的問題及思考
問題：
- 中間/頭部的插入刪除，時間復雜度為O(N)
- 增容需要申請新空間，拷貝數據，釋放舊空間。會有不小的消耗。
- 增容一般是呈2倍的增長，勢必會有一定的空間浪費。例如當前容量為100，滿了以后增容到200，我們再繼續插入了5個數據，后面沒有數據插入了，那么就浪費了95個數據空間。
思考：如何解決以上問題呢？下期會給出了鏈表的結構，現在大家可以想想鏈表會如何解決這些問題。
原文鏈接：https://blog.csdn.net/qq_47882731/article/details/123411114
相關推薦
- 2022-08-21 Android貝塞爾曲線實現加入購物車拋物線動畫_Android
- 2022-05-17 Spring Cloud Loadbalancer 修改默認緩存為Caffeine,修改微服務啟動關
- 2022-10-01 Python?Color類與文字繪制零基礎掌握_python
- 2022-07-08 C#獲取應用程序路徑或Web頁面目錄路徑_C#教程
- 2022-07-27 Python中的協程(Coroutine)操作模塊(greenlet、gevent)_python
- 2021-12-20 ES6 Number 數值的擴展 0.1 + 0.2 === 0.3 居然是false
- 2022-06-21 Android?studio實現動態背景頁面_Android
- 2022-10-15 Qt鍵盤事件實現圖片在窗口上下左右移動_C 語言
- 最近更新
-
- 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同步修改后的遠程分支
提供CDN加速