数据结构的基本概念课件

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

1.1什么是数据结构

众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。那么，什么是数据结构呢？先看以下几个例子。例1、电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1，b1)(a2，b2)…(an，bn)其中ai，bi(i=1，2…n)分别表示某人的名字和对应的电话号码要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。1.1什么是数据结构4算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。数据的结构，直接影响算法的选择和效率。上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。假定名字和其电话号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(ai，bi)，1≤i≤n数据结构还要提供每种结构类型所定义的各种运算的算法。算法的设计，依赖于计算机如何存储人的名字和对5例2、图书馆的书目检索系统自动化问题例3、教师资料档案管理系统例4、多叉路口交通灯的管理问题P3通过以上几例可以直接地认为：数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。例2、图书馆的书目检索系统自动化问题61.2基本概念和术语数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(DataElement):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。1.2基本概念和术语7数据结构主要指逻辑结构和物理结构数据之间的相互关系称为逻辑结构。通常分为四类基本结构：一、集合结构中的数据元素除了同属于一种类型外，别无其它关系。二、线性结构结构中的数据元素之间存在一对一的关系。三、树型结构结构中的数据元素之间存在一对多的关系。四、图状结构或网状结构结构中的数据元素之间存在多对多的关系。

数据结构主要指逻辑结构和物理结构8数据结构的形式定义为：数据结构是一个二元组：Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集。例复数的数据结构定义如下：Complex=(C，R)其中：C是含两个实数的集合﹛C1，C2﹜，分别表示复数的实部和虚部。R={P}，P是定义在集合上的一种关系{〈C1，C2〉}。数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。数据结构的形式定义为：数据结构是一个二元组：9

数据对象可以是有限的，也可以是无限的。数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。抽象数据类型：一个数学模型以及定义在该模型上的一组操作。抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。用三元组描述如下：（Ｄ，Ｓ，Ｐ）数据对象可以是有限的，也可以是无限的。10数据结构在计算机中有两种不同的表示方法：顺序表示和非顺序表示由此得出两种不同的存储结构：顺序存储结构和链式存储结构顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储结构：在每一个数据元素中增加一个存放地址的指针（），用此指针来表示数据元素之间的逻辑关系。数据结构在计算机中有两种不同的表示方法：11数据类型：在一种程序设计语言中，变量所具有的数据种类。例1、在FORTRAN语言中，变量的数据类型有整型、实型、和复数型例2、在C语言中数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义数据对象：某种数据类型元素的集合。例3、整数的数据对象是{…-3，-2，-1，0，1，2，3，…}英文字符类型的数据对象是{A，B，C，D，E，F，…}数据类型：在一种程序设计语言中，变量所具有的数据种类。121.3抽象数据类型的表示和实现P111.3抽象数据类型的表示和实现13

1.4算法和算法分析算法：是对特定问题求解步骤的一种描述算法是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有以下五个特性：（1）有穷性一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。（2）确定性算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。（3）可行性一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。1.4算法和算法分析144）输入一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。5）输出一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。1.4.2算法设计的要求评价一个好的算法有以下几个标准:(1)正确性(Correctness)算法应满足具体问题的需求。(2)可读性(Readability)算法应该好读。以有利于阅读者对程序的理解。(3)健状性(Robustness)算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。4）输入一个算法有零个或多个输入，这些输入取自于某个特定15(4)效率与存储量需求效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。1.4.3算法效率的度量

对一个算法要作出全面的分析可分成两用人才个阶段进行，即事先分析和事后测试事先分析求出该算法的一个时间界限函数事后测试收集此算法的执行时间和实际占用空间的统计资料。定义：如果存在两个正常数c和n0，对于所有的n≧n0，有︱f(n)︳≦c｜g(n)︳则记作f(n)=O(g(n))(4)效率与存储量需求效率指的是算法执行的时间；存储量16一般情况下，算法中基本操作重复执行的次数是问题规模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];}一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函17由于是一个三重循环，每个循环从1到n，则总次数为:n×n×n=n3时间复杂度为T(n)=O(n3)频度：是指该语句重复执行的次数例２{++x;s=0;}将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1)如果将s=0也看成是基本操作，则语句频度为２，其时间复杂度仍为Ｏ(1)，即常量阶。例３、for(I=1;I<=n;++I){++x;s+=x;}语句频度为：2n其时间复杂度为：O(n)即时间复杂度为线性阶。由于是一个三重循环，每个循环从1到n，则总次数为:n×n×18例４、for(I=1;I<=n;++I)for(j=1;j<=n;++j){++x;s+=x;}语句频度为：2n2其时间复杂度为：O(n2)即时间复杂度为平方阶。定理：若A(n)=amnm+am-1nm-1+…+a1n+a0是一个m次多项式，则A(n)=O(nm)证略。例５for(i=2;i<=n;++I)for(j=2;j<=i-1;++j){++x;a[i，j]=x;}例４、for(I=1;I<=n;++I)19语句频度为：1+2+3+…+n-2=(1+n-2)×(n-2)/2=(n-1)(n-2)/2=n2-3n+2∴时间复杂度为O(n2)即此算法的时间复杂度为平方阶.一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。

