Ds2.线性表
一.线性表的定义和基本操作
1.线性表的定义
线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为
相同:每个数据元素所占空间一样大
有限序列:有次序
几个概念：
$a_i$是线性表中的“第i个”元素线性表中的位序
注意:位序从1开始 数组下标从0开始
a1是表头元素；an是表尾元素。
除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅 有一个直接后继
2.线性表的特点
- 表中元素的个数有限。
- 表中元素具有逻辑上的顺序性，表中元素有其先后次序。
- 表中元素都是数据元素，每个元素都是单个元素。
- 表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间
- 表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。
注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面的概念，因此不要将其混滑。
3.线性表的基本操作
3.1.基本操作
InitList(&L):初始化表。构造一个空的线性表,分配内存空间。DestroyList(&L):销毁操作。销毁线性表，并释放线性表L所占用的内存空间
ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素。GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。
其他常用操作
Length(L):求表长。返回线性表L的长度，即工中数据元素的个数。PrintList(L):输出操作。按前后顺序输出线性表L的所有元素值。Empty(L):判空操作。若工为空表，则返回true,否则返回false。
Tips:
①对数据的操作（记忆思路） —— 创销、增删改查 ②C语言函数的定义 —— <返回值类型> 函数名 (<参数1类型> 参数1，<参数2类型> 参数2，……) ③实际开发中，可根据实际需求定义其他的基本操作 ④函数名和参数的形式、命名都可改变（Reference：严蔚敏版《数据结构》） ⑤什么时候要传入引用“&” —— 对参数的修改结果需要“带回来”
Summary:
习题
选择
1.线性表是具有n个（C)的有限序列.A.数据表B.字符C.数据元素D.数据项
线性表是由具有相同数据类型的有限数据元素组成的，数据元素是由数据项组成的。
2.以下（B)是一个线性表。A.由n个实数组成的集合B.由100个字符组成的序列C.所有整数组成的序列D.邻接表
线性表定义的要求为：相同数据类型、有限序列。选项C的元素个数是无穷个，错误：选项A集合中的元素没有前后驱关系，错误；选项D属于存储结构，线性表是一种逻辑结构，不要将二者混为一谈。只有选项B符合线性表定义的要求。
3.在线性表中，除开始元素外，每个元素（A)。A.只有唯一的前趋元素B.只有唯一的后继元素C.有多个前趋元素D.有多个后继元素
线性表中除最后一个(或第一个)元素外，每个元素都只有一个后继（或前驱）元素。
二.顺序表
优点：可随机存取，存储密度高
缺点：要求大片连续空间，改变容量不方便
1.定义
线性表的顺序存储又称顺序表。
用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
typedefstruct {
intnum; //号数
intpeople; //人数
} Customer;
2.顺序表的实现
2.1静态分配
#define MaxSize 10 //定义最大长度
typedefstruct{
ElemTypedata[MaxSize]; //用静态的“数组”存放数据元素
intlength; //顺序表的当前长度
}SqList; //顺序表的类型定义（静态分配方式）
#include <stdio.h>
#define MaxSize 10 //定义最大长度
typedefstruct{
intdata[MaxSize]; //用静态的"数组"存放数据元素
intlength; //顺序表当前长度
}SqList; //顺序表的类型定义
//基本操作--初始化一个顺序表
voidInitList(SqList&L){
for(inti=0;i<MaxSize;i++)
L.data[i] =0; //将所有元素设置为默认初始值
L.length=0; //顺序表初始长度为0
}
intmain(){
SqListL; //声明一个顺序表
InitList(L); //初始化顺序表
//.....未完待续,后续操作
return0;
}
/*不初始化数据元素,内存不刷0*/
#include <stdio.h>
#define MaxSize 10 //定义最大长度
typedefstruct{
intdata[MaxSize]; //用静态的"数组"存放数据元素
intlength; //顺序表当前长度
}SqList; //顺序表的类型定义
//基本操作--初始化一个顺序表
voidInitList(SqList&L){
L.length=0; //顺序表初始长度为0
}
intmain(){
SqListL; //声明一个顺序表
InitList(L); //初始化顺序表
//尝试"违规"打印整个 data 数组
for(inti=0; i<MaxSize; i++)
printf("data[%d]=%d\n",i,L.data[i]);
return0;
}
违规打印后会出现数据错乱的现象
2.2动态分配
#define Initsize 10 //顺序表的初始长度
typedefstruct{
ElemType*data; //指示动态分配数组的指针
intMaxSize; //顺序表的最大容量
intlength; //顺序表的当前长度
}SeqList; //顺序表的类型定义（动态分配方式）
在内存开辟了一整片连续的空间
#include<stdlib.h>
#define Initsize 10 //顺序表的初始长度
typedefstruct{
ElemType*data; //指示动态分配数组的指针
intMaxSize; //顺序表的最大容量
intlength; //顺序表的当前长度
}SeqList;
voidInitList(SeqList&L){
//用malloc 函数申请一片连续的存储空间
L.data= (int*)malloc(InitSize*sizeof(int));
L.length=0;
L.MaxSize=InitSize;
}
//增加动态数组的长度
voidIncreaseSize(SeqList&L, intlen){
int*p=L.data;
L.data= (int*)malloc((L.MaxSize+len)*sizeof(int));
for(inti=0;i<L.length;i++){
L.data[i] =p[i]; //将数据复制到新区域
}
L.MaxSize=L.MaxSize+len; //数组最大长度增加 len
free(p); //释放原来内存空间
}
intmain(){
SeqListL; //声明一个顺序表
InitList(L); //初始化顺序表
//...往顺序表中随便插入几个元素...
IncreaseSize(L,5);
return0;
}
3.顺序表的特点
①随机访问，即可以在 O(1) 时间内找到第 i 个元素。
代码实现：data[i-1]; 静态分配、动态分配都一样
②存储密度高，每个节点只存储数据元素
③拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）
④插入、删除操作不方便，需要移动大量元素
Summary:
