泰國做彩票網(wǎng)站seo關(guān)鍵詞排名怎么提升
🎯引言
歡迎來到HanLop博客的C語言數(shù)據(jù)結(jié)構(gòu)初階系列。在這個(gè)系列中,我們將深入探討各種基本的數(shù)據(jù)結(jié)構(gòu)和算法,幫助您打下堅(jiān)實(shí)的編程基礎(chǔ)。本次我將為你講解。順序表(也稱為數(shù)組)是一種線性表,因其簡單易用而廣泛應(yīng)用于各類編程任務(wù)中。在本篇文章中,我們將介紹順序表的基本概念、順序表的創(chuàng)建和操作方法,以及其優(yōu)缺點(diǎn)。通過一些實(shí)際的代碼示例,您將更好地掌握順序表在C語言中的應(yīng)用,從而為后續(xù)學(xué)習(xí)其他數(shù)據(jù)結(jié)構(gòu)打下堅(jiān)實(shí)的基礎(chǔ)。
👓順序表
1.線性表
線性表的概念
線性表是數(shù)據(jù)結(jié)構(gòu)中最基本、最常用的一種結(jié)構(gòu),由n個(gè)數(shù)據(jù)元素組成一個(gè)有限序列。線性表中的數(shù)據(jù)元素之間存在一對(duì)一的線性關(guān)系,即每個(gè)元素都有唯一的前驅(qū)和后繼(除了第一個(gè)和最后一個(gè)元素)。常見的線性表有:順序表、鏈表、棧、隊(duì)列…
線性表的基本特點(diǎn):
-
線性關(guān)系:每個(gè)元素有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼(第一個(gè)元素除外沒有前驅(qū),最后一個(gè)元素除外沒有后繼)。
-
唯一性:每個(gè)元素在表中的位置是唯一的。
-
相同類型:線性表中的所有元素都是相同的數(shù)據(jù)類型。
邏輯結(jié)構(gòu)
線性表的邏輯結(jié)構(gòu)是指線性表中元素之間的關(guān)系。線性表中的元素具有一對(duì)一的線性關(guān)系,即每個(gè)元素都有唯一的前驅(qū)和后繼(第一個(gè)元素除外沒有前驅(qū),最后一個(gè)元素除外沒有后繼)。這種邏輯結(jié)構(gòu)決定了線性表的基本操作和特點(diǎn)。
物理結(jié)構(gòu)
線性表的物理結(jié)構(gòu)是指線性表在計(jì)算機(jī)內(nèi)存中的存儲(chǔ)方式。主要有兩種存儲(chǔ)方式:
- 順序存儲(chǔ)結(jié)構(gòu)(順序表,數(shù)組):
- 元素依次存儲(chǔ)在一段連續(xù)的內(nèi)存空間中。
- 優(yōu)點(diǎn):可以通過索引快速訪問元素,查找效率高。
- 缺點(diǎn):插入和刪除操作效率較低,因?yàn)樾枰苿?dòng)大量元素。
- 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(鏈表):
- 元素存儲(chǔ)在任意的內(nèi)存位置,元素之間通過指針連接。
- 優(yōu)點(diǎn):插入和刪除操作效率較高,不需要移動(dòng)元素,只需改變指針。
- 缺點(diǎn):查找效率較低,因?yàn)樾枰獜念^遍歷到所需位置。
2.順序表
2.1概念
- 定義:順序表是由一組連續(xù)的存儲(chǔ)單元組成的線性表,元素之間的邏輯順序與物理存儲(chǔ)位置相對(duì)應(yīng)。
- 特點(diǎn):
- 元素類型相同,存儲(chǔ)在一塊連續(xù)的內(nèi)存空間中。
- 支持通過索引快速訪問元素。
- 插入和刪除操作需要移動(dòng)大量元素,效率較低。
- 適用場景:適合于元素?cái)?shù)量固定且需要頻繁進(jìn)行查找操作的場景。
2.2結(jié)構(gòu)
順序表的物理結(jié)構(gòu)如下:
存儲(chǔ)結(jié)構(gòu):使用一段連續(xù)的內(nèi)存空間存儲(chǔ)元素,可以通過下標(biāo)來訪問各個(gè)元素。(底層本質(zhì)上數(shù)組,對(duì)數(shù)組進(jìn)行封裝后成了順序表)
基本操作:
-
插入操作:
-
定義:在順序表的指定位置插入一個(gè)新的元素。
-
步驟:如果插入位置不在表尾,需要將插入位置后的元素依次后移一位,然后將新元素插入到指定位置。
-
時(shí)間復(fù)雜度:最壞情況下是O(n),因?yàn)榭赡苄枰苿?dòng)表尾的所有元素。
-
-
刪除操作:
-
定義:刪除順序表中指定位置的元素。
-
步驟:將刪除位置后的元素依次前移一位,覆蓋被刪除的元素位置。
-
時(shí)間復(fù)雜度:最壞情況下是O(n),因?yàn)榭赡苄枰苿?dòng)表尾的所有元素。
-
-
修改操作:
-
定義:修改順序表中指定位置的元素值。
-
步驟:直接通過索引定位到指定位置,修改元素的值。
-
時(shí)間復(fù)雜度:O(1),因?yàn)樾薷牟僮魇侵苯佣ㄎ坏轿恢眠M(jìn)行修改。
-
-
查找操作:
-
定義:查找順序表中指定元素或元素位置。
-
步驟:通過順序表的索引直接訪問指定位置的元素,或者遍歷整個(gè)表查找特定元素。
-
時(shí)間復(fù)雜度:最壞情況下是O(n),因?yàn)榭赡苄枰闅v整個(gè)表來查找元素。
-
2.3分類
2.3.1靜態(tài)順序表:
- 定義:靜態(tài)順序表是在程序運(yùn)行前就確定了大小,內(nèi)存空間是靜態(tài)分配的,不可動(dòng)態(tài)改變大小。
- 特點(diǎn):數(shù)組長度在創(chuàng)建時(shí)固定,不能動(dòng)態(tài)增加或減少。
- 優(yōu)點(diǎn):訪問速度快,不需要額外的空間管理。
- 缺點(diǎn):浪費(fèi)內(nèi)存空間,不能適應(yīng)動(dòng)態(tài)變化的數(shù)據(jù)需求。
//靜態(tài)順序表
typedef int SLDateType;
#define N 10
typedef struct SeqList
{SLDateType a[N];int size;
}SeqList;
2.3.2動(dòng)態(tài)順序表:
- 定義:動(dòng)態(tài)順序表是在程序運(yùn)行時(shí)根據(jù)需要?jiǎng)討B(tài)分配內(nèi)存空間的順序表。
- 特點(diǎn):可以動(dòng)態(tài)地增加或減少數(shù)組的長度。
- 優(yōu)點(diǎn):節(jié)約內(nèi)存空間,適應(yīng)動(dòng)態(tài)變化的數(shù)據(jù)需求。
- 缺點(diǎn):可能導(dǎo)致頻繁的內(nèi)存分配和拷貝,影響性能。
typedef int SLDateType;
typedef struct SeqList
{SLDateType* a;int size;int capacity;
}SeqList;
2.4動(dòng)態(tài)順序表的實(shí)現(xiàn)
2.4.1SeqList.h文件
//SeqList.h文件的代碼
#include <stdio.h>//標(biāo)準(zhǔn)輸入輸出庫,提供了標(biāo)準(zhǔn)的輸入輸出函數(shù)。
#include <stdlib.h>//標(biāo)準(zhǔn)庫,提供了動(dòng)態(tài)內(nèi)存分配、隨機(jī)數(shù)生成、程序控制等函數(shù)。
#include <assert.h>//斷言庫,用于在程序中插入檢查點(diǎn),確保某個(gè)條件為真,如果條件為假則終止程序執(zhí)行。//動(dòng)態(tài)順序表
typedef int SLDateType;
typedef struct SeqList
{SLDateType* a;int size;int capacity;
}SeqList;//順序表初始化
void SeqListInit(SeqList* p);
//順表打印
void SeqListPrint(SeqList* p);
//順序表的銷毀
void SeqListDestory(SeqList* p);//順序表尾插
void SeqListPushBack(SeqList* p, SLDateType x);
//順序表增容
void CheckCapacity(SeqList* p);
//順序表頭插
void SeqListPushFront(SeqList* p, SLDateType x);
//順序表尾刪
void SeqListPopBack(SeqList* p);//在pos位置插入數(shù)字
void SeqListInsert(SeqList* p, int pos, SLDateType X);
//刪除pos位置的數(shù)字
void SeqListErase(SeqList* p,int pos);
//找到指定的數(shù)字位置,返回下標(biāo)
int SeqListFind(SeqList* p, SLDateType x);
代碼解析:
動(dòng)態(tài)順序表結(jié)構(gòu)體定義
typedef int SLDateType;
typedef struct SeqList
{SLDateType* a; // 指向動(dòng)態(tài)數(shù)組的指針int size; // 當(dāng)前動(dòng)態(tài)順序表中元素的個(gè)數(shù)int capacity; // 當(dāng)前動(dòng)態(tài)順序表的容量
} SeqList;
SLDateType
:定義動(dòng)態(tài)順序表中存儲(chǔ)的元素類型為int
。- struct SeqList:定義了動(dòng)態(tài)順序表的結(jié)構(gòu)體,包含:
SLDateType* a
:指向動(dòng)態(tài)數(shù)組的指針,用于存儲(chǔ)順序表中的元素。int size
:當(dāng)前動(dòng)態(tài)順序表中元素的個(gè)數(shù)。int capacity
:當(dāng)前動(dòng)態(tài)順序表的容量,即可以存儲(chǔ)的最大元素個(gè)數(shù)。
函數(shù)聲明
// 順序表初始化
void SeqListInit(SeqList* p);
// 順序表打印
void SeqListPrint(SeqList* p);
// 順序表的銷毀
void SeqListDestory(SeqList* p);// 順序表尾插
void SeqListPushBack(SeqList* p, SLDateType x);
// 順序表增容
void CheckCapacity(SeqList* p);
// 順序表頭插
void SeqListPushFront(SeqList* p, SLDateType x);
// 順序表尾刪
void SeqListPopBack(SeqList* p);// 在pos位置插入數(shù)字
void SeqListInsert(SeqList* p, int pos, SLDateType X);
// 刪除pos位置的數(shù)字
void SeqListErase(SeqList* p, int pos);
// 找到指定的數(shù)字位置,返回下標(biāo)
int SeqListFind(SeqList* p, SLDateType x);
這些函數(shù)聲明定義了動(dòng)態(tài)順序表的基本操作:
SeqListInit
:初始化動(dòng)態(tài)順序表。SeqListPrint
:打印動(dòng)態(tài)順序表中的元素。SeqListDestory
:銷毀動(dòng)態(tài)順序表,釋放內(nèi)存。SeqListPushBack
:尾部插入元素。CheckCapacity
:檢查并增加動(dòng)態(tài)順序表的容量。SeqListPushFront
:頭部插入元素。SeqListPopBack
:尾部刪除元素。SeqListInsert
:在指定位置插入元素。SeqListErase
:刪除指定位置的元素。SeqListFind
:查找指定元素并返回其位置。
這些函數(shù)聲明提供了對(duì)動(dòng)態(tài)順序表進(jìn)行初始化、增刪改查等基本操作的接口,具體的實(shí)現(xiàn)應(yīng)該在對(duì)應(yīng)的 SeqList.c
文件中完成。
2.4.2SeqList.c文件
//SeqList.c文件
//這里引入了頭文件 SeqList.h,其中定義了動(dòng)態(tài)順序表的結(jié)構(gòu)體 SeqList 和函數(shù)聲明。
#include "SeqList.h"
//順序表的初始化
void SeqListInit(SeqList* p)
{assert(p);p->a = NULL;p->size = p->capacity = 0;
}//順序表的銷毀
void SeqListDestory(SeqList* p)
{assert(p);free(p->a);p->a = NULL;p->size = p->capacity = 0;
}//順序表打印
void SeqListPrint(SeqList* p)
{assert(p);int i = 0;for (i = 0; i < p->size; i++){printf("%d ", p->a[i]);}printf("\n");
}//檢查并增加動(dòng)態(tài)順序表的容量。
void CheckCapacity(SeqList* p)
{assert(p);int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;if (p->capacity == p->size){p->capacity = newcapacity;SLDateType* tmp = (SLDateType*)realloc(p->a, p->capacity * sizeof(SLDateType));if (tmp != NULL){p->a = tmp;}else{exit(1);}}
}//順序表尾插
void SeqListPushBack(SeqList* p, SLDateType x)
{assert(p);CheckCapacity(p);p->a[p->size] = x;p->size++;
}//順序表頭插
void SeqListPushFront(SeqList* p, SLDateType x)
{assert(p);CheckCapacity(p);int i = 0;for (i = p->size; i > 0; i--){p->a[i] = p->a[i-1];}p->a[0] = x;p->size++;
}//順序表尾刪
void SeqListPopBack(SeqList* p)
{assert(p);assert(p->size);p->size--;}//順序表頭刪
void SeqListPopFront(SeqList* p)
{assert(p);assert(p->size);int i = 0;for (i = 0; i < p->size-1; i++){p->a[i] = p->a[i + 1];}p->size--;
}//在pos位置插入數(shù)字
void SeqListInsert(SeqList* p, int pos, SLDateType x)
{assert(p != NULL);assert(pos >= 0 && pos <= p->size);//檢查是否需要增容CheckCapacity(p);for (int i = p->size-1; i > pos-1 ; --i){p->a[i + 1] = p->a[i];//p->a[pos+1]=p->a[pos]}p->a[pos] = x;p->size++;
}//刪除pos位置的數(shù)字
void SeqListErase(SeqList* p, int pos)
{assert(p != NULL);assert(pos >= 0 && pos < p->size);for (int i = pos; i < p->size-1; i++){p->a[i] = p->a[i + 1];//p->a[size-2]=p->a[size-1]}p->size--;
}//找到指定的數(shù)字位置,返回下標(biāo)
int SeqListFind(SeqList* p, SLDateType x)
{assert(p != NULL);for (size_t i = 0; i < p->size; i++){if (p->a[i] == x){return i;}}return -1;
}
代碼解析:
初始化函數(shù) SeqListInit
void SeqListInit(SeqList* p)
{assert(p);p->a = NULL;p->size = p->capacity = 0;
}
- 功能:初始化動(dòng)態(tài)順序表。
- 說明:將動(dòng)態(tài)順序表指針
p
所指向的順序表a
設(shè)置為NULL
,并將size
(元素個(gè)數(shù))和capacity
(容量)都設(shè)置為0
。使用斷言assert(p)
確保傳入的指針p
不為空。
銷毀函數(shù) SeqListDestory
void SeqListDestory(SeqList* p)
{assert(p);free(p->a);p->a = NULL;p->size = p->capacity = 0;
}
- 功能:銷毀動(dòng)態(tài)順序表。
- 說明:釋放動(dòng)態(tài)順序表
a
所指向的內(nèi)存空間,將a
置為NULL
,并將size
和capacity
置為0
。同樣使用斷言assert(p)
確保傳入的指針p
不為空。
打印函數(shù) SeqListPrint
void SeqListPrint(SeqList* p)
{assert(p);int i = 0;for (i = 0; i < p->size; i++){printf("%d ", p->a[i]);}printf("\n");
}
- 功能:打印動(dòng)態(tài)順序表中的元素。
- 說明:遍歷順序表
a
中的每個(gè)元素,依次打印出來。使用斷言assert(p)
確保傳入的指針p
不為空。
增容函數(shù) CheckCapacity
void CheckCapacity(SeqList* p)
{assert(p);int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;if (p->capacity == p->size){p->capacity = newcapacity;SLDateType* tmp = (SLDateType*)realloc(p->a, p->capacity * sizeof(SLDateType));if (tmp != NULL){p->a = tmp;}else{exit(1);}}
}
- 功能:檢查并增加動(dòng)態(tài)順序表的容量。
- 說明:
- 如果當(dāng)前順序表
a
的容量capacity
等于當(dāng)前元素個(gè)數(shù)size
,則表示需要增加容量。 - 計(jì)算新的容量
newcapacity
,如果當(dāng)前容量為0
,則設(shè)置為4
,否則擴(kuò)大為原來的兩倍。 - 使用
realloc
函數(shù)重新分配a
的內(nèi)存空間,將新的容量分配給a
。如果分配失敗,程序退出。 - 使用斷言
assert(p)
確保傳入的指針p
不為空。
- 如果當(dāng)前順序表
尾部插入函數(shù) SeqListPushBack
void SeqListPushBack(SeqList* p, SLDateType x)
{assert(p);CheckCapacity(p);p->a[p->size] = x;p->size++;
}
- 功能:在動(dòng)態(tài)順序表尾部插入元素
x
。 - 說明:首先調(diào)用
CheckCapacity
函數(shù)檢查并增加容量。然后將元素x
插入到順序表a
的末尾,并更新size
。
頭部插入函數(shù) SeqListPushFront
void SeqListPushFront(SeqList* p, SLDateType x)
{assert(p);CheckCapacity(p);int i = 0;//元素從后往前依次往后移動(dòng)一位 注:不能從前往后 因?yàn)榍懊娴脑赝笠苿?dòng)會(huì)覆蓋掉后面的元素for (i = p->size; i > 0; i--){p->a[i] = p->a[i-1];}p->a[0] = x;p->size++;
}
- 功能:在動(dòng)態(tài)順序表頭部插入元素
x
。 - 說明:首先調(diào)用
CheckCapacity
函數(shù)檢查并增加容量。然后將順序表a
中的所有元素后移一位,為新元素騰出空間,最后將x
插入到順序表a
的第一個(gè)位置,并更新size
。
尾部刪除函數(shù) SeqListPopBack
void SeqListPopBack(SeqList* p)
{assert(p);assert(p->size > 0);p->size--;
}
- 功能:從動(dòng)態(tài)順序表尾部刪除元素。
- 說明:首先使用斷言
assert(p)
確保順序表不為空,然后將size
減一,表示刪除尾部的元素。
頭部刪除函數(shù) SeqListPopFront
void SeqListPopFront(SeqList* p)
{assert(p);assert(p->size > 0);int i = 0;//元素從前往后依次向前移動(dòng)一位 for (i = 0; i < p->size-1; i++){p->a[i] = p->a[i + 1];}p->size--;
}
- 功能:從動(dòng)態(tài)順序表頭部刪除元素。
- 說明:首先使用斷言
assert(p)
確保順序表不為空,然后將順序表a
中的所有元素前移一位,覆蓋掉第一個(gè)元素,最后將size
減一,表示刪除頭部的元素。
插入函數(shù) SeqListInsert
void SeqListInsert(SeqList* p, int pos, SLDateType x)
{assert(p != NULL);assert(pos >= 0 && pos <= p->size);CheckCapacity(p);//元素從后往前依次向后移動(dòng)一位 for (int i = p->size-1; i >= pos; --i){p->a[i + 1] = p->a[i];}p->a[pos] = x;p->size++;
}
- 功能:在指定位置
pos
插入元素x
。 - 說明:
- 首先使用斷言確保順序表和位置參數(shù)有效。
- 調(diào)用
CheckCapacity
函數(shù)檢查并增加容量。 - 將插入位置
pos
后的所有元素依次后移一位,為新元素x
騰出空間。 - 將元素
x
插入到指定位置pos
,并更新size
。
刪除函數(shù) SeqListErase
void SeqListErase(SeqList* p, int pos)
{assert(p != NULL);assert(pos >= 0 && pos < p->size);//元素從前往后依次向前移動(dòng)一位 for (int i = pos; i < p->size-1; i++){p->a[i] = p->a[i + 1];}p->size--;
}
- 功能:刪除指定位置
pos
的元素。 - 說明:
- 首先使用斷言確保順序表和位置參數(shù)有效。
- 將指定位置
pos
后的所有元素依次前移一位,覆蓋掉要?jiǎng)h除的元素。 - 最后將
size
減一,表示刪除了一個(gè)元素。
查找函數(shù) SeqListFind
int SeqListFind(SeqList* p, SLDateType x)
{assert(p != NULL);for (size_t i = 0; i < p->size; i++){if (p->a[i] == x){return i;}}return -1;
}
- 功能:查找順序表中值為
x
的元素,返回其位置索引。 - 說明:
- 使用斷言確保順序表有效。
- 遍歷順序表
a
中的所有元素,找到第一個(gè)值等于x
的元素,返回其位置索引。 - 如果未找到,返回
-1
表示未找到。
🥇結(jié)語
通過本篇文章,我們?cè)敿?xì)介紹了順序表這一重要的數(shù)據(jù)結(jié)構(gòu)及其在C語言中的實(shí)現(xiàn)與應(yīng)用。我們探討了順序表的基本概念、操作方法以及優(yōu)缺點(diǎn),并通過實(shí)例代碼展示了如何在實(shí)際編程中使用順序表。掌握順序表不僅有助于理解其他更復(fù)雜的數(shù)據(jù)結(jié)構(gòu),還能提高代碼編寫和優(yōu)化能力。希望本文能為您的編程之旅提供有益的指導(dǎo)。請(qǐng)繼續(xù)關(guān)注HanLop博客,下一篇文章我們將探討另一種常見的數(shù)據(jù)結(jié)構(gòu)——鏈表,敬請(qǐng)期待!