C語言順序表的基本結(jié)構(gòu)與實現(xiàn)思路詳解
一、順序表的概念與結(jié)構(gòu)
1.線性表的解釋
首先我們在這里引入線性表的概念。線性表是n個具有相同特性的數(shù)據(jù)元素的有限序列。線性表是一種在實際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)。
常見的線性表：順序表、鏈表、棧、隊列、字符串……
線性表在邏輯上是線性結(jié)構(gòu)，也就是說是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲時，通常以數(shù)據(jù)和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲。
順序表就是線性表的一種，我們在這里詳細(xì)解釋一下順序表的實現(xiàn)，后續(xù)我們會更新鏈表等內(nèi)容。
2.順序表概念解釋
順序表是用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲。在數(shù)組上完成增刪查改。
而順序表一般可分為：
- 靜態(tài)順序表：使用定長數(shù)組存儲。
- 動態(tài)順序表：使用動態(tài)開辟的數(shù)組存儲。
二、順序表的思路及代碼實現(xiàn)詳解
1.靜態(tài)順序表的實現(xiàn)
我們先想出來一個靜態(tài)表整體的模板思路：
- 定義一個結(jié)構(gòu)體，該結(jié)構(gòu)體包含一個可以存放數(shù)據(jù)的數(shù)組和記錄數(shù)組中有效數(shù)字的變量。
- 初始化結(jié)構(gòu)體。
- 打印結(jié)構(gòu)體。
- 頭插。
- 尾插。
- 頭刪。
- 尾刪。
- 任意位置插入。
- 任意位置刪除。
這里需要有一點注意的是，我們在定義結(jié)構(gòu)體中的數(shù)組時，我們可以用typedef進行變量名簡化，這也方便我們后期更改存儲類型的時候直接更改typedef處就行。同時我們會想到數(shù)組的大小需要define定義一個宏，這樣大大提高了代碼后期的可維護性。
但是我們仔細(xì)想一下，假如我們存儲的數(shù)據(jù)滿了，我們想要繼續(xù)存儲的話還要找到源碼進行更改大小。每次存儲滿了，都要更改。那是不是太麻煩了，且效率很低。這時候我們就聯(lián)想到了動態(tài)的順序表，可以自動開辟空間，從而大大提高效率。
這里我就給出大家靜態(tài)順序表定義及接口的代碼，不再詳細(xì)解釋接口的實現(xiàn)了。我們這里詳細(xì)解釋一下動態(tài)順序表的解釋。靜態(tài)順序表接口的實現(xiàn)與動態(tài)順序表接口實現(xiàn)大同小異，可參考動態(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.動態(tài)順序表思路及代碼實現(xiàn)
2.1 動態(tài)順序表的整體思路
動態(tài)順序表的思路與靜態(tài)大致相同，但也有所不同，我來給大家詳細(xì)解釋一下。我們先看動態(tài)順序表的整體思路模板：
- 定義一個結(jié)構(gòu)體，該結(jié)構(gòu)體包含一個可以存放數(shù)據(jù)的動態(tài)數(shù)組和記錄數(shù)組中有效數(shù)據(jù)的變量，兩外還需要一個變量記錄當(dāng)前數(shù)組的大小。
- 初始化結(jié)構(gòu)體。
- 打印結(jié)構(gòu)體。
- 檢查數(shù)組容量
- 頭插。
- 尾插。
- 頭刪。
- 尾刪。
- 任意位置插入。
- 任意位置刪除。
- 釋放動態(tài)數(shù)組空間
我們上面提到了動態(tài)的數(shù)組，需要用malloc或realloc動態(tài)開辟空間。由于是動態(tài)開辟的，我們這里多了一項釋放動態(tài)開辟的空間。注意，記錄數(shù)組的有效數(shù)據(jù)和數(shù)組大小并不相同。有效數(shù)據(jù)是已經(jīng)存儲的數(shù)據(jù)個數(shù)，而數(shù)組大小是指最能夠存儲數(shù)組的個數(shù)。我們?yōu)槭裁匆涗洈?shù)組的大小呢？這里是用來判斷是否存儲滿了，滿了話要開辟空間。
我們來詳細(xì)看一下每個接口的實現(xiàn)。
2.2 定義結(jié)構(gòu)體的實現(xiàn)
在定義結(jié)構(gòu)體時，我們可以用typedef進行數(shù)組類型簡化，同時方便我們后期更改存儲類型的時候直接更改typedef處即可。同時我們也用typedef進行結(jié)構(gòu)體類型簡化，方便我們以后編輯代碼。我們來看一下代碼的實現(xiàn)：
typedef int SQDataType;
struct SeqList
{
SQDataType* a;
int size;
int capacity;
};
typedef struct SeqList SL;通過上面的代碼我們可以發(fā)現(xiàn)，當(dāng)我們不想存儲int型數(shù)據(jù)時，我們只需把‘typedef int SQDataType’改為‘typedef doubleSQDataType’即可。極大的提高了代碼的維護性。
2.3 初始化結(jié)構(gòu)體
我們初始化結(jié)構(gòu)體時，可以先將數(shù)組置空，我們后期插入數(shù)據(jù)時可再開辟空間。同時當(dāng)然有效數(shù)據(jù)和數(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)體打印方便我們觀察對動態(tài)數(shù)組的操作。打印的時數(shù)組的有效數(shù)據(jù)的內(nèi)容。我們來看代碼的實現(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ì)想一想，是不是在插入每個數(shù)據(jù)之前都要檢查數(shù)組是否已經(jīng)滿了。如果滿了，則需要增容。如果沒有滿，就插入數(shù)據(jù)即可。在這里我們需要實現(xiàn)頭插、尾插、任意插入三個接口，所以我們就把檢查數(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ù)組的時候把數(shù)組指針置空了。在動態(tài)順序表中我們增容一般會擴大到原來的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ù)組尾部插入一個數(shù)據(jù)即可。我們看一下代碼的實現(xiàn)。
void SeqListPushBack(SL* ps, SQDataType x)
{
SQLCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}2.8 頭刪
刪除時我們也有要注意的一點，就是檢查數(shù)組中是否有元素給我們刪除。頭刪的思想就是除去數(shù)組的第一個元素，我們將后面的元素整體向前移動一位，將第一位給覆蓋了。我們來看代碼。
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ù)減一即可。我們看一下代碼的實現(xiàn)。
void SeqListPopBack(SL* ps)
{
assert(ps->size > 0);
ps->size--;
}2.10 任意刪除
在任意刪除時，我們首先要判斷刪除的位置是否合理，不能違背順序表的規(guī)則。同樣，在尾刪之前，我們要檢查數(shù)組中是否有元素給我們刪除。任意刪除就是我們指出刪除位置的下標(biāo)進行刪除。當(dāng)然，我們想要刪除數(shù)組中指定元素時，我們可以先查出元素下標(biāo)在進行刪除。這個相對來說較復(fù)雜一點，我們結(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 任意插入
在任意插入時時，我們也要判斷插入的位置是否合理，不能違背順序表的規(guī)則。插入時，我們不能忘記檢查數(shù)組是否滿了。任意插入的思想與任意刪除的思想基本相同。任意插入的思想就是在我們指出刪除位置的下標(biāo)進行插入。我們看一下代碼實現(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ù)組是動態(tài)開辟的，所以當(dāng)我們不用時，我們要及時釋放掉動態(tài)開辟的空間，避免內(nèi)存泄漏。同時我們要把數(shù)組指針再次置空，避免產(chǎn)生野指針。我們看代碼實現(xiàn)。
void SeqListDestory(SL* ps)
{
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}三、順序表代碼整合
由于代碼量相對來說有一點多，所以我們就將函數(shù)的聲明的定義分開，這樣有利于提高代碼的可讀性，同時會保持一個良好的思路，且方便編寫代碼。
我們將函數(shù)的聲明放在單獨的一個SeqList.h的頭文件，函數(shù)的實現(xiàn)放在一個單獨的SeqList.c源文件，函數(shù)的主方法及調(diào)用放在另一個單獨的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++;
}
//任意刪——刪除下標(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)與實現(xiàn)思路詳解的文章就介紹到這了,更多相關(guān)C語言順序表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家介紹了C語言的循環(huán)小練習(xí)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01
這里嘗試通過C++來實現(xiàn)一個文件IO的功能，看看是否能夠比python的表現(xiàn)更好一些,感興趣的朋友可以參考下2021-05-05
重載函數(shù)是完全不同的幾個函數(shù),有不同的函數(shù)地址,下面這篇文章主要給大家介紹了關(guān)于如何使用C++獲取指定的重載函數(shù)地址的相關(guān)資料,文中通過實例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-06-06
在C++中，decltype作為操作符，用于查詢表達式的數(shù)據(jù)類型。decltype在C++11標(biāo)準(zhǔn)制定時引入，主要是為泛型編程而設(shè)計，以解決泛型編程中，由于有些類型由模板參數(shù)決定，而難以（甚至不可能）表示之的問題。2016-03-03
這篇文章主要為大家詳細(xì)介紹了Qt中QTreeWidget使用的相關(guān)資料，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)Qt有一定的幫助，感興趣的小伙伴可以了解一下2022-12-12
這篇文章主要為大家詳細(xì)介紹了用C語言實現(xiàn)簡易通訊錄，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-02-02
這篇文章主要為大家詳細(xì)介紹了QT自定義之滑動開關(guān)效果，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-08-08
在進行文本檢測時，我們常常會用矩形邊框?qū)z測到的內(nèi)容框除。這篇文章主要為大家介紹的是OpenCV中能實現(xiàn)這一效果的函數(shù)：boundingRect，感興趣的同學(xué)可以學(xué)習(xí)一下2021-12-12
這篇文章主要介紹了C++簡單輸出鉆石菱形圖效果,涉及C++簡單的數(shù)組操作與圖形打印技巧,需要的朋友可以參考下2016-05-05
文章介紹了兩種判斷回文串的方法：解法一通過創(chuàng)建新字符串來處理,解法二在原字符串上直接篩選判斷,兩種方法都使用了雙指針法,文中通過代碼示例講解的非常詳細(xì),需要的朋友可以參考下2025-03-03