数据结构---线性表理解（一）

一、线性表

1、线性表的定义与特点

由N个数据特性相同的元素构成的有限序列，称为线性表。
n个数据元素的有限序列，其中n个数据是相同数据类型的。

类似于数组，但是区别于数组，但是功能高于数组。

可以是整形、Double、结构体数据类型（但是结构体里面的数据可以不一样）、

存在唯一的一个被称作“第一个”的数据元素:

存在唯一的一个被称作“最后一个’的数据元素;

除第一个元素外，结构中的每个数据元素均只有一个前驱;

除最后一个元素外，结构中的每个数据元素均只有一个后继。

前驱、后继

对于赋值字符串一定要是用：strcpy函数。

strcpy(a, "给字符串复制的要求")
 

其实在这个里面，可以将ISBN、书名、定价给他弄成一个结构体，这样多个结构体放在一起就可以组成一个线性表，那么通过函数就可以实现左边的一些要求。这就是利用线性表去实现相应的业务逻辑与功能。 这个里面或者是一个王者荣耀里面的一个英雄。总之来说有点类似于面向对象的编程，

无外乎实现增删改查四件事。

数组和链表最大的区别是数组查询快，链表增删快，所以实际需要根据需求选择数据结构；

顺序表是线性表的一种

用一组连续的内存单元依次存储线性表的各个元素，也就是说，逻辑上相邻的元素，实际的物理存储空间也是连续的。

顺序表需要通过数组实现，也就是借用数组的外壳用来装线性表，

存储结构

typedef int WRITEDATA;
typedef int READDATA;

可以int起多个别名，举一反三。

解释一下为什么给int起一个别名，假设这是一个我需要读很多个传感器数据，目前我只想读取的是整数传感器数据，然后又有很多个传感器数据包括温度、湿度、距离等，我就可以使用这个别名创建很多个对应的数组类型或者是变量等

READDATA Tenp[20]
READDATA Distance[50]

这两个数组都是int类型，但是突然有一天我传感器换成精度很高的了，这个时候我需要Double或者是我资源不够了，我需要将这些int类型变为char类型的，那么如果我没有使用typedef这个关键字直接使用的int，那么我就要每个的去改变对应数组的变量类型，但是我现在使用了这个别名，就可以直接修改这个READDATA这个别名，就相当于是直接修改了Temp[]、Distance[]数组数据类型。

顺序表初始化

#define MAXSIZE 100

typedef int ElemType;

typedef struct{
	ElemType data[MAXSIZE];
	int length;  /* 表示的需要存进去多少个数据 */
}SeqList;

void initList(SeqList *L)
{
	L->length = 0;
}

这个函数表示我们需要传输一个SeqList类型的指针，这个地方怎么理解呐，原本我们是创建了一个结构体，然后命名为SeqList，那么其实编译器就认为这个结构体需要通过SeqList就能找到，相当于是一个标识符，但是我们使用了typedef关键字，就说明这个地方是可以重命名的，就把这个SeqList作为了一种结构体类型，因此就认为我们需要传输的一种SeqList类型的指针（因为这个地方定义了这个结构体类型需要的内存空间，如果不是这个类型的，那编译器怎么知道，它需要申请多少内存空间。）

一般添加都是在尾部添加元素，毕竟是用数组的外壳装的。

int appendElem(SeqList *L, ElemType e)
{
	if(L->length >= MAXSIZE)
	{
		printf("顺序表已满\n");
		return 0;
	}
	else{}
	L->data[L ->length] = e;
	length++; 
	return 1;
}


L ->length  等价于 (*L).Length

• ​**L->length​：这是结构体指针访问成员的标准简化写法**，-> 运算符专门用于指针访问结构体成员。
• ​**(*L).length**​：先对指针 L 解引用（*L 得到结构体变量），再通过 . 运算符访问成员 length。
• ​结论​：两者在功能上完全等价，最终都访问指针 L 指向的结构体中的 length 成员

在开发过程中，一定要建立敏感的边界条件，最大或最小不然就会很容易造成溢出的风险，或者是出现Bug的错误。保证代码的稳定性的前提前在保证鲁棒性，以及可扩展性，毕竟产品的稳定最重要。

另外再使用数组的时候一定要注意 0 这个位置，不要忽略。因为我们可能习惯性的会使用 1 。

void listElem(SeqList *L)
{
	for(int i = 0; i < L->length; i++)
	{
		printf("%d",L->data[i]);
	}
	printf("\n);
}

顺序表插入元素

int insert(SeqList *L, int pos, ElemType e)
{
	if(pos < L->length)
	{
		for(int i = L->length - 1; i > pos - 1; i--)
		{
			L->data[i+1] = L->data[i]
		}
		L->data[pos-1] = e;
		L->length++;
	}
	return 1;
}

需要说明的是在数据结构中我们向某个位置插入数据，其实是从1开始数的，这个地方一定要牢记，相当于是约定俗成的东西。

顺序表插入数据的最好时间复杂度是?

0(1) 相当于是只插入了最后一个位置。

如果是在第一个位置插入，那就是所有的数据都要向后挪动。
效率很低

顺序表删除元素

顺序表查找数据

顺序表动态分配内存地址初始化

栈内存不可控

堆内存是可控的

typedef struct{

    ElemType data[MAXSIZE];

    int length;

}SeqList;


SeqList* initList()

{
    SeqList *L = (SeqList*)malloc(sizeof(SeqList));

    L->data = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);

    L->length = 0;

    return L;

}

