數據結構學習之順序表

? ? ? ? 在C語言學習到一定階段之后，接下來我們就進入到了數據結構的部分內容。

目錄

數據結構與線性表

順序表

? ? ? ? 順序表分類：

? ? ? ? 接下來我們要寫一段代碼實現動態順序表。

首先我們需要準備三個文件：

1.接下來我們要定義一個數據表

2.當創建號我們的順序表之后，我們要對他進行初始化

3.而動態內存創建后就必須有銷毀

4.接下來我們要對順序表進行各種操作：增刪插改

尾部插入數據

?頭部插入數據

尾部刪除數據

頭部刪除數據：

指定位置之前插入數據

指定位置查找數據

完整的代碼：

數據結構與線性表

? ? ? ? 數據就像草原的一群羊一樣，如果你要在草原上找到一個叫做“咩咩”的羊很難，但是如果你要找一頭“3號”羊是比較簡單的。數據結構就是像羊圈管理羊群一樣管理數據。

? ? ? ? 因此可以說，數據結構就是計算機存儲和組織數據的方式。

? ? ? ? 數組就是一種很基礎的數據結構，用來存儲一群同類型的數據。但是隨著我們要對數據進行的操作愈加復雜（訪問、修改、插入數據等等等等），頻繁的訪問數組已經嚴重影響了計算機運行的效率，因此簡單的數組已經無法滿足我們的需要了，因此我們需要進入第一個數據結構類型——線性表。

? ? ? ? 線性表是n個具有相同特性的數據元素的有限序列，是一種廣泛應用的數據結構，常見的線性表有：順序表、鏈表、棧、隊列、字符串等等。

? ? ? ? 但是注意線性表在邏輯上是連續的線性結構，但是物理上不一定是連續的。線性表在物理上儲存的時候通常以數組和鏈式結構的形式儲存。

順序表

? ? ? ? 順序表在底層上是數組。

? ? ? ? 那么既然已經有數組了，我們為什么需要順序表呢？舉例說明：

int a[100]={1,2,3,4,...X...};

????????對于如上所示的100個元素的數組a。如果我們要修改其中一個數字就找先遍歷數組找到對應元素修改，如果要插入和刪除數組的話，都需要遍歷這個100個元素的數組。這個效率顯然是很低的。因此我們需要一個更好用、效率更高的工具：順序表。

? ? ? ? 順序表是在數組的基礎上加上了增刪查改等方法的一種儲存形式。順序表的特性是在物理結構上連續，在邏輯結構上也連續。

? ? ? ? 這是一個固定長度的數組

int a[10]={0};

? ? ? ? 這是動態內存開辟出來的數組，確定大小后再去申請。

int *arr

? ? ? ? 順序表分類：

????????靜態順序表：

