系列文章目錄
文章目錄
前言
?作者簡介：大家好，我是橘橙黃又青，一個想要與大家共同進步的男人????
??個人主頁：橘橙黃又青-CSDN博客
今天開始我們正式進入數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)了，這篇簡單了解一下：
- 線性表的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)；
- 順序表的定義：用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)；
- 順序表的分類：靜態(tài)順序表、動態(tài)順序表；
- 順序表的增刪查改的實現(xiàn)。
簡單了解，通訊錄具備增加、刪除、修改、查找聯(lián)系?等操作。
1.??線性表
在這里我們先了解一下線性表
線性表（ linear list ）是n個具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是?種在實際中?泛使?的數(shù)據(jù)結(jié)構(gòu)，常?的線性表：順序表、鏈表、棧、隊列、字符串...線性表在邏輯上是線性結(jié)構(gòu)，也就說是連續(xù)的?條直線。但是在物理結(jié)構(gòu)上并不?定是連續(xù)的 ， 線性表在物理上存儲時，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲。
?怎么理解，舉一個例子：
生動形象。線性表的存儲結(jié)構(gòu)有順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)兩種。前者稱為順序表，后者稱為鏈表：
其中，線性表在邏輯上是線性結(jié)構(gòu)，也就說是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲時，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲。
2.??什么是順序表？
2.1???順序表定義
順序表（Sequential List）：用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)。一般情況下采用數(shù)組存儲。在數(shù)組上完成數(shù)據(jù)的增刪查改。
?
3.??順序表分類
3.1??靜態(tài)順序表
代碼：
//靜態(tài)順序表 —— 使用定長數(shù)組存儲元素（不實用）
#define N 7//存儲單元初始分配量
typedef int SLDataType;//SLDataType類型根據(jù)實際情況而定，這里是int
typedef struct SeqList
{
SLDataType a[N];//定長數(shù)組
int size;//有效數(shù)據(jù)的個數(shù)
}SL;?圖解：
靜態(tài)順序表
缺陷：空間給少了不夠?，給多了造成空間浪費 ?
優(yōu)點：訪問數(shù)據(jù)快速，由于是連續(xù)存儲，所以可以直接通過下標(biāo)訪問元素，效率高。
3.2??動態(tài)順序表
代碼：
typedef int SLDataType;//SLDataType類型根據(jù)實際情況而定，這里是int
typedef struct SeqList
{
SLDataType* a;
int size;//有效數(shù)據(jù)的個數(shù)
int capacity;//空間容量
}SL;圖解：?
?動態(tài)順序表
?優(yōu)點：可以使用指針動態(tài)地分配內(nèi)存，具有高效的存儲和訪問效率。
?缺點：在插入和刪除元素時需要移動大量的數(shù)據(jù)，效率較低。
4.??順序表的基本操作
通過上面的學(xué)習(xí)我們已經(jīng)初步了解動態(tài)順序表，與靜態(tài)順序表相比動態(tài)的使用更為靈活，可以避免
空間給少了不夠?，給多了造成空間浪費的問題，合理開辟空間。接下來我們也是用動態(tài)順序表來實現(xiàn)基本操作。
分裝函數(shù)：
?4.1??動態(tài)順序表結(jié)構(gòu)體創(chuàng)建
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* arr; //存儲數(shù)據(jù)的底層結(jié)構(gòu)
int capacity; //記錄順序表的空間大小
int size; //記錄順序表當(dāng)前有效的數(shù)據(jù)個數(shù)
}SL;代碼解析：
- 結(jié)構(gòu)體中?
a?指向的數(shù)組類型是我們重定義的SLDataType，這樣當(dāng)我們想創(chuàng)建其它類型的順序表時只需要對?typedef?后面的類型進行需改即可； -
size是用來計數(shù)的，統(tǒng)計當(dāng)前順序表一共有多少個有效元素； -
capacity是用來表示當(dāng)前順序表的容量,當(dāng)capacity == size表示容量已滿。
?4.2??初始化和擴容
//初始化和擴容
void SLInit(SL* ps) {
assert(ps);
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
void SLCheckCapacity(SL* ps) {
if (ps->size == ps->capacity) {
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//如果是擴容是0，則開辟4個int空間，不是則開辟原來空間的兩倍
SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
if (tmp == NULL) {
perror("realloc fail!");
exit(1);//退出程序
}
//擴容成功
ps->arr = tmp;
ps->capacity = newCapacity;
}
}代碼深剖 ：
- 在這里我們需要使用
assert對ps進行一下斷言，以防傳入空指針 - 開辟空間，一定要進行判斷是否開辟成功，如果不進行判斷直接使用可能會導(dǎo)致程序崩潰。
?擴容思路：
?4.3??打印順序表
代碼：
//打印數(shù)據(jù)
void SLPrint(SL* ps) {
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}4.4??順序表頭部插入
代碼：
//順序表的頭部插入
void SLPushFront(SL* ps, SLDataType x) {
assert(ps);
//判斷是否擴容
SLCheckCapacity(ps);
//舊數(shù)據(jù)往后挪動一位
for (int i = ps->size; i > 0; i--) //i = 1
{
ps->arr[i] = ps->arr[i - 1]; //ps->arr[1] = ps->arr[0]
}
ps->arr[0] = x;
ps->size++;
}
圖解：
?
?4.5??頭部刪除
代碼：
//順序表的尾部刪除
void SLPopFront(SL* ps) {
assert(ps);
assert(ps->size);
//不為空執(zhí)行挪動操作
//向前面挪動覆蓋
for (int i = 0; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}圖解：
?4.6??順序表的尾部插入
尾插時需要先判斷順序表是否滿了，滿了要先進行擴容才能繼續(xù)進行擴容。size表示有效元素個數(shù)，同時也是順序表中最后一個元素的后一個位置的下標(biāo)。成功插入后要對有效數(shù)據(jù)個數(shù)size進行加1操作
代碼:
//順序表的尾部插入
void SLPushBack(SL* ps, SLDataType x) {
//斷言--粗暴的解決方式
//assert(ps != NULL);
assert(ps);
//if判斷--溫柔的解決方式
//if (ps == NULL) {
// return;
//}
//空間不夠，擴容
SLCheckCapacity(ps);
//空間足夠，直接插入
ps->arr[ps->size++] = x;
//ps->size++;
}圖解：
?
4.7??順序表尾刪
只需要有效size往前面挪一個覆蓋一個，這樣有效的數(shù)據(jù)就會少一個。
代碼：
//順序表的尾部刪除
void SLPopBack(SL* ps) {
assert(ps);
assert(ps->size);
//順序表不為空
//ps->arr[ps->size - 1] = -1;
ps->size--;
}圖解：
4.8??指定pos下標(biāo)位置插入數(shù)據(jù)
//指定位置之前插入數(shù)據(jù)
void SLInsert(SL* ps, int pos, SLDataType x) {
assert(ps);
assert(pos >= 0 && pos <= ps->size);
SLCheckCapacity(ps);
//pos及之后的數(shù)據(jù)往后挪動一位，pos空出來
for (int i = ps->size; i > pos; i--)
{
ps->arr[i] = ps->arr[i - 1]; //ps->arr[pos+1] = ps->arr[pos]
}
ps->arr[pos] = x;
ps->size++;
}圖解：
?
?4.9??指定pos下標(biāo)位置刪除數(shù)據(jù)
代碼：
//刪除指定位置數(shù)據(jù)
void SLErase(SL* ps, int pos) {
assert(ps);
assert(pos >= 0 && pos < ps->size);
//pos以后的數(shù)據(jù)往前挪動一位
for (int i = pos; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];//ps->arr[i-2] = ps->arr[i-1];
}
ps->size--;
}圖解：
?5.??項目全部代碼
5.1??SeqList.h代碼
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//靜態(tài)順序表
//#define N 100
//struct SeqList
//{
// SLDataType a[N];
// int size;
//};
//動態(tài)順序表
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* arr; //存儲數(shù)據(jù)的底層結(jié)構(gòu)
int capacity; //記錄順序表的空間大小
int size; //記錄順序表當(dāng)前有效的數(shù)據(jù)個數(shù)
}SL;
//typedef struct SeqList SL;
//初始化和銷毀
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps); //保持接口一致性
//順序表的頭部/尾部插入
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);
//順序表的頭部/尾部刪除
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);
//指定位置之前插入數(shù)據(jù)
//刪除指定位置數(shù)據(jù)
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);5.2??seqlist.c代碼
#include"SeqList.h"
//初始化和擴容
void SLInit(SL* ps) {
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
void SLCheckCapacity(SL* ps) {
if (ps->size == ps->capacity) {
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
if (tmp == NULL) {
perror("realloc fail!");
exit(1);//退出程序
}
//擴容成功
ps->arr = tmp;
ps->capacity = newCapacity;
}
}
//順序表的尾部插入
void SLPushBack(SL* ps, SLDataType x) {
//斷言--粗暴的解決方式
//assert(ps != NULL);
assert(ps);
//if判斷--溫柔的解決方式
//if (ps == NULL) {
// return;
//}
//空間不夠，擴容
SLCheckCapacity(ps);
//空間足夠，直接插入
ps->arr[ps->size++] = x;
//ps->size++;
}
//順序表的頭部插入
void SLPushFront(SL* ps, SLDataType x) {
assert(ps);
//判斷是否擴容
SLCheckCapacity(ps);
//舊數(shù)據(jù)往后挪動一位
for (int i = ps->size; i > 0; i--) //i = 1
{
ps->arr[i] = ps->arr[i - 1]; //ps->arr[1] = ps->arr[0]
}
ps->arr[0] = x;
ps->size++;
}
//順序表的尾部刪除
void SLPopBack(SL* ps) {
assert(ps);
assert(ps->size);
//順序表不為空
//ps->arr[ps->size - 1] = -1;
ps->size--;
}
//順序表的尾部刪除
void SLPopFront(SL* ps) {
assert(ps);
assert(ps->size);
//不為空執(zhí)行挪動操作
//向前面挪動覆蓋
for (int i = 0; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}
//指定位置之前插入數(shù)據(jù)
void SLInsert(SL* ps, int pos, SLDataType x) {
assert(ps);
assert(pos >= 0 && pos <= ps->size);
SLCheckCapacity(ps);
//pos及之后的數(shù)據(jù)往后挪動一位，pos空出來
for (int i = ps->size; i > pos; i--)
{
ps->arr[i] = ps->arr[i - 1]; //ps->arr[pos+1] = ps->arr[pos]
}
ps->arr[pos] = x;
ps->size++;
}
//刪除指定位置數(shù)據(jù)
void SLErase(SL* ps, int pos) {
assert(ps);
assert(pos >= 0 && pos < ps->size);
//pos以后的數(shù)據(jù)往前挪動一位
for (int i = pos; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];//ps->arr[i-2] = ps->arr[i-1];
}
ps->size--;
}
//打印數(shù)據(jù)
void SLPrint(SL* ps) {
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}5.3??test.c代碼
用來測試結(jié)果：
#include"SeqList.h"
void slTest01() {
SL sl;
SLInit(&sl);
//測試代碼
//
//順序表的尾部插入
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);//ctrl+d?
SLPushBack(&sl, 4);
//打印
SLPrint(&sl); //1 2 3 4
順序表的尾部插入
//SLPushBack(&sl, 5);
//SLPrint(&sl);
順序表的頭部插入
//SLPushFront(&sl, 5);
//SLPushFront(&sl, 6);
//SLPushFront(&sl, 7);
//SLPrint(&sl); //7 6 5 1 2 3 4
//順序表的尾部刪除
//SLPopBack(&sl);
//SLPopBack(&sl);
//SLPrint(&sl); //1 2
//順序表的頭部刪除
//SLPopFront(&sl);
//SLPopFront(&sl);
//SLPopFront(&sl);
//SLPopFront(&sl);
//SLPopFront(&sl);
//SLPrint(&sl); //3 4
//指定位置之前插入數(shù)據(jù)
//SLInsert(&sl, 0, 100);
//SLPrint(&sl); //100 1 2 3 4
//SLInsert(&sl, sl.size, 200);
//SLPrint(&sl); //100 1 2 3 4 200
//SLInsert(&sl, 100, 300);
//SLPrint(&sl);
//刪除指定位置數(shù)據(jù)
//SLErase(&sl, 0);
//SLPrint(&sl); //2 3 4
//SLErase(&sl, sl.size - 1);
SLErase(&sl, 1);
SLPrint(&sl);//1 3 4
}
int main()
{
slTest01();
return 0;
}?test.c里面的測試代碼，有需要的小伙伴可以解開來試一試文章來源：http://www.zghlxwxcb.cn/news/detail-822513.html
好啦，今天就到這里了，都看到這里了，點一個贊吧，感謝觀看。文章來源地址http://www.zghlxwxcb.cn/news/detail-822513.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)-＞順序表實戰(zhàn)指南，（手把手教會你拿捏數(shù)據(jù)結(jié)構(gòu)順序表）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
