目錄

線性表

順序表

概念與結構

動態順序表的實現

頭文件的創建

順序表初始化

順序表的擴容

尾插功能

頭插功能

尾刪功能

頭刪功能

查找功能

任意位置前插入

任意位置前刪除

銷毀

動態順序表整體呈現

SeqList.h

SeqList.c

---

線性表

線性表是n個具有相同特性的數據元素的有限序列。線性表是一種在實際中廣泛使用的數據結構，常見的線性表：順序表、鏈表、棧、隊列、字符串...

線性表的邏輯結構一定是線性的，但物理結構不一定是線性的。

順序表

概念與結構

概念：順序表是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構，一般情況下采用數組存儲。

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

分類：分為靜態順序表和動態順序表（常用）。

動態順序表的實現

頭文件的創建

我們要在頭文件中完成順序表的創建和頭文件與函數的聲明。

typedef int SLDataType;
typedef struct SeqList
{SLDataType* arr;int size;int capacity;
}SL;

這是頭文件的包含和順序表的創建。

這是對函數的聲明，以上函數我們都會講到。

順序表初始化

首先我們要在源文件中包含剛剛我們創建的頭文件。

然后對順序表進行初始化。

void SLInit(SL* ps)//初始化
{ps->arr = NULL;ps->size = ps->capacity = 0;
}

順序表的擴容

現在我們的順序表里面什么都沒有，我們要擴大我們的空間。或者當我們的順序表空間滿了的時候，我們也要擴大我們的空間。

所以我們要先寫好函數對順序表進行擴容。

擴容函數中我們需要使用realloc函數額外申請空間。

注意：進行擴容操作時請用臨時變量，防止發生問題造成不可逆的傷害。

void SLCheckCapacity(SL* ps)//擴容
{if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}
}

尾插功能

實現尾插功能很簡單，size剛好是數組最后一個元素的后一個下標，確定指針的安全后直接令arr[size]等于x就完成了。

void SLPushBack(SL* ps,SLDataType x)//尾插
{assert(ps);SLCheckCapacity(ps);ps->arr[ps->size++] = x;
}

頭插功能

頭插功能比尾插復雜一點點，需要讓數組中的元素整體后移一個位置，讓arr[0]空缺起來實現x的插入。

void SLPushFront(SL* ps, SLDataType x)//頭插
{assert(ps);SLCheckCapacity(ps);for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;++ps->size;
}

尾刪功能

尾刪很簡單，直接讓size減一就好了。

void SLPopBack(SL* ps)//尾刪
{assert(ps && ps->size);--ps->size;
}

頭刪功能

頭刪也很簡單，就讓后面的元素把前面的元素一一覆蓋就好了。

void SLPopFront(SL* ps)//頭刪
{assert(ps && ps->size);for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}--ps->size;
}

查找功能

遍歷數組查找元素，找到返回下標，沒找到返回-1。

int SLFind(SL* ps, SLDataType x)//查找
{for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x)return i;}return -1;
}

任意位置前插入

這是建立在頭插的基礎上的，讓pos后的元素一一往后移一個位置把pos空出來實現插入。

void SLInsert(SL* ps, int pos, SLDataType x)//任意位置前插入
{assert(ps);assert(pos >= 0 && pos <= ps->size);for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;++ps->size;
}

任意位置前刪除

和頭刪很相似，讓pos后的元素一一往前移一個位置覆蓋pos。

void SLErase(SL* ps, int pos)//任意位置前刪除
{assert(ps && ps->size);assert(pos >= 0 && pos < ps->size);for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}--ps->size;
}

銷毀

結束后一定要進行函數的銷毀操作。

void SLDesTroy(SL* ps)//銷毀
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;
}

動態順序表整體呈現

SeqList.h

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLDataType;
typedef struct SeqList
{SLDataType* arr;int size;int capacity;
}SL;void SLInit(SL* ps);
void SLDesTroy(SL* ps);
void SListPrint(SL s);
void SLCheckCapacity(SL* ps);
void SLPushBack(SL* ps,SLDataType x);
void SLPushFront(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, SLDataType);

SeqList.c

#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"void SLInit(SL* ps)//初始化
{ps->arr = NULL;ps->size = ps->capacity = 0;
}void SListPrint(SL s)//打印
{for (int i = 0; i < s.size; i++){printf("%d ", s.arr[i]);}printf("\n");
}void SLCheckCapacity(SL* ps)//擴容
{if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}
}void SLPushBack(SL* ps,SLDataType x)//尾插
{assert(ps);SLCheckCapacity(ps);ps->arr[ps->size++] = x;
}void SLPushFront(SL* ps, SLDataType x)//頭插
{assert(ps);SLCheckCapacity(ps);for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;++ps->size;
}void SLPopBack(SL* ps)//尾刪
{assert(ps && ps->size);--ps->size;
}void SLPopFront(SL* ps)//頭刪
{assert(ps && ps->size);for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}--ps->size;
}int SLFind(SL* ps, SLDataType x)//查找
{for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x)return i;}return -1;
}void SLInsert(SL* ps, int pos, SLDataType x)//任意位置前插入
{assert(ps);assert(pos >= 0 && pos <= ps->size);for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;++ps->size;
}void SLErase(SL* ps, int pos)//任意位置前刪除
{assert(ps && ps->size);assert(pos >= 0 && pos < ps->size);for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}--ps->size;
}void SLDesTroy(SL* ps)//銷毀
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;
}