静态顺序表
test.c
//顺序表是物理地址连续的存储单元，一次存储数据元素的线性结构，在数组上实现数据增删查改
//顺序表一般可以分为
//1.静态的顺序表：使用定长数组存储
//2.动态的顺序表，使用动态开辟的数组进行存储
//1.连续的物理空间存储——数组
//2.数据必须是从头开始，依次存储，一个一个存
//静态的顺序表，给少了不够用，够多了浪费，不能灵活利用
#include"seqlist.h"
void testseqlist()
{
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);
seqlistpushback(&s, 8);
seqlistpushback(&s, 9);
seqlistpushback(&s, 10);
seqlistpushback(&s, 11);
}
int main()
{
testseqlist();
return 0;
}seqlist.c
#include"seqlist.h"
void seqlistinit(SL* ps)
{
memset(ps->a, 0, sizeof(seqdata)*n);//对数组初始化为0
ps->sz = 0;
}
void seqlistpushback(SL*ps, seqdata x)
{
if (ps->sz >= n)
{
printf("seqlist is full\n");
return;
}
ps->a[ps->sz] = x;//尾插在sz下一个位置的下标
ps->sz++;
//sz可能会超过数组的最大范围，会越界
}seqlist.h
#pragma once
#include<stdio.h>
#include<string.h>
#define n 10
typedef int seqdata;
typedef struct seqlist
{
seqdata a[n];
int sz;
}SL;
void testseqlist();
//初始化一个数组
void seqlistinit(SL* ps);
//尾插
void seqlistpushback(SL*ps, seqdata x);动态版顺序表
seqlist.h
#define _CRT_SECURE_NO_WARNINGS 1;
#pragma once
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
#define n 10
typedef int seqdata;
typedef struct seqlist
{
seqdata *a;//指向动态开辟的数组
int sz;//有效数据的个数
int capacity;//记录容量
}SL;
void testseqlist();
//初始化一个数组
void seqlistinit(SL* ps);
//尾插
void seqlistpushback(SL*ps, seqdata x);
//打印
void seqlistprint(SL*ps);
//头插
void seqlistpushfront(SL *ps, seqdata x);
//检查容量是否充足
void seqlistcheckcapacity(SL*ps);
//尾删
void seqlistpopback(SL*ps);
//头删
void seqlistpopfront(SL*ps);
//中间插入
void seqlistinsert(SL*ps, int pos, seqdata x);
//中间删除
void seqlisterase(SL*ps, int pos);
//销毁
void seqlistdestroy(SL*ps);
//查
void seqlistfind(SL *ps, seqdata x);
//修改
void seqlistmodify(SL *ps,int pos, seqdata x);
seqlist.c
#include"seqlist.h"
void seqlistinit(SL* ps)//对顺序表进行初始化
{
ps->a = NULL;
ps->sz = 0;
ps->capacity = 0;
}
//尾插
void seqlistpushback(SL*ps, seqdata x)
{
seqlistcheckcapacity(ps);
ps->a[ps->sz] = x;//尾插在sz下一个位置的下标
ps->sz++;
//sz可能会超过数组的最大范围，会越界
}
//打印
void seqlistprint(SL*ps)
{
for (int i = 0; i < ps->sz; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
//头插
void seqlistpushfront(SL *ps, seqdata x)//同样面临一个增容的问题，但每次都写增容的代码很麻烦，所以我们可以写一个
{
seqlistcheckcapacity(ps);
int end = ps->sz - 1;
//循环while的写法
//1.初始条件
//2.结束条件
//3.迭代过程
//头插就是每一位都往后挪,第一个位置空了出来
while (end >= 0)//我们想的结束的条件，而循环写的是继续的条件
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[0] = x;//把第一个元素插入
ps->sz++;
}
//搞出一个函数原来检查容量是否充足，如果不足就要增容
void seqlistcheckcapacity(SL*ps)
{
if (ps->sz == ps->capacity)//有效数据对于最大容量，那么我们就要进行扩容
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//一开始sz为0，capacity也为0，所以当等于时有两种情况，
//1.为开辟空间
//2.sz到达了capabilities的容量
//如果一开始的capaci的初值为0，就把capacity改为4，否则就把他扩容两倍
//我们一般扩2倍，扩一倍浪费时间，扩3倍浪费空间
seqdata *tmp = (seqdata*)realloc(ps->a, newcapacity * 2 * sizeof(seqdata));
if (tmp == NULL)
{
printf("realloc failur");
return;
}
else
{
ps->a = tmp;
ps->capacity = newcapacity;
}
}
}
//尾删
void seqlistpopback(SL*ps)
{
//假如说sz为0就不用删除了
//但是如果想用粗暴的方法
//断言，如果大于0就继续删除，等于0的化就会报错
assert(ps->sz>0);
//由sz来标识有多少个有效数据
//直接把sz--，把有效数据减少就行了
//如果我们把最后一个数据置为0，再sz--，不合适，因为可能最后一个元素本来就是一个0，或者他并不是int类型，是一个double类型的变量
ps->sz--;
}
//头删
void seqlistpopfront(SL*ps)
{
//同时也要预防头没有数据了
assert(ps->sz > 0);
int start = 1;
//前一个都用后一个来覆盖
while (start < ps->sz)
{
ps->a[start - 1] = ps->a[start];//start下标最多到sz-1的位置
start++;
}
//头部数据删除完之后
//同样sz也要减
ps->sz--;
}
void seqlistinsert(SL*ps, int pos, seqdata x)
{
//pos只能再sz有效数据里面进行选择
assert(pos < ps->sz);
seqlistcheckcapacity(ps);
int end = ps->sz - 1;
while (end>=pos)
{
ps->a[end + 1] = ps->a[end];
end--;
}
//直到end挪到小于pos就终止了
ps->a[pos] = x;//pos是数组的下标
ps->sz++;
}
void seqlisterase(SL*ps, int pos)
{
//一次把后面的数据往前挪
//把pos的位置给覆盖掉
assert(pos < ps->sz);
int start = pos + 1;
while (start < ps->sz)
{
ps->a[start-1] = ps->a[start];
start++;
}
ps->sz--;
}
void seqlistdestroy(SL*ps)//malloc出来的空间不销毁就会内存泄露
{
free(ps->a);
ps->a = NULL;
ps->sz = ps->capacity = 0;
}
void seqlistfind(SL *ps, seqdata x)//如果有序的化就可以使用二分查找
{
//假如是有序的化，就可以用二分查找，但他并不是有序的
//那么我们就用暴力解法
int i = 0;
for (i = 0; i < ps->sz; i++)
{
if (ps->a[i] == x)
{
return i;//返回x的下标
}
}
return -1;//如果找到的化就返回下标，每找到就返回-1，因为数组里面的下标不可能是-1
}
void seqlistmodify(SL *ps, int pos, seqdata x)
{
assert(pos < ps->sz);
ps->a[pos] = x;
}test.c
//顺序表是物理地址连续的存储单元，一次存储数据元素的线性结构，在数组上实现数据增删查改
//顺序表一般可以分为
//1.静态的顺序表：使用定长数组存储
//2.动态的顺序表，使用动态开辟的数组进行存储
//1.连续的物理空间存储——数组
//2.数据必须是从头开始，依次存储，一个一个存
//静态的顺序表，给少了不够用，够多了浪费，不能灵活利用
#include"seqlist.h"
void testseqlist()
{
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);
seqlistpushback(&s, 8);
seqlistpushback(&s, 9);
seqlistpushback(&s, 10);
seqlistpushback(&s, 11);
seqlistpushfront(&s, 0);
seqlistpushfront(&s, -1);
seqlistpopfront(&s);
seqlistpopback(&s);
seqlistinsert(&s, 0, 20);//0数组的下标
seqlisterase(&s, 0);
seqlistprint(&s);
seqlistdestroy(&s);
}
int main()
{
testseqlist();
return 0;
}随后我会上传一些顺序表的oj