顺序表
顺序表是什么?
顺序表是将元素顺序地存放在一块连续的存储区里,元素间的顺序关系由它们的存储顺序自然表示。实现增删查改的功能。
顺序表所需的头文件:
#include<stdio.h>#include<stdlib.h>#include<assert.h>
目录
顺序表
静态顺序表
动态顺序表
动态顺序表
顺序表的创建
顺序表的初始化
顺序表的销毁
打印顺序表
扩容
尾插
头插
尾删
头删
任意位置删除
任意位置插入
元素的查找
元素修改
测试代码和菜单
顺序表分为静态顺序表和动态顺序表。
静态顺序表
静态顺序表的空间不可改变,使用确定大小的数组来确定元素。
静态顺序表的创建:
typedef struct SeqList{int arr[512];int size; //数组中元素的个数};
动态顺序表
动态顺序表的空间可以被改变,使用动态内存函数开辟数组储存元素
动态顺序表的创建:
typedef struct SeqList{int* a;int size; //有多少元素int capaclity; //容量};
静态顺序表和动态顺序表的区别在于容量是否可变。
我们本节介绍动态顺序表。
动态顺序表
顺序表的创建
我们用一个指针开辟一个空间,既顺序表元素的空间。由于我们指针不一定是int型,为了严谨一定,我们自定义一个数据类型:
typedef int SEQ;
然后就可以创建一个完整的顺序表:
typedef struct SeqLisrt{SEQ* a;int size; //顺序表中有多少元素int capaciti; //顺序表的空间大小}SL;
顺序表的初始化
顺序表第一次使用前需要初始化:
void Init(SL* ps){ps->a = NULL;ps->size = 0;ps->capaciti = 0;}
顺序表的销毁
顺序表在使用完以后需要进行销毁保障安全:
void Destory(SL* ps){free(ps->a);ps->a = NULL;ps->size = 0;ps->capaciti = 0;}
使用free函数释放掉空间,并将其设置为空指针NULL。
打印顺序表
为了直观的看到顺序表里的元素,我们需要一个打印顺序表的函数:
void Print(SL* ps){int i = 0;for (i=0;i<ps->size;i++){printf("%d ",ps->a[i]);}}
扩容
当顺序表中的size>=capaciti是需要扩容,此时顺序表的空间不够用,那我们怎么进行扩容?
由于,最开始使用数据表顺序表被初始化,capaciti为0,将capiaciti的容量赋予在*2
其次赋予a新的空间,由于此时a为NULL,直接开辟新的空间会报警告,我们用一个中间变量tmp开启一块capaciti元素*2的空间,在将这块空间赋予a。
实现代码:
void CheckCapacity(SL* ps){if (ps->size == ps->capaciti){int newcapaciti = ps->capaciti == 0 ? 4 : ps->capaciti * 2; SEQ* tmp = (SEQ*)realloc(ps->a, newcapaciti * sizeof(SEQ)*2);ps->a = tmp;ps->capaciti = newcapaciti;}}
实现以上准备工作后,我们进入顺序表重点,增删查改功能的实现了。
尾插
size为顺序表中的元素个数,每当插入一个新元素后size++;
尾插:将新的元素放到顺序表最后一个元素的后面:
代码实现:
void PushBack(SL* ps, SEQ x){CheckCapacity(ps); //自定义的扩容函数ps->a[ps->size] = x;ps->size++;}
在对顺序表插入新元素的,使用自己写的扩容函数判断一下。
头插
头插:顺序表的元素往后移位,将新的元素放到顺序表的最前面:
void PushFront(SL* ps, SEQ x){CheckCapacity(ps);int end = ps->size - 1;while (end >= 0){ps->a[end+1] = ps->a[end];end--;}ps->a[0] = x;ps->size++;}
尾删
将最后的元素删去:
操作方法:将size--;
代码实现:
void PopBack(SL* ps){ps->size--;}
头删
将顺序表的第一个元素删掉。
操作方法:将顺序表的第一个元素后面的元素往前移一位,size--;
代码实现:
void PopFront(SL* ps){int start = 1;while (start < ps->size){ps->a[start - 1] = ps->a[start];start++;}ps->size--;}
任意位置删除
pos为下标 既要删除元素的位置。
实现方法和头删类似后面的元素覆盖掉前面的元素。
代码实现:
void Erase(SL* ps, int pos){int start = pos;while (start < ps->size - 1){ps->a[start] = ps->a[start + 1];start++;}ps->size--;}
任意位置插入
和头插类似,将元素往后移动在放入元素。
代码实现:
void Insert(SL* ps, int pos, SEQ x){int end = ps->size - 1;while (end > +pos){ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = x;ps->size++;}
元素的查找
使用循环以此查找,直到找到元素或顺序表没有此元素
找到元素返回下标,没有找到返回-1;
代码实现:
int Find(SL* ps, int pos){int i = 0;for (i = 0; i < ps->size; i++){if (ps->a[i] == pos){return i;}}return -1;}
元素修改
找到想修改的位置直接修改即可。
代码实现:
void At(SL* ps, int pos, SEQ x){ps->a[pos] = x;}
以上就是增删查改实现的全过程。
接下来我们来测试代码
测试代码和菜单
测试结果:
测试菜单代码:
void menu(){printf("********************************\n");printf("1.尾插数据 2.头插数据\n");printf("3.尾删数据 4.头删数据\n");printf("5.任意插入 6.任意删除\n");printf("7.修改数据 8.查找数据\n");printf("9.打印数据 -1.退出\n");printf("********************************\n");printf("请输入你操作的选项>:");}int main(){int option = 0;int x = 0;int i = 0;int pos = 0;SL s;Init(&s);//使用顺序表前先初始化while (option != -1){menu();scanf("%d", &option);switch (option){case 1:printf("请输入你要尾插的数据,以-1结束\n");do{scanf("%d", &x);if (x != -1){PushBack(&s, x);}} while (x != -1);break;case 2:printf("请输入你要头插的数据,以-1结束\n");do{scanf("%d", &x);if (x != -1){PushFront(&s, x);}} while (x != -1);break;case 3:printf("请输入你要尾删的元素个数\n");scanf("%d", &x);for (i = 0; i < x; i++){PopBack(&s);}break;case 4:printf("请输入你要头删的元素个数\n");scanf("%d", &x);for (i = 0; i < x; i++){PopFront(&s);}break;case 5:printf("请输入要插入的位置以及插入的数据\n");scanf("%d%d", &pos, &x);Insert(&s, pos, x);break;case 6:printf("请输入要删除的位置\n");scanf("%d", &pos);Erase(&s, pos);break;case 7:printf("请输入位置以及修改的数据\n");scanf("%d%d", &pos, &x);At(&s, pos, x);break;case 8:printf("请输入需要查找的数据\n");scanf("%d", &x);int ret = Find(&s, x);if (ret != -1){printf("找到了下标为:>%d\n", ret);}elseprintf("找不到\n");break;case 9:Print(&s);printf("\n");break;default:break;}}Destory(&s);//使用完后销毁return 0;}
以上就是本知识点的内容了。
求点个赞!!!!!!