2011-7-18 1
数据结构及其应用
（用面向对象方法与 C＋＋描述）
2011-7-18 2
第一章 概述
研究对象,信息的表示方法、数据的组织方法、操作算法设计
意义地位,数据结构＋算法＝程序
程序设计的基础
系统软件的核心
发展过程,数值计算 非数值计算
建立数学模型 客体及其关系的表示
设计数值计算方法 数据的组织
操作算法的设计
非数值计算应用的发展，促进了数据结构
的研究和发展以及其体系的完善。
2011-7-18 3
基本术语
? 数 据,描述客观事物的且能由计算机处理的数
值、字符等符号
? 数据元素,数据的基本单位，在计算机程序中通常
作为一个整体进行考虑和处理（记录、
结点、表目、元素）
? 数 据 项,数据元素的某一属性。数据元素可以由
若干数据项组成，数据项可以由若干
更小的款项（组合项、原子项）组成。
数据项又称域、字段
? 关 键 码,能起唯一标识（数据元素）作用的数据项
? 数据结构,一组同类的数据元素、其间的关系及其上的
一组操作所构成的整体，称为一个数据结构
2011-7-18 4
数据结构的描述方式
? 逻辑结构,是对数据元素之间逻辑关系（抛开具体
的关系含义以及存储方式等）的描述，它可以用一个
数据元素的集合和定义在此集合上的几个关系来表示。
通常可用图形表示，圆圈表示数据元素，箭头表示关
系：
? 物理结构,数据结构在计算机中的具体表示和实现，
又称存储结构
E i E i+1
数据元素 数据元素
关系
2011-7-18 5
数据结构的分类
? 按逻辑结构分类：
纯集合型结构,数据元素之间除了, 同属于一个集合, 这
一
关系外，别无其他关系
线性结构,数据元素之间存在, 一个跟着一个, 的序列关
系
树型结构,数据元素之间存在, 每个元素只能跟着一个元
素
但可以有多个元素跟着它, 的层次关系
图状结构,任意两个数据元素之间都可能存在关系
? 按存储结构分类：
顺序存储结构
链式存储结构
索引存贮结构
2011-7-18 6
基本操作,任一数据结构均有一组相应的基本操作，
有时操作不同，用途迥异（如栈和队列）
常用的基本操作有插入,删除、查找、
更新、排序等
算 法,算法是为了解决给定的问题而规定的一个
有限长的操作步骤序列，则重于解决问题
的方法和步骤。当算法由计算机语言表示
时称为程序（代码）
算法设计目标,可维护性
可靠性（正确性、健壮行）
可读性
高效率（时间、空间）
2011-7-18 7
第二章 线性表
2。 1 线性表的逻辑结构
定义, 由相同种类的数据元素组成的一个有穷
序列称为一个线性表。, 一个跟着一个,
符号表示法,L＝（ e1,e2,… en）
图形表示法：
e2 ene1
2011-7-18 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）
2011-7-18 9
2.2 线性表的顺序存储结构
要实现在计算机内表示一个数据结构，要解决两
种信息的存贮问题：
数据元素本身的存贮
数据元素之间关系的存贮
定义,利用内存物理结构上的邻接特点，实现线性表
的, 一个跟着一个, 这一序列关系的存贮方式，
称为线性表的顺序存贮结构，其上的线性表称
为顺序表。
顺序表的类定义,利用数组作为顺序表的存储结构，
它被封装在类的私有域中
2011-7-18 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 时表示空表
2011-7-18 11
上述顺序表定义中的数据成员 Maxsize 是为判断顺序
表是否为满而设,last 是为便于判断顺序表是否为空、求
表长、置空表而设：
last=Maxsize –1表示顺序表已满，此时再进行插入
操作会导致上溢错误；
last=-1 表示顺序表为空表，此时再进行删除操作
会导致下溢错误；
last+1 代表顺序表的表长；
将 last 赋值为 –1 可实现置空表操作。
由上可知：合理地设置数据成员可大大简化算法的设计
及提高算法的效率。顺序表不仅仅包含存放其数据元
素的数组，它还应包括一些有用的数据成员，以及相
应的操作，它们是一个整体：
2011-7-18 12
顺序表之整体概念：
data
0
1
last
Maxsize
last
数组下标
数组 变量 操作算法
Maxsize-1
初始化操作
插入操作
删除操作
查找操作
排序操作
.,,,,,.,,
.,
.
.,
.
2011-7-18 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];
}
}
2011-7-18 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;
}
2011-7-18 15
（ 3）顺序表插入操作
为了把新元素 x 插入到 i 处，必须把从 i 到 last 的所
有元素成块向后移动一个元素位置，以空出第 i 个位
置供 x 插入：
x
23 1
先移动后面元素
0 i-1 i i+1 last.,,,,,
.,,,,,,,,
.,,
2011-7-18 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;
}
}
2011-7-18 17
（ 4）顺序表删除操作
为了删除第 i 个元素，必须把从 i＋ 1 到 last 的所有元素
向前移动一个元素位置，把第 i 个元素覆盖掉：
1 2,,,
0 i-1 i i+1 last-1 last1
.,,,,,,,,
.,,,,,
2011-7-18 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;
}
2011-7-18 19
顺序存储结构的优缺点
? 优点：
（ 1）算法简单、可读性好、开发代价低
? 缺点：
（ 1）插入、删除操作时需要移动大量元素，
效率较低；
（ 2）最大表长难以估计，太大了浪费空间，
太小了容易溢出。
2011-7-18 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++;
}
}
}
2011-7-18 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 ++;
}
}
2011-7-18 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
2011-7-18 23
多项式的表示
对于稀疏多项式，采用二元组表示法可以大大节省存储
空间：
（ 1）将稀疏多项式的每一项用二元组 < ci,ei >表示
——客体的表示方法
（ 2）用一顺序表（一维数组）来存放上述的二元组
——数据的组织方法
c0 c1 ci cn
e0 e1 ei en
系数
指数
.,,.,,,,,
.
.
.,,
2011-7-18 24
多项式二元组的类定义 ——客体的表示方法
class Polynomial; // 多项式类的前视声明
class term // 多项式中项（二元组）的类定义
{
friend Polynomial; // 定义 Polynomial 类为 term 类的友元类
private,
float coef; // 系数
int exp; // 指数
}
2011-7-18 25
多项式的类定义 ——数据的表示方法
class Polynomial
{
public,
.,, // 成员函数声明（构造、释构、相加等函数）
private,
int MaxTerms ; //共享空间（顺序表）的最大项数
static term termArray[MaxTerms];
//存放二元组的数组，存放多个多项式的共享空间
static int free ; // 共享空间中自由空间之起始下标
int start,finish ; // 多项式在共享空间中的首、尾下标
}
2011-7-18 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
2011-7-18 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 中
2011-7-18 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 ; }
2011-7-18 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 ++ ;
}
2011-7-18 30
作业：
定义多项式类的求表长、查找、插入、删除、判空
表判满表、读取（第 i 个元素）等成员函数，并用这些
函数实现前述的两个多项式的相加操作。
提示：
（ 1）定义查找指数相等的元素的成员函数
（ 2）仿照前述的顺序表合并操作算法，先从多项式 B 中
读取一元素，在 A 中查找有无指数相等元素：
若无，则有序插入 A 中；
若有，则系数相加：
若和为零，则从 A 中删除相应元素；
否则用新系数构造新元素，并插入 A 中相应位置
2011-7-18 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 个非零元素，
其他均为零。因此用二维数组来存储稀疏矩阵的空间
利用率较低，必须考虑对稀疏矩阵的压缩存储表示。
2011-7-18 32
稀疏矩阵的三元组表示法：
（ 1）将稀疏矩阵的非零元素用三元组
< row,column,value > 表示（ 表示稀疏矩阵的
第 row 行、第 column 列的值为 value）
——客体的表示方法
（ 2）用一顺序表（一维数组）来存放上述三元组
（每一个三元组即为顺序表的一个数据元素）
并按行优先顺序存放
——数据的组织方法
template < class Type > class Trituple
{ private,
int row,col;
Type value;
}
2011-7-18 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
2011-7-18 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];
}
2011-7-18 35
说明：
（ 1）压缩前的稀疏矩阵为 Rows 行,Cols 列的矩阵
smData,压缩后的稀疏矩阵存放在一维数组
smArray 中，其中的元素为 Trituple 类型的对象。
声明中的 Terms 对应于顺序表定义中的 last，
MaxTerms 对应于顺序表定义中的 Maxsize，
smArray 对应于顺序表定义中的 data
（ 2）为稀疏矩阵声明了四种操作：
压缩（ Compression）
转置（ Transpose）
相加（ Add）
相乘（ Multiply）
根据实际需要还可以声明其他操作。
（ 3）数值计算与非数值计算的数据结构中所定义的基
本操作有很大的不同
2011-7-18 36
稀疏矩阵的转置操作
快速转置算法思路：
（ 1）引入两个辅助数组 rowSize[ ] 和 rowStart[ ]
rowSize [ i ]——表示稀疏矩阵第 i 列的非零元素个数
rowStart[ i ]——表示稀疏矩阵第 i 列的第一个（行号最小）
非零元素在转置矩阵的三元组表中的位置。
显然应有：
rowStart[ i ] + rowSize[ i ] = rowStart[ i+1 ]
.,,,,,,,,
共有 rowSize[ i ] 个元素
2011-7-18 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 列非零元素在转置矩阵的三元组表中的位置
2011-7-18 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;
}
2011-7-18 39
2。 5 字符串
定义,字符串（简称为串） 是 n ( n >= 0 ) 个字符的有限序列
通常可记为：
S= ? a0 a1 a2 … an-1 ‘
其中,串名 ——S
串值 ——引号中的内容
n——串长，即串中的字符个数（不包括串结束符 ‘ \0 ‘ ）
空串 ——n = 0 的串（但包含串结束符）
空白串 ——仅由若干个空格字符组成的串，其长度不为零
子串 ——从非空串中连续取出的若干个字符组成的串
子串的位置 ——子串的第 0个字符在原串中的位置
可以认为：串是限制数据元素为字符的顺序表
2011-7-18 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;
}
2011-7-18 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‘;
2011-7-18 42
文本编辑
计算机应用中要涉及大量的文本文件，文本文件由大量的串
（行）组成，在某些文本文件（如源程序）中，串（行）长差异
很大，若每行都用等长的串来存贮，则会浪费存贮空间
解决的办法之一是建立一个很大的字符数组作为所有串的共
享空间 ——串值共享空间，再为每个串建立一个描述子，用于描
述该串的长度以及该串在串值共享空间中的位置等信息，并将这
些描述子存入一顺序表中，参见下图：
2011-7-18 43
行表 (linelist) 串值共享空间（ space） MaxSize-1
..
.,free
行
号
0
1
2
3
行长 位置 行 2 行 3 行 0 行 1,,,
.,
.,
.,
.,
自由空间起始地址
0
串值共享空间 ——String（串）
行表 ——Seqlist（顺序表）
设计行内字符插入、删除操作算法
设计整行插入、删除操作算法
2011-7-18 44
第三章 链表
顺序表有下列缺点：
（ 1）插入、删除操作时需要移动大量元素，
效率较低；
（ 2）最大表长难以估计，太大了浪费空间，
太小了容易溢出。
因此，在插入和删除操作是经常性操作的应用场合
选用顺序存储结构不太合适，此时可以选用链式存储结
构。
定义：用指针来表示数据元素之间关系的存储结构
称之为链式存储结构。
2011-7-18 45
定义：用由指针连接起来的一串结点来存储一个线性表
的存储结构称为线性链式存储结构，简称链表。
当每一结点中只有一个指针，并用来表示一个数
据元素到其后继元素之间的接续关系，则称这种
存储结构为单链表。
注：此处的结点是指通过指针型变量动态索取到的存储空间
.,, ^first
first——头指针 指针域 (link) last
last ——尾指针 数据元素域 (data)
^ ——空指针
结点 1头结点 结点 0 结点 n-1
2011-7-18 46
上述的单链表表头设置了一头结点，头结点的数据
域中可以为空，或者存放一些辅助数据。
设置头结点的目的是为了简化对空表的特殊处理，
使得算法更简单、更有效。
对于带头结点的单链表，可以很容易地表示空链表：
头指针 头结点
first ^
last尾指针
2011-7-18 47
用模板定义的单链表类
template <class Type> class List;
template <class Type> class ListNode{
friend class List <Type>;
public:
ListNode( );
ListNode(const Type & item);
ListNode <Type> *NextNode ( ) {return link;}
void InsertAfter (ListNode <Type> * p);
ListNode <Type> * GetNode (const Type & item,
ListNode <Type> * next);
ListNode <Type> * RemoveAfter ( );
private:
Type data;
ListNode <Type> * link;
}
2011-7-18 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);
ListNode<Type> *Find(int i);
int Insert(Type value,int i);
Type *Remove(int i);
Type *Get(int i);
private:
ListNode<Type> *first,*last;
}
2011-7-18 49
ListNode<Type>类（链表结点类）的成员函数的实现
template <class Type> void ListNode<Type>::ListNode( ):link(NULL){}
template <class Type> void ListNode<Type>::
ListNode(const Type & item),data (item),link(NULL){}
template <class Type> void ListNode<Type>::
InsertAfter(ListNode<Type> *p){p->link=link;link=p;}
template <class Type> ListNode<Type> *ListNode<Type>::
GetNode(const Type & item,ListNode<Type> *next=NULL){
ListNode<Type> *newnode=new ListNode<Type>(item,next);
Return newnode;}
template <class Type> ListNode<Type> *ListNode<Type>::
RemoveAfter(){ListNode<Type> *tempptr=link;
If(link==NULL) return NULL;
link=tempptr->link;return tempptr;}
2011-7-18 50
Void InsertAfter(ListNode<Type) *p):
功能：将 p 所指的结点（ *p）链接成为当前结点（ *this）
的后继结点
this
data link data link …
data linkp
p->link=linkLink=p
…
(1)(2)
当前结点
2011-7-18 51
RemoveAfter( )
data link data link data link
当前结点 要删除的结点
功能：删除当前结点 ( *this ) 的后继结点,并返回该结点的指针。
(1)tempptr
(2) link=tempptr->link
this
tempptr->link
2011-7-18 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
头结点
2011-7-18 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)
2011-7-18 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)
2011-7-18 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;
}
2011-7-18 56
3.1.6 单链表的游标 (Iterator)类
2011-7-18 57
单链表游标类声明
Template <class Type> class ListIterator
{
public:
ListIterator(const List<Type> & l):
list(l),current(l.first) { }
Boolean NotNull( );
Boolean NextNotNull ( );
Type * First ( );
Type * Next ( );
private:
const List<Type> & list;
ListNode<Type> * current;
}
2011-7-18 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;
}
2011-7-18 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;
}
2011-7-18 60
2011-7-18 61
2011-7-18 62
2011-7-18 63
2011-7-18 64
2011-7-18 65
2011-7-18 66
2011-7-18 67
2011-7-18 68
2011-7-18 69
2011-7-18 70
2011-7-18 71
2011-7-18 72
2011-7-18 73
2011-7-18 74
2011-7-18 75
2011-7-18 76
2011-7-18 77
2011-7-18 78
2011-7-18 79
2011-7-18 80
2011-7-18 81
2011-7-18 82
2011-7-18 83
2011-7-18 84
2011-7-18 85
2011-7-18 86
2011-7-18 87
2011-7-18 88
2011-7-18 89
2011-7-18 90
2011-7-18 91
2011-7-18 92
2011-7-18 93
2011-7-18 94
2011-7-18 95
2011-7-18 96
2011-7-18 97
2011-7-18 98
2011-7-18 99
2011-7-18 100
2011-7-18 101
2011-7-18 102
2011-7-18 103
2011-7-18 104
2011-7-18 105
2011-7-18 106
2011-7-18 107
2011-7-18 108
2011-7-18 109
2011-7-18 110
2011-7-18 111
2011-7-18 112
2011-7-18 113
数据结构及其应用
（用面向对象方法与 C＋＋描述）
2011-7-18 2
第一章 概述
研究对象,信息的表示方法、数据的组织方法、操作算法设计
意义地位,数据结构＋算法＝程序
程序设计的基础
系统软件的核心
发展过程,数值计算 非数值计算
建立数学模型 客体及其关系的表示
设计数值计算方法 数据的组织
操作算法的设计
非数值计算应用的发展，促进了数据结构
的研究和发展以及其体系的完善。
2011-7-18 3
基本术语
? 数 据,描述客观事物的且能由计算机处理的数
值、字符等符号
? 数据元素,数据的基本单位，在计算机程序中通常
作为一个整体进行考虑和处理（记录、
结点、表目、元素）
? 数 据 项,数据元素的某一属性。数据元素可以由
若干数据项组成，数据项可以由若干
更小的款项（组合项、原子项）组成。
数据项又称域、字段
? 关 键 码,能起唯一标识（数据元素）作用的数据项
? 数据结构,一组同类的数据元素、其间的关系及其上的
一组操作所构成的整体，称为一个数据结构
2011-7-18 4
数据结构的描述方式
? 逻辑结构,是对数据元素之间逻辑关系（抛开具体
的关系含义以及存储方式等）的描述，它可以用一个
数据元素的集合和定义在此集合上的几个关系来表示。
通常可用图形表示，圆圈表示数据元素，箭头表示关
系：
? 物理结构,数据结构在计算机中的具体表示和实现，
又称存储结构
E i E i+1
数据元素 数据元素
关系
2011-7-18 5
数据结构的分类
? 按逻辑结构分类：
纯集合型结构,数据元素之间除了, 同属于一个集合, 这
一
关系外，别无其他关系
线性结构,数据元素之间存在, 一个跟着一个, 的序列关
系
树型结构,数据元素之间存在, 每个元素只能跟着一个元
素
但可以有多个元素跟着它, 的层次关系
图状结构,任意两个数据元素之间都可能存在关系
? 按存储结构分类：
顺序存储结构
链式存储结构
索引存贮结构
2011-7-18 6
基本操作,任一数据结构均有一组相应的基本操作，
有时操作不同，用途迥异（如栈和队列）
常用的基本操作有插入,删除、查找、
更新、排序等
算 法,算法是为了解决给定的问题而规定的一个
有限长的操作步骤序列，则重于解决问题
的方法和步骤。当算法由计算机语言表示
时称为程序（代码）
算法设计目标,可维护性
可靠性（正确性、健壮行）
可读性
高效率（时间、空间）
2011-7-18 7
第二章 线性表
2。 1 线性表的逻辑结构
定义, 由相同种类的数据元素组成的一个有穷
序列称为一个线性表。, 一个跟着一个,
符号表示法,L＝（ e1,e2,… en）
图形表示法：
e2 ene1
2011-7-18 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）
2011-7-18 9
2.2 线性表的顺序存储结构
要实现在计算机内表示一个数据结构，要解决两
种信息的存贮问题：
数据元素本身的存贮
数据元素之间关系的存贮
定义,利用内存物理结构上的邻接特点，实现线性表
的, 一个跟着一个, 这一序列关系的存贮方式，
称为线性表的顺序存贮结构，其上的线性表称
为顺序表。
顺序表的类定义,利用数组作为顺序表的存储结构，
它被封装在类的私有域中
2011-7-18 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 时表示空表
2011-7-18 11
上述顺序表定义中的数据成员 Maxsize 是为判断顺序
表是否为满而设,last 是为便于判断顺序表是否为空、求
表长、置空表而设：
last=Maxsize –1表示顺序表已满，此时再进行插入
操作会导致上溢错误；
last=-1 表示顺序表为空表，此时再进行删除操作
会导致下溢错误；
last+1 代表顺序表的表长；
将 last 赋值为 –1 可实现置空表操作。
由上可知：合理地设置数据成员可大大简化算法的设计
及提高算法的效率。顺序表不仅仅包含存放其数据元
素的数组，它还应包括一些有用的数据成员，以及相
应的操作，它们是一个整体：
2011-7-18 12
顺序表之整体概念：
data
0
1
last
Maxsize
last
数组下标
数组 变量 操作算法
Maxsize-1
初始化操作
插入操作
删除操作
查找操作
排序操作
.,,,,,.,,
.,
.
.,
.
2011-7-18 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];
}
}
2011-7-18 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;
}
2011-7-18 15
（ 3）顺序表插入操作
为了把新元素 x 插入到 i 处，必须把从 i 到 last 的所
有元素成块向后移动一个元素位置，以空出第 i 个位
置供 x 插入：
x
23 1
先移动后面元素
0 i-1 i i+1 last.,,,,,
.,,,,,,,,
.,,
2011-7-18 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;
}
}
2011-7-18 17
（ 4）顺序表删除操作
为了删除第 i 个元素，必须把从 i＋ 1 到 last 的所有元素
向前移动一个元素位置，把第 i 个元素覆盖掉：
1 2,,,
0 i-1 i i+1 last-1 last1
.,,,,,,,,
.,,,,,
2011-7-18 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;
}
2011-7-18 19
顺序存储结构的优缺点
? 优点：
（ 1）算法简单、可读性好、开发代价低
? 缺点：
（ 1）插入、删除操作时需要移动大量元素，
效率较低；
（ 2）最大表长难以估计，太大了浪费空间，
太小了容易溢出。
2011-7-18 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++;
}
}
}
2011-7-18 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 ++;
}
}
2011-7-18 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
2011-7-18 23
多项式的表示
对于稀疏多项式，采用二元组表示法可以大大节省存储
空间：
（ 1）将稀疏多项式的每一项用二元组 < ci,ei >表示
——客体的表示方法
（ 2）用一顺序表（一维数组）来存放上述的二元组
——数据的组织方法
c0 c1 ci cn
e0 e1 ei en
系数
指数
.,,.,,,,,
.
.
.,,
2011-7-18 24
多项式二元组的类定义 ——客体的表示方法
class Polynomial; // 多项式类的前视声明
class term // 多项式中项（二元组）的类定义
{
friend Polynomial; // 定义 Polynomial 类为 term 类的友元类
private,
float coef; // 系数
int exp; // 指数
}
2011-7-18 25
多项式的类定义 ——数据的表示方法
class Polynomial
{
public,
.,, // 成员函数声明（构造、释构、相加等函数）
private,
int MaxTerms ; //共享空间（顺序表）的最大项数
static term termArray[MaxTerms];
//存放二元组的数组，存放多个多项式的共享空间
static int free ; // 共享空间中自由空间之起始下标
int start,finish ; // 多项式在共享空间中的首、尾下标
}
2011-7-18 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
2011-7-18 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 中
2011-7-18 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 ; }
2011-7-18 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 ++ ;
}
2011-7-18 30
作业：
定义多项式类的求表长、查找、插入、删除、判空
表判满表、读取（第 i 个元素）等成员函数，并用这些
函数实现前述的两个多项式的相加操作。
提示：
（ 1）定义查找指数相等的元素的成员函数
（ 2）仿照前述的顺序表合并操作算法，先从多项式 B 中
读取一元素，在 A 中查找有无指数相等元素：
若无，则有序插入 A 中；
若有，则系数相加：
若和为零，则从 A 中删除相应元素；
否则用新系数构造新元素，并插入 A 中相应位置
2011-7-18 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 个非零元素，
其他均为零。因此用二维数组来存储稀疏矩阵的空间
利用率较低，必须考虑对稀疏矩阵的压缩存储表示。
2011-7-18 32
稀疏矩阵的三元组表示法：
（ 1）将稀疏矩阵的非零元素用三元组
< row,column,value > 表示（ 表示稀疏矩阵的
第 row 行、第 column 列的值为 value）
——客体的表示方法
（ 2）用一顺序表（一维数组）来存放上述三元组
（每一个三元组即为顺序表的一个数据元素）
并按行优先顺序存放
——数据的组织方法
template < class Type > class Trituple
{ private,
int row,col;
Type value;
}
2011-7-18 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
2011-7-18 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];
}
2011-7-18 35
说明：
（ 1）压缩前的稀疏矩阵为 Rows 行,Cols 列的矩阵
smData,压缩后的稀疏矩阵存放在一维数组
smArray 中，其中的元素为 Trituple 类型的对象。
声明中的 Terms 对应于顺序表定义中的 last，
MaxTerms 对应于顺序表定义中的 Maxsize，
smArray 对应于顺序表定义中的 data
（ 2）为稀疏矩阵声明了四种操作：
压缩（ Compression）
转置（ Transpose）
相加（ Add）
相乘（ Multiply）
根据实际需要还可以声明其他操作。
（ 3）数值计算与非数值计算的数据结构中所定义的基
本操作有很大的不同
2011-7-18 36
稀疏矩阵的转置操作
快速转置算法思路：
（ 1）引入两个辅助数组 rowSize[ ] 和 rowStart[ ]
rowSize [ i ]——表示稀疏矩阵第 i 列的非零元素个数
rowStart[ i ]——表示稀疏矩阵第 i 列的第一个（行号最小）
非零元素在转置矩阵的三元组表中的位置。
显然应有：
rowStart[ i ] + rowSize[ i ] = rowStart[ i+1 ]
.,,,,,,,,
共有 rowSize[ i ] 个元素
2011-7-18 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 列非零元素在转置矩阵的三元组表中的位置
2011-7-18 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;
}
2011-7-18 39
2。 5 字符串
定义,字符串（简称为串） 是 n ( n >= 0 ) 个字符的有限序列
通常可记为：
S= ? a0 a1 a2 … an-1 ‘
其中,串名 ——S
串值 ——引号中的内容
n——串长，即串中的字符个数（不包括串结束符 ‘ \0 ‘ ）
空串 ——n = 0 的串（但包含串结束符）
空白串 ——仅由若干个空格字符组成的串，其长度不为零
子串 ——从非空串中连续取出的若干个字符组成的串
子串的位置 ——子串的第 0个字符在原串中的位置
可以认为：串是限制数据元素为字符的顺序表
2011-7-18 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;
}
2011-7-18 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‘;
2011-7-18 42
文本编辑
计算机应用中要涉及大量的文本文件，文本文件由大量的串
（行）组成，在某些文本文件（如源程序）中，串（行）长差异
很大，若每行都用等长的串来存贮，则会浪费存贮空间
解决的办法之一是建立一个很大的字符数组作为所有串的共
享空间 ——串值共享空间，再为每个串建立一个描述子，用于描
述该串的长度以及该串在串值共享空间中的位置等信息，并将这
些描述子存入一顺序表中，参见下图：
2011-7-18 43
行表 (linelist) 串值共享空间（ space） MaxSize-1
..
.,free
行
号
0
1
2
3
行长 位置 行 2 行 3 行 0 行 1,,,
.,
.,
.,
.,
自由空间起始地址
0
串值共享空间 ——String（串）
行表 ——Seqlist（顺序表）
设计行内字符插入、删除操作算法
设计整行插入、删除操作算法
2011-7-18 44
第三章 链表
顺序表有下列缺点：
（ 1）插入、删除操作时需要移动大量元素，
效率较低；
（ 2）最大表长难以估计，太大了浪费空间，
太小了容易溢出。
因此，在插入和删除操作是经常性操作的应用场合
选用顺序存储结构不太合适，此时可以选用链式存储结
构。
定义：用指针来表示数据元素之间关系的存储结构
称之为链式存储结构。
2011-7-18 45
定义：用由指针连接起来的一串结点来存储一个线性表
的存储结构称为线性链式存储结构，简称链表。
当每一结点中只有一个指针，并用来表示一个数
据元素到其后继元素之间的接续关系，则称这种
存储结构为单链表。
注：此处的结点是指通过指针型变量动态索取到的存储空间
.,, ^first
first——头指针 指针域 (link) last
last ——尾指针 数据元素域 (data)
^ ——空指针
结点 1头结点 结点 0 结点 n-1
2011-7-18 46
上述的单链表表头设置了一头结点，头结点的数据
域中可以为空，或者存放一些辅助数据。
设置头结点的目的是为了简化对空表的特殊处理，
使得算法更简单、更有效。
对于带头结点的单链表，可以很容易地表示空链表：
头指针 头结点
first ^
last尾指针
2011-7-18 47
用模板定义的单链表类
template <class Type> class List;
template <class Type> class ListNode{
friend class List <Type>;
public:
ListNode( );
ListNode(const Type & item);
ListNode <Type> *NextNode ( ) {return link;}
void InsertAfter (ListNode <Type> * p);
ListNode <Type> * GetNode (const Type & item,
ListNode <Type> * next);
ListNode <Type> * RemoveAfter ( );
private:
Type data;
ListNode <Type> * link;
}
2011-7-18 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);
ListNode<Type> *Find(int i);
int Insert(Type value,int i);
Type *Remove(int i);
Type *Get(int i);
private:
ListNode<Type> *first,*last;
}
2011-7-18 49
ListNode<Type>类（链表结点类）的成员函数的实现
template <class Type> void ListNode<Type>::ListNode( ):link(NULL){}
template <class Type> void ListNode<Type>::
ListNode(const Type & item),data (item),link(NULL){}
template <class Type> void ListNode<Type>::
InsertAfter(ListNode<Type> *p){p->link=link;link=p;}
template <class Type> ListNode<Type> *ListNode<Type>::
GetNode(const Type & item,ListNode<Type> *next=NULL){
ListNode<Type> *newnode=new ListNode<Type>(item,next);
Return newnode;}
template <class Type> ListNode<Type> *ListNode<Type>::
RemoveAfter(){ListNode<Type> *tempptr=link;
If(link==NULL) return NULL;
link=tempptr->link;return tempptr;}
2011-7-18 50
Void InsertAfter(ListNode<Type) *p):
功能：将 p 所指的结点（ *p）链接成为当前结点（ *this）
的后继结点
this
data link data link …
data linkp
p->link=linkLink=p
…
(1)(2)
当前结点
2011-7-18 51
RemoveAfter( )
data link data link data link
当前结点 要删除的结点
功能：删除当前结点 ( *this ) 的后继结点,并返回该结点的指针。
(1)tempptr
(2) link=tempptr->link
this
tempptr->link
2011-7-18 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
头结点
2011-7-18 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)
2011-7-18 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)
2011-7-18 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;
}
2011-7-18 56
3.1.6 单链表的游标 (Iterator)类
2011-7-18 57
单链表游标类声明
Template <class Type> class ListIterator
{
public:
ListIterator(const List<Type> & l):
list(l),current(l.first) { }
Boolean NotNull( );
Boolean NextNotNull ( );
Type * First ( );
Type * Next ( );
private:
const List<Type> & list;
ListNode<Type> * current;
}
2011-7-18 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;
}
2011-7-18 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;
}
2011-7-18 60
2011-7-18 61
2011-7-18 62
2011-7-18 63
2011-7-18 64
2011-7-18 65
2011-7-18 66
2011-7-18 67
2011-7-18 68
2011-7-18 69
2011-7-18 70
2011-7-18 71
2011-7-18 72
2011-7-18 73
2011-7-18 74
2011-7-18 75
2011-7-18 76
2011-7-18 77
2011-7-18 78
2011-7-18 79
2011-7-18 80
2011-7-18 81
2011-7-18 82
2011-7-18 83
2011-7-18 84
2011-7-18 85
2011-7-18 86
2011-7-18 87
2011-7-18 88
2011-7-18 89
2011-7-18 90
2011-7-18 91
2011-7-18 92
2011-7-18 93
2011-7-18 94
2011-7-18 95
2011-7-18 96
2011-7-18 97
2011-7-18 98
2011-7-18 99
2011-7-18 100
2011-7-18 101
2011-7-18 102
2011-7-18 103
2011-7-18 104
2011-7-18 105
2011-7-18 106
2011-7-18 107
2011-7-18 108
2011-7-18 109
2011-7-18 110
2011-7-18 111
2011-7-18 112
2011-7-18 113
