線性表
- 線性表功能以及
- 線性表的介面實作
線性表功能以及
線性表有動態線性表和靜態線性表，線性表本質是有限序列，
線性表和陣列的區別：
- 陣列的大小是有限的 不可動態增加或減少，
- 陣列的訪問可以直接下標參考，效率更高
- 線性表是通過結構體實作的，線性表本質是一個結構體陣列，
線性表的介面實作
介面實作與學籍管理系統，通訊錄等無出其右，均是對結構體進行增 刪 查 改 看
- 創建一個結構體
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a; // 在結構體SeqList中開辟動態陣列a
size_t size; // 陣列中已經存放的有效資料數量
size_t capicity; // 最大可存放資料數量
}SeqList;
該結構體在記憶體中存放是一體的 如圖
如圖 線性表的a指標開辟了一塊連續的記憶體空間
可以見得 順序表的本質是通過開辟一個類似a陣列的連續空間 該空間 可伸縮，但是必須連續存放，
- 順序表的初始化
斷言的使用： assert可以快速診斷出傳進來的指標是否為空
使用memset進行初始化
注意： 此變數可不調入進來
上述代碼 有什么問題呢？
越界訪問 可見 初始化capicity個空間大小
void SeqListInit(SeqList* ps, size_t capicity)
{
assert(ps);
memset(ps, 0, sizeof(SeqList));
printf("Init is ok!");
}
- 線性表的列印
線性表的列印 本質是對a指標指向的記憶體空間的訪問
void SeqListprint(SeqList* ps)
{
assert(ps->a);
for (size_t i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]); // ps->a 是對a的訪問
// a的下標參考就是對a的解應用
//*(ps->a+i)也可
}
}
注意 *(ps->a+i)是對a是一個指向連續空間的指標的更為準確解釋 ps->a[i]則更為直觀，
- 線性表的增容
線性表可增容比較容易是他和陣列的區別
void CheckCapacity(SeqList* ps)
{
if (ps->size == ps->capicity-2)//不可相等進 因為我們是從0開始計數的，否則會出現指標越界問題
{
size_t newcapicity = ps->capicity==0?4:2 * ps->capicity;
SeqList* newroom = (SeqList*)realloc
(ps->a, newcapicity * sizeof(SLDataType));
// 開辟的空間是給指標a使用的 所以要開辟和a一樣屬性的空間
assert(newroom);
// 注意斷言的使用
ps->a = newroom;
ps->capicity = newcapicity;
}
注意： 不可相等進 因為我們是從0開始計數的，否則會出現指標越界問題
可稍作優化 在函式外判斷是否需要擴容 則可省去每次都呼叫函式的時間
void CheckCapacity(SeqList* ps)
{
size_t newcapicity = ps->capicity==0?4:2 * ps->capicity;
SeqList* newroom = (SeqList*)realloc
(ps->a, newcapicity * sizeof(SLDataType));
// 開辟的空間是給指標a使用的 所以要開辟和a一樣屬性的空間
assert(newroom);
// 注意斷言的使用
ps->a = newroom;
ps->capicity = newcapicity;
}
注意 不可忘記assert 防止出現空指標，
- 線性表的放入
尾插：
void SeqListPushBack(SeqList* ps, SLDataType x)
{
assert(ps);
if (ps->capicity == ps->size)
{
CheckCapacity(ps);
}
*(ps->a+ps->size)= x;
ps->size++;
}
注：
a是一個指標 一定要對a進行解參考 ，
頭插
頭插則是一個后面覆寫前面的問題，
void SeqListpushFront(SeqList* ps, SLDataType x)
{
assert(ps); //勿忘判斷
if (ps->capicity == ps->size)
{
CheckCapacity(ps);
}
int i = ps->size;
while (i > 0)
{
*(ps->a + i ) = *(ps->a + i-1);// 此處切記 計數從0開始
i--;
}
*(ps->a + i) = x;
ps->size++;
}
- 線性表的洗掉
線性表的尾刪： 與尾插一樣 都是加加減減操作，
void SeqListPopBack(SeqList* ps)
{
assert(ps);
ps->size--;
ps->a[ps->size] = 0;
}
線性表的頭刪： 線性表的頭刪也是覆寫
void SeqListPopFront(SeqList* ps)
{
assert(ps);
int i = 0;
while (i<ps->size)
{
*(ps->a + i) = *(ps->a + i + 1);
i++;
}
ps->size--;
}
- 線性表的查找
void SeqListFind(SeqList* ps, SLDataType x)
{
assert(ps);
int i = 0;
while (i<ps->size)
{
if (*(ps->a + i) == x)
{
printf("%d", i);
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/276665.html
標籤：其他
上一篇：爬蟲入門級別教程(小白水平)
下一篇：藍橋杯單片機準備目錄