順序表前言
順序表作為數(shù)據(jù)結構的入門知識,整體知識較為簡單,主要對動態(tài)內存開辟 結構體 指針有要求,其余難度較低
順序表要實現(xiàn)的功能
順序表主要需要實現(xiàn)的有順序表的增刪查改和定向搜索銷毀等,具體實現(xiàn)函數(shù)如下
// 對數(shù)據(jù)的管理:增刪查改
void SeqListInit(SeqList* ps);
void SeqListDestroy(SeqList* ps);
void SeqListPrint(SeqList* ps);
void SeqListPushBack(SeqList* ps, SLDateType x);
void SeqListPushFront(SeqList* ps, SLDateType x);
void SeqListPopFront(SeqList* ps);
void SeqListPopBack(SeqList* ps);
// 順序表查找
int SeqListFind(SeqList* ps, SLDateType x);
// 順序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x);
// 順序表刪除pos位置的值
void SeqListErase(SeqList* ps, int pos);
定義順序表
要實現(xiàn)順序表,就需要對順序表進行定義,在c語言中通常使用結構體進行寫入,包括順序表的容量,順序表中存在元素的個數(shù),順序表的主體
在對順序表的定義中存在兩種,如果不使用動態(tài)內存開辟,可以直接定義一個數(shù)組實現(xiàn)順序表,但由于數(shù)組容量是固定的,會把整個順序表固定大小,于是在這里采用動態(tài)內存開辟的方法實現(xiàn)順序表
首先對順序表進行定義
typedef int SLDateType;
typedef struct SeqList
{
SLDateType* a;
int size;
int capacity;
}SeqList;
接下來我們就對順序表的各項功能進行依次實現(xiàn)
順序表初始化
把順序表的結構體定義完成后就可以創(chuàng)建一個順序表了,創(chuàng)建好初始值后就要對順序表進行一定的初始化內容
代碼實現(xiàn)如下
void SeqListInit(SeqList* ps)
{
assert(ps);
ps->a = (SLDateType*)malloc(sizeof(SLDateType) * 4);
if (ps->a == NULL)
{
perror("malloc fail");
return;
}
ps->size = 0;
ps->capacity = 4;
}
關于assert函數(shù)
assert的作用是斷言,主要是用來進行條件判斷,例如這里檢測ps,意思就是檢測ps是否為空指針,如果ps是空指針后續(xù)的操作就不必而行了,這樣有利于檢查錯誤信息,當運行到該語句結論為假時,會直接終止代碼,算是暴力檢查的一種方法
順序表的銷毀
創(chuàng)建完順序表后就要對順序表進行銷毀,銷毀的就是把它對應的空間釋放,置空指針,返回初始值
代碼實現(xiàn)如下
void SeqListDestroy(SeqList* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
}
關于置空指針
一般來說,把相關空間釋放后為了避免出現(xiàn)野指針的情況要把指針置空,但不進行指針的置空在一些情況下也是可以的,一般釋放空間后都會緊跟置空指針
打印順序表
將順序表里的信息打印到屏幕上,進行可視化觀察有無錯誤信息
代碼實現(xiàn)如下
void SeqListPrint(SeqList* ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
順序表的尾插
將一個數(shù)據(jù)插入到順序表中就涉及到了順序表的尾插
思路也很簡單,首先看原來順序表的容量是否滿足要求,如果不滿足就進行一定的擴容,再把要插入的數(shù)據(jù)放到順序表的尾部即可
如何實現(xiàn)檢查容量?
如果順序表的size和capacity是一致的,說明已經(jīng)滿了,到達上限了
因此函數(shù)實現(xiàn)如下
void SLCheckCapacity(SeqList* ps)
{
assert(ps);
SLDateType* tmp = NULL;
if (ps->capacity == ps->size)
{
tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * ps->capacity * 2);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
ps->a = tmp;
ps->capacity *= 2;
printf("擴容成功 當前容量%d\n", ps->capacity);
}
}
但是由于后續(xù)還有再規(guī)定位置插入元素的情況,我們可以直接先寫在x位置插入元素的情況
因此函數(shù)實現(xiàn)就變成了實現(xiàn)在x位置插入元素
函數(shù)實現(xiàn)如下
void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
SLCheckCapacity(ps);
int end = ps->size - 1;
while (pos <= end)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[pos] = x;
ps->size ++ ;
}
有了在x位置插入元素函數(shù)的實現(xiàn),對于在尾部插入函數(shù)只需要將x換成size即可
void SeqListPushBack(SeqList* ps, SLDateType x)
{
assert(ps);
SeqListInsert(ps,ps->size,x);
}
順序表的頭插
和順序表的尾插相似,當我們有了在x位置插入元素的函數(shù)時,這些需求就很好寫了
void SeqListPushFront(SeqList* ps, SLDateType x)
{
assert(ps);
SeqListInsert(ps, 0, x);
}
順序表的頭刪
有了前面的想法,我們也把在x位置的元素進行刪除封裝成一個函數(shù)
函數(shù)實現(xiàn)如下
void SeqListErase(SeqList* ps, int pos)
{
assert(pos >= 0 && pos < ps->size);
int end = ps->size-1;
while (pos <= end)
{
ps->a[pos] = ps->a[pos + 1];
pos++;
}
ps->size--;
}
那么頭刪就是把標號為0的元素刪除
具體函數(shù)實現(xiàn)如下
void SeqListPopFront(SeqList* ps)
{
assert(ps);
SeqListErase(ps, 0);
}
順序表的尾刪
有了頭刪的想法,尾刪和頭刪基本一致
void SeqListPopBack(SeqList* ps)
{
assert(ps);
int end = ps->size - 1;
SeqListErase(ps, end);
}
順序表定向位置查找
最簡單的功能,只需要遍歷順序表即可文章來源:http://www.zghlxwxcb.cn/news/detail-612796.html
int SeqListFind(SeqList* ps, SLDateType x)
{
assert(ps);
for(int i=0;i<ps->size;i++)
{
if (ps->a[i] == x)
return i;
}
return -1;
}
整體來說順序表是數(shù)據(jù)結構入門的部分,難度偏低文章來源地址http://www.zghlxwxcb.cn/news/detail-612796.html
到了這里,關于數(shù)據(jù)結構:手撕順序表---順序表增刪查改尋找功能的實現(xiàn)的文章就介紹完了。如果您還想了解更多內容,請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章,希望大家以后多多支持TOY模板網(wǎng)!