【第二章】线性表
本章结构：
2.1 线性表的定义和基本操作¶
2.1.1 线性表的定义¶
定义：具有相同数据类型的 \(n\) 个数据元素的有限序列。 - \(n\) 为表长，\(n\geq0\)。\(n=0\) 时为空表。 - 用 \(L\) 表示为： - \(L=(a_{1},a_{2},\dots,a_{i},a_{i+1},\dots,a_{n})\) - \(a_{1}\)：第一个数据元素，也叫表头元素。 - \(a_{n}\)：最后一个数据元素，也叫表尾元素。 - 逻辑特性： - 除第一个元素外，每个元素有且仅有一个直接前驱。 - 除最后一个元素外，每个元素有且仅有一个直接后继。 - 特点： - 表中元素的个数有限。 - 表中元素具有逻辑上顺序性，表中元素有先后次序。 - 表中都是数据元素，每个元素都是单个元素。 - 表中元素的数据类型都相同，也就是说每个元素所占据的存储空间相同。 - 表中元素具有抽象性，只讨论元素之间的逻辑关系，不关心元素内容。
注意区分顺序表和线性表，线性表是一种高度抽象的逻辑结构，而顺序表是存储结构。顺序表和链表在同一层次。
2.1.2 线性表的基本操作¶
基本操作：指一个数据结构最核心、最基本的操作。 其他复杂操作：可调用基本操作来实现。
线性表的主要操作有：
- InitList(&L)：初始化表。
- 构造一个空线性表。
- Length(L)：求表长。
- 返回线性表的长度 \(L\)，即表中的数据个数。
- LocateElem(L, e)：按值查找操作。
- 在表 \(L\) 中查找具有给定关键字值的元素。
- GetElem(L, i)：按位查找操作。
- 按位查找操作。获取表 \(L\) 中第 \(i\) 个位置的元素的值。
- ListInsert(&L, i, e)：插入操作。
- 在表 \(L\) 中的第 \(i\) 个位置上插入指定元素 \(e\)。
- ListDelete(&L, i, &e)：删除操作。
- 删除表 \(L\) 中第 \(i\) 个位置的元素，并用 \(e\) 返回删除元素的值。
- PrintList(L)：输出操作。
- 按前后顺序输出线性表 \(L\) 中的所有元素的值。
- Empty(L)：判空操作。
- 若 \(L\) 为空表返回 true，否则返回 false。
- DestroyList(&L)：销毁操作。
- 销毁线性表，释放线性表 \(L\) 所占用的内存空间。
1️⃣基本操作的实现取决于存储结构，存储结构不同算法实现也不同。2️⃣
&为 C++中的引用调用。
2.2 线性表的顺序表示¶
从字面上就能理解，顺序表是有顺序的线性表，约束条件更强。
顺序表：线性表的顺序存储。 特点： - 用地址连续的存储单元依次存储线性表中的数据元素。 - 逻辑相邻的两个元素在物理位置上也相邻。 - 逻辑顺序与物理顺序保持一致。 - 物理存储位置与位序成正比，故可以实现随机存取。
优点： - 随机访问，通过首地址+元素序号 \(O(1)\) 时间内找到指定元素。 - 元素密度高。
缺点： - 插入和删除耗时，可能需要移动大量元素。 - 需要连续空间才能存储，不够灵活。
随机存取就是不需要遍历线性表，直接给出一个位序就可以直接存入。
位序：称 \(i\) 为元素 \(a_{i}\) 在顺序表中的位序。
顺序表中元素的位序从
1开始，而数组的下标是从0开始的。
静态分配顺序表的存储结构描述：
#define MaxSize 50 // 定义线性表最大长度
typedef struct {
ElemType data[MaxSize]; // 顺序表的元素
int length; // 顺序表的当前长度
}SqList; // 顺序表的类型定义
// C语言中分配语句为
L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);
动态分配顺序表的存储结构描述：
#define MaxSize 100 // 表长度初始定义
typedef struct {
ElemType *data; // 用来动态分配数组的指针
int MaxSize,length; // 数组最大容量和当前个数
}SqList; // 动态分配数组顺序表的类型定义
// C++中动态分配语句为
L.data = new ElemType[InitSize];
typedef
用法类似于定义一个类。
#include <stdio.h>
#include <string.h>
typedef struct Books
{
char title[50];
char author[50];
char subject[100];
int book_id;
} Book;
int main( )
{
Book book;
strcpy( book.title, "C 教程");
strcpy( book.author, "Runoob");
strcpy( book.subject, "编程语言");
book.book_id = 12345;
printf( "书标题 : %s\n", book.title);
printf( "书作者 : %s\n", book.author);
printf( "书类目 : %s\n", book.subject);
printf( "书 ID : %d\n", book.book_id);
return 0;
}
2.3 线性表的链式表示¶
2.3.1 顺序表的初始化¶
//
// main.c
// DataStructure
//
// Created by sy on 2025/9/20.
//
#include <stdio.h>
#include <stdlib.h>
#define InitSize 100
typedef struct {
int *data;
int MaxSize, length;
} SqList;
SqList a;
//初始化 SqList指针指所指向的顺序表
void InitList(SqList *L) {
L->data=(int *)malloc(InitSize*sizeof(int)); // 分配内存空间
L->length=0; // 顺序表初始长度为0
L->MaxSize=InitSize; // 初始容量
}
void run(void) {
SqList sq;
InitList(&sq);
printf("length: %d", sq.length);
}
int main(int argc, const char * argv[]) {
// insert code here...
run();
putchar('\n');
return 0;
}
这是根据 wd 书写的一段顺序表的初始化 C 语言代码。
要点在于
malloc()函数的使用方法。