2.线性表的顺序表示
数据结构很重要！
数据结构很重要！！！
数据结构很重要！！！！
思考
1.线性表的顺序表示内容有哪些？（What）
2.为什么要学线性表的顺序表示? ? (Why)
3.如何更好的学习线性表的顺序表示? ? ？(How)
注：特别感谢青岛大学王卓老师
第2章 线性表.pdf
一.线性表的顺序表示内容有哪些？（What）
1.线性表的定义和特点
1.1线性表定义：
具有相同特性的数据元素，构成的一个有限序列。
1.2线性表的例子
1.相同特性（int,char.....）
2.线性关系
1.3线性表逻辑特征
线性表是一种典型的线性结构
2.案例引入
2.1案例1：一元多项式的运算
2.2案例2：稀疏多项式的运算
引申：如果存三项，你还按原来数组下标存，那么必定造成很大空间浪费。
稀疏多项式解决办法：
- 有下标i
- 系数a[i]（多项式值）
- 指数（多项式指数值）
把每一项系数和指数也存储起来，也都成为了一个线性表，只不过这个线性表，每一项为俩个数据项。
创建一个新数组C，分别从头遍历比较a和b的每一项。
指数相同：对应稀疏相加，其和不为零，则在C中增加一个新项
指数不相同：将指数较小的项复制到C中
问题：新数组多大合适呢？
解决：用链式存储，解决了空间复杂度
2.3案例3：图书信息管理系统
1.需要的功能：增删查改、排序、计数
2.解决办法：图书表抽象为线性表，用数组元素来存储图书
存储：1.顺序表 2.链式表
选择：比较俩种存储结构有什么区别，各有什么好处？
引申：（学生、教师、员工、库存、商品）管理系统
2.4总结
1.线性表中数据元素的类型可以为简单类型（多项式)，也可以为复杂类型（图书信息）。
2.找出：基本操作（增删查改）有很大相似性，不应为每个具体应用单独编写一个程序。
3.从具体应用中抽象出共性的逻辑结构和基本操作（抽象数据类型），然后实现其存储结构（存储数据元素及其关系）和基本结构（实现操作）。
3.线性表的类型定义
抽象数据类型线性表的定义如下：
下面是逻辑结构定义的运算，运算的功能是“做什么”。
1.基本操作
a.初始化、销毁、清空
b.判断是否为空、线性表长度
c.返回线性表L中第i个数据元素的值、返回元素e的位置（返回L中第一个与e满足compare（）数据元素的位序，若元素不存在返回值为0）。
d.返回e元素直接前趋的值，返回e元素直接后继的值
e.在i位置前插入元素e
d.删除i个元素，并用e返回其值，L的长度减一，遍历线性表。
"如何做”等实现细节，需要存储结构之后才考虑。
存储结构：
1.线性表顺序存储
2.线性表链式存储
4.线性表的顺序表示和实现
1.线性表的顺序表示
1.顺序存储定义：逻辑上相邻，物理上也相邻。
存储：元素、元素依次关系
第一个元素：起始位置，或基地址。
2.线性存储：存储位置连续
也可以计算出其他元素的位置
3.元素位置计算
L是一个存储单元的大小
前提：知道第一个元素位置，求第i个元素位置：
loc(ai)=loc(a1)+(i-1)*L
O(1)：知道基地址，每个数组中其中一个元素都可以计算出来，想找哪一个就找哪一个，所以不考虑数组中有多少元素。
4.顺序表优点
1.物理位置表示逻辑位置关系
2.任何元素均可随机存取（优点）
2.线性表的顺序实现
1.数据语言实现方法：
用高级语言已经实现的数据类型描述存储结构。
2.C语言中：
定义了数组的大小，那么不管你插入多少个元素，求出来的结果永远是你定义的数组大小。
如果你没有定义数组大小，那么算出来的就是你实际赋值的数组大小。
注：Java中数组长度根据，实际存储的长度
length表示：真实数组长度
3.多项式例子
4.图书表顺序存储结构类型定义
5.类C语言有关的操作
1.元素类型说明
2.数组静态/动态分配
3.C语言的内存动态分配
malloc(sizeof(ElemType)*MaxSize) : 分配空间大小
L.data：是基地址
free(p):释放指针p所指变量的存储空间
4.C++中内存动态分配
动态分配：int *p1=new int;
静态分配：int *p1=new int(10);
5.C++中的参数传递
传地址：实参地址传递给形参
6.传值方式
1.传实参值到形参
调用函数，是将实参的值传递给形参，最后形参的结果变化了，最后调用完形参就没有了，实参的值没有变。
实参值到形参
float a,b;
swap(a,b);
void swap（int m,int n）{
float temp;
temp=m;
m=n;
n=temp;
}
2.传实参地址到形参
float *p1,*p2;
p1=&a；p2=&b;
swap(p1,p2)
void swap(int *m,int *n){
float t;
t=*m;
*m=*n;
*n=t;
}
p1->a地址
p2->b地址
t=a地址内容
a地址内容=b地址内容
b地址内容=a地址内容
a、b地址值发生变化
函数调用结束，m、n形参地址值消失
3.形参变化不影响实参
float *p1,*p2;
p1=&a; p2=&b;
swap(p1,p2);
void swap(int *m,int *n){
float *t;
t=m;
m=n;
n=t;
}
7.传地址方式--数组名作参数
数组名传递，首元素地址传递整个数组
对形参数组怎么操作，其实就是对实参数组怎么操作
8.传地址方式--引用类型做参数
引用用的同一块空间：&j=i i发生改变，j的值也发生改变
对m、n的形参操作，其实就是对实参a、b的操作
比传指针、传数组操作简单。
通过引用变量，直接操作实参。
m是对a地址的引用，等同于a
n是对b地址的引用，等同于b
然后a,b进行直接交换
float a,b;
swap(a,b);
void swap(float &m,float &n){
float t;
t=m;
m=n;
n=t;
}
6.线性表的顺序存储表示
1.顺序表示意图
SqList *L 指针顺序表。
然后可以使用，L->elem
2.线性表的基本操作
3.操作算法中用到的预定义常量和类型
7.顺序表基本操作的实现
1.线性表L的初始化（参数用引用）
第二行：L.elem：表示首地址
如果内存小，可能分配不成功。
分配失败：存空值；分配成功：存地址
第三行：!（L.elem为空值) ：非0（为真），则分配失败。
2.销毁、清空线性表
销毁：释放存储空间（C++）
清空：线性表还在，但是里面没有元素
3.线性表长度、是否为空
4.顺序表的取值
i是[1-n]个
常量阶，复杂度都是：o(1)
只要不发生变化，都是常量阶。
随机存取，想要哪一个都可以。
5.按值查找（顺序表的查找）
while语句实现
6.顺序表的查找算法分析
7.平均查找值
每一个都会查找到，平均的情况：平均查找长度。
Pi=1/n
假设每个记录的查找概论相等：
ASL=(1+2+...+n)/n=(n+1)/2
8.插入算法
9.顺序表的删除
7.顺序表小结
1.线性表顺序存储特点
2.线性表的基本操作
3.顺序表的操作算法分析
空间复杂度：在原来位置上就可以操作。
4.顺序表优点
二.为什么要学线性表的顺序表示? ? (Why)
1.顺序线性表是什么？
具有相同特性的数据元素，构成的一个有限序列。
2.表需求（适用场景）
比如我们要存储非数值元素，可能是一张表。
那么此时，我就用数组来进行存储，操纵就是增删查改。
3.顺序线性表优点
顺序存储，查找速度快。
存储密度大。结点本身所占的存储量/结点结构所占的存储量。
4顺序线性表缺点
删除和插入，时间复杂度比较高。
三.如何学习好线性表的顺序表示
1.练习代码
1.顺序表类型定义 案例1：
每一个数据元素都是，俩部分组成。
typedef struct{ //多项式非零项的定义
float p; //系数
int e; //指数
} Polynomial;
用Polynomial这个类型，在定义一个数组，就可以存放多个数据元素了。
length：表示存放了多少元素。
typedef struct{
Polynomial *elem;
int length
}
数组静态
#define Maxsize 1000 //多项式可能达到的最大长度
typedef struct{
ElemType data[MaxSize]; //元素类型和数组大小都可以修改
int length;
}SqList;
动态分配
typedef struct{
ElemType *data; //得到的是基地址
int length;
}SqList;
SqList L;
L.data=(ElemType*)malloc(sizeof(ElemType)*MaxSize);
malloc（m）：开辟m字节长度的地址空间，并返回这段空间的首地址。
sizeof（x）：计算变量X(变量类型)的长度。
(ElemType*)：告诉800个字节要存字符还是整数。
free（p）:释放指针p所指变量的存储空间，彻底删除一个变量。
注：需要加载头文件：
2.顺序表类型定义 案例2：
#define MAXSIZE 10000
typedef struct{
char id[20];
char name[50];
int price;
}Book;
typedef struct{
Book *elem; //存储空间的基地址
int length; //图书个数
}SqList; //图书表的顺序存储结构类型为SqList
1.线性表初始化（参数引用）
Status InitList_Sq(SqList &L){ //构造一个空格的顺序表L
L.elem=new ElemType[MAXSIZE]; //为顺序表分配空间
if(!L.elem) exit(OVERFLOW) //存储分配失败
L.length=0; //空表长度为0
return ok;
}
2.销毁、清空线性表
销毁：释放存储空间（C++）
void DestroyList(SqList &L){
if(L.elem) delete L.elem ; //释放存储空间
}
清空：线性表还在，但是里面没有元素
void clearList(SqList &L){
L.length = 0;
}
3.线性表长度、是否为空
线性表长度:
int GetLength(SqList L){
return L.length;
}
线性表是否为空：
int GetLength(SqList L)
if(L.length==0) return 1; //返回1：OK
else return 0;
}
4.顺序表的取值
i是[1-n]个
常量阶，复杂度都是：o(1)
只要不发生变化，都是常量阶。
随机存取，想要哪一个都可以。
int GetElem(SqList L，int i，ElemType &e){
if(i<1||i>L.length) return ERROR; //判断i值是否合理，若不合理，返回ERROR
e=L.elem[i-1]; //第i-1的存储单元着第i个元素
return ok;
}
5.按值查找（顺序表的查找）
int locateElem(SqList L,ElemType e){
for(i=0;i
if(e==L.elem[i]) return i+1; //查找成功。返回序号
return 0; //查找失败，返回0
}
}
while语句实现
int LocateElem(SqList L,ElemType e){
int i=0;
while(i if(i return 0; } Status ListInsert_Sq(SqList &L,int i,ElemType e){ if(i<1||i>L.length+1) return ERROR; if(L.length==MAXSIZE) return ERROR; for(j=L.length-1;j>=i-1;j--){ L.elem[j+1]=L.elem[j]; //从最后一个元素开始后移一位，知道插入位置后移最后一次，完毕 L.elem[i-1] = e; L.length++; return ok; } } Status ListDelete_Sq(SqList &L，int i){ if((i<1)||i>L.length)) return ERROR; for(j=i;j<=L.length-1;j++) L.elem[j-1] = L.elem[j]; //被删除元素之后的元素前移 L.length--; //表长减 1 return ok; } 多找案例，多练。 搞清楚，基本的数据定义，扎实基础。 用心 用心、用心 用心、用心、用心 知其然、知其所以然！！！ 多学习，多思考，多总结，多输出，多交流 （five kills）~~~6.插入算法
7.顺序表的删除
2.多总结、多思考、多输出
3.用心