【数据结构与算法02】 顺序表

简介: 顺序存储:逻辑上相邻的元素存在地址相邻的区域内,每个元素占的空间都相等

线性表


定义


具有相同的数据类型的几个数据元素有限序列,其中n为表长,当n=0时线性表是空表,如下:



线性表的基本操作(创销、增删改查)


  1. InitList(&L):初始化表,构造空的线性表L,分配内存空间
  2. DestroyList(&L):销毁操作,销毁线性表,并释放空间
  3. ListInsert(&L,i,e):插入
  4. ListDelete(&L,i,e):删除
  5. LocateElem(L,e):按值查找
  6. GetElem(L,e):按位查找
  7. &L:取L的地址


什么时候传入引用&? --对参数的修改结果需要"带回来"


c49bf6ca3d059cca76b3acca43d27783.jpg


顺序表


逻辑上相邻,物理(地址)上也相邻


顺序存储:逻辑上相邻的元素存在地址相邻的区域内,每个元素占的空间都相等


Q:如何判断一个数据元素的大小


A:sizeof(x),x是数据类型,注意sizeof是C语言32个关键字之一


静态分配


8539ef32da57dcc9cd0b54037284ac9d.jpg


动态分配


f93f099923fbd876ec867828ded12047.jpg


动态申请和释放内存空间


malloc:开辟一片存储空间,返回一个空的指针


L.data=(ElemType *)malloc(sizeof(ElemType) *Initsize)


ElemType *:强制转型你定义的元素指针


例如:data的数据类型为int,则ElemType也应转为int类型


顺序表的特点


  1. 随机访问
  2. 存储密度高
  3. 扩展容量难


初始化顺序表


typedef struct {
  int *data;//指示动态分配数组的指针
  int MaxSize;//顺序表的最大容量
  int lenght;//顺序表的当前长度
} SeqList;
void InitList(SeqList &L) {
  //使用malloc申请一片连续的存储空间:sizeof(int)=4Byte
  L.data = (int *)malloc(InitSize * sizeof(int));
  L.lenght = 0;
  L.MaxSize = InitSize;
}


顺序表的插入删除查找


插入


Screenshot_20221002_085333.jpg


//插入
bool ListInsert(SeqList &L, int i, int e) {
  if (i < 1 || i > L.lenght + 1) {
    return false;
  }
  if (L.lenght > InitSize) {
    return false;
  }
  for (int j = L.lenght; j >= i; j--) {
    L.data[j] = L.data[j - 1];
  }
  L.data[i - 1] = e;
  L.lenght++;
  return true;
}


1.传入L,注意这里的L使用了😉&,所以是传入L的本身,而不是它的复制品


2.使用了一个for循环,让第i-1个元素之后的所有元素,都向后移动一位,同时也能逆向找到插入次序i


for (int j = L.lenght; j >= i; j--) {L.data[j] = L.data[j - 1];}


3.插入元素值,L.data[i - 1] = e;


删除


//删除
bool ListDelete(SeqList &L, int i, int &e) {
  printf("%d\n", i);
  if (i < 1 || i > L.lenght) {
    printf("%d", L.lenght);
    return false;
  }
  e = L.data[i - 1];
  for (int j = i; j < L.lenght; j++) {
    L.data[j - 1] = L.data[j];
  }
  L.lenght--;
  return true;
}


查找


2c4bb9a6f9b336c0e1175dfff90656fb.jpg

相关文章
|
2月前
|
存储 编译器 C语言
数据结构-顺序表详解(看这篇就足够了,哈哈哈)
数据结构-顺序表详解(看这篇就足够了,哈哈哈)
57 2
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
1月前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
66 3
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
2月前
|
存储 Java
数据结构第二篇【关于java线性表(顺序表)的基本操作】
数据结构第二篇【关于java线性表(顺序表)的基本操作】
35 6
|
2月前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
26 3
|
2月前
|
存储 C语言
探索C语言数据结构:利用顺序表完成通讯录的实现
本文介绍了如何使用C语言中的顺序表数据结构实现一个简单的通讯录,包括初始化、添加、删除、查找和保存联系人信息的操作,以及自定义结构体用于存储联系人详细信息。
32 2
|
2月前
|
存储
【数据结构】线性表和顺序表
【数据结构】线性表和顺序表
22 1
|
2月前
|
存储 算法 索引
【数据结构】——顺序表
【数据结构】——顺序表
|
2月前
|
存储
数据结构1——顺序表
数据结构1——顺序表
19 1