?

🔥個人主頁：@草莓熊Lotso

🎬作者簡介：C++研發方向學習者

📖個人專欄：?《C語言》?《數據結構與算法》《C語言刷題集》《Leetcode刷題指南》

??人生格言：生活是默默的堅持，毅力是永久的享受。??

?前言：各位朋友們，從今天開始博主將恢復數據結構與算法專欄的更新，為大家分享數據結構初階相關知識，用C語言與大家一起實現一些數據結構，那么我們這篇文章將會接著上次順序表的初始化繼續往后詳細實現順序表的頭插，尾插，頭刪，尾刪等功能。那么這里特別聲明一下，博主會將這些功能分開實現，最后再單獨為大家呈現本節所有內容的完整代碼。

---

目錄

一.順序表的尾插

二.順序表的頭插

三.順序表的尾刪?

四.順序表的頭刪

五.代碼展現以及時間復雜度對比

SeqList.h：

SeqList.c：?

test.c：?

尾插，頭插，尾刪，頭刪時間復雜度對比：

---

一.順序表的尾插

--這里分布實現的時候主要展示SeqList.c文件和test.c文件，頭文件這里就不展示了。

SeqList.c：

//尾插
void SLPushBack(SL* ps, SLTDataType x)
{//空間不夠if (ps->size == ps->capacity){//增容int newCapacity = ps->capacity ==0 ? 4 : 2 * ps->capacity;SLTDataType* tmp = (SLTDataType*)realloc(ps->arr, newCapacity*sizeof(SLTDataType));if (tmp = NULL){perror("realloc");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空間足夠ps->arr[ps->size++] = x;//插入完后，size往后走
}

?重點提示：?

增容：我們一般成倍數增加，最好是兩倍。這樣可以有效降低增容的次數，就算可能會存在空間的浪費，但是不會太多。

我們再來看看在此過程中要注意的一些問題：

為了方便觀察，我們再來實現一個打印順序表的函數，很簡單，這里就不解釋了?

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

test.c：?

#include"SeqList.h"void test1()
{SL s;SLInit(&s);SLPushBack(&s, 1);//1SLPushBack(&s, 2);//12SLPushBack(&s, 3);//123SLPushBack(&s, 4);//1234SLPrint(&s);//1 2 3 4}int main()
{test1();
}

--測試結果如下，成功打印出了經過4次尾插之后的順序表

---

二.順序表的頭插

--頭插和尾插都離不開空間的檢查增容，所以我們在實現尾插之前可以直接用一個函數實現空間的檢查，后續需要時直接復用就可以了。

//檢查空間
void SLCheckCapacity(SL*ps)
{//擴容int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLdatatype* tmp = (SLdatatype*)realloc(ps->arr, newcapacity * sizeof(SLdatatype));if (tmp == NULL){perror("realloc");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;
}

?SeqList.c：

//頭插
void SLPushFront(SL* ps, SLdatatype x)
{assert(ps);//ps！=NULL//檢查空間是否足夠SLCheckCapacity(ps);//空間足夠for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;ps->size++;
}

?重點提示：

這里其實沒啥坑了，該說的我們都在前面說過了，值得注意的就是頭插，順序表中的其它元素一定是從后往前的順序向后移動一位，如圖所示。再就是利用assert斷言判斷ps不為空了，用if也可以這里就不演示了。

test.c：?

#include"SeqList.h"void test1()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPrint(&s);//1 2 3 4SLPushFront(&s, 5);SLPrint(&s);// 5 1 2 3 4
}int main()
{test1();
}

--測試出來也沒啥問題，在前面頭插了一個5。?

---

三.順序表的尾刪?

--順序表的尾刪其實就很簡單了，大家可以想想我們是使用free釋放掉還是令ps->arr[ps->size-1]=0，然后ps->size--呢？其實兩者都不需要，直接ps->size--就結束了，不需要其它的過程。

?SeqList.c：

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

重點提示：?

尾刪這里直接就是ps->size--就可以了，不用其它的操作了。這里斷言的時候注意ps->size也不能為0就行，不然刪除不了。

test.c：?

#include"SeqList.h"void test1()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPrint(&s);//1 2 3 4SLPushFront(&s, 5);SLPrint(&s);// 5 1 2 3 4SLPopBack(&s);SLPopBack(&s);SLPrint(&s);// 5 1 2
}int main()
{test1();
}

--測試之后沒問題，尾刪掉了兩個數據，打印出來結果為5 1 2

---

四.順序表的頭刪

SeqList.c：

//頭刪
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--;
}

重點提示：?

頭刪的斷言和尾刪一樣，值得注意的是我們需要將數據按從前往后的順序依次向前移動一位，注意最后循環的終止條件是i=ps->size-1，所以循環進行的條件就是i<ps->size-1。如圖所示，1覆蓋掉了原來的5。實現了頭刪，刪除完后ps->size--就可以了。

test.c：?

#include"SeqList.h"void test1()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPrint(&s);//1 2 3 4SLPushFront(&s, 5);SLPrint(&s);// 5 1 2 3 4SLPopBack(&s);SLPopBack(&s);SLPrint(&s);// 5 1 2SLPopFront(&s);SLPrint(&s);//1 2
}int main()
{test1();
}

--測試沒有問題，頭刪掉一個5，最終結果打印出來是正確的

---

五.代碼展現以及時間復雜度對比

SeqList.h：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLdatatype;
typedef struct SeqList
{SLdatatype* arr;int size;int capacity;
}SL;//順序表初始化
void SLInit(SL* ps);//打印順序表
void SLPrint(SL* ps);//尾插
void SLPushBack(SL* ps, SLdatatype x);
//頭插
void SLPushFront(SL* ps, SLdatatype x);
//尾刪
void SLPopBack(SL* ps);
//頭刪
void SLPopFront(SL* ps);

SeqList.c：?

#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"//初始化
void SLInit(SL* ps)
{ps->arr = NULL;ps->size = 0;ps->capacity = 0;
}//打印
void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}
//檢查空間
void SLCheckCapacity(SL*ps)
{//擴容int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLdatatype* tmp = (SLdatatype*)realloc(ps->arr, newcapacity * sizeof(SLdatatype));if (tmp == NULL){perror("realloc");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;
}//尾插
void SLPushBack(SL* ps, SLdatatype x)
{//檢查空間是否足夠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--;
}

test.c：?

#include"SeqList.h"void test1()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPrint(&s);//1 2 3 4SLPushFront(&s, 5);SLPrint(&s);// 5 1 2 3 4SLPopBack(&s);SLPopBack(&s);SLPrint(&s);// 5 1 2SLPopFront(&s);SLPrint(&s);//1 2
}int main()
{test1();
}

尾插，頭插，尾刪，頭刪時間復雜度對比：

結論：我們通過對比可以看出順序表的尾插，尾刪的時間復雜度比頭插，頭刪要好很多，所有我們可以看出如果操作尾部數據比較多的話，順序表這個數據結構是比較優秀的。?

---

往期回顧：

【數據結構初階】--算法復雜度的深度解析

【數據結構初階】--順序表(一)

結語：繼上篇博客中我們實現的動態順序表的初始化后，在本篇中我們完成了順序表的尾插，頭插，尾刪，頭刪這四個接口的實現，那么順序表的實現我們其實還沒完全完成，博主將會在后續的博客中繼續和大家一起實現順序表中指定位置的插入和刪除以及查找和修改這四個接口，如果文章對你有幫助的話，歡迎評論，點贊，收藏加關注，感謝大家的支持