数据结构第五课

线性表的顺序存储结构

线性表的顺序存储——顺序表

2. 顺序表的核心性质

• 线性表本质：具有相同数据类型的 n (n≥0) 个数据元素的有限序列。
• 顺序存储特点：用一组地址连续的存储单元，依次存储线性表的数据元素。
• 逻辑与物理的对应：逻辑上相邻的元素，物理存储位置也相邻，元素间的关系由存储单元的邻接关系体现。
  —————————————————————————————————————————————————————————————————

练习

线性表 L=(a1,a2,…,an)，下列说法正确的是（）
A. 每个元素都有一个直接前驱和一个直接后继
B. 表中诸元素的排列必须是由小到大或由大到小
C. 除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继

正确答案：C

—————————————————————————————————————————————————————————————————

3. 顺序存储方法：静态分配

用一组地址连续的存储单元依次存放线性表的数据元素，可用数组 V[n]来实现。

地址计算公式：
LOC(ai) = LOC(a1) + (i-1) × m
m 为每个元素占用的存储单元数

逻辑结构 → 存储结构（直接映射）

• 逻辑结构：(a1, a2, …, ai, …, an)
• 存储下标：0 1 … i-1 … n-1
• 存储结构：data[0] data[1] … data[i-1] … data[n-1] + length 属性
  > 位序从1开始，数组下标从0开始，二者差1
  —————————————————————————————————————————————————————————————————

顺序表类型定义（静态分配）（背！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！）

#define MaxSize 50 // 最大元素个数，这里假设ElemType为char类型
typedef struct {
ElemType data[MaxSize];
int length; // 顺序表当前长度
} SqList;

• data：存放顺序线性表的元素
• length：存放线性表的实际长度
  说明：注意逻辑位序和物理位序相差1。
  静态分配缺点：数组大小固定，存满后无法再存入，只能覆盖；若声明过大空间会造成浪费。

—————————————————————————————————————————————————————————————————

顺序表的实现：动态分配（类型定义）（背！！！！！！！！！！！！！！！！！！！！！！！！）

Q：如果“数组”存满了怎么办？
A：顺序表的表长刚开始确定后就无法更改（存储空间是静态的）
思考：如果刚开始就声明一个很大的内存空间呢？存在什么问题？

#define InitSize 10 // 顺序表的初始长度
typedef struct {
ElemType *data; // 指向动态分配数组的指针
int length; // 顺序表的当前长度
int MaxSize; // 顺序表的最大容量
} SqList;//顺序表的类型定义（动态分配方式）

————————————————————————
动态申请和释放内存空间

malloc,free函数

L.data = (ElemType *) malloc(sizeof(ElemType) * InitSize);

说明：

• malloc 函数返回一个通用指针，需要强制转型为你定义的数据元素类型指针
• malloc 函数的参数，指明要分配多大的连续内存空间
• 对应头文件： #include <stdlib.h>
• 释放内存用 free 函数

#include <stdlib.h> // malloc、free函数的头文件
#define InitSize 10 // 默认的最大长度

typedef struct{
int *data; // 指示动态分配数组的指针
int MaxSize; // 顺序表的最大容量
int length; // 顺序表的当前长度
}SeqList;

// 初始化顺序表
void InitList(SeqList &L){
// 用 malloc 函数申请一片连续的存储空间
L.data = (int *) malloc(InitSize * sizeof(int));
L.length = 0;
L.MaxSize = InitSize;
}

// 增加动态数组的长度
void IncreaseSize(SeqList &L, int len){
int *p = L.data;
// 申请一块更大的新空间
L.data = (int *)malloc((L.MaxSize + len) * sizeof(int));
// 将原数据复制到新区域
for(int i = 0; i < L.length; i++){
L.data[i] = p[i];
}
L.MaxSize = L.MaxSize + len; // 顺序表最大长度增加 len
free(p); // 释放原来的内存空间
}

int main() {
SeqList L; // 声明一个顺序表
InitList(L); // 初始化顺序表
// …往顺序表中随便插入几个元素…
IncreaseSize(L, 5);
return 0;
}

注： realloc 函数也可实现扩容，但建议初学者使用 malloc 和 free ，更能理解背后过程
缺点：扩容需要复制全部数据，时间开销大

地址计算练习

顺序表运算的实现
顺序表基本运算算法

（1）初始化线性表 InitList(&L)

构造一个空的线性表L，只需将length成员设置为0即可。

void InitList(SqList &L)
{
L.length = 0;
}

