准备工作
我们还是分一个头文件和两个源文件
sequence.h
sequence.c
test.c
sequence.h
#include <stdio.h> typedef struct Sequence_List { int* p;//顺序表的初始地址 int count;//元素数量 int capacity;//容量 }SL;//顺序表的动态储存
sequence.c
void Initialize(SL* s)//初始化顺序表 { assert(s);//判断s是否为空指针 s->p = NULL; s->count = 0; s->capacity = 0; }
void Destroy(SL* s)//释放顺序表内存 { assert(s); free(s->p); s->p = NULL; s->count = 0; s->capacity = 0; }
检查，扩容
sequence.c
void SeqListInit(SL* s)//检查，扩容 { assert(s); if (s->capacity == s->count)//判断是否满足扩容条件 { int i = (s->capacity == 0 ? 4 : s->capacity*2);//第一次扩容4，后续的扩容都是之前的两倍 SLData* p1 = (SLData*)realloc(s->p, sizeof(SLData) * i); if (p1 == NULL)//判断，防止空指针让原本的位置丢失 { perror("realloc fail");//开辟失败报错 return; } s->p = p1; s->capacity = i;//容量增加 } }
头插头删，尾插尾删
sequence.c
尾插：
void SeqListPushBack(SL* s, SLData x)//尾插，x是你要插入的元素 { assert(s); SeqListInit(s);//检查空间是否需要扩容 s->p[s->count] = x;//插入 s->count++;//元素数量增加 }
头插：
void SeqListPopBack(SL* s, SLData x)//头插 { assert(s); SeqListInit(s); int i = 0; int j = s->count; for (i = j; i > 0; i--) { s->p[j] = s->p[j - 1];//移动已有元素 } s->p[0] = x;//在第一个元素的位置插入你想要的数值 s->count++; }
尾删：
void SeqListPopBack(SL* s)//尾删 { assert(s); assert(s->count > 0);//判断数量，少于0就不能删除了 s->count--; }
头删：
void SeqListPopFront(SL* s)//头删 { assert(s); assert(s->count > 0); int j = 0; while (j < s->count) { s->p[j] = s->p[j + 1];//原理是覆盖 j++; } s->count--; }
顺序表查找
sequence.c
int SeqListFind(SL* s, int x)//搜索，x是你要搜索的数值 { assert(s); int i = 0; for (i = 0; i < s->count; i++) { if (s->p[i] == x) { return i;//找到返回下标 } } return -1;//找不到返回-1，下标不可能是-1，如果返回-1就说明没找到 }
顺序表打印
sequence.c
void SeqListPrint(SL* s)//打印 { assert(s); int i = 0; for (i = 0; i < s->count; i++) { printf("%d ", s->p[i]); } printf("\n"); }
在指定位置插入和删除x
sequence.c
pos是指下标。
插入：
void SeqListInsert(SL* s, size_t pos, int x)//在pos的位置放入元素x { assert(s); assert(pos <= s->count);//判断插入位置是否合法，这里相等也就等于尾插 SeqListInit(s); size_t i = s->count; for (i = s->count; i > pos; i--) { s->p[i] = s->p[i - 1];//往后挪动下标为pos元素后面所有元素的位置 } s->p[pos] = x;//在下标为pos的位置放入x s->count++; }
删除：
void SeqListErase(SL* s, size_t pos)//删除pos位置的元素 { assert(s); assert(pos < s->count); size_t j = pos; for (; j < s->count; j++) { s->p[j] = s->p[j + 1]; } s->count--; }
完整版顺序表
sequence.h
#include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int SLData; typedef struct Sequence_List { SLData* p;//顺序表的初始地址 int count;//元素数量 int capacity;//容量 }SL; //函数声明区 void Initialize(SL* s);//初始化 void Destroy(SL* s);//释放内存 void SeqListInit(SL* s);//检查，扩容 void SeqListPushBack(SL* s, SLData x);//尾插 void SeqListPushFront(SL* s, SLData x);//头插 void SeqListPopBack(SL* s);//尾删 void SeqListPopFront(SL* s);//头删 int SeqListFind(SL* s, int x);//搜索 void SeqListPrint(SL* s);//打印顺序表 void SeqListInsert(SL* s, size_t pos, int x);//在pos的位置放入元素x void SeqListErase(SL* s, size_t pos);//删除pos位置的元素
sequence.c
#include "sequence.h"; void Initialize(SL* s)//初始化顺序表 { assert(s); s->p = NULL; s->count = 0; s->capacity = 0; } void Destroy(SL* s)//释放顺序表的动态内存 { assert(s); free(s->p); s->p = NULL; s->count = 0; s->capacity = 0; } void SeqListInit(SL* s)//检查，扩容 { assert(s); if (s->capacity == s->count) { int i = (s->capacity == 0 ? 4 : s->capacity*2); SLData* p1 = (SLData*)realloc(s->p, sizeof(SLData) * i); if (p1 == NULL) { perror("realloc fail"); return; } s->p = p1; s->capacity = i; } } void SeqListPushBack(SL* s, SLData x)//尾插 { assert(s); SeqListInit(s); s->p[s->count] = x; s->count++; } void SeqListPushFront(SL* s, SLData x)//头插 { assert(s); SeqListInit(s); int i = s->count; while (i > 0) { s->p[i] = s->p[i - 1]; i--; } s->p[0] = x; s->count++; } void SeqListPopBack(SL* s)//尾删 { assert(s); assert(s->count > 0); s->count--; } void SeqListPopFront(SL* s)//头删 { assert(s); assert(s->count > 0); int j = 0; while (j < s->count) { s->p[j] = s->p[j + 1]; j++; } s->count--; } int SeqListFind(SL* s, int x)//搜索 { assert(s); int i = 0; for (i = 0; i < s->count; i++) { if (s->p[i] == x) { return i; } } return -1; } void SeqListPrint(SL* s)//打印 { assert(s); int i = 0; for (i = 0; i < s->count; i++) { printf("%d ", s->p[i]); } printf("\n"); } void SeqListInsert(SL* s, size_t pos, int x)//在pos的位置放入元素x { assert(s); assert(pos <= s->count); SeqListInit(s); size_t i = s->count; for (i = s->count; i > pos; i--) { s->p[i] = s->p[i - 1]; } s->p[pos] = x; s->count++; } void SeqListErase(SL* s, size_t pos)//删除pos位置的元素 { assert(s); assert(pos < s->count); size_t j = pos; for (; j < s->count; j++) { s->p[j] = s->p[j + 1]; } s->count--; }
test.c
#include "sequence.h"; void test1()//实验程序的总接口 { SL s1; Initialize(&s1); SeqListPushBack(&s1, 1);//尾插 SeqListPushBack(&s1, 2); SeqListPushBack(&s1, 5); SeqListPushBack(&s1, 0); SeqListPushFront(&s1, 3);//头插 SeqListPopBack(&s1);//尾删 SeqListPopFront(&s1);//头删 SeqListInsert(&s1, 2, 9);//在pos的位置放入元素x SeqListErase(&s1, 3);//删除pos位置的元素 int num = SeqListFind(&s1, 2);//搜索 SeqListPrint(&s1);//打印 printf("%d\n", num);//打印搜索的下标 Destroy(&s1); } int main() { test1(); return 0; }
运行结果：
