目录
前言
一、初始准备
二、尾插尾删
三、头插尾删
四、随机位置插入删除
五、顺序表缺陷
六、全部代码
前言
顺序表和链表都是线性表
顺序表的本质就是数组，能够连续存储数据
一、初始准备
建立结构体
静态版本
由于静态版本容量是固定的，所以只需两个成员即可，即数据成员和记录有效数据的成员
由于静态版本不好控制容量大小，大了容易造成浪费，小了无法使用，所以选择动态版本更合适
动态版本
有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;
}
