// 求顺序表 LA 与 LB 的共同元素，结果在 LA 中
{
int n = LA.Length( );
int m = LB.Length( );
int i = 0;
while ( i < n )
{
Type x = LA.Get( i ); // 从 LA 中取一元素
int k = LB.Find( x ); // 在 LB 中查找该元素
数据元素
数据元素
关系
Ei
E i+1
物理结构：数据结构在计算机中的具体表示和实现，
又称存储结构
2020/5/25
4
数据结构的分类
按逻辑结构分类：
纯集合型结构:数据元素之间除了“同属于一个集合”这
一 关系外，别无其他关系
线性结构：数据元素之间存在“一个跟着一个”的序列关
系
树型结构：数据元素之间存在“每个元素只能跟着一个元
ei
i
0 c0=1.2 e0=0 c1=51.3 e1=50
i=0
c2=3.7 e2=101
2020/5/25
22
多项式的表示
对于稀疏多项式，采用二元组表示法可以大大节省存储 空间：
（1）将稀疏多项式的每一项用二元组< ci , ei >表示
——客体的表示方法 （2）用一顺序表（一维数组）来存放上述的二元组
符号表示法：L＝（e1,e2,…en）
图形表示法：
e1
e2
en
2020/5/25
7
e 其中： i ---表示线性表 L 的第 i 个数据元素
n ---表示线性表 L 的表长（n>=0） n=0 时的线性表称为空表
e e e e i-1 称为 i 的前驱， i+1 称为 i 的后继
线性表的基本操作：
friend Polynomial; // 定义 Polynomial 类为 term 类的友元类 private :
float coef; // 系数 int exp; // 指数 }
2020/5/25
24
多项式的类定义——数据的表示方法
class Polynomial
{
public :
...
// 成员函数声明（构造、释构、相加等函数）
变量
0 Maxsize
1
last
...
last 数组下标
Maxsize-1
...
...
操作算法 初始化操作 插入操作 删除操作 查找操作 排序操作
......
2020/5/25
12
顺序表的基本操作（算法）
（1）顺序表初始化操作算法
template <class Type> Seqlist<Type>::Seqlist(int sz)
//构造函数，通过指定参数 sz 定义数组的长度，并将 last 置为 –1
//即置空表
{
if(sz>0)
{
Maxsize=sz;
last=-1;
// last+1=0 , 表明表中无元素，空表
data=new Type[Maxsize];
}
}
2020/5/25
13
（2）顺序表查找操作
template <class Type> int Seqlist<Type>::Find(Type & x) const
——数据的组织方法
系数 c0 c1 . . . ci 指数 e0 e1 . . . ei
. . . cn ... . en .
2020/5/25
23
多项式二元组的类定义——客体的表示方法
class Polynomial; // 多项式类的前视声明 class term // 多项式中项（二元组）的类定义 {
0 1 . . . i-1 i i+1 . . .
...
...
last-1 last ...
1 2 ...
2020/5/25
17
template <class Type> int Seqlist<Type>::Remove(Type & x) //将 x 从表中删除。若 x 在表中并成功删除则返回 1， //否则返回 0 {
的研究和发展以及其体系的完善。
2020/5/25
2
基本术语
数 据：描述客观事物的且能由计算机处理的数
值、字符等符号
数据元素：数据的基本单位，在计算机程序中通常
作为一个整体进行考虑和处理（记录、 结点、表目、元素）
数 据 项：数据元素的某一属性。数据元素可以由
若干数据项组成，数据项可以由若干 更小的款项（组合项、原子项）组成。 数据项又称域、字段
有限长的操作步骤序列，则重于解决问题
的方法和步骤。当算法由计算机语言表示
时称为程序（代码）
算法设计目标：可维护性
可靠性（正确性、健壮行）
可读性
高效率（时间、空间）
2020/5/25
6
第二章 线性表
2。1 线性表的逻辑结构 定义：由相同种类的数据元素组成的一个有穷
序列称为一个线性表。“一个跟着一个”
素 但可以有多个元素跟着它”的层次关系
图状结构：任意两个数据元素之间都可能存在关系
按存储结构分类：
顺序存储结构
链式存储结构
2020/5/25 索引存贮结构
5
基本操作：任一数据结构均有一组相应的基本操作，
有时操作不同，用途迥异（如栈和队列）
常用的基本操作有插入、 删除、查找、
更新、排序等
算
法：算法是为了解决给定的问题而规定的一个
if (k==-1)
// 未找到
{ LA.Insert( x ,n); // 将该元素追加到 LA 中
n++;
}
}
}
2020/5/25
20
template < class Type >
void Intersection( Seqlist <Type> & LA,Seqlist <Type> & LB)
（1）初始化（置空表）——可由构造函数实现 （2）求表长（ Length ） （3）查找或定位（ Find ）
（4）插入（ Insert ） （5）删除（ Remove ） （6）排序（ Sort ）
（7）判空（ IsEmpty）
2020/5/25
8
2.2 线性表的顺序存储结构
要实现在计算机内表示一个数据结构，要解决两 种信息的存贮问题：
int i=Find(x); if (i>=0) {
last--; for (int j=i;j<=last;j++) data[j]=data[j+1]; return 1; } return 0; }
2020/5/25
18
顺序存储结构的优缺点
优点：
（1）算法简单、可读性好、开发代价低
缺点：
0 . . . i-1 i i+1 . . .
last
...
...
...
... 3 2 1
x
先移动后面元素
2020/5/25
15
template <class Type> int Seqlist<Type>::Insert(Type & x, int i) //将 x 插入表中 i 处，若成功返回 1 ，否则返回 0 {
//查找 x 在表中位置，若查找成功，函数返回 x 的位置 //否则返回－1 {
int i=0; while(i<=last && data[i]!=x) i++; if (i>last) return –1; else return i; }
2020/5/25
14
（3）顺序表插入操作
为了把新元素 x 插入到 i 处，必须把从 i 到 last 的所 有元素成块向后移动一个元素位置，以空出第 i 个位 置供 x 插入：
last+1 代表顺序表的表长； 将 last 赋值为 –1 可实现置空表操作。
由上可知：合理地设置数据成员可大大简化算法的设计 及提高算法的效率。顺序表不仅仅包含存放其数据元 素的数组，它还应包括一些有用的数据成员，以及相 应的操作，它们是一个整体：
2020/5/25
11
顺序表之整体概念：
数组 data
关 键 码：能起唯一标识（数据元素）作用的数据项 数据结构：一组同类的数据元素、其间的关系及其上的
一组操作所构成的整体，称为一个数据结构
2020/5/25
3
数据结构的描述方式
逻辑结构：是对数据元素之间逻辑关系（抛开具体
的关系含义以及存储方式等）的描述，它可以用一个 数据元素的集合和定义在此集合上的几个关系来表示。 通常可用图形表示，圆圈表示数据元素，箭头表示关 系：
（1）插入、删除操作时需要移动大量元素， 效率较低；
（2）最大表长难以估计，太大了浪费空间， 太小了容易溢出。
2020/5/25
19
顺序表应用举例
当将两个顺序表作集合考虑时的“并”与“交”操作算法
template <class Type>
void Union(Seqlist <Type> & LA,Seqlist <Type> & LB)
if (i<0||i>last+1||last==Maxsize-1) return 0; else {