《大话数据结构》读书笔记——第3章 线性表 顺序存储结构知识点及代码实现【带注释】

本文涉及的产品
传统型负载均衡 CLB,每月750个小时 15LCU
网络型负载均衡 NLB,每月750个小时 15LCU
EMR Serverless StarRocks,5000CU*H 48000GB*H
简介: 《大话数据结构》读书笔记——第3章 线性表 顺序存储结构知识点及代码实现【带注释】

线性表(List):零个或多个数据元素的有限序列


3.2线性表的定义


关键点:

  1. 元素之间存在顺序,若元素存在多个,则第一个元素无前驱,最后一个元素无后继,中间元素有且只有一个前驱与后继。
  2. 在较复杂的线性表中,一个数据元素可以由多个数据项构成;

image.png


3.4线性表的顺序存储结构


用一段地址连续的存储单元一次存储线性表的数据元素。


描述顺序存储结构的三个属性

  • 存储的起始位置
  • 线性表的最大存储容量
  • 线性表的当前长度


举个例子:

小明同学要倒6杯水,首先他拿出了将纸杯一个个从塑料袋中取出连续的摆在桌上,拿第一个杯子的时候得考虑好起始位置,不然可能后面的杯子无法放置。

这时最大容量即容器数目已经确定了,开始按先后顺序给杯子倒水,开始倒水-倒完之间的任意时刻的装满水的杯子的数量为当前量。

notice:当前长度在任意时刻,都会小于等于最大存储容量。(线性表长度<=数组的长度)


3.5.4 线性表顺序存储结构的优缺点


image.png


C语言代码实现线性表的顺序存储结构


抽象数据类型

ADT 线性表(list)
Data
Operation
    InitList(*L);           初始化操作,建立一个空的线性表L。
    ListEmpty(L);           判断线性表是否为空,为空返回true,反之返回false。
    ClearLIst(*L);          清空线性表中所有元素。
    GetElem(L,i,*e);        得到线性表中第i位置的元素返回给e。
    LocateElem(L,e);        判断线性表中是否存在对应元素,查找成功返回对应序号,反之返回失败。
    ListInsert(*L,i,e);     在线性表第i个位置插入元素,并用e返回值。
    ListDelete(*L,i,*e);    删除第i个位置的元素,并用e返回其值。
    ListLength(L);          返回线性表元素个数。


在本书中,线性表元素从1开始,数组从0开始;因此,下图需要好好理解,尤其是在插入、删除操作时,很有必要搞清楚循环的初值和条件。


image.png

