一、 线性表
1. 线性表的基础知识
1.1 线性表的定义
线性表是具有相同数据类型的n(n>0)个数据元素的有限序列。
若用L命名，表示：L=(a1,a2,a3,…,ai-1,ai,ai+1,…,an)
1.2 线性表的逻辑特性和特点
逻辑特性
- a1：唯一的表头元素
- a2：唯一的表尾元素
- 除去a1：每个元素有且仅有一个直接前驱a(i-1)
- 除去an：每个元素有且仅有一个直接后继a(i+1)
特点
- n = 0：空表
- 表中元素有限个
- 表中元素具有逻辑上的顺序性，各个元素有先后次序
- 表中元素都是数据元素，每一个元素都是单个元素
- 表中元素的数据类型都相同
- 表中各个元素占用相同大小的存储空间
- 表中元素具有抽象性
1.3 线性表的存储结构
顺序存储结构：顺序表
链式存储结构：链表
1.4 顺序存储与链式存储的比较
顺序表
- 可以随机访问
- 占用存储空间连续
- 顺序表的插删，需要移动多个元素
链表
- 只能顺序访问
- 占用额外的存储空间存储元素间的关系，空间利用率更低
- 存储空间不一定连续
- 链表的插删不需要移动多个元素
2. 顺序表
2.1 顺序表的定义
线性表的顺序存储叫顺序表
2.2 顺序表的特点
- 把线性表中所有元素按照逻辑顺序，依次存储到从指定位置开始的一块连续存储空间
- 逻辑相邻的两个元素物理也相邻
- 第i+1个元素的存储位置紧接在第i个元素的存储位置后面
- 顺序表可以实现随机存取
2.3 顺序表的顺序存储类型描述
一维数组静态分配
- 数组的大小空间已经固定
- 空间满时，再加入新数据会导致溢出
#include "stdio.h"
#define MaxSize 50 //线性表的最大长度
typedef int ElemType;
typedef struct
{
ElemType data[MaxSize]; //顺序表的元素
int length; //顺序表当前的长度
}SqList; //使用typedef重新定义的顺序表的类型
一维数组动态分配
- 空间满时，可以开辟另外一块更大的空间，达到扩充目的
- 依旧是一次性选择一块大的空间，只不过可以在程序运行时动态指定空间大小
#include "stdio.h"
#include "malloc.h"
typedef int ElemType;
#define MAXSIZE 100 //动态数组的最大容量
typedef struct
{
ElemType *data; //动态分配数组的指针
int length; //顺序表当前长度
}SqList; //使用typedef重新定义的顺序表的类型
//动态分配空间
L->data=(int *)malloc(MAXSIZE*sizeof(int));
2.4 顺序表上基本操作
2.4.1 插入操作
实现思路
1. 在顺序表L的第i个（1<=i<=L.length+1）个位置插入新元素e
2. 如果i的输入不合法，则返回0，表示插入失败
3. 若i的输入合法，顺序表的第i个元素以及其后的所有元素右移一个版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/180248.html
