柚子快報邀請碼778899分享：數(shù)據(jù)結(jié)構(gòu)——順序表
柚子快報邀請碼778899分享：數(shù)據(jù)結(jié)構(gòu)——順序表
一.過程解析
首先我們需要三個文件，分別是頭文件——SeqList.h,具體操作文件——SeqList.c,以及測試文件——test.c?
首先在頭文件中我們寫出需要用到的內(nèi)容
#pragma once
#include
#include
#include
//定義動態(tài)順序表結(jié)構(gòu)
typedef struct SeqList {
int* arr;
int capacity;//空間大小
int size;//有效數(shù)據(jù)個數(shù)
}SL;
typedef int SLDatatype;
//typedef struct SeqList SL;
//初始化
void SLTnit(SL* ps);//函數(shù)聲明
//銷毀
void SLDestroy(SL* ps);
//插入數(shù)據(jù)
void SLPushBack(SL* ps, SLDatatype x);
void SLPushFront(SL* ps, SLDatatype x);
//打印
void SLPrint(SL* ps);
//判斷空間是否可以使用
void SLCheckCapacity(SL* ps);
//刪除
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);
//在指定位置之前插入數(shù)據(jù)
void SLInsert(SL* ps, SLDatatype x, int pos);
//刪除指定位置的數(shù)據(jù)
void SLErase(SL* ps, int pos);
//查找指定位置的數(shù)據(jù)
int SLFind(SL* ps, SLDatatype x);
根據(jù)頭文件的內(nèi)容，我們一步步進行——代碼的實現(xiàn)在SeqList.c中進行，測試在test.c中進行
1.初始化的實現(xiàn)
在SeqList.c中可以寫出以下代碼：
//初始化
void SLTnit(SL* ps)
{
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
在這個環(huán)節(jié)中有一個易錯點，如果我們最開始在頭文件中寫的是
void SLTnit(SL s);
則在SeqList.c中應(yīng)該寫
void SLTnit(SL s)
{
s.arr = NULL;
s.size = s.capacity = 0;
}
?這樣看似也正確，但是在測試時卻會出現(xiàn)
那么是為什么呢？原因就在于我們忽略了傳值調(diào)用和傳址調(diào)用的區(qū)別，在這里應(yīng)該用傳址調(diào)用！
2.銷毀的實現(xiàn)?
當我們實現(xiàn)初始化時，同理就可以實現(xiàn)銷毀
//銷毀
void SLDestroy(SL* ps)
{
if (ps->arr)//相當于ps->arr!=NULL
{
free(ps->arr);
}
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
則在test.c中有以下框架：
#include"SeqList.h"
void SLtest01()
{
SL s;
SLTnit(&s);
SLDestroy(&s);
}
int main()
{
SLtest01();
return 0;
}
有基本框架，我們可以進行其他的代碼實現(xiàn)
3.插入數(shù)據(jù)的代碼實現(xiàn)
插入有兩種，一種是在數(shù)據(jù)的最前面插入——頭插，一種是在數(shù)據(jù)的最后面插入——尾插；
3.1尾插
因為我們要在數(shù)據(jù)中插入一個數(shù)，我們首先應(yīng)該想到的是原有的空間是否充足，因此我們需要寫一個函數(shù)來進行判斷——這時我們需要運用到一個函數(shù)realloc
在MSDN中有
void *realloc( void *memblock, size_t size );
又因為我們不能確定空間是否可以申請到，我們需要引入一個中間變量，可以定義為SLDatatype* tmp，那么問題又來了，當空間不夠使，我們應(yīng)該怎樣擴容呢？
通常，增容我們是成倍數(shù)的增加，比如2,3......（最常用的是2），那么我們?yōu)槭裁床豢梢砸淮卧黾右粋€呢，這樣沒有了空間的浪費了，這時因為——增容的操作本身就有一定的程序性能的消耗，如果頻繁地增容很可能導(dǎo)致程序效率低下！
3.1.1 判斷空間是否充足的代碼實現(xiàn)
void SLCheckCapacity(SL* ps)
{
if (ps->size == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//考慮等于0的情況
SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype));//應(yīng)為字節(jié)數(shù)
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
}
在這個代碼中我們需要注意的是：
1.不能忽略ps->capacity==0的情況；
2.必須要引入中間變量；
3.注意運用realloc我么申請的是字節(jié)數(shù)。
3.1.2 尾插的代碼實現(xiàn)
首先我們應(yīng)該先判斷傳入的數(shù)據(jù)的地址是否為空，有兩種方式：
第一種：
//第一種
if (ps == NULL)
{
return;
}
第二種：
//第二種
assert(ps);//等價于assert(ps!=NULL)
3.2頭插?
?在頭插中我們需要進行數(shù)據(jù)整體后移一位的操作，然后讓第一個位置為指定數(shù)據(jù)
代碼實現(xiàn)：
void SLPushFront(SL* ps, SLDatatype x)
{
assert(ps);
SLCheckCapacity(ps);
//數(shù)據(jù)整體后移一位
for (int i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
//下標為0的位置
ps->arr[0] = x;
ps->size++;
}
需要注意的是，在末尾我們不要忘了ps->size的自增。?
4.刪除數(shù)據(jù)的代碼實現(xiàn)?
刪除數(shù)據(jù)也有兩種類型：尾刪和頭刪。
4.1 尾刪
代碼實現(xiàn)如下：
//尾刪
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size);//因為要刪除數(shù)據(jù)，所以ps->size不能為0
ps->arr[ps->size - 1] = -1;//語句1
ps->size--;
}
需要注意的是 ：語句1刪去也會成立。
4.2 頭刪
首先從下標為1的數(shù)據(jù)從后向前挪動一位
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size);
//數(shù)據(jù)整體向前挪動一位
for (int i = 0; i < ps->size-1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}
5.在指定位置之前插入數(shù)據(jù)
//在指定位置之前插入數(shù)據(jù)
void SLInsert(SL* ps, SLDatatype x, int pos)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
SLCheckCapacity(ps);
//pos及之后的數(shù)據(jù)向后移動
for (int i = ps->size; i > pos; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[pos] = x;
ps->size++;
}
需要注意的是：
1.在插入之前空間是否充足；
2.注意i的取值范圍;
3.pos等于0時為在第一個數(shù)據(jù)前插入，pos等于ps->size時為在最后一個數(shù)的后面插入。
?6.刪除指定位置的數(shù)據(jù)
先刪除指定位置的數(shù)據(jù)，然后位于其后的數(shù)據(jù)整體向前挪動一位。
//刪除指定位置的數(shù)據(jù)
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
//pos之后的數(shù)據(jù)整體向后挪動一位
for (int i = pos; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}
7.查找數(shù)據(jù)
查找數(shù)據(jù)較簡單，具體如下：
//查找指定位置的數(shù)據(jù)
int SLFind(SL* ps, SLDatatype x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return 1;
}
}
//如果沒有找到
return -1;
}
順序表在這里就大概結(jié)束了！
需要注意的是：在寫的過程中，要邊寫邊測試（本篇文章中省略了檢驗的過程）?。?！
二.總的代碼（SeqList.c中的）
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
//初始化
void SLTnit(SL* ps)
{
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
//銷毀
void SLDestroy(SL* ps)
{
if (ps->arr)//相當于ps->arr!=NULL
{
free(ps->arr);
}
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
//判斷空間是否可以使用
void SLCheckCapacity(SL* ps)
{
if (ps->size == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//考慮等于0的情況
SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype));//應(yīng)為字節(jié)數(shù)
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
}
//插入數(shù)據(jù)
//尾插
void SLPushBack(SL* ps, SLDatatype x)
{
//第二種
assert(ps);//等價于assert(ps!=NULL)
第一種
//if (ps == NULL)
//{
// return;
//}
SLCheckCapacity(ps);
ps->arr[ps->size++] = x;
}
void SLPushFront(SL* ps, SLDatatype x)
{
assert(ps);
SLCheckCapacity(ps);
//數(shù)據(jù)整體后移一位
for (int i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
//下標為0的位置
ps->arr[0] = x;
ps->size++;
}
//刪除
//尾刪
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size);//因為要刪除數(shù)據(jù)，所以ps->size不能為0
ps->arr[ps->size - 1] = -1;
ps->size--;
}
//頭刪
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size);
//數(shù)據(jù)整體向前挪動一位
for (int i = 0; i < ps->size-1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}
//在指定位置之前插入數(shù)據(jù)
void SLInsert(SL* ps, SLDatatype x, int pos)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
SLCheckCapacity(ps);
//pos及之后的數(shù)據(jù)向后移動
for (int i = ps->size; i > pos; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[pos] = x;
ps->size++;
}
//刪除指定位置的數(shù)據(jù)
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
//pos之后的數(shù)據(jù)整體向后挪動一位
for (int i = pos; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}
//查找指定位置的數(shù)據(jù)
int SLFind(SL* ps, SLDatatype x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return 1;
}
}
//如果沒有找到
return -1;
}
好了，就到這里，我們下一個知識點見(*￣︶￣)！
柚子快報邀請碼778899分享：數(shù)據(jù)結(jié)構(gòu)——順序表
參考文章
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點和立場。
轉(zhuǎn)載請注明，如有侵權(quán)，聯(lián)系刪除。
Farfetch優(yōu)選坊
