C語言數(shù)據(jù)結(jié)構(gòu)深入探索順序表
更新時間：2022年03月25日 11:14:32 作者：天影云光
順序表，全名順序存儲結(jié)構(gòu)，是線性表的一種，線性表用于存儲邏輯關(guān)系為“一對一”的數(shù)據(jù)，順序表自然也不例外，不僅如此，順序表對數(shù)據(jù)的物理存儲結(jié)構(gòu)也有要求，跟隨下文來具體了解吧
1.線性表
線性表（linear list）是n個具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表：順序表、鏈表、棧、隊(duì)列、字符串…
線性表在邏輯上是線性結(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 接口實(shí)現(xiàn)
靜態(tài)順序表只適用于確定知道需要存多少數(shù)據(jù)的場景。靜態(tài)順序表的定長數(shù)組導(dǎo)致N定大了，空間開多了浪費(fèi)，開少了不夠用。所以現(xiàn)實(shí)中基本都是使用動態(tài)順序表，根據(jù)需要動態(tài)的分配空間大小，所以下面我們實(shí)現(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);
//如果滿了，就要擴(kuò)容
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);
//如果滿了，就要擴(kuò)容
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);
//如果滿了，就要擴(kuò)容
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);
//如果滿了，就要擴(kuò)容
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ù)項(xiàng)。26. 刪除有序數(shù)組中的重復(fù)項(xiàng).
原地移除數(shù)組中所有的元素val，要求時間復(fù)雜度為O(N)，空間復(fù)雜度為O(1)。27. 移除元素.
合并兩個有序數(shù)組。88. 合并兩個有序數(shù)組.
2.4 順序表的問題及思考
問題：
- 中間/頭部的插入刪除，時間復(fù)雜度為O(N)
- 增容需要申請新空間，拷貝數(shù)據(jù)，釋放舊空間。會有不小的消耗。
- 增容一般是呈2倍的增長，勢必會有一定的空間浪費(fèi)。例如當(dāng)前容量為100，滿了以后增容到200，我們再繼續(xù)插入了5個數(shù)據(jù)，后面沒有數(shù)據(jù)插入了，那么就浪費(fèi)了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)文章
線程的主要優(yōu)勢在于，能夠通過全局變量來共享信息。不過，這種便捷的共享是有代價的：必須確保多個線程不會同時修改同一變量，或者某一線程不會讀取正由其他線程修改的變量。為了防止出現(xiàn)線程某甲試圖訪?問一共享變量時，線程某乙正在對其進(jìn)行修改。引入了互斥量2022-05-05
pair是一種模板類型，其中包含兩個數(shù)據(jù)值，兩個數(shù)據(jù)的類型可以不同,本篇詳細(xì)的介紹了Pair的使用方法和實(shí)例，有興趣的同學(xué)可以了解一下。2016-12-12
這篇文章主要介紹了C語言將字符串逆序輸出的實(shí)例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-02-02
這篇文章主要介紹了C++?左值引用與?const?關(guān)鍵字,左值引用是已定義的變量的別名，其主要用途是用作函數(shù)的形參，將?const?關(guān)鍵字用于左值引用時，其在初始化時可接受的賦值形式變得更加廣泛了，這里來總結(jié)一下，需要的朋友可以參考下2022-09-09
這篇文章主要為大家詳細(xì)介紹了OpenCV實(shí)現(xiàn)傾斜文字校正，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
這篇文章給大家分享C語言所有經(jīng)典排序方法，文章給大家提供完整的實(shí)例代碼幫助大家快速學(xué)習(xí)掌握C語言排序方法，感興趣的朋友一起看看吧2021-08-08
這篇文章主要介紹了C++遞歸刪除一個目錄的實(shí)現(xiàn)方法,涉及到目錄的操作及遞歸算法的應(yīng)用,需要的朋友可以參考下2014-10-10
進(jìn)程同步是一個操作系統(tǒng)級別的概念,是在多道程序的環(huán)境下，存在著不同的制約關(guān)系，為了協(xié)調(diào)這種互相制約的關(guān)系，實(shí)現(xiàn)資源共享和進(jìn)程協(xié)作，從而避免進(jìn)程之間的沖突，引入了進(jìn)程同步2021-06-06
本文將介紹Qt之ui在程序中的使用-多繼承法，需要的朋友可以參考2012-11-11
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)推箱子小項(xiàng)目，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-08-08