数据结构学习培训课件

1、数 据 结 构第一章 绪 论1.1 什么是数据结构1.2 有关概念和术语1.3 算法和算法分析 1.3.1 算法 1.3.2 算法设计的要求 1.3.3 算法效率的度量 1.3.4 算法的存储空间的需求第一章 绪 论 计算机是一门研究利用计算机进行信息表示和处理的科学。涉及： 信息的表示 信息的处理 而信息的表示和组织又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。1.1 什么是数据结构 众

2、所周知，计算机的程序是对信息进行处理。在大多数情况下，这些信息并不是没有组织的，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。什么是数据结构呢？例子： 例1、电话号码查询系统 设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排： (a1，b1)(a2，b2)(an，bn)其中(ai，bi)(i=1，2n) 分别表示某人的名字和对应的电话号码。要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的信息。数据结构含义： 就是研究数据的逻辑结构和物理结构以及它们之间相互关系

3、，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。 所有能被输入到计算机中，且能被计算机处理的符号的集合。数据:是计算机操作的对象的总称。 是计算机处理的信息的某种特定的符号表示形式。1.2 有关概念和术语是数据（集合）中的一个“个体”数据元素:是数据结构中讨论的基本单位数据结构主要指逻辑结构和物理结构 数据之间的相互关系称为逻辑结构。通常分为四类基本结构：一、集合 结构中的数据元素除了同属于一种类型外，别无其它关系。二、线性结构 结构中的数据元素之间存在一对一的关系。三、树型结构 结构中的数据元素之间存在一对多的关系。四、图状结构或网状结构 结构中的数据

4、元素之间存在多对多的关系。 一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。 数据在计算机中的表示称为数据的物理结构，又称为存储结构。 数据对象可以是有限的，也可以是无限的。数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。数据类型：在一种程序设计语言中，变量所具有的数据种类。例1、 在FORTRAN语言中，变量的数据类型有整型、实型、和复

5、数型 例2、在C+语言中数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义数据对象：某种数据类型元素的集合。例3、整数的数据对象是-3，-2，-1，0，1，2，3，英文字符类型的数据对象是A，B，C，D，E，F，1.3 算法和算法分析1.3.1 算法： 是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。 算法具有以下五个特性：（1）有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。（2）确定性 算法中每一条指令必须有确切的含义。不存在二义性。（3）可行性 一个算法是可行的。即算法描

6、述的操作都是可以通过已经实现的基本运算执行有限次来实现的。（4）输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。（5）输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。1.3.2 算法设计的要求设计算法时，通常应考虑达到以下目标：1正确性2. 可读性3健壮性4高效率与低存储量需求1正确性 首先，算法应当满足以特定的“规格说明”方式给出的需求。 其次，对算法是否“正确”的理解可以有以下四个层次：a程序中不含语法错误；b程序对于几组输入数据能够得出满足要求的结果； c程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果； 通常以第 c

7、 层意义的正确性作为衡量一个算法是否合格的标准。 d程序对于一切合法的输入数据都能得出满足要求的结果；2. 可读性 算法主要是为了人的阅读与交流，其次才是为计算机执行，因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。3健壮性 当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。4高效率与低存储量需求通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。1.3.3 算法效率的

