探索數據結構：深入了解順序表的奧秘


?? 歡迎大家來到貝蒂大講堂??

🎈🎈養成好習慣，先贊后看哦~🎈🎈

所屬專欄：數據結構與算法
貝蒂的主頁：Betty’s blog

1. 什么是順序表

順序表是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構，它與數組非常類似，但是相比于數組順序表有一個非常明顯的優點——可以動態內存增長空間大小

2. 順序表的功能

順序表可以大致包含以下幾個功能：

  1. 初始化順序表中的數據。

  2. 打印順序表中的數據。

  3. 對順序表進行尾插(末尾插入數據)。

  4. 對順序表中數據進行尾刪(末尾刪除數據)。

3. 順序表的定義

定義順序表我們首先需要一個動態內存開辟的空間，當前數據的個數(size)，以及方便擴容的容量大小(capacity)。

typedef int SLDataType; //類型重命名，方便后續修改類型
#define N 4 //初始化空間大小
typedef struct SeqList
{SLDataType* a;    //指向動態開辟的數組size_t size;      //有效數據個數size_t capacity;  //容量大小
}SeqList;

4. 功能的具體實現

4.1 初始化順序表

(1) 代碼實現

初始化順序表時我們可以先開辟四個空間，之后不夠再進行擴容。

void SeqListInit(SeqList* p)
{assert(p);  //斷言p->a =(SLDataType*)malloc(N*sizeof(SLDataType));  //初始順序表為四個空間if (p == NULL){perror("malloc fail:");return ;}p->size = 0;  //初始數據個數為0p->capacity = 4;  //初始空間容量為4
}
(2) 復雜度分析
  • 時間復雜度：由于沒有其他未知數的引入，所以所需時間是個常數，也就是O(1)。
  • 空間復雜度：動態開辟N個空間，所以空間復雜度為O(N)。

4.2 打印數據

(1) 代碼實現

打印數據只用循環打印就可以了。

void SeqListPrint(const SeqList* p)
{assert(p);  //斷言if (p->size == 0)  //判斷順序表是否為空{printf("順序表為空\n");return;}int i = 0;for (i = 0; i < p->size; i++)  //打印順序表{printf("%d ", p->a[i]);}printf("\n");
}
(2) 復雜度分析
  • 時間復雜度：因為會打印順序表中的所有數據，所以時間復雜度為O(N)。
  • 空間復雜度：打印順序表并不需要開辟格外的空間，所以空間復雜度為O(N)。

4.3 尾插數據

尾插數據，顧名思義就是在順序表末尾插入數據，在插入數據之前我們應該檢查順序表是否為滿。

(1) 檢查是否已滿
void CheckCapacity(SeqList* p)
{assert(p);  //斷言if (p->size == p->capacity)  //檢查容量，滿了則增容{size_t newcapacity = 2 * p->capacity;  //，擴容為原來的2倍SLDataType* prt = (SLDataType*)realloc(p->a, newcapacity * sizeof(SLDataType));  //擴容if (prt == NULL){perror("realloc fail:");return ;}p->a = prt;  // prt不為空，開辟成功p->capacity = newcapacity;  //更新容量}
}
(2) 插入數據
void SeqListPushBack(SeqList* p, SLDataType x)
{assert(p);  //斷言CheckCapacity(p);  //檢查順序表容量是否已滿p->a[p->size] = x;  //尾插數據p->size++;  //有效數據個數+1
}
(3) 復雜度分析
  • 時間復雜度：沒有變量影響時間，時間復雜度為O(1)。
  • 空間復雜度：以最壞的情況考慮，會進行擴容，空間復雜度為O(N)。

4.4 尾刪數據

同理，尾刪數據就是刪除順序表中最后一個元素，我們只需將size–。注意：刪除之前要保證順序表中有數據。

(1) 代碼實現
void SeqListPopBack(SeqList* p)
{assert(p);  //斷言assert(p->size > 0);  //順序表不能為空p->size--;  //有效數據個數-1
}
(2) 復雜度分析
  • 時間復雜度：沒有變量影響時間，時間復雜度為O(1)。
  • 空間復雜度：沒有變量影響空間，空間復雜度為O(N)。

