C語言數(shù)據(jù)結(jié)構(gòu)深入探索順序表
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)的形式存儲
2.順序表
2.1概念及結(jié)構(gòu)
順序表是用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲。在數(shù)組上完成數(shù)據(jù)的增刪查改。
順序表一般可以分為：
靜態(tài)順序表：使用定長數(shù)組存儲元素。
動態(tài)順序表：使用動態(tài)開辟的數(shù)組存儲
2.2 接口實現(xiàn)
靜態(tài)順序表只適用于確定知道需要存多少數(shù)據(jù)的場景。靜態(tài)順序表的定長數(shù)組導(dǎo)致N定大了，空間開多了浪費，開少了不夠用。所以現(xiàn)實中基本都是使用動態(tài)順序表，根據(jù)需要動態(tài)的分配空間大小，所以下面我們實現(xiàn)動態(tài)順序表。
#pragma once
#include<stdio.h>
#include<assert.h>
typedef int SLDataType;
typedef struct SeqList
{
int* a;
int size; //存儲數(shù)據(jù)個數(shù)
int capacity;//存儲空間大小
}SeqList;
void SeqListInit(SeqList* psl);//初始化
void SeqListDestroy(SeqList* psl);//銷毀
void SeqListPrint(SeqList* psl);//打印
void SeqListCheckCapacity(SeqList* psl);//檢查容量
int SeqListFind(SeqList* psl, SLDataType x);//查找
//時間復(fù)雜度是O（1）
void SeqListPushBack(SeqList* psl, SLDataType x);//尾插
void SeqListPopBack(SeqList* psl);//尾刪
//時間復(fù)雜度是O（N）
void SeqListPushFront(SeqList* psl, SLDataType x);//頭插
void SeqListPopFront(SeqList* psl);//頭刪
//時間復(fù)雜度是O（N）
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);//在pos位置插入
void SeqListErase(SeqList* psl, size_t pos);//在pos位置刪除
2.2.1初始化
就是將元素分別初始化。
//初始化
void SeqListInit(SeqList* psl)
{
assert(psl);
psl->a = NULL;
psl->size = 0;
psl->capacity = 0;
}
2.2.2 檢查容量
初始化時容量為0，想要放數(shù)據(jù)得增加容量，每次插入數(shù)據(jù)也得保證容量充足，為了方便，我們先寫一個用于檢查容量并增容的函數(shù)。
//檢查容量
void SeqListCheckCapacity(SeqList* psl)
{
assert(psl);
//如果滿了，就要擴容
if (psl->size == psl->capacity)
{
size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;//防止一開始capacity=0無法*2增容
SLDataType* tmp = realloc(psl->a, sizeof(SLDataType) * newCapacity);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
psl->a = tmp;
psl->capacity = newCapacity;
}
}
}
2.2.3 順序表打印
就是遍歷一次把所有元素打印出來，這樣可以檢查函數(shù)寫的是否正確，及時訂正。
//打印
void SeqListPrint(SeqList* psl)
{
assert(psl);
for (int i = 0; i < psl->size; i++)
{
printf("%d ", psl->a[i]);
}
printf("\n");
}
2.2.4 順序表尾插
//尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
assert(psl);
//如果滿了，就要擴容
SeqListCheckCapacity(psl);
psl->a[psl->size] = x;
psl->size++;
}
2.2.5 順序表尾刪
只需要把size-1這樣的話下一個數(shù)據(jù)就會把尾部數(shù)據(jù)覆蓋掉，達(dá)到刪除的效果。
//尾刪
void SeqListPopBack(SeqList* psl)
{
assert(psl);
if (psl->size > 0)
{
psl->size--;
}
}
2.2.6 順序表頭插
//頭插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
assert(psl);
//如果滿了，就要擴容
SeqListCheckCapacity(psl);
//挪動數(shù)據(jù),騰出頭部位置
int end = psl->size - 1;
while (end >= 0)
{
psl->a[end + 1] = psl->a[end];
end--;
}
psl->a[0] = x;
psl->size++;
}
2.2.7 順序表頭刪
將第一個位置覆蓋掉，然后用尾刪的思路將最后一個數(shù)據(jù)刪除。
//頭刪
void SeqListPopFront(SeqList* psl)
{
assert(psl);
//挪動數(shù)據(jù)覆蓋第一個
if(psl->size>0)
{
int begin = 1;
while (begin < psl->size)
{
psl->a[begin - 1] = psl->a[begin];
begin++;
}
}
psl->size--;
}
2.2.8 順序表在pos位置插入x
思路跟頭插很像,但內(nèi)含陷阱！
//在pos位置插入
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
assert(psl);
//如果滿了，就要擴容
SeqListCheckCapacity(psl);
溫和檢測
//if (pos > psl->size)
//{
// printf("pos越界：%d\n", pos);
// return;
//}
//暴力檢測
assert(pos <= psl->size);
//pos=0的時候由于無符號整型判斷時的整型提升，會出問題
//size_t end = psl->size - 1;
//while (end >= pos)
//{
// psl->a[end + 1] = psl->a[end];
// end--;
//}
//psl->a[pos] = x;
//psl->size++;
//這樣寫才不會有問題
size_t end = psl->size;
while (end > pos)
{
psl->a[end] = psl->a[end - 1];
--end;
}
psl->a[pos] = x;
psl->size++;
}
2.2.9 順序表刪除pos位置的值
思路跟頭刪很像
//在pos位置刪除
void SeqListErase(SeqList* psl, size_t pos)
{
assert(psl);
assert(pos < psl->size);
size_t begin = pos + 1;
while (begin < psl->size)
{
psl->a[begin - 1] = psl->a[begin];
++begin;
}
psl->size--;
}
2.2.10 尾插、尾刪、頭插、頭刪的改進(jìn)
有了上面兩個通常情況下的增刪函數(shù)，我們就能改進(jìn)尾插、尾刪、頭插、頭刪。這樣能夠快速寫完順序表
//尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
assert(psl);
SeqListCheckCapacity(psl);
SeqListInsert(psl, psl->size, x);//在size位置插入數(shù)據(jù)
}
//尾刪
void SeqListPopBack(SeqList* psl)
{
assert(psl);
SeqListErase(psl, psl->size-1);//在size-1位置刪除數(shù)據(jù)
}
//頭插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
assert(psl);
SeqListCheckCapacity(psl);
SeqListInsert(psl, 0, x);//在0位置插入數(shù)據(jù)
}
//頭刪
void SeqListPopFront(SeqList* psl)
{
assert(psl);
SeqListErase(psl, 0);//在0位置刪除數(shù)據(jù)
}
2.2.11 順序表查找
遍歷一遍，一個個找
int SeqListFind(SeqList* psl, SLDataType x)
{
assert(psl);
for (int i = 0; i < psl->size; ++i)
{
if (psl->a[i] == x)
{
return i;
}
}
return -1;
}
2.2.12 順序表銷毀
最后的最后，一定要養(yǎng)成好習(xí)慣，不要忘記銷毀之前申請的空間，防止內(nèi)存泄漏。
//銷毀
void SeqListDestroy(SeqList* psl)
{
free(psl->a);
psl->a = NULL;
psl->capacity = 0;
psl->size = 0;
}
2.3 數(shù)組相關(guān)面試題
刪除排序數(shù)組中的重復(fù)項。26. 刪除有序數(shù)組中的重復(fù)項.
原地移除數(shù)組中所有的元素val，要求時間復(fù)雜度為O(N)，空間復(fù)雜度為O(1)。27. 移除元素.
合并兩個有序數(shù)組。88. 合并兩個有序數(shù)組.
2.4 順序表的問題及思考
問題：
- 中間/頭部的插入刪除，時間復(fù)雜度為O(N)
- 增容需要申請新空間，拷貝數(shù)據(jù)，釋放舊空間。會有不小的消耗。
- 增容一般是呈2倍的增長，勢必會有一定的空間浪費。例如當(dāng)前容量為100，滿了以后增容到200，我們再繼續(xù)插入了5個數(shù)據(jù)，后面沒有數(shù)據(jù)插入了，那么就浪費了95個數(shù)據(jù)空間。
思考：如何解決以上問題呢？下期會給出了鏈表的結(jié)構(gòu)，現(xiàn)在大家可以想想鏈表會如何解決這些問題。
到此這篇關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)深入探索順序表的文章就介紹到這了,更多相關(guān)C語言 順序表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
樹的3中常見搜索方式，包括二叉樹方式（每一層只有0和1）、滿m叉樹（每一層都有0 到m - 1）、子集樹，也稱為全排列樹,需要的朋友可以參考下2014-02-02
這篇文章主要為大家詳細(xì)介紹了Opencv實現(xiàn)輪廓提取功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-05-05
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)自動發(fā)牌程序，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-04-04
QT提供了圖形繪制接口QPainter，通過該接口可以繪制多種圖形，包括多邊形。本文就來利用它實現(xiàn)繪制一個簡單的多邊形，感興趣的可以嘗試一下2022-11-11
C++?vector與數(shù)組轉(zhuǎn)換寫入/讀出文件方式
這篇文章主要介紹了C++?vector與數(shù)組轉(zhuǎn)換寫入/讀出文件方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11
C4996錯誤的意思：是VS覺得strcpy這函數(shù)不安全,建議你使更安全的函數(shù),那么如何解決呢,本文主要介紹了vs運行時報C4996代碼錯誤的問題解決,感興趣的可以了解一下2024-01-01
基于Matlab實現(xiàn)離散系統(tǒng)分岔圖的繪制
這篇文章主要介紹了如何利用Matlab實現(xiàn)離散分岔圖的繪制，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)Matlab有一定的幫助，需要的可以參考一下2022-04-04
這篇文章主要為大家詳細(xì)介紹了C++簡單實現(xiàn)復(fù)數(shù)計算器的的相關(guān)代碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2016-06-06
C語言實現(xiàn)學(xué)生宿舍信息管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)學(xué)生宿舍信息管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
C++ 將數(shù)據(jù)轉(zhuǎn)為字符串的幾種方法
這篇文章主要介紹了C++ 將數(shù)據(jù)轉(zhuǎn)為字符串的幾種方法，十分的實用，有需要的小伙伴可以參考下。2015-06-06