C語言順序表的基本結(jié)構(gòu)與實(shí)現(xiàn)思路詳解
一、順序表的概念與結(jié)構(gòu)
1.線性表的解釋
首先我們在這里引入線性表的概念。線性表是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)。
常見的線性表：順序表、鏈表、棧、隊(duì)列、字符串……
線性表在邏輯上是線性結(jié)構(gòu)，也就是說是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲(chǔ)時(shí)，通常以數(shù)據(jù)和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲(chǔ)。
順序表就是線性表的一種，我們在這里詳細(xì)解釋一下順序表的實(shí)現(xiàn)，后續(xù)我們會(huì)更新鏈表等內(nèi)容。
2.順序表概念解釋
順序表是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲(chǔ)。在數(shù)組上完成增刪查改。
而順序表一般可分為：
- 靜態(tài)順序表：使用定長數(shù)組存儲(chǔ)。
- 動(dòng)態(tài)順序表：使用動(dòng)態(tài)開辟的數(shù)組存儲(chǔ)。
二、順序表的思路及代碼實(shí)現(xiàn)詳解
1.靜態(tài)順序表的實(shí)現(xiàn)
我們先想出來一個(gè)靜態(tài)表整體的模板思路：
- 定義一個(gè)結(jié)構(gòu)體，該結(jié)構(gòu)體包含一個(gè)可以存放數(shù)據(jù)的數(shù)組和記錄數(shù)組中有效數(shù)字的變量。
- 初始化結(jié)構(gòu)體。
- 打印結(jié)構(gòu)體。
- 頭插。
- 尾插。
- 頭刪。
- 尾刪。
- 任意位置插入。
- 任意位置刪除。
這里需要有一點(diǎn)注意的是，我們在定義結(jié)構(gòu)體中的數(shù)組時(shí)，我們可以用typedef進(jìn)行變量名簡化，這也方便我們后期更改存儲(chǔ)類型的時(shí)候直接更改typedef處就行。同時(shí)我們會(huì)想到數(shù)組的大小需要define定義一個(gè)宏，這樣大大提高了代碼后期的可維護(hù)性。
但是我們仔細(xì)想一下，假如我們存儲(chǔ)的數(shù)據(jù)滿了，我們想要繼續(xù)存儲(chǔ)的話還要找到源碼進(jìn)行更改大小。每次存儲(chǔ)滿了，都要更改。那是不是太麻煩了，且效率很低。這時(shí)候我們就聯(lián)想到了動(dòng)態(tài)的順序表，可以自動(dòng)開辟空間，從而大大提高效率。
這里我就給出大家靜態(tài)順序表定義及接口的代碼，不再詳細(xì)解釋接口的實(shí)現(xiàn)了。我們這里詳細(xì)解釋一下動(dòng)態(tài)順序表的解釋。靜態(tài)順序表接口的實(shí)現(xiàn)與動(dòng)態(tài)順序表接口實(shí)現(xiàn)大同小異，可參考動(dòng)態(tài)順序表接口的詳解。
代碼如下：
#define MAX_SIZE 10
typedef int SQDataType;
typedef struct SeqList
{
SQDataType a[MAX_SIZE];
int size;
}SL;
//typedef struct SeqList SL;
typedef struct SeqList SL;
//初始化結(jié)構(gòu)體
void SeqListInit(SL* ps);
//打印
void SeqListPrint(SL s);
//尾插
void SeqListPushBack(SL* ps, SQDataType x);
//尾刪
void SeqListPopBack(SL* ps);
//頭插
void SeqListPushFrint(SL* ps, SQDataType x);
//頭刪
void SeqListPopFrint(SL* ps);
//查找位置
int SeqListFind(SL s, SQDataType x);
//任意插入
void SeqListInsert(SL* ps, int pos, SQDataType x);
//任意刪
void SeqListErase(SL* ps, int pos);2.動(dòng)態(tài)順序表思路及代碼實(shí)現(xiàn)
2.1 動(dòng)態(tài)順序表的整體思路
動(dòng)態(tài)順序表的思路與靜態(tài)大致相同，但也有所不同，我來給大家詳細(xì)解釋一下。我們先看動(dòng)態(tài)順序表的整體思路模板：
- 定義一個(gè)結(jié)構(gòu)體，該結(jié)構(gòu)體包含一個(gè)可以存放數(shù)據(jù)的動(dòng)態(tài)數(shù)組和記錄數(shù)組中有效數(shù)據(jù)的變量，兩外還需要一個(gè)變量記錄當(dāng)前數(shù)組的大小。
- 初始化結(jié)構(gòu)體。
- 打印結(jié)構(gòu)體。
- 檢查數(shù)組容量
- 頭插。
- 尾插。
- 頭刪。
- 尾刪。
- 任意位置插入。
- 任意位置刪除。
- 釋放動(dòng)態(tài)數(shù)組空間
我們上面提到了動(dòng)態(tài)的數(shù)組，需要用malloc或realloc動(dòng)態(tài)開辟空間。由于是動(dòng)態(tài)開辟的，我們這里多了一項(xiàng)釋放動(dòng)態(tài)開辟的空間。注意，記錄數(shù)組的有效數(shù)據(jù)和數(shù)組大小并不相同。有效數(shù)據(jù)是已經(jīng)存儲(chǔ)的數(shù)據(jù)個(gè)數(shù)，而數(shù)組大小是指最能夠存儲(chǔ)數(shù)組的個(gè)數(shù)。我們?yōu)槭裁匆涗洈?shù)組的大小呢？這里是用來判斷是否存儲(chǔ)滿了，滿了話要開辟空間。
我們來詳細(xì)看一下每個(gè)接口的實(shí)現(xiàn)。
2.2 定義結(jié)構(gòu)體的實(shí)現(xiàn)
在定義結(jié)構(gòu)體時(shí)，我們可以用typedef進(jìn)行數(shù)組類型簡化，同時(shí)方便我們后期更改存儲(chǔ)類型的時(shí)候直接更改typedef處即可。同時(shí)我們也用typedef進(jìn)行結(jié)構(gòu)體類型簡化，方便我們以后編輯代碼。我們來看一下代碼的實(shí)現(xiàn)：
typedef int SQDataType;
struct SeqList
{
SQDataType* a;
int size;
int capacity;
};
typedef struct SeqList SL;通過上面的代碼我們可以發(fā)現(xiàn)，當(dāng)我們不想存儲(chǔ)int型數(shù)據(jù)時(shí)，我們只需把‘typedef int SQDataType’改為‘typedef doubleSQDataType’即可。極大的提高了代碼的維護(hù)性。
2.3 初始化結(jié)構(gòu)體
我們初始化結(jié)構(gòu)體時(shí)，可以先將數(shù)組置空，我們后期插入數(shù)據(jù)時(shí)可再開辟空間。同時(shí)當(dāng)然有效數(shù)據(jù)和數(shù)組大小都要初始化成零。我們看代碼的實(shí)現(xiàn)。
void SeqListInit(SL* ps)
{
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
}我們這里是改變了結(jié)構(gòu)體的內(nèi)容，所以需要傳地址，用指針變量來接收。
2.4 結(jié)構(gòu)體打印
結(jié)構(gòu)體打印方便我們觀察對動(dòng)態(tài)數(shù)組的操作。打印的時(shí)數(shù)組的有效數(shù)據(jù)的內(nèi)容。我們來看代碼的實(shí)現(xiàn)。
void SeqListPrint(SL s)
{
int i = 0;
for (i = 0; i < s.size; i++)
{
printf("%d ", s.a[i]);
}
printf("\n");
}2.5 檢查數(shù)組容量
我們仔細(xì)想一想，是不是在插入每個(gè)數(shù)據(jù)之前都要檢查數(shù)組是否已經(jīng)滿了。如果滿了，則需要增容。如果沒有滿，就插入數(shù)據(jù)即可。在這里我們需要實(shí)現(xiàn)頭插、尾插、任意插入三個(gè)接口，所以我們就把檢查數(shù)組容量單獨(dú)分裝一個(gè)函數(shù)，這樣提高代碼的簡潔性。我們看一下代碼的實(shí)現(xiàn)。
void SQLCheckCapacity(SL* ps)
{
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SQDataType* tmp =(SQDataType*)realloc(ps->a, sizeof(SQDataType) * newcapacity);
if (tmp == NULL)
{
printf("realloc failed\n");
exit(-1);
}
ps->capacity = newcapacity;
ps->a = tmp;
}
}當(dāng)我們檢查增容時(shí)，我們還要判斷一下之前的數(shù)組大小是否為零，如果是零的話，我們要給其賦一個(gè)值。因?yàn)槲覀儎傞_始初始化數(shù)組的時(shí)候把數(shù)組指針置空了。在動(dòng)態(tài)順序表中我們增容一般會(huì)擴(kuò)大到原來的2倍。
2.6 頭插
在插入之前要判斷數(shù)組是否已經(jīng)滿了。頭插的思想就是把數(shù)組的內(nèi)容整體后移一位，我們把要插入的數(shù)據(jù)放在第一位。我們結(jié)合著代碼一起理解。
void SeqListPushFrint(SL* ps, SQDataType x)
{
SQLCheckCapacity(ps);
int end = ps->size - 1;
while (end >= 0)
{
ps->a[end+1] = ps->a[end];
end--;
}
ps->a[0] = x;
ps->size++;
}2.7 尾插
同樣， 在插入之前要判斷數(shù)組是否已經(jīng)滿了。尾插的思想很簡單。就是直接在數(shù)組尾部插入一個(gè)數(shù)據(jù)即可。我們看一下代碼的實(shí)現(xiàn)。
void SeqListPushBack(SL* ps, SQDataType x)
{
SQLCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}2.8 頭刪
刪除時(shí)我們也有要注意的一點(diǎn)，就是檢查數(shù)組中是否有元素給我們刪除。頭刪的思想就是除去數(shù)組的第一個(gè)元素，我們將后面的元素整體向前移動(dòng)一位，將第一位給覆蓋了。我們來看代碼。
void SeqListPopFrint(SL* ps)
{
assert(ps->size > 0);
int i = 0;
for (i = 0; i < ps->size - 1; i++)
{
ps->a[i] = ps->a[i + 1];
}
ps->size--;
}2.9 尾刪
同樣，在尾刪之前，我們要檢查數(shù)組中是否有元素給我們刪除。尾刪的思想十分簡單，就是把數(shù)組的有效數(shù)據(jù)減一即可。我們看一下代碼的實(shí)現(xiàn)。
void SeqListPopBack(SL* ps)
{
assert(ps->size > 0);
ps->size--;
}2.10 任意刪除
在任意刪除時(shí)，我們首先要判斷刪除的位置是否合理，不能違背順序表的規(guī)則。同樣，在尾刪之前，我們要檢查數(shù)組中是否有元素給我們刪除。任意刪除就是我們指出刪除位置的下標(biāo)進(jìn)行刪除。當(dāng)然，我們想要?jiǎng)h除數(shù)組中指定元素時(shí)，我們可以先查出元素下標(biāo)在進(jìn)行刪除。這個(gè)相對來說較復(fù)雜一點(diǎn)，我們結(jié)合著代碼理解一下。
//查找位置
int SeqListFind(SL s, SQDataType x)
{
int i = 0;
for (i = 0; i < s.size; i++)
{
if (s.a[i] == x)
{
return i;
}
}
return -1;
}
void SeqListErase(SL* ps, int pos)
{
assert(pos >= 0 && pos < ps->size);
int begin = pos + 1;
while (begin < ps->size)
{
ps->a[begin - 1] = ps->a[begin];
begin++;
}
ps->size--;
}2.11 任意插入
在任意插入時(shí)時(shí)，我們也要判斷插入的位置是否合理，不能違背順序表的規(guī)則。插入時(shí)，我們不能忘記檢查數(shù)組是否滿了。任意插入的思想與任意刪除的思想基本相同。任意插入的思想就是在我們指出刪除位置的下標(biāo)進(jìn)行插入。我們看一下代碼實(shí)現(xiàn)。
void SeqListInsert(SL* ps, int pos, SQDataType x)
{
assert(pos >= 0 && pos <= ps->size);
SQLCheckCapacity(ps);
int end = ps->size-1;
while (end >= pos)
{
ps->a[end+1] = ps->a[end];
end--;
}
ps->a[pos] = x;
ps->size++;
}2.12 空間釋放
由于我們的數(shù)組是動(dòng)態(tài)開辟的，所以當(dāng)我們不用時(shí)，我們要及時(shí)釋放掉動(dòng)態(tài)開辟的空間，避免內(nèi)存泄漏。同時(shí)我們要把數(shù)組指針再次置空，避免產(chǎn)生野指針。我們看代碼實(shí)現(xiàn)。
void SeqListDestory(SL* ps)
{
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}三、順序表代碼整合
由于代碼量相對來說有一點(diǎn)多，所以我們就將函數(shù)的聲明的定義分開，這樣有利于提高代碼的可讀性，同時(shí)會(huì)保持一個(gè)良好的思路，且方便編寫代碼。
我們將函數(shù)的聲明放在單獨(dú)的一個(gè)SeqList.h的頭文件，函數(shù)的實(shí)現(xiàn)放在一個(gè)單獨(dú)的SeqList.c源文件，函數(shù)的主方法及調(diào)用放在另一個(gè)單獨(dú)的test.c源文件。
SeqList.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SQDataType;
struct SeqList
{
SQDataType* a;
int size;
int capacity;
};
typedef struct SeqList SL;
//初始化結(jié)構(gòu)體
void SeqListInit(SL* ps);
//打印
void SeqListPrint(SL s);
//尾插
void SeqListPushBack(SL* ps, SQDataType x);
//尾刪
void SeqListPopBack(SL* ps);
//頭插
void SeqListPushFrint(SL* ps, SQDataType x);
//頭刪
void SeqListPopFrint(SL* ps);
//查找位置
int SeqListFind(SL s, SQDataType x);
//任意插入
void SeqListInsert(SL* ps, int pos, SQDataType x);
//任意刪
void SeqListErase(SL* ps, int pos);
//銷毀空間
void SeqListDestory(SL* ps);SeqList.c
#include"SeqList.h"
//初始化結(jié)構(gòu)體
void SeqListInit(SL* ps)
{
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
}
//打印
void SeqListPrint(SL s)
{
int i = 0;
for (i = 0; i < s.size; i++)
{
printf("%d ", s.a[i]);
}
printf("\n");
}
//查容增容
void SQLCheckCapacity(SL* ps)
{
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SQDataType* tmp =(SQDataType*)realloc(ps->a, sizeof(SQDataType) * newcapacity);
if (tmp == NULL)
{
printf("realloc failed\n");
exit(-1);
}
ps->capacity = newcapacity;
ps->a = tmp;
}
}
//尾插
void SeqListPushBack(SL* ps, SQDataType x)
{
SQLCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
//尾刪
void SeqListPopBack(SL* ps)
{
assert(ps->size > 0);
ps->size--;
}
//頭插
void SeqListPushFrint(SL* ps, SQDataType x)
{
SQLCheckCapacity(ps);
int end = ps->size - 1;
while (end >= 0)
{
ps->a[end+1] = ps->a[end];
end--;
}
ps->a[0] = x;
ps->size++;
}
//頭刪
void SeqListPopFrint(SL* ps)
{
assert(ps->size > 0);
int i = 0;
for (i = 0; i < ps->size - 1; i++)
{
ps->a[i] = ps->a[i + 1];
}
ps->size--;
}
//查找位置
int SeqListFind(SL s, SQDataType x)
{
int i = 0;
for (i = 0; i < s.size; i++)
{
if (s.a[i] == x)
{
return i;
}
}
return -1;
}
//任意插——在下標(biāo)為pos的位置插入數(shù)據(jù)
void SeqListInsert(SL* ps, int pos, SQDataType x)
{
assert(pos >= 0 && pos <= ps->size);
SQLCheckCapacity(ps);
int end = ps->size-1;
while (end >= pos)
{
ps->a[end+1] = ps->a[end];
end--;
}
ps->a[pos] = x;
ps->size++;
}
//任意刪——?jiǎng)h除下標(biāo)為pos的數(shù)據(jù)
void SeqListErase(SL* ps, int pos)
{
assert(pos >= 0 && pos < ps->size);
int begin = pos + 1;
while (begin < ps->size)
{
ps->a[begin - 1] = ps->a[begin];
begin++;
}
ps->size--;
}
//銷毀空間
void SeqListDestory(SL* ps)
{
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}test.c
#include"SeqList.h"
void test()
{
SL s1;
SeqListInit(&s1);
SeqListPushBack(&s1, 1);
SeqListPushFrint(&s1, 1);
SeqListPushFrint(&s1, 2);
SeqListPushFrint(&s1, 3);
SeqListPushFrint(&s1, 4);
SeqListPushBack(&s1, 5);
SeqListPrint(s1);
SeqListPopFrint(&s1);
SeqListPrint(s1);
int pos = SeqListFind(s1, 1);
SeqListInsert(&s1, pos, 10);
SeqListInsert(&s1, 0, 20);
SeqListPrint(s1);
SeqListErase(&s1, 0);
SeqListPrint(s1);
SeqListDestory(&s1);
}
int main()
{
test();
return 0;
}到此這篇關(guān)于C語言順序表的基本結(jié)構(gòu)與實(shí)現(xiàn)思路詳解的文章就介紹到這了,更多相關(guān)C語言順序表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
map是STL的一個(gè)關(guān)聯(lián)容器，它以<key,value>一對一的形式存儲(chǔ)，且map的內(nèi)部自建一個(gè)紅黑樹，使得其可以自動(dòng)排序，本文就介紹一下C++ map的簡單使用，感興趣的可以了解一下2021-05-05
C++ 中重載和運(yùn)算符重載加號實(shí)現(xiàn)矩陣相加實(shí)例代碼
這篇文章主要介紹了C++ 中重載和運(yùn)算符重載加號實(shí)現(xiàn)矩陣相加實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下2017-03-03
深入解析Radix Sort基數(shù)排序算法思想及C語言實(shí)現(xiàn)示例
基數(shù)排序和桶排序、計(jì)數(shù)排序共同是三種最常用的線性排序算法,這里我們就來深入解析Radix Sort基數(shù)排序算法思想及C語言實(shí)現(xiàn)示例,需要的朋友可以參考下2016-07-07
這篇文章主要為大家詳細(xì)介紹了基于C語言實(shí)現(xiàn)簡單掃雷游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-11-11
樸素模式匹配算法也稱為布魯特-福斯算法，感覺很是高大上，但是實(shí)現(xiàn)起來很簡單。這篇文章主要給大家介紹了關(guān)于C語言樸素模式匹配算法的相關(guān)資料,需要的朋友可以參考下2021-06-06
C++編寫DLL動(dòng)態(tài)鏈接庫的步驟與實(shí)現(xiàn)方法
這篇文章主要介紹了C++編寫DLL動(dòng)態(tài)鏈接庫的步驟與實(shí)現(xiàn)方法,結(jié)合實(shí)例形式分析了C++導(dǎo)出類文件及生成與調(diào)用DLL動(dòng)態(tài)連接庫的相關(guān)操作技巧,需要的朋友可以參考下2016-08-08
這篇文章主要給大家介紹了關(guān)于C++利用LuaIntf調(diào)用Lua以及利用lua-intf來調(diào)用C++函數(shù)的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來一起看看吧。2017-11-11![C++程序中main（int argc, char *argv[]）函數(shù)的參數(shù)意義](http://img.jbzj.com/images/xgimg/bcimg7.png)
C++程序中main（int argc, char *argv[]）函數(shù)的參數(shù)意義
這篇文章主要介紹了C++程序中main（int argc, char *argv[]）函數(shù)的參數(shù)意義,本文給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2018-09-09
這篇文章主要為大家介紹了Qt6.0?qproperty-*不生效原因解決分析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-08-08
這篇文章主要為大家介紹了C語言刷題判斷鏈表中是否有環(huán)題解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-07-07