🎉🎉想快速入門資料結構，推薦訂閱作者的初階資料結構專欄！此專欄預計更新：順序表，鏈表，堆疊，佇列，二叉樹，排序演算法等等
🎉🎉初階資料結構我們通過c語言實作，所以此專欄也可以幫助大家鞏固大家的c語言知識
??寫在前面
首先非常感謝各位小伙伴對我的支持，在大家的支持下，我們的c進階專欄已經完結撒花啦！通過對c語言的學習，想必大家的代碼能力已經得到了一定的提升
所以今天我們開始入坑計算機中最重要的學科之一：資料結構
這是度娘對資料結構的定義
**資料結構是計算機存盤、組織資料的方式，**資料結構是指相互之間存在一種或多種特定關系的資料元素的集合，通常情況下，精心選擇的資料結構可以帶來更高的運行或者存盤效率，資料結構往往同高效的檢索演算法和索引技術有關，
解決的問題是：如何讓計算機存盤，組織我們需要存盤的資料
我們今天從最簡單的資料結構開始介紹：線性表中的順序表
目錄
- 一些定義
- 線性表
- 順序表
- 順序表的定義
- 初始化
- 增加元素
- 尾插
- 頭插
- 任意位置插入
- 洗掉元素
- 尾刪
- 頭刪
- 任意位置洗掉
- 查找
- 其它函式
- 列印函式
- 順序表銷毀
- 完整實作代碼
一些定義
線性表
同樣，先給出度娘上的定義
線性表（linear list）是資料結構的一種，一個線性表是n個具有相同特性的資料元素的有限序列，
線性表中資料元素之間的關系是一對一的關系，即除了第一個和最后一個資料元素之外，其它資料元素都是首尾相接的（注意，這句話只適用大部分線性表，而不是全部，比如，回圈鏈表邏輯層次上也是一種線性表（存盤層次上屬于鏈式存盤，但是把最后一個資料元素的尾指標指向了首位結點），
劃重點板塊：
線性表是一個有限的序列，存盤具有相同特性的元素
線性表可能在物理上不連續，但在邏輯結構上一定是連續的
線性表的邏輯結構
鏈表的邏輯結構
可以顯然觀察到，它們是全部呈線性的
順序表
本質是一個陣列，在物理上連續存放
而我們今天要實作的，就是順序表的增刪查改
順序表的定義
線性表的定義一般分為兩種方法：靜態的和動態的
我們先介紹線性表的基本框架
因為是采用陣列存放，所以我們需要定義一個陣列
另外，為了方便后續的操作和判斷，需要引入變數來記錄順序表中已存盤的元素個數
所以，我們用一個結構體來定義順序表
struct SeqList
{
int a[];//存盤元素的陣列
int size;//陣列此時的大小
}
邏輯結構就是這樣的
但這樣定義我們并沒有給出陣列的容量，所以這樣定義不正確
所以，我們可以用#define定義這個陣列的最大儲存容量，這也是我們的靜態實作方法
#define MAX 1000//定義一個最多能存盤1000個元素的順序表
struct SeqList
{
int arr[MAX];
int size;
}
但是，靜態順序表有一個很大的缺陷，就是定義多大的陣列無法確定
例如，1000容量的陣列只需存盤10個元素，會造成空間的大量浪費
或者，存盤100個元素我們只定義了10容量，存盤空間顯然不夠
所以我們可以考慮，要多少容量，我們就開多少容量
這就是引入了我們的動態定義方式
注意，這里用到了動態記憶體管理的知識，如果對動態記憶體管理還不太了解的小伙伴，可以看看我的文章.
因為動態記憶體開辟需要指標，所以我們可以定義一個指標變數arr，作為陣列
int* arr;
我們同樣需要size來記錄當前陣列存盤了多少元素
但是，我們現在要引入一個新的變數，用于記錄當前陣列的容量，當我們需要插入元素的時候，可以用這個變數檢查是否需要增容
struct SeqList
{
int* arr;
int size;
int capacity;//記錄當前陣列的最大容量
}
當然，我們還需要做一些改進
首先是typedef，簡化順序表的名稱
typedef struct SeqList
{
int* arr;
int size;
int capacity;//記錄當前陣列的最大容量
}SL;
其次，為了后續方便修改存盤型別，我們可以將資料型別重命名
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a;
int size;
int capacity;//記錄當前陣列的最大容量
}SL;
至此，我們的順序表定義全部完成
接下來是增刪查改的實作
初始化
注意！在使用順序表前，需要將順序表初始化！
void SeqListInit(SL* ps)
{
ps->a=NULL;//將陣列置空
ps->size=ps->capacity=0;//已存盤資料和容量都為0
}
增加元素
尾插
先講最容易實作的尾插
首先，我們剛初始化的陣列，容量為0，肯定不夠我們增加元素
而且后面也存在容量不夠需要開辟新空間的問題
所以我們可以先實作一個增容函式
void SeqListCheckCapacity(SL* ps)
{
if (ps->size == ps->capacity)//檢查是否存盤個數達到容量上限
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//我們一次增容兩倍，初始容量設定為4
SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity);
if (!tmp)
{
printf("%s\n", strerror(errno));
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
}
尾插，我們直接在陣列后面添加新元素即可，不需要過多的介紹
void SeqListPushBack(SL* ps, SLDataType x)
{
SeqListCheckCapacity(ps);//先檢查容量是否達到上限
ps->a[ps->size] = x;//直接在最后插入元素
ps->size++;//最后不要忘了將存盤個數+1
}
頭插
在順序表的最前面插入元素，實作要稍微復雜一點
因為順序表的存盤是按物理順序的，所以我們要存盤元素時，也需要將后面的資料依次往后挪動一位
void SeqListPushFront(SL* ps, SLDataType x)
{
SeqListCheckCapacity(ps);
int end = ps->size - 1;
while (end >= 0)
{
ps->a[end + 1] = ps->a[end];
end--;
}//while里面實作資料的挪動
ps->a[0] = x;
ps->size++;
}
任意位置插入
插入同樣需要挪動資料
為了避免資料覆寫，我們需要從后往前進行挪動資料
函式定義
void SeqListInsert(SL* ps, int pos, SLDataType x)
pos表示需要插入的位置
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
SeqListCheckCapacity(ps);
if (pos <= 1)
{
SeqListPushFront(ps, x);
}
else if (pos >= ps->size)
{
SeqListPushBack(ps, x);
}
else
{
int end = ps->size - 1;
while (end >= pos - 1)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[pos - 1] = x;
ps->size++;
}
}
洗掉元素
尾刪
同樣從最簡單的尾刪開始
假如我們的最初資料是這樣
我們的尾刪可以直接將size-1，讓順序表訪問不到我們刪的元素就行了
但如果陣列為空的話，我們的洗掉將會出現size為負數的問題
所以需要注意：在洗掉前，我們需要判斷陣列是否為空
void SeqListPopBack(SL* ps)
{
assert(ps->size);//判斷陣列是否為空
ps->size--;//直接進行洗掉
}
頭刪
根據順序表的定義，我們進行頭刪同樣需要挪動陣列，與頭插相似
將資料往前挪動即可
void SeqListPopFront(SL* ps)
{
assert(ps->size);
int start = 0;
while (start < ps->size - 1)
{
ps->a[start] = ps->a[start + 1];
start++;
}//while里面是挪動資料
ps->size--;
}
任意位置洗掉
聰明的你，應該能舉一反三了吧！
所以這個函式我不畫圖實作，大家可以嘗試自己理解~
void SeqListErase(SL* ps, int pos)
{
assert(ps->size);
if (pos == 1)
{
SeqListPopFront(ps);
}
else if (pos == ps->size)
{
SeqListPopBack(ps);
}
else
{
int cur = pos - 1;
while (cur < ps->size)
{
ps->a[cur] = ps->a[cur + 1];
cur++;
}
ps->size--;
}
}
查找
我們這里直接暴力查找
函式回傳值為某資料在陣列中的位置，如果沒有找到則回傳-1
int SeqListFind(SL* ps, SLDataType x)
{
assert(ps->a);
for (int i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
{
return i + 1;
}
}
return -1;
}
使用方法：
我們可以使用這個函式來找某個資料在順序表中存在的位置
int pos=0;
int x=0;//某個查找的數字
pos=SeqListFind(ps,x);
其它函式
列印函式
void SeqListPrint(SL* ps)
{
if (!ps->size)
{
printf("NULL");
exit(-1);
}
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
順序表銷毀
因為是動態開辟的記憶體，所以我們使用完需要銷毀以防止記憶體泄露
void SeqListDestory(SL* ps)
{
free(ps->a);//釋放記憶體
ps->a = NULL;//指標置空
ps->size = ps->capacity = 0;//容量設定為0
}
完整實作代碼
//SeqLish.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<windows.h>
#include<assert.h>
#include<errno.h>
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a;
int size;
int capacity;
}SL;
void SeqListInit(SL* ps);
void SeqListPrint(SL* ps);
void SeqListDestory(SL* ps);
void SeqListCheckCapacity(SL* ps);
void SeqListPushBack(SL* ps, SLDataType x);
void SeqListPushFront(SL* ps, SLDataType x);
void SeqListPopBack(SL* ps);
void SeqListPopFront(SL* ps);
int SeqListFind(SL* ps, SLDataType x);
void SeqListInsert(SL* ps, int pos, SLDataType x);
void SeqListErase(SL* ps, int pos);
//SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
void SeqListInit(SL* ps)
{
ps->a = NULL;
ps->size = ps->capacity = 0;
}
void SeqListPrint(SL* ps)
{
if (!ps->size)
{
printf("NULL");
exit(-1);
}
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
void SeqListDestory(SL* ps)
{
free(ps->a);
ps->a = NULL;
ps->size = ps->capacity = 0;
}
void SeqListCheckCapacity(SL* ps)
{
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity);
if (!tmp)
{
printf("%s\n", strerror(errno));
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
}
void SeqListPushBack(SL* ps, SLDataType x)
{
SeqListCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
void SeqListPushFront(SL* ps, SLDataType x)
{
SeqListCheckCapacity(ps);
int end = ps->size - 1;
while (end >= 0)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[0] = x;
ps->size++;
}
void SeqListPopBack(SL* ps)
{
assert(ps->size);
ps->size--;
}
void SeqListPopFront(SL* ps)
{
assert(ps->size);
int start = 0;
while (start < ps->size - 1)
{
ps->a[start] = ps->a[start + 1];
start++;
}
ps->size--;
}
int SeqListFind(SL* ps, SLDataType x)
{
assert(ps->a);
for (int i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
{
return i + 1;
}
}
return -1;
}
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
SeqListCheckCapacity(ps);
if (pos <= 1)
{
SeqListPushFront(ps, x);
}
else if (pos >= ps->size)
{
SeqListPushBack(ps, x);
}
else
{
int end = ps->size - 1;
while (end >= pos - 1)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[pos - 1] = x;
ps->size++;
}
}
void SeqListErase(SL* ps, int pos)
{
assert(ps->size);
if (pos == 1)
{
SeqListPopFront(ps);
}
else if (pos == ps->size)
{
SeqListPopBack(ps);
}
else
{
int cur = pos - 1;
while (cur < ps->size)
{
ps->a[cur] = ps->a[cur + 1];
cur++;
}
ps->size--;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/317927.html
標籤：其他