目錄
一、線性表
二、順序表
2.1概念及結(jié)構(gòu)
2.2接口實(shí)現(xiàn)
2.3動(dòng)態(tài)順序表的創(chuàng)建
2.3動(dòng)態(tài)順序表的初始化
2.3.1傳值初始化
2.3.2傳址初始化
2.4動(dòng)態(tài)順序表的清空
2.5動(dòng)態(tài)順序表的擴(kuò)容
2.6動(dòng)態(tài)順序表內(nèi)容的打印
三、動(dòng)態(tài)順序表的使用
3.1尾插尾刪
3.1.1尾插
3.1.2尾刪
3.2頭插頭刪
3.2.1頭插
3.2.2頭刪
3.3在pos位置插入x
3.4刪除pos位置的值
3.5修改某個(gè)位置的值
四、完整代碼
一、線性表
線性表(linear list)是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實(shí)際中廣泛使
用的數(shù)據(jù)結(jié)構(gòu),常見的線性表:順序表、鏈表、棧、隊(duì)列、字符串...
線性表在邏輯上是線性結(jié)構(gòu),也就說(shuō)是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的,
線性表在物理上存儲(chǔ)時(shí),通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲(chǔ)。
二、順序表
2.1概念及結(jié)構(gòu)
順序表是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu),一般情況下采用數(shù)組存
儲(chǔ)。在數(shù)組上完成數(shù)據(jù)的增刪查改。
順序表一般分為:
靜態(tài)順序表:使用定長(zhǎng)數(shù)組儲(chǔ)存元素。
//靜態(tài)順序表
#define N 100
struct SeqList
{
int a[N];//定長(zhǎng)數(shù)組
int size;//有效數(shù)據(jù)的個(gè)數(shù)
};
?
缺點(diǎn):不是很靈活
動(dòng)態(tài)順序表:使用動(dòng)態(tài)開辟的數(shù)組儲(chǔ)存。
2.2接口實(shí)現(xiàn)
靜態(tài)順序表只適用于確定知道需要存多少數(shù)據(jù)的場(chǎng)景。靜態(tài)順序表的定長(zhǎng)數(shù)組導(dǎo)致N定大了,空
間開多了浪費(fèi),開少了不夠用。所以現(xiàn)實(shí)中基本都是使用動(dòng)態(tài)順序表,根據(jù)需要?jiǎng)討B(tài)的分配空間
大小,所以下面我們實(shí)現(xiàn)動(dòng)態(tài)順序表。
所謂動(dòng)態(tài)其實(shí)指的這個(gè)結(jié)構(gòu)體里的指針是動(dòng)態(tài)內(nèi)存開辟來(lái)的,是可變的,用的時(shí)候動(dòng)態(tài)開辟,不夠的話繼續(xù)開辟,程序結(jié)束的時(shí)候釋放。
2.3動(dòng)態(tài)順序表的創(chuàng)建
typedef int SLDatatype;//將int重命名為SLDatatype
typedef struct SeqList
{
SLDatatype* a;//指向動(dòng)態(tài)開辟的數(shù)組
SLDatatype capacity;//容量
SLDatatype size;//有效數(shù)據(jù)的個(gè)數(shù)
}SL;//將結(jié)構(gòu)體SeqList重命名為SL
2.3動(dòng)態(tài)順序表的初始化
2.3.1傳值初始化
//傳值初始化
void SLInit(SL s)
{
s.a = NULL;
s.size = 0;
s.capacity = 0;
}
?函數(shù)那個(gè)章節(jié)我們學(xué)過形參只是實(shí)參的臨時(shí)拷貝,并沒有實(shí)際作用,生命周期短,出了函數(shù)的作用域就會(huì)銷毀,我們不考慮這種初始化方式。
2.3.2傳址初始化
//傳址初始化
void SLInit(SL* ps)
{
ps->a = 0;
ps->capacity = 0;
ps->size = 0;
}
void SLInit(SL* ps)
{
ps->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);//開辟了4個(gè)字節(jié)的空間
if (ps->a == NULL)
{
perror("malloc failed");
exit(-1);
}
ps->capacity = 4;//開辟了空間就要給容量賦值
ps->size = 0;
}
上面兩種初始化方式都可以給予結(jié)構(gòu)體成員變量賦值,但是我們使用第二種,因?yàn)榈诙N為我們開辟了空間。
2.4動(dòng)態(tài)順序表的清空
void SLDestr(SL* ps)
{
free(ps->a);
ps->a = NULL;
ps->capacity = 0;//內(nèi)存釋放,容量清零
ps->size = 0;//內(nèi)存釋放,有效數(shù)據(jù)清零
}
2.5動(dòng)態(tài)順序表的擴(kuò)容
void SLCheckcapacity(SL* ps)
{
if (ps->size == ps->capacity)
{
SLDatatype* tmp = (SLDatatype*)realloc(ps->a, ps->capacity * 2 *( sizeof(SLDatatype)));//擴(kuò)容尾原來(lái)的倍數(shù)
if (tmp == NULL)
//判斷是否擴(kuò)容失敗
{
perror("realloc failed");
exit(-1);
}
ps->a = tmp;
ps->capacity *= 2;//擴(kuò)容后修改原來(lái)的容量
}
}
這就是所謂的動(dòng)態(tài),當(dāng)我們空間不夠時(shí),就需要開辟新的空間,使用realloc函數(shù)要注意是否開辟成功,定義一個(gè)中間指針,當(dāng)開辟成功時(shí)將這個(gè)指針賦值給動(dòng)態(tài)數(shù)組中的指針。?
2.6動(dòng)態(tài)順序表內(nèi)容的打印
void SLprint(SL* ps)
{
int i = 0;
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
size為有效數(shù)據(jù)個(gè)數(shù),使用循環(huán)打印其中的有效數(shù)據(jù)。?
三、動(dòng)態(tài)順序表的使用
3.1尾插尾刪
3.1.1尾插
void SLPushBack(SL* ps, SLDatatype x)
{
SLCheckcapacity(ps);//檢查空間是否足夠插入
ps->a[ps->size] = x;//賦值
ps->size++;//插入一個(gè)有效數(shù)據(jù),有效數(shù)據(jù)個(gè)數(shù)加一
}
?首先一定要檢查規(guī)矩是否足夠,根據(jù)上面開辟的空間,容量為4,有效數(shù)據(jù)為size為0,所以從第一個(gè)空間開始插入數(shù)據(jù)。
3.1.2尾刪
//尾刪
void SLPopBack(SL* ps)
{
assert(ps->size > 0);//判斷是否會(huì)造成越界
if (ps->size == 0)
{
return;
}
ps->size--;//刪除一個(gè)數(shù)據(jù),有效數(shù)據(jù)個(gè)數(shù)減一
}
插入數(shù)據(jù)后size的大小也會(huì)變化,數(shù)組中最后一個(gè)數(shù)字的下標(biāo)剛好和size的大小一樣我們只需要將size減1就行。?
3.2頭插頭刪
3.2.1頭插
void SLPushFront(SL* ps, SLDatatype x)
{
SLCheckcapacity(ps);//檢查空間是否足夠
int end = ps->size;
while (end > 0)
{
ps->a[end] = ps->a[end - 1];//將前一個(gè)數(shù)據(jù)后移動(dòng)
end--;
}
ps->a[0] = x;//將x賦給初始位置
ps->size++;//加入一個(gè)數(shù)字,有效數(shù)據(jù)個(gè)數(shù)加1
}
?老規(guī)矩一定要檢查空間是否足夠,頭部插入數(shù)據(jù)我們只需要將原來(lái)的數(shù)據(jù)往后移動(dòng)一格就將第一格的位置空出來(lái),再將數(shù)值插入就行,插入一個(gè)數(shù)據(jù),有效數(shù)據(jù)加1即可。
3.2.2頭刪
void SLPopFront(SL* ps)
{
assert(ps->size > 0);//防止越界訪問
if (ps->size==0)
{
return;
}
int begin = 0;
while (begin < ps->size)
{
ps->a[begin] = ps->a[begin+1];//將后一個(gè)數(shù)據(jù)往前移動(dòng)
begin++;
}
ps->size--;//減少一個(gè)數(shù)字,有效數(shù)據(jù)減1
}
這里的刪除并不是真正意義上的刪除,我們只需要將原來(lái)的數(shù)據(jù)往前移動(dòng)一位使后一位的數(shù)據(jù)覆蓋在前一位,這就做到了刪除,順便再將有效數(shù)據(jù)減1就行。?
3.3在pos位置插入x
void SLInsert(SL* ps, int pos, int x)
{
assert(pos >= 0 && pos <= ps->size);//防止越界訪問
SLCheckcapacity(ps);
int end = ps->size;
while (end >=pos)
{
ps->a[end] = ps->a[end-1];//和頭插的思想差不多,將數(shù)據(jù)后移
end--;
}
ps->a[pos] = x;//將x賦值給pos位置
ps->size++;//有效數(shù)據(jù)加1
}
我們可以這樣理解:將pos看成初始位置,是不是就轉(zhuǎn)化為頭插了?按照頭插的思想就可以完成在pos位置上插入x。?
3.4刪除pos位置的值
void SLErase(SL* ps, int pos)
{
assert(pos >= 0 && pos <= ps->size);//防止越界訪問
SLCheckcapacity(ps);
int begin = pos;
while (begin < ps->size)
{
ps->a[begin] = ps->a[begin + 1];//和頭刪的思想差不多,將數(shù)據(jù)前移
begin++;
}
ps->size--;//有效數(shù)據(jù)減1
}
我們會(huì)發(fā)現(xiàn)3.4和3.5不僅可以做到某個(gè)位置值的插入和刪除,也可以做到尾插尾刪和頭插頭刪。?
3.5修改某個(gè)位置的值
void SLModify(SL* ps, SLDatatype pos, SLDatatype x)
{
assert(pos >= 0 && pos < ps->size);//防止越界
ps->a[pos] = x;
}
?這樣修改某個(gè)位置的值看起來(lái)是挺麻煩,但是是為了安全考慮。文章來(lái)源:http://www.zghlxwxcb.cn/news/detail-701531.html
四、完整代碼
#define _CRT_SECURE_NO_WARNINGS 67
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
//靜態(tài)順序表
//#define N 100
//struct SeqList
//{
// int a[N];//定長(zhǎng)數(shù)組
// int size;//有效數(shù)據(jù)的個(gè)數(shù)
//};
//動(dòng)態(tài)順序表
//創(chuàng)建
typedef int SLDatatype;
typedef struct SeqList
{
SLDatatype* a;//指向動(dòng)態(tài)開辟的數(shù)組
SLDatatype capacity;//容量
SLDatatype size;//有效數(shù)據(jù)的個(gè)數(shù)
}SL;
//傳值初始化
//void SLInit(SL s)
//{
// s.a = NULL;
// s.size = 0;
// s.capacity = 0;
//}
//傳址初始化
//void SLInit(SL* ps)
//{
// ps->a = 0;
// ps->capacity = 0;
// ps->size = 0;
//}
void SLInit(SL* ps)
{
ps->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);//開辟了4個(gè)字節(jié)的空間
if (ps->a == NULL)
{
perror("malloc failed");
exit(-1);
}
ps->capacity = 4;
ps->size = 0;
}
//清空
void SLDestr(SL* ps)
{
free(ps->a);
ps->a = NULL;
ps->capacity = 0;
ps->size = 0;
}
//打印
void SLprint(SL* ps)
{
int i = 0;
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
//檢查容量
void SLCheckcapacity(SL* ps)
{
if (ps->size == ps->capacity)
{
SLDatatype* tmp = (SLDatatype*)realloc(ps->a, ps->capacity * 2 *( sizeof(SLDatatype)));//擴(kuò)容尾原來(lái)的倍數(shù)
if (tmp == NULL)
{
perror("realloc failed");
exit(-1);
}
ps->a = tmp;
ps->capacity *= 2;
}
}
//尾插
void SLPushBack(SL* ps, SLDatatype x)
{
SLCheckcapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
//尾刪
void SLPopBack(SL* ps)
{
assert(ps->size > 0);
if (ps->size == 0)
{
return;
}
ps->size--;
}
//頭插
void SLPushFront(SL* ps, SLDatatype x)
{
SLCheckcapacity(ps);
int end = ps->size;
while (end > 0)
{
ps->a[end] = ps->a[end - 1];
end--;
}
ps->a[0] = x;
ps->size++;
}
//頭刪
void SLPopFront(SL* ps)
{
assert(ps->size > 0);
if (ps->size==0)
{
return;
}
int begin = 0;
while (begin < ps->size)
{
ps->a[begin] = ps->a[begin+1];
begin++;
}
ps->size--;
}
//在pos位置插入x
void SLInsert(SL* ps, int pos, int x)
{
assert(pos >= 0 && pos <= ps->size);
SLCheckcapacity(ps);
int end = ps->size;
while (end >=pos)
{
ps->a[end] = ps->a[end-1];
end--;
}
ps->a[pos] = x;
ps->size++;
}
//刪除pos位置的值
void SLErase(SL* ps, int pos)
{
assert(pos >= 0 && pos <= ps->size);
SLCheckcapacity(ps);
int begin = pos;
while (begin < ps->size)
{
ps->a[begin] = ps->a[begin + 1];
begin++;
}
ps->size--;
}
int SLFind(SL* ps, int x)
{
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
return i;
}
return -1;
}
void SLModify(SL* ps, SLDatatype pos, SLDatatype x)
{
assert(pos >= 0 && pos < ps->size);
ps->a[pos] = x;
}
int main()
{
SL s1;
//傳值初始化
//SLInit(s1);
//傳址初始化
SLInit(&s1);
//尾插
SLPushBack(&s1, 1);
SLPushBack(&s1, 2);
SLPushBack(&s1, 3);
SLPushBack(&s1, 4);
SLPushBack(&s1, 5);
SLPushBack(&s1, 6);
SLPushBack(&s1, 7);
//尾插測(cè)試
printf("尾插:\n");
SLprint(&s1);
//尾刪
SLPopBack(&s1);
//尾刪測(cè)試
printf("尾刪:\n");
SLprint(&s1);
//頭插
SLPushFront(&s1,10);
//頭插測(cè)試
printf("頭插:\n");
SLprint(&s1);
//頭刪
SLPopFront(&s1);
//頭刪測(cè)試
printf("頭刪:\n");
SLprint(&s1);
//在pos位置插入x
SLInsert(&s1, 0, 100);
//pos插入x測(cè)試
printf("pos位置插入x\n");
SLprint(&s1);
//刪除pos位置的值
SLErase(&s1, 0);
//測(cè)試
printf("刪除pos位置的值\n");
SLprint(&s1);
//改
SLModify(&s1, 2, 1);
printf("修改某個(gè)位置上的值:\n");
//
SLprint(&s1);
//清空
SLDestr(&s1);
return 0;
}
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-701531.html
到了這里,關(guān)于詳解初階數(shù)據(jù)結(jié)構(gòu)之順序表(SeqList)——單文件文件實(shí)現(xiàn)SeqList的增刪查改的文章就介紹完了。如果您還想了解更多內(nèi)容,請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持TOY模板網(wǎng)!