数据结构——动态顺序表

数据结构的动态顺序表有以下几个操作：创建，销毁，初始化，增删查改和打印以及内存空间不够时的扩容

本文的宏定义：

#define SeqTypeData int

1.动态顺序表的创建

typedef struct SeqListInit{//动态顺序表的创建SeqTypeData* a;int size;//实际有效空间int capacity;//申请空间大小
}SL;

2.动态顺序表的销毁

void SeqListDestroy(SL* ps) {//顺序表销毁free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
};

值得注意的是，ps->a要赋值NULL，避免野指针的出现。

3.动态顺序表的初始化

void SeqListInit(SL* ps){//顺序表初始化ps->a = NULL;ps->capacity = ps->size = 0;
};

4.动态顺序表的增加

插入时都要判断空间是否足够，是否需要扩容，以及ps->size要加一。

（1）头插

void SeqListPushFront(SL* ps, SeqTypeData x) {//顺序表头插SeqListCheckCapacity(ps);//判断是否需要扩容//挪动数据ps->size++;for (int i = 0; i < ps->size; i++) {ps->a[ps->size - i] = ps->a[ps->size - i - 1];}ps->a[0] = x;
}

头插也就是把数据都向后挪一位，再给第一位赋值。

（2）尾插

void SeqListPushBack(SL* ps, SeqTypeData x) {//顺序表尾插SeqListCheckCapacity(ps);//判断是否需要扩容ps->a[ps->size++] = x;
}

（3）任意位置插入

void SeqListInsert(SL* ps, int adr, SeqTypeData x)//adr为逻辑地址，等于数组下标加一
{if (adr > (ps->size + 1) || adr < 1){printf("adr invalid\n");return;}SeqListCheckCapacity(ps);//判断是否需要扩容int end = ps->size ;while (end >= adr-1){ps->a[end + 1] = ps->a[end];--end;}ps->a[adr-1] = x;ps->size++;
}

任意位置插入要记得判断插入位置的合法性，再将插入位置的数据向后移一位，再在插入位置赋值即可。

5.动态顺序表的删除

进行删除操作时，要判断表是否已经是空表，此时不可再删。删除成功时，ps->size减一。

（1）头删

void SeqListPopFront(SL* ps) {//顺序表头删if (ps->size == 0){printf("顺序表为空，不可再删\n");}else{for (int i = 0; i < ps->size; i++) {ps->a[i] = ps->a[i+1];}ps->size--;}
}

（2）尾删

void SeqListPopBack(SL* ps) {//顺序表尾删if (ps->size--);else{printf("顺序表为空，不可再删\n");}
}

（3）任意位置删除

void SeqListErase(SL* ps, int adr) {if (ps->size == 0){printf("顺序表为空，不可再删\n");}if (adr > (ps->size + 1)){printf("删除位置错误\n");}for (int i = adr; i < ps->size; i++) {ps->a[i-1] = ps->a[i];}ps->size--;
}

任意位置的删除也要检验删除位置的合法性。

6.动态顺序表的任意位置的修改

void SeqListCheck(SL* ps, int adr, SeqTypeData x) {//adr为逻辑地址，等于数组下标加一if(adr>(ps->size+1))printf("修改位置错误\n");elseps->a[adr - 1] = x;
}

任意位置的修改也要检验删除位置的合法性。

7.顺序表的打印

void SeqListPrint(SL ps) {//顺序表打印for (int i = 0; i < ps.size; i++){printf("%d ", ps.a[i]);}
}

8.动态顺序表的扩容

void SeqListCheckCapacity(SL* ps) {//顺序表检查是否需要扩容if (ps->size == ps->capacity) {SeqTypeData newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SeqTypeData* tem = (SeqTypeData*)realloc(ps->a, newcapacity * sizeof(SeqTypeData));if (tem == NULL) {printf("realloc fail\n");exit(-1);}ps->a = tem;ps->capacity = newcapacity;}
}

