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：稀疏多项式的运算

引申：如果存三项，你还按原来数组下标存，那么必定造成很大空间浪费。

稀疏多项式解决办法：

1. 有下标i
2. 系数a[i]（多项式值）
3. 指数（多项式指数值）

把每一项系数和指数也存储起来，也都成为了一个线性表，只不过这个线性表，每一项为俩个数据项。

创建一个新数组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所指变量的存储空间，彻底删除一个变量。

注：需要加载头文件：<stdio.h>

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<L.length;i++){

if(e==L.elem[i]) return i+1; //查找成功。返回序号

return 0; //查找失败，返回0

}

}

while语句实现

int LocateElem(SqList L,ElemType e){
int i=0;

while(i<L.length&&L.elem[i]!=e) i++;

if(i<L.length) return i+1;

return 0;

}

6.插入算法

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;

}

}

7.顺序表的删除

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;

}

2.多总结、多思考、多输出

多找案例，多练。

3.用心

搞清楚，基本的数据定义，扎实基础。

用心

用心、用心

用心、用心、用心

知其然、知其所以然！！！

多学习，多思考，多总结，多输出，多交流 （five kills）~~~