20221027数据结构与算法之线性表——顺序表

广州疫情被封区，在家学习

#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
//动态顺序表的实现
typedef int data_t;

typedef struct SeqList
{
  data_t* data;
  size_t size;//实际大小
  size_t capacity;//总大小
}SL;

void SeqListInit(SL* ps)//初始化顺序表
{
  ps->data = NULL;
  ps->size = ps->capacity = 0;
}

void SeqListPrint(SL* ps)//测试打印顺序表
{
  int i;
  for (i = 0; i < ps->size; i++)
  {
    printf("%d ", ps->data[i]);
  }
  printf("\n");
}

void SeqListPushBack(SL* ps, data_t x)//尾插
{
  if (ps->capacity == ps->size)//如果顺序表满了，则扩容*2
  {
    size_t newcapacity = (ps->capacity == 0) ? 4 : ps->capacity * 2;
    data_t* temp = (data_t*)realloc(ps->data, newcapacity * sizeof(ps->data));
    if (temp == NULL)
    {
      printf("realloc fail.");
    }
    ps->data = temp;
    ps->capacity = newcapacity;
  }
  //
  ps->data[ps->size] = x;
  ps->size++;
}

void SeqListPopBack(SL* ps)//尾删
{
  if (ps->size == 0)
  {
    printf("error:no data");
  }
  else
  {
    ps->size--;
  }
}

void SeqListPushFront(SL* ps, data_t x)//头插
{
  if (ps->capacity == ps->size)//如果顺序表满了，则扩容*2
  {
    size_t newcapacity = (ps->capacity == 0) ? 4 : ps->capacity * 2;
    data_t* temp = (data_t*)realloc(ps->data, newcapacity * sizeof(ps->data));
    if (temp == NULL)
    {
      printf("realloc fail.");
    }
    ps->data = temp;
    ps->capacity = newcapacity;
  }
  if (ps->size > 0)//如果有数据则向后挪动
  {
    int begin = ps->size;
    while (begin > 0)
    {
      ps->data[begin] = ps->data[begin - 1];
      begin--;
    }
  }
  ps->data[0] = x;//扩容+挪数据之后，再插入
  ps->size++;
}

void SeqListPopFront(SL* ps)//头删
{
  if (ps->capacity == 0 || ps->size == 0)
  {
    printf("error:no data.");
  }
  else
  {
    ps->data++;      //两种方法
    ps->size--;
    ps->capacity--;
    /*  int begin = 0;
      while (begin < ps->size)
      {
        ps->data[begin] = ps->data[begin + 1];
        begin++;
      }
      ps->size--;*/
  }
}

int SeqListFind(SL* ps, data_t x)//查找
{
  int i;
  for (i = 0; i < ps->size; i++)
  {
    if (ps->data[i] == x)
    {
      return i;//有这个元素，只能找第一个
    }
  }
  return -1;//找不到，
}

void SeqListInsert(SL* ps, data_t x,int k)//任意位置插入
{
  //
}

int main()
{
  SL s1;
  SeqListInit(&s1);

  SeqListPushBack(&s1, 4);
  SeqListPushBack(&s1, 3);
  SeqListPushBack(&s1, 2);
  SeqListPushBack(&s1, 1);
  SeqListPushFront(&s1, 5);
  SeqListPrint(&s1);
  int index = SeqListFind(&s1, 2);
  printf("找到2了，下标为%d\n", index);

  SeqListPopFront(&s1);
  SeqListPopFront(&s1);
  SeqListPopFront(&s1);
  SeqListPopFront(&s1);
  SeqListPopFront(&s1);
  SeqListPopFront(&s1);//error no data.


  return 0;
}