4.5 頭插數據

頭部插入數據就是在第一個元素位置插入一個元素。

(1) 代碼實現
void SeqListPushFront(SeqList* p, SLDataType x)
{assert(p);  //斷言CheckCapacity(p);  //檢查順序表容量是否已滿int i = 0;for (i = p->size - 1; i >= 0; i--)  //順序表中[0,size-1]的元素依次向后挪動一位{p->a[i + 1] = p->a[i];}p->a[0] = x;  //頭插數據p->size++;  //有效數據個數+1
}
(2) 復雜度分析
  • 時間復雜度：因為從頭部插入數據，后續數據需要依次覆蓋，所以時間復雜度為O(N)。
  • 空間復雜度：因為可能會進行擴容，按最壞的情況來算，空間復雜度為O(N)。

4.5 頭刪數據

從頭部刪除數據，與尾部刪除數據不同，需要依次往前覆蓋。

(1) 代碼實現
void SeqListPopFront(SeqList* p)
{assert(p);  //斷言assert(p->size > 0);  //順序表不能為空int i = 0;for (i = 1; i < p->size; i++)  //順序表中[1,size-1]的元素依次向前挪動一位{p->a[i - 1] = p->a[i];}p->size--;  //有效數據個數-1
}
(2) 復雜度分析
  • 時間復雜度：因為需要往前覆蓋數據，所以時間復雜度自然為O(N)。
  • 空間復雜度：因為并沒有開辟其他空間，所以空間復雜度為O(1)。

4.6 查找指定值

根據輸入參數，在順序表中查找指定的值并返回其下標，若未找到則返回-1。

(1) 代碼實現
int SeqListFind(const SeqList* p, SLDataType x)
{assert(p);  //斷言int i = 0;for (i = 0; i < p->size; i++){if (p->a[i] == x){return i;  //查找到，返回該值在數組中的下標}}return -1;  //沒有查找到
}
(2) 復雜度分析
  • 時間復雜度：以最壞的情況分析，時間復雜度為O(N)。
  • 空間復雜度：并沒有格外的空間消耗，空間復雜度為O(1)。

4.7 指定位置修改

我們可以通過指定下標或者查找指定值的下標來修改任意位置的值。

(1) 代碼實現
void SeqListModify(SeqList* p, int pos, SLDataType x)
{assert(p);  //斷言assert(p->size > 0);  //順序表不能為空assert(pos >= 0 && pos < p->size);  //檢查pos下標的合法性p->a[pos] = x;  //修改pos下標處對應的數據
}
(2) 復雜度分析
  • 時間復雜度：因為是通過指定下標修改，所以時間復雜度為O(1)。
  • 空間復雜度：沒有開辟額外的空間，所以空間復雜度為O(1)。

4.8 指定位置插入

和前面其他插入一樣，指定位置插入也需要判斷是否擴容。

(1) 代碼實現
void SeqListInsert(SeqList* p, int pos, SLDataType x)
{assert(p);//斷言assert(pos <= p->size); //檢查pos下標的合法性SeqListCheck(p);//擴容int cur = p->size;while (cur > pos){p->a[cur] = p->a[cur - 1];//覆蓋--cur;}p->a[pos] = x;p->size++;
}
(2) 復雜度分析
  • 時間復雜度：需要依次覆蓋，時間復雜度為O(N)。
  • 空間復雜度：可能需要擴容，空間復雜度為O(N)。

4.9 指定位置刪除

和前面的刪除差不多，但是指定刪除可能會依次覆蓋。

(1) 代碼實現
void SeqListErase(SeqList* p, int pos)
{assert(p);  //斷言assert(p->size > 0);  //順序表不能為空assert(pos >= 0 && pos < p->size);  //檢查pos下標的合法性int i = 0;for (i = pos + 1; i < p->size; i++)  //將pos位置后面的數據依次向前挪動一位{p->a[i - 1] = p->a[i];}p->size--;  //有效數據個數-1
}
(2) 復雜度分析
  • 時間復雜度：需要依次覆蓋，時間復雜度為O(N)。
  • 空間復雜度：沒有額外的空間消耗，空間復雜度為O(1)。