8、度量通常有两种衡量算法效率的方法:事后统计法事前分析估算法缺点：1必须执行程序 2其它因素掩盖算法本质和算法执行时间相关的因素：1算法选用的策略2问题的规模3编写程序的语言4编译程序产生的机器代码的质量5计算机执行指令的速度 一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。 假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，则可记作：T (n) = O(f(n)称T(n)为算法的(渐近)时间复杂度。如何估算 算法的时间复杂度？算法 = 控制结构 + 原操作 （固有数据类型的操作）算法的执行时间 =原操作(i

9、)的执行次数原操作(i)的执行时间 算法的执行时间 与 原操作执行次数之和 成正比 从算法中选取一种对于所研究的问题来说是 基本操作 的原操作，以该基本操作 在算法中重复执行的次数 作为算法运行时间的衡量准则。void mult(int a, int b, int c ) for (i=1; i=n; +i) for (j=1; j=n; +j) cij = 0; for (k=1; k=n; +k) cij += aik*bkj; /for /mult基本操作: 乘法操作时间复杂度: O(n3)例1例 +x;s=0; 将x自增看成是基本操作，则语句频度为，即时间复杂度为(1) 如果将s=0也

10、看成是基本操作，则语句频度为1，其时间复杂度仍为(1)，即常量阶。例 for(i=1;i=n;+i) +x;s+=x; 语句频度为：n其时间复杂度为：O(n) 即时间复杂度为线性阶。i=0: 赋值次i=1: 赋值 2 次i=2: 赋值3次i=n-1:赋值n次.+1+2+3+n=(1+n)n/2=n2/2+n/2例 for(i=1;i=n;+i)for(j=1;j=n;+j) +x;s+=x; 语句频度为：n2其时间复杂度为：O(n2) 即时间复杂度为平方阶。例 for(i=0;i=n-1;+i) for(j=0;j1=n0，n为正整数时，xn+1xn，所以：|an|*|xn|+|an-1|*|

11、xn-1|+|a1|*|x1|+|a0|*|x0| |an|*|xn|+|an-1|*|xn|+|a1|*|xn|+|a0|*|xn|=(|an|+|an-1|+|a1|+|a0|)|xn|=c|xn|其中：n0=1, c= |an|+|an-1|+|a1|+|a0|, g(n)=xn 一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。 以下六种计算算法时间的多项式是最常用的。其关系为： O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指数时间的关系为： O(2n

12、)O(n!)0 ;i-) for(j=0;jaj+1) aj aj+1; 最好情况：0次 最坏情况：每次都换， (n2) 例7： 递归程序的分析int fact( int n) if(n=1) return 1; else return n*fact(n-1);f(n)=c+f(n-1) =c+(c+f(n-2) =2c+f(n-2) =(n-1)c+f(1) =(n-1)c+c01.3.4 算法的存储空间的需求算法的空间复杂度定义为: 表示随着问题规模 n 的增大，算法运行所需存储量的增长率与 g(n) 的增长率相同。S(n) = O(g(n)算法的存储量包括:1输入数据所占空间2程序本身所

13、占空间3辅助变量所占空间 若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。 若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。 若所需存储量依赖于特定的输入，则通常按最坏情况考虑。注意：时间与空间往往是对矛盾，要综合考虑。作业：. 计算时间复杂度 sum=1; for(i=0;sumn;i+) sum+=i;2.设给定若干n值，比较两函数n2和50nlog2n的增长趋势，并确定在什么范围内，函数n2的值大于50nlog2n的值。答案: (自做)1.sum=0+1+2+m=m*(m+1)/2n m*(m+1)2n m*m2n m

14、50nlog2n =n 50log2n =2 n n50 =n439 第二章 线性表2.1 线性表的类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加2.1 线性表的逻辑结构 线性表：由n(n0)个数据元素(结点)a1，a2， an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n0)记作： (a1，a2，an) 这里的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。例1、26个英文字母组成的字母表 （A，B

15、，C、Z）例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。 （6，17，28，50，92，188） . . . 神经衰弱 17 男790634张立立 健康 21 男790633刘建平 一般 20 女790632陈 红 健康 18 男790631王小林 健康情况年龄性 别学 号姓 名例3、学生健康情况登记表如下： 从以上例子可看出线性表的逻辑特征是：(1) 对非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；(2) 有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a n-1；(3) 其余的内部结点ai(2in-1)都有且仅有一个直接前

16、趋a i-1和一个直接后继ai+1。 线性表是一种典型的线性结构。 数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。2.2 线性表的顺序存储结构2.2.1 线性表 把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。 假设线性表的每个元素需占用m个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置作为参考点。则线性表中第i+1个数据元素的存储位置Loc(ai+1)和第i个数据元素的存储位置Loc(ai)之间满足下列关系： Loc(ai+1)=Loc(ai)+m aiai+1Loc(ai+1)m个字节Loc(ai)线性

17、表的第i个数据元素ai的存储位置为 : a1a2aianLoc(a1)i-1个元素Loc(ai)=(i-1)*m+Loc(a1)=Loc(a1)-m+i*m由于Loc(a1)和m都是已知的所以：V0= Loc(a1)-mLoc(ai)=V0+i*m 由于在高级语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，利用C+语言的结构类型来定义顺序表类型。 # define ListSize 100 /表容量 typedef int DataType;/以int为例 struct Sqlist Da

18、taType dataListSize; int lenth;/当前表中元素数 ;lenth.SqlistdataListSize个2.2.2 顺序表上实现的基本操作 在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。 注意：C/C+语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素位置是L.datai-1。 线性表的插入和删除两种运算。 1、插入 线性表的插入运算是指在表的i(1in+1)个位置上，插入一个新结点x，使长度为n的线性表 (a1，a i-1，ai，an) 变成长度为n+1的线性表 (a1，a i-1，x，ai，a

19、n)注：可用memmove(L.data+i+1,L.dada+i,(L.lenth-i+1)*sizeof(DataType)代替for循环（包含文件： string.h,一般格式格式： memmove(目的地址，源地址，移动字节数)void InsertList(L,x,i)/在线性表L中第i个位置插入元素x if(iL.length+1) cout“插入序号错误”=ListSize) 溢出处理；else for(j=L.length-1;j=i-1;j-) /第i个元素（下标为i-1)开始 L.dataj+1=L.dataj;/顺序后移 L.datai-1=x; L.length+; m

20、emcpy(目的地址,源地址，字节数）memset(目的地址,字符，字节数）int a5050,b5050;a清0for(i=0;i50;i+) for(j=0;j50;j+) aij=0;拷贝：for(i=0;i50;i+) for(j=0;j最好情况； 当=1时，需移动表中所有结点-最坏情况，a1，a i-1，ai，anx移动数据：n-i+1算法的平均移动 由于插入可能在表中任何位置上进行，在长度为n的线性表中第i个位置上插入一个结点，令Eis(n)表示移动结点的期望值（即移动的平均次数），则在第i个位置上插入一个结点的移动次数为n-i+1。 Pi代表在第i个位置插入概率，则 Eis(n)

21、= p1 * n+p2*(n-1)+ .+ pn*1+pn+1*0 若表中任何位置(1in+1)上插入结点的概率是均等的，则 p1=p2=p3=p n+1=1/(n+1)因此，在等概率插入的情况下： Eis(n)=1/(n+1)n+(n-1)+1+0=n/2a1，a i-1，ai，an可能的插入点有n+1处结论：在顺序表上做插入运算，平均要移动表上一半结点。当表长 n较大时，算法的效率相当低。虽然Eis(n)中n的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为O(n)。 2、删除 线性表的删除运算是指将表的第i(1in)结点删除，使长度为n的线性表： (a1，a i-

22、1，ai，a i+1，an)变成长度为n-1的线性表 (a1，a i-1，a i+1，an)void deleteList(L,i)/表L中删除第i个元素 if(iL.length) cout“删除序号错”endl; return ERROR; for(j=i; jch; while (ch!=$)p=new LNode;pdata=ch; pnext=h; h=p; cin ch; LNode *CreateList( ) char ch; LNode *h,*p; h=NULL; cinch; while (ch!=$) p=new LNode; pdata=ch; pnext=h; h=

23、p; cin ch; return h; #include struct LNode char data; LNode *next;LNode *CreateList( ) char ch; LNode *h,*p; h=NULL; cinch; while (ch!=$) p=new LNode; pdata=ch; pnext=h; h=p; cin ch; return h; void CreateList1( LNode *&h) char ch; LNode *p; h=NULL; cinch; while (ch!=$) p=new LNode; pdata=ch; pnext=h

24、; h=p; cin ch; void print(LNode *h) LNode *p; while(p!=NULL) coutdatanext; coutch; while(ch!=$) p=new LNode; pdata=ch; if(head=NULL) head=p; else r-next=p; r=p;cinch;if(r!=NULL) r-next=NULL; return head;头结点（哨兵结点）引入： 增加一个表头结点，数据域可根据需要使用或不用。特点：a、表中第一个结点和在表的其它位置上的操作一致，无需进行特殊处理；b、无论链表是否为空，其头指针是指向头结点。因此空

25、表和非空表的处理统一。NULLhead有头结点的空表head= 无头结点的空表LNode *creat() LNode *r,*h; char ch; h=new LNode; r=h; cinch;while(ch!=$) r-next=new LNode; r=r-next; r-data=ch; cinch;r-next=NULL; 上述算法里动态申请新结点空间时未加错误处理，在实际使用时间，可作下列判定与处理： p= new LNode; if(p= =NULL) 错误处理； 二、查找运算 1、按序号查找 在链表中，即使知道被访问结点的序号i，也不能象顺序表中那样直接按序号i访问结点，

26、而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。 设单链表的长度为n，要查找表中第i个结点，仅当1=inext & jnext; j+; if (i=j) return p; else return NULL;2、按值查找 按值查找是在链表中，查找是否有结点值等于给定值key的结点，若有，则返回首次找到的其值为key的结点的存储位置；否则返回NULL。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值key作比较。其算法如下：LNode *locatenode(head，key) p=headnext; while( p &

27、pdata!=key) p=pnext; return p; 该算法的执行时间亦与输入实例中的的取值key有关，其平均时间复杂度的分析类似于按序号查找。三、插入运算 插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点，并令q指针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化xai-1ai三、插入运算 插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为

28、x的新结点，并令q指针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化ai-1aix三、插入运算 插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点，并令q指针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化ai-1aix三、插入运算 插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点，并令q指

29、针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化ai-1aixpqq-next=p-next;三、插入运算 插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点，并令q指针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化ai-1aixpqq-next=p-next;p-next=q;三、插入运算 插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到

30、ai-1的存储位置p，然后生成一个数据域为x的新结点，并令q指针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化ai-1aixpqq-next=p-next;p-next=q;三、插入运算 插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点，并令q指针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化ai-1aixpqq-next=p-next;p-next=q;定位ai-1并将指针p指向它；三、插

31、入运算 插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点，并令q指针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化ai-1aixpqq = new LNode;q-data=x;q-next=p-next;p-next=q;定位ai-1并将指针p指向它；三、插入运算 插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点，并令q指针指向该新结

32、点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化ai-1aixpqq = new LNode;q-data=x;q-next=p-next;p-next=q;p=getnode(head，i-1);功能：在头指针为head的链表中定位第i-1个结点,并返回结点位置。三、插入运算 void insertnode(head， x， i) LNode * p，*q; p=getnode(head，i-1); if(p=NULL) cout“position error”data=x; qnext=pnext; pnext=q; LNode * getnode(

33、head ，i) p=head; j=0; /计数用 while(pnext & jnext; j+; if (i=j) return p;else return NULL;四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：ai-1aiai+1四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的

34、存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：ai-1aiai+1四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：ai-1aiai+1四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结

35、点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：ai-1aiai+1pp-next=p-next-next;四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：ai-1aiai+1pp-next=p-next-next;问题：链表的逻辑结构已正确了，但结点ai空间丢了。四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域ne

36、xt中，所以必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：ai-1aiai+1pp-next=p-next-next;r=p-next;p-next=r-next;delete r;四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：ai-1aiai+1pp-next=p-next-next;r=p-next;p

37、-next=r-next;delete r;r四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：ai-1aiai+1pp-next=p-next-next;r=p-next;p-next=r-next;delete r;r四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令pn

38、ext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：ai-1aiai+1pp-next=p-next-next;p=getnode(head，i-1);r=p-next;p-next=r-next;delete r;r四、删除运算void deletelist(head， i) LNode *p， *r; p=getnode(head，i-1); if(p= =NULL | pnext= =NULL) return ERROR; r=pnext; pnext=rnext; delete r; 从上面的讨论可以看出，链表上实现插入和删除运算，无须移动结点，仅需修改

39、指针。作业： （1） 链表是有序的，现在插入数据x，要求插入后仍然有序 （2）链表是有序的，现在删除数据x，若x不存在，输出一段提示信息。 要求：按链表有头结点和无头结点两种情况分别写出并上机调试通过。五、静态链1、静态链表的概念 用一维数组来实现线性链表，这种用一维数组表示的线性链表，称为静态链表。静态：体现在表的容量是一定的。（数组的大小）链表：插入与删除同前面所述的动态链表方法相同2、静态链表的类型定义#define MAXSIZE 1000 / 链表的最大长度struct Component ElemType data; int cur; ; Component VListMAXSIZ

40、E;SLinkList类型的数组变量是结构数组，每一数组分量包括两个域：data：用于存储线性表元素；cur： 用于存储直接后继元素在数组中的位置静态链表图示0h=5数组下标静态链表与线性链表的区别？线性链表图示地址a18a22a4-1a30123456789101010a11026a21014a40a310101012101410221024102610281030102010181016h=1020例：静态链表的操作 设插入和删除只在表的头上进行（栈）h=7（5，7，2，3）（8，5，7，2，3）h=0表中加入x01234793-15123567891001234793-151235678

41、9102.(1)VListi.data=x;1.在VList中找空位置 i(比如0)(2)VListi.cur=h; x7 (3)h=i; 空位置的标识：将所有空位置构成链表，用av表示链首012342793-11058451-12365678910av=02.(1)Vlisti.data=x;1.在VList中找空位置 i(2)Vlisti.cur=h; (3)h=i; if(av= -1) 无空间处理elsei=av;av=VListi.curVListi.data=x; VListi.cur=h; h=i;删除：if(h!=-1) x=VListh.data;i=h;h=VListi.c

42、ur; VListi.cur=av; av=i; h=7空表初始化：开始，表是空的，所以：for(i=0;inextnext和rear，显然，查找时间都是O(1)。因此，实际中也常采用尾指针表示单循环链表.。 a1anrear 由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或pnext是否为空，而是判断它们是否等于某一指定指针，如头指针或尾指针等。2.3.3 双向链表 双向链表(Double linked list):在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为：str

43、uct DuLNode datatype data; DuLNode *prior，*next; ;结点存储前趋结点 的地址存储数据元素存储后继结点 的地址指针域数据域指针域 双链表一般由头指针唯一确定的，将头结点和尾结点链接起来构成循环链表，并称之为双向链表。 设指针p指向某一结点，则双向链表结构的对称性可用下式描述： ppriornext=p=pnextprior L（c）非空的双向循环链表 (b)空的双向循环链表Lpabc双向链表结点p前的插入数据x的操作：pqxai-1aiq= new DuLNode;q-data=x;q-prior=p-prior;q-next=p;p-prior-

44、next=q;p-prior=q;双向链表结点p前的插入数据x的操作：pqxq= new DuLNode;q-data=x;q-prior=p-prior;q-next=p;p-prior-next=q;p-prior=q;ai-1ai双向链表结点p前的插入数据x的操作：pqxai-1aiq= new DuLNode;q-data=x;q-prior=p-prior;q-next=p;p-prior-next=q;p-prior=q;ai+1aippriornext=pnext;pnextprior=pprior; delete p;p删除p指针所指的结点：ai-1ai+1aippriorne

45、xt=pnext;pnextprior=pprior; delete p;p删除p指针所指的结点：ai-1ai+1aippriornext=pnext;pnextprior=pprior; delete p;p删除p指针所指的结点：ai-1 双向链表的插入、删除灵活；链表维护的工作量大，所需的存储空间较大。24 一元多项式的表示及相加P n (x) = pn xn + pn-1 xn-1 + p1 x + p0 Q m (x) = qm xm + qm-1 xm-1+ q1x + q0一、一元多项式的表示 多项式的操作是表处理的典型用例。数学上,一元多项式可按降幂写成：（指数为正整数的情况）其

46、中：pn 、qm不为0 存储结构：用线性链表表示。增加头结点，每个结点有coef:系数 exp指数 next：指针其中，头结点的exp为-1。coefexpnext多项式 A (x) = 5 x 17 + 9 x 8 + 3x +7ha517983170-1例：求两多项式的和多项式 A (x) = 5 x 17 + 9 x 8 +3x+7 B (x) = 9 x 8 +22 x 7 +8 x二、一元多项式的相加算法一元多项式相加运算规则：指数相同的项系数相加A (x) B (x)相加的和多项式为 C (x) = A (x) + B (x) = 5 x 17+ 22 x 7 + 11x +7 设

47、多项式A (x) ，B (x)分别用带表头结点的线性链表pa,pb表示,完成:ha=ha+hb一元多项式加法算法主要步骤 分别对两个链表ha 、hb进行扫描，设 工作指针pa 、 pb分别指向两个多项式当前进行比较的结点，q指针指向pa的前驱，初始： q=ha; pa=ha-next; pb=hb-next;若pa,pb都不为空：则比较两者指数： pa-exp pb-exp： q,pa后移；pa-exp = pb-exp：将pb所指结点的系数“加”到pa所指结点 的系数上；若和为0，则pa所指结点删除。 q , pa, pb调整pa-exp exp ： 从表hb中复制pb所指结点的coef,e

48、xp，并将其插入到 ha表pa所指结点之前；若pb不空：hb表中从pb开始的结点插入到ha表尾上int comp(int a,int b) if(ab) return -1; if(a=b) return 0; else return 1; PloyAdd(ha,hb) q=ha;pa=ha-next; pb=hb-next; while(pa!=NULL & pb!=NULL) switch(comp(pa-exp,pb-exp) -1: q=pa; pa=pa-next;break; 0: pa-coef+=pb-coef; if(pa-coef=0) q-next=pa-next; de

49、lete pa; pa=q; else q=pa; pa=pa-next; pb=pb-next; break; 1: r=new Node;r-coef=pb-coef;r-exp=pb-exp;q-next=r;r-next=pa;q=r;pb=pb-next;break; while(pb!=NULL) r=new Node; r-coef=pb-coef; r-exp=pb-exp; q-next=r; r-next=pa; q=r; pb=pb-next; while改成：while(pb!=hb)在改成循环链后，此while可省去。1、线性表v的数据递增有序，试将x插入表中并保持有

50、序性（1）表顺序表示（2）链表表示（3）带有头结点的链表2、写一个线性表的转置算法（顺序和链表表示两种情况） （a1,a2,.,an)变为（an,an-1,.,a1)实习题目： hc=ha*hb第三章 栈和队列3.1 栈 3.1.1 栈的定义 3.1.2 栈的表示和实现3.2 栈的应用举例 3.1 栈3.1.1 栈的定义及基本运算 栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。 假设栈S=(a1，a2，a3，an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，an

51、的次序进栈，退栈的第一个元素应为栈顶元素。因此，栈的修改是按后进先出的原则进行的，所以，栈称为后进先出（先进后出）表（LIFO，FILO）。3.1.2 顺序存储栈 栈是线性表的特例，因此线性表的存储结构对栈也适应。 栈的顺序存储结构简称为顺序栈，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top（栈顶指针）来指出栈顶。栈顶 栈底例、一叠盘子、弹夹等。 anan-1.a2a1入出-1 空栈top016 为指示当前栈顶的位置，需top为栈顶指针（ MAXSIZE代表栈容量）。初始化:x进栈

52、：退栈：top=-1;if(top= =MAXSIZE-1 上溢处理； else top+; stacktop=x;if(top=-1) 下溢处理； else y=stacktop; top-;3.1.3 链栈 栈的链式存储结构称为链栈，插入和删除操作仅限制在链头位置上进行。栈顶指针就是链表的头指针。 初始化：top=NULLX进栈：p= new StackNode;p-data=x; p-next=top;top=p;退栈:if(top = = NULL) 下溢处理；else y= top-data; p=top;top=p-next;delete p; top3.2 栈的应用举例 由于栈结

53、构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。 3.2.1 数制转换 十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理: N=(n / d)*d+n % d例如 (1348)10=(2504)8，其运算过程如下： n n /8 n % 8 1348 168 4 168 21 0 21 2 5 2 0 2 void conversion( ) initstack(s); cinn; while(n) push(s,n%8); n=n/8; while(! Stackempty(s) pop(s,e);cout

54、next=NULL;x进队：r=new Node; r-data=x; r-next=NULL; rear-next=r;rear=r;退队：if(front = rear) 队空处理；else p=front-next;y=p-data;front-next=p-next;delete p; if(front-next= =NULL) rear=front;fr习题1、链栈中为何不设头指针？2、循环队列的优点是什么？如何判断它的空和满？3、设长度为n的链队列用单循环链表表示，若只设头指针，则怎样进行入队和出队操作；若只设尾指针呢？4、利用栈的基本操作，写一个返回栈s中结点个数的算法int s

55、tacksize(seqstack s)，并说明s为何不用作为指针参数？5、利用栈的基本操作，写一个将栈中所有结点均删除算法，并说明S为何要作为指针参数？6、用第二种方法，即少用一个元素空间的方法来区别循环队列的队空和队满，试设计置空队、判队空、判队满、出队、入队及取队头元素等六个基本操作。 第四章 串4.1 串类型的定义4.2 串的表示和实现 4.2.1 定长顺序存储表示 4.2.2 堆分配存储表示 4.2.3 串的块链存储表示4.1 串类型的定义一、串和基本概念 串(String)是零个或多个字符组成的有限序列。一般记作S=“a1a2a3an”，其中S是串名，双引号括起来的字符序列是串值；

56、ai(1in)可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。长度为零的串称为空串(Empty String)，它不包含任何字符。 通常将仅由一个或多个空格组成的串称为空白串(Blank String) 注意：空串和空白串的不同，例如“ ”和“”分别表示长度为1的空白串和长度为0的空串。 串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。通常将子串在主串中首次出现时的该子串的首字符在主串中的位置，定义为子串在主串中的序号（或位置）。例如，设A和B分别为 A=“This is a string” B=“is”则B是A的子串，A为主串。B在A中出现了两次，其

57、中首次出现所对应的主串位置是3。因此，称B在A中的序号（或位置）为3 特别地，空串是任意串的子串，串总是其自身的子串。 通常在程序中使用的串可分为两种：串变量和串常量。串常量和整常数、实常数一样，在程序中只能被引用但不能改变其值，即只能读不能写。通常串常量是由直接量来表示的，例如语句cout“overflow”中“overflow”是直接量。但有的语言允许对串常量命名，以使程序易读、易写。如C+中，可定义 const char path=“dir/bin/appl”;这里path是一个串常量，对它只能读不能写。串变量和其它类型的变量一样，其取值是可以改变的。二、串的基本操作 对于串的基本操作，

58、许多高级语言均提供了相应的运算或标准库函数来实现。C/C+语言中常用的串运算如下： 定义下列几个变量： char s120=“dirtreeformat”,s220=“test.cpp”; char s330,*p; int result;（1）求串长(length) int strlen(char *s); /求串的长度（2）串复制(copy) char *strcpy(char *to,char *from); 该函数将串from复制到串to中，并且返回一个指向串to的开始处的指针。 例如：strcpy(s3,s1); /s3=“dirtreeformat”(3)联接(concatenat

59、ion) char strcat(char *to,char *from) 该函数将串from复制到串to的末尾，并且返回一个指向串to的开始处的指针。 例如：strcat(s3,”/”) strcat(s3,s2); /s3=“dirtreeformat/test.cpp”例1、求子串 求子串的过程即为复制字符序列的过程，将串s中的第pos个字符开始的连续的len个字符复制到串sub中。 void substr(string sub,string s,int pos,int len) if(posstrlen(s)-1 | len0) n=strlen(s); m=strlen(t); i=

60、pos; while(in-m+1) substr(sub,s,i,m); if(strcmp(sub,t)!=0) +i; else return i; return 0; 4.2 串的表示和实现 因为串是特殊的线性表，故其存储结构与线性表的存储结构类似。只不过由于组成串的结点是单个字符。串有三种表示方法。4.2.1定长顺序存储表示 定长顺序存储表示,也称为静态存储分配的顺序表。用一组连续的存储单元来存放串中的字符序列。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先给出： #define MAXSTRLEN 256 typedef char sstringMAXSTRL