（2）销毁线性表 DestroyList(&L)

释放线性表L占用的内存空间。

void DestroyList(SqList &L)
{
free(L); //L是顺序表
// free(L)释放L所指向的空间
}

（3）判断是否为空表 ListEmpty(L)

返回一个值表示L是否为空表。若L为空表，则返回true，否则返回false。

bool ListEmpty(SqList L)
{
return (L.length == 0);
}

（4）求线性表的长度 ListLength(L)

返回顺序表L的长度，实际上只需返回length成员的值即可。

int ListLength(SqList L)
{
return (L.length);
}

（5）输出线性表 DispList(L)

当线性表L不为空时，顺序显示L中各元素的值。

void DispList(SqList L)
{
if (ListEmpty(L)) return;
for (int i = 0; i < L.length; i++)
printf("%c", L.data[i]);
printf("\\n");
}

（6）按位取元素 （求某个数据元素值）GetElem(L, i, &e)

返回L中i(1<=i<=ListLength(L))个元素的值，存放在e中（用 e 返回第 i (1≤i≤L.length) 个元素的值。）

bool GetElem(SqList L, int i, ElemType &e)
{
if (i < 1 || i > L.length) return false;
e = L.data[i–1]; // 时间复杂度O(1)
return true; // 体现顺序表**随机存取特性**
}

（7）按元素值查找 LocateElem(L, e)

顺序查找第一个值域与e相等的元素的逻辑位序。若这样的元素不存在，则返回值为0。（返回L中第一个值与e相等的元素的位序；不存在则返回0。）

int LocateElem(SqList L, ElemType e)
{
int i = 0;
while (i < L.length && L.data[i] != e)
i++;
if (i >= L.length) return 0;
else return i+1;
}

（8）（！！！！！！！！！！！！！！！！！！）插入数据元素 ListInsert(&L, i, e)
用存储位置的相邻来体现数据元素之间的逻辑关系
在第 i (1≤i≤L.length+1) 个位置之前插入新元素e。
操作原理：第i个及之后的元素全部后移一位，空出位置放入e，表长+1。
ListInsert(&L,i,e:插入操作。在表L中的第i个位置（位序）上插入指定元素e)

bool ListInsert(SqList &L, int i, ElemType e)
{
int j;
if (i < 1 || i > L.length+1) // 插入位置非法
return false;
if (L.length >= MaxSize) // 顺序表已满
return false;
// 从最后一个元素开始，i及之后元素后移
for (j = L.length; j >= i; j—)
L.data[j] = L.data[j–1];
L.data[i–1] = e; // 插入新元素
L.length++; // 表长加1
return true;
}

对于本算法来说，元素移动的次数不仅与表长L.length=n有关，而且与插入位置有关：
插入算法时间复杂度分析
– 最好情况：插入在表尾（i=n+1），移动0次，时间复杂度 O(1)
– 最坏情况：插入在表头（i=1），移动n次，时间复杂度 O(n)
– 平均情况：等概率插入下，平均移动次数为 n/2，时间复杂度 O(n)

平均移动次数推导：
长度为n的表共有 n+1 个可插入位置，在第i位插入需移动 n-i+1 个元素。
等概率下 pi=1/(n+1)，平均移动次数：E_ins = 1/(n+1) × Σ(i=1到n+1) (n-i+1) = n/2
因此插入算法的平均时间复杂度为O(n)

一、 单选题
考点 1：顺序表删除元素
题目： 在一个长度为n的顺序表中，删除表中第i（1≤i≤n）个元素需要移动（ ）个元素。

· ✅ n-i
· n-i+1
· n-i-1
· i

考点 2：顺序表时间复杂度
题目： 在n个结点的顺序表中，算法的时间复杂度O(1)的操作是（ ）。

· ✅ 访问第i个结点（1<=i<=n）和求第i个结点的直接前趋
· 在第i个结点后插入一个新结点(1<=i<=n)
· 删除第i个结点(1<=i<=n)
· 将n个结点从小到大排序

考点 3：线性表运算
题目： 在线性表的下列运算中，不改变数据元素之间结构关系的运算是

· 插入
· 删除
· 排序
· ✅ 定位

考点 4：表尾插入时间复杂度
题目： 在长度为n的顺序表的表尾插入一个新元素的时间复杂度为（ ）。

· O(n)
· ✅ O(1)
· O(n^2)
· O(log2n)

考点 5：顺序表的说法

