2009-7-25 1
数据结构及其应用
（用面向对象方法与 C＋＋描述）
2009-7-25 2
第一章 概述研究对象,信息的表示方法、数据的组织方法、操作算法设计意义地位,数据结构＋算法＝程序程序设计的基础系统软件的核心发展过程,数值计算 非数值计算建立数学模型 客体及其关系的表示设计数值计算方法 数据的组织操作算法的设计非数值计算应用的发展，促进了数据结构的研究和发展以及其体系的完善。
2009-7-25 3
基本术语
数 据,描述客观事物的且能由计算机处理的数值、字符等符号
数据元素,数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理（记录、
结点、表目、元素）
数 据 项,数据元素的某一属性。数据元素可以由若干数据项组成，数据项可以由若干更小的款项（组合项、原子项）组成。
数据项又称域、字段
关 键 码,能起唯一标识（数据元素）作用的数据项
数据结构,一组同类的数据元素、其间的关系及其上的一组操作所构成的整体，称为一个数据结构
2009-7-25 4
数据结构的描述方式
逻辑结构,是对数据元素之间逻辑关系（抛开具体的关系含义以及存储方式等）的描述，它可以用一个数据元素的集合和定义在此集合上的几个关系来表示。
通常可用图形表示，圆圈表示数据元素，箭头表示关系：
物理结构,数据结构在计算机中的具体表示和实现，
又称存储结构
E i E i+1
数据元素 数据元素关系
2009-7-25 5
数据结构的分类
按逻辑结构分类：
纯集合型结构,数据元素之间除了,同属于一个集合,这一关系外，别无其他关系线性结构,数据元素之间存在,一个跟着一个,的序列关系树型结构,数据元素之间存在,每个元素只能跟着一个元素但可以有多个元素跟着它,的层次关系图状结构,任意两个数据元素之间都可能存在关系
按存储结构分类：
顺序存储结构链式存储结构索引存贮结构
2009-7-25 6
基本操作,任一数据结构均有一组相应的基本操作，
有时操作不同，用途迥异（如栈和队列）
常用的基本操作有插入,删除、查找、
更新、排序等算 法,算法是为了解决给定的问题而规定的一个有限长的操作步骤序列，则重于解决问题的方法和步骤。当算法由计算机语言表示时称为程序（代码）
算法设计目标,可维护性可靠性（正确性、健壮行）
可读性高效率（时间、空间）
2009-7-25 7
第二章 线性表
2。 1 线性表的逻辑结构定义,由相同种类的数据元素组成的一个有穷序列称为一个线性表。,一个跟着一个,
符号表示法,L＝（ e1,e2,… en）
图形表示法：
e2 ene1
2009-7-25 8
其中,ei ---表示线性表 L 的第 i 个数据元素
n ---表示线性表 L 的表长（ n>=0）
n=0 时的线性表称为空表
ei-1 称为 ei 的前驱,ei+1 称为 ei 的后继线性表的基本操作：
（ 1）初始化（置空表） ——可由构造函数实现
（ 2）求表长（ Length ）
（ 3）查找或定位（ Find ）
（ 4）插入（ Insert ）
（ 5）删除（ Remove ）
（ 6）排序（ Sort ）
（ 7）判空（ IsEmpty）
2009-7-25 9
2.2 线性表的顺序存储结构要实现在计算机内表示一个数据结构，要解决两种信息的存贮问题：
数据元素本身的存贮数据元素之间关系的存贮定义,利用内存物理结构上的邻接特点，实现线性表的,一个跟着一个,这一序列关系的存贮方式，
称为线性表的顺序存贮结构，其上的线性表称为顺序表。
顺序表的类定义,利用数组作为顺序表的存储结构，
它被封装在类的私有域中
2009-7-25 10
template <class Type> class SeqList {
Public:
SeqList(int MaxSize=defaultSize);
~SeqList( ) {delete [ ] data;}
int Length( ) const {return last+1;}
int Find(Type & x) const;
int Insert(Type & x,int i);
int Remove(Type & x);
int IsEmpty( ) {return last = = - 1;}
int Isfull( ) {return last = =MaxSize – 1 ;}
Type & Get( int i ) {return i <0 || i >last? NULL,data[i];}
Private:
Type * data; // 用数组存放线性表 ——顺序存贮结构
int Maxsize; // 数组大小，但顺序表的长度为 last+1
int last; }// last 为表中最后元素的下标,last=-1 时表示空表
2009-7-25 11
上述顺序表定义中的数据成员 Maxsize 是为判断顺序表是否为满而设,last 是为便于判断顺序表是否为空、求表长、置空表而设：
last=Maxsize –1表示顺序表已满，此时再进行插入操作会导致上溢错误；
last=-1 表示顺序表为空表，此时再进行删除操作会导致下溢错误；
last+1 代表顺序表的表长；
将 last 赋值为 –1 可实现置空表操作。
由上可知：合理地设置数据成员可大大简化算法的设计及提高算法的效率。顺序表不仅仅包含存放其数据元素的数组，它还应包括一些有用的数据成员，以及相应的操作，它们是一个整体：
2009-7-25 12
顺序表之整体概念：
data
0
1
last
Maxsize
last
数组下标数组 变量 操作算法
Maxsize-1
初始化操作插入操作删除操作查找操作排序操作
.,,,,,.,,
.,
.
.,
.
2009-7-25 13
顺序表的基本操作（算法）
（ 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];
}
}
2009-7-25 14
（ 2）顺序表查找操作
template <class Type> int Seqlist<Type>::Find(Type & x)
const
//查找 x 在表中位置，若查找成功，函数返回 x 的位置
//否则返回－ 1
{
int i=0;
while(i<=last && data[i]!=x) i++;
if (i>last) return –1;
else return i;
}
2009-7-25 15
（ 3）顺序表插入操作为了把新元素 x 插入到 i 处，必须把从 i 到 last 的所有元素成块向后移动一个元素位置，以空出第 i 个位置供 x 插入：
x
23 1
先移动后面元素
0 i-1 i i+1 last.,,,,,
.,,,,,,,,
.,,
2009-7-25 16
template <class Type> int Seqlist<Type>::Insert(Type & x,
int i)
//将 x 插入表中 i 处，若成功返回 1,否则返回 0
{
if (i<0||i>last+1||last==Maxsize-1) return 0;
else
{
last++;
for(int j=last;j>i;j--) data[j]=data[j-1];
data[i]=x;
return 1;
}
}
2009-7-25 17
（ 4）顺序表删除操作为了删除第 i 个元素，必须把从 i＋ 1 到 last 的所有元素向前移动一个元素位置，把第 i 个元素覆盖掉：
1 2,,,
0 i-1 i i+1 last-1 last1
.,,,,,,,,
.,,,,,
2009-7-25 18
template <class Type> int Seqlist<Type>::Remove(Type & x)
//将 x 从表中删除。若 x 在表中并成功删除则返回 1，
//否则返回 0
{
int i=Find(x);
if (i>=0)
{
last--;
for (int j=i;j<=last;j++) data[j]=data[j+1];
return 1;
}
return 0;
}
2009-7-25 19
顺序存储结构的优缺点
优点：
（ 1）算法简单、可读性好、开发代价低
缺点：
（ 1）插入、删除操作时需要移动大量元素，
效率较低；
（ 2）最大表长难以估计，太大了浪费空间，
太小了容易溢出。
2009-7-25 20
顺序表应用举例当将两个顺序表作集合考虑时的,并,与,交,操作算法
template <class Type>
void Union(Seqlist <Type> & LA,Seqlist <Type> & LB)
// 合并顺序表 LA 与 LB,重复元素只留一个，结果在 LA 中。
{ int n=LA.Length();
int m=LB.Length();
for (int i=0;i<=m-1;i++)
{
Type x=LB.Get(i); // 从顺序表 LB 中取一元素
int k=LA.Find(x); // 在顺序表 LA 中查找该元素
if (k==-1) // 未找到
{ LA.Insert( x,n); // 将该元素追加到 LA 中
n++;
}
}
}
2009-7-25 21
template < class Type >
void Intersection( Seqlist <Type> & LA,Seqlist <Type> & LB)
// 求顺序表 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 中查找该元素
if ( k== - 1) // 未找到
{ LA.Remove( i ); n--;} // 则从 LA 中删除该元素
else i ++;
}
}
2009-7-25 22
多项式及其运算
A(x)=a0x + a1x +a2x +…+ an-1x + anx =
B(x)=b0x + b1x +b2x +…+ bn-1x +bnx =
A(x)+B(x)=
实际应用中，上述一元多项式中的很多系数有可能为零，
即为稀疏多项式，如下式所示：
Σ aix
i=0
n
i0 1 2 n-1 n
0 1 2 n-1 n Σ bixi
i=0
Σ (ai+bi)x
n
i=0
i
P (x)=1.2+51.3x +3.7x5
0
50 101
P(x)=Σci xi=0n ei
c0=1.2 e0=0
c1=51.3 e1=50
c2=3.7 e2=101
2009-7-25 23
多项式的表示对于稀疏多项式，采用二元组表示法可以大大节省存储空间：
（ 1）将稀疏多项式的每一项用二元组 < ci,ei >表示
——客体的表示方法
（ 2）用一顺序表（一维数组）来存放上述的二元组
——数据的组织方法
c0 c1 ci cn
e0 e1 ei en
系数指数
.,,.,,,,,
.
.
.,,
2009-7-25 24
多项式二元组的类定义 ——客体的表示方法
class Polynomial; // 多项式类的前视声明
class term // 多项式中项（二元组）的类定义
{
friend Polynomial; // 定义 Polynomial 类为 term 类的友元类
private,
float coef; // 系数
int exp; // 指数
}
2009-7-25 25
多项式的类定义 ——数据的表示方法
class Polynomial
{
public,
.,,// 成员函数声明（构造、释构、相加等函数）
private,
int MaxTerms ; //共享空间（顺序表）的最大项数
static term termArray[MaxTerms];
//存放二元组的数组，存放多个多项式的共享空间
static int free ; // 共享空间中自由空间之起始下标
int start,finish ; // 多项式在共享空间中的首、尾下标
}
2009-7-25 26
多项式的相加
A(x)=Σaix B(x)=Σbjx
C(x)=A(x)+B(x)
n m
i=0 j=0
e i e j
A,Start A,finish
B,Start B,finish
free MaxTerm-1
2009-7-25 27
多项式 A＋ B算法思路：
（ 1）保留 A,B两个多项式，将 A＋ B放人 C中；
（ 2）开始时 C.start = free；
（ 3）设置两个指针 a 和 b 分别作为 A 与 B 的检测指针，开始时分别指向 A 与 B 的首项，即：
a = A,start ; b = B,start；
（ 4）当两个指针都未超出相应多项式的最末位置时，比较它们所指示的对应项的指数：
若指数相等，则对应项系数相加，若相加结果不为零，则在
C 中加入一个新项若指数不等，则把指数小者拷贝到 C 中
（ 5）当两个指针中有一个超出了相应多项式的最末位置，则将另一个多项式的剩余部分拷贝到 C 中
2009-7-25 28
Polynomial Polynomial,,Add ( Polynomial B ) {
Polynomial C; int a = start; int b =B.start; C.start = free; float c;
while ( a <= finish && b <= B.finish )
switch ( compare(termArray[a].exp,termArray[b].exp )) {
case?=?,c= termArray[a].coef + termArray[b].coef ;
if (c) NewTerm( c,termArray[a].exp ) ;
a++ ; b++ ; break ;
case?>?,NewTerm( termArray[b].coef,termArray[b].exp);
b++ ; break ;
case?<‘,NewTerm( termArray[a].coef,termArray[a].exp);
a++ ; }
for ( ; a <= finish ; a++ )
NewTerm( termArray[a].coef,termArray[a].exp);
for ( ; b <= B.finish ; b++ )
NewTerm( termArray[b].coef,termArray[b].exp);
C.finish=free-1;
return C ; }
2009-7-25 29
void Polynomial,,NewTerm( float c,int e )
// 把一个新的项（二元组 < c,e >）追加到多项式 C(x) 中
{
if ( free >= MaxTerms )
{
cout << ―Too many terms in polynomials‖ << endl ;
return ;
}
termArray[ free ],coef = c ;
termArray[ free ],exp = e ;
free ++ ;
}
2009-7-25 30
作业：
定义多项式类的求表长、查找、插入、删除、判空表判满表、读取（第 i 个元素）等成员函数，并用这些函数实现前述的两个多项式的相加操作。
提示：
（ 1）定义查找指数相等的元素的成员函数
（ 2）仿照前述的顺序表合并操作算法，先从多项式 B 中读取一元素，在 A 中查找有无指数相等元素：
若无，则有序插入 A 中；
若有，则系数相加：
若和为零，则从 A 中删除相应元素；
否则用新系数构造新元素，并插入 A 中相应位置
2009-7-25 31
稀疏矩阵（ Sparse Matrix）－－数值计算中的顺序表设计
0 0 0 22 0 0 15
0 11 0 0 0 17 0
A = 0 0 0 -6 0 0 0
0 0 0 0 0 39 0
91 0 0 0 0 0 0
0 0 28 0 0 0 0
矩阵 A 是一个 6 行 7 列的稀疏矩阵，只有 8 个非零元素，
其他均为零。因此用二维数组来存储稀疏矩阵的空间利用率较低，必须考虑对稀疏矩阵的压缩存储表示。
2009-7-25 32
稀疏矩阵的三元组表示法：
（ 1）将稀疏矩阵的非零元素用三元组
< row,column,value > 表示（ 表示稀疏矩阵的第 row 行、第 column 列的值为 value）
——客体的表示方法
（ 2）用一顺序表（一维数组）来存放上述三元组
（每一个三元组即为顺序表的一个数据元素）
并按行优先顺序存放
——数据的组织方法
template < class Type > class Trituple
{ private,
int row,col;
Type value;
}
2009-7-25 33
矩阵 A的三元组表示：
表下标 行 (row) 列 (col) 值 (value)
0 0 3 22
1 0 6 15
2 1 1 11
3 1 5 17
4 2 3 -6
5 3 5 39
6 4 0 91
7 5 2 28
2009-7-25 34
稀疏矩阵的类声明：
template < class Type > class SparseMatrix
{ public:
SparseMatrix(int MaxTerms=defaultSize);
~SparseMatrix() {delete [ ] smArray;}
SparseMatrix<Type> Compression(smData<Type>);
SparseMatrix<Type> Transpose();
SparseMatrix<Type> Add(SparseMatrix <Type> b);
SparseMatrix<Type> Multiply(SparseMatrix<Type> b);
private:
int Rows,Cols,Terms,MaxTerms;
Trituple <Type> smArray[MaxTerms];
}
2009-7-25 35
说明：
（ 1）压缩前的稀疏矩阵为 Rows 行,Cols 列的矩阵
smData,压缩后的稀疏矩阵存放在一维数组
smArray 中，其中的元素为 Trituple 类型的对象。
声明中的 Terms 对应于顺序表定义中的 last，
MaxTerms 对应于顺序表定义中的 Maxsize，
smArray 对应于顺序表定义中的 data
（ 2）为稀疏矩阵声明了四种操作：
压缩（ Compression）
转置（ Transpose）
相加（ Add）
相乘（ Multiply）
根据实际需要还可以声明其他操作。
（ 3）数值计算与非数值计算的数据结构中所定义的基本操作有很大的不同
2009-7-25 36
稀疏矩阵的转置操作快速转置算法思路：
（ 1）引入两个辅助数组 rowSize[ ] 和 rowStart[ ]
rowSize [ i ]——表示稀疏矩阵第 i 列的非零元素个数
rowStart[ i ]——表示稀疏矩阵第 i 列的第一个（行号最小）
非零元素在转置矩阵的三元组表中的位置。
显然应有：
rowStart[ i ] + rowSize[ i ] = rowStart[ i+1 ]
.,,,,,,,,
共有 rowSize[ i ] 个元素
2009-7-25 37
上述公式表示，若已知稀疏矩阵第 i 列的第一个非零元素在转置矩阵的三元组表中的位置 rowStart [ i ],以及稀疏矩阵第 i 列的非零元素个数 rowSize [ i ],就可以算出第 i+1 列非零元素在转置矩阵的三元组表中的位置 rowStart [ i+1]
另外，根据转置矩阵的定义可知：
rowStart [ 0 ] = 0
因此：
rowStart [ 1 ] = rowSize [ 0 ] + rowStart [ 0 ] = rowSize [ 0 ]
rowStart [ 2 ] = rowSize [ 1 ] + rowStart [ 1 ]
.,,,,,
因此，只要预先统计得到 rowSize [ i ] ( i = 0,1,2,.,,)
就可以得到第 i + 1 列非零元素在转置矩阵的三元组表中的位置
2009-7-25 38
template <class Type> SparseMatrix<Type> SparseMatrix<Type>::
FastTranspos( )//
{ int *rowSize = new int[Cols]; int *rowStart = new int[Cols];
SparseMatrix<Type> b; b.Rows = Cols; b.Cols = Rows; b.Terms = Terms;
if (Terms > 0 ) {
for (int i = 0; i<Cols; i ++) rowSize[i] = 0;
for (i=0;i<Terms;i++) rowSize[smArray[i].col]++;
rowStart[0]=0;
for (i=1;i<Cols;i++) rowStart[i]=rowStart[i-1]+rowSize[i-1];
for (i=0;i<Terms;i++){
int j=rowStart[smArray[i].col];
b.smArray[j].row=smArray[i].col;
b.smArray[j].col=smArray[i].row;
b.smArray[j].value=smArray[i].value;
rowStart[smArray[i].col]++;}
}
delete [] rowSize; delete [] rowStart; return b;
}
2009-7-25 39
2。 5 字符串定义,字符串（简称为串） 是 n ( n >= 0 ) 个字符的有限序列通常可记为：
S=? a0 a1 a2 … an-1 ‘
其中,串名 ——S
串值 ——引号中的内容
n——串长，即串中的字符个数（不包括串结束符 ‘ \0 ‘ ）
空串 ——n = 0 的串（但包含串结束符）
空白串 ——仅由若干个空格字符组成的串，其长度不为零子串 ——从非空串中连续取出的若干个字符组成的串子串的位置 ——子串的第 0个字符在原串中的位置可以认为：串是限制数据元素为字符的顺序表
2009-7-25 40
2.5.1 字符串抽象数据类型和类定义
class String{
public:
String(const String &);String(const char *const);String();
~String() {delete [ ] ch;}
int Length() const {return curLen； }
String & operator()(int pos,int len);
int operator ==(const String & ob) const {return strcmp(ch,ob.ch)==0;}
int operator !=(const String & ob) const{return strcmp(ch,ob.ch)!=0;}
int operator ! () const {return curLen==0； }
String & operator = (const String &);
String & operator += (const String &);
char & operator [ ] (int i );
int Find(String pat) const;
private:
int curLen;
char * ch;
}
2009-7-25 41
有了上述的串类定义，就可以进行下列操作：
String s1;
String s2 ( ― Hello World ‖ );
s1 = s2;
String s3 ( ― ; nice to here ! ‖ );
s1 + = s3;
int len=s1.length();
String s4;
s4=s1(6,5);
If (s1==s2)…
If (s1!=s2)…
If (! s1)…
Char c=s1[6];
s1[6]=?w‘;
2009-7-25 42
文本编辑计算机应用中要涉及大量的文本文件，文本文件由大量的串
（行）组成，在某些文本文件（如源程序）中，串（行）长差异很大，若每行都用等长的串来存贮，则会浪费存贮空间解决的办法之一是建立一个很大的字符数组作为所有串的共享空间 ——串值共享空间，再为每个串建立一个描述子，用于描述该串的长度以及该串在串值共享空间中的位置等信息，并将这些描述子存入一顺序表中，参见下图：
2009-7-25 43
行表 (linelist) 串值共享空间（ space） MaxSize-1
..
.,free
行号
0
1
2
3
行长 位置 行 2 行 3 行 0 行 1,,,
.,
.,
.,
.,
自由空间起始地址
0
串值共享空间 ——String（串）
行表 ——Seqlist（顺序表）
设计行内字符插入、删除操作算法设计整行插入、删除操作算法
2009-7-25 44
第三章 链表顺序表有下列缺点：
（ 1）插入、删除操作时需要移动大量元素，
效率较低；
（ 2）最大表长难以估计，太大了浪费空间，
太小了容易溢出。
因此，在插入和删除操作是经常性操作的应用场合选用顺序存储结构不太合适，此时可以选用链式存储结构。
定义：用指针来表示数据元素之间关系的存储结构称之为链式存储结构。
2009-7-25 45
定义：用由指针连接起来的一串结点来存储一个线性表的存储结构称为线性链式存储结构，简称链表。
当每一结点中只有一个指针，并用来表示一个数据元素到其后继元素之间的接续关系，则称这种存储结构为单链表。
注：此处的结点是指通过指针型变量动态索取到的存储空间
.,,^first
first——头指针 指针域 (link) last
last ——尾指针 数据元素域 (data)
^ ——空指针结点 1头结点 结点 0 结点 n-1
e0 e1 en-1
2009-7-25 46
上述的单链表表头设置了一头结点，头结点的数据域中可以为空，或者存放一些辅助数据。
设置头结点的目的是为了简化对空表的特殊处理，
使得算法更简单、更有效。
对于带头结点的单链表，可以很容易地表示空链表：
头指针 头结点
first ^
last尾指针
2009-7-25 47
用模板定义的单链表类
template <class Type> class List; //单链表类的前视声明
template <class Type> class ListNode{ //链表结点类的定义
friend class List <Type>; //将 List 类定义为 ListNode 类的友元
public:
ListNode( );
ListNode(const Type & item);
ListNode <Type> *NextNode ( ) {return link;}//后继结点指针
void InsertAfter (ListNode <Type> * p);
//将 *p 结点插入到当前结点之后
ListNode <Type> * GetNode (const Type & item,
ListNode <Type> * next); //创建一个新结点
ListNode <Type> * RemoveAfter ( ); //删除后继结点
private:
Type data;
ListNode <Type> * link;
}
data link
2009-7-25 48
template <class Type> class List//单链表类的定义
{
public:
List( ) {last=first=new ListNode<Type> (value,NULL);}
//构造函数，建立一个空链表
~List( );
void MakeEmpty( );//删除所有元素结点，将链表置为空链表
int Length( ) const; //求单链表表长
ListNode<Type> *Find(Type value); //查找值为 value 的结点
ListNode<Type> *Find(int i); //查找结点 i,返回结点 i 的指针
int Insert(Type value,int i);
//将值为 value 的新结点插入结点 i 之前
Type *Remove(int i); //删除结点 i
Type Get(int i); //读取结点 i 的值
private:
ListNode<Type> *first,*last; //头指针，尾指针
}
2009-7-25 49
ListNode<Type>类（链表结点类）的成员函数的实现
template <class Type> void ListNode<Type>::
ListNode( ):link(NULL){}
template <class Type> void ListNode<Type>::
ListNode(const Type & item)
//构造函数，创建一个新结点，该结点的值为 item,指针域为 NULL
{
data=item;
link=NULL;
}
template <class Type> ListNode<Type> * ListNode<Type>::
GetNode(const Type & item,ListNode<Type> * next=NULL)
//创建一个新结点，该结点的值为 item,指针域为 NULL,并返回
//该结点的指针
{
ListNode<Type> *newnode=new ListNode<Type>(item,next);
return newnode;
}
2009-7-25 50
InsertAfter( ) 函数
template <class Type> void ListNode<Type>::
InsertAfter(ListNode<Type> *p)
{将 p 所指的结点（ *p）链接成为当前结点（ *this）的后继结点
p->link=link; //(1)
link=p; //(2)
}
this
data link data link …
data linkp
p->link=linklink=p
…
(1)(2)
当前结点
2009-7-25 51
RemoveAfter( )
data link data link data link
当前结点 要删除的结点
template <class Type> ListNode<Type> *ListNode<Type>::
RemoveAfter()//删除当前结点 ( *this ) 的后继结点,并返回该结点的指针
{ ListNode<Type> *tempptr=link; //(1)
if (link==NULL) return NULL;
link=tempptr->link; //(2)
return tempptr;
}
：
(1)tempptr=link
(2) link=tempptr->link
this
2009-7-25 52
List<Type>类（链表类）的成员函数的实现
template <class Type> void List<Type>::MakeEmpty( )
{// 将当前链表置为空表
ListNode<Type> *q ;
while (first ->link != NULL)
// 循环删除头结点的后继结点，直到无后继结点为止
{q=first ->link ; first ->link=q ->link ; delete q ;}
last=first;// 最后让 last 指向头结点，完成置空表操作
}
first …
(1) q=first->link
(2) first->link=q->link
(最后 )
last
头结点
2009-7-25 53
template <class Type> int List<Type>::Insert(Type value,int i);
{// 将值为 value 的新数据元素插入到链表中结点 i 之前
ListNode<Type> *p = Find(i-1);// 查找结点 i-1
if (p==NULL) return 0;// 结点 i-1 不存在，插入失败
ListNode<Type> *newnode=GetNode(value,p->link);// 创建新结点
// 并使新结点指向结点 i (1)
if (p->link==NULL) last=newnode;// 若结点 i 不存在，则新结点将
// 是表尾结点
p->link=newnode;// 让结点 i-1 指向新结点，实现插入 (2)
return 1;
} … …结点 i-1 结点 i
新结点
p
newnode
(1)
(2)
2009-7-25 54
template <class Type> Type *List<Type>,,Remove( int i )
{// 删除结点 i,若成功，则返回该结点的数据元素（地址），
// 否则返回 NULL
ListNode<Type> *p= Find(i-1),*q ; // 查找结点 i-1
if ( p==NULL || p->link==NULL) return NULL;// 若结点 i-1 或者
// 结点 i 不存在，则返回 NULL,删除失败
q=p->link; // (1)
p->link=q->link;// (2)
Type value=q->data;
if (q==last) last=p;
delete q;
return &value;
}
… …结点 i-1 结点 i 结点 i+1
p q
(1)
(2)
2009-7-25 55
template <class Type> ListNode<Type> *List<Type>::Find( int i )
{ // 查找结点 i,若找到，则返回该结点的指针，否则返回 NULL
if ( i <-1 ) return NULL;
if ( i == -1 ) return first;// 结点 –1 即为头结点
ListNode<Type> *p=first->link;// p 指向结点 0
int j=0;
while(p!= NULL && j<i ) // 从结点 0 开始顺序向后查找，若第一个
// 条件不成立，即 p=NULL,则说明 i 值太大，查找失败；
// 若第二个条件不成立，则存在结点 i,查找成功,p 即为指向该结
// 点的指针
{ p=p->link;
j=j++;
}
return p;
}
2009-7-25 56
3.1.6 单链表的游标 (Iterator)类在实际应用中经常要对单链表进行打印、统计、检索等需要向后搜索整个链表的操作，因此设计具有光标功能的，能够记住当前位置并能得到其后继结点的游标类是有意义的。
单链表的位置概念,current 是结点 i+1的位置有了单链表结点 i+1 的位置 current,删除结点 i+1 或在结点 i+1 前插入新结点就会简单得多，无需查找过程。
… …
current
结点 i 结点 i+1
2009-7-25 57
单链表游标类声明
Template <class Type> class ListIterator
{ public:
ListIterator(const List<Type> & l),list(l),current(l.first) { }
Boolean NotNull( ); // 检查游标结点（指针 current
// 所指的结点）是否为不空
Boolean NextNotNull ( ); // 检查游标结点的后继结点是
//否为不空
Type * First ( );//使游标指向头结点
Type * Next ( ); // 使游标指向后继结点
private:
const List<Type> & list;
ListNode<Type> * current;//游标（指针）
}
2009-7-25 58
单链表游标类成员函数的定义
template <class Type> Boolean ListIterator<Type>::NotNull( )
{// 检查游标结点（ current 所指的结点）是否为不空（注：
//此处结点不空是指该结点的指针不空）。若不空，则返回真，
// 否则返回假
if ( current != NULL ) return True;
else return False;
}
template <class Type> Boolean ListIterator<Type>::NextNotNull( )
{// 检查游标结点（游标所指的结点）的后继结点是否为不空。
// 若不空，则返回真；否则返回假
if ( current != NULL && current->link != NULL ) return True;
else return False;
}
2009-7-25 59
template <class Type> ListNode<Type> * ListIterator<Type>::First( )
{// 使游标指向头结点
if ( list.first->link != NULL ） current = list.first; // 若头结点的指针
//域不空，即链表为非空表,则使游标指向头结点
else current = NULL; // 否则置空游标
return current;
}
template <class Type> ListNode<Type> * ListIterator<Type>::Next( )
{// 使游标指向后继结点
if ( current != NULL && current->link != NULL )
current=current->link;// 若游标结点及其后继结点都不空，则
// 将游标指向后继结点
else current=NULL;// 否则置空游标
return current;
}
2009-7-25 60
游标类应用举例：
int sum ( const List <int> &l )
//计算 int 型单链表 l 的累加和
{
ListIterator<int> li(l);//定义一个单链表对象 l 及其游标类对象 li,并
//将游标指向单链表的头结点（由构造函数实现）
if ( ! li.nextNotNull()) return 0;//空链表，返回 0
int retvalue=*li.First();//读取头结点的值，假定头结点的值为 0
while ( li.nextNotNull()) retvalue += *li.Next();
//若存在后继结点，则循环累加
return retvalue;
}
课堂作业：
使用游标类求 int 型单链表的最大结点。若单链表为空则返回 NULL，
否则返回最大结点的位置。
2009-7-25 61
3.2 循环链表（ Circular List）
e0 e1 en-1
循环链表的定义,（ P82－ P83）
循环链表与单链表不同的是链表中表尾结点的 link 域不是 NULL，而是链表头结点的指针（链表指针）
…first
last
表头结点
first
last
空表
2009-7-25 62
循环链表（带头结点）的类定义：
enum Boolean {False,True}
template <class Type> class CircList;//循环链表类的前视声明
template <class Type> class CircListNode
{//循环链表结点的类定义
public:
CircListNode (Type d=0,CircListNode<Type> * next=NULL):
data ( d ),link ( next ) { }//构造函数，创建一个循环
//链表结点，并初始化数据域为 d,指针域为 NULL
private:
Type data;
CircListNode < Type > * link;
}
data link
2009-7-25 63
template <class Type> class CircList
{ public:
CircList ( Type value );
~CircList ( );
int Length ( ) const;
Boolean IsEmpty ( ) { return first->link == first; }
Boolean Find ( const Type & value );
Type GetData ( ) const;//读取游标结点（ *current )的数据域
void Firster ( ) { current=first; }//将 current 指向头结点
Boolean First ( );//将 current 指向第一个元素结点（ e0）
Boolean Next ( );//将 current 指向后继结点
Boolean Prior ( );//将 current 指向前驱结点？
void Insert ( const Type & value );//在游标结点后插入新结点
void Remove ( );//删除游标结点的后继结点
private:
CircListNode<Type> * first,* current,* last ;
//头指针，游标，尾指针
}
2009-7-25 64
作业：
（ 1）比较单链表及其游标类与循环链表类的定义的不同
（ 2）考察循环链表中游标功能的实现方法
（ 3）模仿循环链表的类定义，重新定义单链表的类，使其具有游标功能，并设计新单链表的各成员函数自学,3.3 多项式及其相加
2009-7-25 65
双向链表（ Doubly Linked List）
如果在一个应用问题中经常要求检测指针向前驱和后继方向移动，
为保证移动的时间复杂度达到最小，就必须采用双向链表表示。
双向链表的结点结构：
前驱结点 后继结点
template <class Type> class DblNode
{
private:
Type data;
DblNode <Type> * lLink,* rLink;
}
lLink data rLink
左链指针 右链指针数据
2009-7-25 66
带头结点的双向 循环链表,
空表游标结点,* current
游标结点的前驱结点,* ( current -> lLink )
游标结点的后继结点,* ( current -> rLink )
e0 e1 en-1…
current
first
first
2009-7-25 67
双向循环链表的类定义：
template <class Type> class DblList
{
public:
DblList ( Type uniqueVal );
~DblList ( );
int Length ( ) const;
int IsEmpty ( ) { return first->rLink==first ;}
int Find ( const Type & target );
Type getData ( ) const;
void Firster ( ) { current = first; }
int First ( );
int Next ( );
int Prior ( );
int operator ! ( ) { return current != NULL;}
void Insert ( const Type & value );
void Remove ( ) ;
private:
DblNode <Type> * first,* current;
}
2009-7-25 68
2009-7-25 69
2009-7-25 70
2009-7-25 71
2009-7-25 72
2009-7-25 73
2009-7-25 74
2009-7-25 75
2009-7-25 76
2009-7-25 77
2009-7-25 78
2009-7-25 79
2009-7-25 80
2009-7-25 81
2009-7-25 82
2009-7-25 83
2009-7-25 84
2009-7-25 85
2009-7-25 86
2009-7-25 87
2009-7-25 88
2009-7-25 89
2009-7-25 90
2009-7-25 91
2009-7-25 92
2009-7-25 93
2009-7-25 94
2009-7-25 95
2009-7-25 96
2009-7-25 97
2009-7-25 98
2009-7-25 99
2009-7-25 100
2009-7-25 101
2009-7-25 102
2009-7-25 103
2009-7-25 104
2009-7-25 105
2009-7-25 106
2009-7-25 107
2009-7-25 108
2009-7-25 109
2009-7-25 110
2009-7-25 111
2009-7-25 112
2009-7-25 113
2009-7-25 114
2009-7-25 115
2009-7-25 116
数据结构及其应用
（用面向对象方法与 C＋＋描述）
2009-7-25 2
第一章 概述研究对象,信息的表示方法、数据的组织方法、操作算法设计意义地位,数据结构＋算法＝程序程序设计的基础系统软件的核心发展过程,数值计算 非数值计算建立数学模型 客体及其关系的表示设计数值计算方法 数据的组织操作算法的设计非数值计算应用的发展，促进了数据结构的研究和发展以及其体系的完善。
2009-7-25 3
基本术语
数 据,描述客观事物的且能由计算机处理的数值、字符等符号
数据元素,数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理（记录、
结点、表目、元素）
数 据 项,数据元素的某一属性。数据元素可以由若干数据项组成，数据项可以由若干更小的款项（组合项、原子项）组成。
数据项又称域、字段
关 键 码,能起唯一标识（数据元素）作用的数据项
数据结构,一组同类的数据元素、其间的关系及其上的一组操作所构成的整体，称为一个数据结构
2009-7-25 4
数据结构的描述方式
逻辑结构,是对数据元素之间逻辑关系（抛开具体的关系含义以及存储方式等）的描述，它可以用一个数据元素的集合和定义在此集合上的几个关系来表示。
通常可用图形表示，圆圈表示数据元素，箭头表示关系：
物理结构,数据结构在计算机中的具体表示和实现，
又称存储结构
E i E i+1
数据元素 数据元素关系
2009-7-25 5
数据结构的分类
按逻辑结构分类：
纯集合型结构,数据元素之间除了,同属于一个集合,这一关系外，别无其他关系线性结构,数据元素之间存在,一个跟着一个,的序列关系树型结构,数据元素之间存在,每个元素只能跟着一个元素但可以有多个元素跟着它,的层次关系图状结构,任意两个数据元素之间都可能存在关系
按存储结构分类：
顺序存储结构链式存储结构索引存贮结构
2009-7-25 6
基本操作,任一数据结构均有一组相应的基本操作，
有时操作不同，用途迥异（如栈和队列）
常用的基本操作有插入,删除、查找、
更新、排序等算 法,算法是为了解决给定的问题而规定的一个有限长的操作步骤序列，则重于解决问题的方法和步骤。当算法由计算机语言表示时称为程序（代码）
算法设计目标,可维护性可靠性（正确性、健壮行）
可读性高效率（时间、空间）
2009-7-25 7
第二章 线性表
2。 1 线性表的逻辑结构定义,由相同种类的数据元素组成的一个有穷序列称为一个线性表。,一个跟着一个,
符号表示法,L＝（ e1,e2,… en）
图形表示法：
e2 ene1
2009-7-25 8
其中,ei ---表示线性表 L 的第 i 个数据元素
n ---表示线性表 L 的表长（ n>=0）
n=0 时的线性表称为空表
ei-1 称为 ei 的前驱,ei+1 称为 ei 的后继线性表的基本操作：
（ 1）初始化（置空表） ——可由构造函数实现
（ 2）求表长（ Length ）
（ 3）查找或定位（ Find ）
（ 4）插入（ Insert ）
（ 5）删除（ Remove ）
（ 6）排序（ Sort ）
（ 7）判空（ IsEmpty）
2009-7-25 9
2.2 线性表的顺序存储结构要实现在计算机内表示一个数据结构，要解决两种信息的存贮问题：
数据元素本身的存贮数据元素之间关系的存贮定义,利用内存物理结构上的邻接特点，实现线性表的,一个跟着一个,这一序列关系的存贮方式，
称为线性表的顺序存贮结构，其上的线性表称为顺序表。
顺序表的类定义,利用数组作为顺序表的存储结构，
它被封装在类的私有域中
2009-7-25 10
template <class Type> class SeqList {
Public:
SeqList(int MaxSize=defaultSize);
~SeqList( ) {delete [ ] data;}
int Length( ) const {return last+1;}
int Find(Type & x) const;
int Insert(Type & x,int i);
int Remove(Type & x);
int IsEmpty( ) {return last = = - 1;}
int Isfull( ) {return last = =MaxSize – 1 ;}
Type & Get( int i ) {return i <0 || i >last? NULL,data[i];}
Private:
Type * data; // 用数组存放线性表 ——顺序存贮结构
int Maxsize; // 数组大小，但顺序表的长度为 last+1
int last; }// last 为表中最后元素的下标,last=-1 时表示空表
2009-7-25 11
上述顺序表定义中的数据成员 Maxsize 是为判断顺序表是否为满而设,last 是为便于判断顺序表是否为空、求表长、置空表而设：
last=Maxsize –1表示顺序表已满，此时再进行插入操作会导致上溢错误；
last=-1 表示顺序表为空表，此时再进行删除操作会导致下溢错误；
last+1 代表顺序表的表长；
将 last 赋值为 –1 可实现置空表操作。
由上可知：合理地设置数据成员可大大简化算法的设计及提高算法的效率。顺序表不仅仅包含存放其数据元素的数组，它还应包括一些有用的数据成员，以及相应的操作，它们是一个整体：
2009-7-25 12
顺序表之整体概念：
data
0
1
last
Maxsize
last
数组下标数组 变量 操作算法
Maxsize-1
初始化操作插入操作删除操作查找操作排序操作
.,,,,,.,,
.,
.
.,
.
2009-7-25 13
顺序表的基本操作（算法）
（ 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];
}
}
2009-7-25 14
（ 2）顺序表查找操作
template <class Type> int Seqlist<Type>::Find(Type & x)
const
//查找 x 在表中位置，若查找成功，函数返回 x 的位置
//否则返回－ 1
{
int i=0;
while(i<=last && data[i]!=x) i++;
if (i>last) return –1;
else return i;
}
2009-7-25 15
（ 3）顺序表插入操作为了把新元素 x 插入到 i 处，必须把从 i 到 last 的所有元素成块向后移动一个元素位置，以空出第 i 个位置供 x 插入：
x
23 1
先移动后面元素
0 i-1 i i+1 last.,,,,,
.,,,,,,,,
.,,
2009-7-25 16
template <class Type> int Seqlist<Type>::Insert(Type & x,
int i)
//将 x 插入表中 i 处，若成功返回 1,否则返回 0
{
if (i<0||i>last+1||last==Maxsize-1) return 0;
else
{
last++;
for(int j=last;j>i;j--) data[j]=data[j-1];
data[i]=x;
return 1;
}
}
2009-7-25 17
（ 4）顺序表删除操作为了删除第 i 个元素，必须把从 i＋ 1 到 last 的所有元素向前移动一个元素位置，把第 i 个元素覆盖掉：
1 2,,,
0 i-1 i i+1 last-1 last1
.,,,,,,,,
.,,,,,
2009-7-25 18
template <class Type> int Seqlist<Type>::Remove(Type & x)
//将 x 从表中删除。若 x 在表中并成功删除则返回 1，
//否则返回 0
{
int i=Find(x);
if (i>=0)
{
last--;
for (int j=i;j<=last;j++) data[j]=data[j+1];
return 1;
}
return 0;
}
2009-7-25 19
顺序存储结构的优缺点
优点：
（ 1）算法简单、可读性好、开发代价低
缺点：
（ 1）插入、删除操作时需要移动大量元素，
效率较低；
（ 2）最大表长难以估计，太大了浪费空间，
太小了容易溢出。
2009-7-25 20
顺序表应用举例当将两个顺序表作集合考虑时的,并,与,交,操作算法
template <class Type>
void Union(Seqlist <Type> & LA,Seqlist <Type> & LB)
// 合并顺序表 LA 与 LB,重复元素只留一个，结果在 LA 中。
{ int n=LA.Length();
int m=LB.Length();
for (int i=0;i<=m-1;i++)
{
Type x=LB.Get(i); // 从顺序表 LB 中取一元素
int k=LA.Find(x); // 在顺序表 LA 中查找该元素
if (k==-1) // 未找到
{ LA.Insert( x,n); // 将该元素追加到 LA 中
n++;
}
}
}
2009-7-25 21
template < class Type >
void Intersection( Seqlist <Type> & LA,Seqlist <Type> & LB)
// 求顺序表 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 中查找该元素
if ( k== - 1) // 未找到
{ LA.Remove( i ); n--;} // 则从 LA 中删除该元素
else i ++;
}
}
2009-7-25 22
多项式及其运算
A(x)=a0x + a1x +a2x +…+ an-1x + anx =
B(x)=b0x + b1x +b2x +…+ bn-1x +bnx =
A(x)+B(x)=
实际应用中，上述一元多项式中的很多系数有可能为零，
即为稀疏多项式，如下式所示：
Σ aix
i=0
n
i0 1 2 n-1 n
0 1 2 n-1 n Σ bixi
i=0
Σ (ai+bi)x
n
i=0
i
P (x)=1.2+51.3x +3.7x5
0
50 101
P(x)=Σci xi=0n ei
c0=1.2 e0=0
c1=51.3 e1=50
c2=3.7 e2=101
2009-7-25 23
多项式的表示对于稀疏多项式，采用二元组表示法可以大大节省存储空间：
（ 1）将稀疏多项式的每一项用二元组 < ci,ei >表示
——客体的表示方法
（ 2）用一顺序表（一维数组）来存放上述的二元组
——数据的组织方法
c0 c1 ci cn
e0 e1 ei en
系数指数
.,,.,,,,,
.
.
.,,
2009-7-25 24
多项式二元组的类定义 ——客体的表示方法
class Polynomial; // 多项式类的前视声明
class term // 多项式中项（二元组）的类定义
{
friend Polynomial; // 定义 Polynomial 类为 term 类的友元类
private,
float coef; // 系数
int exp; // 指数
}
2009-7-25 25
多项式的类定义 ——数据的表示方法
class Polynomial
{
public,
.,,// 成员函数声明（构造、释构、相加等函数）
private,
int MaxTerms ; //共享空间（顺序表）的最大项数
static term termArray[MaxTerms];
//存放二元组的数组，存放多个多项式的共享空间
static int free ; // 共享空间中自由空间之起始下标
int start,finish ; // 多项式在共享空间中的首、尾下标
}
2009-7-25 26
多项式的相加
A(x)=Σaix B(x)=Σbjx
C(x)=A(x)+B(x)
n m
i=0 j=0
e i e j
A,Start A,finish
B,Start B,finish
free MaxTerm-1
2009-7-25 27
多项式 A＋ B算法思路：
（ 1）保留 A,B两个多项式，将 A＋ B放人 C中；
（ 2）开始时 C.start = free；
（ 3）设置两个指针 a 和 b 分别作为 A 与 B 的检测指针，开始时分别指向 A 与 B 的首项，即：
a = A,start ; b = B,start；
（ 4）当两个指针都未超出相应多项式的最末位置时，比较它们所指示的对应项的指数：
若指数相等，则对应项系数相加，若相加结果不为零，则在
C 中加入一个新项若指数不等，则把指数小者拷贝到 C 中
（ 5）当两个指针中有一个超出了相应多项式的最末位置，则将另一个多项式的剩余部分拷贝到 C 中
2009-7-25 28
Polynomial Polynomial,,Add ( Polynomial B ) {
Polynomial C; int a = start; int b =B.start; C.start = free; float c;
while ( a <= finish && b <= B.finish )
switch ( compare(termArray[a].exp,termArray[b].exp )) {
case?=?,c= termArray[a].coef + termArray[b].coef ;
if (c) NewTerm( c,termArray[a].exp ) ;
a++ ; b++ ; break ;
case?>?,NewTerm( termArray[b].coef,termArray[b].exp);
b++ ; break ;
case?<‘,NewTerm( termArray[a].coef,termArray[a].exp);
a++ ; }
for ( ; a <= finish ; a++ )
NewTerm( termArray[a].coef,termArray[a].exp);
for ( ; b <= B.finish ; b++ )
NewTerm( termArray[b].coef,termArray[b].exp);
C.finish=free-1;
return C ; }
2009-7-25 29
void Polynomial,,NewTerm( float c,int e )
// 把一个新的项（二元组 < c,e >）追加到多项式 C(x) 中
{
if ( free >= MaxTerms )
{
cout << ―Too many terms in polynomials‖ << endl ;
return ;
}
termArray[ free ],coef = c ;
termArray[ free ],exp = e ;
free ++ ;
}
2009-7-25 30
作业：
定义多项式类的求表长、查找、插入、删除、判空表判满表、读取（第 i 个元素）等成员函数，并用这些函数实现前述的两个多项式的相加操作。
提示：
（ 1）定义查找指数相等的元素的成员函数
（ 2）仿照前述的顺序表合并操作算法，先从多项式 B 中读取一元素，在 A 中查找有无指数相等元素：
若无，则有序插入 A 中；
若有，则系数相加：
若和为零，则从 A 中删除相应元素；
否则用新系数构造新元素，并插入 A 中相应位置
2009-7-25 31
稀疏矩阵（ Sparse Matrix）－－数值计算中的顺序表设计
0 0 0 22 0 0 15
0 11 0 0 0 17 0
A = 0 0 0 -6 0 0 0
0 0 0 0 0 39 0
91 0 0 0 0 0 0
0 0 28 0 0 0 0
矩阵 A 是一个 6 行 7 列的稀疏矩阵，只有 8 个非零元素，
其他均为零。因此用二维数组来存储稀疏矩阵的空间利用率较低，必须考虑对稀疏矩阵的压缩存储表示。
2009-7-25 32
稀疏矩阵的三元组表示法：
（ 1）将稀疏矩阵的非零元素用三元组
< row,column,value > 表示（ 表示稀疏矩阵的第 row 行、第 column 列的值为 value）
——客体的表示方法
（ 2）用一顺序表（一维数组）来存放上述三元组
（每一个三元组即为顺序表的一个数据元素）
并按行优先顺序存放
——数据的组织方法
template < class Type > class Trituple
{ private,
int row,col;
Type value;
}
2009-7-25 33
矩阵 A的三元组表示：
表下标 行 (row) 列 (col) 值 (value)
0 0 3 22
1 0 6 15
2 1 1 11
3 1 5 17
4 2 3 -6
5 3 5 39
6 4 0 91
7 5 2 28
2009-7-25 34
稀疏矩阵的类声明：
template < class Type > class SparseMatrix
{ public:
SparseMatrix(int MaxTerms=defaultSize);
~SparseMatrix() {delete [ ] smArray;}
SparseMatrix<Type> Compression(smData<Type>);
SparseMatrix<Type> Transpose();
SparseMatrix<Type> Add(SparseMatrix <Type> b);
SparseMatrix<Type> Multiply(SparseMatrix<Type> b);
private:
int Rows,Cols,Terms,MaxTerms;
Trituple <Type> smArray[MaxTerms];
}
2009-7-25 35
说明：
（ 1）压缩前的稀疏矩阵为 Rows 行,Cols 列的矩阵
smData,压缩后的稀疏矩阵存放在一维数组
smArray 中，其中的元素为 Trituple 类型的对象。
声明中的 Terms 对应于顺序表定义中的 last，
MaxTerms 对应于顺序表定义中的 Maxsize，
smArray 对应于顺序表定义中的 data
（ 2）为稀疏矩阵声明了四种操作：
压缩（ Compression）
转置（ Transpose）
相加（ Add）
相乘（ Multiply）
根据实际需要还可以声明其他操作。
（ 3）数值计算与非数值计算的数据结构中所定义的基本操作有很大的不同
2009-7-25 36
稀疏矩阵的转置操作快速转置算法思路：
（ 1）引入两个辅助数组 rowSize[ ] 和 rowStart[ ]
rowSize [ i ]——表示稀疏矩阵第 i 列的非零元素个数
rowStart[ i ]——表示稀疏矩阵第 i 列的第一个（行号最小）
非零元素在转置矩阵的三元组表中的位置。
显然应有：
rowStart[ i ] + rowSize[ i ] = rowStart[ i+1 ]
.,,,,,,,,
共有 rowSize[ i ] 个元素
2009-7-25 37
上述公式表示，若已知稀疏矩阵第 i 列的第一个非零元素在转置矩阵的三元组表中的位置 rowStart [ i ],以及稀疏矩阵第 i 列的非零元素个数 rowSize [ i ],就可以算出第 i+1 列非零元素在转置矩阵的三元组表中的位置 rowStart [ i+1]
另外，根据转置矩阵的定义可知：
rowStart [ 0 ] = 0
因此：
rowStart [ 1 ] = rowSize [ 0 ] + rowStart [ 0 ] = rowSize [ 0 ]
rowStart [ 2 ] = rowSize [ 1 ] + rowStart [ 1 ]
.,,,,,
因此，只要预先统计得到 rowSize [ i ] ( i = 0,1,2,.,,)
就可以得到第 i + 1 列非零元素在转置矩阵的三元组表中的位置
2009-7-25 38
template <class Type> SparseMatrix<Type> SparseMatrix<Type>::
FastTranspos( )//
{ int *rowSize = new int[Cols]; int *rowStart = new int[Cols];
SparseMatrix<Type> b; b.Rows = Cols; b.Cols = Rows; b.Terms = Terms;
if (Terms > 0 ) {
for (int i = 0; i<Cols; i ++) rowSize[i] = 0;
for (i=0;i<Terms;i++) rowSize[smArray[i].col]++;
rowStart[0]=0;
for (i=1;i<Cols;i++) rowStart[i]=rowStart[i-1]+rowSize[i-1];
for (i=0;i<Terms;i++){
int j=rowStart[smArray[i].col];
b.smArray[j].row=smArray[i].col;
b.smArray[j].col=smArray[i].row;
b.smArray[j].value=smArray[i].value;
rowStart[smArray[i].col]++;}
}
delete [] rowSize; delete [] rowStart; return b;
}
2009-7-25 39
2。 5 字符串定义,字符串（简称为串） 是 n ( n >= 0 ) 个字符的有限序列通常可记为：
S=? a0 a1 a2 … an-1 ‘
其中,串名 ——S
串值 ——引号中的内容
n——串长，即串中的字符个数（不包括串结束符 ‘ \0 ‘ ）
空串 ——n = 0 的串（但包含串结束符）
空白串 ——仅由若干个空格字符组成的串，其长度不为零子串 ——从非空串中连续取出的若干个字符组成的串子串的位置 ——子串的第 0个字符在原串中的位置可以认为：串是限制数据元素为字符的顺序表
2009-7-25 40
2.5.1 字符串抽象数据类型和类定义
class String{
public:
String(const String &);String(const char *const);String();
~String() {delete [ ] ch;}
int Length() const {return curLen； }
String & operator()(int pos,int len);
int operator ==(const String & ob) const {return strcmp(ch,ob.ch)==0;}
int operator !=(const String & ob) const{return strcmp(ch,ob.ch)!=0;}
int operator ! () const {return curLen==0； }
String & operator = (const String &);
String & operator += (const String &);
char & operator [ ] (int i );
int Find(String pat) const;
private:
int curLen;
char * ch;
}
2009-7-25 41
有了上述的串类定义，就可以进行下列操作：
String s1;
String s2 ( ― Hello World ‖ );
s1 = s2;
String s3 ( ― ; nice to here ! ‖ );
s1 + = s3;
int len=s1.length();
String s4;
s4=s1(6,5);
If (s1==s2)…
If (s1!=s2)…
If (! s1)…
Char c=s1[6];
s1[6]=?w‘;
2009-7-25 42
文本编辑计算机应用中要涉及大量的文本文件，文本文件由大量的串
（行）组成，在某些文本文件（如源程序）中，串（行）长差异很大，若每行都用等长的串来存贮，则会浪费存贮空间解决的办法之一是建立一个很大的字符数组作为所有串的共享空间 ——串值共享空间，再为每个串建立一个描述子，用于描述该串的长度以及该串在串值共享空间中的位置等信息，并将这些描述子存入一顺序表中，参见下图：
2009-7-25 43
行表 (linelist) 串值共享空间（ space） MaxSize-1
..
.,free
行号
0
1
2
3
行长 位置 行 2 行 3 行 0 行 1,,,
.,
.,
.,
.,
自由空间起始地址
0
串值共享空间 ——String（串）
行表 ——Seqlist（顺序表）
设计行内字符插入、删除操作算法设计整行插入、删除操作算法
2009-7-25 44
第三章 链表顺序表有下列缺点：
（ 1）插入、删除操作时需要移动大量元素，
效率较低；
（ 2）最大表长难以估计，太大了浪费空间，
太小了容易溢出。
因此，在插入和删除操作是经常性操作的应用场合选用顺序存储结构不太合适，此时可以选用链式存储结构。
定义：用指针来表示数据元素之间关系的存储结构称之为链式存储结构。
2009-7-25 45
定义：用由指针连接起来的一串结点来存储一个线性表的存储结构称为线性链式存储结构，简称链表。
当每一结点中只有一个指针，并用来表示一个数据元素到其后继元素之间的接续关系，则称这种存储结构为单链表。
注：此处的结点是指通过指针型变量动态索取到的存储空间
.,,^first
first——头指针 指针域 (link) last
last ——尾指针 数据元素域 (data)
^ ——空指针结点 1头结点 结点 0 结点 n-1
e0 e1 en-1
2009-7-25 46
上述的单链表表头设置了一头结点，头结点的数据域中可以为空，或者存放一些辅助数据。
设置头结点的目的是为了简化对空表的特殊处理，
使得算法更简单、更有效。
对于带头结点的单链表，可以很容易地表示空链表：
头指针 头结点
first ^
last尾指针
2009-7-25 47
用模板定义的单链表类
template <class Type> class List; //单链表类的前视声明
template <class Type> class ListNode{ //链表结点类的定义
friend class List <Type>; //将 List 类定义为 ListNode 类的友元
public:
ListNode( );
ListNode(const Type & item);
ListNode <Type> *NextNode ( ) {return link;}//后继结点指针
void InsertAfter (ListNode <Type> * p);
//将 *p 结点插入到当前结点之后
ListNode <Type> * GetNode (const Type & item,
ListNode <Type> * next); //创建一个新结点
ListNode <Type> * RemoveAfter ( ); //删除后继结点
private:
Type data;
ListNode <Type> * link;
}
data link
2009-7-25 48
template <class Type> class List//单链表类的定义
{
public:
List( ) {last=first=new ListNode<Type> (value,NULL);}
//构造函数，建立一个空链表
~List( );
void MakeEmpty( );//删除所有元素结点，将链表置为空链表
int Length( ) const; //求单链表表长
ListNode<Type> *Find(Type value); //查找值为 value 的结点
ListNode<Type> *Find(int i); //查找结点 i,返回结点 i 的指针
int Insert(Type value,int i);
//将值为 value 的新结点插入结点 i 之前
Type *Remove(int i); //删除结点 i
Type Get(int i); //读取结点 i 的值
private:
ListNode<Type> *first,*last; //头指针，尾指针
}
2009-7-25 49
ListNode<Type>类（链表结点类）的成员函数的实现
template <class Type> void ListNode<Type>::
ListNode( ):link(NULL){}
template <class Type> void ListNode<Type>::
ListNode(const Type & item)
//构造函数，创建一个新结点，该结点的值为 item,指针域为 NULL
{
data=item;
link=NULL;
}
template <class Type> ListNode<Type> * ListNode<Type>::
GetNode(const Type & item,ListNode<Type> * next=NULL)
//创建一个新结点，该结点的值为 item,指针域为 NULL,并返回
//该结点的指针
{
ListNode<Type> *newnode=new ListNode<Type>(item,next);
return newnode;
}
2009-7-25 50
InsertAfter( ) 函数
template <class Type> void ListNode<Type>::
InsertAfter(ListNode<Type> *p)
{将 p 所指的结点（ *p）链接成为当前结点（ *this）的后继结点
p->link=link; //(1)
link=p; //(2)
}
this
data link data link …
data linkp
p->link=linklink=p
…
(1)(2)
当前结点
2009-7-25 51
RemoveAfter( )
data link data link data link
当前结点 要删除的结点
template <class Type> ListNode<Type> *ListNode<Type>::
RemoveAfter()//删除当前结点 ( *this ) 的后继结点,并返回该结点的指针
{ ListNode<Type> *tempptr=link; //(1)
if (link==NULL) return NULL;
link=tempptr->link; //(2)
return tempptr;
}
：
(1)tempptr=link
(2) link=tempptr->link
this
2009-7-25 52
List<Type>类（链表类）的成员函数的实现
template <class Type> void List<Type>::MakeEmpty( )
{// 将当前链表置为空表
ListNode<Type> *q ;
while (first ->link != NULL)
// 循环删除头结点的后继结点，直到无后继结点为止
{q=first ->link ; first ->link=q ->link ; delete q ;}
last=first;// 最后让 last 指向头结点，完成置空表操作
}
first …
(1) q=first->link
(2) first->link=q->link
(最后 )
last
头结点
2009-7-25 53
template <class Type> int List<Type>::Insert(Type value,int i);
{// 将值为 value 的新数据元素插入到链表中结点 i 之前
ListNode<Type> *p = Find(i-1);// 查找结点 i-1
if (p==NULL) return 0;// 结点 i-1 不存在，插入失败
ListNode<Type> *newnode=GetNode(value,p->link);// 创建新结点
// 并使新结点指向结点 i (1)
if (p->link==NULL) last=newnode;// 若结点 i 不存在，则新结点将
// 是表尾结点
p->link=newnode;// 让结点 i-1 指向新结点，实现插入 (2)
return 1;
} … …结点 i-1 结点 i
新结点
p
newnode
(1)
(2)
2009-7-25 54
template <class Type> Type *List<Type>,,Remove( int i )
{// 删除结点 i,若成功，则返回该结点的数据元素（地址），
// 否则返回 NULL
ListNode<Type> *p= Find(i-1),*q ; // 查找结点 i-1
if ( p==NULL || p->link==NULL) return NULL;// 若结点 i-1 或者
// 结点 i 不存在，则返回 NULL,删除失败
q=p->link; // (1)
p->link=q->link;// (2)
Type value=q->data;
if (q==last) last=p;
delete q;
return &value;
}
… …结点 i-1 结点 i 结点 i+1
p q
(1)
(2)
2009-7-25 55
template <class Type> ListNode<Type> *List<Type>::Find( int i )
{ // 查找结点 i,若找到，则返回该结点的指针，否则返回 NULL
if ( i <-1 ) return NULL;
if ( i == -1 ) return first;// 结点 –1 即为头结点
ListNode<Type> *p=first->link;// p 指向结点 0
int j=0;
while(p!= NULL && j<i ) // 从结点 0 开始顺序向后查找，若第一个
// 条件不成立，即 p=NULL,则说明 i 值太大，查找失败；
// 若第二个条件不成立，则存在结点 i,查找成功,p 即为指向该结
// 点的指针
{ p=p->link;
j=j++;
}
return p;
}
2009-7-25 56
3.1.6 单链表的游标 (Iterator)类在实际应用中经常要对单链表进行打印、统计、检索等需要向后搜索整个链表的操作，因此设计具有光标功能的，能够记住当前位置并能得到其后继结点的游标类是有意义的。
单链表的位置概念,current 是结点 i+1的位置有了单链表结点 i+1 的位置 current,删除结点 i+1 或在结点 i+1 前插入新结点就会简单得多，无需查找过程。
… …
current
结点 i 结点 i+1
2009-7-25 57
单链表游标类声明
Template <class Type> class ListIterator
{ public:
ListIterator(const List<Type> & l),list(l),current(l.first) { }
Boolean NotNull( ); // 检查游标结点（指针 current
// 所指的结点）是否为不空
Boolean NextNotNull ( ); // 检查游标结点的后继结点是
//否为不空
Type * First ( );//使游标指向头结点
Type * Next ( ); // 使游标指向后继结点
private:
const List<Type> & list;
ListNode<Type> * current;//游标（指针）
}
2009-7-25 58
单链表游标类成员函数的定义
template <class Type> Boolean ListIterator<Type>::NotNull( )
{// 检查游标结点（ current 所指的结点）是否为不空（注：
//此处结点不空是指该结点的指针不空）。若不空，则返回真，
// 否则返回假
if ( current != NULL ) return True;
else return False;
}
template <class Type> Boolean ListIterator<Type>::NextNotNull( )
{// 检查游标结点（游标所指的结点）的后继结点是否为不空。
// 若不空，则返回真；否则返回假
if ( current != NULL && current->link != NULL ) return True;
else return False;
}
2009-7-25 59
template <class Type> ListNode<Type> * ListIterator<Type>::First( )
{// 使游标指向头结点
if ( list.first->link != NULL ） current = list.first; // 若头结点的指针
//域不空，即链表为非空表,则使游标指向头结点
else current = NULL; // 否则置空游标
return current;
}
template <class Type> ListNode<Type> * ListIterator<Type>::Next( )
{// 使游标指向后继结点
if ( current != NULL && current->link != NULL )
current=current->link;// 若游标结点及其后继结点都不空，则
// 将游标指向后继结点
else current=NULL;// 否则置空游标
return current;
}
2009-7-25 60
游标类应用举例：
int sum ( const List <int> &l )
//计算 int 型单链表 l 的累加和
{
ListIterator<int> li(l);//定义一个单链表对象 l 及其游标类对象 li,并
//将游标指向单链表的头结点（由构造函数实现）
if ( ! li.nextNotNull()) return 0;//空链表，返回 0
int retvalue=*li.First();//读取头结点的值，假定头结点的值为 0
while ( li.nextNotNull()) retvalue += *li.Next();
//若存在后继结点，则循环累加
return retvalue;
}
课堂作业：
使用游标类求 int 型单链表的最大结点。若单链表为空则返回 NULL，
否则返回最大结点的位置。
2009-7-25 61
3.2 循环链表（ Circular List）
e0 e1 en-1
循环链表的定义,（ P82－ P83）
循环链表与单链表不同的是链表中表尾结点的 link 域不是 NULL，而是链表头结点的指针（链表指针）
…first
last
表头结点
first
last
空表
2009-7-25 62
循环链表（带头结点）的类定义：
enum Boolean {False,True}
template <class Type> class CircList;//循环链表类的前视声明
template <class Type> class CircListNode
{//循环链表结点的类定义
public:
CircListNode (Type d=0,CircListNode<Type> * next=NULL):
data ( d ),link ( next ) { }//构造函数，创建一个循环
//链表结点，并初始化数据域为 d,指针域为 NULL
private:
Type data;
CircListNode < Type > * link;
}
data link
2009-7-25 63
template <class Type> class CircList
{ public:
CircList ( Type value );
~CircList ( );
int Length ( ) const;
Boolean IsEmpty ( ) { return first->link == first; }
Boolean Find ( const Type & value );
Type GetData ( ) const;//读取游标结点（ *current )的数据域
void Firster ( ) { current=first; }//将 current 指向头结点
Boolean First ( );//将 current 指向第一个元素结点（ e0）
Boolean Next ( );//将 current 指向后继结点
Boolean Prior ( );//将 current 指向前驱结点？
void Insert ( const Type & value );//在游标结点后插入新结点
void Remove ( );//删除游标结点的后继结点
private:
CircListNode<Type> * first,* current,* last ;
//头指针，游标，尾指针
}
2009-7-25 64
作业：
（ 1）比较单链表及其游标类与循环链表类的定义的不同
（ 2）考察循环链表中游标功能的实现方法
（ 3）模仿循环链表的类定义，重新定义单链表的类，使其具有游标功能，并设计新单链表的各成员函数自学,3.3 多项式及其相加
2009-7-25 65
双向链表（ Doubly Linked List）
如果在一个应用问题中经常要求检测指针向前驱和后继方向移动，
为保证移动的时间复杂度达到最小，就必须采用双向链表表示。
双向链表的结点结构：
前驱结点 后继结点
template <class Type> class DblNode
{
private:
Type data;
DblNode <Type> * lLink,* rLink;
}
lLink data rLink
左链指针 右链指针数据
2009-7-25 66
带头结点的双向 循环链表,
空表游标结点,* current
游标结点的前驱结点,* ( current -> lLink )
游标结点的后继结点,* ( current -> rLink )
e0 e1 en-1…
current
first
first
2009-7-25 67
双向循环链表的类定义：
template <class Type> class DblList
{
public:
DblList ( Type uniqueVal );
~DblList ( );
int Length ( ) const;
int IsEmpty ( ) { return first->rLink==first ;}
int Find ( const Type & target );
Type getData ( ) const;
void Firster ( ) { current = first; }
int First ( );
int Next ( );
int Prior ( );
int operator ! ( ) { return current != NULL;}
void Insert ( const Type & value );
void Remove ( ) ;
private:
DblNode <Type> * first,* current;
}
2009-7-25 68
2009-7-25 69
2009-7-25 70
2009-7-25 71
2009-7-25 72
2009-7-25 73
2009-7-25 74
2009-7-25 75
2009-7-25 76
2009-7-25 77
2009-7-25 78
2009-7-25 79
2009-7-25 80
2009-7-25 81
2009-7-25 82
2009-7-25 83
2009-7-25 84
2009-7-25 85
2009-7-25 86
2009-7-25 87
2009-7-25 88
2009-7-25 89
2009-7-25 90
2009-7-25 91
2009-7-25 92
2009-7-25 93
2009-7-25 94
2009-7-25 95
2009-7-25 96
2009-7-25 97
2009-7-25 98
2009-7-25 99
2009-7-25 100
2009-7-25 101
2009-7-25 102
2009-7-25 103
2009-7-25 104
2009-7-25 105
2009-7-25 106
2009-7-25 107
2009-7-25 108
2009-7-25 109
2009-7-25 110
2009-7-25 111
2009-7-25 112
2009-7-25 113
2009-7-25 114
2009-7-25 115
2009-7-25 116
