1.順序表概念
順序表是用以一段物理地址連續的存盤單眼依次存盤資料元素的線性結構，一般情況采用陣列存盤，在陣列上完成資料的增刪查改，順序表一般分為靜態順序表和動態順序表，這里主要講如何實作動態順序表，
2.順序表分類
順序表一般可以分為：靜態順序表，動態順序表
2.1靜態順序表
靜態順序表:通過定長的陣列存盤，
優點：實作方便，只需要會用陣列就能夠寫出簡單的靜態順序表，
缺點：不夠靈活，開辟的陣列如果過大榮以浪費大量的空間，而開辟的陣列過小也容易導致資料不夠存放，適用于能預先知道所需空間，而且不用對內容頻繁改動的情況（但實際上從實作角度來看，其實動態通訊錄也沒有麻煩太多，所以一般都是使用動態順序表）
2.2動態順序表
動態順序表：使用動態開辟的陣列存盤
優點：泛用性好，能夠適用于各種不同的環境，并且能根據所需存盤內容多少，動態的分配空間，更加的靈活，且不容易存在空間浪費的情況，一般都是需要多少空間就能那多少空間用，
缺點：相較于順序表更難實作，有一定的使用門檻，
3.順序表實作
3.1順序表結構
3.1.1靜態順序表結構
由于靜態順序表不是本篇文章的主要內容所以只是稍微提及一下結構，
#typedef SLDataType int
#define N 10
typedef struct SeqList
{
SLDataType arr[N];
int size;
}SeqList;SeqList：順序表的英文縮寫，本文提到的所有SeqList均為順序表的意思
SLData Type：順序表中要存放的資料型別，只需要改動typedef int SLDataType后面的內容就能改變所需要存放的資料型別，這里假定我們需要存放的是int型別的資料
N：所開辟陣列大小
arr[N]： 為順序表開辟的陣列空間
size：順序表已經使用的空間長度
3.2動態順序表結構
typedef int SLDataType
typedef struct SeqList
{
SLData Type* a;
int size;
int capacity;
}SeqList;SeqList：順序表的英文縮寫，本文提到的所有SeqList均為順序表的意思
SLData Type：順序表中要存放的資料型別，只需要改動 typedef int SLDataType 后面的內容就能改變所需要存放的資料型別，這里假定我們需要存放的是int型別的資料
size：已用空間的大小
capacity：剩余空間的大小
3.3動態順序表功能實作
檔案："SeqList.c"
3.3.1順序表初始化
void SeqListInit(SeqList* ps) //順序表初始化
{
assert(ps);
ps->a = NULL;
//初始指標指空
ps->size = 0;
//初始已用容量為零
ps->capacity = 0;
//初始可用容量為零
}3.3.2順序表空間檢查
void CheckSeqList(SeqList* ps)
{
assert(ps);
int new_capacity = ps->capacity;
SLDataType* new_a = NULL;
//開辟兩個臨時變數以防止開辟失敗影響原空間內容
if (ps->size == ps->capacity)
//如果已用空間與可用空間相等就開辟空間
{
(new_capacity == 0) ? (new_capacity = 4) : (new_capacity = 2 * new_capacity);
//當首次開辟直接開辟四個空間，否則開辟原空間的兩倍
new_a = (SLDataType*)realloc(ps->a, new_capacity * sizeof(SLDataType));
//開辟原來空間的兩倍
if (new_a == NULL)
{
printf("開辟空間失敗");
exit(-1);
}
//new_a是空指標表示開辟失敗
else
{
ps->capacity = new_capacity;
ps->a = new_a;
}
//開辟成功將空間和空間長度給SeqList
}
}3.3.3順序表銷毀
void SeqListDestory(SeqList* ps) //順序表銷毀
{
assert(ps);
free(ps->a);
//釋放開辟的空間
ps->a = NULL;
//指標指空
ps->size = 0;
//已用空間置零
ps->capacity = 0;
//可用空間置零
}3.3.4列印順序表
void SeqListPrint(SeqList* ps) //順序表列印
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
//將順序表的內容依次列印
}3.3.5順序表頭部插入資料
void SeqListPushFront(SeqList* ps, SLDataType x) //順序表頭插
{
assert(ps);
CheckSeqList(ps);
//檢查順序表是否已滿
for (int i = ps->size -1 ; i >=0 ; i--)
{
ps->a[i+1] = ps->a[i];
}
//從后到前一次往后放一位
ps->a[0] = x;
//第一位為插入內容
ps->size++;
//已用空間+1
}3.3.6順序表尾部插入資料
void SeqListPushBack(SeqList* ps, SLDataType x) //順序表尾插
{
assert(ps);
CheckSeqList(ps);
//檢查順序表是否已滿
ps->a[ps->size] = x;
//在順序表最后放入x
ps->size++;
//順序表已用空間+1
}3.3.7順序表頭部洗掉資料
void SeqListPopFront(SeqList* ps) //順序表頭刪
{
assert(ps);
for (int i = 0; i < ps->size -1; i++)
{
ps->a[i] = ps->a[i + 1];
}
//將順序表依次往前移
ps->size--;
//順序表可用空間-1
}3.3.8順序表尾部洗掉資料
void SeqListPopBack(SeqList* ps) //順序表尾刪
{
assert(ps);
ps->size--;
//順序表可用空間-1
}3.3.9順序表按值查找
int SeqListFind(const SeqList* ps, SLDataType x) //順序表按值查找
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
{
return i;
//依次與x匹配，找到回傳所在位置
}
}
return -1;
//找不到回傳-1
}3.3.10順序表按位插入
void SeqListInsert(SeqList* ps, int pos, SLDataType x) //順序表位插
{
assert(ps);
CheckSeqList(ps);
//檢查順序表是否已滿
if (pos > ps->size)
{
printf("超出可檢測范圍");
exit(-1);
}
//要插入位置是否為合格
for (int i = ps->size - 1; i >= pos - 1; i--)
{
ps->a[i + 1] = ps->a[i];
}
//從后到前依次往后移一位
ps->a[pos - 1] = x;
//第pos-1位為插入內容
ps->size++;
//已用空間+1
}3.3.11順序表按位洗掉
void SeqListErase(SeqList* ps, int pos) //順序表位刪
{
assert(ps);
if (pos > ps->size)
{
printf("超出可檢測范圍");
exit(-1);
}
//要洗掉位置是否為合格為止
for (int i = pos - 1; i < ps->size - 1; i++)
{
ps->a[i] = ps->a[i+1];
}
//從前向后依次往前移一位
ps->size--;
//已用空間-1
}3.4順序表頭檔案
檔案："SeqList.h"
#pragma once //防止重復定義
typedef int SLDataType;
#include<stdio.h>
#include<stdlib.h>
#include<assert.h> //頭檔案，其他檔案只用包含該檔案
typedef struct SeqList //順序表結構
{
SLDataType *a;
int size;
int capacity;
}SeqList;
void SeqListInit(SeqList* ps); //順序表初始
void SeqListDestory(SeqList* ps); //順序表銷毀
void SeqListPrint(SeqList* ps); //順序表列印
void SeqListPushFront(SeqList* ps, SLDataType x); //順序表頭插
void SeqListPushBack(SeqList* ps, SLDataType x); //順序表尾插
void SeqListPopFront(SeqList* ps); //順序表頭刪
void SeqListPopBack(SeqList* ps); //順序表頭刪
void SeqListInsert(SeqList* ps, int pos, SLDataType x); //順序表位插
void SeqListErase(SeqList* ps, int pos); //順序表位刪
void CheckSeqList(SeqList* ps); //檢查表容量
int SeqListFind(const SeqList* ps, SLDataType x); //順序表查找 3.5順序表功能測驗
檔案："test.c"
#include"SeqList.h"
int main()
{
SeqList seqlist;
SeqListInit(&seqlist); //初始化順序表--通過
SeqListPushFront(&seqlist, 3);
SeqListPushFront(&seqlist, 2);
SeqListPushFront(&seqlist, 1);
SeqListPushFront(&seqlist, 0);
SeqListPrint(&seqlist); //頭插測驗--通過
SeqListPushBack(&seqlist, 4);
SeqListPushBack(&seqlist, 5);
SeqListPushBack(&seqlist, 6);
SeqListPushBack(&seqlist, 7);
SeqListPrint(&seqlist); //尾插測驗--通過
SeqListPopFront(&seqlist);
SeqListPopFront(&seqlist);
SeqListPrint(&seqlist); //頭刪測驗--通過
SeqListPopBack(&seqlist);
SeqListPopBack(&seqlist);
SeqListPrint(&seqlist); //尾插測驗--通過
printf("%d ", SeqListFind(&seqlist, 1));
printf("%d \n", SeqListFind(&seqlist, 4));
SeqListPrint(&seqlist); //查找測驗--通過
SeqListInsert(&seqlist, 3, 0);
SeqListInsert(&seqlist, 5, 0);
SeqListPrint(&seqlist); //位插測驗--通過
SeqListErase(&seqlist, 3);
SeqListErase(&seqlist, 4);
SeqListPrint(&seqlist); //位刪測驗--通過
SeqListDestory(&seqlist); //銷毀順序表--通過
return 0;
}
?寫在最后
?筆記時間：2021_09_25
🌐代碼：Gitee:朱雯睿 (zhu-wenrui) - Gitee.com
Github:https://github.com/Zero0Tw0
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/303047.html
標籤：其他