4.10 回收空間

在結束操作之后，需要釋放開辟的空間，以防止內存泄漏。

(1) 代碼實現
void SeqListDestory(SeqList* p)
{assert(p);  //斷言free(p->a);   //釋放動態開辟的空間p->a = NULL;  //置空p->size = 0;  //數據個數置0p->capacity = 0;  //空間容量大小置0
}
(2) 復雜度分析
  • 時間復雜度：沒有額外的時間消耗，時間復雜度為O(1)。
  • 空間復雜度：沒有額外的空間消耗，空間復雜度為O(1)。

5. 完整代碼

5.1 SeqList.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define N 4 //初始化空間大小
typedef int SLDataType; //類型重命名，方便后續修改類型
typedef struct SeqList
{SLDataType* a;    //指向動態開辟的數組size_t size;      //有效數據個數size_t capacity;  //容量大小
}SeqList;void SeqListInit(SeqList* p);//初始化順序表
void SeqListPrint(const SeqList* p);//打印順序表
void SeqListPushBack(SeqList* p, SLDataType x);//尾插
void SeqListPopBack(SeqList* p);//尾刪
void SeqListPushFront(SeqList* p, SLDataType x);//頭插
void SeqListPopFront(SeqList* p);//頭刪
int SeqListFind(const SeqList* p, SLDataType x);//查找數據
void SeqListModify(SeqList* p, int pos, SLDataType x);//修改數據
void SeqListInsert(SeqList* p, int pos, SLDataType x);//指定插入
void SeqListErase(SeqList* p, int pos);//指定刪除
void SeqListDestory(SeqList* p);//釋放空間

5.2 SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
void SeqListInit(SeqList* p)
{assert(p);  //斷言p->a =(SLDataType*)malloc(N*sizeof(SLDataType));  //初始順序表為四個空間if (p == NULL){perror("malloc fail:");return ;}p->size = 0;  //初始數據個數為0p->capacity = 4;  //初始空間容量為4
}
void CheckCapacity(SeqList* p)
{assert(p);  //斷言if (p->size == p->capacity)  //檢查容量，滿了則增容{size_t newcapacity = 2 * p->capacity;  //，擴容為原來的2倍SLDataType* prt = (SLDataType*)realloc(p->a, newcapacity * sizeof(SLDataType));  //擴容if (prt == NULL){perror("realloc");return ;}p->a = prt;  // prt不為空，開辟成功p->capacity = newcapacity;  //更新容量}
}
void SeqListPushBack(SeqList* p, SLDataType x)
{assert(p);  //斷言CheckCapacity(p);  //檢查順序表容量是否已滿p->a[p->size] = x;  //尾插數據p->size++;  //有效數據個數+1
}
void SeqListPrint(const SeqList* p)
{assert(p);  //斷言if (p->size == 0)  //判斷順序表是否為空{printf("順序表為空\n");return;}int i = 0;for (i = 0; i < p->size; i++)  //打印順序表{printf("%d ", p->a[i]);}printf("\n");
}
void SeqListPopBack(SeqList* p)
{assert(p);  //斷言assert(p->size > 0);  //順序表不能為空p->size--;  //有效數據個數-1
}
void SeqListPushFront(SeqList* p, SLDataType x)
{assert(p);  //斷言CheckCapacity(p);  //檢查順序表容量是否已滿int i = 0;for (i = p->size - 1; i >= 0; i--)  //順序表中[0,size-1]的元素依次向后挪動一位{p->a[i + 1] = p->a[i];}p->a[0] = x;  //頭插數據p->size++;  //有效數據個數+1
}
void SeqListPopFront(SeqList* p)
{assert(p);  //斷言assert(p->size > 0);  //順序表不能為空int i = 0;for (i = 1; i < p->size; i++)  //順序表中[1,size-1]的元素依次向前挪動一位{p->a[i - 1] = p->a[i];}p->size--;  //有效數據個數-1
}
int SeqListFind(const SeqList* p, SLDataType x)
{assert(p);  //斷言int i = 0;for (i = 0; i < p->size; i++){if (p->a[i] == x){return i;  //查找到，返回該值在數組中的下標}}return -1;  //沒有查找到
}
void SeqListModify(SeqList* p, int pos, SLDataType x)
{assert(p);  //斷言assert(p->size > 0);  //順序表不能為空assert(pos >= 0 && pos < p->size);  //檢查pos下標的合法性p->a[pos] = x;  //修改pos下標處對應的數據
}
void SeqListInsert(SeqList* p, int pos, SLDataType x)
{assert(p);//斷言assert(pos <= p->size); //檢查pos下標的合法性SeqListCheck(p);//擴容int cur = p->size;while (cur > pos){p->a[cur] = p->a[cur - 1];//覆蓋--cur;}p->a[pos] = x;p->size++;
}
void SeqListErase(SeqList* p, int pos)
{assert(p);  //斷言assert(p->size > 0);  //順序表不能為空assert(pos >= 0 && pos < p->size);  //檢查pos下標的合法性int i = 0;for (i = pos + 1; i < p->size; i++)  //將pos位置后面的數據依次向前挪動一位{p->a[i - 1] = p->a[i];}p->size--;  //有效數據個數-1
}
void SeqListDestory(SeqList* p)
{assert(p);  //斷言free(p->a);   //釋放動態開辟的空間p->a = NULL;  //置空p->size = 0;  //數據個數置0p->capacity = 0;  //空間容量大小置0
}

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/715202.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/715202.shtml
英文地址，請注明出處：http://en.pswp.cn/news/715202.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