语句频度为：20以下六种计算算法时间的多项式是最常用的。其关系为：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)指数时间的关系为：O(2n)<O(n!)<O(nn)当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。以下六种计算算法时间的多项式是最常用的。其关系为：21有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例如：Voidbubble-sort(inta[]，intn)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次

有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集22最坏情况：1+2+3+…+n-1=n(n-1)/2平均时间复杂度为:O(n2)1.4.4算法的存储空间需求空间复杂度:算法所需存储空间的度量，记作:S(n)=O(f(n))其中n为问题的规模(或大小)最坏情况：1+2+3+…+n-123

第二章线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.3.1线性链表2.3.2循环链表2.3.3双向链表2.4一元多项式的表示及相加

第二章线性表2.1242.1线性表的逻辑结构线性表(LinearList)：由n(n≧)个数据元素(结点)a1，a2，…an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n>0)记作：(a1，a2，…an)这里的数据元素ai(1≦i≦n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。例1、26个英文字母组成的字母表（A，B，C、…、Z）例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）2.1线性表的逻辑结构25例3、学生健康情况登记表如下：姓名学号性别年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790634男17神经衰弱……..……..…….…….…….例3、学生健康情况登记表如下：姓名学号性26例4、一副扑克的点数（2，3，4，…，J，Q，K，A）从以上例子可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内部结点ai(2≦i≦n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。抽象数据类型的定义为：P19例4、一副扑克的点数27

算法2.1例2-1利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B。voidunion(List&La，ListLb){La-len=listlength(La);Lb-len=listlength(Lb);for(I=1;I<=lb-len;I++){getelem(lb，I，e);if(!locateelem(la，e，equal))listinsert(la，++la-en，e)}}

算法2.128算法2.2例2-2巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。此问题的算法如下：

算法2.229voidmergelist(listla，listlb，list&lc)initlist(lc);I=j=1;k=0;la-len=listlength(la);lb-len=listlength(lb);while((I<=la-len)&&(j<=lb-len)){voidmergelist(listla，listl30getelem(la，I，ai);getelem(lb，j，bj);if(ai<=bj){listinsert(lc，++k，ai);++I;}else{listinsert(lc，++k，bj);++j;}}while(I<=la-len){getelem((la，I++，ai);listinsert(lc，++k，ai);}while(j<=lb-len){getelem((lb，j++，bj);listinsert(lc，++k，bi);}}getelem(la，I，ai);getelem(lb，312.2线性表的顺序存储结构2.2.1线性表把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第I+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(aI)之间满足下列关系：LOC(ai+1)=LOC(ai)+l线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(I-1)*l

2.2线性表的顺序存储结构32由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。#defineListSize100typedefintDataType;typedefstruc{DataTypedata[ListSize];intlength;}Sqlist;由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型332.2.2顺序表上实现的基本操作在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素是l.data[I-1]。以下主要讨论线性表的插入和删除两种运算。1、插入线性表的插入运算是指在表的第I(1≦i≦n+1个位置上，插入一个新结点x，2.2.2顺序表上实现的基本操作34使长度为n的线性表(a1，…ai-1，ai，…，an)变成长度为n+1的线性表(a1，…ai-1，x，ai，…，an)

算法2.3VoidInsertList(Sqlist*L，DataTypex，intI){intj;if(I<1||I>l.length+1)printf(“Positionerror”);returnERROR

使长度为n的线性表35if(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++;}if(l.length>=ListSize)36现在分析算法的复杂度。这里的问题规模是表的长度，设它的值为。该算法的时间主要化费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）是。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。当时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度O（1）；当=1时，结点后移语句将循环执行n次，需移动表中所有结点，这是最坏情况，现在分析算法的复杂度。37其时间复杂度为O（n）。由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度在长度为n的线性表中第i个位置上插入一个结点，令Eis(n)表示移动结点的期望值（即移动的平均次数），则在第i个位置上插入一个结点的移动次数为n-I+1。故Eis(n)=pi(n-I+1)不失一般性，假设在表中任何位置(1≦i≦n+1)上插入结点的机会是均等的，则p1=p2=p3=…=pn+1=1/(n+1)因此，在等概率插入的情况下，Eis(n)=(n-I+1)/(n+1)=n/2

其时间复杂度为O（n）。38也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长n较大时，算法的效率相当低。虽然Eis(n)中n的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为O(n)。2、删除线性表的删除运算是指将表的第i(1≦i≦n)结点删除，使长度为n的线性表：(a1，…ai-1，ai，ai+1…，an)变成长度为n-1的线性表(a1，…ai-1，ai+1，…，an)也就是说，在顺序表上做插入运算，平均要移动表上一半结点39VoiddeleteList(Sqlist*L，intI){intj;if(I<1||I>l.length)printf(“Positionerror”);returnERRORfor(j=i;j<=l.length-1;j++)l.data[j-1]=l.data[j];l.length--;}

VoiddeleteList(Sqlist*L，in40该算法的时间分析与插入算法相似，结点的移动次数也是由表长n和位置i决定。若I=n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动结点；若I=1，则前移语句将循环执行n-1次，需移动表中除开始结点外的所有结点。这两种情况下算法的时间复杂度分别为O(1)和O(n)。删除算法的平均性能分析与插入算法相似。在长度为n的线性表中删除一个结点，令Ede(n)表示所需移动结点的平均次数，删除表中第i个结点的移动次数为n-i，故Ede(n)=pi(n-I)式中，pi表示删除表中第i个结点的概率。在等该算法的时间分析与插入算法相似，结点的移动次数也是由表长n和41概率的假设下，p1=p2=p3=…=pn=1/n由此可得：Ede(n)=(n-I)/n=(n-1)/2即在顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是O(n)。

2.3线性表的链式表示和实现线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，但它也使得概率的假设下，42插入和删除操作会移动大量的结点.为避免大量结点的移动，我们介绍线性表的另一种存储方式，链式存储结构，简称为链表(LinkedList)。2.3.1线性链表链表是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构：插入和删除操作会移动大量的结点.为避免大量结点的移动，我们介43

其中：data域是数据域，用来存放结点的值。next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起的。由于上述链表的每一个结只有一个链域，故将这种链表称为单链表（SingleLinked)。显然，单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。同时，由于终端结点无后继，故终端结点的指针域为空，即null（图示中也可用^表示)。例1、线性表:(bat，cat，eat，fat，hat，jat，lat，mat)datalink

44的单链表示意图如下：……110……130135……160头指针head165170……200205…………………hat200…….……cat135eat170….……matNullbat130fat110…………jat205lat160…………165的单链表示意图如下：45headbatcateatmat^…单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。例如：若头指针名是head，则把链表称为表head。用C语言描述的单链表如下：Typedefchardatatype;

Typedefstructnode{datatypedata;structnode*next;}listnode;headbatcateatma46typedeflistnode*linklist;listnode*p;linklisthead;注意区分指针变量和结点变量这两个不同的概念。P为动态变量，它是通过标准函数生成的，即p=(listnode*)malloc(sizeof(listnode));函数malloc分配了一个类型为listnode的结点变量的空间，并将其首地址放入指针变量p中。一旦p所指的结点变量不再需要了，又可通过标准函数free(p)释放所指的结点变量空间。typedeflistnode*link47指针变量P和（其值为结点地址）和结点变量*P之间的关系。指针变量P和（其值为结点地址）和结点变量*P之间的关系。48一、建立单链表假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并以换行符‘\n’为输入结束标记。动态地建立单链表的常用方法有如下两种：1、头插法建表该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。一、建立单链表49linklistcreatelistf(void){charch;linklisthead;listnode*p;head=null;ch=getchar();while(ch!=‵\n′{p=(listnode*)malloc(sizeof(listnode));p–>data=ch;p–>next=head;linklistcreatelistf(void)50head=p;ch=getchar();}return(head);}head=p;51listlinkcreatelist(intn){intdata;linklisthead;listnode*phead=null;for(i=n;i>0;--i){p=(listnode*)malloc(sizeof(listnode));scanf((〝%d〞，&p–>data);p–>next=head;head=p;}listlinkcreatelist(int52return(head);}2、尾插法建表

头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。例：return(head);53linklistcreater(){charch;linklisthead;listnode*p，*r;//(，*head;)head=NULL;r=NULL;while((ch=getchar()!=‵\n′){p=(listnode*)malloc(sizeof(listnode));p–>data=ch;if(head=NULL)head=p;else

linklistcreater()54r–>next=p;r=p;}if(r!=NULL)r–>next=NULL;return(head);}说明：第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的，原因是开始结点的位置是存放在头指针（指针变量）中，

r–>next=p;55而其余结点的位置是在其前趋结点的指针域中。算法中的第一个if语句就是用来对第一个位置上的插入操作做特殊处理。算法中的第二个if语句的作用是为了分别处理空表和非空表两种不同的情况，若读入的第一个字符就是结束标志符，则链表head是空表，尾指针r亦为空，结点*r不存在；否则链表head非空，最后一个尾结点*r是终端结点，应将其指针域置空。如果我们在链表的开始结点之前附加一个结点，并称它为头结点，那么会带来以下两个优点：a、由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就而其余结点的位置是在其前趋结点的指针域中。算法中的第56和在表的其它位置上的操作一致，无需进行特殊处理；b、无论链表是否为空，其头指针是指向头结点在的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。其算法如下：linklistcreatelistr1(){charch;linklisthead=(linklist)malloc(sizeof(listnode));listnode*p，*r

和在表的其它位置上的操作一致，无需进行特殊处理；57r=head;while((ch=getchar())!=‵\n′{p=(listnode*)malloc(sizeof(listnode));p–>data=ch;p–>next=p;r=p;}r–>next=NULL;return(head);}r=head;58上述算法里动态申请新结点空间时未加错误处理，可作下列处理：p=(listnode*)malloc(sizeof(listnode))if(p==NULL)error(〝Nospacefornodecanbeobtained〞);returnERROR;

以上算法的时间复杂度均为O(n)。上述算法里动态申请新结点空间时未加错误处理，可作下列处理：59二、查找运算

1、按序号查找在链表中，即使知道被访问结点的序号i，也不能象顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。设单链表的长度为n，要查找表中第i个结点，仅当1≦i≦n时，i的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是第0个结点，其算法如下：二、查找运算60Listnode*getnode(linklisthead，inti){intj;listnode*p;p=head;j=0;while(p–>next&&j<I){p=p–>next;j++;}if(i==j)returnp;Listnode*getnode(linklisthe61

elsereturnNULL;}

2、按值查找按值查找是在链表中，查找是否有结点值等于给定值key的结点，若有的话，则返回首次找到的其值为key的结点的存储位置；否则返回NULL。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值key作比较。其算法如下：else62Listnode*locatenode(linklisthead，intkey){listnode*p=head–>next;while(p&&p–>data!=key)p=p–>next;returnp;}

该算法的执行时间亦与输入实例中的的取值key有关，其平均时间复杂度的分析类似于按序号查找，也为O(n)。Listnode*locatenode(linklist63三、插入运算插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，我们必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点*p，并令结点*p的指针域指向新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化，插入过程如：三、插入运算64具体算法如下：voidinsertnode(linklisthead，datetypex，inti){listnode*p，*q;p=getnode(head，i-1);if(p==NULL)error(〝positionerror〞);q=(listnode*)malloc(sizeof(listnode));q–>data=x;q–>next=p–next;p–>next=q;}具体算法如下：65设链表的长度为n，合法的插入位置是1≦i≦n+1。注意当i=1时，getnode找到的是头结点，当i=n+1时，getnode找到的是结点an。因此，用i-1做实参调用getnode时可完成插入位置的合法性检查。算法的时间主要耗费在查找操作getnode上，故时间复杂度亦为O(n)。四、删除运算删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点aai-1的指针域next中，所以我们必须首先找到

设链表的长度为n，合法的插入位置是1≦i≦n+1。注意当66ai-1的存储位置p。然后令p–>next指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间，将其归还给“存储池”。此过程为：ai-1的存储位置p。然后令p–>next指向ai67具体算法如下：voiddeletelist(linklisthead，inti){listnode*p，*r;p=getnode(head，i-1);if(p==NULL||p–>next==NULL)returnERROR;r=p–>next;p–>next=r–>next;free(r);}具体算法如下：68

设单链表的长度为n，则删去第i个结点仅当1≦i≦n时是合法的。注意，当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点的直接前趋*p存在并不意味着被删结点就一定存在，仅当*p存在（即p!=NULL）且*p不是终端结点（即p–>next!=NULL）时，才能确定被删结点存在。显然此算法的时间复杂度也是O(n)。从上面的讨论可以看出，链表上实现插入和删除运算，无须移动结点，仅需修改指针。设单链表的长度为n，则删去第i个结点仅当1≦i≦n时是692.3.2循环链表

循环链表时一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。单循环链表：在单链表中，将终端结点的指针域NULL改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如下图所示：2.3.2循环链表70

a1an

….head⑴非空表⑵空表在用头指针表示的单链表中，找开始结点a1的时间是O(1)，然而要找到终端结点an，则需从头指针开始遍历整个链表，其时间是O(n)a1an….head⑴非空表⑵空表在71在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头指针表示的单循环链表就显得不够方便.如果改用尾指针rear来表示单循环链表，则查找开始结点a1和终端结点an都很方便，它们的存储位置分别是(rear–>next)—>next和rear，显然，查找时间都是O(1)。因此，实际中多采用尾指针表示单循环链表。由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p—>next是否为空，而是判断它们是否等于某一指定指针，如头指什或尾指针等。在很多实际问题中，表的操作常常是在表的72例、在链表上实现将两个线性表(a1，a2，a3，…an)和(b1，b2，b3，…bn)链接成一个线性表的运算。linklistconnect(linklistheada，linklistheadb){linklistp=heada—>next;heada—>next=(headb—next)—>nextfree(headb—>next);headb—>next=p;return(headb);}例、在链表上实现将两个线性表(a1，a2，a3，…an)和(732.3.3双链表双向链表(Doublelinkedlist):在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为：

typedefstructdlistnode{datatypedata;strucdlistnode*prior，*next;}dlistnode;typedefdlistnode*dlinklist;dlinklisthead;2.3.3双链表74和单链表类似，双链表一般也是由头指针唯一确定的，增加头指针也能使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向链表。设指针p指向某一结点，则双向链表结构的对称性可用下式描述：(p—>prior)—>next=p=(p—>next)—>prior即结点*p的存储位置既存放在其前趋结点*(p—>prior)的直接后继指针域中，也存放在它的后继结点*(p—>next)的直接前趋指针域中。和单链表类似，双链表一般也是由头指针唯一75双向链表的前插操作算法如下：voiddinsertbefor(dlistnode*p，datatypex){dlistnode*q=malloc(sizeof(dlistnode));q—>data=x;q—>prior=p—>prior;q—>next=p;p—>prior—>next=q;p—>prior=q;}双向链表的前插操作算法如下：76voidddeletenode(dlistnode*p){p–>prior–>next=p–>next;p–>next–>prior=p–>prior;free(p);}

注意：与单链表的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算是法的时间复杂度均为O(1)。voidddeletenode(dlistnode77

第三章栈和队列3.1栈3.1.1抽象数据类型栈的定义3.1.2栈的表示和实现3.2栈的应用举例3.2.1数制转换3.2.2括号匹配的检验3.2.4行编辑程序3.2.5迷宫求解3.2.5表达式求值第三章栈和队列3.1栈78

3.1.1栈3.1.1栈的定义及基本运算栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。

793.1.2顺序栈由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top数据结构的基本概念80例、一叠书或一叠盘子。

栈的抽象数据类型的定义如下：P44

anan-1a2a1……栈顶栈底例、一叠书或一叠盘子。an81top7654321-1top7654321-182来指示当前栈顶的位置，通常称top为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可。顺序栈的类型定义如下：#defineStackSize100typedefchardatatype;typedefstruct{datatypedata[stacksize];inttop;}seqstack;来指示当前栈顶的位置，通常称top为栈顶指针。因此，顺序栈的83设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即s–>data[0]是栈底元素，那么栈顶指针s–>top是正向增加的，即进栈时需将s–>top加1，退栈时需将s–>top减1。因此，s–>top<0表示空栈，s–>top=stacksize-1表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称“上溢”;当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。设S是SeqStack类型的指针变量。若栈底位置843、判断栈满intstackfull(seqstack*s){return(s–>top==stacksize-1);}4、进栈voidpush(seqstack*s，datatypex){if(stackfull(s))error(“stackoverflow”);s–>data[++s–>top]=x;}3、判断栈满851、置空栈voidinitstack(seqstack*s){s–>top=-1;}2、判断栈空intstackempty(seqstack*s){return(s–>top==-1);}1、置空栈865、退栈datatypepop(seqstack*s){if(stackempty(s))error(“stackunderflow”);x=s–>data[top];s–>top--;return(x)//return(s–>data[s–>top--]);}

5、退栈876、取栈顶元素Datatypestacktop(seqstack*s){if(stackempty(s)error(“stackisenpty”);returns–>data[s–>top];}

6、取栈顶元素883.1.3链栈栈的链式存储结构称为链栈，它是运算是受限的单链表，克插入和删除操作仅限制在表头位置上进行.由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。链栈的类型说明如下：typedefstructstacknode{datatypedatastructstacknode*next}stacknode;3.1.3链栈89Voidinitstack(seqstack*p){p–>top=null;}intstackempty(linkstack*p){returnp–>top==null;}

Voidinitstack(seqstack*p)90Voidpush(linkstack*p,datatypex){stacknode*qq=(stacknode*)malloc(sizeof(stacknode));q–>data=x;q–>next=p–>top;p–>top=p;}Voidpush(linkstack*p,datatyp91Datatypepop(linkstack*p){datatypex;stacknode*q=p–>top;if(stackempty(p)error(“stackunderflow.”);x=q–>data;p–>top=q–>next;free(q);returnx;}Datatypepop(linkstack*p)92datatypestacktop(linkstack*p){if(stackempty(p))error(“stackisempty.”);returnp–>top–>data;}datatypestacktop(linksta93

3.2栈的应用举例由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。

3.2.1数制转换

十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:N=(ndivd)*d+nmodd(其中:div为整除运算,mod为求余运算)例如(1348)10=(2504)8，其运算过程如下：3.2栈的应用举例94nndiv8nmod8134816841682102125202nndiv895voidconversion(){initstack(s);scanf(“%”,n);while(n){push(s,n%8);n=n/8;}while(!Stackempty(s)){pop(s,e);printf(“%d”,e);}}voidconversion(){963.2.2括号匹配的检验

假设表达式中充许括号嵌套,则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例：（（）（）（（）））3.2.3行编辑程序

在编辑程序中，设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。

3.2.2括号匹配的检验97行编辑程序算法如下:voidlineedit(){initstack(s);ch=gether();while(ch!=eof){while(ch!=eof&&ch!=‘\n’){

switch(ch){case‘#’:pop(s,c);case‘@’:clearstack(s);default:push(s,ch);}行编辑程序算法如下:98ch=getchar();}clearstack(s);if(ch!=eof)ch=gethar();}destroystack(s);}ch=getchar();993.2.4迷宫求解

入口出口3.2.4迷宫求解出口1003.4队列3.4.1抽象数据类型队列的定义队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(FirstInFirstOut)的线性表，简称FIFO表。当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,…an，也就是说队列的修改是依先进先出的原则进行的。3.4队列101下图是队列的示意图：

a1a2…an

出队入队队头队尾队列的抽象数据定义见书Ｐ593.4.2循环队列－队列的顺序表示和实现

队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个向量空间来存放当前队下图是队列的示意图：出队入队队头队尾队列的抽象数据定义见书Ｐ102列中的元素。由于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位置，它们的初始值地队列初始化时均应置为０。入队时将新元素插入所指的位置，然后将加１。出队时，删去所指的元素，然后将加１并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。０１２３0123

FrontrearabcFrontrear

(a)队列初始为空（b）A,B,C入队列中的元素。由于队列的队头和队尾的位置是变化的，因而要设两个103０１２３０１２３bc

frontrearfrontrear（c)a出队(d)b,c出队，队为空和栈类似，队列中亦有上溢和下溢现象。此外，顺序队列中还存在“假上溢”现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。０１２３０１２３bcf104为充分利用向量空间。克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（CircularQueue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为：if(I+1==QueueSize)i=0;elsei++;

利用模运算可简化为：i=(i+1)%QueueSize为充分利用向量空间。克服上述假上溢现象的方法是将向量空间想象105显然，因为循环队列元素的空间可以被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。如图所示：由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列“空”还是“满”。解决此问题的方法至少有三种：其一是另设一个布尔变量以匹别队列的空和满；其二是少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；显然，因为循环队列元素的空间可以被利106其三是使用一个计数器记录队列中元素的总数（实际上是队列长度）。下面我们用第三种方法实现循环队列上的六种基本操作，为此先给出循环队列的类型定义。#defineQueueSize100typedefcharDataType;typedefStruct{intfront;intrear;intcount;datatypedata[queuesize]}cirqueue;其三是使用一个计数器记录队列中元素的总数（实际上是队列长度）107（1）置空队voidinitqueue(cirqueue*q){q–>front=q–>rear=0;q–>count=0;}（2）判断队空i