©2020-2024 ioDraw All rights reserved,
Privacy Policy
目录
前言
一、初始准备
二、尾插尾删
三、头插尾删
四、随机位置插入删除
五、顺序表缺陷
六、全部代码
前言
顺序表和链表都是线性表
顺序表的本质就是数组，能够连续存储数据
一、初始准备
建立结构体
静态版本
由于静态版本容量是固定的，所以只需两个成员即可，即数据成员和记录有效数据的成员
由于静态版本不好控制容量大小，大了容易造成浪费，小了无法使用，所以选择动态版本更合适
动态版本
有3个成员，一个是数据成员类型的指针，指向开辟空间的起始位置，第二个则是记录有效数据的成员，第三个则是目前容量的大小
因为结构体类型名字太长，不方便使用，所以用typedef将其类型名修改
为了方便存储不同类型的数据，则也用typedef将类型名修改，比如存储浮点型数据时，只要将int改为float或double即可
初始化结构体变量
由于要改变实参，所以必须传地址，即
把其数据成员全部置为0或NULL
判断容量
由于起初没有开辟空间，所以不知道是满了，还是根本就没开辟空间，所以用条件操作符来判断
同时还要判断增容是否失败，失败了就提示一下，然后exit(-1)退出程序
由于realloc增容有两种情况，所以采用把起始地址返回给一个临时指针变量，增容成功后再赋值给原来的指针变量即可
销毁顺序表和初始化顺序表差不多，只是多了个free
调试看写的代码是否没有错误太麻烦，所以得打印
二、尾插尾删
每次尾插数据时都要判断容量是否足够
每次尾删时都要查看顺序表中还有没有数据，采用断言的方式，方便找错
三、头插尾删
每次头插也要判断容量是否足够
头插需要往后挪动数据，把第一个元素的空间空出来，再插入像插入的数据
每次头删时都要查看顺序表中还有没有数据，采用断言的方式，方便找错
四、随机位置插入删除
要想对随机位置的数据进行插入与删除，那就必须得先找到其下标
查找下标，循环遍历即可，找得到就返回其下标，找不到就返回-1
每次随机插入都要判断容量是否足够
同时还要判断i是否再数组下标范围内，采用断言，方便找错
随机删除要判断i是否再数组下标范围内，采用断言，方便找错
五、顺序表缺陷
空间不够了，需要扩容，扩容是有消耗的
避免频繁扩容，一次一般是扩容2倍，可能存在一定空间的的浪费
头插或者中间插入时，需要挪动数据，也是有消耗的
六、全部代码
//头文件 #pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h>
//静态版本 //typedef int DataType; //#define N 1000 //typedef struct SeqList //{ //
DataType a[N]; // int sz; //}SL; //动态版本 typedef int DataType; typedef struct
SeqList { DataType* a; int sz;//有效数据的个数 int capacity;//以开辟空间的大小 }SL; //初始化顺序表
void SeqListInit(SL* ps); //检查容量 void SeqListCheckCapacity(SL* ps); //销毁循序表
void SeqListDestroy(SL* ps); //打印顺序表 void SeqListPrint(SL* ps); //尾插 void
SeqListPushBack(SL* ps, DataType x); //尾删 void SeqListPopBack(SL* ps); //头插
void SeqListPushFront(SL* ps, DataType x); //头删 void SeqListPopFront(SL* ps);
//查找 int SeqListFind(SL* ps, DataType pos); //随机位置插入 void SeqListInsert(SL* ps,
DataType x); //随机位置删除 void SeqListDelete(SL* ps); //定义文件 #include"SeqList.h"
void SeqListInit(SL* ps) { ps->a = NULL; ps->sz = 0; ps->capacity = 0; } void
SeqListCheckCapacity(SL* ps) { if (ps->sz == ps->capacity) { int newcapacity =
ps->capacity == 0 ? 4 : 2 * ps->capacity; DataType* tmp =
(DataType*)realloc(ps->a, sizeof(DataType) * newcapacity); if (tmp == NULL) {
printf("增容失败\n"); exit(-1); } ps->capacity = newcapacity; ps->a = tmp; } } void
SeqListDestroy(SL* ps) { free(ps->a); ps->a = NULL; ps->sz = 0; ps->capacity =
0; } void SeqListPrint(SL* ps) { int i = 0; for (i = 0; i < ps->sz; i++) {
printf("%d ", ps->a[i]); } printf("\n"); } void SeqListPushBack(SL* ps,
DataType x) { SeqListCheckCapacity(ps); ps->a[ps->sz] = x; ps->sz++; } void
SeqListPopBack(SL* ps) { assert(ps->sz > 0); ps->sz--; } void
SeqListPushFront(SL* ps,DataType x) { SeqListCheckCapacity(ps); int end1 =
ps->sz; while (end1) { int end2 = end1 - 1; ps->a[end1--] = ps->a[end2]; }
ps->a[end1] = x; ps->sz++; } void SeqListPopFront(SL* ps) { assert(ps->sz > 0);
int begin1 = 0; while (begin1 < ps->sz) { int begin2 = begin1 + 1;
ps->a[begin1++] = ps->a[begin2]; } ps->sz--; } int SeqListFind(SL* ps, DataType
pos) { int cur = 0; while (cur < ps->sz) { if (ps->a[cur] == pos) { return cur;
} else { cur++; } } return -1; } void SeqListInsert(SL* ps, DataType x) {
SeqListCheckCapacity(ps); int i = SeqListFind(ps, 5); assert(i >= 0 && i <=
ps->sz); int end1 = ps->sz; while (end1 > i) { int end2 = end1 - 1;
ps->a[end1--] = ps->a[end2]; } ps->a[end1] = x; ps->sz++; } void
SeqListDelete(SL* ps) { int i = SeqListFind(ps, 5); assert(i >= 0 && i <=
ps->sz); while (i < ps->sz) { int cur = i + 1; ps->a[i++] = ps->a[cur]; }
ps->sz--; } //测试文件 #include"SeqList.h" void test1() { SL s; SeqListInit(&s);
SeqListPushBack(&s, 1); SeqListPushBack(&s, 2); SeqListPushBack(&s, 3);
SeqListPushBack(&s, 4); SeqListPushBack(&s, 5); SeqListPushBack(&s, 6);
SeqListPushBack(&s, 7); SeqListPrint(&s); SeqListPopBack(&s);
SeqListPopBack(&s); SeqListPopBack(&s); SeqListPopBack(&s); SeqListPopBack(&s);
SeqListPrint(&s); SeqListDestroy(&s); } void test2() { SL s; SeqListInit(&s);
SeqListPushFront(&s, 1); SeqListPushFront(&s, 2); SeqListPushFront(&s, 3);
SeqListPushFront(&s, 4); SeqListPushFront(&s, 5); SeqListPushFront(&s, 6);
SeqListPushFront(&s, 7); SeqListPrint(&s); SeqListPopFront(&s);
SeqListPopFront(&s); SeqListPopFront(&s); SeqListPopFront(&s);
SeqListPopFront(&s); SeqListPrint(&s); /*int ret = SeqListFind(&s, 3);
printf("查找的数的下标为：%d\n", ret);*/ SeqListDestroy(&s); } void test3() { SL s;
SeqListInit(&s); SeqListPushBack(&s, 1); SeqListPushBack(&s, 2);
SeqListPushBack(&s, 3); SeqListPushBack(&s, 4); SeqListPushBack(&s, 5);
SeqListPushBack(&s, 6); SeqListPushBack(&s, 7); SeqListInsert(&s, 15);
SeqListPrint(&s); SeqListDelete(&s); SeqListPrint(&s); } int main() {
//test1(); //test2(); test3(); return 0; }