C語言：順序表（上）

C語言：順序表（上）

1.順序表的介紹
2.順序表的實現

1.順序表的介紹

線性表是n個具有相同特性的數據元素的有限序列。

線性表是一種在實際中廣泛使用的數據結構，常見的線性表：順序表、鏈表、棧、隊列、字符串…

線性表在邏輯上是線性結構，也就說是連續的一條直線。但是在物理結構上并不一定是連續的，線性表在物理上存儲時，通常以 數組 和 鏈式結構 的形式存儲。

順序表的底層結構是數組，對數組的封裝，實現了常用的增刪改查等接口。

順序表分為兩類：

  • 靜態順序表：使用定長數組存儲元素。容易出現空間不夠用、空間浪費的問題。
    在這里插入圖片描述

  • 動態順序表：空間可以按需申請。

接下來以動態順序表為例，編程實現順序表。

2.順序表的實現

首先，我們打開vs2022，創建一個頭文件SeqList.h，用來定義結構體和函數聲明，再創建SeqList.c來編寫函數，創建test.c文件來進行測試。
在這里插入圖片描述
實現順序表的過程中，我們需要realloc函數來進行開辟和調整空間，用assert進行檢查，所以我們在頭文件SeqList.h中應包含stdio.h、stdlib.h、assert.h。

//SeqList.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

定義順序表SeqList，再用typedef重命名為SL。

typedef struct SeqList
{int* arr;int size;    //有效數據個數int capacity;//空間大小（個數）
}SL;

指針arr可以指向數組、結構體、字符串等等數據，所以要把int重命名，以便后續更改arr指向的數據。

//SeqList.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;//把int重命名，方便后續更改
typedef struct SeqList
{SLDataType* arr;int size;    //有效數據個數int capacity;//空間大小（個數）
}SL;

接下來進行函數聲明，我們要編寫函數實現順序表的初始化、銷毀、打印、尾插/刪、頭插/刪、定位插入/刪除、查找。

//SeqList.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;//把int重命名，方便后續更改
typedef struct SeqList
{SLDataType* arr;int size;    //有效數據個數int capacity;//空間大小（個數）
}SL;
void SLInit(SL* ps);//順序表初始化void SLDestroy(SL* ps);//順序表銷毀void SLPrint(SL s);//順序表打印void SLPushBack(SL* ps, SLDataType x);//尾插void SLPushFront(SL* ps, SLDataType x);//頭插void SLPopBack(SL* ps);//尾刪void SLPopFront(SL* ps);//頭刪void SLInsert(SL* ps, int pos, SLDataType x);//定位插入void SLErase(SL* ps, int pos);//定位刪除int SLFind(SL* ps, SLDataType x);//查找

順序表初始化：指針ps指向順序表，把arr先置為NULL，有效數據的個數size為0，空間大小capacity為0。

void SLInit(SL* ps)//順序表初始化
{ps->arr = NULL;ps->size = ps->capacity = 0;
}

順序表銷毀：需要判斷順序表是否為空，若為空則不需要銷毀，若不為空則先用free釋放arr指向的空間，再把size、capacity置為0。

void SLDestroy(SL* ps)//順序表銷毀
{if (ps->arr)//若ps->arr為NULL，不再free，若不為NULL，則執行freefree(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;
}

在創建順序表之后，我們通過頭插、尾插、定位插入的方式往順序表中插入數據，但在插入之前，我們需要檢查arr指向的空間是否足夠，不夠則用realloc函數增加空間。

我們先判斷size與capacity是否相等，若相等，則說明空間不足，如圖所示：
在這里插入圖片描述
size與capacity不相等，則以原空間大小的2倍增加空間。

void SLCheckCapacity(SL* ps)//檢查插入前空間是否足夠
{if (ps->capacity == ps->size)//空間大小和有效數據個數一致，則空間不足{int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* t = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//要申請多大空間if (t == NULL)//若空間申請失敗{perror("realloc fail !");exit(1);//退出程序}ps->arr = t;//空間申請成功ps->capacity = newCapacity;//記錄新的空間大小}
}

