数据结构第三弹----顺序表-阿里云开发者社区

数据结构第三弹----顺序表

2024-03-26 20

版权

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

简介： 数据结构第三弹----顺序表

1、线性表

1.1、线性表的基本框架

1.2、线性表的概念

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

1.3、线性表的存储结构

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，

线性表在物理上存储时，通常以数组和链式结构的形式存储。

2.顺序表

2.1、顺序表的概念

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

2.2、顺序表的存储结构

静态顺序表：使用定长数组存储元素。（缺陷：空间给少了不够用，给多了造成空间浪费）
动态顺序表：使用动态开辟的数组存储。（优势：动态开辟空间，使用相对灵活，相比于静态开辟空间也可以少空间浪费）

2.2、顺序表接口函数实现

注：顺序表不仅仅只要下面实现的这些函数喔，实现方式也是不唯一的，有兴趣的uu可以将头插尾插头删尾删用指定位置插入删除实现喔！！！

(1)头文件-----(头文件的包含、顺序表的结构创建和接口函数的声明)

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//顺序表的动态存储
typedef int SLDataType;
typedef struct SeqList
{
  SLDataType* a; //指向动态开辟的数组
  int size;      //有效数据个数
  int capacity;  //容量空间的大小
}SL;
//初始化
void SeqListInit(SL* s);
//
void SeqListDestroy(SL* s);
//打印
void SeqListPrint(SL* s);
//头插
void SeqListPushFront(SL* s, SLDataType x);
//尾插
void SeqListPushBack(SL* s, SLDataType x);
//头删
void SeqListPopFront(SL* s);
//尾删
void SeqListPopBack(SL* s);
//指定位置插入
void SeqListInsert(SL* s, int pos, SLDataType x);
//指定位置删除
void SeqListErase(SL* s, int pos);
//大小
int SeqListLength(SL* s);
//修改指定位置数据
void SeqListModify(SL* s, int pos, SLDataType x);
// 顺序表查找
int SeqListFind(SL* s, SLDataType x);

(2)源文件-----(顺序表接口函数的实现)

#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"
//打印
void SeqListPrint(SL* s)
{
  assert(s);//S指针不为空
  for (int i = 0; i < s->size; i++)
  {
    printf("%d ", s->a[i]);
  }
  printf("\n");
}
//初始化
void SeqListInit(SL* s)
{
  assert(s);
  assert(s->a);//数据起始地址不为空才初始化
  s->a = NULL;
  s->size = s->capacity = 0;
}
//销毁  新加
void SeqListDestroy(SL* s)
{
  assert(s);
  free(s->a);
  s->a = NULL;
  s->size = s->capacity = 0;
}
//检查容量
void SeqListCheckCapacity(SL* s)
{
  assert(s);
  if (s->size == s->capacity)
  {
    //两种情况 一种没有元素 一种满元素 扩容
    int newcapacity = s->capacity == 0 ? 4 : 2 * s->capacity;
    //开辟空间
    SLDataType* tmp = (SLDataType*)realloc(s->a, sizeof(SLDataType) * newcapacity);
    
    //判断是否开辟成功
    if (tmp == NULL)
    {
      //失败则直接退出程序
      printf("realloc fail\n");
      exit(-1);
    }
    else
    {
      //把空间和容量给原来顺序表
      s->a = tmp;
      s->capacity = newcapacity;
    }
  }
}
//头插
void SeqListPushFront(SL* s, SLDataType x)
{
  assert(s);
  SeqListCheckCapacity(s);
  int end = s->size - 1;
  while (end >= 0)
  {
    s->a[end + 1] = s->a[end];
    end--;
  }
  s->a[0] = x;
  s->size++;
}
//尾插
void SeqListPushBack(SL* s, SLDataType x)
{
  assert(s);
  //检查容量 空间  注意形参写什么 定义为一级指针用一级指针
  SeqListCheckCapacity(s);
  s->a[s->size] = x;
  s->size++;
}
//头删
void SeqListPopFront(SL* s)
{
  assert(s);
  assert(s->size > 0);
  int start = 0;
  while (start < s->size - 1)
  {
    s->a[start] = s->a[start + 1];
    start++;
  }
  s->size--;
}
//尾删
void SeqListPopBack(SL* s)
{
  assert(s);
  assert(s->size > 0);
  s->size--;
}
// 顺序表查找  新加
int SeqListFind(SL* s, SLDataType x)
{
  assert(s);
  assert(s->size > 0);
  for (int i = 0; i < s->size; i++)
  {
    if (s->a[i] == x);
    return i;
  }
  return -1;
}
//指定位置插入 pos是下标
void SeqListInsert(SL* s, int pos, SLDataType x)
{
  assert(s);
  //pos在数组大小范围内
  assert(pos >= 0 && pos < s->size);
  SeqListCheckCapacity(s);
  int end = s->size - 1;
  while (end >= pos)
  {
    s->a[end + 1] = s->a[end];
    end--;
  }
  s->a[pos] = x;
  s->size++;
}
//指定位置删除
void SeqListErase(SL* s, int pos)
{
  assert(s);
  assert(pos >= 0 && pos < s->size);
  assert(s->size > 0);
  int start = pos;
  while (start < s->size - 1)
  {
    s->a[start] = s->a[start + 1];
    start++;
  }
  s->size--;
}
//大小
int SeqListLength(SL* s)
{
  assert(s);
  return s->size;
}
void SeqListModify(SL* s, int pos, SLDataType x)
{
  assert(s);
  s->a[pos] = x;
}

(3)源文件(顺序表函数接口的测试)

#include "SeqList.h"
void testSeqList()
{
  SL s;
  //初始化
  SeqListInit(&s);
  //尾插测试
  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 2);
  SeqListPushBack(&s, 3);
  SeqListPushBack(&s, 4);
  //打印
  SeqListPrint(&s);
  //头插测试
  SeqListPushFront(&s, 5);
  SeqListPushFront(&s, 6);
  SeqListPushFront(&s, 7);
  //打印
  SeqListPrint(&s);
  //尾删测试
  SeqListPopBack(&s);
  SeqListPopBack(&s);
  SeqListPopBack(&s);
  SeqListPrint(&s);
  //头删测试
  SeqListPopFront(&s);
  SeqListPopFront(&s);
  SeqListPrint(&s);
  //在下标为1的位置插入
  SeqListInsert(&s, 1, 10);
  SeqListPrint(&s);
  //下标为0的位置删除
  SeqListErase(&s, 0);
  SeqListPrint(&s);
  //长度测试
  int length = SeqListLength(&s);
  printf("顺序表长度为：%d\n", length);
  //修改测试
  SeqListModify(&s, 0, 100);
  SeqListPrint(&s);
}
int main()
{
  testSeqList();
  return 0;
}