阅读量:5
顺序表
前言：相信大家在学完C语言后，对于指针，结构体以及动态内存管理有了一定的见解，那么数据结构像是检验真理的唯一标椎，它考察了你掌握这三种语法的程度，如果掌握的不是很理想的友友们，建议看看鄙人主页总结的文章，好啦，数据结构之旅就正式开始啦。
一.数据结构
数据结构：计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成，即数据由那部分构成，以什么方式构成，以及数据元素之间呈现的结构。
1.逻辑结构
逻辑结构：数据对象中数据元素之间的相互关系。
逻辑结构分为：集合结构，线性结构，树形结构和图形结构。
2.物理结构
物理结构：数据的逻辑结构在计算机中的存储形式。
物理结构分为：顺序存储结构和链式存储结构。
二.顺序表的分类
顺序表实际属于线性表这个大家族，那么什么是线性表呢？
- 线性表：是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
- 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，
- 线性表在物理上存储时，通常以
数组和链式结构的形式存储。
1.静态顺序表
#define MAXSIZE 100 //静态顺序表的容量 typedef int SLDataType; //增强程序的可维护性 typedef struct SeqList { SLDataType arr[MAXSIZE];//定长数组 int size; //有效的数据个数 }SeqList; 也许有人会问：这个静态顺序表说的这么神秘，本质上不就是一个数组吗？
答：没错，顺序表的低层就是数组，逻辑结构与物理结构都是连续的。不过顺序表对数组进行了封装，提供了大量常用的接口（所谓接口就是调用函数），方便完成数据进行增，删，查，改等一系列的操作。
静态顺序表的缺点：程序一但运行，数组的大小就确定了，不能被修改。数组大小给小了，空间就不够用；数组大小给大了，空间就白白的浪费掉了；
为了方便对静态顺序表进行扩容，于是，动态顺序表便应运而生。
2.动态顺序表
typedef int SLDataType;//增强程序的可维护性 typedef struct SeqList { SLDataType* arr; //动态的，可以扩容 int size; //有效的数据个数 int capacity; //容量 }SL; 动态顺序表：通过堆区的动态内存管理控制顺序表空间的大小，即容量。
以下介绍的是基于动态顺序表的实现。
三.顺序表的实现
1.创建顺序表
创建一个顺序表结构，包含指向这块空间的起始地址，顺序表中存储数据的个数以及顺序表的最大容量。
typedef int SLDataType;//增强程序的可维护性，改变数据类型，只需改变int即可 typedef struct SeqList { SLDataType* arr; //指向顺序表的起始位置，方便扩容 int size; //顺序表的有效的数据个数 int capacity; //顺序表的容量大小 }SL;//类型的重命名 //等价于typedef struct SeqList SL; SL sl;//sl就代表顺序表 2.初始化顺序表
一般初始化我们都习惯赋值为0，指针赋值为NULL。
void SeqListInit(SL* ps) { assert(ps);//断言操作，等价于assert(ps != NULL); ps->arr = NULL; ps->size = 0; ps->capacity = 0; } 3.判断是否扩容
当我们想要增加数据的时候，会遇到容量不够用的问题。所以在此之前，应该检查容量与有效数据之间的关系，判断是否要扩容，接着插入数据。
void SeqListCheckCapacity(SL* ps) { assert(ps); if (ps->size == ps->capacity)//顺序表已满，进行扩容操作 { //判断顺序表容量是否为0，若为0，开辟储存4个数据大小的空间，若不为0，则容量翻倍 int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; //开辟空间 SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType)); if (tmp == NULL)//开辟失败 { perror("realloc fail!"); exit(1);//强行退出程序（表示遇到异常情况） } ps->arr = tmp;//开辟成功，修改指针 ps->capacity = newcapacity;//修改容量 } } 注意：若传入realloc的指针为空指针(NULL)，则realloc函数等价于malloc函数。
4.打印顺序表
循环遍历顺序表数据即可。
void SeqListPrint(SL* ps) { assert(ps); for (int i = 0; i < ps->size; i++) { printf("%d ", ps->arr[i]); } printf("\n"); } 5.插入操作
1.头插
头插的思想：将数据整体向后挪动一位。注意：为了防止覆盖原先的数据，采用从后向前挪动。再进行头部插入，最后有效数据个数+1。
void SeqListPushFront(SL* ps, SLDataType x) { assert(ps); SeqListCheckCapacity(ps);//检查容量 int end = ps->size; while (end > 0) { ps->arr[end] = ps->arr[end - 1];//将数据整体向后挪动一位。 end--; } ps->arr[0] = x;//头插 ps->size++;//有效数据个数+1 //等价于在下标为0处插入：SeqListInsert(ps, 0, x); } 2.尾插
尾插的思想：直接在尾部插入，有效数据个数+1即可。
void SeqListPushBack(SL* ps, SLDataType x) { assert(ps); SeqListCheckCapacity(ps);//检查容量 ps->arr[ps->size++] = x;//尾插：采用后置++ //等价于在下标为ps->size处插入：SeqListInsert(ps, ps->size, x); } 3.按照下标插入
按照下标插入的思想：与头插的思想相同，只不过是要挪动数据的起始位置不同而已。
void SeqListInsert(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos <= ps->size);//判断下标的合法性 SeqListCheckCapacity(ps); int end = ps->size; while (end > pos) { ps->arr[end] = ps->arr[end - 1]; end--; } ps->arr[pos] = x; ps->size++; } 6.删除操作
1.头删
头删的思想：不是真正意义上的删除数据，而是将头部之后的数据整体向前挪动一位，覆盖头部数据，达到与头删相同的效果，最后有效数据个数-1。注意：为了防止覆盖原先的数据，采用从前向后挪动，这里与头插不同。
void SeqListPopFront(SL* ps) { assert(ps); assert(ps->size > 0);//前提：顺序表存在数据 int start = 0; while (start < ps->size - 1) { ps->arr[start] = ps->arr[start + 1]; start++; } ps->size--;//有效数据个数-1 //等价于在下标为0处删除：SeqListErase(ps, 0); } 2.尾删
尾删的思想：有效数据个数-1即可。
void SeqListPopBack(SL* ps) { assert(ps); assert(ps->size > 0);//前提：顺序表存在数据 ps->size--;//有效数据个数-1 //等价于在下标为ps->size - 1处删除：SeqListErase(ps, ps->size - 1); } 3.按照下标删除
按照下标删除的思想：与头删的思想相同，只不过是要挪动数据的起始位置不同而已。
void SeqListErase(SL* ps, int pos) { assert(ps); assert(ps->size > 0);//前提：顺序表存在数据 assert(pos >= 0 && pos < ps->size);//判断下标的合法性 int start = pos; while (start < ps->size - 1) { ps->arr[start] = ps->arr[start + 1]; start++; } ps->size--; } 7.查找数据
查找的思想：遍历数据，找到了返回下标，未找到返回-1即可。
int SeqListFind(SL* ps, SLDataType x) { assert(ps); for (int i = 0; i < ps->size; i++) { if (ps->arr[i] == x) { return i;//找到该数据，返回下标 } } return -1;//未找到，返回-1 } 8.修改数据
修改的思想：利用下标确定位置，直接修改就行。较为简单。
void SeqListModify(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos < ps->size); ps->arr[pos] = x; } 9.清空顺序表
清空的思想：将有效数据个数与容量赋值为0。
void SeqListClear(SL* ps) { assert(ps); ps->size = 0; ps->capacity = 0; } 10.销毁顺序表
销毁的思想：由于空间是利用动态内存函数 realloc 在堆区开辟的，所以要及时释放，避免内存泄漏。
void SeqListDestory(SL* ps) { assert(ps); if (ps->arr != NULL) { free(ps->arr); } ps->arr = NULL;//置为NULL，防止野指针 SeqListClear(ps);//清空顺序表 } 四.模块化源代码
1.SeqList.h
//#pragma once：防止头文件被重复包含 #ifndef __SEQLIST_H__ #define __SEQLIST_H__ #include<stdio.h> #include<stdlib.h> #include<string.h> #include<assert.h> typedef int SLDataType;//增强程序的可维护性 typedef struct SeqList { SLDataType* arr; //动态的，可以扩容 int size; //有效的数据个数 int capacity; //容量 }SL; void SeqListInit(SL* ps);//顺序表初始化 void SeqListCheckCapacity(SL* ps);//检查顺序表的容量 void SeqListPrint(SL* ps);//打印顺序表 void SeqListPushBack(SL* ps, SLDataType x);//顺序表尾部插入 void SeqListPushFront(SL* ps, SLDataType x);//顺序表头部插入 void SeqListPopBack(SL* ps);//顺序表尾部删除 void SeqListPopFront(SL* ps);//顺序表头部删除 void SeqListInsert(SL* ps, int pos, SLDataType x);//顺序表按照位置（下标）插入 void SeqListErase(SL* ps, int pos);//顺序表按照位置（下标）删除 int SeqListFind(SL* ps, SLDataType x);//顺序表查找元素值，返回下标 void SeqListModify(SL* ps, int pos, SLDataType x);//顺序表按位置（下标）修改 void SeqListClear(SL* ps);//清空顺序表 void SeqListDestory(SL* ps);//销毁顺序表 #endif 2.SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"SeqList.h" void SeqListInit(SL* ps) { assert(ps);//等价于assert(ps != NULL); ps->arr = NULL; ps->size = 0; ps->capacity = 0; } void SeqListCheckCapacity(SL* ps) { assert(ps); if (ps->size == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));//扩容 if (tmp == NULL) { perror("realloc fail!"); exit(1);//强行退出程序（表示遇到异常情况） } ps->arr = tmp; ps->capacity = newcapacity; } } void SeqListPrint(SL* ps) { assert(ps); for (int i = 0; i < ps->size; i++) { printf("%d ", ps->arr[i]); } printf("\n"); } void SeqListPushBack(SL* ps, SLDataType x) { assert(ps); SeqListCheckCapacity(ps); ps->arr[ps->size++] = x; //SeqListInsert(ps, ps->size, x); } void SeqListPushFront(SL* ps, SLDataType x) { assert(ps); SeqListCheckCapacity(ps); int end = ps->size; while (end > 0) { ps->arr[end] = ps->arr[end - 1]; end--; } ps->arr[0] = x; ps->size++; //SeqListInsert(ps, 0, x); } void SeqListPopBack(SL* ps) { assert(ps); assert(ps->size > 0); ps->size--; //SeqListErase(ps, ps->size - 1); } void SeqListPopFront(SL* ps) { assert(ps); assert(ps->size > 0); int start = 0; while (start < ps->size - 1) { ps->arr[start] = ps->arr[start + 1]; start++; } ps->size--; //SeqListErase(ps, 0); } void SeqListInsert(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos <= ps->size); SeqListCheckCapacity(ps); int end = ps->size; while (end > pos) { ps->arr[end] = ps->arr[end - 1]; end--; } ps->arr[pos] = x; ps->size++; } void SeqListErase(SL* ps, int pos) { assert(ps); assert(ps->size > 0); assert(pos >= 0 && pos < ps->size); int start = pos; while (start < ps->size - 1) { ps->arr[start] = ps->arr[start + 1]; start++; } ps->size--; } int SeqListFind(SL* ps, SLDataType x) { assert(ps); for (int i = 0; i < ps->size; i++) { if (ps->arr[i] == x) { return i; } } return -1; } void SeqListModify(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos < ps->size); ps->arr[pos] = x; } void SeqListClear(SL* ps) { assert(ps); ps->size = 0; ps->capacity = 0; } void SeqListDestory(SL* ps) { assert(ps); if (ps->arr != NULL) { free(ps->arr); } ps->arr = NULL; SeqListClear(ps); } 3.test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"SeqList.h" enum//匿名枚举 { EXIT, PUSHBACK, PUSHFRONT, POPBACK, POPFRONT, INSERT, ERASE, FIND, MODIFY, PRINT, CLEAR }; void Menu() { printf("*************顺序表************\n"); printf("****1.尾插 2.头插****\n"); printf("****3.尾删 4.头删****\n"); printf("****5.插入 6.删除****\n"); printf("****7.查找 8.修改****\n"); printf("****9.打印 10.清空****\n"); printf("****0.退出 ******\n"); printf("*******************************\n"); } int main() { SL sl; SeqListInit(&sl); int select = 0; //菜单选项 SLDataType value; //插入的值 int pos = 0; //插入或删除的下标 do { Menu(); printf("请选择您的操作："); scanf("%d", &select); switch (select) { case EXIT: printf("退出顺序表!"); break; case PUSHBACK: printf("请输入您要尾插的值(输入-1代表结束)："); while ((scanf("%d", &value), value != -1)) //逗号表达式 { SeqListPushBack(&sl, value); } break; case PUSHFRONT: printf("请输入您要头插的值(输入-1代表结束)："); do { scanf("%d", &value); if (value != -1) { SeqListPushFront(&sl, value); } } while (value != -1); break; case POPBACK: SeqListPopBack(&sl); break; case POPFRONT: SeqListPopFront(&sl); break; case INSERT: printf("请输入要插入的《下标》与《值》："); scanf("%d %d", &pos, &value); SeqListInsert(&sl, pos, value); break; case ERASE: printf("请输入要删除的《下标》："); scanf("%d", &pos); SeqListErase(&sl, pos); break; case FIND: printf("请输入要查找的《值》："); scanf("%d", &value); int ret = SeqListFind(&sl, value); if (ret != -1) { printf("找到了下标为：%d\n", ret); } else { printf("找不到!"); } break; case MODIFY: printf("请输入要修改的《下标》以及修改后的《值》:"); scanf("%d %d", &pos, &value); SeqListModify(&sl, pos, value); break; case PRINT: SeqListPrint(&sl); break; case CLEAR: SeqListClear(&sl); break; default: printf("您输入的值错误，请重新选择!\n"); break; } } while (select); SeqListDestory(&sl); return 0; } 五.顺序表必做OJ题
创作不易，如果能帮到你的话能赏个三连吗？感谢啦！！！