?
?
Stack SeqList
{int arr[100];//定長數組int size;//順序表當前有效的數據個數}??

? ? ? ? 動態順序表：

?
Stack Seqlist
{int *arr;//int size//有效數字個數int capacity;//空間大小
};?

相較于靜態順序表，動態順序表可以動態增容。

? ? ? ? 接下來我們要寫一段代碼實現動態順序表。

首先我們需要準備三個文件：

Seqlist.c——實現順序表的方法
Seqlist.h——順序表結構，順序表聲明，方法

test.c——測試代碼

1.接下來我們要定義一個數據表

2.當創建號我們的順序表之后，我們要對他進行初始化

這里我們用傳值返回就會報錯，原因：傳值返回是值拷貝，但是這里s1沒有值。
所以這里要用傳址返回。

3.而動態內存創建后就必須有銷毀

4.接下來我們要對順序表進行各種操作：增刪插改

聲明：

尾部插入數據

原理展示：

要申請多大的空間？

?增容一般是2到3倍（2倍更常見）。因為一次性給太多空間就會像靜態順序表那樣浪費大量空間而得不償失，而過少就會導致需要頻繁地擴容而導致程序運行效率過低

?尾部插入數據函數一：

尾部插入數據函數二：

因此這部分的代碼為：

但是這個結構是比較脆弱的，如果用戶輸入了這么一個東西，它就會報錯：讀取訪問權限沖突。

	SLPushback(NULL, 5);

?所以我們要對這個函數進行改造。

溫柔的方式

//溫柔的解決方式
if (ps->arr == NULL)
{return;
}
if (ps->size == ps->capacity)//空間不夠了
{
//code
}

暴力的方式

//暴力判斷
assert(ps->arr!= NULL);
//等價于assert(ps)

尾部插入的代碼：

//尾部插入數據
void SLPushback(SL* ps, STDatatype x)
{//暴力判斷assert(ps->arr!= NULL);//等價于assert(ps)if (ps->size == ps->capacity)//空間不夠了{//申請空間//要增容只能用realloc函數，不能用malloc和callocint newcapacity = ps->capacity == 0 ? 4:2*ps->capacity;STDatatype*tmp = realloc(ps->arr, newcapacity * 2 * sizeof(STDatatype));//tmp指的是結構體當中的數組arrif (tmp==NULL )//realloc可能申請失敗所以要判斷{perror("realloc error");return 1;//程序推出}//申請成功ps->arr = tmp;ps->capacity = newcapacity;}ps->arr[ps->size++] = x;
}
?頭部插入數據

?原理圖：

如圖所示，如果要申請空間挪動數據的話從最后一位開始

?代碼為：

尾部刪除數據

原理圖：

????????

代碼：?

??

頭部刪除數據：

原理圖：

代碼：??

指定位置之前插入數據

原理：

代碼;?指定位置刪除數據

原理圖：

? ? ? ? 代碼：

指定位置查找數據

查找數據相對來說比較簡單，這里受限于篇幅，只講解暴力查找的算法，即循環遍歷數組

完整的代碼：

Seqlist.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include<assert.h>
//定義順序表的結構//#define N 100
//靜態順序表
//struct SeqList
//{
//	int arr[N];
//	int size;//有效數據個數
//};
typedef int STDatatype;
//這里是為了將來方便替換數組存儲數據的類型
// 如果將來需要替換數據類型為char，只需要將int改為char即可//動態順序表
typedef struct SeqList
{STDatatype* arr; int size;//有效數據個數int capacity;//順序表空間大小
}SL;//這是為了將來為了方便調用結構體//順序表初始化
void SLInit(SL* ps);//順序表的銷毀
void SLDestory(SL* ps);
//校驗順序表空間夠不夠
void SLCheckCapacity(SL* ps);
//順序表的打印
void SLPrint(SL s);
//順序表頭部/尾部插入數據
void SLPushback(SL*ps, STDatatype x);//尾部插入數據
void SLPushfront(SL*ps, STDatatype x);//頭部插入數據void SLPopback(SL*ps);	//尾部刪除數據
void SLPopfront(SL*ps);//頭部刪除數據
//指定位置之前插入數據/刪除數據/查找數據
void SLInsert(SL* ps, int pos,STDatatype x);//插入數據
//ps表示在ps所在的數組里插入數據
//pos在指定順序表里下標的位置
//x為插入的數據
void SLDelete(SL* ps,int pos);//刪除數據
int SLFind(SL* ps, STDatatype x);//查找數據

Seqlist.c

#define _CRT_SECURE_NO_WARNINGS
#include"Seqlist.h"
//Seqlist.c——實現順序表的方法
//Seqlist.h——順序表結構，順序表聲明，方法
//順序表的初始化
void SLInit(SL *ps)
{ps->arr = NULL;//需要包含頭文件<stdlib.h>ps->size=ps->capacity=0;}
//順序表的銷毀
void SLDestory(SL*ps)
{if (ps->arr)//判斷數據表的數組不為空{free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}
//校驗順序表空間夠不夠
void SLCheckCapacity(SL* ps)
{if (ps->size == ps->capacity)//空間不夠了{//申請空間//要增容只能用realloc函數，不能用malloc和callocint newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDatatype* tmp = realloc(ps->arr, newcapacity * 2 * sizeof(STDatatype));//tmp指的是結構體當中的數組arrif (tmp == NULL)//realloc可能申請失敗所以要判斷{perror("realloc error");return 1;//程序推出}ps->arr = tmp;ps->capacity = newcapacity;}
}
//順序表的打印
void SLPrint(SL s)
{for (int i = 0;i < s.size;i++){printf("%d ", s.arr[i]);}printf("\n");
}
//尾部插入數據
void SLPushback(SL* ps, STDatatype x)
{//溫柔的方式// if(ps == NULL)// {//	return;// }//暴力判斷assert(ps);//等價于assert(ps->arr!= NULL);//校驗空間夠不夠SLCheckCapacity(ps);ps->arr[ps->size++] = x;
}
//頭部插入數據
void SLPushfront(SL* ps, STDatatype x)
{assert(ps);SLCheckCapacity(ps);//先讓順序表中整體的數據向后移動一位。for (int i = ps->size - 1;i >=0;i--){ps->arr[i+1]=ps->arr[i];//最后為arr[1]=arr[0]}ps->arr[0] = x;ps->size++;
}//尾部刪除數據
void SLPopback(SL* ps, STDatatype x)
{assert(ps);assert(ps->size != 0);//順序表不為空//這段代碼是否存在無所謂:ps->arr[ps->size - 1] = -1;--ps->size;
}
//頭部刪除數據
void SLPopfront(SL* ps)
{assert(ps);assert(ps->size != 0);//數據表整體向前移動一位for (int i = 0;i <= ps->size - 1;i++){ps->arr[i] = ps->arr[i+1];}ps->size--;
}
//指定位置之前插入數據
void SLInsert(SL* ps, int pos, STDatatype x)
{assert(ps);//pos必須>=0且<=sizeassert(pos>=0&&pos<=ps->size);SLCheckCapacity(ps);//校驗空間夠不夠//讓pos位置及之后的數據集體向后一位for (int i = ps->size-1;i >= pos;i--){ps->arr[i+1] = ps->arr[i];//最后為arr[pos+1]=arr[pos]}//pos位置空出來了ps->arr[pos] = x;ps->size++;
}
//指定位置刪除數據
void SLDelete(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--;}
//指定位置查找數據
int SLFind(SL* ps, STDatatype x)
{assert(ps);//遍歷數組查找for (int i = 0;i <= ps->size - 1;i++){if (x == ps->arr[i]){//找到了return i;}else {continue;}}return -1;//無效的下標表示沒找到
}

test.c

?

#define _CRT_SECURE_NO_WARNINGS
#include"Seqlist.h"
void SLtest1()
{SL s1;SLInit(&s1);//這里我們不能用傳值返回//傳值返回是值拷貝，但是這里s1沒有值//所以這里要用傳址返回//增刪查改操作。//順序表的插入//測試尾插SLPushback(&s1,1);SLPushback(&s1,2);SLPushback(&s1,3);SLPushback(&s1,4);//測試頭插SLPushfront(&s1, 5);SLPushfront(&s1, 6);SLPrint(s1);// 測試頭刪SLPopfront(&s1);SLPopfront(&s1);SLPrint(s1);// 測試尾刪SLPopback(&s1);SLPopback(&s1);SLPrint(s1);//順序表的銷毀SLDestory(&s1);
}
void SLtest2()
{SL s1;//初始化SLInit(&s1);//尾部插入數據SLPushback(&s1, 1);SLPushback(&s1, 2);SLPushback(&s1, 3);SLPushback(&s1, 4);//在指定位置之前插入數據SLInsert(&s1, 0, 99);SLInsert(&s1, s1.size, 88);SLPrint(s1);//99 1 2 3 4 88//刪除指定位置的數據SLDelete(&s1, 2);SLPrint(s1);//查找指定數據int F=SLFind(&s1, 3);if (F >= 0){printf("找到了，位置是%d\n",F);}else{printf("沒找到\n");}銷毀SLDestory(&s1);
}
int main()
{SLtest1();SLtest2();return 0;
}

????????順序表的內容并沒有結束，但是受限于篇幅原因我只能先到這里了，感謝各位讀者朋友的閱讀，求一個贊，謝謝。

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

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

相關文章

C# wpf

C# wpf

學習網址&#xff1a;控件的父類們 - WPF中文網 - 從小白到大佬 控件的父類&#xff1a; 由此我們可以得出結論&#xff0c;控件的父類們(準確的說&#xff0c;應該叫父類的父類的父類)&#xff0c;至少有如下幾個類型&#xff1a; DispatcherObjectDependencyObjectVisualU…
閱讀更多...
JavaEE-多線程實戰02

JavaEE-多線程實戰02

接上 多線程編程實戰01 第三個多線程程序 package thread.test;//定義了一個叫MyThread3的類&#xff0c;實現了Runable接口,所以它必須重寫run()方法 class MyThread3 implements Runnable {Overridepublic void run() {//線程執行的具體內容//進入一個無限循環&#xff0c;…
閱讀更多...
【無報錯，親測有效】如何在Windows和Linux系統中查看MySQL版本

【無報錯，親測有效】如何在Windows和Linux系統中查看MySQL版本

如何在Windows和Linux系統中查看MySQL版本 MySQL作為最流行的開源關系型數據庫管理系統之一&#xff0c;了解如何查看其版本信息對于開發者和數據庫管理員來說是常用的一個基本操作。本文將詳細介紹在Windows和Linux系統中查看MySQL版本的方法。 文章目錄 如何在Windows和Linu…
閱讀更多...
數字智慧方案5961丨智慧能源與運維云平臺解決方案（52頁PPT）（文末有下載方式）

數字智慧方案5961丨智慧能源與運維云平臺解決方案（52頁PPT）（文末有下載方式）

詳細資料請看本解讀文章的最后內容。 資料解讀&#xff1a;智慧能源與運維云平臺解決方案 在當今數字化時代&#xff0c;能源管理與設備運維的智能化、高效化成為企業發展的關鍵。智慧能源與運維云平臺解決方案應運而生&#xff0c;為企業提供了全面且先進的能源管理和運維手段…
閱讀更多...
Qt指南針

Qt指南針

Qt寫的指南針demo. 運行結果 滑動調整指針角度 實現代碼 h文件 #ifndef COMPASS_H #define COMPASS_H#include <QWidget> #include <QColor>class Compass : public QWidget {Q_OBJECT// 可自定義屬性Q_PROPERTY(QColor backgroundColor READ backgroundColor WRI…
閱讀更多...
北大新媒體運營黃金提示詞 | 北大Deepseek系列第七彈《DeepSeek與新媒體運營》，13所大學系列一站下載

北大新媒體運營黃金提示詞 | 北大Deepseek系列第七彈《DeepSeek與新媒體運營》，13所大學系列一站下載

今天大師兄給大家推薦的是北京大學Deepseek系列第七彈《DeepSeek與新媒體運營》。 本文檔系統介紹了DeepSeek模型在新媒體運營中的應用&#xff0c;技術原理、實踐案例及行業挑戰。 適用人群&#xff1a;新媒體運營人員、AI研究者、企業決策者。 思維導圖 napkin生成 《老…
閱讀更多...
2025年真實面試問題匯總（一）

2025年真實面試問題匯總（一）

Spingboot中如何實現有些類是否加載 在 Spring Boot 中可以通過 條件化配置&#xff08;Conditional Configuration&#xff09; 來控制某些類是否加載。Spring Boot 提供了一系列 Conditional 注解&#xff0c;允許根據特定條件動態決定 Bean 或配置類是否生效。以下是常見的…
閱讀更多...
綜合案例建模（2）

綜合案例建模（2）

文章目錄 螺旋片端蓋多孔扭轉環作業一作業二作業三 螺旋片端蓋 上視基準面畫草圖&#xff0c;拉伸250&#xff0c;向外拔模15度 以地面圓&#xff08;如果不行就轉換實體引用&#xff09;&#xff0c;創建螺旋線&#xff0c;錐形螺紋線15度向外 前視基準面去畫草圖 以上一步草圖…
閱讀更多...
Qt5與現代OpenGL學習（三）紋理

Qt5與現代OpenGL學習（三）紋理

把第一張圖放到D盤的1文件夾里面&#xff1a;1.png triangle.h #ifndef WIDGET_H #define WIDGET_H#include <QOpenGLWidget> #include <QOpenGLFunctions> #include <QOpenGLVertexArrayObject> #include <QOpenGLShaderProgram> #include <QOpen…
閱讀更多...
這是一款好用的PDF工具！

這是一款好用的PDF工具！

用戶習慣有時確實非常頑固&#xff0c;想要改變它可能需要漫長的時間。 比如PDF軟件&#xff0c;我認為國產的福/昕、萬/興等軟件都非常不錯&#xff0c;它們貼合國人的使用習慣&#xff0c;操作起來非常順手。但因為我習慣使用DC&#xff0c;所以在處理PDF文檔時&#xff0c;…
閱讀更多...
輕松實現CI/CD: 用Go編寫的命令行工具簡化Jenkins構建

輕松實現CI/CD: 用Go編寫的命令行工具簡化Jenkins構建

在工作中&#xff0c;隨著開發維護的服務越來越多&#xff0c;在很長的一段時間里&#xff0c;我來回在多個服務之間開發、構建、查看容器是否啟動成功。尤其是開發測試階段&#xff0c;需要打開jenkins頁面、搜索應用、再構建、再打開rancher頁面、搜索應用&#xff0c;這一連…
閱讀更多...
第十六屆藍橋杯 2025 C/C++B組第一輪省賽 全部題解（未完結）

第十六屆藍橋杯 2025 C/C++B組第一輪省賽 全部題解（未完結）

目錄 前言&#xff1a; 試題A&#xff1a;移動距離 試題C&#xff1a;可分解的正整數 試題D&#xff1a;產值調整 試題E&#xff1a;畫展布置 前言&#xff1a; 我參加的是第一輪省賽&#xff0c;說實話第一次參加還是比較緊張的&#xff0c;真到考場上看啥都想打暴力&…
閱讀更多...
Qt Creator環境編譯的Release軟件放在其他電腦上使用方法

Qt Creator環境編譯的Release軟件放在其他電腦上使用方法

本文解決的問題&#xff1a;將Qt Creator環境編譯的exe可執行程序放到其他電腦上不可用情況 1、尋找windeployqt工具所在路徑" D:\Qt5.12.10\5.12.10\msvc2015_64\bin" &#xff0c;將此路徑配置到環境變量&#xff1b; 2、用Qt Creator環境編譯出Release版本可執行…
閱讀更多...
使用skywalking進行go的接口監控和報警

使用skywalking進行go的接口監控和報警

安裝 helm upgrade --install skywalking ./skywalking-v1 --namespace skywalking --create-namespace 查看安裝結果 kubectl get pod -n skywalking NAME READY STATUS RESTARTS AGE elasticsearch-6c4ccbf99f-ng6sk 1/1 …
閱讀更多...
2025年- H16-Lc124-169.多數元素（技巧）---java版

2025年- H16-Lc124-169.多數元素（技巧）---java版

1.題目描述 2.思路 3.代碼實現 import java.util.Arrays;public class H169 {public int majorityElement(int[] nums) {Arrays.sort(nums);int nnums.length;return nums[n/2];}public static void main(String[] args){H169 test07new H169();int[] nums{2,2,1,1,1,2,2};int…
閱讀更多...
k8s術語pod

k8s術語pod

Pod概覽 理解Pod Pod是kubernetes中你可以創建和部署的最小也是最簡的單位，pod代表著集群中運行的進程。 Pod中封裝著應用的容器（有的情況下是好幾個容器），存儲、獨立的網絡IP,管理容器如何運行的策略選項。Pod代表著部署的一個單位：kubemetes中應用的一個實例，可能由一個…
閱讀更多...
《數字圖像處理（面向新工科的電工電子信息基礎課程系列教材）》章節思維導圖

《數字圖像處理（面向新工科的電工電子信息基礎課程系列教材）》章節思維導圖

今天看到了幾本書的思維導圖&#xff0c;感觸頗深&#xff0c;如果思維導圖只是章節安排&#xff0c;這樣的思維導圖有毛用。 給出《數字圖像處理&#xff08;面向新工科的電工電子信息基礎課程系列教材&#xff09;》實質內容章節的思維導圖。思維導圖的優勢是邏輯關系和知識…
閱讀更多...
Nacos簡介—4.Nacos架構和原理二

Nacos簡介—4.Nacos架構和原理二

大綱 1.Nacos的定位和優勢 2.Nacos的整體架構 3.Nacos的配置模型 4.Nacos內核設計之一致性協議 5.Nacos內核設計之自研Distro協議 6.Nacos內核設計之通信通道 7.Nacos內核設計之尋址機制 8.服務注冊發現模塊的注冊中心的設計原理 9.服務注冊發現模塊的注冊中心的服務數…
閱讀更多...
【MySQL】復合查詢與內外連接

【MySQL】復合查詢與內外連接

目錄 一、復合查詢 1、基本查詢回顧&#xff1a; 2、多表查詢&#xff1a; 3、自連接&#xff1a; 4、子查詢&#xff1a; 單列子查詢 多行子查詢&#xff1a; 多列子查詢&#xff1a; 在from語句中使用子查詢&#xff1a; 5、合并查詢&#xff1a; union&#xff1…
閱讀更多...
后端工程師需要掌握哪些基礎技能

后端工程師需要掌握哪些基礎技能

后端工程師是構建系統核心邏輯的關鍵角色&#xff0c;需要掌握從基礎到進階的完整技術棧。以下是結合國內實際開發需求的技能樹整理&#xff0c;附帶學習建議&#xff1a; 一、編程語言&#xff08;至少精通1-2種&#xff09; # 國內主流選擇&#xff08;按優先級排序&#x…
閱讀更多...
最新文章

Copyright @ 2022~2023