尾插：尾插函數需要參數指向順序表的指針ps和插入的數據x，先用assert檢查ps是否為NULL，再通過SLCheckCapacity函數檢查空間是否足夠，若不足則增加空間，在插入數據之后，還要讓size加1，記錄新的有效數據個數。
在這里插入圖片描述

void SLPushBack(SL* ps, SLDataType x)//尾插
{assert(ps);SLCheckCapacity(ps);//檢查插入前空間是否足夠ps->arr[ps->size] = x;ps->size++;
}

頭插：頭插與尾插類似，頭插還需要循環把數據整體向后挪動一位。

void SLPushFront(SL* ps, SLDataType x)//頭插
{assert(ps);SLCheckCapacity(ps);//檢查插入前空間是否足夠for (int i = ps->size;i > 0;i--)//讓順序表中已有的數據整體往后挪一位{                               //從最后一位開始挪，避免覆蓋   ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;ps->size++;
}

順序表打印函數：

void SLPrint(SL s)//打印
{for (int i = 0;i < s.size;i++)printf("%d ", s.arr[i]);printf("\n");
}

尾刪：只要size減1，讓原本最后一個數據無法被訪問，就實現了尾刪。

void SLPopBack(SL* ps)//尾刪
{assert(ps);assert(ps->size);//順序表不為空--ps->size;
}

在這里插入圖片描述
頭刪：與尾刪類似，頭刪還要數據整體向前挪一位，且從第二位數據開始挪，通過覆蓋第一位數據實現頭刪。

void SLPopFront(SL* ps)//頭刪
{assert(ps);assert(ps->size);for (int i = 0;i < ps->size - 1;i++)//數據整體往前挪一位{                                   //從第二位往前挪，覆蓋第一位實現刪除ps->arr[i] = ps->arr[i + 1];}ps->size--;
}

定位插入：類似頭插、尾插，但多了一個參數pos，pos為數據插入后的下標，所以0<=pos<=size，在插入前，下標為pos及大于pos的數據往后挪一位。

void SLInsert(SL* ps, int pos, SLDataType x)//定位插入,插入后下標為pos
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);for (int i = ps->size;i > pos;i--)//pos及之后的數據整體往后挪一位{ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}

定位刪除：pos為下標，顯然0<=pos<size，下標大于pos的數據往前挪一位，通過arr[pos+1]把arr[pos]覆蓋掉來實現定位刪除。

void SLErase(SL* ps, int pos)//定位刪除
{assert(ps);assert(pos >= 0 && pos < ps->size);for (int i = pos;i < ps->size-1;i++)//pos之后數據往前挪一位{                                   //arr[pos+1]覆蓋掉arr[pos]ps->arr[i] = ps->arr[i + 1];}ps->size--;
}

查找：SLFind函數的參數x為要查找的數據，遍歷整個順序表，找到返回下標，找不到返回-1。

