概念
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组 上完成数据的增删查改。
顺序表一般可以分为： 静态顺序表：使用定长数组存储。动态顺序表：使用动态开辟的数组存储。
头文件声明
SeqList.h
#pragma once#include<stdbool.h>typedef int SDataType;/*//静态顺序表typedef struct SeqList{SDataType array[100]; //能存100个数的静态顺序表int size;//表是当前顺序表中有多少个数，顺便也表示了即将插入的下标} SeqList;*///动态顺序表typedef struct SeqList{SDataType *array;//指上堆上的空间int size;//表是当前顺序表中有多少个数，顺便也表示了即将插入的下标int capacity;//容量} SeqList;//初始化/销毁//seqlist 是一个变量的地址//capacity 表示顺序表的容量void SeqListInit(SeqList * seqlist,int capacity);void SeqListDestroy(SeqList * seqlist);//增删改查//插入 (前，中，后)//尾插void SeqListPushBack(SeqList *seqlist, SDataType value);//头插void SeqListPushFront(SeqList * seqlist, SDataType value);//中间插入void SeqListInsert(SeqList *seqlsit, int pos, SDataType value);//删除//尾删void SeqListPopBack(SeqList *seqlist);//头删void SeqListPopFront(SeqList *seqlist);//删除pos所在的下标的数据void SeqListErase(SeqList *seqlist, int pos);//打印void SeqListPrint(const SeqList *seqlist);//修改pos所在下标的数据为valuevoid SeqListModify(SeqList *seqlist, int pos, SDataType value);//查找int SeqListFind(const SeqList *seqlist, SDataType value);//找到并删除遇到的第一个valuevoid SeqListRemove(SeqList *seqlist, SDataType value);//判断顺序表是否为空bool SeqListEmpty(const SeqList *seqlist);//返回数据个数int SeqListSize(const SeqList *seqlist);//冒泡排序void SeqListBubbleSort(SeqList *seqlist);//二分查找int SeqListSort(const SeqList *seqlist, SDataType value);//删除遇到的所有valuevoid SeqListRemoveAll(SeqList *seqlist, SDataType value);
顺序表主要功能实现
SeqList.c
#include"SeqList.h"#include<assert.h>#include<malloc.h>#include<stdio.h>#include<stdlib.h>//检查是否需要扩容，如果需要扩容就进行扩容//保证函数结束后，容量一定够用static void CheckCapacity(SeqList *seqlist){assert(seqlist != NULL);assert(seqlist->array != NULL);assert(seqlist->size <= seqlist->capacity);if (seqlist->size < seqlist->capacity){return;}//空间扩大两倍int capacity = 2 * seqlist->capacity;//申请新空间SDataType *array = (SDataType *)malloc(sizeof(SDataType)*capacity);assert(array);//搬移for (int i = 0; i < seqlist->size; i++){array[i] = seqlist->array[i];}//释放原空间free(seqlist->array);seqlist->array = array;}void SeqListInit(SeqList * seqlist, int capacity){assert(seqlist != NULL);seqlist->array = (SDataType*)malloc(sizeof(SDataType)* capacity);assert(seqlist->array);seqlist->size = 0;seqlist->capacity = capacity;}void SeqListDestroy(SeqList * seqlist){assert(seqlist != NULL);assert(seqlist->array != NULL);free(seqlist->array);seqlist->array = NULL;seqlist->size = 0;seqlist->capacity = 0;}//尾插void SeqListPushBack(SeqList *seqlist, SDataType value){assert(seqlist != NULL);assert(seqlist->array !=NULL);CheckCapacity(seqlist);seqlist->array[seqlist->size] = value;seqlist->size++;}//尾删void SeqListPopBack(SeqList *seqlist){assert(seqlist != NULL);assert(seqlist->array != NULL);assert(seqlist->size > 0); //数据元素个数大于0seqlist->size--;}//头插/*1. 从后往前搬，避免覆盖2. 写循环先确定循环的边界i 空间下表 [size,0)i 数据下标 [size -1,0]3. 搬移空间下标：array[i] = array[i-1];数据下标：array[i+1] = array[i];*/void SeqListPushFront(SeqList * seqlist, SDataType value){assert(seqlist != NULL);assert(seqlist->array != NULL);CheckCapacity(seqlist);//做数据的搬移，i代表空间下标for (int i = seqlist->size; i > 0; i--){seqlist->array[i] = seqlist->array[i - 1];}seqlist->array[0] = value;seqlist->size++;}//前删void SeqListPopFront(SeqList *seqlist){assert(seqlist != NULL);assert(seqlist->array != NULL);assert(seqlist->size > 0);#if 0for (int i = 0; i < seqlist->size; i++){seqlist->array[i] = seqlist->array[i + 1];}#endiffor (int i = 1; i < seqlist->size; i++){seqlist->array[i - 1] = seqlist->array[i];}seqlist->size--;}//中间插void SeqListInsert(SeqList *seqlist, int pos, SDataType value){assert(seqlist != NULL);assert(seqlist->array != NULL);assert(pos >= 0 && pos <= seqlist->size);CheckCapacity(seqlist);for (int i = seqlist->size - 1; i >= pos; i--){seqlist->array[i + 1] = seqlist->array[i];}seqlist->array[pos] = value;}//中间删void SeqListErase(SeqList *seqlist, int pos){assert(seqlist!= NULL);assert(seqlist->array != NULL);assert(seqlist->size > 0);assert(pos >= 0 && pos < seqlist->size);#if 0//i代表数据for (int i = pos; i < seqlist->size - 1; i++){seqlist->array[i] = seqlist->array[i + 1];}#endif//i代表数据for (int i = pos + 1; i < seqlist->size ; i++){seqlist->array[i - 1] = seqlist->array[i];}seqlist->size--;}//打印void SeqListPrint(const SeqList *seqlist){for (int i = 0; i < seqlist->size; i++)printf("%d", seqlist->array[i]);printf("\n");}//修改pos所在下标的数据为valuevoid SeqListModify(SeqList *seqlist, int pos, SDataType value){assert(pos >= 0 && pos < seqlist->size);seqlist->array[pos] = value;}//查找//找到返回下标//没找到返回-1int SeqListFind(const SeqList *seqlist, SDataType value){for (int i = 0; i < seqlist->size; i++){if (seqlist->array[i] == value){return i;}}return -1;}//找到并删除遇到的第一个valuevoid SeqListRemove(SeqList *seqlist, SDataType value){int pos = SeqListFind(seqlist, value);if (pos != -1){SeqListErase(seqlist, pos);}}//判断顺序表是否为空bool SeqListEmpty(const SeqList *seqlist){return seqlist->size == 0;}//返回数据个数int SeqListSize(const SeqList *seqlist){return seqlist->size;}void Swap(int *a, int *b){int t = *a;*a = *b;*b = t;}//冒泡排序void BubbleSort(int array[], int size){int isSorted; //如果数组本身有序，就可以优化for (int i = 0; i < size - 1; i++){isSorted = 1; //1代表有序//一次冒泡过程//一次冒泡过程中，如果没有交换就说明本身有序for (int j = 0; j < size - 1 - i; j++){if (array[j]>array[j + 1]){Swap(array + j, array + j + 1);//Swap(&array[i])isSorted = 0;}}//一次冒泡结束if (isSorted == 1){break;}}}//冒泡排序void SeqListBubbleSort(SeqList *seqlist){BubbleSort(seqlist->array, seqlist->size);}//二分查找int SeqListSort(const SeqList *seqlist, SDataType value){int left = 0;int right = seqlist->size;while (left < right){int mid = (right - left) / 2 + left;if (value == seqlist->array[mid]){return mid;}else if (value < seqlist->array[mid]){right = mid;}else{left = mid + 1;}}return -1;}void SeqListRemoveAll(SeqList *seqlist, SDataType value){#if 0 //O(N*2) O(1)int pos;while ((pos = SeqListFind(seqlist, value)) != -1){SeqListErase(seqlist, pos);}#endif#if 0 //O(N) O(N)//开辟新数组SDataType *array = (SDataType *)malloc(sizeof(SDataType)* seqlist->size);assert(array);//搬出去int index = 0;for (int i = 0; i < seqlist->size; i++){if (seqlist->array[i] != value){array[index] = seqlist->array[i];index++;}}//搬回去for (int j = 0; j < index; j++){seqlist->array[j] = array[j];}seqlist->size = index;#endifint index = 0;for (int i = 0; i < seqlist->size; i++){if (seqlist->array[i] != value){seqlist->array[index] = seqlist->array[i];index++;}}seqlist->size = index;}
测试用例
Main.c
#include"SeqList.h"void TestSeqList1(){SeqList seqlist;SeqListInit(&seqlist, 100);SeqListPushBack(&seqlist, 1);SeqListPushBack(&seqlist, 2);SeqListPushBack(&seqlist, 3);//1,2,3SeqListPushFront(&seqlist, 11);SeqListPushFront(&seqlist, 12);SeqListPushFront(&seqlist, 13);//13,12,11,1,100,2,3SeqListInsert(&seqlist, 4, 100);//13,12,11,1,100,2,3SeqListPopBack(&seqlist);//13,12,11,1,100,2SeqListPopFront(&seqlist);//12,11,1,100,2SeqListErase(&seqlist, 3);//12,11,100,2SeqListDestroy(&seqlist);}void TestSeqList2(){SeqList seqlist;SeqListInit(&seqlist, 10);SeqListPushBack(&seqlist, 3);SeqListPushBack(&seqlist, 5);SeqListPushBack(&seqlist, 2);SeqListPushBack(&seqlist, 7);SeqListPushBack(&seqlist, 9);SeqListPushBack(&seqlist, 4);SeqListPushBack(&seqlist, 8);SeqListPushBack(&seqlist, 6);SeqListPushBack(&seqlist, 1);SeqListPushBack(&seqlist, 0);SeqListBubbleSort(&seqlist);int r = SeqListSort(&seqlist, 3);printf("%d\n", r);SeqListPrint(&seqlist);}int main(){TestSeqList2();system("pause");return 0;}