【初中生講機器學習】13. 決策樹算法一萬字詳解！一篇帶你看懂！

【初中生講機器學習】13. 決策樹算法一萬字詳解！一篇帶你看懂！

創建時間&#xff1a;2024-03-02 最后編輯時間&#xff1a;2024-03-02 作者&#xff1a;Geeker_LStar 你好呀~這里是 Geeker_LStar 的人工智能學習專欄&#xff0c;很高興遇見你~ 我是 Geeker_LStar&#xff0c;一名初三學生&#xff0c;熱愛計算機和數學&#xff0c;我們一起加…
閱讀更多...
取送貨問題（Pickup and Delivery Problem）

取送貨問題（Pickup and Delivery Problem）

取送貨問題及其變體 廣義取送貨問題&#xff08;General Pickup and Delivery Problems&#xff0c;GPDP&#xff09;可以分為兩類&#xff1a; Vehicle Routing Problems with Backhauls&#xff0c;VRPB&#xff1a;從配送中心&#xff08;depot&#xff09;取貨運輸貨物到客…
閱讀更多...
測試/測試開發八股——找大廠測試實習基礎篇

測試/測試開發八股——找大廠測試實習基礎篇

第一部分：基礎概念 1. 軟件測試是什么？ 在規定的條件下對一個產品或者程序進行操作，以發現程序錯誤，衡量軟件質量，并對其是否能滿足設計要求進行評估的過程。 軟件測試工程師的任務 2. 軟件測試工程師的任務 軟件測試工程師主要工作是檢查軟件是否有bug、是否具有穩定…
閱讀更多...
5.設備驅動程序

5.設備驅動程序

5. 設備驅動程序 Linux 內核是一個比較龐大的系統&#xff0c;深入理解內核可以減少在系統移植中的障礙。在系統移植中設備驅動開發是一項很復雜的工作&#xff0c;由于 Linux 內核提供了一部分源代碼&#xff0c;同時還提供了對某些公共部分的支持&#xff0c;例如&#xff0c…
閱讀更多...
數據結構與算法：堆

數據結構與算法：堆

