《数据结构上清华大学出版社课件》由会员分享，可在线阅读，更多相关《数据结构上清华大学出版社课件（217页珍藏版）》请在金锄头文库上搜索。
1、数据结构数据结构(上上)1数据结构(上)清华大学出版社第第1章章绪论绪论第第2章章线性表线性表第第3章栈和队列章栈和队列第第4章章串串第第5章数组与广义表章数组与广义表2数据结构(上)清华大学出版社第一章第一章绪论绪论3数据结构(上)清华大学出版社学习重点：数据结构的基本概念；数据的逻辑结构、存储结构以及两者之间的关系；算法及特性；大O记号的表示。4数据结构(上)清华大学出版社1.1数据结构的概念数据结构的概念1.2抽象数据类型（抽象数据类型（ADT）1.3算法描述与分析算法描述与分析5数据结构(上)清华大学出版社程序设计的实质即为计算机处理问题编制一组“指令”，首先需要解决两个问题：即算法和
2、数据结构。算法即处理问题的策略；数据结构即为问题的数学模型。6数据结构(上)清华大学出版社数值计算问题的数学模型通常可用一组线性或非线性的代数方程组或微分方程组来描述.非数值计算问题的数学模型正是本门课程要讨论的数据结构。7数据结构(上)清华大学出版社例如：例如：迷宫、棋盘在计算机内部的表示 交叉路口的红绿灯管理 七桥问题 8数据结构(上)清华大学出版社概括地说，概括地说， 数据结构是一门讨论数据结构是一门讨论“描述现描述现实世界实体的数学模型实世界实体的数学模型( (非数值计非数值计算算) )及其上的操作在计算机中如何及其上的操作在计算机中如何表示和实现表示和实现”的学科。的学科。9数据结构
3、(上)清华大学出版社一、基本概念和术语一、基本概念和术语二、数据结构二、数据结构三、数据类型和抽象数据类型三、数据类型和抽象数据类型10数据结构(上)清华大学出版社 所有能被输入被输入到计算机中，且能被计算机处理的符号处理的符号( (数字、字符等数字、字符等) )的集合。数据数据是计算机操作的对象计算机操作的对象的总称。 是计算机处理的信息的信息的某种特定的符号表示形式表示形式。11数据结构(上)清华大学出版社 是数据（集合）中的一个 “个体个体”,在计算机中通常作为一个整体进行考虑和处理。是数据结构中讨论的基基本单位本单位。数据元素数据元素例如，学生信息系统中学生信息表中的一个记录12数据结
4、构(上)清华大学出版社它是数据结构中讨论的最小最小单位。 又如,描述一个学生的数据元素由多个款项构成，其中每个款项称为一个“数据项数据项”。称之为组合项称之为组合项年月日姓 名学 号班 号性别出生日期入学成绩原子项原子项13数据结构(上)清华大学出版社数据对象数据对象 具有相同特性的数据元素的集合。如:整数、实数等。14数据结构(上)清华大学出版社数据结构数据结构1.指互相之间存在着一种或多种关系的数据元素的集合。2.在任何问题中，数据元素之间都不会是孤立的，在它们之间都存在着这样或那样的关系，这种数据元素之间的关系称为结构。15数据结构(上)清华大学出版社如，在 2行 3列的二维数组中六个元
5、素a1,a2,a3,a4,a5,a6之间存在着两个关系:“行行” ” 的次序关系的次序关系:row=,col=,“列列” ” 的次序关系的次序关系: :a1a2 a3a4a5 a616数据结构(上)清华大学出版社 在含6个数据元素a1,a2,a3,a4,a5,a6的集合上存在如下的次序关系次序关系:|i=1,2,3,4,5可见，不同的“关系关系”构成不同的“结构结构”则构成“一维数组一维数组” 。17数据结构(上)清华大学出版社数据结构的形式定义描述数据结构的形式定义描述为:数据结构数据结构是一个二元组 Data_Structures=(D,R)其中: D是数据元素的有限集数据元素的有限集，
6、R是D上关系的有限集关系的有限集。18数据结构(上)清华大学出版社从关系关系或结构结构分，数据结构数据结构可归结为以下四类四类: :线性线性结构树形树形结构图状图状结构集合集合结构19数据结构(上)清华大学出版社数据结构包括“逻辑结构逻辑结构” 和“物理结物理结构构”两个方面(层次):逻辑结构逻辑结构 是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系来表示;物理结构物理结构 是逻辑结构在计算机中的表示和实现，故又称“存储结构存储结构” 。20数据结构(上)清华大学出版社数据的存储结构关系有两种表示方法：数据的存储结构关系有两种表示方法：顺序存储顺序存储以以
7、B相对于相对于A的存储位置的存储位置表示表示B是是A的后继的后继例如例如: :令 B 的存储位置和 A 的存储位置之间相差一个预设常量 C，而 C 是一个隐含值， A B21数据结构(上)清华大学出版社链式存储链式存储以附加信息以附加信息( (指针指针) )表示后继关系表示后继关系以和A绑定在一起的附加信息(指针)表示后继关系，这个指针即为B的存储地址，由此得到的数据存储结构为链式存储结构。B A以“由数据元素A的存储映象和附加的指针合成的结点结点”表示数据元素。22数据结构(上)清华大学出版社存储结构的描述方法随编程环境的不同而不同，对每一个数据结构而言，必定存在与它密切相关的一组操作。若操
8、作的种类和数目不同，即使逻辑结构相同，数据结构能起的作用也不同。 23数据结构(上)清华大学出版社数据类型数据类型（Data Type）是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型抽象数据类型（Abstract Data Type，简称ADT）是指一个数学模型以及定义在该模型上的一组操作 24数据结构(上)清华大学出版社抽象数据类型形式定义为：抽象数据类型形式定义为：ADT抽象数据类型名数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义25数据结构(上)清华大学出版社一、什么是算法一、什么是算法二、算法技术分析初步二、算法技术分析初步三、算法效率的衡量方
9、法和准则三、算法效率的衡量方法和准则四、算法的存储空间需求四、算法的存储空间需求26数据结构(上)清华大学出版社 是一个有穷的规则集合，这是一个有穷的规则集合，这些规则为解决某一特定任务规定了些规则为解决某一特定任务规定了一个一个运算序列运算序列。算法算法描述算法的方法有：描述算法的方法有：自然语言自然语言程序设计语言（或类程序设计语言）程序设计语言（或类程序设计语言）流程图（包括传统流程图和流程图（包括传统流程图和N-S结构图）结构图）伪语言伪语言PAD图图27数据结构(上)清华大学出版社一个算法必须满足以下五五个重要特性特性：3可行性可行性1有穷性有穷性2确定性确定性5有输出有输出4有输入
10、有输入28数据结构(上)清华大学出版社有穷性有穷性一个算法必须在有穷步之后正常结束，即必须在有限时间内完成而不能形成无穷循环。确定性确定性算法的每一步必须有确切的定义，无二义性。算法的执行对应着的相同的输入仅有唯一的一条路经。 29数据结构(上)清华大学出版社可行性可行性 算法中的每一条指令必须是切实可行的，即原则上可以通过已经实现的基本运算执行有限次来实现。有输入有输入 一个算法具有零个或多个输入，这些输入取自特定的数据对象集合。30数据结构(上)清华大学出版社有输出有输出 一个算法具有一个或多个输出，这些输出同输入之间存在某种特定的关系。31数据结构(上)清华大学出版社健壮性健壮性 当输入
11、的数据非法非法时，算法应当恰当地作出反映或进行相应处理进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出处理出错的方法错的方法不应是中断程序的执行，而应是返回返回一个表示错误或错误性质的值表示错误或错误性质的值，以便在更高的抽象层次上进行处理。32数据结构(上)清华大学出版社和算法执行时间时间相关的因素因素：1问题的规模问题的规模2 2书写程序的语言书写程序的语言 3 3编译程序所生成目标代码的质量编译程序所生成目标代码的质量 4 4硬件的速度硬件的速度 33数据结构(上)清华大学出版社 一个特定算法的算法的 “运行工作量运行工作量” 的大小，只依赖于问题的规模（通常用整数量 n表示），
12、或者说，它是问题规模的函数是问题规模的函数。假如，随着问题规模n的增长，算法执行时算法执行时间的增长率和间的增长率和f(n)的增长率相同的增长率相同，则可记作：T(n)=O(f(n)称称 T(n)为算法的为算法的(渐近)时间复杂度时间复杂度34数据结构(上)清华大学出版社如何估算如何估算 算法的时间复杂度？算法的时间复杂度？35数据结构(上)清华大学出版社1.空间复杂度空间复杂度空间复杂度（Spacecomplexity）是指程序运行从开始到结束所需的存储量。它指的是：当问题的规模以某种单位由1增至n时，解决该问题的算法实现所占用的空间也以某种单位由1增至f(n)。则称该算法的空间代价是f(n
13、)。36数据结构(上)清华大学出版社2.时间复杂度时间复杂度时间复杂度时间复杂度（Timecomplexity）是指程序运行从开始到结束所需要的时间。定义为（大记号）：如果存在两个正常数c和n0，使得对所有的n，nn0，有：f(n)cg(n)则有：f(n)(g(n)称为算法的渐进时间复杂度渐进时间复杂度（AsymptoticComplexity）。37数据结构(上)清华大学出版社例如：算法语句对应的语句频度for（i=0；in;i+）nfor（j=0；jn;j+）n2cij=0;n2for(k=0;kn;k+)n3cij=cij+aik*bkj;n338数据结构(上)清华大学出版社算法的时间复
14、杂度，即是算法的时间量度,记做：T(n)=O(f(n)例如给出X=X+1x=x+1；时间复杂度为O(1)，称为常量阶；for(i=1;i=n;i+)x=x+1;时间复杂度为O(n)，称为线性阶；for(i=1;i=n;i+)for(j=1;j=n;j+)x=x+1;时间复杂度为O(n2),称为平方阶。for(i=0;in-1;i+)for(j=i+1;jn;j+)if(ai.datalast);/*线性表的数据个数*/for(i=1;ilast;i+)printf(ndata=);scanf(%d,&(L-datai-1);/*输入数据*/*Creat_Seqlistend*/59数据结构(上
15、)清华大学出版社 在顺序表指定位置插入元素的过程。在顺序表指定位置插入元素的过程。2往顺序表中插入一个新数据元素往顺序表中插入一个新数据元素60数据结构(上)清华大学出版社图图2-4 2-4 顺序表插入前、后的状态示意顺序表插入前、后的状态示意 61数据结构(上)清华大学出版社线性表的插入是指在表的第i个位置上插入一个值为x的新元素，插入后使原表长为n的表:(a1，a2，.，ai-1，ai，ai+1，.，an)成为表长为n+1的表:(a1，a2，.，ai-1，x，ai，ai+1，.，an)。i的取值范围为1=ilast=MAXSIZE) printf(n Error?n);return(-1)
16、; /* 表空间已满，不能插入! */ if (i L-last) printf(n Error?);return(-1); /*检查插入位置的正确性*/ 63数据结构(上)清华大学出版社 else /* 向后移动数据数据 */ for (j=L-last-1; j=i; j-) L-dataj+1=L-dataj; L-datai=x; /* 插入数据 */ L-last +; /* 线性表长度加1 */ return(1);/*插入成功，返回*/ 64数据结构(上)清华大学出版社插入算法的时间性能分析插入算法的时间性能分析顺序表上的插入运算，时间主要消耗在了数据的移动上，在第i个位置上插入
17、x，从ai到an都要向下(右)移动一个位置，共需要移动n-i+1个元素，而i的取值范围为：1=i=n+1，即有n+1个位置可以插入。设在第i个位置上作插入的概率为Pi，则平均移动数据元素的次数：65数据结构(上)清华大学出版社假设在线性表的任何位置插入元素的概率pi相等（暂不考虑概率不相等情况），则66数据结构(上)清华大学出版社元素插入位置的可能值：i=1,2,n,n+1相应向后移动元素次数：n-i+1=n,n-1,1,0对n,n-1,1,0求总和，显然为n(n+1)/2。所以，插入时数据元素平均移动次数为：67数据结构(上)清华大学出版社这说明：在顺序表上做插入操作需移动表中一半的数据元素
18、。显然时间复杂度为(n)。68数据结构(上)清华大学出版社线性表的删除运算是指将表中第线性表的删除运算是指将表中第 i i 个个元素从线性表中去掉，删除后使原表长为元素从线性表中去掉，删除后使原表长为 n n的线性表：的线性表： (a(a1 1，a a2 2，a ai-1i-1，a ai i，a ai+1i+1，a an n) ) 成成为表长为为表长为 n-1 n-1 的线性表：的线性表：(a(a1 1，a a2 2，a ai-1i-1， a ai+1i+1，a an n) )。 i i 的取值范围为：的取值范围为：1=i=n 1=i=n ，如图如图2-52-5所示。所示。3删除顺序表中的一个
19、数据元素删除顺序表中的一个数据元素69数据结构(上)清华大学出版社图图2-5 2-5 顺序表里删除元素示意顺序表里删除元素示意 70数据结构(上)清华大学出版社 void Delete_Seqlist(Seqlist *L,int i) int j; i-; if (i L-last-1) printf(n Not exist！); else for (j=i+1;jlast-1;j+) L-dataj-1=L-dataj; /* 向前移动数据数据 */ L-last-; /* 线性表长度减1 */ 71数据结构(上)清华大学出版社本算法注意以下问题：本算法注意以下问题：（1）删除第i个元素，
20、i的取值为1=ilast的值为0，条件（iL-last-1）也包括了对表空的检查。（3）删除ai之后，该数据已不存在，如果需要，先取出ai，再做删除。72数据结构(上)清华大学出版社删除算法的时间性能分析：删除算法的时间性能分析：与插入运算相同，其时间主要消耗在了移动表中元素上，删除第i个元素时，其后面的元素 ai+1an 都要向上移动一个位置，共移动了 n-i 个元素，所以平均移动数据元素的次数： 73数据结构(上)清华大学出版社假设在线性表的任何位置删除元素的概率qi相等（暂不考虑概率不相等情况）：元素删除位置的可能值：i=1,2,n相应向前移动元素次数：n-i=n-1,n-2,074数据
21、结构(上)清华大学出版社对n-1,1,0求总和，显然为n(n-1)/2。则删除时数据元素平均移动次数为：这说明顺序表上作删除运算时大约需要移动表中一半的元素，显然该算法的时间复杂度为(n)。75数据结构(上)清华大学出版社 查找顺序表中第一个与给定数据相等的查找顺序表中第一个与给定数据相等的元素的算法。元素的算法。 给定数据给定数据x x，在顺序表，在顺序表L L中查找第一个与中查找第一个与它相等的数据元素。如果查找成功，则返回它相等的数据元素。如果查找成功，则返回该元素在表中的位置；如果查找失败，则返该元素在表中的位置；如果查找失败，则返回回-1-1。算法如下。算法如下: :4在顺序表中查找
22、一个数据元素在顺序表中查找一个数据元素76数据结构(上)清华大学出版社int Location_SeqList(SeqList *L, DataType x) int i=0; while(idatai!= x)i+; if (iL-last-1) return -1; else return i; /*返回的是存储位置返回的是存储位置*/该该算算法法的的主主要要运运算算是是比比较较。显显然然比比较较的的次次数数与与x x在在表表中中的的位位置置有有关关，也也与与表表长长有有关关。当当 a a1 1=x =x 时时，比比较较一一次次成成功功。当当 a an n=x =x 时时比比较较 n n
23、次次成成功功。平平均均比比较较次次数为（数为（n+1n+1）/2/2，时间性能为，时间性能为O(n)O(n)。77数据结构(上)清华大学出版社 打印顺序表中各结点值的算法。打印顺序表中各结点值的算法。算法描述：算法描述： 当顺序表当顺序表L L不空时，将各个结点的值打不空时，将各个结点的值打印输出。算法如下印输出。算法如下: :5打印顺序表的各结点值打印顺序表的各结点值78数据结构(上)清华大学出版社Print_SeqList(SeqList *L) if (L-last = 0) printf (The sequential list is empty !); else for (i=1;
24、ilast; i+) printf (%d, L-datai-1);79数据结构(上)清华大学出版社 获取顺序表现有元素个数的算法。获取顺序表现有元素个数的算法。 算法描述：由于顺序表当前的元素个数，算法描述：由于顺序表当前的元素个数，在其管理信息单元在其管理信息单元L-lastL-last里记录，因此只里记录，因此只需将顺序表需将顺序表L L的的L-lastL-last当前值读出即可。算当前值读出即可。算法如下法如下: :6求顺序表的长度求顺序表的长度80数据结构(上)清华大学出版社Length_ SeqList(SeqList *L) printf (The Length of seque
25、ntial list is =%d, L-last);81数据结构(上)清华大学出版社 往顺序表末尾添加新元素的算法。往顺序表末尾添加新元素的算法。 往顺序表往顺序表L L的末尾添加一个新的数据元的末尾添加一个新的数据元素素x x。算法如下。算法如下: :7往顺序表末尾添加一个新的数据元素往顺序表末尾添加一个新的数据元素82数据结构(上)清华大学出版社Append_ SeqList(SeqList *L, datatype x) if (L-last = MAXSIZE) printf (The sequential list is full !);/* 顺顺序表已序表已满满，不能再插入，不能
26、再插入 */ else L-dataL-last = x ; /* 能能够够插入插入 */ L-last+ ; 83数据结构(上)清华大学出版社 例例2-4 2-4 设计一个算法，将顺序表：设计一个算法，将顺序表： L= (a1, a2,., ai, ai+1, , an1, an ) 中的元素进行逆置，即把顺序表中的元素进行逆置，即把顺序表SqSq中的中的元素排列顺序改换成：元素排列顺序改换成： L = (an, an1, , ai+1,ai, , a2, a1)应用应用:84数据结构(上)清华大学出版社解：为算法取名Invert_SeqList()Invert_ SeqList(SeqLi
27、st *L) if (L-last last-1 ;85数据结构(上)清华大学出版社for (i=0; idatai; /* 把第i个元素暂存于temp */ L-datai = L-dataj; /* 把第j个元素存入表的第i个元素 */86数据结构(上)清华大学出版社L-dataj = temp ; /* 把temp里内容存入表的第j个元素 */ 87数据结构(上)清华大学出版社2.3 2.3 线性表的链式存储与实现线性表的链式存储与实现 采用链式存储结构存放数据时，数据采用链式存储结构存放数据时，数据元素间的邻接关系不是直接通过存储结点元素间的邻接关系不是直接通过存储结点间的位置关系反映
28、出来，而是由每个存储间的位置关系反映出来，而是由每个存储结点里的指针来指明。因此，链式存储结结点里的指针来指明。因此，链式存储结构不要求邻接的数据元素在物理位置上也构不要求邻接的数据元素在物理位置上也是邻接的。是邻接的。 2.3.1 2.3.1 单链表单链表88数据结构(上)清华大学出版社链表是由一个个结点构成的，结点定义如下：typedef struct node DataType data; /*数据域*/ struct node *next; /*指针域*/ LNode，*LinkList；89数据结构(上)清华大学出版社图图2-7 2-7 单链表中存储结点的示意单链表中存储结点的示意
29、90数据结构(上)清华大学出版社 单链表采用的链式存储结构，优点是不单链表采用的链式存储结构，优点是不以表的总存储需求进行存储分配，而是以单以表的总存储需求进行存储分配，而是以单个数据存储结点的大小（个数据存储结点的大小（sizesize）来进行动态）来进行动态存储分配，即当有新的数据元素希望进入链存储分配，即当有新的数据元素希望进入链表时，就按照存储结点的大小向系统提出存表时，就按照存储结点的大小向系统提出存储请求。储请求。 91数据结构(上)清华大学出版社图图2-8 2-8 单链表示意单链表示意 92数据结构(上)清华大学出版社图图2-8 2-8 带头结点的单链表示意带头结点的单链表示意
30、93数据结构(上)清华大学出版社 单链表表头指针的作用是十分重要的，单链表表头指针的作用是十分重要的，因为从它可以找到表的第因为从它可以找到表的第1 1个存储结点，然个存储结点，然后才能够沿着各结点的指针域找到表中的其后才能够沿着各结点的指针域找到表中的其他所有结点。他所有结点。 当单链表为空（即长度为当单链表为空（即长度为0 0）时，其表）时，其表头指针头指针Head=NULLHead=NULL。 94数据结构(上)清华大学出版社 我们假定，如果指针我们假定，如果指针p p指向一个单链表指向一个单链表的存储结点，那么的存储结点，那么“p-Data”p-Data”表示所指结表示所指结点的数据域
31、，点的数据域，“p-Next”p-Next”表示所指结点的表示所指结点的指针域。指针域。 2.3.2 2.3.2 单链表的基本算法描述单链表的基本算法描述95数据结构(上)清华大学出版社插入运算插入运算 Insert_LinkList(L,i,x) Insert_LinkList(L,i,x) ，在链，在链表表L L的第的第i i个元素结点处插入值为个元素结点处插入值为x x的元素。的元素。算法思路：算法思路：. .找到第找到第i-1i-1个结点；若存在继续个结点；若存在继续2 2，否则结束否则结束. .申请、填装新结点；申请、填装新结点；. .将新结点插入。结束。将新结点插入。结束。算法如下
32、：算法如下：1往单链表中插入一个新结点往单链表中插入一个新结点96数据结构(上)清华大学出版社int Insert_LinkList( LinkList L, int i, TataType x) /*在含头结点的单链表L的第i个位置上插入值为x的元素*/ LNode *p,*q; p=L;int k=0; while(p!=NULL)&(knext; k+; /*查找第i-1个结点*/ if (p = =NULL|ki-1) printf(参数i错);return 0; /*第i-1个不存在不能插入*/ 97数据结构(上)清华大学出版社else q=( LNode*)malloc(sizeo
33、f(LNode); q-data=x; /*申请、填装结点*/ q-next=p-next; /*新结点插入在第i-1个结点的后面*/ p-next=q; return 1; 98数据结构(上)清华大学出版社图图2-11 单链单链表上插入表上插入值为值为x的的结结点点99数据结构(上)清华大学出版社 删除单链表删除单链表L L上的第上的第i i个数据结点：个数据结点：Del_LinkList(L,i)Del_LinkList(L,i)算法思路：算法思路： . .找到第找到第i-1i-1个结点；若存在继续个结点；若存在继续2 2，否则结束；否则结束； . .若存在第若存在第i i个结点则继续个结
34、点则继续3 3，否则结，否则结束；束； . .删除第删除第i i个结点，结束。个结点，结束。算法如下：算法如下：2从单链表中删除指定的结点从单链表中删除指定的结点100数据结构(上)清华大学出版社void Del_LinkList(LinkList L，int i) /*删除含头结点的单链表L上的第i个结点*/ LNode *p,*q,*s; q=L,p=q-next;int k=1; while(p&(knext; k+; /*查找第i个结点*/101数据结构(上)清华大学出版社 if (k=i) )q-next=p-next; free(p) ; printf(“删除结点成功。”); el
35、se printf(“inext; L-next=NULL; while (p) q=p-next; p-next=L-next; L-next=p; p=q; 该算法只是对链表中该算法只是对链表中顺序扫描一边即完成顺序扫描一边即完成了倒置，所以时间性了倒置，所以时间性能为能为O(n)O(n)。 104数据结构(上)清华大学出版社2.4 2.4 循环与双向链表循环与双向链表2.4.1双向链表双向链表1双链表的结点双链表的结点 所谓所谓“双向链表双向链表”，是在数据的存储结点，是在数据的存储结点里，存放两个指针域，一个指向它的直接后里，存放两个指针域，一个指向它的直接后继，另一个指向它的直接前驱
36、。继，另一个指向它的直接前驱。 105数据结构(上)清华大学出版社图图2-15 双双链链表表结结点及双点及双链链表示意表示意 106数据结构(上)清华大学出版社双向链表结点的定义如下：双向链表结点的定义如下：typedef struct dlnode DataType data; struct dlnode *prior,*next;DLNode,*DLinkList;107数据结构(上)清华大学出版社 在双链表中值为在双链表中值为x x的结点后插入值为的结点后插入值为y y的的结点。结点。算法思想算法思想: : 先找值为先找值为x x的结点的结点ptr,ptr,有三种情有三种情况况: : 1
37、 1 不存在不存在 2 2 最后一个结点最后一个结点 3 3 一般情况一般情况2在双链表指定位置后插入结点在双链表指定位置后插入结点108数据结构(上)清华大学出版社图图2-16 在双在双链链表上的后向插入示意表上的后向插入示意图图 109数据结构(上)清华大学出版社 删除双链表上删除双链表上datadata域的值为域的值为x x的结点。的结点。算法思想算法思想: : 先找值为先找值为x x的结点的结点ptr,ptr,有四种情有四种情况况: : 1 1 不存在不存在 2 2 最后一个结点最后一个结点 3 3 一般情况一般情况 4 4 最后一个最后一个3将双链表上指定取值的结点删除将双链表上指定
38、取值的结点删除110数据结构(上)清华大学出版社 如果把单链表最后一个结点的如果把单链表最后一个结点的nextnext域存域存储的值由储的值由NULLNULL改为指向表的起始结点，使整改为指向表的起始结点，使整个表的结点首尾相接，形成一个环，这样的个表的结点首尾相接，形成一个环，这样的链表被称为链表被称为“循环链表循环链表”。 2.4.2循环链表循环链表1循环链表的各种形式循环链表的各种形式111数据结构(上)清华大学出版社图图2-18 表表头头指指针针式的循式的循环链环链表表 112数据结构(上)清华大学出版社用表尾指针取代表头指针的循环链表的形式用表尾指针取代表头指针的循环链表的形式 图图
39、2-19 表尾指表尾指针针式的循式的循环单链环单链表表 113数据结构(上)清华大学出版社 在用表尾指针代替表头指针后，要寻找在用表尾指针代替表头指针后，要寻找表的起始结点和终端结点都变得很方便了。表的起始结点和终端结点都变得很方便了。 借助于双链表的概念，也可以把结点组织借助于双链表的概念，也可以把结点组织成循环双链表，如图成循环双链表，如图2-202-20所示。图所示。图2-2-2020（a a）所示为一个循环双链表的示意；图）所示为一个循环双链表的示意；图2-202-20（b b）所示为一个带表头结点的循环双）所示为一个带表头结点的循环双链表，链表，114数据结构(上)清华大学出版社这时
40、是表头结点的这时是表头结点的priorprior域指向链表的域指向链表的终端结点，终端结点的终端结点，终端结点的nextnext域指向表头结点，域指向表头结点，从而构成循环；图从而构成循环；图2-202-20（c c）所示为带表头）所示为带表头结点的空循环双链表的形式，表头结点的结点的空循环双链表的形式，表头结点的priorprior和和nextnext域全都是指向它自己，也就是域全都是指向它自己，也就是在循环双链表空时，满足条件在循环双链表空时，满足条件Ck_h-prior = Ck_h-nextCk_h-prior = Ck_h-next。 115数据结构(上)清华大学出版社图图2-20
41、表表头头指指针针式的循式的循环环双双链链表表116数据结构(上)清华大学出版社 例例2-8 2-8 有两个循环单链表，表头指针有两个循环单链表，表头指针分别是分别是Ck_h1Ck_h1和和Ck_h2Ck_h2。编写一个算法，将链。编写一个算法，将链表表Ck_h1Ck_h1链接到链接到Ck_h2Ck_h2之后，仍然保存循环链之后，仍然保存循环链表的形式。表的形式。 117数据结构(上)清华大学出版社图图2-23 两个循两个循环链环链表的表的链链接接 118数据结构(上)清华大学出版社解：具体算法如下。解：具体算法如下。Link_Ck(LinkList Ck_h1, LinkList Ck_h2)
42、 /*两个两个链链表均非空表均非空*/ ptr = Ck_h1; while (ptr-Next != Ck_h1) /* 找到找到Ck_h1的表尾，的表尾，ptr指向它指向它 */ qtr = Ck_h2 ; while (qtr-Next != Ck_h2) /* 找到找到Ck_h2的表尾，的表尾，qtr指向它指向它 */ qtr-Next = Ck_h1 ; /* 将将Ck_h2链链接到接到Ck_h1之后之后 */ ptr-Next = Ck_h2-next ; /* 保持循保持循环环 */119数据结构(上)清华大学出版社2.5单链表的应用单链表的应用符号多项式的相加操作是线性表处理的
43、典型用例。在数学上的一个多项式:我们称为项多项式，是多项式的项（0in），其中ai为系数，为变数，i为指数，一般多项式可以使用顺序表来表示其数据结构，也可以使用链表来表示。120数据结构(上)清华大学出版社设有两个已知多项式:将两个多项式相加得一个新的多项式C：121数据结构(上)清华大学出版社多项式相加的链表存储结构多项式相加的链表存储结构多项式采用链表来表示。每个结点对应多项式的一个项，存储该项的系数和指数，其结点结构如下：typedefstructpolyintcoef;/*变量的系数*/intexp;/*变量的指数*/structpoly*next;/*指到下一结点的指针*/Lpoly
44、;122数据结构(上)清华大学出版社每个多项式由多个结点组成，高指数的项（高次幂）的结点在链表头部，低指数的项（低次幂）的结点在链表的后部。A，B两个多项式的链表结构图如下：123数据结构(上)清华大学出版社多项式相加的算法实现多项式相加的算法实现为了进行加法运算，设置p,q 两个指针变量分别指向pa,pb两个链表的第一个数据元素结点。然后对p,q两个结点的指数域进行比较。指数相同系数相加，连入C链表；指数不同，将指数较大的结点连入C表。124数据结构(上)清华大学出版社现设C链表头指针pc指向pa（这样充分利用现有结点，节省资源），设指针变量r也指向pa，当有结点连入C表时pc不动r向前移动
45、。每处理一次，相关指针p,q,r一般需要向前移动。125数据结构(上)清华大学出版社126数据结构(上)清华大学出版社 对照后面多项式相加的算法和图2.16可看出两个指数为14的项相加后，得一个系数为11新项连在pc链上。当p,q指针前向后移动之后，将p,q所指两个结点的指数相比，q结点的指数较大，于是将q结点连入pc链。这里p不移动，q,r各向前移动一步，此时链表状态如图2.17所示。127数据结构(上)清华大学出版社图图2.17第二次处理第二次处理结合图示阅读后面的算法，读者自行分析，结合图示阅读后面的算法，读者自行分析，即可得相加后的链表。算法如下：即可得相加后的链表。算法如下：128数
46、据结构(上)清华大学出版社Lpoly *add_poly(Lpoly *pa, Lpoly *pb) p=pa-next; q=pb-next; r=pa; pc=pa; while (p!=NULL) & (q!=NULL) if(p-exp=q-exp) x=p-coef+q-coef; if(x!=0) p-coef=x ; r=p; else r-next=p-next; p=p-next; q=q-next; 129数据结构(上)清华大学出版社 else if(p-expq-exp) r-next=p; r=p; p p-next; else r-next=q; r=q; q=q-n
47、ext; /* while end */ if(p=NULL) r-next=q; else r-next=p; return(pc) /* add_poly end */ 130数据结构(上)清华大学出版社第3章 栈和队列131数据结构(上)清华大学出版社 栈和队列是二种特殊的线性表。是操作受限的线性表。一、栈一、栈1 1、栈的概述、栈的概述 栈(Stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。132数据结构(上)清华大学出版社根据栈的定义可知，最先放入栈
48、中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。 也就是说，栈是一种后进先出栈是一种后进先出(Last In (Last In First Out)First Out)的线性表，简称为的线性表，简称为LIFOLIFO表。表。133数据结构(上)清华大学出版社 初始化栈：初始化栈：INISTACK(&S)INISTACK(&S) 将栈S置为一个空栈(不含任何元素)。 进栈：进栈：PUSH(&S,X)PUSH(&S,X) 将元素X插入到栈S中，也称为 “入栈”、 “插入”、 “压入”。 出栈：出栈： POP(&S) POP(&S) 删除栈S中
49、的栈顶元素，也称为”退栈”、 “删除”、 “弹出”。 取栈顶元素：取栈顶元素： GETTOP(S)GETTOP(S) 取栈S中栈顶元素。 判栈空：判栈空： EMPTY(S)EMPTY(S) 判断栈S是否为空，若为空，返回值为1，否则返回值为0。2、栈的运算、栈的运算134数据结构(上)清华大学出版社例1：设栈的输入序列是(1,2,3,4),则 不可能是其出栈序列A.1243 B.2134 C.1432 D.4312 E.3214例2：依次读入数据元素序列(a,b,c,d,e,f,g)进栈，每进一个元素，机器可要求下一个元素进栈或出栈；如此进行，则栈空时弹出的元素构成的序列是以下哪些序列？ A.
50、decfbga B.fegdacb C.efdgbca D.cdbefag 135数据结构(上)清华大学出版社例3：一个输入序列abcd经过一个栈到达输出序列，并且一旦离开输入序列后就不能再返回到输入序列，则下面为正确输出序列。A.bcadB.cbdaC.dabcD.acbdE.dcba二、顺序栈 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。并设指针top指向栈顶元素的当前位置。136数据结构(上)清华大学出版社1、顺序栈存储结构定义：、顺序栈存储结构定义：Structseqstackelemtypestackmaxsize;inttop;注释：空栈时注释：空栈时top=0,进栈
51、一个元素进栈一个元素top+1.137数据结构(上)清华大学出版社2、顺序栈的主要运算、顺序栈的主要运算进栈操作进栈操作voidpush(ElemTypex)if(top=MAXSIZE-1)printf(“溢出溢出”);exit(1);elsetop+;elemtop=x;138数据结构(上)清华大学出版社出栈出栈ElemTypepop()ElemTypex;if(top!=0)x=elemtop;top-;returnx;elseprintf(“栈为空栈为空!”);exit(1);139数据结构(上)清华大学出版社三、链栈三、链栈typedef struct Lsnode ElemType
52、 data; struct Lsnode *next; Lsnode *top; 一个链表栈由栈顶指针一个链表栈由栈顶指针top唯一确定。唯一确定。 140数据结构(上)清华大学出版社进栈操作 void Push(Lsnode *top; ElemType x)void Push(Lsnode *top; ElemType x) p=(Lsnode *)malloc(sizeof(Lsnode); p=(Lsnode *)malloc(sizeof(Lsnode); p-data=x; p-data=x; p-next=top-next; p-next=top-next; top-next=p
53、; top-next=p; /*Push*/ /*Push*/ 1、链栈的主要运算、链栈的主要运算141数据结构(上)清华大学出版社出栈操作 ElemType Pop(Lsnode *top) ElemType Pop(Lsnode *top) if(top-next!=NULL) if(top-next!=NULL) p=top-next; top-next=p-next; p=top-next; top-next=p-next; x=p-data; free(p); return x; x=p-data; free(p); return x; else printf(Stack null!
54、 n); else printf(Stack null! n); return #; return #; /*Pop*/*Pop*/142数据结构(上)清华大学出版社1 1、队列的概述、队列的概述 仅允许在一端进行插入，另一端进行删除的线性表，称为队列(queue)。允许插入的一端称为队尾(rear)，允许删除的一端称为队头（front）。 队队列列是是一一种种先先进进先先出出（First First In In First First OutOut）的的特特殊线性表，或称殊线性表，或称FIFOFIFO表。表。四、队列四、队列143数据结构(上)清华大学出版社2、队列的基本运算、队列的基本运算
55、初始化队列初始化队列 INIQUEUE(&Q)INIQUEUE(&Q) 将队列Q设置成一个空队列。入队列入队列 ENQUEUE(&Q,X) ENQUEUE(&Q,X) 将元素X插入到队尾中，也称“进队” ，“插入”。 出队列出队列 DLQUEUE(&Q) DLQUEUE(&Q) 将队列Q的队头元素删除，也称“退队”、“删除”。取队头元素取队头元素 GETHEAD(Q) GETHEAD(Q) 得到队列Q的队头元素之值。判队空判队空 EMPTY(Q) EMPTY(Q) 判断队列Q是否为空，若为空返回1，否则返回0。144数据结构(上)清华大学出版社1. 1. 队列的顺序存储数据类型描述队列的顺序存
56、储数据类型描述structseqqueueelemtypequeuemaxsize;intfront;/队头指针intrear;/队尾指针;五、顺序队列五、顺序队列145数据结构(上)清华大学出版社2. 2. 顺序队列顺序队列 理论上讲，若尾指针理论上讲，若尾指针rearrear指向一维数组最后指向一维数组最后, ,而头而头指针指向一维数组开头，称为指针指向一维数组开头，称为队满队满。 但但有有可可能能出出现现这这样样情情况况，尾尾指指针针指指向向一一维维数数组组最最后后，但但前前面面有有很很多多元元素素已已经经出出队队，即即空空出出很很多多位位置置，这这时时要要插插入入元元素素，仍仍然然会会
57、发发生生溢溢出出。我我们们将将这这种种溢溢出出称为称为“假溢出假溢出”。146数据结构(上)清华大学出版社 要克服“假溢出”，方法一：平移法。可以将整个队列中元素向前移动，直到头指针front为-1，或者每次出队时，都将队列中元素前移一个位置。因此，顺序队列的队满判定条件为rear=maxsize。但是，在顺序队列中，这些克服假溢出的方法都会引起大量元素的移动，花费大量的时间，所以在实际应用中很少采用，另一方法：采用循环队列形式。3. 3. 循环队列循环队列为了克服顺序队列中假溢出，通常将一维数组queue0到qmaxsize-1看成是一个首尾相接的圆环，即queue0与queuemaxsiz
58、e-1相接在一起。将这种形式的顺序队列称为循环队列，见下图。147数据结构(上)清华大学出版社思考：会产生思考：会产生什么问题？如什么问题？如何解决？何解决？148数据结构(上)清华大学出版社进队列voidenqueue(seqqueueq,elemtypex)if(q.rear+1)%maxsize=q.front)printf(“overflow!n”);elseq.rear=(q.rear+1)%maxsize;q.queueq.rear-1=x;149数据结构(上)清华大学出版社出队列voiddlqueue(seqqueueq)if(q.rear=q.front)printf(“und
59、erflow”);elseq.front=(q.front+1)%maxsize;150数据结构(上)清华大学出版社1 .1 .链队列的数据类型描述链队列的数据类型描述structlink/定义单链表数据类型elemtypedata;link*next;structlinkqueue/定义链队列数据类型link*front,*rear;/定义头指针和尾指针;六、链队列六、链队列151数据结构(上)清华大学出版社152数据结构(上)清华大学出版社入队列voidpush(linkqueue&s,elemtypex)link*p;p=malloc(sizeof(link);p-data=x;p-ne
60、xt=s.rear-next;s.rear-next=p;s.rear=p;2 .2 .链队列的运算链队列的运算153数据结构(上)清华大学出版社出队列voidpop(linkqueue&s)link*p;p=s.front-next;if(p-next=NULL)s.front-next=NULL;s.rear=s.front;elses.front-next=p-next;free(p);154数据结构(上)清华大学出版社 从上述出队列算法中可知，若链队列中只有一个元素时，需作特殊处理(用if语句判断)，修改队尾指针。为了避免修改队尾指针，我们可以采用一种改进的出队列算法。其基本思想是：出
61、队列时，修改头指针，删除头结点而非队头结点，这时，将队头结点成为新的头结点，队列中第二个结点成为队头结点。这时，不管队列中有多少个元素，都不需作特殊处理（不需用if语句来判断），这种改进的算法如下：voidpop(linkqueue&s)link*p;p=s.front;s.front=p-next;free(p);155数据结构(上)清华大学出版社八、队列的应用八、队列的应用 队列在日常生活中和计算机程序设计中，有着非常重要的作用，在此，仅举出两个方面例子来说明它，其它应用在后面章节中将会遇到。 第一个例子就是CPU资源的竞争问题。在具有多个终端的计算机系统中，有多个用户需要使用CPU各自运
62、行自己的程序，它们分别通过各自终端向操作系统提出使用CPU的请求，操作系统按照每个请求在时间上的先后顺序，将其排成一个队列，每次把CPU分配给队头用户使用，当相应的程序运行结束，则令其出队，再把CPU分配给新的队头用户，直到所有用户任务处理完毕。156数据结构(上)清华大学出版社第二个例子就是主机与外部设备之间速度不匹配的问题。以主机和打印机为例来说明，主机输出数据给打印机打印，主机输出数据的速度比打印机打印的速度要快得多，若直接把输出的数据送给打印机打印，由于速度不匹配，显然是不行的。所以解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依此写如到这个缓冲区中，写满后就暂停输出，继而
63、去做其它的事情，打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求，主机接到请求后再向缓冲区写入打印数据，这样利用队列既保证了打印数据的正确，又使主机提高了效率。157数据结构(上)清华大学出版社第第4章章串串4.1 串的基本概念4.2 串的存储与实现4.3 串的模式匹配158数据结构(上)清华大学出版社 串是一种特殊的线性表，特殊性在于它串是一种特殊的线性表，特殊性在于它的每个数据元素只能是字符，在于串可以作的每个数据元素只能是字符，在于串可以作为整体参与所需要的处理。为整体参与所需要的处理。 159数据结构(上)清华大学出版社 本章主要介绍以下几个方面的内容：
64、本章主要介绍以下几个方面的内容： 串的基本知识；串的基本知识； 串的存储实现及各种处理算法；串的存储实现及各种处理算法； 串的模式匹配；串的模式匹配；160数据结构(上)清华大学出版社4.14.1.1 .1 串串的基础知识的基础知识 串，就是通常所说的字符串，是一种特串，就是通常所说的字符串，是一种特殊的线性表，它的数据元素仅限于是字符殊的线性表，它的数据元素仅限于是字符（英文字母、数字、空格以及其他字符）。（英文字母、数字、空格以及其他字符）。可把串定义如下。可把串定义如下。 161数据结构(上)清华大学出版社 “ “串串”是由是由0 0个或多个字符构成的一个个或多个字符构成的一个有限序列，
65、用双引号作为其定界符。若有一有限序列，用双引号作为其定界符。若有一个串个串s s： s = “cs = “c1 1c c2 2c cn n1 1c cn n （n n0 0） 那么，那么，s s被称为是该串的被称为是该串的“串名串名”， c c1 1c c2 2ccn n1 1c cn n就是串就是串s s的的“值值”。162数据结构(上)清华大学出版社 括在双引号内的字符个数括在双引号内的字符个数n n，称为字符，称为字符串的串的“长度长度”。当。当n=0n=0时，称其是一个时，称其是一个“空空串串”。 串中每个字符的序号，称为它在字符串中每个字符的序号，称为它在字符串的串的“位置位置”。字
66、符串中任意多个连续字符。字符串中任意多个连续字符所组成的子序列，称作是该串的所组成的子序列，称作是该串的“子串子串”，字符串本身称为字符串本身称为“主串主串”。子串第。子串第1 1个字符个字符在主串中的位置，称作是该子串在在主串中的位置，称作是该子串在“主串中主串中的位置的位置”。163数据结构(上)清华大学出版社4.2.1定长顺序串定长顺序串4. 2 4. 2 串的存储与实现串的存储与实现这这种种存存储储方方法法也也称称为为静静态态存存储储。类类似似于于线线性性表表的的顺顺序序存存储储结结构构，用用一一组组地地址址连连续续的的存存储储单单元元存存储储串串值值的的字字符符序序列列。即即用用数数
67、组组表表示示串串，实实际际上上是是把把串串作作为为特特殊殊的的表表来来表表示示，特特殊殊性性在在于于表表中中的的元元素素类类型型为为字字符符型型。按按照照事事先先定定义义的的大大小小，为为每每个个串串变变量量分分配配一一个个固固定长度的存储区，用定长度的存储区，用C C可描述为：可描述为：164数据结构(上)清华大学出版社/*-定长顺序串-*/#defineMAXSTRLEN255;/*用户自己定义的最大串长*/TypedefstructcharchMAXSTRLEN+1;SString;165数据结构(上)清华大学出版社采用定长顺序存储方式时，进行串的连接操作和插入等操作时，极有可能出现连接
68、后的字符串或插入后的字符串的长度超过预定义的长度MAXSTRLEN，此时会将多出的部分用“截断”的方法处理。这样，就得不到正确的结果。166数据结构(上)清华大学出版社这就要求事先将串的最大长度定的大一些，但是又会出现浪费空间的问题。克服这个缺点是使用不限定串长的最大长度的方法，即动态分配串值的存储空间。167数据结构(上)清华大学出版社4.2.2堆串堆串串的堆分配存储表示即串的动态分配存储空间。这种存储表示的特点是：仍以一组地址连续的存储单元存放字符序列，但是它们的存储空间是在程序执行过程中动态分配而得。168数据结构(上)清华大学出版社即每个串的存储首地址是在算法执行过程中是动态分配的。在
69、C语言中，已经有一个称为堆的存储空间，动态分配用malloc()和free()函数来完成。169数据结构(上)清华大学出版社堆串的定义堆串的定义typedefstructchar*ch;/*串数组*/intlength;/*串长*/HString;HStrings1;170数据结构(上)清华大学出版社s1.ch=(char*)malloc(length);/*动态分配存储空间，让s1.ch指向它*/free(s1.ch);/*串的空间释放*/由于堆分配存储结构的特点，因此在串处理的应用程序中常被选用。171数据结构(上)清华大学出版社4.2.3串操作的实现串操作的实现前面已介绍了串的几种存储表
70、示。其中堆串是串处理的软件中常被选用的方法。下面就堆分配存储前提下，对串运算的实现进行介绍。 172数据结构(上)清华大学出版社1.串赋值函数串赋值操作是将一个字符串常量tval赋值给串S.算法如下：173数据结构(上)清华大学出版社intStrAssign(HString*S,char*tval)/*将字符串tval的值赋值给串S*/intlen,i=0;if(S-ch!=NULL)free(S-ch);while(tvali!=0)i+;len=i;/*把串tval的长度赋值给len*/174数据结构(上)清华大学出版社if(len)S-ch=(char*)malloc(len);if(S
71、-ch=NULL)return(0);for(i=0;ichi=tvali;/*把串tval赋值给S*/elseS-ch=NULL;S-length=len;return(1);175数据结构(上)清华大学出版社2串插入函数串的插入是指在当前主串的pos位置插入一个子串T。这和线性表的插入明显不同，线性表在指定位置仅插入一个数据元素，而串插入在指定位置插入若干个连续字符。176数据结构(上)清华大学出版社具体实现方法为，将原串中从插入位置pos开始以及后面的字符逐次向后移动相应位置，具体移动长度是插入子串的长度T.length。将从pos到pos+T.length-1的存储空间腾出来，以便装入
72、子串T。原字符串的长度变为length+s.length。算法如下：177数据结构(上)清华大学出版社voidStrInsert(HString*S,intpos,HStringT)/*若1posStrLength(S)1，则在串S的第pos个*/*字符之前插入串T，*/if(posS-length+1)printf(“n位置错误!”);return;/*插入位置不合法*/charS1S-length;/*S1作为辅助串空间用于暂存S-ch*/178数据结构(上)清华大学出版社if(T.length)/*T非空，则为S重新分配空间并插入T*/p=S-ch;i=0;while(ilength)S
73、1i+=*(p+i);/*暂存串S*/S-ch=newcharS-length+T.length;/*为S重新分配串值存储空间*/for(i=0,k=0;ichk+=S1i;/*保留插入位置之前的子串*/j=0;179数据结构(上)清华大学出版社while(jchk+=T.chj+;/*插入T*/while(ilength)S-chk+=S1i+;/*复制插入位置之后的子串*/S-length+=T.length;/*置串S的长度*/*if*/*StrInsert*/180数据结构(上)清华大学出版社3串的删除函数串的删除，指把当前主串的第pos位置开始的len个字符删除。实现方法为，将当前串
74、从pos+len位置到字符串尾部的字符依次向前移动len个位置，原字符串的长度变为length-len。算法如下：181数据结构(上)清华大学出版社voidStrDelete(HString*S,intpos,intlen)if(posS-length)printf(n位置错误!);elseif(pos+lenS-length)S-length=pos-1;/*删除的长度超出主串，截尾*/182数据结构(上)清华大学出版社elsefor(inti=pos+len-1;ilength;i+)S-chi-len=S-chi;/*字符逐个向前移动，跳过len个*/S-length=S-length-
75、len;/*设置删除后的新串长*/183数据结构(上)清华大学出版社4串的清空函数该函数是将串清为空串，并释放占用的内存空间。算法如下：intStrClear(HString*S)if(S-ch)free(S-ch);S-ch=NULL;S-length=0;return(1);184数据结构(上)清华大学出版社5串的复制函数该函数是将一个字符串的值复制到另一个串中。算法如下：185数据结构(上)清华大学出版社intStrCopy(HString*S,HStringT)if(S-ch)free(S-ch);/*先清空S*/S-ch=(char*)malloc(T.length);if(S-ch
76、=NULL)return(0);for(inti=0;ichi=T.chi;/*把串T赋值给S*/S-length=T.length;return(1);186数据结构(上)清华大学出版社6串的比较函数该函数是比较两个字符串S和T，当两个串相等时返回0;ST时返回1。算法如下：187数据结构(上)清华大学出版社intStrCompare(HStringS,HStringT)for(inti=0;iT.length&ilength);if(temp=NULL)return(0);189数据结构(上)清华大学出版社for(inti=0;ilength;i+)tempi=S-chi;/*先把串S放入
77、临时串temp中*/free(S-ch);S-ch=(char*)malloc(S-length+T.length);/*为S分配新的空间*/for(inti=0;ilength;i+)S-chi=tempi;for(intj=0;jchi+j=T.chj;return(1);.190数据结构(上)清华大学出版社8求子串函数该函数是将某字符串中一连续的字符序列复制到另一个串中。算法如下：voidSubString(HString*Sub,HStringS,intpos,intlen)if(Sub-ch)free(Sub-ch);191数据结构(上)清华大学出版社if(posS.length|l
78、enS.length-pos+1)Sub-ch=NULL;Sub.length=0;elseSub-ch=(char*)malloc(len)if(Sub-ch=NULL)return(0);for(inti=1;ichi=S.chpos-1+i;Sub-length=len;192数据结构(上)清华大学出版社4.3串的模式匹配串的模式匹配子串的定位通常称为串的模式匹配。设有两个字符串S和T，设S为主串，也称正文串。设T为子串也称为模式。在主串S中查找与子串T（模式）相匹配（相同）的子串，如果匹配成功，确定模式串T的第一个字符在主串S中出现的位置。称查找模式T在主串S中的匹配位置的运算为模式匹
79、配。193数据结构(上)清华大学出版社算法从主串S的第pos个字符开始查找一个与模式串T相同的子串，若在串S中找到一个与T相同的子串，则函数返回模式串T的第一个字符在串S中出现的位置；若在主串S中从pos位置开始没有找到一个与模式串T相同的子串，则函数返回-1。194数据结构(上)清华大学出版社4.3.1朴素模式匹配算法朴素模式匹配算法主要思想：从主串S的第pos个字符起和模式T的第一个字符进行比较，若相等则继续比较S和T的后续字符；否则从主串S的第pos+1个字符起再重新和模式T的第一个字符进行比较。依次类推，直至模式T和主串S的一个子串完全相等，则称匹配成功，否则称匹配失败。195数据结构
80、(上)清华大学出版社算法如下：intStrIndex(HStringS,intpos,HStringT)if(S.length=0|T.length=0)return(0);inti=pos-1,j=0;while(iS.length&j=T.length)return(i-j+1);/*存在返回第一次出现的位置*/elsereturn(0);196数据结构(上)清华大学出版社朴素模式匹配算法比较简单，易于理解，但效率不高。主要原因是由于主串S指针i回溯消耗了大量的时间。假设主串长度为n=S.length,子串长度为m=T.length,该算法在最好情况下的时间复杂度为O(n+m)。最坏情况下
81、的时间复杂度将达到O(n*m)。197数据结构(上)清华大学出版社4.3.2模式匹配的模式匹配的KMP算法算法(略略)198数据结构(上)清华大学出版社第5章 数组和广义表199数据结构(上)清华大学出版社 一、数组的定义一、数组的定义 如果把一维数组看成是一个定长的线性表，则二维数组可看成：它的每个数据元素也是一个定长线性表。(a1,a2, , ap)200数据结构(上)清华大学出版社 对于Amn，可看成下面的线性表： A=(1 ，2 ，3 ， p ) (p=m或n) 其中，每个数据元素j 是一个列向量形式线性表。 j =(1j ，2j ，3j ， mj ) 1=j=n或者是一个行向量形式线
82、性表 j =(j1 ，j2 ，j3 ， jn ) 1=j=m即，二维数组可看成是一维数组的一维数组类型。二、数组的顺序表示和实现二、数组的顺序表示和实现 一旦建立，则结构中的数据元素个数和元素之间关系就不再变动。 以列序为主序如Fortran语言 以行序为主序如C、pascal 二维数组存储方式201数据结构(上)清华大学出版社202数据结构(上)清华大学出版社 假设每个数据元素占L个存储单元，则二维数组A中任一元素aij的存储位置由下式确定：以行为主序以行为主序 LOC(i,j)=+(i-1)n+(j-1)d LOC(i,j)=+(j-1)m+(i-1)d 例：设数组a0.49,0.79的基
83、地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a45,68的存储地址为()；若以列序为主序存储，则元素a45,68的地址为().以列为主序以列为主序203数据结构(上)清华大学出版社三、特殊矩阵的压缩存储三、特殊矩阵的压缩存储 即为多个值相同的元只分配一个存储空间，而对零元不分配空间。 假设值相同的元素或零元素在矩阵中的分布有一定规律，则称此类矩阵为特殊矩阵；反之，称为稀疏矩阵。 n阶矩阵中的元满足aij=aji，则称为n n阶对称矩阵阶对称矩阵。5阶对称矩阵 204数据结构(上)清华大学出版社 下下( (上上) )三角矩阵是三角矩阵是指矩阵的上(下)三角中的元均为常数
84、或零的n阶矩阵。则只需存储下(上)三角中的元和一个常数即可。 对角矩阵，对角矩阵，即所有非零元都集中在以主对角线为中心的带状区域。下三角矩阵 上三角矩阵 205数据结构(上)清华大学出版社 3对角矩阵 四、稀疏矩阵的压缩存储四、稀疏矩阵的压缩存储 非0元远远比0元少，且分布没一定规律。=t/mn0.05时为稀疏矩阵。注：注：t为非0元个数。为稀疏因子。206数据结构(上)清华大学出版社 稀疏矩阵中的非0元可由三元组(i,j,aij)确定。则三元组表和行列数可唯一确定一个稀疏矩阵。1 1、三元组顺序表、三元组顺序表207数据结构(上)清华大学出版社ijv131228243332411454ijv
85、141228311332423544 按矩阵按矩阵A A的列序进行转置。的列序进行转置。即按转置后的即按转置后的B B中三中三元组的次序依次在元组的次序依次在A A的三元组中找到相应三元组进的三元组中找到相应三元组进行转置。行转置。( (把把A A中列序号最小的先进行转置中列序号最小的先进行转置) )A的三元组表A的转置三元组表B关键是重排三元组之间的次序。关键是重排三元组之间的次序。有二种方法：有二种方法：如何由如何由A A变成转置矩阵变成转置矩阵B B？208数据结构(上)清华大学出版社按按A A中三元组次序进行转置，并将转置后的三元组放中三元组次序进行转置，并将转置后的三元组放入入B B
86、中恰当位置。中恰当位置。 设设num和和cpot二个向量。二个向量。numcol表示表示A中第中第col列列非非0元个数，元个数，cpotcol表示表示A中第中第col列第一个非列第一个非0元在元在B三元组表中位置。三元组表中位置。 cpot1=1cpotcol=cpotcol-1+numcol-1col12345numcol11211cpotcol12356209数据结构(上)清华大学出版社2 2、稀疏矩阵的链式存储结构、稀疏矩阵的链式存储结构 稀疏矩阵中同一行的非零元通过向右的right指针链接成一个带表头结点的循环链表。 同一列的非零元也通过down指针链接成一个带表头结点的循链链表。因
87、此，每个非零元既是第i行循环链表中的一个结点，又是第j列循环链表中的一个结点，相当于处在一个十字交叉路口，故称链表为十字链表。 十字链表组成 在链表中，每个非0元可用一个含5个域的结点表示。注：行指针域(right)，用来指向本行中下一个非零元素； 列指针域(down) ，用来指向本列中下一个非零元素。210数据结构(上)清华大学出版社211数据结构(上)清华大学出版社五、广义表五、广义表 1 1广义表的定义广义表的定义 广义表是n0个元素a1，a2，an的有限序列，其中每一个ai或者是原子，或者是一个子表。广义表通常记为LS=(a1,a2,an)，其中LS为广义表的名字，n为广义表的长度，
88、每一个ai为广义表的元素。但在习惯中，一般用大写字母表示广义表，小写字母表示原子。2 2广义表举例广义表举例 (1)A=(),A为空表，长度为0。212数据结构(上)清华大学出版社(2)B=(a,（b,c）)B是长度为2的广义表，第一项为原子，第二项为子表。(3)C=(x,y,z)C是长度为3的广义表，每一项都是原子。(4)D=(B,C)D是长度为2的广义表，每一项都是上面提到的子表。(5)E=(a,E)是长度为2的广义表，第一项为原子，第二项为它本身。213数据结构(上)清华大学出版社广义表A=(a,b,(c,d),(e,(f,g)Head(Tail(Head(Tail(Tail(A)=?2
89、14数据结构(上)清华大学出版社3 3、广义表的深度、广义表的深度 一个广义表的深度是指该广义表展开后所含括号对的数目。 例如，A=(b,c)的深度为1，B=(A,d)的深度为2，C=(f,B,h)的深度为3。215数据结构(上)清华大学出版社4 4、存储结构、存储结构 由于广义表的元素类型不一定相同，因此，难以用顺序结构存储表中元素，通常采用链接存储方法来存储广义表中元素，并称之为广义链表。常见的表示方法有：单链表表示法 即模仿线性表的单链表结构，每个原子结点只有一个链域link，结点结构是：216数据结构(上)清华大学出版社可用如下图的结构描述广义表C=(A,B)=(x,(a,b),(x,(a,b),y) ，设头指针为hc。 217数据结构(上)清华大学出版社