#include<stdio.h>
#define OK 1
#define ERROR 0
#define MAXSIZE 20
typedef int status;  // Status是函数的类型,其值是函数结果状态代码,如OK等
typedef int elemtype; //定义线性表元素的数据类型,便于后期修改操作
typedef struct
{
  elemtype data[MAXSIZE];  //开辟一段空间(占座)
  int length;     //当前线性表的长度,在初始化函数中确定大小
}Sqlist;
//初始化线性表,建立一个空的线性表
status InitList(Sqlist *L)  
{
  L->length = 0;
  return OK;
}
status ListEmpty(Sqlist L)
{
  if (L.length == 0)
  return true;
  else
  return false;
}
status ClearList(Sqlist *L)
{
  L->length = 0;
  return OK;
}
/*得到线性表中第i个元素并通过e返回,这里是传入一个地址进去接收得到的值。
注意事项:
1.若线性表为空,返回error
2.若i不在当前线性表长度范围内,返回error
3.在范围内时,注意线性表的元素位置,与数组位置的差值*/
status GetElem(Sqlist L, int i, int *e)
{
  if (L.length == 0||i<1||i>L.length)
  {
  return ERROR;
  }
  //这一步可以省略下面的if语句,因为if语句顺序执行到这里,只有(<=)这种情况未考虑
  //if (i <= L.length)
  //{
  *e = L.data[i - 1];
  //}
  return OK;
}
//查找线性表内是否存在对应元素
status LocateElem(Sqlist L,int e)
{
  if (L.length == 0)
  return ERROR;
  //注意这里的循环条件
  for (int i = 0; i < L.length; i++)
  {
  if (L.data[i] == e)
    return i;
  }
  return ERROR;
}
/*插入元素条件:
1.已达到最大容量的线性表不可插入
2.插入的位置不合理也不可插入
注意:
数组与线性表之间下标的关系
插入元素后,线性表长度发生变化,记得+1*/
status ListInsert(Sqlist *L, int i,int e)
{
  int k;
  if (L->length == MAXSIZE || i<1 || i>MAXSIZE)
  return ERROR;
  if (i >= 1 && i <= L->length)
  {
  for (k = L->length; k >= i; k--)
  {
    L->data[k] = L->data[k - 1];
  }
  }
  //如果线性表没有满,且插入元素位置在当前长度与最大容量之间,可直接插入
  L->data[i-1] = e;
  L->length++;
  return OK;
}
/*删除元素并通过地址返回被删除元素的值
条件:1、表是否为空,是否在线性表中
删除元素后,长度-1*/
status ListDelete(Sqlist *L, int i, int *e)
{
  if (L->length == 0||i<1||i>L->length)
  return ERROR;
  //注意这里的循环次数
  for (int k = i-1; k < L->length-1; k++)
  {
  L->data[k] = L->data[k + 1];
  }
  L->length--;
  return OK;
}
status ListLength(Sqlist L)
{
  return L.length;
}
/*求并集:将所有在线性表Lb中但不在La中的元素插入到La中*/
void UnionList(Sqlist *La,Sqlist Lb)
{
  int La_len, Lb_len;
  La_len = ListLength(*La);
  Lb_len = ListLength(Lb);
  for (int i = 1; i <= Lb_len; i++)
  {
  int e;
  GetElem(Lb, i, &e);
  if (!LocateElem(*La, e))  
  {
    ListInsert(La,++La_len,e);
  }
  }
}
/*当然上面的初始化线性表操作时,可以直接附初值。
我在调试的时候,存在的问题:
1、判断语句中,“==”与赋值号书写错误
2、循环时,初始条件和判断条件的设置,+-1,相差很大。*/


PS:

就先写到这里吧,后面想到要补充得,再回头来改呗!

相关实践学习
SLB负载均衡实践
本场景通过使用阿里云负载均衡 SLB 以及对负载均衡 SLB 后端服务器 ECS 的权重进行修改,快速解决服务器响应速度慢的问题
负载均衡入门与产品使用指南
负载均衡(Server Load Balancer)是对多台云服务器进行流量分发的负载均衡服务,可以通过流量分发扩展应用系统对外的服务能力,通过消除单点故障提升应用系统的可用性。 本课程主要介绍负载均衡的相关技术以及阿里云负载均衡产品的使用方法。
目录
相关文章
|
5天前
|
存储 Java 开发者
Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效
【10月更文挑战第19天】在软件开发中,随着项目复杂度的增加,数据结构的组织和管理变得至关重要。Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,帮助开发者告别混乱,提升代码质量。
14 1
|
20天前
|
存储 Java
数据结构第二篇【关于java线性表(顺序表)的基本操作】
数据结构第二篇【关于java线性表(顺序表)的基本操作】
27 6
|
15天前
|
存储 算法 索引
HashMap底层数据结构及其增put删remove查get方法的代码实现原理
HashMap 是基于数组 + 链表 + 红黑树实现的高效键值对存储结构。默认初始容量为16,负载因子为0.75。当存储元素超过容量 * 负载因子时,会进行扩容。HashMap 使用哈希算法计算键的索引位置,通过链表或红黑树解决哈希冲突,确保高效存取。插入、获取和删除操作的时间复杂度接近 O(1)。
25 0
|
18天前
探索顺序结构:栈的实现方式
探索顺序结构:栈的实现方式
|
20天前
05(数据结构考研)树相关操作代码
05(数据结构考研)树相关操作代码
26 0
|
20天前
|
算法
04(数据结构考研)串相关操作代码
04(数据结构考研)串相关操作代码
16 0
|
18天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
18 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
18天前
初步认识栈和队列
初步认识栈和队列
44 10
|
12天前
数据结构(栈与列队)
数据结构(栈与列队)
13 1
|
18天前
|
算法
数据结构与算法二:栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式
这篇文章讲解了栈的基本概念及其应用,并详细介绍了中缀表达式转换为后缀表达式的算法和实现步骤。
33 3