朋友們大家好啊&#xff0c;本篇文章來到堆的內容&#xff0c;堆是一種完全二叉樹&#xff0c;再介紹堆之前&#xff0c;我們首先對樹進行講解 樹與堆 1.樹的介紹1.1節點的分類 2.樹的存儲結構3.二叉樹的概念和結構3.1 二叉樹的特點3.2 特殊的二叉樹3.3二叉樹的存儲結構 4.堆的…
閱讀更多...
Acwing---1460. 我在哪？

Acwing---1460. 我在哪？

我在哪&#xff1f; 1.題目2.基本思想3.代碼實現 1.題目 農夫約翰出門沿著馬路散步&#xff0c;但是他現在發現自己可能迷路了&#xff01; 沿路有一排共 N N N 個農場。 不幸的是農場并沒有編號&#xff0c;這使得約翰難以分辨他在這條路上所處的位置。 然而&#xff0c;…
閱讀更多...
Mybatis | 動態SQL

Mybatis | 動態SQL

目錄: 動態SQL中的 “元素” :\<if>元素\<choose>、\<when>、\<otherwise>元素\<where>、\<trim>元素\<set>元素\<foreach>元素\<bind>元素 作者簡介 &#xff1a;一只大皮卡丘&#xff0c;計算機專業學生&#xff0c;正…
閱讀更多...
單細胞Seurat - 降維與細胞標記(4)

單細胞Seurat - 降維與細胞標記(4)

本系列持續更新Seurat單細胞分析教程&#xff0c;歡迎關注&#xff01; 非線形降維 Seurat 提供了幾種非線性降維技術&#xff0c;例如 tSNE 和 UMAP&#xff0c;來可視化和探索這些數據集。這些算法的目標是學習數據集中的底層結構&#xff0c;以便將相似的細胞放在低維空間中…
閱讀更多...
__vueParentComponent和__vue__獲取dom元素上的vue實例

__vueParentComponent和__vue__獲取dom元素上的vue實例

vue2: 使用__vue__ const el document.querySelector(.xxx); const vueInstance el.__vue__;vue3: 使用 __vueParentComponent const el document.querySelector(.xxx); const vueInstance el.__vueParentComponent;
閱讀更多...
Python錯題集-4：NameError:（變量名錯誤）

Python錯題集-4：NameError:（變量名錯誤）

1問題描述 Traceback (most recent call last): File "D:\pycharm\projects\1-可視化學習\8.3更改小提琴圖的中位數、均值、顏色等.py", line 8, in <module> violin_parts plt.violinplot(data, showmediansTrue, showmeansTrue) …
閱讀更多...
代碼隨想錄算法訓練營第四十四天 完全背包 、零錢兌換 II 、組合總和 Ⅳ

代碼隨想錄算法訓練營第四十四天 完全背包 、零錢兌換 II 、組合總和 Ⅳ

代碼隨想錄算法訓練營第四十四天 | 完全背包 、零錢兌換 II 、組合總和 Ⅳ 完全背包 題目鏈接&#xff1a;題目頁面 (kamacoder.com) 解釋一、01背包 一維 &#xff1a;為什么要倒序遍歷背包&#xff1f; 首先要明白二維數組的遞推過程&#xff0c;然后才能看懂二維變一維的…
閱讀更多...
【MATLAB源碼-第150期】基于matlab的開普勒優化算法（KOA)機器人柵格路徑規劃，輸出做短路徑圖和適應度曲線。

【MATLAB源碼-第150期】基于matlab的開普勒優化算法（KOA)機器人柵格路徑規劃，輸出做短路徑圖和適應度曲線。

操作環境&#xff1a; MATLAB 2022a 1、算法描述 開普勒優化算法&#xff08;Kepler Optimization Algorithm, KOA&#xff09;是一個虛構的、靈感來自天文學的優化算法&#xff0c;它借鑒了開普勒行星運動定律的概念來設計。在這個構想中&#xff0c;算法模仿行星圍繞太陽的…
閱讀更多...
項目風險：測試大佬結合實例告訴你如何應對！

項目風險：測試大佬結合實例告訴你如何應對！