题目： 以下关于顺序表的说法中正确的是
· 顺序表利用一维数组表示，因此顺序表与一维数组在结构上一致，它们可以通用
· 在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻
· ✅ 顺序表和一维数组一样，都可以按下标随机（或直接）访问，顺序表还可以从某一指定元素开始，向前或向后逐个元素顺序访问
· 在顺序表中每一个元素的类型不必相同

二、线性表的顺序存储结构（理论部分）

顺序表运算的实现

· 在长度为n的线性表中插入一个元素时共移动n-i+1个元素，其移动元素的平均次数为：n/2
· 在长度为n的线性表中删除一个元素时共移动n-i个元素，其移动元素的平均次数为：(n-1)/2

引用类型作形参的三点说明（重点）
（1）传递引用给函数与传递指针的效果是一样的，形参变化实参也发生变化。
（2）引用类型作形参，在内存中并没有产生实参的副本，它直接对实参操作；而一般变量作参数，形参与实参就占用不同的存储单元，所以形参变量的值是实参变量的副本。因此，当参数传递的数据较大时，用引用比用一般变量传递参数的时间和空间效率都好。
（3）指针参数虽然也能达到与使用引用的效果，但在被调函数中需要重复使用“指针变量名”的形式进行运算，这很容易产生错误且程序的阅读性较差；另一方面，在主调函数的调用点处，必须用变量的地址作为实参。

顺序表的算法实现:
· 顺序表的初始化
· 顺序表的取值
· 顺序表的查找
· 顺序表的插入
· 顺序表的删除

知识回顾与重要考点
· 线性表的基本操作
· 初始化
· 插入 ListInsert(&L, i, e) 需要传入元素e，插入位置i
· 删除 ListDelete(&L, i, &e)
· 查找 GetElem(L, i)
· 时间复杂度考量
· 分析代码：理解为什么有的参数要加“&”引用
· 算法分析：理解为什么要考虑平均情况，以及最坏情况？
· 代码重点
· 代码实现
· 本章任务
· 设计并实现基于线性表结构的图书信息管理系统，系统采用顺序表存储图书信息。（要求图书信息变量命名前加上学生姓的缩写，至少完成初始化、输出、查找、插入、删除功能）

三、 图书信息管理系统代码实现（C语言）

#include<stdio.h>
#include<stdlib.h>
#define maxsize 100
typedef struct{
int no;
char name[10];
int price;
}book;
typedef struct{
book data[maxsize];
int length;
}sqlist;

void initlist(sqlist *L)
{
L->length=0;
printf("初始化成功\\n");
}

void inputlist(sqlist *L)
{
int i,n;
printf("请输入图书的数量: ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("请输入第%d本图书的编号: ",i+1);
scanf("%d",&L->data[L.length].no);
printf("请输入第%d本图书的名称: ",i+1);
scanf("%s",L->data[L.length].name);
printf("请输入第%d本图书的单价: ",i+1);
scanf("%d",&L->data[L.length].price);
L->length++;
}
}

void outputlist(sqlist L)
{
int i;
printf("图书编号\\t图书名称\\t图书单价\\n");
for(i=0;i<L.length;i++)
{
printf("%d\\t%s\\t%d\\n",L.data[i].no,L.data[i].name,L.data[i].price);
}
}

int main()
{
sqlist L;
int choice;
initlist(&L);
while(1)
{
printf("\\n欢迎使用图书信息管理系统!\\n");
printf("1. 初始化\\n");
printf("2. 输入图书信息\\n");
printf("3. 输出图书信息\\n");
printf("4. 查找图书信息\\n");
printf("5. 插入图书信息\\n");
printf("6. 删除图书信息\\n");
printf("0. 退出\\n");
printf("请输入你的选择: ");
scanf("%d",&choice);
switch(choice)
{
case 1: initlist(&L); break;
// … 后续代码被截断
}
}
return 0;
}

欢迎使用图书信息管理系统!
1. 初始化
2. 输入图书信息
3. 输出图书信息
4. 查找图书信息
5. 插入图书信息
6. 删除图书信息
0. 退出
请输入你的选择: 1
初始化成功
请输入你的选择: 2
请输入图书的数量: 2
请输入第1本图书的编号: 1001
请输入第1本图书的名称: C语言
请输入第1本图书的单价: 45
请输入第2本图书的编号: 1002
请输入第2本图书的名称: 数据结构
请输入第2本图书的单价: 55
请输入你的选择: 3
图书编号图书名称图书单价
1001C语言45
1002数据结构55
请输入你的选择: 0