数据结构(顺序表)

简介: 数据结构(顺序表)

1.线性表

线性表是n个相同特性的数据元素的有限序列,常见的线性表有:顺序表、链表、栈、队列...

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

理上存储时,通常以数组和链式结构的形式存储。

da316be621c54134a4b608826516876c.png

2.顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组

上完成数据的增删查改。

顺序表一般可以分为:

1. 静态顺序表:使用定长数组存储元素。

#define N 7
typedef int Data
 
typedef struct Seqlist
{
   Data arr[N];  //定长数组
   size_t size;  //有效个数
}Seqlist


2. 动态顺序表:使用动态开辟的数组存储。

 
typedef int Data
 
typedef struct Seqlist
{
   Data arr*;  //变长数组
   size_t size;  //有效个数
   size_t capacity //容量
}Seqlist


3.顺序表的接口实现

静态顺序表只适合数据个数已经确定的场合,如果不是,则顺序表的N给大了会造成空间浪费,给小了也不够用的情况,所以我们使用更加灵活的动态顺序表。

顺序表头文件(函数声明):

#pragma once
#include<stdio.h>
typedef int Data;
typedef struct Stu
{
  Data* a;
  int size;
  int capacity;
}stu;
stu p;
//初始化和销毁
void SLInit(stu* ps);
void SLDestroy(stu* ps);
//打印顺序表数据
void SLPrint(stu* ps);
//扩容
void SLCheckCapacity(stu* ps);
 
//头部插入删除 / 尾部插入删除
void SLPushBack(stu* ps, Data x);
void SLPopBack(stu* ps);
void SLPushFront(stu* ps, Data x);
void SLPopFront(stu* ps);
 
//指定位置之前插入/删除数据
void SLInsert(stu* ps, int pos, Data x);
void SLErase(stu* ps, int pos);


初始化和销毁:

//初始化销毁
void SLInit(stu* ps)
 {
  ps->a = NULL;
  ps->size = ps->capacity = 0;
  Data* b;
  b = (Data*)malloc(sizeof(Data) * 4);
  if (b == NULL)
    return 1;
  ps->a = b;
  ps->capacity = 4;
}
//销毁
void SLDestroy(stu* ps)
{
  free(ps->a);
  ps->a = NULL;
  ps->size = 0;
  ps->capacity = 0;
}


打印顺序表数据:

//打印
void SLPrint(stu* ps)
{
  for (int i = 0; i < ps->size; i++)
  {
    printf("%d ", ps->a[i]);
  }
}


扩容:

//扩容
void SLCheckCapacity(stu* ps)
{
  Data* b;
  b = (Data*)realloc(ps->a, sizeof(Data) * ps->capacity * 2);
  ps->capacity = ps->capacity * 2;
  if (b == NULL)
    return 1;
  ps->a = b;
}


尾部插入删除:

//尾插
void SLPushBack(stu* ps, Data x)
{
  if (ps->size == ps->capacity)
  {
    SLCheckCapacity(&p);
  }
  ps->a[ps->size] = x;
  ps->size++;
}
//尾删
void SLPopBack(stu* ps)
{
  ps->size--;
}


头部插入删除:

//头插
void SLPushFront(stu* ps, Data x)
{
  if (ps->size == ps->capacity)
  {
    SLCheckCapacity(&p);
  }
  for (int i = ps->size; i>0; i--)
  {
     ps -> a[i] =ps->a[i - 1];
  }
  ps->a[0] = x;
  ps->size++;
}
//头删
void SLPopFront(stu* ps)
{
  for (int i = 0; i < ps->size-1; i++)
  {
    ps->a[i] = ps->a[i+1];
  }
  ps->size--;
}


指定位置之前插入/删除数据:

//指定位置之前插入
void SLInsert(stu* ps, int pos, Data x)
{
  if (ps->size < pos)
    return 1;
  if (ps->capacity == 0 || ps->size == ps->capacity)
  {
    SLCheckCapacity(&p);
  }
  for (int i = 0; i < ps->size - pos + 1; i++)
  {
    ps->a[ps->size-i] = ps->a[ps->size-1-i];
  }
  ps->a[pos] = x;
  ps->size++;
}
//指定位置删除
void SLErase(stu* ps, int pos)
{
  for (int i = 0; i < ps->size - pos; i++)
  {
    ps->a[pos + i] = ps->a[pos + i+1];
  }
  ps->size--;
}


目录
相关文章
|
9天前
|
存储 缓存 算法
数据结构和算法学习记录——总结顺序表和链表(双向带头循环链表)的优缺点、CPU高速缓存命中率
数据结构和算法学习记录——总结顺序表和链表(双向带头循环链表)的优缺点、CPU高速缓存命中率
11 0
TU^
|
23天前
|
存储 索引
数据结构~~顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存 储。在数组上完成数据的增删查改。
TU^
22 0
|
24天前
|
存储 缓存
[数据结构]——顺序表和链表
[数据结构]——顺序表和链表(下):https://developer.aliyun.com/article/1515507
|
1天前
|
存储 机器学习/深度学习 算法
【数据结构与算法】:手搓顺序表(Python篇)
【数据结构与算法】:手搓顺序表(Python篇)
|
1天前
|
存储 算法 C++
【数据结构与算法】:带你手搓顺序表(C/C++篇)
【数据结构与算法】:带你手搓顺序表(C/C++篇)
|
5天前
数据结构初阶 顺序表的补充
数据结构初阶 顺序表的补充
5 0
|
5天前
|
存储
数据结构初阶 顺序表的讲解
数据结构初阶 顺序表的讲解
7 0
|
9天前
|
算法
数据结构和算法学习记录——复习静态顺序表的两个接口函数(在指定位置插入数据,在指定位置删除数据)
数据结构和算法学习记录——复习静态顺序表的两个接口函数(在指定位置插入数据,在指定位置删除数据)
6 0
|
9天前
|
存储 算法
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)
8 0
|
9天前
|
存储 算法
数据结构和算法学习记录——线性表之顺序表(顺序表概念、结构、顺序表接口函数-头插头删、尾插尾删)
数据结构和算法学习记录——线性表之顺序表(顺序表概念、结构、顺序表接口函数-头插头删、尾插尾删)
8 0