线性表的定义和特点

线性表是具有相同特性的数据元素的一个有限序列

:线性起点/起始节点

 :的直接前驱

 :的直接后继

:线性终点/终端节点

n:元素总个数,表长

下标:是元素的序号,表示元素在表中的位置

n=0时称为空表

线性表

由n(n>0)个数据元素(结点),组成的有限序列

将非空的线性表(n>0)记作:()

这里的数据元素()只是一个抽象的符号,其具体含义在不同的情况下,可以不同

例1

分析26个英文字母组成的英文表

        (A,B,C...Z)

数据元素都是字母,元素间关系是线性关系

例2

分析学生情况登记表

略

每条记录也是线性关系

例3

某单位历年拥有计算机的数量(4,6,45,34,33) 线性关系(先后)

例4 

12星座 (白羊座,金牛座,...双鱼座) 线性关系(先后)

同一线性表的元素必定有相同特性,数据元素之间的关系是线性关系

综上 线性表的逻辑特征是:
在非空的线性表中,有且一个开始节点,它没有直接前趋,仅有一个后继

在非空的线性表中,有且一个终端节点,它没有直接后继,仅有一个前趋

其余节点() 仅有一个前趋,仅有一个后继

线性表是一种典型的线性结构

线性表案例

例1

一元多项式的运算:实现两个多项式加,减,乘运算

线性表P=()

每一项的指数i隐含在其系数的序号中

用数组来表示

指数用下标表示,系数用具体值表示

操作

两个多项式相加

线性表R  = ()

例2:稀疏多项式

如果用前面下标代表指数,会造成空间浪费

多项式非零项的数组表示

线性表  

线性表A=((7,0),(3,1),(9,8).(5,17))

线性表B=((8,1),(22,7),(-9,8))

创建一个新数组c

分别从头遍历比较a和b的每一项

指数相同,对应系数相加,若其和不为0,则在c中加一个新项

指数不相同,则将指数较少的项复制到c中

一个多项式遍历完毕时,将另一个剩余项依次复制到c即可

缺陷:并不知道数组c的空间要分配多少

顺序存储结构存在问题

存储空间分配不灵活

运算的空间复杂度高(需要额外的空间)

解决问题

链式存储结构 后续详细介绍

例3:图书信息管理系统

需要的功能: 增(插入)删改查排序计数

图书表抽象为线性表

表中每本书抽象成线性表中的数据元素

图书顺序表:数组存储

图书链表:链表存储

选择适当的存储结构

实现此存储结构上的基本操作

利用基本操作完成功能

总结:

线性表中数据元素的类型可以为简单类型,也可以为复杂类型

许多实际应用问题所涉及的基本操作有很大相似性,不应为每个具体应用单独编写一个程序

从具体应用中抽象出共性的逻辑结构和基本操作(抽象数据类型),然后实现其存储结构和基本操作

线性表的类型定义

抽象数据类型线性表的定义如下:

ADT List{

        数据对象: D = {   属于Elemset,  }

        数据关系: R = {  属于 (i=2,3,....n)}

        基本操作:

                InitList(&L)

        略

} ADT List

基本操作:

初始化线性表

InitList(&L)

操作结构:构造一个空的线性表L

销毁线性表

DestroyList(&L)

初始条件:线性表L已经存在

操作结果:销毁线性表L

清除线性表

ClearList(&L)

初始条件:线性表L已经存在.

操作结果:将线性表L重置为空表

判断线性表是否为空

ListEmpty(L)

初始条件:线性表L已经存在

操作结果:若线性表L为空表,则返回Ture,否则返回False

返回线性表L的元素个数

ListLlenth(L)

初始条件:线性表L已经存在

操作结果:返回线性表L中的数据元素个数

返回线性表第i个元素的值

GetElem(L,i,&e);

初始条件:线性表L已经存在,1<=i <= ListLenth(L)

操作结果:用e 返回线性表L中第i个元素的值

返回L中第1个与e满足compare()的数据元素的位序

LocateElem(L,e,compare())

初始条件:线性表L已经存在,compare()是数据元素判定函数

操作结果:返回L中第1个与e满足compare()的数据元素的位序,若这样的数据元素不存在则返回值为0.

待补充

忘保存，明天补上

线性表的顺序表示和实现2

顺序表的特点：

以物理位置相邻表示逻辑关系

任一元素均可随机存取（优点）

用高级语言实现数据类型

用一维数组表示顺序表

线性表可变（删除）

数组长度不可动态定义

注:一维数组的定义方式

类型说明符 数组名[常量表达式]

说明:常量表达式中可以包含常量和符号常量,不能包含变量,, 即C语言中不允许对数组的大小做动态定义

解决方式:用一变量表示顺序表的长度属性

如下所示

c定义结构体

#define LIST_INIT_SIZE 100 
//线性表存储空间的初始分配量
//定义了一个结构体 ​SqList​，包含一个数组和一个整型变量 
typedef struct { 
    Elem Type elem[LIST_INIT_SIZE];
    int length; //当前长度
} SqList;

实例

多项式的顺序存储结构类型定义

c实现

#define MAXSIZE 1000
//多项式可能达到的最大长度

//结构体：多项式非零项定义
typedef struct {
    float p; //系数
    int e; //指数
} Polynomial;

//结构体:多项式顺序存储结构
typedef struct{
    Polynomial *elem; //基地址
    int length; //当前项个数
} SqList;

图书表的顺序存储结构类型定义

#define MAXSIZE 10000
//图书表可能达到的最大长度

//图书信息定义
typedef struct {
    char no[20]; //图书ISBN
    char name[50]; //图书名字
    float price; //图书价格
} Book;

//图书表顺序存储结构类型为SqList
typedef struct {
    Book *elem; //存储空间的基地址
    int length; //图书表中当前图书个数
}SqList; //图书表的顺序存储结构类型为SqList

补充知识:

元素类型说明

顺序表类型定义

类c

typedef struct {
    ElemType data[]; //ElemType一般是自定义的顺序表里的元素类型
    int length;
} SqList; //顺序表类型

ElemType一般是自定义的顺序表里的元素类型

如下所示

typedef strcut {
    float p;
    int e;
} Polynomial;

typedef strcut {
    Polynomial *elem;
    int length;
}SqList;

数组定义

静态分配

typedef struct {
    ElemType data[MaxSize];
    int length;
} SqList; 

动态分配

typedef struct{
    ElemType *data;
    int length;
}SqList;

动态分配创建变量

#include <stdlib.h>
typedef struct{
    ElemType *data;
    int length;
}SqList;

SqList L;
L.data = (ElemType*)malloc(sizeof(ElemType)*MaxSize);
//MaxSize:数组最大长度 sizeof:获取类型长度 malloc分配固定长度的空间
//释放指针p所指变量的存储空间,即彻底删除一个变量
free(L.data)

c++动态存储分配

new 类型名(初值列表)

功能:申请用于存放T类型对象的内存空间,并根据初值列表赋初值

结果值;

成功:T类型的指针,指向新分配的内存

失败:0

int *p1 = new int;
int *p2 = new int(10);
delete p1;