25.顺序表专题-阿里云开发者社区

25.顺序表专题

2024-06-03 11

版权

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

简介： 25.顺序表专题

介绍

1.目标：做出一个通讯录项目 //下一篇发布~

2.数据结构是计算机存储，组织数据的方式

3.作用

1）能够存储数据

2）存储的数据能够方便查找

如果把数据比作草原上的散乱羊，在其有了结构之后就能很快的找到某只羊

4.接下来我们先来探讨一下线性表其中的顺序表（底层类似于数组，本质为指针）

线性表：具有相同特性的数据结构

物理结构：不一定连续（其中的顺序表物理也连续
逻辑结构：连续

通过数据结构，能够有效将数据组织和管理在一起，对数据进行增删查改

最基础的数据结构：数组

5.顺序表分类：静态顺序表和动态顺序表

我们主要来对动态数据表进行讨论，因为其的空间利用会更灵活，可以按需求申请

动态顺序表

实现：

.h部分 1.顺序表结构 2.声明顺序表的方法

.c部分 1.增删查改的实现 2.实现顺序表的方法 3.运行

SeqList.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#define INIT_CAPACITY 4
typedef int SLDataType;
typedef struct Seqlist
{
  SLDataType* a;
  int size;//有效数据个数
  int capacity; //空间容量
}SL;
//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);
//扩容
void SLCheckCapacity(SL* ps);
//头部尾部的插入删除
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
//指定位置之前插入/删除
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, SLDataType x);

SeqList.c //增删查改

#include"SeqList.h"
void SLInit(SL* ps)
{
  ps->a = NULL;
  ps->size = 0;
  ps->capacity = 0;
}
void SLDestroy(SL* ps)
{
  free(ps->a);
  ps->a = NULL;
}
void SLPrint(SL* ps)
{
  int i = 0;
  for (i = 0; i < ps->size; i++)
  {
    printf("%d ", ps->a[i]);
  }
  printf("\n");
}
//检查容量
void SLCheckCapacity(SL* ps)
{
  if (ps->size == ps->capacity)
  {
    int Newcapacity;
    Newcapacity = (ps->capacity == 0) ? 4 : (2 * ps->capacity);
    SLDataType* p = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * Newcapacity);
    if (p == NULL)
    {
      perror("realloc fail");
      exit(1);
    }
    else
    {
      ps->a = p;
      ps->capacity = Newcapacity;//realloc没错就将其赋值给ps->capacity
    }
  }
}
//尾插
void SLPushBack(SL* ps,SLDataType x)
{
  assert(ps);
  SLCheckCapacity(ps);
  ps->a[ps->size] = x;//要用p->size
  ps->size++;
}
void SLPopBack(SL* ps)
{
  assert(ps);
  SLCheckCapacity(ps);
  ps->size--;
}
void SLPushFront(SL* ps, SLDataType x)
{
  assert(ps);
  SLCheckCapacity(ps);
  int i = 0;
  for (i = ps->size; i > 0; i--)
    ps->a[i] = ps->a[i - 1];
  ps->a[0] = x;
  ps->size++;
}
void SLPopFront(SL* ps)
{
  assert(ps);
  SLCheckCapacity(ps);
  int i = 0;
  for (i = 0; i<ps->size-1; i++)
    ps->a[i] = ps->a[i + 1];
  ps->size--;
}
//指定位置之前插入/删除
void SLInsert(SL* ps, int pos, SLDataType x)
{
  assert(ps);
  SLCheckCapacity(ps);
  int i = 0;
  for (i = ps->size; i > pos; i--)
    ps->a[i] = ps->a[i - 1];
  ps->a[pos] = x;
  ps->size++;
}
void SLErase(SL* ps, int pos)
{
  assert(ps);
  SLCheckCapacity(ps);
  int i = 0;
  for (i = pos; i < ps->size - 1; i++)
    ps->a[i] = ps->a[i + 1];
  ps->size--;
}
int SLFind(SL* ps, SLDataType x)
{
  for (int i = 0; i < ps->size; i++)
  {
    if (ps->a[i] == x)
      return i;
  }
  printf("nofind\n");
  return 0;
}

test.c

#include"SeqList.h"
int main()
{
  SL s1;//注意结构体的设置
  SL* p = &s1;
  SLInit(p);
  SLPushBack(p, 1);
  SLPushBack(p, 2);
  SLPushBack(p, 3);
  SLPushBack(p, 4);
  SLPushFront(p, 99);
  SLPopBack(p);
  SLInsert(p, 2, 88);
  SLPrint(p);
  SLDestroy(p);
}

运行结果

sum：

敲的时候主要是感觉单词有点长，不过早点养成好的命名习惯啦，如果去除增强安全性的代码，实际上的思路就是最简单的数组，建议大家边写边调试，就会清晰多啦

文章标签：

存储