項目有風險 今天下午15點&#xff0c;團隊成員D向他的主管Z反饋他測試的項目有風險&#xff1a;項目在測試周期內&#xff0c;但在用例評審時發現有一處功能邏輯有爭議&#xff0c;需要產品經理跟業務方確認&#xff0c;可能出現的情況有&#xff1a; 1 不變更需求&#xff0…
閱讀更多...
【技巧】SpringCloud Gateway實現多子域(單個應用開放多個端口)

【技巧】SpringCloud Gateway實現多子域(單個應用開放多個端口)

0. 目錄 1. 需求背景2. 實現3. 額外 - 其它Servlet容器實現3.1 Undertow3.2 Tomcat 4. 相關 1. 需求背景 瀏覽器針對單個網站地址(ipport)存在“6個請求”限制&#xff1b;通過多子域配置可以突破這個限制&#xff0c;增加網站的響應效率&#xff0c;尤其是針對三維服務這類大…
閱讀更多...
【深入了解設計模式】組合設計模式

【深入了解設計模式】組合設計模式

組合設計模式 組合模式是一種結構型設計模式&#xff0c;它允許你將對象組合成樹狀結構來表現“整體-部分”關系。組合模式使得客戶端可以統一對待單個對象和組合對象&#xff0c;從而使得代碼更加靈活和易于擴展。 概述 ? 對于這個圖片肯定會非常熟悉&#xff0c;上圖我們可…
閱讀更多...
Carla自動駕駛仿真九：車輛變道路徑規劃

Carla自動駕駛仿真九：車輛變道路徑規劃

文章目錄 前言一、關鍵函數二、完整代碼效果 前言 本文介紹一種在carla中比較簡單的變道路徑規劃方法&#xff0c;主要核心是調用carla的GlobalRoutePlanner模塊和PID控制模塊實現變道&#xff0c;大體的框架如下圖所示。 一、關鍵函數 1、get_spawn_point(),該函數根據指定r…
閱讀更多...
c語言字符串函數之strcpy函數，strnpy函數

c語言字符串函數之strcpy函數，strnpy函數

strcpy函數 語法格式 strcpy(字符數組1,字符串2&#xff09; 它的作用是把字符串2復制到字符數組1里面 #include<stdio.h> #include<string.h> int main() {char c[]"河南";char d[]"安徽";char d[];printf("%s\n",strcpy(c,d));…
閱讀更多...
力扣hot100題解（python版41-43題）

力扣hot100題解（python版41-43題）

41、二叉樹的層序遍歷 給你二叉樹的根節點 root &#xff0c;返回其節點值的 層序遍歷 。 &#xff08;即逐層地&#xff0c;從左到右訪問所有節點&#xff09;。 示例 1&#xff1a; 輸入&#xff1a;root [3,9,20,null,null,15,7] 輸出&#xff1a;[[3],[9,20],[15,7]]示例…
閱讀更多...
【C語言結構體】用戶自定義類型--結構體，結構體傳參，位段，聯合體和枚舉【圖文詳解】

【C語言結構體】用戶自定義類型--結構體，結構體傳參，位段，聯合體和枚舉【圖文詳解】

歡迎來CILMY23的博客喔&#xff0c;本篇為【C語言結構體】用戶自定義類型--結構體&#xff0c;結構體傳參&#xff0c;位段&#xff0c;聯合體和枚舉【圖文詳解】&#xff0c;感謝觀看&#xff0c;支持的可以給個一鍵三連&#xff0c;點贊關注收藏。 前言 上一篇&#xff08;ht…
閱讀更多...
GO—函數

GO—函數

Go 語言支持普通函數、匿名函數和閉包&#xff0c;從設計上對函數進行了優化和改進&#xff0c;讓函數使用起來更加方便。 Go 語言的函數屬于“一等公民”&#xff08;first-class&#xff09;&#xff0c;也就是說&#xff1a; 函數本身可以作為值進行傳遞。支持匿名函數和閉…
閱讀更多...
最新文章

Copyright @ 2022~2023