int SLFind(SL* ps, SLDataType x)//查找
{assert(ps);for (int i = 0;i < ps->size;i++){if (ps->arr[i] == x)return i;//找到了，返回下標}return -1;//未找到
}

在SeqList.c文件中的代碼如下：

//SeqList.c
#include"SeqList.h"
void SLInit(SL* ps)//順序表初始化
{ps->arr = NULL;ps->size = ps->capacity = 0;
}
void SLDestroy(SL* ps)//順序表銷毀
{if (ps->arr)//若ps->arr為NULL，不再free，若不為NULL，則執行freefree(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;
}
void SLCheckCapacity(SL* ps)//檢查插入前空間是否足夠
{if (ps->capacity == ps->size)//空間大小和有效數據個數一致，則空間不足{int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* t = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//要申請多大空間if (t == NULL)//若空間申請失敗{perror("realloc fail !");exit(1);//退出程序}ps->arr = t;//空間申請成功ps->capacity = newCapacity;}
}
void SLPushBack(SL* ps, SLDataType x)//尾插
{assert(ps);SLCheckCapacity(ps);//檢查插入前空間是否足夠ps->arr[ps->size] = x;ps->size++;
}
void SLPushFront(SL* ps, SLDataType x)//頭插
{assert(ps);SLCheckCapacity(ps);//檢查插入前空間是否足夠for (int i = ps->size;i > 0;i--)//讓順序表中已有的數據整體往后挪一位{                               //從最后一位開始挪，避免覆蓋   ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;ps->size++;
}
void SLPrint(SL s)//打印
{for (int i = 0;i < s.size;i++)printf("%d ", s.arr[i]);printf("\n");
}
void SLPopBack(SL* ps)//尾刪
{assert(ps);assert(ps->size);//順序表不為空--ps->size;
}
void SLPopFront(SL* ps)//頭刪
{assert(ps);assert(ps->size);for (int i = 0;i < ps->size - 1;i++)//數據整體往前挪一位{                                   //從第二位往前挪，覆蓋第一位實現刪除ps->arr[i] = ps->arr[i + 1];}ps->size--;
}
void SLInsert(SL* ps, int pos, SLDataType x)//定位插入,插入后下標為pos
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);for (int i = ps->size;i > pos;i--)//pos及之后的數據整體往后挪一位{ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}
void SLErase(SL* ps, int pos)//定位刪除
{assert(ps);assert(pos >= 0 && pos < ps->size);for (int i = pos;i < ps->size-1;i++)//pos之后數據往前挪一位{                                   //arr[pos+1]覆蓋掉arr[pos]ps->arr[i] = ps->arr[i + 1];}ps->size--;
}
int SLFind(SL* ps, SLDataType x)//查找
{assert(ps);for (int i = 0;i < ps->size;i++){if (ps->arr[i] == x)return i;//找到了，返回下標}return -1;//未找到
}

最后，我們就可以在test.c文件中做測試了，例如測試頭插和尾插：

#include"SeqList.h"
void test1()
{SL s;SL* ps = &s;SLInit(ps);SLPushFront(ps, 1);SLPushBack(ps,2);SLPushBack(ps, 3);SLPushBack(ps, 4);SLPrint(s);SLDestroy(ps);
}
int main()
{test1();return 0;
}

在這里插入圖片描述

拙作一篇，望諸位同道不吝斧正。

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

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

相關文章

GPT - 5被曝將在8月初發布！并同步推出mini、nano版

GPT - 5被曝將在8月初發布！并同步推出mini、nano版

據《TheVerge》最新報道&#xff0c;OpenAI 正準備在 8 月發布新版本旗艦大模型 GPT-5&#xff0c;如果順利的話發布節點最早會在 8 月初。同時&#xff0c;下個月發布 GPT-5 時&#xff0c;還會一并推出 mini&#xff08;小型&#xff09;和 nano&#xff08;微型&#xff09;…
閱讀更多...
【Linux操作系統】簡學深悟啟示錄：Linux環境基礎開發工具使用

【Linux操作系統】簡學深悟啟示錄：Linux環境基礎開發工具使用

文章目錄1.軟件包管理器yum2.Linux編輯器vim2.1 三模式切換2.2 正常模式2.3 底行模式2.4 可視化模式2.5 vim 配置3.Linux編譯器gcc/g3.1 預處理3.2 編譯3.3 匯編3.4 連接3.5 函數庫4.Linux自動化構建工具Makefile5.Linux調試器gdb希望讀者們多多三連支持小編會繼續更新你們的鼓…
閱讀更多...
八大神經網絡的區別

八大神經網絡的區別

神經網絡名稱全稱/修正名稱主要作用核心特點典型應用場景CINICNN&#xff08;卷積神經網絡&#xff09;處理圖像、視頻等空間數據&#xff0c;提取局部特征。使用卷積核、池化操作&#xff1b;擅長平移不變性。圖像分類、目標檢測、人臉識別。RINIRNN&#xff08;循環神經網絡&…
閱讀更多...
從 SQL Server 到 KingbaseES V9R4C12，一次“無痛”遷移與深度兼容體驗實錄

從 SQL Server 到 KingbaseES V9R4C12，一次“無痛”遷移與深度兼容體驗實錄

#數據庫平替用金倉 #金倉產品體驗官 摘要&#xff1a;本文以體驗項目案例為主線&#xff0c;從下載安裝、數據類型、T-SQL、JDBC、性能基準、踩坑回退六大維度&#xff0c;全景驗證 KingbaseES V9R4C12 對 SQL Server 的“零改造”兼容承諾&#xff1b;并給出 TPCH 100G 性能對…
閱讀更多...
EasyPlayer播放器系列開發計劃2025

EasyPlayer播放器系列開發計劃2025

EasyPlayer系列產品發展至今&#xff0c;已經超過10年&#xff0c;從最早的EasyPlayer RTSP播放器&#xff0c;到如今維護的3條線&#xff1a;EasyPlayer-RTSP播放器&#xff1a;Windows、Android、iOS&#xff1b;EasyPlayerPro播放器&#xff1a;Windows、Android、iOS&#…
閱讀更多...
通信名詞解釋：I2C、USART、SPI、RS232、RS485、CAN、TCP/IP、SOCKET、modbus等

通信名詞解釋：I2C、USART、SPI、RS232、RS485、CAN、TCP/IP、SOCKET、modbus等

以下內容參考AI生成內容1. I2C&#xff08;Inter-Integrated Circuit&#xff0c;集成電路間總線&#xff09;定義&#xff1a;由飛利浦&#xff08;現恩智浦&#xff09;開發的短距離串行通信總線&#xff0c;用于芯片級設備間的低速數據傳輸。工作原理&#xff1a;采用兩根信…
閱讀更多...
bash的特性-常見的快捷鍵

bash的特性-常見的快捷鍵

一、前言在 Linux Shell 編程和日常使用中&#xff0c;Bash 快捷鍵 是提升命令行操作效率的利器。熟練掌握這些快捷鍵&#xff0c;不僅可以節省大量輸入時間&#xff0c;還能顯著提升你在終端環境下的操作流暢度。本文將帶你全面了解 Bash 中常用的快捷鍵&#xff0c;包括&…
閱讀更多...
【Java Web實戰】從零到一打造企業級網上購書網站系統 | 完整開發實錄（三）

【Java Web實戰】從零到一打造企業級網上購書網站系統 | 完整開發實錄（三）

&#x1f3a8; 核心功能設計 &#x1f464; 用戶管理系統 用戶管理是整個系統的基礎&#xff0c;我設計了完整的用戶生命周期管理&#xff1a; &#x1f510; 用戶注冊流程 #mermaid-svg-D0eUHWissjNhkqlB {font-family:"trebuchet ms",verdana,arial,sans-serif;fon…
閱讀更多...
uniapp input 聚焦時鍵盤彈起滾動到對應的部分

uniapp input 聚焦時鍵盤彈起滾動到對應的部分

實現效果代碼如下<template><view idapp><view class"aa"></view><iconfont name"left"></iconfont>姓氏&#xff1a;<input style"background-color: antiquewhite;" type"text" v-model&quo…
閱讀更多...
【基礎篇三】WebSocket：實時通信的革命

【基礎篇三】WebSocket：實時通信的革命

目錄 一、傳統HTTP的"痛點"分析 1.1 HTTP的單向通信模式 1.2 "實時"效果的痛苦嘗試 ?編輯 1.3 性能對比分析 二、WebSocket 協議詳解 2.1 WebSocket是什么&#xff1f; ?編輯 2.2 WebSocket的核心特性 2.2.1 全雙工通信&#xff08;Full-Duple…
閱讀更多...
設計模式（十八）行為型：中介者模式詳解

設計模式（十八）行為型：中介者模式詳解

設計模式&#xff08;十八&#xff09;行為型&#xff1a;中介者模式詳解中介者模式&#xff08;Mediator Pattern&#xff09;是 GoF 23 種設計模式中的行為型模式之一&#xff0c;其核心價值在于通過引入一個中介者對象來封裝一組對象之間的交互&#xff0c;從而降低對象間的…
閱讀更多...
Upload-Labs通關全攻略詳細版

Upload-Labs通關全攻略詳細版

前端校驗繞過：pass 01 兩種思路：1.通過抓包，修改后綴 2.前端禁用js繞過前端后綴檢驗 首先寫一個木馬，改為圖片格式GIF89a<?php eval($_POST[cmd])?>抓包之后改為PHP格式： 使用蟻劍連接木馬，第一次嘗試一直是返回數據為空，原因是沒有鏈接到木馬，于是尋找木馬地址…
閱讀更多...
C#觀察者模式示例代碼

C#觀察者模式示例代碼

using System; using System.Collections.Generic; using System.Threading;namespace RefactoringGuru.DesignPatterns.Observer.Conceptual {// Observer觀察者 也可以叫做訂閱者 subscriberspublic interface IObserver{// Receive update from subject// 接收來自主題的更新…
閱讀更多...
電子電子架構 --- 軟件項目的開端：裁剪

電子電子架構 --- 軟件項目的開端：裁剪

我是穿拖鞋的漢子，魔都中堅持長期主義的汽車電子工程師。 老規矩，分享一段喜歡的文字，避免自己成為高知識低文化的工程師： 簡單，單純，喜歡獨處，獨來獨往，不易合同頻過著接地氣的生活，除了生存溫飽問題之外，沒有什么過多的欲望，表面看起來很高冷，內心熱情，如果你身…
閱讀更多...
Open CV圖像基本操作可莉版

Open CV圖像基本操作可莉版

Open CV圖像基本操作一、處理單個像素值訪問像素值修改像素值二、處理單個ROI區域&#xff08;自選區域&#xff09;提取 ROI修改 ROI三、 處理圖像通道通道分離通道合并四、處理整體圖像縮放圖像旋轉圖像平移圖像翻轉一、處理單個像素值 圖像是由像素組成的矩陣&#xff0c;每…
閱讀更多...
k8s:將打包好的 Kubernetes 集群鏡像推送到Harbor私有鏡像倉庫

k8s:將打包好的 Kubernetes 集群鏡像推送到Harbor私有鏡像倉庫

本文介紹了在離線環境中部署Harbor鏡像倉庫的完整流程。首先通過腳本創建多個Harbor項目&#xff0c;然后使用KubeKey工具將預打包的Kubernetes鏡像(kubesphere.tar.gz)推送到Harbor倉庫。接著配置containerd以支持從私有倉庫拉取鏡像&#xff0c;包括設置TLS證書和鏡像倉庫端點…
閱讀更多...
IntelliJ IDEA中管理多版本Git子模塊的完整指南

IntelliJ IDEA中管理多版本Git子模塊的完整指南

1.背景介紹項目是父子工程。父工程XXX-ZZZ-CCC。子模塊XXX-api在線上git網站管理,有多個分支版本。現在需要接收別人代碼&#xff0c;導入到本機管理。可以實現本機切換&#xff0c;修改&#xff0c;上傳。2.創建本地倉庫并拉取所有版本2.1.創建目錄在D:\ideaworkspace\midend-…
閱讀更多...
Android ADB命令之內存統計與分析

Android ADB命令之內存統計與分析

一、核心命令總覽工具 / 命令用途示例adb shell dumpsys meminfo查看設備全局內存狀態adb shell dumpsys meminfoadb shell dumpsys meminfo <package>獲取應用詳細內存分類統計adb shell dumpsys meminfo com.example.appadb shell top動態查看進程內存和 CPU 占用adb s…
閱讀更多...
算法思維進階 力扣 300.最長遞增子序列 暴力搜索 記憶化搜索 DFS 動態規劃 C++詳細算法解析 每日一題

算法思維進階 力扣 300.最長遞增子序列 暴力搜索 記憶化搜索 DFS 動態規劃 C++詳細算法解析 每日一題

目錄零、題目描述一、為什么這道題值得你深入理解&#xff1f;二、題目拆解&#xff1a;提取核心關鍵點三、明確思路&#xff1a;從暴力到優化的完整進化3. 進一步優化&#xff1a;動態規劃&#xff08;自底向上遞推&#xff09;4. 終極優化&#xff1a;貪心 二分查找&#xf…
閱讀更多...
圖解網絡-小林coding筆記（持續更新）

圖解網絡-小林coding筆記（持續更新）

大綱 #mermaid-svg-trl6Q4B1uDO1z05w {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-trl6Q4B1uDO1z05w .error-icon{fill:#552222;}#mermaid-svg-trl6Q4B1uDO1z05w .error-text{fill:#552222;stroke:#552222;}#merm…
閱讀更多...
最新文章

Copyright @ 2022~2023