顺序表

//顺序表是物理地址连续的存储单元，一次存储数据元素的线性结构，在数组上实现数据增删查改
//顺序表一般可以分为
//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;
}

#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可能会超过数组的最大范围，会越界
}

#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);

#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);

#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;
}

//顺序表是物理地址连续的存储单元，一次存储数据元素的线性结构，在数组上实现数据增删查改
//顺序表一般可以分为
//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;
}