动态顺序表基本操作--头插头删尾插尾删-阿里云开发者社区

动态顺序表基本操作--头插头删尾插尾删

2023-09-26 29

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 动态顺序表基本操作--头插头删尾插尾删

顺序表就是一个数组，有静态的，也有动态的。动态顺序表相比静态顺序表更加灵活，可以进行扩容。

静态顺序表：静态顺序表

🎑构建动态顺序表

//动态顺序表
typedef int DataType;
typedef struct SeqList
{
  DataType* a;//指向动态开辟数组的第一个元素的位置
  int size;//存储有效数据个数
  int capacity;//空间大小
}SeqList;

🎑初始化和销毁

注意，静态顺序表是在栈上开辟的，动态顺序表是在堆上开辟的。因为是在堆上动态开辟的，所以用完之后我们要手动销毁所开辟的内存。

🎃初始化1.0

最简单的初始化是初始线性表指向第一个元素的指针为空，size=0，capacity=0.

即：

//初始化
void Init(SeqList* p)
{
  p->a = NULL;
  p->size = 0;
  p->capacity = 0;
}

🎃初始化2.0

初始化时给线性表开一些空间。

//初始化2.0
void SLInit(SeqList* p)
{
  p->a = (DataType*)malloc(sizeof(DataType) * 4);//开辟四个空间
  if (p->a == NULL)//假如malloc开辟空间失败
  {
    perror("malloc failed");
    exit(-1);//让程序以异常的形式退出
  }
  p->size = 0;//有效元素个数为0；
  p->capacity = 4;
}

🎃空间销毁

//空间销毁
void SLDestroy(SeqList* p)
{
  free(p->a);
  p->a = NULL;
  p ->size = 0;
  p->capacity = 0;
}

🎑动态表基本操作

🎃打印

void SLprint(SeqList* p)
{
  int i = 0;
  for (i = 0; i < p->size; i++)
  {
    printf("%d ", p->a[i]);
  }
  printf("\n");
}

🎃尾插

//后插
void SLPushBack(SeqList* p, DataType x)
{
  if (p->size == p->capacity)//线性表已满->扩容
  {
    DataType* tmp = (DataType*)realloc(p->a, p->capacity * 2 * (sizeof(DataType)));
    if (tmp == NULL)
    {
      perror("relloc failed");
      exit(-1);
    }
    p->a = tmp;
    p->capacity *= 2;
  }
  p->a[p->size] = x;
  p->size++;
}

🎃尾删

//尾删
void SLPopBack(SeqList* p)
{
  if (p->size == 0)
    return;
  p->size--;
}

//尾删
void SLPopBack(SeqList* p)
{
  //if (p->size == 0)
  //  return;
  assert(p->size > 0);
  p->size--;
}

🎃扩容

void SLCheckCapacity(SeqList* p)
{
  //扩容
  if (p->size == p->capacity)//线性表已满->扩容
  {
    DataType* tmp = (DataType*)realloc(p->a, p->capacity * 2 * (sizeof(DataType)));
    if (tmp == NULL)
    {
      perror("relloc failed");
      exit(-1);
    }
    p->a = tmp;
    p->capacity *= 2;
  }
}

🎃头插

//头插
void SLPushFront(SeqList *p,DataType x)
{
  //检查容量是否已经满
  SLCheckCapacity(p);
  int end = p->size - 1;
  while (end >= 0)
  {
    p->a[end + 1] = p - >a[end];
    --end;
  }
}

🎃头删

//头删
void SLPopFront(SeqList* p)
{
  if (p->size == 0)
    return;
  int start=1;
  while (start <= p->size - 1)
  {
    p->a[start - 1] = p->a[start];
    start++;
  }
  p->size--;
}

🎑调试运行

尾插

打印

尾删

打印

头插

打印

头删

打印

销毁空间

🎆完整代码

test.c 主函数中进行调试

SeqList.c 实现各种函数

SeqList.h 头文件

🎆SeqList.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//动态顺序表
typedef int DataType;
typedef struct SeqList
{
  DataType* a;//指向动态开辟数组的第一个元素的位置
  int size;//存储有效数据个数
  int capacity;//空间大小
}SeqList;
void Init(SeqList* p);
void SLInit(SeqList* p);
void SLDestroy(SeqList* p);
void SLprint(SeqList* p);
void SLCheckCapacity(SeqList* p);//扩容
void SLPushBack(SeqList* p, DataType x);//后插
void SLPopBack(SeqList* p);//尾删
void SLPushFront(SeqList* p, DataType x);
void SLPopFront(SeqList* p);

🎆SeqList.c

#include "SeqList.h"
//初始化1.0
void Init(SeqList* p)
{
  p->a = NULL;
  p->size = 0;
  p->capacity = 0;
}
//初始化2.0
void SLInit(SeqList* p)
{
  p->a = (DataType*)malloc(sizeof(DataType) * 4);//开辟四个空间
  if (p->a == NULL)//加入malloc开辟空间失败
  {
    perror("malloc failed");
    exit(-1);//让程序以异常的形式退出
  }
  p->size = 0;//有效元素个数为0；
  p->capacity = 4;
}
//空间销毁
void SLDestroy(SeqList* p)
{
  free(p->a);
  p->a = NULL;
  p ->size = 0;
  p->capacity = 0;
}
void SLprint(SeqList* p)
{
  int i = 0;
  for (i = 0; i < p->size; i++)
  {
    printf("%d ", p->a[i]);
  }
  printf("\n");
}
void SLCheckCapacity(SeqList* p)
{
  //扩容
  if (p->size == p->capacity)//线性表已满->扩容
  {
    DataType* tmp = (DataType*)realloc(p->a, p->capacity * 2 * (sizeof(DataType)));
    if (tmp == NULL)
    {
      perror("relloc failed");
      exit(-1);
    }
    p->a = tmp;
    p->capacity *= 2;
  }
}
//后插
void SLPushBack(SeqList* p, DataType x)
{
  if (p->size == p->capacity)//线性表已满->扩容
  {
    DataType* tmp = (DataType*)realloc(p->a, p->capacity * 2 * (sizeof(DataType)));
    if (tmp == NULL)
    {
      perror("relloc failed");
      exit(-1);
    }
    p->a = tmp;
    p->capacity *= 2;
  }
  p->a[p->size] = x;
  p->size++;
}
//尾删
void SLPopBack(SeqList* p)
{
  //if (p->size == 0)
  //  return;
  assert(p->size > 0);
  p->size--;
}
//头插
void SLPushFront(SeqList *p,DataType x)
{
  int end = p->size - 1;
  while (end >= 0)
  {
    p->a[end + 1] = p ->a[end];
    --end;
  }
  p ->a[0] = x;
  p->size++;
}
//头删
void SLPopFront(SeqList* p)
{
  if (p->size == 0)
    return;
  if (p->size==p->capacity)
    //扩容
    SLCheckCapacity(p);
  int start=1;
  while (start <= p->size - 1)
  {
    p->a[start - 1] = p->a[start];
    start++;
  }
  p->size--;
}

🎆test.c

#include "SeqList.h"
int main()
{
  SeqList s;//创建线性表变量
  SLInit(&s);//初始化
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLprint(&s);
  SLPopBack(&s);//尾删
  SLprint(&s);
  SLPushFront(&s, 10);
  SLprint(&s);
  SLPopFront(&s);
  SLprint(&s);
  SLDestroy(&s);
  return 0;
}