目錄
一、線性表
二、順序表
1.實現動態順序表
SeqList.h
SeqList.c
Test.c
問題
經驗:free 出問題,2種可能性
解決問題
(2)尾刪
(3)頭插,頭刪
(4)在 pos 位插
(5)在 pos 位刪
(6)查找
2.整體代碼
SeqList.h
SeqList.c
test.c
一、線性表
線性表(linear list)是 n 個具有相同特性的數據元素的有限序列。 線性表是一種在實際中廣泛使用的數據結構,常見的線性表:順序表、鏈表、棧、隊列、字符串。
線性表在邏輯上是線性結構,也就說是連續的一條直線。但是在物理結構上并不一定是連續的,線性表在物理上存儲時,通常以數組和鏈式結構的形式存儲。
二、順序表
順序表是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構,一般情況下采用數組存儲。在數組上完成數據的增刪查改。
分類:
(1)靜態順序表:使用定長數組存儲元素
(2)動態順序表:使用動態開辟的數組存儲
靜態順序表只適用于確定知道需要存多少數據的場景。靜態順序表的定長數組導致N定大了,空間開多了浪費,開少了不夠用。所以現實中基本都是使用動態順序表,根據需要動態的分配空間大小
1.實現動態順序表
SeqList.h?
為方便替換成其他類型,我們將這些類型統一重命名為 SLDataType
typedef int SLDataType;
#define INIT_CAPACITY 4 // 初始化容量typedef struct SeqList
{SLDataType* a;int size; // 有效數據個數int capacity; // 空間容量
}SL;// 增刪查改
void SLInit(SL* ps);
void SLDestroy(SL* ps);//打印順序表數據
void SLPrint(SL* ps);void SLPushBack(SL* ps, SLDataType x); // 尾插
void SLPopBack(SL* ps); // 尾刪
void SLPushFront(SL* ps, SLDataType x); // 頭插
void SLPopFront(SL* ps); // 頭刪// 擴容,2倍合適
void SLCheckCapacity(SL* ps);
SeqList.c
void SLInit(SL* ps)
{assert(ps);ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);if (ps->a == NULL){perror("malloc fail");return;}ps->size = 0;ps->capacity = INIT_CAPACITY;
}void SLDestroy(SL* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0; // 結合性,從右往左賦值
}void SLPrint(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; ++i){printf("%d ", ps->a[i]);}printf("\n");
}// 擴容,2倍合適
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2);//思考這里對不對if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp; // 防止不是原地擴容ps->capacity *= 2;}}void SLPushBack(SL* ps, SLDataType x) // 尾插
{assert(ps);// 擴容 2倍合適SLCheckCapacity(ps);ps->a[ps->size++] = x;
}
Test.c
void TestSeqList1()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPrint(&s);SLDestroy(&s);
}int main()
{TestSeqList1();return 0;
}
運行上面的代碼,順序表里插入1234:,程序沒毛病
問題
void TestSeqList1()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPushBack(&s, 5);SLPrint(&s);SLDestroy(&s);
}
奇怪的事情發生了:
SLPushBack(&s, 6);
SLPushBack(&s, 7);
奇怪的事情又發生了:??
? 光標在閃
這里反反復復調試都發現不了問題
經驗:free 出問題,2種可能性
(1)野指針 或 位置不對。這種情況不多
eg:申請一塊空間,從中間位置釋放,報錯。(應該從起始位置釋放)
(2)指針指向的空間(數組)上面,可能有越界。
- 下標越界
- 開少了
解決問題
realloc 返回的是地址,->a,a 我們沒有動過,動的都是 a 指向的內容
free 有時候出問題,通常不是free ( ) 里面有問題,而是前面有越界
仔細查,動空間的只有 SLPushBack(? ? )
// 擴容,2倍合適
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2);//思考這里對不對if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp; // 防止原地擴容ps->capacity *= 2;}}void SLPushBack(SL* ps, SLDataType x) // 尾插
{assert(ps);// 擴容 2倍合適SLCheckCapacity(ps);ps->a[ps->size++] = x;
}
ps->a[ps->size++] = x; 邏輯沒有問題,問題大概率出現在擴容
先看下標越界了嗎?size 沒有越界的可能性
還有一種可能是開少了。
你以為你原來是 4 個,擴容到 8 個。你以為你有 8 個,實際上沒有 8 個。你當成 8 個訪問的呀,就越了。
8 個 SLDataType 是 4*8=32 字節。
ps->capacity * 2 這里是 4*2=8 字節
正確寫法:
// 擴容 2倍合適
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2);if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}
}void SLPushBack(SL* ps, SLDataType x) // 尾插
{assert(ps);SLCheckCapacity(ps);ps->a[ps->size++] = x;
}
?問題解決
(2)尾刪
void SLPopBack(SL* ps) // 尾刪
{assert(ps);//ps->a[ps->size - 1] = 0; 加上沒用ps->size--;
}
由 size 遍例順序表,size --?后,前 size-1個是有效數據,第 size 個訪問不到了
注意:這里不用釋放,一部分一部分釋放會報錯。
但是不用擔心,當我們不用這個順序表時會?SLDestroy(&s) ; 空間還是會釋放的
刪空了還刪,會報錯。所以要檢查
void SLPopBack(SL* ps) // 尾刪
{assert(ps);// 溫柔的檢查if (ps->size == 0)return;ps->size--;
}
斷言 assert 會直接告訴你哪出錯了,并且終止掉程序
void SLPopBack(SL* ps) // 尾刪
{assert(ps);// 暴力檢查assert(ps->size > 0);ps->size--;
}
(3)頭插,頭刪
要挪動數據,以實現順序表連續性
順序表尾插,尾刪效率不錯。頭插,頭刪效率不太行。但有時候就要頭插,頭刪
void SLPushFront(SL* ps, SLDataType x) // 頭插
{assert(ps);SLCheckCapacity(ps);//挪動memmove(&(ps->a[1]), &(ps->a[0]), sizeof(SLDataType) * ps->size);//頭插ps->a[0] = x;ps->size++;
}void SLPopFront(SL* ps) // 頭刪
{assert(ps);assert(ps->size > 0);memmove(&(ps->a[0]), &(ps->a[1]), sizeof(SLDataType) * ps->size);ps->size--;
}
我們發現:插入N個數據。尾插時間復雜度:O(N)? ?? 頭插時間復雜度:O(N^2)
頭插1萬個數據,要執行1億次。所以,盡量避免使用頭插
疑問:為什么頭插用memmove庫函數了,時間復雜度還是O(N^2)
答:雖然我們用的是庫函數,一步到位,沒有用模擬實現。我們分析它的時間復雜度,還是要看到本質,本質就是模擬實現,通過模擬實現分析它的時間復雜度。
本質:
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];--end;}ps->a[0] = x;ps->size++;
}
可以看到,頭插1個數據,執行N次,時間復雜度O(N)。頭插N個數據,執行N^2次,時間復雜度O(N^2)? 從模擬實現的角度看,它是一個等差數列
(4)在 pos 位插
// 順序表在pos位置插入x
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);// 插入時 = size 相當于尾插SLCheckCapacity(ps);//挪動memmove(&(ps->a[pos + 1]), &(ps->a[pos]), sizeof(SLDataType) * (ps->size - pos));//插入ps->a[pos] = x;ps->size++;
}
我們可以簡化頭插(在第0位),尾插(在第size位)。
void SLPushBack(SL* ps, SLDataType x) // 尾插
{assert(ps);/*SLCheckCapacity(ps);ps->a[ps->size++] = x;*/SLInsert(ps, ps->size, x);
}void SLPushFront(SL* ps, SLDataType x) // 頭插
{assert(ps);/*SLCheckCapacity(ps);//挪動memmove(&(ps->a[1]), &(ps->a[0]), sizeof(SLDataType) * ps->size);//頭插ps->a[0] = x;ps->size++;*/SLInsert(ps, 0, x);
}
(5)在 pos 位刪
// 順序表刪除pos位置的值
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//覆蓋memmove(&(ps->a[pos]), &(ps->a[pos + 1]), sizeof(SLDataType) * (ps->size - pos - 1));ps->size--;
}
可以簡化 頭刪,尾刪 的代碼。
void SLPopBack(SL* ps) // 尾刪
{assert(ps);/*// 暴力檢查assert(ps->size > 0);溫柔的檢查//if (ps->size == 0)// return;ps->size--;*/SLErase(ps, ps->size - 1);
}void SLPopFront(SL* ps) // 頭刪
{assert(ps);/*assert(ps->size > 0);memmove(&(ps->a[0]), &(ps->a[1]), sizeof(SLDataType) * ps->size);ps->size--;*/SLErase(ps, 0);
}
疑問:用這個新的代碼尾刪,假設現在size = 8,根據上面代碼,最大容量 capacity 也 = 8。要尾刪,刪下標為7的位置,傳給 pos,pos+1 = 8 。SLErase 里面 &(ps->a[pos + 1]) 不會越界訪問嗎?
解答:這時要 memmove 移動?ps->size - pos - 1 = 0 個字節。我們看 memmove 模擬實現:num 是要移動的字節個數,這里 num = 0 ,循環沒進去,也就不存在越界訪問了
(6)查找
//順序表查找
int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (x == ps->a[i]){return i;}}return -1;
}
問:為什么刪除后,不用 realloc 回收一部分內存的使用權?
答:當擴容時,realloc 開內存,分為異地擴容,本地擴容。想要新開辟空間,如果原空間后面的大小夠,就本地擴容,效率高。后面大小不夠,就異地擴容,效率低。
而現代計算機內存空間的數量很多,不怕浪費,為保證運行效率,寧愿占著茅坑不拉屎。
當我們確認不再使用時,也會 SLDestroy 釋放全部空間
問:為什么不寫菜單?
答:數據結構部分,菜單沒有什么價值。而且不好調試。菜單一般在命令行程序,控制數據庫的服務器,會輸入選項(指令去控制)。
寫菜單的話,也不要一上來就寫菜單。先在 test.c 里寫一組一組測試 ,測的沒問題了,再寫菜單
2.整體代碼
SeqList.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLDataType;
#define INIT_CAPACITY 4 // 初始化容量typedef struct SeqList
{SLDataType* a;int size; // 有效數據個數int capacity; // 空間容量
}SL;// 增刪查改
void SLInit(SL* ps);
void SLDestroy(SL* ps);//打印順序表數據
void SLPrint(SL* ps);void SLPushBack(SL* ps, SLDataType x); // 尾插
void SLPopBack(SL* ps); // 尾刪
void SLPushFront(SL* ps, SLDataType x); // 頭插
void SLPopFront(SL* ps); // 頭刪// 順序表查找
int SLFind(SL* ps, SLDataType x);
// 順序表在pos位置插入x
void SLInsert(SL* ps, int pos, SLDataType x);
// 順序表刪除pos位置的值
void SLErase(SL* ps, int pos);// 擴容,2倍合適
void SLCheckCapacity(SL* ps);
SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"void SLInit(SL* ps)
{assert(ps);ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);if (ps->a == NULL){perror("malloc fail");return;}ps->size = 0;ps->capacity = INIT_CAPACITY;
}void SLDestroy(SL* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0; // 結合性,從右往左賦值
}void SLPrint(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; ++i){printf("%d ", ps->a[i]);}printf("\n");
}// 擴容 2倍合適
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2);if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}
}void SLPushBack(SL* ps, SLDataType x) // 尾插
{assert(ps);/*SLCheckCapacity(ps);ps->a[ps->size++] = x;*/SLInsert(ps, ps->size, x);
}void SLPopBack(SL* ps) // 尾刪
{assert(ps);/*// 暴力檢查assert(ps->size > 0);溫柔的檢查//if (ps->size == 0)// return;ps->size--;*/SLErase(ps, ps->size - 1);
}void SLPushFront(SL* ps, SLDataType x) // 頭插
{assert(ps);/*SLCheckCapacity(ps);//挪動memmove(&(ps->a[1]), &(ps->a[0]), sizeof(SLDataType) * ps->size);//頭插ps->a[0] = x;ps->size++;*/SLInsert(ps, 0, x);
}void SLPopFront(SL* ps) // 頭刪
{assert(ps);/*assert(ps->size > 0);memmove(&(ps->a[0]), &(ps->a[1]), sizeof(SLDataType) * ps->size);ps->size--;*/SLErase(ps, 0);
}//順序表查找
int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (x == ps->a[i]){return i;}}return -1;
}// 順序表在pos位置插入x
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);// 插入時 = size 相當于尾插SLCheckCapacity(ps);//挪動memmove(&(ps->a[pos + 1]), &(ps->a[pos]), sizeof(SLDataType) * (ps->size - pos));//插入ps->a[pos] = x;ps->size++;
}// 順序表刪除pos位置的值
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//覆蓋memmove(&(ps->a[pos]), &(ps->a[pos + 1]), sizeof(SLDataType) * (ps->size - pos - 1));ps->size--;
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"void TestSeqList1()//第一組測試用例
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPushBack(&s, 5);SLPushBack(&s, 6);SLPushBack(&s, 7);SLPushBack(&s, 8);SLPrint(&s);SLPopBack(&s);SLPopBack(&s);SLPrint(&s);SLPushFront(&s, 9);SLPushFront(&s, 10);SLPushFront(&s, 11);SLPushFront(&s, 12);SLPushFront(&s, 13);SLPushFront(&s, 14);SLPrint(&s);SLPopFront(&s);SLPopFront(&s);SLPopFront(&s);SLPrint(&s);SLInsert(&s, 3, 30);SLPrint(&s);SLErase(&s, 3);SLPrint(&s);int pos = SLFind(&s, 3);if (pos == -1){printf("沒找到\n");}else{printf("找到了,下標是:%d", pos);}SLDestroy(&s);
}int main()
{TestSeqList1();return 0;
}