前??言
線性表(linear list)是n個具有相同特性的數(shù)據(jù)元素的有限序列。線性表是一種在實際中廣泛使用的數(shù)據(jù)結(jié)構(gòu),常見的線性表有:順序表、鏈表、棧、隊列、字符串等
線性表在邏輯上是線性結(jié)構(gòu)(即連續(xù)的一條直線)。但在物理結(jié)構(gòu)上并不一定是連續(xù)的。線性表在物理上存儲時,通常以數(shù)組或鏈式結(jié)構(gòu)的形式存儲。
本文將要介紹的即是線性表中的順序表。
順序表是用一段物理地址連續(xù)的存儲單元依此存儲數(shù)據(jù)元素的線性結(jié)構(gòu)。一般情況下采用數(shù)組存儲。在數(shù)組上完成數(shù)據(jù)的增刪查改。
順序表一般可以分為:
● 靜態(tài)順序表:使用定長數(shù)組存儲元素
● 動態(tài)順序表:使用動態(tài)開辟的數(shù)組存儲元素
可以發(fā)現(xiàn),靜態(tài)順序表只適用于確定知道需要存多少數(shù)據(jù)的場景,使用限制較多,如果靜態(tài)順序表中的N定大了,容易造成空間浪費,定小了又會造成空間不足。因此在實際中多使用的是動態(tài)順序表,根據(jù)需要動態(tài)的分配空間大小。本文中也將主要介紹動態(tài)順序表的實現(xiàn)。
如上所說,動態(tài)順序表是通過動態(tài)開辟的數(shù)組來存儲數(shù)據(jù)的,但為了方便了解順序表的存儲情況,比如:當前表中有多少個數(shù)據(jù),當前表的容量是多少,我們還需要定義兩個變量,一個用來記錄當前表中的有效元素個數(shù),一個用來記錄當前表的容量。基于此,我們考慮用一個結(jié)構(gòu)體來表示順序表,結(jié)構(gòu)體中包含指向動態(tài)開辟的數(shù)組的指針及額外的兩個變量(size、capacity)。
🍚如下是順序表結(jié)構(gòu)體的聲明:
typedef int SLDataType; //為了適應多種類型數(shù)據(jù)的存儲,方便進行類型修改,首先對數(shù)據(jù)類型進行重命名
typedef struct SeqList {
SLDataType* data; //存儲數(shù)據(jù)
int size; //記錄表中數(shù)據(jù)個數(shù)
int capacity; // 記錄線性表容量大小
}SeqList;
🍚在使用順序表之前,首先要做的自然是順序表的初始化了,如下所示是順序表初始化接口的實現(xiàn):
//順序表初始化
void SeqListInit(SeqList* sl) {
assert(sl); //確保傳入的不是空指針,以便及時發(fā)現(xiàn)空指針訪問錯誤
sl->data = NULL; //初始化時將指向動態(tài)數(shù)組的指針先置空
sl->size = 0; //初始時表中無數(shù)據(jù)
sl->capacity = 0; //初始時可以先不開辟空間,等需要存數(shù)據(jù)時在開
}
考慮到形參是實參的一份臨時拷貝,如果直接以結(jié)構(gòu)體作為函數(shù)參數(shù),若結(jié)構(gòu)體過大,拷貝傳參時無疑會產(chǎn)生較大的消耗,因此在實現(xiàn)順序表的各個接口時,均采用結(jié)構(gòu)體指針傳參的形式,如此,調(diào)用函數(shù)時,只需要拷貝一份結(jié)構(gòu)體的指針,就可以通過指針訪問結(jié)構(gòu)體的各個成員了。
🍚為了直觀的看到順序表中的存儲情況,我們可以設(shè)計一個接口打印出順序表中的存儲內(nèi)容,以下是接口的實現(xiàn):
//順序表數(shù)據(jù)打印
void SeqListPrint(SeqList* sl) {
assert(sl);
int i = 0;
//逐個打印順序表中元素
while (i< sl->size) {
printf("%d ", sl->data[i]);
i++;
}
printf("\n");
}
🍚當我們不需要再使用順序表時,可以將順序表進行銷毀,因此我們也設(shè)計一個接口來實現(xiàn):
//順序表銷毀
void SeqListDestroy(SeqList* sl) {
assert(sl);
//如果指向動態(tài)數(shù)組的指針不為空,則通過指針釋放動態(tài)數(shù)組,并將指針置空,以防之后被誤用
if (!(sl->data)) {
free(sl->data);
sl->data = NULL;
}
sl->size = 0; //清空表中數(shù)據(jù),即表中有效數(shù)據(jù)個數(shù)歸零
sl->capacity = 0; //動態(tài)數(shù)組釋放后,表的容量自然也歸零了
}
2.2 順序表擴容🍚在開頭我們也說到了,對于動態(tài)順序表,當當前表容量不夠時是可以進行擴容的,那如何來實現(xiàn)呢?在C語言中有一個動態(tài)內(nèi)存開辟函數(shù)(realloc)可以用來擴容,以下我們就來具體實現(xiàn)一下順序表的擴容接口:
//順序表容量檢查
void SLCheckCapacity(SeqList* sl) {
assert(sl);
//當表中有效元素個數(shù)與當前表容量相等時,表示當前表已存滿數(shù)據(jù),即需要擴容
if (sl->size == sl->capacity) {
//每次擴容的大小可根據(jù)自己需求指定,這里設(shè)置的是每次擴容后,新的容量為原容量的兩倍。
//如上我們設(shè)置順序表初始化時是沒有開辟空間的,因此這里還需判斷一開始容量為0的情況,此時直接先開辟四個數(shù)據(jù)類型大小的空間
//realloc函數(shù)在參數(shù)指針為空時相當于malloc函數(shù)
int newCapacity = sl->capacity == 0 ? 4 : 2 * (sl->capacity);
SLDataType* temp = (SLDataType*)realloc(sl->data, newCapacity * sizeof(SLDataType));
//注意空間開辟失敗的情況,如果開辟失敗將返回空指針,因此這里先用臨時指針接收指向返回空間的指針,
//對空指針進行判斷,確保不會造成空指針訪問時,在將指針賦值給表中指針,同時更新容量
assert(temp);
sl->data = temp;
sl->capacity = newCapacity;
}
}
2.3 順序表尾插🍚所謂順序表尾插,即是在順序表末尾插入新元素,此時只需要確保表中還有足夠的空間可以插入數(shù)據(jù)。尾插不會影響之前的數(shù)據(jù),因此插入新元素后也不需要改變之前元素的位置,以下是接口的實現(xiàn):
//順序表尾插
void SeqListPushBack(SeqList* sl, SLDataType data) {
assert(sl);
//要想往表中插入數(shù)據(jù),首先要確定表中還有足夠的空間,否則在非開辟空間中訪問會造成數(shù)組越界問題,如果空間不夠則可以擴容
SLCheckCapacity(sl);
//經(jīng)過容量檢查后可以確保表中還有空間可以插入數(shù)據(jù),則尾插只需要將數(shù)據(jù)插入到表中現(xiàn)有所有效元素最后一位的后一個位置
//基于表中數(shù)據(jù)下標是從0開始,所以表中有效元素個數(shù)即為要進行尾插的位置(下標)
sl->data[sl->size] = data;
sl->size++; //將數(shù)據(jù)插入后更新表中有效元素的個數(shù)
}
2.4 順序表頭插🍚同樣的,只要是插入數(shù)據(jù),都必須先確保有足夠的空間,所以都需要檢查空間容量。但與尾插不同的是,要從順序表頭部插入數(shù)據(jù),則將影響之前已有的所有數(shù)據(jù),即需要將之前的數(shù)據(jù)整體向后挪一位,再將數(shù)據(jù)放入第一個位置,同時要記得將有效元素的個數(shù)加一。如圖所示為順序表頭插示意圖,以下是對應接口的實現(xiàn):
//順序表頭插
void SeqListFront(SeqList* sl, SLDataType data) {
assert(sl);
SLCheckCapacity(sl);
int end = sl->size ;
while (end >0) {
sl->data[end] = sl->data[end - 1];
end--;
}
sl->data[0] = data;
sl->size++;
}
2.5 順序表尾刪🍚順序表尾插與尾刪的實現(xiàn)都相對其它接口要簡單些,順序表尾刪即意味著不再需要訪問當前所有有效元素的最后一個元素,那只需要將有效元素的個數(shù)減一即可,但這里還需要注意的一點是:只有當表中有數(shù)據(jù)時才可以刪除數(shù)據(jù),如果表中都沒有數(shù)據(jù)了(size = 0),此時再將有效元素的個數(shù)減一(size - 1 = -1),那size將變成負數(shù),而計數(shù)是不可能為負值的,所以這里還需要進行空表判斷,如果表空則不需要再刪除數(shù)據(jù)了。以下是接口的實現(xiàn):
//順序表尾刪
void SeqListPopBack(SeqList* sl) {
assert(sl);
assert(sl->size >0); //確保表中還有數(shù)據(jù)
sl->size--; //刪除數(shù)據(jù)后,表中有效元素個數(shù)減一
}
2.6 順序表頭刪🍚如圖所示,順序表頭刪時無需另外刪除頭部數(shù)據(jù),只需將除頭部數(shù)據(jù)外的剩余數(shù)據(jù)逐個向前挪動覆蓋原數(shù)據(jù)即可,同時更新有效元素個數(shù)。以下是接口實現(xiàn):
//順序表頭刪
void SeqListPopFront(SeqList* sl) {
assert(sl);
assert(sl->size >0); //確保表非空
int begin = 1;
//從下標為1的位置開始逐個向前挪動覆蓋原數(shù)據(jù)
while (begin< sl->size) {
sl->data[begin - 1] = sl->data[begin];
begin++;
}
sl->size--;
}
2.7 順序表查找🍚順序表查找即是通過遍歷表中有效元素,對比查找表中是否有目標元素,一旦找到則返回對應下標,找不到則返回-1。如果不想從頭開始查找的話,也可以指定查找起始位置,以下是對應接口的實現(xiàn):
//順序表查找數(shù)據(jù)
//begin:開始查找的位置
int SeqListFind(SeqList* sl, SLDataType data, int begin) {
assert(sl);
int i = begin;
while (i< sl->size) {
if (sl->data[i] == data) {
return i; //找到即返回對應下標
}
i++;
}
return -1; //未找到則返回-1
}
2.8 順序表指定位置插入🍚在順序表指定位置插入數(shù)據(jù),不會影響指定位置之前的數(shù)據(jù),但會影響從指定位置開始之后的數(shù)據(jù),需要先將會被影響的這部分數(shù)據(jù)整體向后挪動一位,再在指定位置上插入數(shù)據(jù)。需要注意的是,除了容量的檢查,所輸入的指定位置也應當是有效的,即指定下標應當大于等于0,并小于等于size(有效元素個數(shù))??梢园l(fā)現(xiàn)當指定下標為0時,此時的操作相當于頭插;當指定下標為size時,此時的操作相當于尾插。以下是對應接口的實現(xiàn):
//在指定位置插入數(shù)據(jù)
void SeqListInsert(SeqList* sl, int position, SLDataType data) {
assert(sl);
assert(position >= 0);
assert(position<= sl->size);
SLCheckCapacity(sl);
int end = sl->size; //從后往前逐個將數(shù)據(jù)向后挪動一位
while (end >position) {
sl->data[end] = sl->data[end - 1];
end--;
}
sl->data[end] = data;
sl->size++; //更新有效元素個數(shù)
}
2.9 順序表指定位置刪除🍚與頭刪相似,刪除指定位置的數(shù)據(jù),只需要將指定位置之后的數(shù)據(jù)整體向前挪動一位即可,也不需要另外將所要刪除的數(shù)據(jù)置0或做什么別的修改,只要后面的數(shù)據(jù)覆蓋了要刪除的數(shù)據(jù),目標數(shù)據(jù)自然就消失了。事實上,當指定下標為0時,該刪除操作即為頭刪,當指定下標為最后一位有效元素的下標(size - 1)時,該刪除操作即為尾刪。以下是對應接口的實現(xiàn):
//從指定位置刪除數(shù)據(jù)
void SeqListErase(SeqList* sl, int position) {
assert(sl);
assert(position >= 0);
assert(position< sl->size);
int begin = position + 1; //從前往后逐個將數(shù)據(jù)向前挪動一位
while (begin< sl->size) {
sl->data[begin - 1] = sl->data[begin];
begin++;
}
sl->size--; //更新有效元素個數(shù)
}
以上就是動態(tài)順序表的主要接口的具體實現(xiàn),通過這些接口我們即可以實現(xiàn)對順序表的增刪查改??梢园l(fā)現(xiàn),其實我們只需要實現(xiàn)順序表在指定位置上的數(shù)據(jù)插入接口與數(shù)據(jù)刪除接口就可以完成在任意位置數(shù)據(jù)的插入和刪除了,因此如果需要實現(xiàn)順序表的頭插、尾插、頭刪、尾刪功能,也可以使用這兩個接口。
在上一節(jié)中,我們實現(xiàn)了動態(tài)順序表的主要接口,接下來我們可以將這些接口整合起來:將各接口及結(jié)構(gòu)體的聲明統(tǒng)一編寫在一個頭文件(這里是SeqList.h)中,并在該頭文件中包含實現(xiàn)接口時所需要用到的庫文件;接著將各接口的具體實現(xiàn)編寫在與頭文件對應的.c
文件中,并在該.c
文件中包含對應的頭文件(SeqList.h)。
SeqList.h:
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include#include#include
typedef int SLDataType;
typedef struct SeqList {
SLDataType* data; //存儲數(shù)據(jù)
int size; //記錄表中數(shù)據(jù)個數(shù)
int capacity; // 記錄順序表容量大小
}SeqList;
//順序表初始化
void SeqListInit(SeqList* sl);
//順序表數(shù)據(jù)打印
void SeqListPrint(SeqList* sl);
//順序表銷毀
void SeqListDestroy(SeqList* sl);
//順序表容量檢查
void SLCheckCapacity(SeqList* sl);
順序表尾插
//void SeqListPushBack(SeqList* sl, SLDataType data);
順序表頭插
//void SeqListFront(SeqList* sl, SLDataType data);
順序表尾刪
//void SeqListPopBack(SeqList* sl);
順序表頭刪
//void SeqListPopFront(SeqList* sl);
//在指定位置插入數(shù)據(jù)
void SeqListInsert(SeqList* sl, int position, SLDataType data);
//從指定位置刪除數(shù)據(jù)
void SeqListErase(SeqList* sl, int position);
//順序表修改數(shù)據(jù)
void SeqListModify(SeqList* sl, int position, SLDataType data);
//順序表查找數(shù)據(jù)
int SeqListFind(SeqList* sl, SLDataType data, int begin);
SeqList.c:
#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
//順序表初始化
void SeqListInit(SeqList* sl) {
assert(sl);
sl->data = NULL;
sl->size = 0;
sl->capacity = 0;
}
//順序表數(shù)據(jù)打印
void SeqListPrint(SeqList* sl) {
assert(sl);
int i = 0;
while (i< sl->size) {
printf("%d ", sl->data[i]);
i++;
}
printf("\n");
}
//順序表銷毀
void SeqListDestroy(SeqList* sl) {
assert(sl);
if (!(sl->data)) {
free(sl->data);
sl->data = NULL;
}
sl->size = 0;
sl->capacity = 0;
}
//順序表容量檢查
void SLCheckCapacity(SeqList* sl) {
assert(sl);
if (sl->size == sl->capacity) {
int newCapacity = sl->capacity == 0 ? 4 : 2 * (sl->capacity);
SLDataType* temp = (SLDataType*)realloc(sl->data, newCapacity * sizeof(SLDataType));
assert(temp);
sl->data = temp;
sl->capacity = newCapacity;
}
}
順序表尾插
//void SeqListPushBack(SeqList* sl, SLDataType data) {
// assert(sl);
// SLCheckCapacity(sl);
// sl->data[sl->size] = data;
// sl->size++;
//}
順序表頭插
//void SeqListFront(SeqList* sl, SLDataType data) {
// assert(sl);
// SLCheckCapacity(sl);
// int end = sl->size ;
// while (end >0) {
// sl->data[end] = sl->data[end - 1];
// end--;
// }
// sl->data[0] = data;
// sl->size++;
//}
順序表尾刪
//void SeqListPopBack(SeqList* sl) {
// assert(sl);
// assert(sl->size >0);
// sl->size--;
//}
順序表頭刪
//void SeqListPopFront(SeqList* sl) {
// assert(sl);
// assert(sl->size >0);
// int begin = 1;
// while (begin< sl->size) {
// sl->data[begin - 1] = sl->data[begin];
// begin++;
// }
// sl->size--;
//}
//在指定位置插入數(shù)據(jù)
void SeqListInsert(SeqList* sl, int position, SLDataType data) {
assert(sl);
assert(position >= 0);
assert(position<= sl->size);
SLCheckCapacity(sl);
int end = sl->size;
while (end >position) {
sl->data[end] = sl->data[end - 1];
end--;
}
sl->data[end] = data;
sl->size++;
}
//從指定位置刪除數(shù)據(jù)
void SeqListErase(SeqList* sl, int position) {
assert(sl);
assert(position >= 0);
assert(position< sl->size);
int begin = position + 1;
while (begin< sl->size) {
sl->data[begin - 1] = sl->data[begin];
begin++;
}
sl->size--;
}
//順序表修改數(shù)據(jù)
void SeqListModify(SeqList* sl, int position, SLDataType data) {
assert(sl);
assert(position >= 0);
assert(position< sl->size);
sl->data[position] = data;
}
//順序表查找數(shù)據(jù)
//begin:開始查找的位置
int SeqListFind(SeqList* sl, SLDataType data, int begin) {
assert(sl);
int i = begin;
while (i< sl->size) {
if (sl->data[i] == data) {
return i;
}
i++;
}
return -1;
}
以上是我對數(shù)據(jù)結(jié)構(gòu)中順序表的一些學習記錄總結(jié),如有錯誤,希望大家?guī)兔χ刚?,也歡迎大家給予建議和討論,謝謝!
你是否還在尋找穩(wěn)定的海外服務器提供商?創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源,準確流量調(diào)度確保服務器高可用性,企業(yè)級服務器適合批量采購,新人活動首月15元起,快前往官網(wǎng)查看詳情吧