首先需要分配顺序表结构体内存，

接着我需要开辟

这是在堆内存中，

    //声明一个线性表并初始化   
    SeqList *list = initList();
    appendElem(list, 88);

这是在栈内存中，

    SeqList list;
    appendElem(&list, 88);

栈​：编译器自动管理，存储局部变量（如函数内定义的 int x）

![[Pasted image 20250612000011.png]]
​
data 存储地址值本身，其占用空间是隐式的（由系统自动管理）

*data 的值**​：即堆内存中动态数组的首地址（例如 0x7f8a3c000b60）

 ElemType data[MAXSIZE];
 

ElemType 只是决定了data里面的数据类型，

顺序表的精髓是物理地址连续

深入理解：为什么需要二级指针？

顺序表的结构设计体现了数据与元信息分离的思想：

• ​**SeqList 结构体**​ 仅存储“描述信息”（长度、容量、数据区指针）

• 数据区​ 独立存储在堆的另一区域，通过指针链接。指的就是data实际区域。

• 元信息大小固定（如 sizeof(SeqList) 约12-24字节），便于传递。

• 数据区可独立扩容而不影响结构体地址

如果我们需要知道data数据中的值，在编译器实际的运行中，其实是先找到data存储的首地址，然后在通过首地址进行地址便宜，最后指向我们想要取出的内存里面存储的值。

这个地方其实就是二级指针的嵌套使用。很好的实例。
使用顺序表结构体。

访问数据​：L->data[i] 通过首地址偏移 i * sizeof(int) 访问对应元素

为什么需要两次分配？​*

(1) ​职责分离原则

• ​关键点​：结构体本身不存储元素，只记录元素在哪里、有多少。

(2) ​连续存储的强制要求

顺序表的精髓是物理地址连续​（实现O(1)随机访问）。而：

• 结构体分配的内存大小固定（无法存储可变长数组）
• 数据区需要独立的大块连续内存（malloc 保证连续性）

(3) ​动态扩容的灵活性

若数据区与结构体绑定：

• 扩容需整体复制结构体+数据 → 效率极低
  分离后：
• 扩容只需 realloc(L->data) → 原结构体地址不变，
• 方便操作。

关于结构体的引申，是不是可以理解为结构体不会存储数据？

一、普通结构体：直接存储元素

当结构体成员定义为基本类型或固定数组时，结构体内存中直接存储元素数据。
​示例​：

struct Student {
    int id;         // 直接存储整型元素（4字节）
    char name[20];  // 直接存储字符数组（20字节）
    float score;    // 直接存储浮点数（4字节）
};

• ​内存布局​：

• ​特点​：

  • 元素物理存储在结构体内部的内存空间。
  • 总大小 = 各成员大小之和 + 内存对齐填充字节（如有）

二、动态数据结构的结构体：间接管理元素*

在动态顺序表、链表等结构中，结构体通过指针间接管理外部存储的元素，自身不存元素数据。
​示例（动态顺序表）​​：

typedef struct {
    int *data;      // 指针：仅存储堆内存首地址（4/8字节）
    int size;       // 计数器：存储元素个数（4字节）
    int capacity;   // 容量：最大元素数量（4字节）
} SeqList;

• ​内存布局​：

• ​特点​：

  • data 成员仅存储外部数据区的首地址​（非元素本身）。
  • 元素存储在独立的堆内存中，结构体通过指针访问。
  • 优势：支持动态扩容（realloc）

三、关键对比总结

四、为什么动态结构体不直接存储元素？

1. ​连续存储要求​：顺序表需物理地址连续，结构体大小固定无法容纳动态数组。
2. ​扩容效率​：
   • 若元素存在结构体内，扩容需复制整个结构体（低效）。
   • 分离存储后，只需调整数据区指针（realloc）。
3. ​内存灵活性​：
   • 结构体体积小（仅元数据），传递效率高；
   • 数据区可独立分配释放。

typedef struct{

    ElemType *data;

    int length;

    int capacity;

}SeqList;


可以搞成一个动态的data，按需分配空间。

2、线性表的顺序表示与实现

线性表还是具有一定的不方便，并且删除和增加需要依次挪动。

3、线性表的链式表示与实现

待续

4、线性表的应用

待续

文章源码获取方式：
如果您对本文的源码感兴趣，欢迎在评论区留下您的邮箱地址。我会在空闲时间整理相关代码，并通过邮件发送给您。由于个人时间有限，发送可能会有一定延迟，请您耐心等待。同时，建议您在评论时注明具体的需求或问题，以便我更好地为您提供针对性的帮助。

【版权声明】
本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议。这意味着您可以自由地共享（复制、分发）和改编（修改、转换）本文内容，但必须遵守以下条件：
署名：您必须注明原作者（即本文博主）的姓名，并提供指向原文的链接。
相同方式共享：如果您基于本文创作了新的内容，必须使用相同的 CC 4.0 BY-SA 协议进行发布。

感谢您的理解与支持！如果您有任何疑问或需要进一步协助，请随时在评论区留言。