一、順序表的概念與結構

1.1線性表

線性表（linear list）是n個具有相同特性的數據元素的有限序列。線性表是?種在實際中廣泛使用的數據結構，常見的線性表：順序表、鏈表、棧、隊列、字符串…
線性表在邏輯上是線性結構，也就說是連續的?條直線。但是在物理結構上并不?定是連續的，線性表在物理上存儲時，通常以數組和鏈式結構的形式存儲。

1.2順序表分類

1.2.1 順序表和數組的區別

順序表的底層結構是數組，對數組的封裝，實現了常用的增刪改查等接口

1.2.2順序表分類

• 靜態順序表

概念：使用定長數組存儲元素

靜態順序表缺陷：空間給少了不夠用，給多了造成空間浪費

• 動態順序表

二、動態順序表的實現

2.1結構體表示順序表

首先需要一個結構體來表示順序表：

typedef int SLDataType;//筆者在此直接使用了接下來要實現的順序表的數據類型
//順序表結構體
typedef struct SL
{SLDataType* a;int size;int capacity;
}SL;

2.2順序表的初始化和銷毀

//初始化順序表
void init(SL* s)
{s->a = NULL;s->size = s->capacity = 0;
}

//順序表銷毀
void SLDestory(SL* s)
{assert(s);if(s->a){free(s->a);}s->a = NULL;s->size = s->capacity = 0;
}

2.3順序表的增刪查改

在每次插入時都會面對著是否擴容的問題，因此我們抽離出檢查擴容的函數。

//檢查是否滿了
void check(SL* s)
{if (s->size == s->capacity){int new_capacity = (s->capacity == 0) ? 4 : s->capacity * 2;SLDataType* temp = (SLDataType*)realloc(s->a, sizeof(SLDataType) * new_capacity);if (temp == NULL){perror("realloc is fail!");//如果realloc失敗會報錯exit (EXIT_FAILURE);}s->a = temp;s->capacity =new_capacity;}
}

//頭插
void PushFront(SL* s, SLDataType x)
{assert(s);check(s);for (int i =s->size;i>0;i--){s->a[i] =s->a[i-1];}s->a[0] = x;s->size++;
}//尾插
void PushBack(SL* s, SLDataType x)
{assert(s);check(s);s->a[s->size] = x;s->size++;
}//頭刪
void PopFront(SL* s)
{assert(s && s->size);for (int i =0;i<s->size-1;i++){s->a[i] = s->a[i+1];}s->size--;
}//尾刪
void PopBack(SL* s)
{assert(s);assert(s->size);s->size--;
}//任意位置的插入
void Insert(SL* s, int pos, SLDataType x)
{assert(pos >= 0 && pos <= s->size);check(s);for (int i = s->size; i > pos; i--){s->a[i] = s->a[i - 1];}s->a[pos] = x;s->size++;
}//任意位置的刪除，pos是下標
void Erase(SL* s, int pos)
{assert(s);assert(pos >= 0 && pos < s->size);for (int i = pos; i < s->size; i++){s->a[i] = s->a[i + 1];}s->size--;
}//查找元素是否存在，存在返回下標，否則返回-1
int Find(SL* s, SLDataType x)
{assert(s);for (int i = 0; i < s->size; i++){if (x == s->a[i])return i;}return -1;
}

2.4順序表的打印

//打印
void print(SL* s)
{for (int i = 0; i < s->size; i++){printf("%d ", s->a[i]);}printf("\n");
}

三、順序表的源代碼

//order_table.h#pragma once#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>typedef int SLDataType;
//順序表結構體
typedef struct SL
{SLDataType* a;int size;int capacity;
}SL;//初始化順序表
void init(SL *s);
//打印
void print(SL* s);//增刪查改
void PushFront(SL* s,SLDataType x);//頭插void PushBack(SL* s, SLDataType x);//尾插void PopFront(SL* s);//頭刪void PopBack(SL* s);//尾刪void Insert(SL* s, int pos, SLDataType x);//任意位置的插入，pos意為下標void Erase(SL* s, int pos);//任意位置的刪除,pos意為下標int Find(SL* s, SLDataType x);//查找元素是否存在，存在返回下標，否則返回-1void SLDestory(SL* s);

//order_table.c
#include"order_table.h"//順序表結構體
void init(SL* s)
{s->a = NULL;s->size = 0;s->capacity = 0;
}//打印
void print(SL* s)
{for (int i = 0; i < s->size; i++){printf("%d ", s->a[i]);}printf("\n");
}//檢查是否滿了
void check(SL* s)
{if (s->size == s->capacity){int new_capacity = (s->capacity == 0) ? 4 : s->capacity * 2;SLDataType* temp = (SLDataType*)realloc(s->a, sizeof(SLDataType) * new_capacity);if (temp == NULL){perror("realloc is fail!");exit (EXIT_FAILURE);}s->a = temp;s->capacity =new_capacity;}
}
//頭插
void PushFront(SL* s, SLDataType x)
{check(s);for (int i =s->size;i>0;i-- ){s->a[i] =s->a[i-1];}s->a[0] = x;s->size++;
}void PushBack(SL* s, SLDataType x)//尾插
{check(s);s->a[s->size] = x;s->size++;
}void PopFront(SL* s)//頭刪
{assert(s && s->size);for (int i =0;i<s->size-1;i++){s->a[i] = s->a[i+1];}s->size--;
}void PopBack(SL* s)//尾刪
{assert(s);assert(s->size);s->size--;
}void Insert(SL* s, int pos, SLDataType x)//任意位置的插入
{assert(pos >= 0 && pos <= s->size);check(s);for (int i = s->size; i > pos; i--){s->a[i] = s->a[i - 1];}s->a[pos] = x;s->size++;
}void Erase(SL* s, int pos)//任意位置的刪除
{assert(s);assert(pos >= 0 && pos < s->size);for (int i = pos; i < s->size; i++){s->a[i] = s->a[i + 1];}s->size--;
}int Find(SL* s, SLDataType x)//查找元素是否存在，存在返回下標，否則返回-1
{assert(s);for (int i = 0; i < s->size; i++){if (x == s->a[i])return i;}return -1;
}void SLDestory(SL* s)
{assert(s);if(s->a){free(s->a);}s->a = NULL;s->size = s->capacity = 0;
}