文档介绍：第2章线性表
线性表的类型定义
线性表的顺序表示和实现
线性表的链式表示和实现
一元多项式的表示及相加
1
线性表的类型定义
线性表的概念
线性表的逻辑结构是具有相同类型的n个数据元素的有限序列: L=(D,R) 其中R为D上的一个二元关系
D ={ a1 ,a2 ,…,an }
R ={ < ai,ai+1 >| 1≤i≤n-1 ,ai∈D}
有序对
ai(i=1,...,n)是属于某数据对象的元素,
n为线性表的长度(n≥0),n=0的表称为空表。
例英文字母表(A,B,C,…..Z)是一个线性表
例
学生信息表
也是线性表
2
线性表的结构特点
(1)所有数据元素ai在同一个线性表中必须是相同的数据类型;
(2)在非空线性表中必存在唯一的一个称为“头”的元素;
(3)在非空线性表中必存在唯一的一个称为“尾”的元素;
(4)除“头”外,每个元素都有且只有一个前驱元素。
(5)除“尾”外,每个元素都有且只有一个后继元素。
线性表的类型定义
3
顺序存储结构(顺序表)
用一组地址连续的存储单元依次存放线性表的数据元素,称为线性表的顺序存储结构。
地址计算:设每个元素占L个单元,并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)= LOC(ai)+L
线性表的第i个数据元素ai 的存储位置为
LOC(ai)= LOC(a1)+(i-1)*L
LOC(a1)通常称作线性表的起始位置或基地址。
线性表的顺序表示和实现
4
特点:
(1)逻辑上相邻的数据元素在物理上也相邻;
(2)是顺序存储结构、随机存取数据元素。
这种存储结构只要知道元素的序号,就很容易找到第i个数据元素,且无论序号i为何值,找到第i个元素所需时间相同。
线性表的顺序表示和实现
5
表示方式:
数组表示:注意:C语言中,数组下标从0开始。
#define MAX 100 //常量定义
datatype data[MAX];
int length;
datatype为抽象数据类型,可用int, float, double, char 或结构体类型代替。如: typedef int datatype
length为顺序表当前长度
线性表的顺序表示和实现
6
a1
a2
an
0
1
n-1
1
2
n
内存
数组下标
元素序号
Max-1
#define Max 100
int data[Max];
int n;
例
typedef struct student
{ int num;
char name[20];
int age ;
float score;
}datatype;
#define Max 100
datatype class1[Max];
int n;
备用空间
数据元素不是简单类型时,可定义结构体数组
7
表示方式:
将length与data封装在一起,单独定义一种顺序表类型—用结构体建立。
例#define MAX 1000
typedef struct
{ int data[MAX];
int length;
}SeqList;
如何声明变量(顺序表)L?
SeqList L;
L. length =2;
[0]=91;
[1]=82;
SeqList即为顺序表类型,可用该类型建立很多顺序表。
思考:如何定义学生的顺序表?
线性表的顺序表示和实现
8
#define MAX 1000
typedef struct student
{ int num;
char name[20];
int age ;
float score;
}stu;
typedef struct List
{ stu data[MAX];
int length;
}SeqList;
如何定义学生的顺序表?
#define MAX 1000
struct student
{ int num;
char name[20];
int age ;
float score;
};
typedef struct List
{struct student data[MAX];
int length;
}SeqList;
SeqList class; [0].num=9608066
[0].age=18 [0].score=
线性表的顺序表示和实现
9
表示方式: