顺序表就是一个数组，有静态的，也有动态的。动态顺序表相比静态顺序表更加灵活，可以进行扩容。
静态顺序表： 静态顺序表
🎑构建动态顺序表
//动态顺序表 typedef int DataType; typedef struct SeqList { DataType* a;//指向动态开辟数组的第一个元素的位置 int size;//存储有效数据个数 int capacity;//空间大小 }SeqList;
🎑初始化和销毁
注意，静态顺序表是在栈上开辟的，动态顺序表是在堆上开辟的。因为是在堆上动态开辟的，所以用完之后我们要手动销毁所开辟的内存。
🎃初始化1.0
最简单的初始化是初始线性表指向第一个元素的指针为空，size=0，capacity=0.
即：
//初始化 void Init(SeqList* p) { p->a = NULL; p->size = 0; p->capacity = 0; }
🎃初始化2.0
初始化时给线性表开一些空间。
//初始化2.0 void SLInit(SeqList* p) { p->a = (DataType*)malloc(sizeof(DataType) * 4);//开辟四个空间 if (p->a == NULL)//假如malloc开辟空间失败 { perror("malloc failed"); exit(-1);//让程序以异常的形式退出 } p->size = 0;//有效元素个数为0； p->capacity = 4; }
🎃空间销毁
//空间销毁 void SLDestroy(SeqList* p) { free(p->a); p->a = NULL; p ->size = 0; p->capacity = 0; }
🎑动态表基本操作
🎃打印
void SLprint(SeqList* p) { int i = 0; for (i = 0; i < p->size; i++) { printf("%d ", p->a[i]); } printf("\n"); }
🎃尾插
//后插 void SLPushBack(SeqList* p, DataType x) { if (p->size == p->capacity)//线性表已满->扩容 { DataType* tmp = (DataType*)realloc(p->a, p->capacity * 2 * (sizeof(DataType))); if (tmp == NULL) { perror("relloc failed"); exit(-1); } p->a = tmp; p->capacity *= 2; } p->a[p->size] = x; p->size++; }
🎃尾删
//尾删 void SLPopBack(SeqList* p) { if (p->size == 0) return; p->size--; }
//尾删 void SLPopBack(SeqList* p) { //if (p->size == 0) // return; assert(p->size > 0); p->size--; }
🎃扩容
void SLCheckCapacity(SeqList* p) { //扩容 if (p->size == p->capacity)//线性表已满->扩容 { DataType* tmp = (DataType*)realloc(p->a, p->capacity * 2 * (sizeof(DataType))); if (tmp == NULL) { perror("relloc failed"); exit(-1); } p->a = tmp; p->capacity *= 2; } }
🎃头插
//头插 void SLPushFront(SeqList *p,DataType x) { //检查容量是否已经满 SLCheckCapacity(p); int end = p->size - 1; while (end >= 0) { p->a[end + 1] = p - >a[end]; --end; } }
🎃头删
//头删 void SLPopFront(SeqList* p) { if (p->size == 0) return; int start=1; while (start <= p->size - 1) { p->a[start - 1] = p->a[start]; start++; } p->size--; }
🎑调试运行
尾插
尾插
尾插
打印
尾删
打印
头插
打印
头删
打印
销毁空间
🎆完整代码
test.c 主函数中进行调试
SeqList.c 实现各种函数
SeqList.h 头文件
🎆SeqList.h
#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> #include<assert.h> //动态顺序表 typedef int DataType; typedef struct SeqList { DataType* a;//指向动态开辟数组的第一个元素的位置 int size;//存储有效数据个数 int capacity;//空间大小 }SeqList; void Init(SeqList* p); void SLInit(SeqList* p); void SLDestroy(SeqList* p); void SLprint(SeqList* p); void SLCheckCapacity(SeqList* p);//扩容 void SLPushBack(SeqList* p, DataType x);//后插 void SLPopBack(SeqList* p);//尾删 void SLPushFront(SeqList* p, DataType x); void SLPopFront(SeqList* p);
🎆SeqList.c
#include "SeqList.h" //初始化1.0 void Init(SeqList* p) { p->a = NULL; p->size = 0; p->capacity = 0; } //初始化2.0 void SLInit(SeqList* p) { p->a = (DataType*)malloc(sizeof(DataType) * 4);//开辟四个空间 if (p->a == NULL)//加入malloc开辟空间失败 { perror("malloc failed"); exit(-1);//让程序以异常的形式退出 } p->size = 0;//有效元素个数为0； p->capacity = 4; } //空间销毁 void SLDestroy(SeqList* p) { free(p->a); p->a = NULL; p ->size = 0; p->capacity = 0; } void SLprint(SeqList* p) { int i = 0; for (i = 0; i < p->size; i++) { printf("%d ", p->a[i]); } printf("\n"); } void SLCheckCapacity(SeqList* p) { //扩容 if (p->size == p->capacity)//线性表已满->扩容 { DataType* tmp = (DataType*)realloc(p->a, p->capacity * 2 * (sizeof(DataType))); if (tmp == NULL) { perror("relloc failed"); exit(-1); } p->a = tmp; p->capacity *= 2; } } //后插 void SLPushBack(SeqList* p, DataType x) { if (p->size == p->capacity)//线性表已满->扩容 { DataType* tmp = (DataType*)realloc(p->a, p->capacity * 2 * (sizeof(DataType))); if (tmp == NULL) { perror("relloc failed"); exit(-1); } p->a = tmp; p->capacity *= 2; } p->a[p->size] = x; p->size++; } //尾删 void SLPopBack(SeqList* p) { //if (p->size == 0) // return; assert(p->size > 0); p->size--; } //头插 void SLPushFront(SeqList *p,DataType x) { int end = p->size - 1; while (end >= 0) { p->a[end + 1] = p ->a[end]; --end; } p ->a[0] = x; p->size++; } //头删 void SLPopFront(SeqList* p) { if (p->size == 0) return; if (p->size==p->capacity) //扩容 SLCheckCapacity(p); int start=1; while (start <= p->size - 1) { p->a[start - 1] = p->a[start]; start++; } p->size--; }
🎆test.c
#include "SeqList.h" int main() { SeqList s;//创建线性表变量 SLInit(&s);//初始化 SLPushBack(&s, 1); SLPushBack(&s, 2); SLPushBack(&s, 3); SLprint(&s); SLPopBack(&s);//尾删 SLprint(&s); SLPushFront(&s, 10); SLprint(&s); SLPopFront(&s); SLprint(&s); SLDestroy(&s); return 0; }