9.全部代码

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"#include <stdio.h>
#include <stdlib.h>
#include <assert.h>void SeqListInit(SL* ps){//顺序表初始化ps->a = NULL;ps->capacity = ps->size = 0;
};void SeqListDestroy(SL* ps) {//顺序表销毁free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
};void SeqListPrint(SL ps) {//顺序表打印for (int i = 0; i < ps.size; i++){printf("%d ", ps.a[i]);}if (ps.size == 0)printf("顺序表为空");printf("\n");
}//int SeqListCapacity(SL* ps) {//
//	return ps->capacity;
//}void SeqListPushBack(SL* ps, SeqTypeData x) {//顺序表尾插SeqListCheckCapacity(ps);ps->a[ps->size++] = x;
}void SeqListPushFront(SL* ps, SeqTypeData x) {//顺序表头插SeqListCheckCapacity(ps);//挪动数据ps->size++;for (int i = 0; i < ps->size; i++) {ps->a[ps->size - i] = ps->a[ps->size - i - 1];}ps->a[0] = x;
}void SeqListCheckCapacity(SL* ps) {//顺序表检查是否需要扩容if (ps->size == ps->capacity) {SeqTypeData newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SeqTypeData* tem = (SeqTypeData*)realloc(ps->a, newcapacity * sizeof(SeqTypeData));if (tem == NULL) {printf("realloc fail\n");exit(-1);}ps->a = tem;ps->capacity = newcapacity;}
}void SeqListPopBack(SL* ps) {//顺序表尾删if (ps->size--);else{printf("顺序表为空，不可再删\n");}
}void SeqListPopFront(SL* ps) {//顺序表头删if (ps->size == 0){printf("顺序表为空，不可再删\n");}else{for (int i = 0; i < ps->size; i++) {ps->a[i] = ps->a[i+1];}ps->size--;}
}void SeqListFind(SL ps, SeqTypeData x) {//顺序表查找/*int cnt;*/for (int i = 0; i < ps.size; i++) {if (ps.a[i] == x) {printf("%d", i + 1);//返回逻辑下标/*cnt++;*/}}/*if (cnt == 0)printf("没有这个数字");*/
}void SeqListInsert(SL* ps, int adr, SeqTypeData x)//adr为逻辑地址，等于数组下标加一
{if (adr > (ps->size + 1) || adr < 1){printf("adr invalid\n");return;}SeqListCheckCapacity(ps);int end = ps->size ;while (end >= adr-1){ps->a[end + 1] = ps->a[end];--end;}ps->a[adr-1] = x;ps->size++;
}void SeqListErase(SL* ps, int adr) {//adr为逻辑地址，等于数组下标加一if (ps->size == 0){printf("顺序表为空，不可再删\n");}if (adr > (ps->size + 1)){printf("删除位置错误\n");}for (int i = adr; i < ps->size; i++) {ps->a[i-1] = ps->a[i];}ps->size--;
}void SeqListCheck(SL* ps, int adr, SeqTypeData x) {if(adr>(ps->size+1))printf("修改位置错误\n");elseps->a[adr - 1] = x;
}void menu()
{printf("请选择\n");printf("********1.头插  2.尾插********\n");printf("********3.头删  4.尾删********\n");printf("********5.随插  6.随删********\n");printf("********7.查找  8.打印********\n");printf("********9.修改  0.退出********\n");printf("请选择\n");
}int main()
{int input;SL ps;SeqTypeData x;int adr;SeqListInit(&ps);do {menu();scanf("%d", &input);switch (input){case 1:printf("请输入头插数字\n");scanf("%d", &x);SeqListPushFront(&ps, x);break;case 2:printf("请输入尾插数字\n");scanf("%d", &x);SeqListPushBack(&ps, x);break;case 3:SeqListPopFront(&ps);break;case 4:SeqListPopBack(&ps);break;case 5:printf("请输入插入位置和数字\n");scanf("%d%d", &adr, &x);SeqListInsert(&ps, adr, x);break;case 6:printf("请输入删除位置\n");scanf("%d", &adr);SeqListErase(&ps, adr);break;case 7:printf("请输入查找数字\n");scanf("%d", &x);SeqListFind(ps, x);break;case 8:SeqListPrint(ps);break;case 9:printf("请输入修改位置和数字\n");scanf("%d%d", &adr, &x);SeqListCheck(&ps, adr, x);break;case 0:printf("正在退出中");break;}} while (input);return 0;
}

10.效果展示

由于图片大小问题，只展示了部分功能。