数 据 结 构主讲：陈光喜 博士课号,032844
课时,40(讲课 )+16(实验 )
上课地点,6312 (周一 ) 3314 (周五 )
计算科学与数学系
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜第一章 绪 论
1.1 例子
1.2 数据结构、基本概念和术语
1.3 算法和算法分
1.3.1 算法
1.3.2 算法设计的要求
1.3.3 算法的复杂度
1.3.4 算法的描述
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜第一章 绪 论
计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：
信息的表示 信息的处理信息的表示和组又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，系统程序和应用程序的规模越来越大，结构愈加复杂。要有“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
1.1 例子
(Niklaus Wirth) Algorithm + Data Structures = Programs
程序设计,为计算机处理问题编制一组指令集算法,处理问题的策略 数据结构,问题的数学模型例,有关 数值计算 的程序设计问题结构静力分析计算 ─━ 线性代数方程组数据结构主要研究的 是非数值计算 程序的数据结构
1 电话号码查询系统设电话号码薄记录了人的名和电话号码，假定按如下形式安排,(a1,b1)(a2,b2)…(a n,bn) 其中 ai,bi(i=1，
2…n) 分别表示某人的名字和对应的电话号码要求设计一个算法，当给定人名时，算法得到他的电话号码，
如果该电话簿中没这个人，算法指出没有。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
算法的设计，依赖于计算机如何存储人的名字和 对应 (逻辑关系 )的电话号码，即依赖于名字和其电话号码的 结构 。
数据的结构，直接影响算法的选择和效率 。
该问题是一种数据 结构问题 (存储结构 )。可将名字和对应的电话号码设计成：二维数组、表结构、向量。
数据结构还要提供 每种结构类型所定义的各种运算的算法 (操作 )。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
2 在字典里查找某个单词算法,比较“大小” 模型,?
3 计算机下五子棋算法,下棋的规则,策略 模型,?
可以认为,数据结构描述现实世界实体的数学模型
(非数值计算 )及其上的操作在计算机中的表示和实现,
(研究数据的逻辑结构,物理结构以及对结构定义相应的运算，而且确保经过运算后所得到的结果仍然是原来的结构。 )
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
数据 (Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素 (Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。
数据对象 (Data Object)：是性质相同的数据元素的集合。是数据的一个子集。
数据结构 (Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。
1.2 基本概念和术语
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
数据结构主要指逻辑结构和物理结构
数据间的相互关系称为逻辑结构,常分为四类基本结构：
一,集合 结构中的数据元素除同属于一种类型外,无其它关系。
二,线性结构 结构中的数据元素之间存在一对一的关系。
三,树型结构 结构中的数据元素之间存在一对多的关系。
四,图状结构或网状结构 数据元素之间存在多对多的关系。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜数据结构的形式定义为：数据结构是一个二元组,Data-Structure=(D,R)
其中,D是数据元素的有限集,R是 D上关系的有限集。
例 复数的数据结构定义,Complex=(C,R)
其中,C是含两个实数的集合 ﹛ C1,C2﹜,分别表示复数的实部和虚部。 R={P},P是定义在集合上的一种关系 {〈 C1,C2〉 }。
数据结构在计算机中的表示称为数据的物理结构，又称为 存储结构 。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
数据对象 D可以是有限的，也可以是无限的。
数据结构不同于数据类型，也不同于数据对象，它描述数据类型的数据对象和数据对象各元素之间的相互关系。
R是 D上元素的关系集合。
数据的 逻辑结构,反映数据之间逻辑关系的数据结构。
数据结构的图形表示 (略 ) P7
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
数据结构类型,线性结构，非线性结构。
线性结构,1)有且仅有一个根结点 2)每个结点最多只有一个根前件一个后件
两种不同的存储结构,顺序存储结构和链式存储结构
顺序存储结构,用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系 。
链式存储结构,在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
数据类型,在一种程序设计语言中，变量所具有的数据种类。
例如 C语言，变量的数据类型有基本类型 (整型、
浮点型、字符型 )和构造类型 (数组、结构、
联合、指针、枚举型、自定义 )
数据对象：某种数据类型元素的集合。
例如,整数的数据对象是 {… -3,-2,-1,0,1，
2,3,…} 英文字符类型的数据对象是 {A,B，
C,D,E,F,…}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
算法：是对特定问题求解步骤的一种描述算法是有限长的 操作序列
算法具有以下五个特性：
1有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
2确定性 算法中每一条指令必须有确切的含义。
不存在二义性。且算法只有一个入口和一个出口。
3可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
1.3 算法与分析
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
4 输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。
5 输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。
1.3.2 算法设计的要求
(1) 正确性 (Correctness ) 算法应满足具体问题的需求。
(2)可读性 (Readability) 算法应该好读。以有利于阅读者对程序的理解。
(3)健状性 (Robustness) 算法应具有容错处理。
当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
(4)效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。
1.3.3 算法的复杂度
算法分析可分成两个阶段进行，即事先分析和事后测试
事先分析 求出该算法的一个时间界限函数
事后测试 收集此算法的执行时间和实际占用空间的统计资料。
定义：如果存在两个正常数 c和 n0，对于所有的
n≧ n0，有 ︱ f(n) ︳ ≦ c｜ g(n) ︳
则记作 f(n)=O(g(n))
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜一般情况下，算法中基本操作重复执行的次数是问题规模 n的某个函数，算法的时间量度记作 T(n)=O(f(n))
称作算法的渐近时间复杂度。
例１ for(I=1,I<=n;++I)
for(j=1;j<=n;++j)
{
c[I][j]=0;
for(k=1;k<=n;++k)
c[I][j]+=a[I][k]*b[k][j];
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
由于是一个三重循环，每个循环从 1到 n，则总次数为,n× n× n=n3
时间复杂度为 T(n)=O(n3)
频度,是指该语句重复执行的次数例 2 for(i=2;i<=n;++I)
for(j=2;j<=i-1;++j)
{++x;a[i,j]=x;}
语句频度为：
1+2+3+…+n -2=(1+n-2) × (n-2)/2
=(n-1)(n-2)/2 =n2-3n+2
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
∴ 时间复杂度为 O(n2)
一个算法时间为 O(1)的算法，它的基本运算执行的次数是固定的。总的时间由一个常数来限界。而一个时间为 O(nk)的算法则由一个 k次多项式来限界。
常见多项式时间算法关系
O(1)<O(logn)<O(n)<O(nlogn) <O(n2)<O(n3)
常见指数时间算法关系
O(2n)<O(n!)<O(nn)
指数时间算法能否化简为多项式时间算法?(NP-hard)
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
有的情况下，算法中基本操作重复执行的次数与问题的输入数据有关。
Void bubble-sort(int a[],int n)
for(I=n-1;change=TURE;I>1 && change;--I)
{ change=false;
for(j=0;j<I;++j)
if (a[j]>a[j+1]) {
a[j] ←→a[j+1];
change=TURE}}
最好情况,0次,最坏情况,n(n-1)/2
通常考虑最坏时间复杂度
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜算法的空间复杂度 (略 )
空间复杂度,算法所需存储空间的度量
1.3.4 算法描述伪语言,
1)符号表达式
2)赋值语句
3)控制转移语句
4)循环语句
5)其他语句
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜本章学习要点
1.熟悉各名词术语的含义,掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。
2.理解算法各要素的确切含义,① 动态有穷性 (能执行结束 );② 确定性 (对于相同的输入执行相同的路径 );③ 有输入 ;④ 有输出 ;⑤ 可行性 (用以描述算法的操作都是足够基本的 ).
3.掌握估算算法时间复杂度的方法。
4.了解算法描述语言。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜第二章 线性表及其顺序存储结构
2.1 线性表的基本概念
2.2 栈及其应用
2.3 队列及其应用
2.4 字符串
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜线性表 (Linear List),由 n(n≧ )个数据元素 (结点 )a1,a2,…a n组成的有限序列。其中数据元素的个数 n定义为表的长度。当 n=0时称为空表，
将非空的线性表 (n>0)记作,(a1,a2,…a n)
数据元素 ai(1≦ i≦ n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。
例 英语字母组成的字母表
（ A,B,C,…,Z）
2.1 线性表的基本概念
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜例 2 学生健康情况登记表如下：
姓 名 学 号 性 别 年龄 健康情况王蔷 850631 女 18 健康刘建平 820633 男 21 健康赵军 840634 男 19 神经衰弱
…….,…….,……,……,…….
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
例 3、扑克的点数
（ 2,3,4,…,J,Q,K,A）
线性表的逻辑特征是：
在非空的线性表,有且仅有一个开始结点 a1，
它没有直接前件，而仅有一个直接后件 a2；
有且仅有一个终端结点 an，它没有直接后件，
而仅有一个直接前件 a n-1；
其余的结点 ai(2≦ i≦ n-1)都有且仅有一个直接前件 a i-1和一个直接后件 a i+1。
线性表是一种 典型的线性结构 。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
2.2.1 线性表的存储把线性表的结点按逻辑顺序 依次 存放在一组地址 连续的存储单元里。用这种方法存储的线性表简称顺序表。
前件和后件在存储空间总是相邻的。
设线性表的每个元素需占用 L个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。
则线性表中第 I+1个数据元素的存储位置 LOC( a i+1)和第 i个数据元素的存储位置 LOC(a i )之间满足下列关系：
LOC(a i+1)=LOC(a i)+L
即有,LOC(ai)=LOC(a1)+(i-1)*L
2.1.2 线性表的顺序存储结构
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
在 C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，可以用结构类型来定义顺序表类型。通常数组长度应该要比线性表实际长度大，利于插入等操作。
#define ListSize 100
typedef int DataType;
typedef struc{
DataType data[ListSize];
int length;
} Sqlist;
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
2.2.2 顺序表上实现的基本操作数据的运算是定义在逻辑结构上的,而运算的具体实现则是在存储结构上进行的。 在顺序表存储结构中,很容易实现线性表的一些操作,
如线性表的构造,第 i个元素的访问。 (线性表的初始化 P18)
注意,C语言中的数组下标从,0”开始，因此，
若 L是 Sqlist类型的顺序表，则表中第 i个元素是
L.data[i-1]。
线性表的 运算 有,插入,删除,查找,排序，
分解,合并,复制,逆转等。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
2.1.3 插入线性表的插入运算是指在表的第 i(1≦i≦n+1)
个位置上，插入一个新结点 x,使长度为 n的线性表 (a1,…a i-1,ai,…,an) 变成长度为
n+1的线性表 (a1,…a i-1,x,ai,…,an)
算法 2.1(线性表插入算法 )
Void InsertList(Sqlist*L,DataType x,int i)
{ int j;
if(i<1 || i>L.length-1) //插入位置分析
{ printf(“Position error”);
return ERROR;}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
if(L.length>=ListSize){
printf(“overflow”);
exit(overflow);} //越界
for(j=L.length-1;j>=i-1;j--)//移位
L.data[j+1]=L.data[j];
L.data[i-1]=x;
L.length++;
}
文字描述 P19-20
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
算法的复杂度分析。
问题规模是表的长度 (设为 n)。算法的时间主要花费在循环的结点后移语句上，
该语句的执行次数 (即移动结点的次数 )是
(n-i+1).可见所需移动结点的次数依赖于表的长度和插入位置。
当 i= n+1时,循环变量的终值大于初值，
结点后移语句不进行；这是最好情况，
其时间复杂度 O)(1)；
当 i=1时，结点后移语句将循环执行 n次，
需移动表中所有结点，这是最坏情况，
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
其时间复杂度为 O（ n）
下面分析算法的平均复杂度在长度为 n的线性表中第 i个位置上插入一个结点，令 Eis(n)表示移动结点的期望值 (即移动的平均次数 )则在第 i个位置上插入一个结点的移动次数为 n-i+1。有 Eis(n)= pi(n-i+1)
假设在表中任何位置 (1≦ i≦ n+1)上插入结点的机会是均等的，则 p1=p2=p3=…=p n+1=1/(n+1)
因此，在等概率插入的情况下，
E=对 i求和 (n-i+1)/(n+1)=n/2
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜即在顺序表上做插入运算，平均要移动表上一半结点。
当表长 n较大时，算法的效率相当低。虽然 E中 n的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为 O(n)。
2、删除线性表的删除运算是指将表的第 i(1≦i≦n) 结点删除,
使长度为 n的线性表,(a1,… a i-1,ai,a i+1…,an)
变成长度为 n-1的线性表
(a1,…a i-1,a i+1,…,an)
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜算法 2.2(线性表删除算法 )
Void deleteList(Sqlist*L,int i)
{ int j;
if(i<1 || i>L.length){
printf(“Position error”);
return ERROR;}
for(j=i;j<=L.length-1;j++)
L.data[j-1]=L.data[j];
L.length--;
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
算法的时间复杂度分析与插入算法相似，结点的移动次数也是由表长 n和位置 i决定。
i=n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动结点；
i=1，则前移语句将循环执行 n-1次，需移动表中除开始结点外的所有结点。这两种情况下算法的时间复杂度分别为 O(1)和 O(n)。
算法的平均性能分析令 Ede(n)表示所需移动结点的平均次数，删除表中第 i个结点的移动次数为 n-i，故,Ede(n)= pi(n-i)
pi表示删除表中第 i个结点的概率。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
等概率的假设下,p1=p2=p3=…=p n=1/n
可得,Ede(n)=对 I求和 (n-i)/n=(n-1)/2
即在顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是 O(n)。
见教材 P21-22
总体上讲,对于 小 线性表来说顺序存储和这两个算法还是合适的；
对大线性表来说效率就不高。
线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系,这样就可以随机存取表中的任一结点，但它也使插入和删除操作会移动大量的结点,为避免大量结点的移动,通常线性表可以采用另一种存储方式,链式存储结构,简称为链表 (Linked
List).它的关键就是在存储每个结点值的同时,存储指示其后继结点的地址信息 (即指针 (pointer):
data(数据域 )记录数据,link(指针域 )记录后继结点的地址 。
data link
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
2.2.1 栈的定义及基本运算栈 (Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶 (Top)，另一端为栈底 (Bottom)。当表中没有元素时称为空栈。
假设栈 S=(a1,a2,a3,…a n)，则 a1称为栈底元素,an为栈顶元素。栈中元素按 a1,a2，
a3,…a n的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是 按后进先出 的原则进行的。因此，栈称为后进先出表（ LIFO）。
2.2 栈及其应用
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜例、一叠书或一叠盘子。
a n
a n-1
a2
a1
……
栈顶栈底
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
top
7
6
5
4
3
2
1
-1
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
2.2,2 顺序栈与运算由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。
栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位臵是固定不变的，
所以可以将栈底位臵设臵在数组的两端的任何一个端点；栈顶位臵是随着进栈和退栈操作而变化的，故需用一个整型变量 top
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜来指示当前栈顶的位臵，通常称 top为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为 top即可。顺序栈的类型定义如下：
# define StackSize 100
typedef char datatype;
typedef struct {
datatype data[stacksize];
int top;
}seqstack;
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜设 S是 SeqStack类型的指针变量。若栈底位臵在向量的低端，即 s–>data[0]是栈底元素，那么栈顶指针 s–>top是正向增加的，即进栈时需将 s–>top加 1，退栈时需将
s–>top 减 1。因此,s–>top<0表示空栈,s–
>top =stacksize-1表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称“上溢” ;当栈空时再做退栈运算也将产生溢出，
简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，
因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
1、臵空栈
void initstack(seqstack *s)
{
s–>top=-1;
}
2、判断栈空
int stackempty(seqstack *s)
{
return(s–>top==-1);
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
3、判断栈满
int stackfull(seqstack *s)
{
return(s–>top==stacksize-1);
}
4、进栈
void push(seqstack *s,datatype x)
{
if (stackfull(s))
error(“stack overflow”);
s–>data[++s–>top]=x;}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
5、退栈
datatype pop(seqstack *s)
{
if(stackempty(s))
error(“stack underflow”);
x=s–>data[top];
s–>top--;
return(x)
//return(s–>data[s–>top--]);
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
6、取栈顶元素
Datatype stacktop(seqstack *s)
{
if(stackempty(s)
error(“stack is enpty”);
return s–>data[s–>top];
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜由于栈结构具有的后进先出的固有特性，
致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。
2.2.3.1 数制转换十进制 N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理,
N=(n div d)*d+n mod d
( 其中,div为整除运算,mod为求余运算 )
例如 (1348)10=(2504)8,其运算过程如下：
2.2.3 栈的应用举例
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
n n div 8 n mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
void conversion( ) {
int n,*s;
initstack(s);
scanf (“%”,&n);
while(n){
push(s,n%8);
n=n/8;}
while(! stackempty(s)){
pop(s,e);
printf(“%d”,e);}
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
2.2.3.2 表达式求值表达式求值是程序设计语言编译中的一个最基本问题,其实现方法是栈的一个典型的应用实例 。
表达式是由操作数 (operand),运算符 (operator)和界限符 (delimiter)组成的 。
操作数可以是常数,变量或常量的标识符 ;运算符可以是算术运算体符,关系运算符和逻辑符；界限符为左右括号和标识表达式结束的结束符 。 在此仅讨论简单算术表达式的求值 。 在这种表达式中只含加,减,乘,除四则运算,所有的运算对象均为单变量 。 表达式的结束符为,;”。
算术四则运算的规则为：
（ 1） 先乘除,后加减；
（ 2） 同级运算时先左后右；
（ 3） 先括号内,后括号外 。
计算机系统在处理表达式前,首先设置两个栈：
（ 1） 操作数栈 (OPRD)：存放处理表达式过程中的操作数 。
（ 2） 运算符栈 (OPTR)：存放处理表达式过程中的运算符 。 开始时,在运算符栈中先在栈底压入一个表达式的结束符,;”。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜计算机系统在处理表达式时,运算规则如下：
（ 1）假如是操作数,则将其压入操作数栈，并依次读下一个符号。
（ 2）假如是运算符,则：
1）假如读出的运算符的优先级大于运算符栈栈顶运算符的优先级，则将其压入运算符栈,并依次读下一个符号。
2）假如读出的是表达式结束符,;”,且运算符栈栈顶的运算符也为,#”
，则表达式处理结束,最后的表达式的计算结果在操作数栈的栈顶位置。
3）假如读出的是,(”,则将其压入运算符栈。
4）假如读出的是,)”,则：
A）若运算符栈栈顶不是,(”，则从操作数栈连续退出两个操作数，从运算符栈中退出一个运算符，然后作相应的运算，并将运算结果压入操作数栈，然后继续执行 A）。
B）若运算符栈栈顶为,(”,则从运算符栈退出,)”,依次读下一个符号。
5）读出运算符的优先级不大于运算符栈栈顶运算符的优先级,则从操作数栈连续退出两个操作数,从运算符栈中退出一个运算符,然后作相应的运算,将运算结果压入操作数栈,此时读出的运算符下次重新考虑 (即不读入下一个符号 )。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜上述讨论的表达式运算符在两个操作数中间 (除单目运算符外 )，这种表达式被称为 中缀表达式 。中缀表达式有时必须借助括号才能将运算顺序表达清楚，处理起来比较复杂。在编译系统中，对表达式的处理采用的是另外一种方法，即将中缀表达式转变为 后缀表达式,然后对后缀式表达式进行处理，后缀表达式也称为逆波兰式。
波兰表示法 （也称为前缀表达式）是由波兰逻辑学家 Lukasiewicz
提出的，其特点是将运算符置于运算对象的前面，如 a+b表示为
+ab； 逆波兰式 则是将运算符置于运算对象的后面，如 a+b表示为
ab+,中缀表达式经过上述处理后,运算时按从左到右的顺序进行，
不需要括号。得到后缀表达式后，在计算表达式时，可以设置一个栈，从左到右扫描后缀表达式，每读到一个操作数就将其压入栈中；每到一个运算符时，则从栈顶取出两个操作数进行运算，
并将结果压入栈中，一直到后缀表达式读完。最后栈顶就是计算结果。
思考,1+2*(4-sin(3/7+2)) 如何处理?
2.2.2.4 递归 (略 )
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
2.3.1 队列的定义队列 (Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。
允许删除的一端称为队头 (front)，允许插入的一端称为队尾 (rear)。
如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出 (First In First Out)的线性表，简称 FIFO表。
当队列中没有元素时称为空队列。在空队列中依次加入元素 a1,a2,… an之后,a1是队头元素,an是队尾元素。显然退出队列的次序也只能是 a1,a2,… an,
队列的修改是依先进先出的原则进行的。
2.3 队列及其应用
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜下图是队列的示意图：
a1 a2 … an出队 入队队头
front
队尾
rear
2.3.2 队列的顺序表示队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个向量空间来存放。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜由于队列的队头和队尾的位臵是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位臵，它们的初始值地队列初始化时均应臵为
-1。入队时将新元素插入 rear所指的位臵，然后将 rear加１。出队时，删去 front所指的元素，然后将 front加１并返回被删元素。当头尾指针相等时队列为空。 约定 在非空队列中，头指针 front
总是指向队列中实际队头元素的前面一个位臵，
尾指针 rear总是指向队尾元素。
-1 0 1 2 -1 0 1 2 3
Front
rear
a b c
Front rear
(a)队列初始为空 （ b） A,B,C入队
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜-1 0 １ ２ ０ １ ２
b c
front rear front
rear
（ c) a出队 (d) b,c出队，队为空和栈类似，队列中亦有上溢和下溢现象。此外，
顺序队列中还存在,假上溢,现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
2.3.1 顺序队列的基本运算算法
(0) 顺序队列定义
#define queuesize 100
Typedef int datatype;
Typedef struc{ int front,rear; datatype data[queuesize];} sqqueue;
（ 1） 初始化队列
int initQueue(sqqueue *q)
{/*创建一个空队列由指针 q指出 */
if ((q=(sqqueue*)malloc(sizeof(sqqueue))= =NULL) return FALSE;
q->front= -1;
q->rear=-1;
return TRUE;
}
（ 2） 入队列操作
int append(sqqueue *q,datatype x)
{/*将元素 x插入到队列 q中,作为 q的新队尾 */
if(q->rear>=queuesize-1) return FALSE; /*队列满 */
q->rear++;
q->queue[q->rear]=x;
return TRUE;
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
（ 3） 出队列操作
datatype delete(sqqueue*q)
{/*若队列 q不为空,则返回队头元素 */
datatype x;
if(q->rear= =q->front) return NULL; /*队列空 */
x=q->queue[++q->front];
return x;}
（ 4） 取队头元素操作
datatype getHead(sqqueue *q)
{/*若队列 q不为空,则返回队头元素 */
if(q->rear= =q->front) return NULL; /*队列空 */
return (q->queue[q->front+1]); }
（ 5） 判队列非空操作
int Empty(sqqueue *q)
{/*队列 q为空时,返回 TRUE；否则返回 FALSE*/
if (q->rear= =q->front) return TRUE;
return FALSE;}
（ 6） 求队列长度操作
int length(sqqueue *q)
{ return(q->rear-q->front);}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜循环队列是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量,存储在其中的队列称为循环队列 (Circular Queue).在循环队列中进行出队和入队操作时,头尾指针仍要加 1,朝前移动当头尾指针指向向量上界 (QueueSize-1)时,其加 1
操作的结果是指向向量的下界 0。
这种循环意义下的加 1操作可以描述为：
if(i+1==QueueSize) i=0;
else i++;
利用模运算可简化为,i=(i+1)%QueueSize
2.3.2 循环队列
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
0
1
23
4
5front
rear(b)
A
B
C
0
1
23
4
5front
rear
(a)
0
1
23
4
5
A
B
CD
E
F
front
rear
(c)
循环队列示意图
（ a）队列空；（ b）队列非空；
(c)队列满图所示,为循环队列的三种状态,(a)为队列空时,有 q-
>front==q->rear;(c)为队列满时,也有 q->front==q->rear；
因此凭 q->front==q->rear不能判定队列是空还是满 。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜因为循环队列元素的空间可以被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。
因此，除一些简单的应用外，真正实用的顺序队列是循环队列。
由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过 front=rear来判断队列
“空”还是“满”。
为了区分循环队列是空还是满,我们可以设定一个标志位 s,s= 0时为空队列,s=1时队列非空 。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜用 C语言定义循环队列结构如下：
#define MAXNUM 100
Typedef int datatype;
typedef struct
{datatype queue[MAXNUM];
int front; /*队头指针 */
int rear; /*队尾指针 */
int s; /*队列标志位 */
}qqueue;
下面给出循环队列的初始化,入队列及出队列的算法 。
（ 1） 初始化队列
int initQueue(qqueue *q) /*创建一个空队列由指针 q指出 */
{if ((q=(qqueue*)malloc(sizeof(qqueue)))= =NULL) return FALSE;
q->front= MAXNUM;
q->rear=MAXNUM;
q->s=0;
return TRUE; }
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
（ 2） 入队列操作
void append(qqueue *q,datatype x)
{if (( q->s==1)&&(q->front==q->rear)) return FALSE; /*队列满 */
q->rear++;
if (q->rear= =MAXNUM) q->rear=0;
q->queue[q->rear]=x;
q->s=1; /*置队列非空 */ }
（ 3） 出队列操作
datatype delete(qqueue *q)
{datatype x;
if (q->s= =0) retrun NULL; /*队列为空 */
q->front++;
if (q->front= =MAXNUM) q->front=0;
x=q->queue[q->front];
if (q->front = =q->rear) q->s=0; /*置队列空 */
return x; }
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜也可以用一个计数器记录队列中元素的总数 (队列长度 ).下面给出循环队列的类型定义。
#define queuesize 100
typedef char datatype;
typedef Struct{
int front;
int rear;
int count;
datatype data[queuesize]
}cirqueue;
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
（ 1）臵空队
void initqueue(cirqueue *q){
if ((q=(cirqueue *)malloc(sizeof(cirqueue)))==NULL)
error(“内存错误” );
q–>front=q–>rear=0;
q–>count=0; }
（ 2）判断队空
int queueempty(cirqueue *q) {
return q–>count==0; }
（ 3）判断队满
int queuefull(cirqueue *q){
return q–>count==queuesize; }
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
（ 4）入队
void enqueue(cirqueue *q,datatype x)
{
if(queuefull(q))
error(“queue overflow”);
q–>count++;
q–data[q–rear]=x;
q–rear=(q–rear+1)%queuesize;
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
（ 5）出队
datatype dequeue(cirqueue *q)
{ datatype temp;
if(queueempty(q))
error(“queue underflow”);
temp=q–>data[q–>front];
q–>count--;
q–front=(q–>front+1)%queuesize;
return temp;
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
（ 6）取头指针
datatype queuefront(cirqueue *q)
{
if(queueempty(q))
error(“queue is empty.”);
return q–>data[q–>front];
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
2.3.3 队列的应用
2.3.1 工作调度和分配模型分析 (P39)
2.3.2 输入输出缓冲区结构 (略 )
2.3.3 汽车加油站工作模拟 (重点讲解 )
模型分析与详细设计 (P40-44)
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
2.4 串
2.4.1 串类型的定义
2.4.2 串的表示和实现
2.4.2.1 定长顺序存储表示
2.4.2.2 堆分配存储表示
2.4.2.3 串的块链存储表示
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
2.4.1 串类型的定义一、串和基本概念串 (String)是零个或多个字符组成的有限序列。
一般记作 S=“a1a2a3… an”，其中 S 是串名，双引号括起来的字符序列是串值； ai(1≦ i≦ n)可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。长度为零的串称为空串
(Empty String)，它不包含任何字符。
通常将仅由一个或多个空格组成的串称为空白串 (Blank String)
注意：空串和空白串的不同，例如,,和,”
分别表示长度为 1的空白串和长度为 0的空串。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号
（或位臵）。例如，设 A和 B分别为
A=“This is a string” B=“is”
则 B是 A的子串,A为主串。 B在 A中出现了两次，
其中首次出现所对应的主串位臵是 3。因此，
称 B在 A中的序号（或位臵）为 3
特别地，空串是任意串的子串，任意串是其自身的子串。
通常在程序中使用的串可分为两种：串变量和串常量。串常量和整常数、实常数一样，在
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜程序中只能被引用但不能不能改变其值，即只能读不能写。通常串常量是由直接量来表示的，
例如语句 Error(“overflow”)中,overflow”是直接量。但有的语言允许对串常量命名，以使程序易读、易写。如 C++中，可定义
const char path[]=“dir/bin/appl”;
这里 path是一个串常量，对它只能读不能写。串变量和其它类型的变量一样，其取值是可以改变的。
二、串的抽象数据定义串的抽象数据类型定义台书 P71
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜三、串的基本操作对于串的基本操作，许多高级语言均提供了相应的运算或标准库函数来实现。下面仅介绍几种在 C语言中常用的串运算，其它的串操作见的文件。
定义下列几个变量：
char s1[20]=“dirtreeformat”,s2[20]=“file.mem”;
char s3[30],*p;
int result;
(1) 求串长 (length)
int strlen(char s); //求串的长度例如,printf(“%d”,strlen(s1)); 输出 13
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
（ 2）串复制 (copy)
char *strcpy(char to,char from);
该函数将串 from复制到串 to中，并且返回一个指向串 to的开始处的指针。
例如,strcpy(s3,s1); //s3=“dirtreeformat”
(3)联接 (concatenation)
char strcat(char to,char from)
该函数将串 from复制到串 to的末尾，并且返回一个指向串 to的开始处的指针。
例如,strcat(s3,”/”)
strcat(s3,s2); //s3=“dirtreeformat/file.mem”
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
(4)串比较（ compare)
int strcmp(chars1,char s2);
该函数比较串 s1和串 s2的大小，当返回值小于 0，
等于 0或大于 0时分别表示 s1<s2\s1=s2或 s1>s2
例如,result=strcmp(“baker”,”Baker”) result>0
result=strcmp(“12”,”12”); result=0
result=strcmp(“Joe”,”Joseph”); result<0
（ 5）字符定位 (index)
char strchr(char s,char c);
该函数是找 c在字符串中第一次出现的位臵，若找到则返回该位臵，否则返回 NULL。
例如,p=strchr(s2,”.”); p 指向,file”之后的位臵
if(p) strcpy(p,”.cpp”); s2=“file.cpp”
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜上述串的操作是最基本的，其中后四个还有变种形式：
strncpy,strncat,strncmp,strnchr。串的其余操作可由这些基本操作组合而成。
例 1、求子串求子串的过程即为复制字符序列的过程，将串 S
中的第 pos个字符开始长度为 len的字符复制到串 T中。
void substr(string sub,string s,int pos,int len)
{
if(pos<0 || pos>strlen(s)-1 || len<0)
error(“parameter error”)
strncpy(sub,&s[pos],len);
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜例 2、串的定位 index(s,t,pos)
在主串中取从第 i个字符起、长度和串 T
相等的子串和 T比较，若相等，则求得函数值为 i，否则值增 1直至 S中不存在和串 T相等的子串为止。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜int index(string s,string t,int pos){
if(pos>0){
n=strlen(s); m=strlen(t); i=pos;
while(i<n-m+1){
substr(sub,s,i,m);
if(strcmp(sub,t)!=0)
++i;
else return(i);
}
}
return(0);
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜2.4.2 串的表现和实现因为串是特殊的线性表，故其存储结构与线性表的存储结构类似。只不过由于组成串的结点是单个字符。串有三种机内表示方法，下面分别介绍。
2.4.2.1定长顺序存储表示定长顺序存储表示,也称为静态存储分配的顺应表。它是用一组连续的存储单元来存放串中的字符序列。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先给出：
#define maxstrlen 256
typedef char sstring[maxstrlen];
sstring s; //s是一个可容纳 255个字符的顺序串。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜一般可使用一个不会出现在串中的特殊字符在串值的尾部来表示串的结束。例如,C语言中以字符
‵ \0′ 表示串值的终结，这就是为什么在上述定义中，串空间最大值 maxstrlen为 256，但最多只能存放 255个字符的原因，因为必须留一个字节来存放
‵ \0′ 字符。若不设终结符，可用一个整数来表示串的长度，那么该长度减 1的位臵就是串值的最后一个字符的位臵。此时顺序串的类型定义和顺序表类似：
typedef struct{
char ch[maxstrlen];
int length;
}sstring; //其优点是涉及到串长操作时速度快。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜2.4.2.2堆分配存储表示这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。所以也称为动态存储分配的顺序表。在 C语言中，利用和等动态存储管理函数，来根据实际需要动态分配和释放字符数组空间。这样定义的顺序串类型也有两种形式。
typedef char *string; //c中的串库相当于此类型定义
typedef struct{
char *ch;
int length;
}hsring;
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
status sinsert(hstring s,int pos,hstring t){
if(pos<1 || pos>s.length+1)
return error;
if(t.length){
if(!(s.ch=(char*)realloc(s.ch,(s.length+t.length
)*sizeof(char)))
exit(overflow);
for(i=s.length-1;i>pos-1;--i)
s.ch[I+t.length]=s.ch[i];
s.ch[pos-1..pos+t.length-
2]=t.ch[0..t.length-1];
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
s.length+=t.length;
}
return ok;
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
int strlen(hstring s){
return s.length;
}
status clearstring(hstring s){
if(s.ch){free(s.ch);s.ch=NULL;}
s.length=0;
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
status strassign(hstring t,char *chars){
//生成一个其值等于串常量 chars的串 t
if(t.ch) free(t.ch);
for(i=0,(c=chars;c;++i),++c);
if(!i) {
t.ch=null; t.length=0;
}
else{
if(!(t.ch=(char *)malloc(I*sizeof(char))))
exit(overflow);
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
t.ch[0..i-1]=chars[0..i-1];
t.length=i;
}
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
int strcmp(hstring s,hstring t){
for(i=0;i<s.length && i<t.length;++i)
if(s.ch[i]!=t.ch[i]
return(s.ch[i]-t.ch[i]);
return s.length-t.length;
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
status concat(hstring t,hstring s1,hstring s2){
if(!(t.ch)=(char*)malloc(s1.length+s2.length)*
sizeof(char)))
exit(overflow);
t.ch[0..s1.length-1]=s1.ch[0..s1.length-1];
t.length=s1.length+s2.length;
t.ch[s1.length..t.length-
1]=s2.ch[0..s2.length-1];
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
Status substr(hstring sub,hstring s,int pos,int
len){
if(pos<1 || pos>s.length || len<0 ||
len>s.length-pos+1)
return error;
if(sub.ch) free(sub.ch);
if(!len){
sub.ch=null;
sub.length=0;
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
else{
sub.ch=(char *)malloc(len*sizeof(char));
sub.ch[0..len-1]=s[pos-1..pos+len-2];
s.length=len;
}
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
2.4.2.3 串的链式存储结构顺序串上的插入和删除操作不方便，需要移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。
typedef struct node{
char data;
struct node *next;
}lstring;
一个链串由头指针唯一确定。
这种结构便于进行插入和删除运算，但存储空间利用率太低。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜为了提高存储密度，可使每个结点存放多个字符。
通常将结点数据域存放的字符个数定义为 结点的大小,显然，当结点大小大于 1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。
对于结点大小不为 1的链串，其类型定为义只需对上述的结点类型做简单的修改即可。
#define nodesize 80
typedef struct node{
char data[nodesize];
struct node *next;
}lstring;
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜2.4.3 串的模式匹配算法子串定位运算又称为模式匹配 (Pattern
Matching)或串匹配 (String Matching)，此运算的应用在非常广泛。例如，在文本编辑程序中，
我们经常要查找某一特定单词在文本中出现的位臵。显然，解此问题的有效算法能极大地提高文本编辑程序的响应性能。
在串匹配中，一般将主串称为目标串，子串称之为模式串。设 S为目标串,T为模式串，且不妨设：
S=“s0s1s2… sn-1” T=“t0t1… tm-1”
串的匹配实际上是对于合法的位臵 0≦ i≦ n-m依次将目标串中的子串 s[i..i+m-1]和模式串
t[0..m-1]进行比较，若 s[i..i+m-1]=t[0..m-1]，
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜其算法段为：
for(i=0;i<=n-m;i++){
if(S[i..i+m-1]=T[0..m-1]
return i;
下面以第二种 定长的顺序串类型 作为存储结构，给出具体的串匹配算法。
int index(sstring s,sstring t,int pos){
int i,j,k;
int m=s.length;
int n=t.length;
for(i=0;i<=n-m;i++){
j=0;k=i;
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜则称从位臵 i开始的匹配成功，亦称模式 t在目标 s中出现；若 s[i..i+m-1] ≠t[0..m -1]，
，则称从位臵 i开始的匹配失败。上述的位臵 i
又称为位移，当 s[i..i+m-1]=t[0..m-1]时,i
称为有效位移；当 s[i..i+m-1] ≠t[0..m -1]时，
i称为无效位移。这样，串匹配问题可简化为是找出某给定模式 T在一给定目标 T中首次出现的有效位移。
串匹配的算法很多，这里我们只讨论一种最简单的称为朴素的串匹配算法。其基本思想是用一个循环来依次检查 n-m+1个合法的位移
i(0≦ i≦ n-m)是否为有效位移，
≠
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
while(j<m && s.ch[k]==t.ch[j]{
k++;j++;
}
if(j==m)
return i;
}
return –1;
}
显然，该算法在最坏情况下的时间复杂度为 O((n-m)m)。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜链串上的子串定位算法用结点大小为 1的单链表做串的存储结构时，
实现朴素的匹配算法很简单。只是现在的位移是结点地址而非整数，且单链表中没有存储长度信息。若匹配成功，则返回有效位移所指的结点地址，否则返回空指针。具体算法如下：
lstring *lindex(lstring s,lstring t){
lstring *shift,*q,*p;
shift=S;
q=shift;p=t;
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
while(q && p){
if(q->data==p->data){
q=q->next;
p=p->next;
}
else{
shift=shift->next;
q=shift;
p=t;
}
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
if(p==null)
return shift;
else
return null;
}
课时,40(讲课 )+16(实验 )
上课地点,6312 (周一 ) 3314 (周五 )
计算科学与数学系
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜第一章 绪 论
1.1 例子
1.2 数据结构、基本概念和术语
1.3 算法和算法分
1.3.1 算法
1.3.2 算法设计的要求
1.3.3 算法的复杂度
1.3.4 算法的描述
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜第一章 绪 论
计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：
信息的表示 信息的处理信息的表示和组又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，系统程序和应用程序的规模越来越大，结构愈加复杂。要有“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
1.1 例子
(Niklaus Wirth) Algorithm + Data Structures = Programs
程序设计,为计算机处理问题编制一组指令集算法,处理问题的策略 数据结构,问题的数学模型例,有关 数值计算 的程序设计问题结构静力分析计算 ─━ 线性代数方程组数据结构主要研究的 是非数值计算 程序的数据结构
1 电话号码查询系统设电话号码薄记录了人的名和电话号码，假定按如下形式安排,(a1,b1)(a2,b2)…(a n,bn) 其中 ai,bi(i=1，
2…n) 分别表示某人的名字和对应的电话号码要求设计一个算法，当给定人名时，算法得到他的电话号码，
如果该电话簿中没这个人，算法指出没有。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
算法的设计，依赖于计算机如何存储人的名字和 对应 (逻辑关系 )的电话号码，即依赖于名字和其电话号码的 结构 。
数据的结构，直接影响算法的选择和效率 。
该问题是一种数据 结构问题 (存储结构 )。可将名字和对应的电话号码设计成：二维数组、表结构、向量。
数据结构还要提供 每种结构类型所定义的各种运算的算法 (操作 )。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
2 在字典里查找某个单词算法,比较“大小” 模型,?
3 计算机下五子棋算法,下棋的规则,策略 模型,?
可以认为,数据结构描述现实世界实体的数学模型
(非数值计算 )及其上的操作在计算机中的表示和实现,
(研究数据的逻辑结构,物理结构以及对结构定义相应的运算，而且确保经过运算后所得到的结果仍然是原来的结构。 )
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
数据 (Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素 (Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。
数据对象 (Data Object)：是性质相同的数据元素的集合。是数据的一个子集。
数据结构 (Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。
1.2 基本概念和术语
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
数据结构主要指逻辑结构和物理结构
数据间的相互关系称为逻辑结构,常分为四类基本结构：
一,集合 结构中的数据元素除同属于一种类型外,无其它关系。
二,线性结构 结构中的数据元素之间存在一对一的关系。
三,树型结构 结构中的数据元素之间存在一对多的关系。
四,图状结构或网状结构 数据元素之间存在多对多的关系。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜数据结构的形式定义为：数据结构是一个二元组,Data-Structure=(D,R)
其中,D是数据元素的有限集,R是 D上关系的有限集。
例 复数的数据结构定义,Complex=(C,R)
其中,C是含两个实数的集合 ﹛ C1,C2﹜,分别表示复数的实部和虚部。 R={P},P是定义在集合上的一种关系 {〈 C1,C2〉 }。
数据结构在计算机中的表示称为数据的物理结构，又称为 存储结构 。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
数据对象 D可以是有限的，也可以是无限的。
数据结构不同于数据类型，也不同于数据对象，它描述数据类型的数据对象和数据对象各元素之间的相互关系。
R是 D上元素的关系集合。
数据的 逻辑结构,反映数据之间逻辑关系的数据结构。
数据结构的图形表示 (略 ) P7
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
数据结构类型,线性结构，非线性结构。
线性结构,1)有且仅有一个根结点 2)每个结点最多只有一个根前件一个后件
两种不同的存储结构,顺序存储结构和链式存储结构
顺序存储结构,用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系 。
链式存储结构,在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
数据类型,在一种程序设计语言中，变量所具有的数据种类。
例如 C语言，变量的数据类型有基本类型 (整型、
浮点型、字符型 )和构造类型 (数组、结构、
联合、指针、枚举型、自定义 )
数据对象：某种数据类型元素的集合。
例如,整数的数据对象是 {… -3,-2,-1,0,1，
2,3,…} 英文字符类型的数据对象是 {A,B，
C,D,E,F,…}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
算法：是对特定问题求解步骤的一种描述算法是有限长的 操作序列
算法具有以下五个特性：
1有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
2确定性 算法中每一条指令必须有确切的含义。
不存在二义性。且算法只有一个入口和一个出口。
3可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
1.3 算法与分析
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
4 输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。
5 输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。
1.3.2 算法设计的要求
(1) 正确性 (Correctness ) 算法应满足具体问题的需求。
(2)可读性 (Readability) 算法应该好读。以有利于阅读者对程序的理解。
(3)健状性 (Robustness) 算法应具有容错处理。
当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
(4)效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。
1.3.3 算法的复杂度
算法分析可分成两个阶段进行，即事先分析和事后测试
事先分析 求出该算法的一个时间界限函数
事后测试 收集此算法的执行时间和实际占用空间的统计资料。
定义：如果存在两个正常数 c和 n0，对于所有的
n≧ n0，有 ︱ f(n) ︳ ≦ c｜ g(n) ︳
则记作 f(n)=O(g(n))
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜一般情况下，算法中基本操作重复执行的次数是问题规模 n的某个函数，算法的时间量度记作 T(n)=O(f(n))
称作算法的渐近时间复杂度。
例１ for(I=1,I<=n;++I)
for(j=1;j<=n;++j)
{
c[I][j]=0;
for(k=1;k<=n;++k)
c[I][j]+=a[I][k]*b[k][j];
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
由于是一个三重循环，每个循环从 1到 n，则总次数为,n× n× n=n3
时间复杂度为 T(n)=O(n3)
频度,是指该语句重复执行的次数例 2 for(i=2;i<=n;++I)
for(j=2;j<=i-1;++j)
{++x;a[i,j]=x;}
语句频度为：
1+2+3+…+n -2=(1+n-2) × (n-2)/2
=(n-1)(n-2)/2 =n2-3n+2
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
∴ 时间复杂度为 O(n2)
一个算法时间为 O(1)的算法，它的基本运算执行的次数是固定的。总的时间由一个常数来限界。而一个时间为 O(nk)的算法则由一个 k次多项式来限界。
常见多项式时间算法关系
O(1)<O(logn)<O(n)<O(nlogn) <O(n2)<O(n3)
常见指数时间算法关系
O(2n)<O(n!)<O(nn)
指数时间算法能否化简为多项式时间算法?(NP-hard)
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
有的情况下，算法中基本操作重复执行的次数与问题的输入数据有关。
Void bubble-sort(int a[],int n)
for(I=n-1;change=TURE;I>1 && change;--I)
{ change=false;
for(j=0;j<I;++j)
if (a[j]>a[j+1]) {
a[j] ←→a[j+1];
change=TURE}}
最好情况,0次,最坏情况,n(n-1)/2
通常考虑最坏时间复杂度
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜算法的空间复杂度 (略 )
空间复杂度,算法所需存储空间的度量
1.3.4 算法描述伪语言,
1)符号表达式
2)赋值语句
3)控制转移语句
4)循环语句
5)其他语句
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜本章学习要点
1.熟悉各名词术语的含义,掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。
2.理解算法各要素的确切含义,① 动态有穷性 (能执行结束 );② 确定性 (对于相同的输入执行相同的路径 );③ 有输入 ;④ 有输出 ;⑤ 可行性 (用以描述算法的操作都是足够基本的 ).
3.掌握估算算法时间复杂度的方法。
4.了解算法描述语言。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜第二章 线性表及其顺序存储结构
2.1 线性表的基本概念
2.2 栈及其应用
2.3 队列及其应用
2.4 字符串
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜线性表 (Linear List),由 n(n≧ )个数据元素 (结点 )a1,a2,…a n组成的有限序列。其中数据元素的个数 n定义为表的长度。当 n=0时称为空表，
将非空的线性表 (n>0)记作,(a1,a2,…a n)
数据元素 ai(1≦ i≦ n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。
例 英语字母组成的字母表
（ A,B,C,…,Z）
2.1 线性表的基本概念
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜例 2 学生健康情况登记表如下：
姓 名 学 号 性 别 年龄 健康情况王蔷 850631 女 18 健康刘建平 820633 男 21 健康赵军 840634 男 19 神经衰弱
…….,…….,……,……,…….
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
例 3、扑克的点数
（ 2,3,4,…,J,Q,K,A）
线性表的逻辑特征是：
在非空的线性表,有且仅有一个开始结点 a1，
它没有直接前件，而仅有一个直接后件 a2；
有且仅有一个终端结点 an，它没有直接后件，
而仅有一个直接前件 a n-1；
其余的结点 ai(2≦ i≦ n-1)都有且仅有一个直接前件 a i-1和一个直接后件 a i+1。
线性表是一种 典型的线性结构 。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
2.2.1 线性表的存储把线性表的结点按逻辑顺序 依次 存放在一组地址 连续的存储单元里。用这种方法存储的线性表简称顺序表。
前件和后件在存储空间总是相邻的。
设线性表的每个元素需占用 L个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。
则线性表中第 I+1个数据元素的存储位置 LOC( a i+1)和第 i个数据元素的存储位置 LOC(a i )之间满足下列关系：
LOC(a i+1)=LOC(a i)+L
即有,LOC(ai)=LOC(a1)+(i-1)*L
2.1.2 线性表的顺序存储结构
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
在 C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，可以用结构类型来定义顺序表类型。通常数组长度应该要比线性表实际长度大，利于插入等操作。
#define ListSize 100
typedef int DataType;
typedef struc{
DataType data[ListSize];
int length;
} Sqlist;
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
2.2.2 顺序表上实现的基本操作数据的运算是定义在逻辑结构上的,而运算的具体实现则是在存储结构上进行的。 在顺序表存储结构中,很容易实现线性表的一些操作,
如线性表的构造,第 i个元素的访问。 (线性表的初始化 P18)
注意,C语言中的数组下标从,0”开始，因此，
若 L是 Sqlist类型的顺序表，则表中第 i个元素是
L.data[i-1]。
线性表的 运算 有,插入,删除,查找,排序，
分解,合并,复制,逆转等。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
2.1.3 插入线性表的插入运算是指在表的第 i(1≦i≦n+1)
个位置上，插入一个新结点 x,使长度为 n的线性表 (a1,…a i-1,ai,…,an) 变成长度为
n+1的线性表 (a1,…a i-1,x,ai,…,an)
算法 2.1(线性表插入算法 )
Void InsertList(Sqlist*L,DataType x,int i)
{ int j;
if(i<1 || i>L.length-1) //插入位置分析
{ printf(“Position error”);
return ERROR;}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
if(L.length>=ListSize){
printf(“overflow”);
exit(overflow);} //越界
for(j=L.length-1;j>=i-1;j--)//移位
L.data[j+1]=L.data[j];
L.data[i-1]=x;
L.length++;
}
文字描述 P19-20
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
算法的复杂度分析。
问题规模是表的长度 (设为 n)。算法的时间主要花费在循环的结点后移语句上，
该语句的执行次数 (即移动结点的次数 )是
(n-i+1).可见所需移动结点的次数依赖于表的长度和插入位置。
当 i= n+1时,循环变量的终值大于初值，
结点后移语句不进行；这是最好情况，
其时间复杂度 O)(1)；
当 i=1时，结点后移语句将循环执行 n次，
需移动表中所有结点，这是最坏情况，
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
其时间复杂度为 O（ n）
下面分析算法的平均复杂度在长度为 n的线性表中第 i个位置上插入一个结点，令 Eis(n)表示移动结点的期望值 (即移动的平均次数 )则在第 i个位置上插入一个结点的移动次数为 n-i+1。有 Eis(n)= pi(n-i+1)
假设在表中任何位置 (1≦ i≦ n+1)上插入结点的机会是均等的，则 p1=p2=p3=…=p n+1=1/(n+1)
因此，在等概率插入的情况下，
E=对 i求和 (n-i+1)/(n+1)=n/2
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜即在顺序表上做插入运算，平均要移动表上一半结点。
当表长 n较大时，算法的效率相当低。虽然 E中 n的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为 O(n)。
2、删除线性表的删除运算是指将表的第 i(1≦i≦n) 结点删除,
使长度为 n的线性表,(a1,… a i-1,ai,a i+1…,an)
变成长度为 n-1的线性表
(a1,…a i-1,a i+1,…,an)
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜算法 2.2(线性表删除算法 )
Void deleteList(Sqlist*L,int i)
{ int j;
if(i<1 || i>L.length){
printf(“Position error”);
return ERROR;}
for(j=i;j<=L.length-1;j++)
L.data[j-1]=L.data[j];
L.length--;
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
算法的时间复杂度分析与插入算法相似，结点的移动次数也是由表长 n和位置 i决定。
i=n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动结点；
i=1，则前移语句将循环执行 n-1次，需移动表中除开始结点外的所有结点。这两种情况下算法的时间复杂度分别为 O(1)和 O(n)。
算法的平均性能分析令 Ede(n)表示所需移动结点的平均次数，删除表中第 i个结点的移动次数为 n-i，故,Ede(n)= pi(n-i)
pi表示删除表中第 i个结点的概率。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
等概率的假设下,p1=p2=p3=…=p n=1/n
可得,Ede(n)=对 I求和 (n-i)/n=(n-1)/2
即在顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是 O(n)。
见教材 P21-22
总体上讲,对于 小 线性表来说顺序存储和这两个算法还是合适的；
对大线性表来说效率就不高。
线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系,这样就可以随机存取表中的任一结点，但它也使插入和删除操作会移动大量的结点,为避免大量结点的移动,通常线性表可以采用另一种存储方式,链式存储结构,简称为链表 (Linked
List).它的关键就是在存储每个结点值的同时,存储指示其后继结点的地址信息 (即指针 (pointer):
data(数据域 )记录数据,link(指针域 )记录后继结点的地址 。
data link
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
2.2.1 栈的定义及基本运算栈 (Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶 (Top)，另一端为栈底 (Bottom)。当表中没有元素时称为空栈。
假设栈 S=(a1,a2,a3,…a n)，则 a1称为栈底元素,an为栈顶元素。栈中元素按 a1,a2，
a3,…a n的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是 按后进先出 的原则进行的。因此，栈称为后进先出表（ LIFO）。
2.2 栈及其应用
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜例、一叠书或一叠盘子。
a n
a n-1
a2
a1
……
栈顶栈底
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
top
7
6
5
4
3
2
1
-1
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
2.2,2 顺序栈与运算由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。
栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位臵是固定不变的，
所以可以将栈底位臵设臵在数组的两端的任何一个端点；栈顶位臵是随着进栈和退栈操作而变化的，故需用一个整型变量 top
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜来指示当前栈顶的位臵，通常称 top为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为 top即可。顺序栈的类型定义如下：
# define StackSize 100
typedef char datatype;
typedef struct {
datatype data[stacksize];
int top;
}seqstack;
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜设 S是 SeqStack类型的指针变量。若栈底位臵在向量的低端，即 s–>data[0]是栈底元素，那么栈顶指针 s–>top是正向增加的，即进栈时需将 s–>top加 1，退栈时需将
s–>top 减 1。因此,s–>top<0表示空栈,s–
>top =stacksize-1表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称“上溢” ;当栈空时再做退栈运算也将产生溢出，
简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，
因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
1、臵空栈
void initstack(seqstack *s)
{
s–>top=-1;
}
2、判断栈空
int stackempty(seqstack *s)
{
return(s–>top==-1);
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
3、判断栈满
int stackfull(seqstack *s)
{
return(s–>top==stacksize-1);
}
4、进栈
void push(seqstack *s,datatype x)
{
if (stackfull(s))
error(“stack overflow”);
s–>data[++s–>top]=x;}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
5、退栈
datatype pop(seqstack *s)
{
if(stackempty(s))
error(“stack underflow”);
x=s–>data[top];
s–>top--;
return(x)
//return(s–>data[s–>top--]);
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
6、取栈顶元素
Datatype stacktop(seqstack *s)
{
if(stackempty(s)
error(“stack is enpty”);
return s–>data[s–>top];
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜由于栈结构具有的后进先出的固有特性，
致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。
2.2.3.1 数制转换十进制 N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理,
N=(n div d)*d+n mod d
( 其中,div为整除运算,mod为求余运算 )
例如 (1348)10=(2504)8,其运算过程如下：
2.2.3 栈的应用举例
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
n n div 8 n mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
void conversion( ) {
int n,*s;
initstack(s);
scanf (“%”,&n);
while(n){
push(s,n%8);
n=n/8;}
while(! stackempty(s)){
pop(s,e);
printf(“%d”,e);}
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
2.2.3.2 表达式求值表达式求值是程序设计语言编译中的一个最基本问题,其实现方法是栈的一个典型的应用实例 。
表达式是由操作数 (operand),运算符 (operator)和界限符 (delimiter)组成的 。
操作数可以是常数,变量或常量的标识符 ;运算符可以是算术运算体符,关系运算符和逻辑符；界限符为左右括号和标识表达式结束的结束符 。 在此仅讨论简单算术表达式的求值 。 在这种表达式中只含加,减,乘,除四则运算,所有的运算对象均为单变量 。 表达式的结束符为,;”。
算术四则运算的规则为：
（ 1） 先乘除,后加减；
（ 2） 同级运算时先左后右；
（ 3） 先括号内,后括号外 。
计算机系统在处理表达式前,首先设置两个栈：
（ 1） 操作数栈 (OPRD)：存放处理表达式过程中的操作数 。
（ 2） 运算符栈 (OPTR)：存放处理表达式过程中的运算符 。 开始时,在运算符栈中先在栈底压入一个表达式的结束符,;”。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜计算机系统在处理表达式时,运算规则如下：
（ 1）假如是操作数,则将其压入操作数栈，并依次读下一个符号。
（ 2）假如是运算符,则：
1）假如读出的运算符的优先级大于运算符栈栈顶运算符的优先级，则将其压入运算符栈,并依次读下一个符号。
2）假如读出的是表达式结束符,;”,且运算符栈栈顶的运算符也为,#”
，则表达式处理结束,最后的表达式的计算结果在操作数栈的栈顶位置。
3）假如读出的是,(”,则将其压入运算符栈。
4）假如读出的是,)”,则：
A）若运算符栈栈顶不是,(”，则从操作数栈连续退出两个操作数，从运算符栈中退出一个运算符，然后作相应的运算，并将运算结果压入操作数栈，然后继续执行 A）。
B）若运算符栈栈顶为,(”,则从运算符栈退出,)”,依次读下一个符号。
5）读出运算符的优先级不大于运算符栈栈顶运算符的优先级,则从操作数栈连续退出两个操作数,从运算符栈中退出一个运算符,然后作相应的运算,将运算结果压入操作数栈,此时读出的运算符下次重新考虑 (即不读入下一个符号 )。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜上述讨论的表达式运算符在两个操作数中间 (除单目运算符外 )，这种表达式被称为 中缀表达式 。中缀表达式有时必须借助括号才能将运算顺序表达清楚，处理起来比较复杂。在编译系统中，对表达式的处理采用的是另外一种方法，即将中缀表达式转变为 后缀表达式,然后对后缀式表达式进行处理，后缀表达式也称为逆波兰式。
波兰表示法 （也称为前缀表达式）是由波兰逻辑学家 Lukasiewicz
提出的，其特点是将运算符置于运算对象的前面，如 a+b表示为
+ab； 逆波兰式 则是将运算符置于运算对象的后面，如 a+b表示为
ab+,中缀表达式经过上述处理后,运算时按从左到右的顺序进行，
不需要括号。得到后缀表达式后，在计算表达式时，可以设置一个栈，从左到右扫描后缀表达式，每读到一个操作数就将其压入栈中；每到一个运算符时，则从栈顶取出两个操作数进行运算，
并将结果压入栈中，一直到后缀表达式读完。最后栈顶就是计算结果。
思考,1+2*(4-sin(3/7+2)) 如何处理?
2.2.2.4 递归 (略 )
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
2.3.1 队列的定义队列 (Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。
允许删除的一端称为队头 (front)，允许插入的一端称为队尾 (rear)。
如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出 (First In First Out)的线性表，简称 FIFO表。
当队列中没有元素时称为空队列。在空队列中依次加入元素 a1,a2,… an之后,a1是队头元素,an是队尾元素。显然退出队列的次序也只能是 a1,a2,… an,
队列的修改是依先进先出的原则进行的。
2.3 队列及其应用
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜下图是队列的示意图：
a1 a2 … an出队 入队队头
front
队尾
rear
2.3.2 队列的顺序表示队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个向量空间来存放。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜由于队列的队头和队尾的位臵是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位臵，它们的初始值地队列初始化时均应臵为
-1。入队时将新元素插入 rear所指的位臵，然后将 rear加１。出队时，删去 front所指的元素，然后将 front加１并返回被删元素。当头尾指针相等时队列为空。 约定 在非空队列中，头指针 front
总是指向队列中实际队头元素的前面一个位臵，
尾指针 rear总是指向队尾元素。
-1 0 1 2 -1 0 1 2 3
Front
rear
a b c
Front rear
(a)队列初始为空 （ b） A,B,C入队
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜-1 0 １ ２ ０ １ ２
b c
front rear front
rear
（ c) a出队 (d) b,c出队，队为空和栈类似，队列中亦有上溢和下溢现象。此外，
顺序队列中还存在,假上溢,现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
2.3.1 顺序队列的基本运算算法
(0) 顺序队列定义
#define queuesize 100
Typedef int datatype;
Typedef struc{ int front,rear; datatype data[queuesize];} sqqueue;
（ 1） 初始化队列
int initQueue(sqqueue *q)
{/*创建一个空队列由指针 q指出 */
if ((q=(sqqueue*)malloc(sizeof(sqqueue))= =NULL) return FALSE;
q->front= -1;
q->rear=-1;
return TRUE;
}
（ 2） 入队列操作
int append(sqqueue *q,datatype x)
{/*将元素 x插入到队列 q中,作为 q的新队尾 */
if(q->rear>=queuesize-1) return FALSE; /*队列满 */
q->rear++;
q->queue[q->rear]=x;
return TRUE;
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
（ 3） 出队列操作
datatype delete(sqqueue*q)
{/*若队列 q不为空,则返回队头元素 */
datatype x;
if(q->rear= =q->front) return NULL; /*队列空 */
x=q->queue[++q->front];
return x;}
（ 4） 取队头元素操作
datatype getHead(sqqueue *q)
{/*若队列 q不为空,则返回队头元素 */
if(q->rear= =q->front) return NULL; /*队列空 */
return (q->queue[q->front+1]); }
（ 5） 判队列非空操作
int Empty(sqqueue *q)
{/*队列 q为空时,返回 TRUE；否则返回 FALSE*/
if (q->rear= =q->front) return TRUE;
return FALSE;}
（ 6） 求队列长度操作
int length(sqqueue *q)
{ return(q->rear-q->front);}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜循环队列是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量,存储在其中的队列称为循环队列 (Circular Queue).在循环队列中进行出队和入队操作时,头尾指针仍要加 1,朝前移动当头尾指针指向向量上界 (QueueSize-1)时,其加 1
操作的结果是指向向量的下界 0。
这种循环意义下的加 1操作可以描述为：
if(i+1==QueueSize) i=0;
else i++;
利用模运算可简化为,i=(i+1)%QueueSize
2.3.2 循环队列
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
0
1
23
4
5front
rear(b)
A
B
C
0
1
23
4
5front
rear
(a)
0
1
23
4
5
A
B
CD
E
F
front
rear
(c)
循环队列示意图
（ a）队列空；（ b）队列非空；
(c)队列满图所示,为循环队列的三种状态,(a)为队列空时,有 q-
>front==q->rear;(c)为队列满时,也有 q->front==q->rear；
因此凭 q->front==q->rear不能判定队列是空还是满 。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜因为循环队列元素的空间可以被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。
因此，除一些简单的应用外，真正实用的顺序队列是循环队列。
由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过 front=rear来判断队列
“空”还是“满”。
为了区分循环队列是空还是满,我们可以设定一个标志位 s,s= 0时为空队列,s=1时队列非空 。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜用 C语言定义循环队列结构如下：
#define MAXNUM 100
Typedef int datatype;
typedef struct
{datatype queue[MAXNUM];
int front; /*队头指针 */
int rear; /*队尾指针 */
int s; /*队列标志位 */
}qqueue;
下面给出循环队列的初始化,入队列及出队列的算法 。
（ 1） 初始化队列
int initQueue(qqueue *q) /*创建一个空队列由指针 q指出 */
{if ((q=(qqueue*)malloc(sizeof(qqueue)))= =NULL) return FALSE;
q->front= MAXNUM;
q->rear=MAXNUM;
q->s=0;
return TRUE; }
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
（ 2） 入队列操作
void append(qqueue *q,datatype x)
{if (( q->s==1)&&(q->front==q->rear)) return FALSE; /*队列满 */
q->rear++;
if (q->rear= =MAXNUM) q->rear=0;
q->queue[q->rear]=x;
q->s=1; /*置队列非空 */ }
（ 3） 出队列操作
datatype delete(qqueue *q)
{datatype x;
if (q->s= =0) retrun NULL; /*队列为空 */
q->front++;
if (q->front= =MAXNUM) q->front=0;
x=q->queue[q->front];
if (q->front = =q->rear) q->s=0; /*置队列空 */
return x; }
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜也可以用一个计数器记录队列中元素的总数 (队列长度 ).下面给出循环队列的类型定义。
#define queuesize 100
typedef char datatype;
typedef Struct{
int front;
int rear;
int count;
datatype data[queuesize]
}cirqueue;
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
（ 1）臵空队
void initqueue(cirqueue *q){
if ((q=(cirqueue *)malloc(sizeof(cirqueue)))==NULL)
error(“内存错误” );
q–>front=q–>rear=0;
q–>count=0; }
（ 2）判断队空
int queueempty(cirqueue *q) {
return q–>count==0; }
（ 3）判断队满
int queuefull(cirqueue *q){
return q–>count==queuesize; }
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
（ 4）入队
void enqueue(cirqueue *q,datatype x)
{
if(queuefull(q))
error(“queue overflow”);
q–>count++;
q–data[q–rear]=x;
q–rear=(q–rear+1)%queuesize;
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
（ 5）出队
datatype dequeue(cirqueue *q)
{ datatype temp;
if(queueempty(q))
error(“queue underflow”);
temp=q–>data[q–>front];
q–>count--;
q–front=(q–>front+1)%queuesize;
return temp;
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
（ 6）取头指针
datatype queuefront(cirqueue *q)
{
if(queueempty(q))
error(“queue is empty.”);
return q–>data[q–>front];
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
2.3.3 队列的应用
2.3.1 工作调度和分配模型分析 (P39)
2.3.2 输入输出缓冲区结构 (略 )
2.3.3 汽车加油站工作模拟 (重点讲解 )
模型分析与详细设计 (P40-44)
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
2.4 串
2.4.1 串类型的定义
2.4.2 串的表示和实现
2.4.2.1 定长顺序存储表示
2.4.2.2 堆分配存储表示
2.4.2.3 串的块链存储表示
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
2.4.1 串类型的定义一、串和基本概念串 (String)是零个或多个字符组成的有限序列。
一般记作 S=“a1a2a3… an”，其中 S 是串名，双引号括起来的字符序列是串值； ai(1≦ i≦ n)可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。长度为零的串称为空串
(Empty String)，它不包含任何字符。
通常将仅由一个或多个空格组成的串称为空白串 (Blank String)
注意：空串和空白串的不同，例如,,和,”
分别表示长度为 1的空白串和长度为 0的空串。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号
（或位臵）。例如，设 A和 B分别为
A=“This is a string” B=“is”
则 B是 A的子串,A为主串。 B在 A中出现了两次，
其中首次出现所对应的主串位臵是 3。因此，
称 B在 A中的序号（或位臵）为 3
特别地，空串是任意串的子串，任意串是其自身的子串。
通常在程序中使用的串可分为两种：串变量和串常量。串常量和整常数、实常数一样，在
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜程序中只能被引用但不能不能改变其值，即只能读不能写。通常串常量是由直接量来表示的，
例如语句 Error(“overflow”)中,overflow”是直接量。但有的语言允许对串常量命名，以使程序易读、易写。如 C++中，可定义
const char path[]=“dir/bin/appl”;
这里 path是一个串常量，对它只能读不能写。串变量和其它类型的变量一样，其取值是可以改变的。
二、串的抽象数据定义串的抽象数据类型定义台书 P71
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜三、串的基本操作对于串的基本操作，许多高级语言均提供了相应的运算或标准库函数来实现。下面仅介绍几种在 C语言中常用的串运算，其它的串操作见的文件。
定义下列几个变量：
char s1[20]=“dirtreeformat”,s2[20]=“file.mem”;
char s3[30],*p;
int result;
(1) 求串长 (length)
int strlen(char s); //求串的长度例如,printf(“%d”,strlen(s1)); 输出 13
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
（ 2）串复制 (copy)
char *strcpy(char to,char from);
该函数将串 from复制到串 to中，并且返回一个指向串 to的开始处的指针。
例如,strcpy(s3,s1); //s3=“dirtreeformat”
(3)联接 (concatenation)
char strcat(char to,char from)
该函数将串 from复制到串 to的末尾，并且返回一个指向串 to的开始处的指针。
例如,strcat(s3,”/”)
strcat(s3,s2); //s3=“dirtreeformat/file.mem”
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
(4)串比较（ compare)
int strcmp(chars1,char s2);
该函数比较串 s1和串 s2的大小，当返回值小于 0，
等于 0或大于 0时分别表示 s1<s2\s1=s2或 s1>s2
例如,result=strcmp(“baker”,”Baker”) result>0
result=strcmp(“12”,”12”); result=0
result=strcmp(“Joe”,”Joseph”); result<0
（ 5）字符定位 (index)
char strchr(char s,char c);
该函数是找 c在字符串中第一次出现的位臵，若找到则返回该位臵，否则返回 NULL。
例如,p=strchr(s2,”.”); p 指向,file”之后的位臵
if(p) strcpy(p,”.cpp”); s2=“file.cpp”
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜上述串的操作是最基本的，其中后四个还有变种形式：
strncpy,strncat,strncmp,strnchr。串的其余操作可由这些基本操作组合而成。
例 1、求子串求子串的过程即为复制字符序列的过程，将串 S
中的第 pos个字符开始长度为 len的字符复制到串 T中。
void substr(string sub,string s,int pos,int len)
{
if(pos<0 || pos>strlen(s)-1 || len<0)
error(“parameter error”)
strncpy(sub,&s[pos],len);
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜例 2、串的定位 index(s,t,pos)
在主串中取从第 i个字符起、长度和串 T
相等的子串和 T比较，若相等，则求得函数值为 i，否则值增 1直至 S中不存在和串 T相等的子串为止。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜int index(string s,string t,int pos){
if(pos>0){
n=strlen(s); m=strlen(t); i=pos;
while(i<n-m+1){
substr(sub,s,i,m);
if(strcmp(sub,t)!=0)
++i;
else return(i);
}
}
return(0);
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜2.4.2 串的表现和实现因为串是特殊的线性表，故其存储结构与线性表的存储结构类似。只不过由于组成串的结点是单个字符。串有三种机内表示方法，下面分别介绍。
2.4.2.1定长顺序存储表示定长顺序存储表示,也称为静态存储分配的顺应表。它是用一组连续的存储单元来存放串中的字符序列。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先给出：
#define maxstrlen 256
typedef char sstring[maxstrlen];
sstring s; //s是一个可容纳 255个字符的顺序串。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜一般可使用一个不会出现在串中的特殊字符在串值的尾部来表示串的结束。例如,C语言中以字符
‵ \0′ 表示串值的终结，这就是为什么在上述定义中，串空间最大值 maxstrlen为 256，但最多只能存放 255个字符的原因，因为必须留一个字节来存放
‵ \0′ 字符。若不设终结符，可用一个整数来表示串的长度，那么该长度减 1的位臵就是串值的最后一个字符的位臵。此时顺序串的类型定义和顺序表类似：
typedef struct{
char ch[maxstrlen];
int length;
}sstring; //其优点是涉及到串长操作时速度快。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜2.4.2.2堆分配存储表示这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。所以也称为动态存储分配的顺序表。在 C语言中，利用和等动态存储管理函数，来根据实际需要动态分配和释放字符数组空间。这样定义的顺序串类型也有两种形式。
typedef char *string; //c中的串库相当于此类型定义
typedef struct{
char *ch;
int length;
}hsring;
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
status sinsert(hstring s,int pos,hstring t){
if(pos<1 || pos>s.length+1)
return error;
if(t.length){
if(!(s.ch=(char*)realloc(s.ch,(s.length+t.length
)*sizeof(char)))
exit(overflow);
for(i=s.length-1;i>pos-1;--i)
s.ch[I+t.length]=s.ch[i];
s.ch[pos-1..pos+t.length-
2]=t.ch[0..t.length-1];
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
s.length+=t.length;
}
return ok;
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
int strlen(hstring s){
return s.length;
}
status clearstring(hstring s){
if(s.ch){free(s.ch);s.ch=NULL;}
s.length=0;
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
status strassign(hstring t,char *chars){
//生成一个其值等于串常量 chars的串 t
if(t.ch) free(t.ch);
for(i=0,(c=chars;c;++i),++c);
if(!i) {
t.ch=null; t.length=0;
}
else{
if(!(t.ch=(char *)malloc(I*sizeof(char))))
exit(overflow);
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
t.ch[0..i-1]=chars[0..i-1];
t.length=i;
}
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
int strcmp(hstring s,hstring t){
for(i=0;i<s.length && i<t.length;++i)
if(s.ch[i]!=t.ch[i]
return(s.ch[i]-t.ch[i]);
return s.length-t.length;
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
status concat(hstring t,hstring s1,hstring s2){
if(!(t.ch)=(char*)malloc(s1.length+s2.length)*
sizeof(char)))
exit(overflow);
t.ch[0..s1.length-1]=s1.ch[0..s1.length-1];
t.length=s1.length+s2.length;
t.ch[s1.length..t.length-
1]=s2.ch[0..s2.length-1];
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
Status substr(hstring sub,hstring s,int pos,int
len){
if(pos<1 || pos>s.length || len<0 ||
len>s.length-pos+1)
return error;
if(sub.ch) free(sub.ch);
if(!len){
sub.ch=null;
sub.length=0;
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
else{
sub.ch=(char *)malloc(len*sizeof(char));
sub.ch[0..len-1]=s[pos-1..pos+len-2];
s.length=len;
}
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
2.4.2.3 串的链式存储结构顺序串上的插入和删除操作不方便，需要移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。
typedef struct node{
char data;
struct node *next;
}lstring;
一个链串由头指针唯一确定。
这种结构便于进行插入和删除运算，但存储空间利用率太低。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜为了提高存储密度，可使每个结点存放多个字符。
通常将结点数据域存放的字符个数定义为 结点的大小,显然，当结点大小大于 1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。
对于结点大小不为 1的链串，其类型定为义只需对上述的结点类型做简单的修改即可。
#define nodesize 80
typedef struct node{
char data[nodesize];
struct node *next;
}lstring;
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜2.4.3 串的模式匹配算法子串定位运算又称为模式匹配 (Pattern
Matching)或串匹配 (String Matching)，此运算的应用在非常广泛。例如，在文本编辑程序中，
我们经常要查找某一特定单词在文本中出现的位臵。显然，解此问题的有效算法能极大地提高文本编辑程序的响应性能。
在串匹配中，一般将主串称为目标串，子串称之为模式串。设 S为目标串,T为模式串，且不妨设：
S=“s0s1s2… sn-1” T=“t0t1… tm-1”
串的匹配实际上是对于合法的位臵 0≦ i≦ n-m依次将目标串中的子串 s[i..i+m-1]和模式串
t[0..m-1]进行比较，若 s[i..i+m-1]=t[0..m-1]，
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜其算法段为：
for(i=0;i<=n-m;i++){
if(S[i..i+m-1]=T[0..m-1]
return i;
下面以第二种 定长的顺序串类型 作为存储结构，给出具体的串匹配算法。
int index(sstring s,sstring t,int pos){
int i,j,k;
int m=s.length;
int n=t.length;
for(i=0;i<=n-m;i++){
j=0;k=i;
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜则称从位臵 i开始的匹配成功，亦称模式 t在目标 s中出现；若 s[i..i+m-1] ≠t[0..m -1]，
，则称从位臵 i开始的匹配失败。上述的位臵 i
又称为位移，当 s[i..i+m-1]=t[0..m-1]时,i
称为有效位移；当 s[i..i+m-1] ≠t[0..m -1]时，
i称为无效位移。这样，串匹配问题可简化为是找出某给定模式 T在一给定目标 T中首次出现的有效位移。
串匹配的算法很多，这里我们只讨论一种最简单的称为朴素的串匹配算法。其基本思想是用一个循环来依次检查 n-m+1个合法的位移
i(0≦ i≦ n-m)是否为有效位移，
≠
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
while(j<m && s.ch[k]==t.ch[j]{
k++;j++;
}
if(j==m)
return i;
}
return –1;
}
显然，该算法在最坏情况下的时间复杂度为 O((n-m)m)。
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜链串上的子串定位算法用结点大小为 1的单链表做串的存储结构时，
实现朴素的匹配算法很简单。只是现在的位移是结点地址而非整数，且单链表中没有存储长度信息。若匹配成功，则返回有效位移所指的结点地址，否则返回空指针。具体算法如下：
lstring *lindex(lstring s,lstring t){
lstring *shift,*q,*p;
shift=S;
q=shift;p=t;
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
while(q && p){
if(q->data==p->data){
q=q->next;
p=p->next;
}
else{
shift=shift->next;
q=shift;
p=t;
}
}
Chgx@gliet.edu.cn
数据结构
2003-2004(夏 ) 主讲,陈光喜
if(p==null)
return shift;
else
return null;
}
