1、 C C语言版语言版清华大学出版社 2009年9月第第 1 章章 概概 论论 o 什么是数据结构什么是数据结构o 为什么要学习数据结构为什么要学习数据结构o 算法和算法分析算法和算法分析1.1.1 数据和数据元素数据和数据元素数据（数据（data）是信息的载体，是对客观事物的符是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储和加工处理。号表示，它能够被计算机识别、存储和加工处理。1.1 什么是数据结构什么是数据结构 数据数据在计算机科学中指所有能输入到计算机中并被计在计算机科学中指所有能输入到计算机中并被计算机程序处理的符号的总称。如图像、数、字符、声音、算机程序处理的符号的总称
2、。如图像、数、字符、声音、视频等都可以通过编码而由计算机处理，因此它们也属于视频等都可以通过编码而由计算机处理，因此它们也属于数据的范畴。数据的范畴。是数据的基本单位。是数据的基本单位。通常在计算机程序通常在计算机程序中作为一个整体进行考虑和处理。中作为一个整体进行考虑和处理。数据数据元素也称为元素、结点或记录。一个数元素也称为元素、结点或记录。一个数据元素可以由若干个数据项（也称字段、据元素可以由若干个数据项（也称字段、域）组成，数据项是数据不可分割的最域）组成，数据项是数据不可分割的最小单位。小单位。数据元素数据元素（data element）：数据对象（数据对象（data object）
3、：）：是性质相同的数据元素的集合，它是性质相同的数据元素的集合，它是数据的一个子集。是数据的一个子集。例如，所有的例如，所有的“数数”构成了数据集合，而正整数集合构成了数据集合，而正整数集合N=1，2，3，是是“数数”的数据对象；所有的数据对象；所有的字符是数据，大写字母集合的字符是数据，大写字母集合C=A，B，Z是该数据的数据对象。是该数据的数据对象。1.1.2 数据对象和数据类型数据对象和数据类型 要注意的是：要注意的是：计算机中计算机中的正的正整数数据对象集合整数数据对象集合N1应该是上述应该是上述集合集合N的一个子集，的一个子集，N1=1，2，maxint，其中，其中maxint是是依
4、赖于所使用的计算机和语言的依赖于所使用的计算机和语言的最大整数。最大整数。数据类型数据类型（data type）是计算是计算机程序中的数据对象以及定义在机程序中的数据对象以及定义在这个数据对象集合上的一组操作这个数据对象集合上的一组操作的总称。的总称。可以看作是数据结构的实现。可以看作是数据结构的实现。例如，例如，C语言中的整数类型是区间语言中的整数类型是区间-maxint，maxint上的整数，在这上的整数，在这个集合上可以进行加、减、乘、整个集合上可以进行加、减、乘、整除、求余等操作。除、求余等操作。数据结构（数据结构（data structure）是指数据对象（集合）以及该数是指数据对象
5、（集合）以及该数据对象集合中的数据元素之间的相互据对象集合中的数据元素之间的相互关系的集合（即数据元素的关系的集合（即数据元素的组织形组织形式式）。）。一组数据元素和一组运算（关系）两个集合组成的集合一组数据元素和一组运算（关系）两个集合组成的集合1.1.3 1.1.3 数据结构数据结构根据数据元素之间关系的不同，数根据数据元素之间关系的不同，数据结构分为两大类：据结构分为两大类：线性结构线性结构 非线性结构非线性结构 集合集合：数据元素之间除了：数据元素之间除了“属于同一个集合属于同一个集合”的关系以外，别无其他关系。的关系以外，别无其他关系。线性结构线性结构：数据元素之间存在一对一的关系。
6、：数据元素之间存在一对一的关系。树型结构树型结构：数据元素之间存在一对多的关系。：数据元素之间存在一对多的关系。图状结构图状结构（或称网状结构）：数据元素之间存（或称网状结构）：数据元素之间存在多对多的关系。在多对多的关系。数据元素之间的数据元素之间的逻辑关系逻辑关系，也称为数据，也称为数据的逻辑结构。是数据元素之间的逻辑结构。是数据元素之间抽象化抽象化的相的相互关系。是用户所看到的数据结构，是面互关系。是用户所看到的数据结构，是面向问题的，它不考虑数据的存储。数据的向问题的，它不考虑数据的存储。数据的逻辑结构通常有下列逻辑结构通常有下列4类：类：数据元素之间的运算（关系）：数据元素之间的运算
7、（关系）：对对数据元素施加的操作，有时也直接称为数据元素施加的操作，有时也直接称为数据的运算或操作。数据的运算或操作。数据的数据的物理结构：物理结构：又称又称存储结构。存储结构。是数据的逻辑结构在计算机存储器内的是数据的逻辑结构在计算机存储器内的表示（又称映象）。它属于具体实现的表示（又称映象）。它属于具体实现的视图，是面向计算机的。视图，是面向计算机的。例例1.1 学生成绩表（表1.1）是一个数据结构。表1.1 学生成绩表(每行是一个数据元素)学号姓名计算机导论高等数学普通物理平均成绩04081101陈小洁8090858504081102马丽丽7568787404081103林春英82786
8、67504081104王澄娟9085938904081150张吉祥70887578 数据结构可以理解为：数据结构可以理解为：按某种逻辑关系组织起来的一批数据，应用计算机语言，按一定的存储表示方式把它们存储在计算机的存储器中存储在计算机的存储器中，并在这些数据上定义了一个运算运算的集合。数据结构主要研究什么？数据结构主要研究什么？（或者说数据结构的研究对象是什么？）或者说数据结构的研究对象是什么？）数据结构的内容可归纳为三个部分：数据结构的内容可归纳为三个部分：按某种逻辑关系组织起来的一批数据，按一定按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在的映象方式把它
9、存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，这些数据上定义了一个运算的集合，就叫做数就叫做数据结构。据结构。逻辑结构逻辑结构 存储结构存储结构 运算集合运算集合上述上述4种基本的存储方法，既可以单独使用，也可种基本的存储方法，既可以单独使用，也可以组合起来对数据结构进行以组合起来对数据结构进行存储映象存储映象。同一种逻辑。同一种逻辑结构，若采用不同的存储方法，则可以得到不同的结构，若采用不同的存储方法，则可以得到不同的存储结构。存储结构。数据的存储结构数据的存储结构（4种基本的存储）顺序存储方法顺序存储方法 链接存储方法链接存储方法 索引存储方法索引存储方法 散列存储方法散列存
10、储方法算法+数据结构=程序1.2 1.2 为什么要学习数据结构为什么要学习数据结构?1.2.1 学习数据结构的重要性学习数据结构的重要性数据结构数据结构是计算机专业的专业基础是计算机专业的专业基础课。它主要讨论在软件开发中如何课。它主要讨论在软件开发中如何进行数据的组织、数据的表示和数进行数据的组织、数据的表示和数据的处理。它不仅为操作系统、编据的处理。它不仅为操作系统、编译原理、数据库系统、计算机网络译原理、数据库系统、计算机网络等后续课提供必要的知识，而且也等后续课提供必要的知识，而且也为学习者提供必要的技能训练。为学习者提供必要的技能训练。例例1.2 电话号码的查询问题。电话号码的查询问
11、题。要求编写一个电话号码的查询程序。对于任要求编写一个电话号码的查询程序。对于任意给出的一个姓名，如果该人留有电话号码，意给出的一个姓名，如果该人留有电话号码，那么就找出他的电话号码；否则就指出该人那么就找出他的电话号码；否则就指出该人没有电话号码。没有电话号码。1.2.2 数据结构的应用举例例例1.3 n个城市之间铺设光缆的问题。假设需要在n个城市之间铺设光缆，并且任意两个城市之间都可以铺设。大家知道，在n个城市之间只要铺设n-1条光缆，即能将这n个城市连成网络，只是由于地理位置的不同，所需经费也不同，问题是采用什么样的设计方案能使总投资最省。这个问题的数学模型如下页所示的“图”，图中“顶点
12、”表示城市，顶点之间的连线及其上面的数值表示可以铺设的光缆及所需经费。1.3 算法和算法分析1.3.1 什么是算法?由于数据的运算是通过算法来描述的，因此，讨论算法是数据结构课程的重要内容之一。算法算法（Algorithm）是对特定问题求解步骤的一种描述对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作；此外，一个算法还具有下列5个特性：1、有穷性有穷性 在有穷步内结束在有穷步内结束 2、确定性确定性 算法中的每一步不会产生二义性算法中的每一步不会产生二义性 3、可行性可行性 每一步均可经有限次运算实现每一步均可经有限次运算实现 4、输入输入 有零个或多个输入有
13、零个或多个输入 5、输出输出 有零个或多个输出有零个或多个输出程序与算法的异同 在一个算法中算法中，有些指令可能重复执行有些指令可能重复执行，因而指令的执行次数可能远远大于算法中的指令条数。由有穷性和可行性得知，对于任何输入，一个算法在执行了有限条指令后一定要终止，而且必须在有限时间内完成。因此，一个程序如果对一个程序如果对任何输入都不会产生无限循环，则它就是一个算法任何输入都不会产生无限循环，则它就是一个算法。尽管算法的含义与程序非常相似，但两者还是有区别的。首先，一个程序不一定满足有穷性，因此它不一定是算法。一个程序不一定满足有穷性，因此它不一定是算法。例如，系统程序中的操作系统，只要整个
14、系统不遭受破坏，它就永远不会停止，即使没有作业要处理，它仍处于等待循环中，以待一个新作业的进入。因此操作系统就不是一个算法。其次，程序中的指令必须是计算机可以执行的，而算法中的指令却无此限止。如果一个算法采用机器可执行的语言如果一个算法采用机器可执行的语言来书写，那么它就是一个程序来书写，那么它就是一个程序。1.3.2 算法的描述和设计 一个算法可以采用自然语言、数学语言或者约定的符号语一个算法可以采用自然语言、数学语言或者约定的符号语言（如伪码、框图等）来描述。言（如伪码、框图等）来描述。我们使用C语言来描述。书中采用的一些预定义常量，简要说明如下：/*函数结果的状态代码*/#define
15、TRUE 1#define FALSE 0#define OK 1#define ERROR 0 其他有关C语言的知识，请参考专门介绍C语言的书籍。如何评价算法的优劣？如何评价算法的优劣？一般来说，设计一个“好”的算法应该考虑以下几点：1、正确性正确性算法应当满足具体问题的需求。2、健壮性健壮性当输入数据非法非法时，算法也能适当地作反应或进行处理，而不会产生莫明其妙的输出结果或出错信息，并中止程序的执行。3、可读性可读性算法主要是为了方便人们的阅读和交流，其次才是机器执行。4、执行算法所耗费的时间执行算法所耗费的时间。5、执行算法所耗费的存储空间执行算法所耗费的存储空间，其中主要考虑辅助存储空
16、间。1.3.3 算法分析 评价一个程序优劣的重要依据是看这个程序的执行需要占用多少机器资源占用多少机器资源。在各种机器资源中，最重要的是时间资源和空间资源。因此，在进行程序分析时，大家最关心两点：程序所用算法运行时所要花费的时间代价 时间复杂度程序中使用的数据结构所占有的空间代价 空间复杂度通常，一个算法是由通常，一个算法是由控制结构控制结构（顺序、（顺序、选择和循环）和选择和循环）和基本语句基本语句构成的，而构成的，而算法时间取决于两者的综合效果。以算法时间取决于两者的综合效果。以基本语句重复执行的次数作为算法的基本语句重复执行的次数作为算法的时间度量。大部分情况下它是最深层时间度量。大部分
17、情况下它是最深层循环语句内的基本语句的执行次数循环语句内的基本语句的执行次数（频度）。（频度）。所谓语句的频度，指的是所谓语句的频度，指的是该语句重复执行的次数。该语句重复执行的次数。1、算法的时间复杂度分析 一般，我们把一般，我们把算法运行的时间定义运行的时间定义成函数成函数T(n)，一个算法所耗费的时间一个算法所耗费的时间将随输入数据量将随输入数据量n的增大而增大，的增大而增大，n是是该该算法输入数据的规模，这个数据规输入数据的规模，这个数据规模不是某一个具体的输入。模不是某一个具体的输入。T(n)的单的单位是不确定的，一般把它看成是在一位是不确定的，一般把它看成是在一个特定的计算机上执行
18、的指令条数。个特定的计算机上执行的指令条数。当讨论一个程序的运行时间当讨论一个程序的运行时间 T(n)时，时，注重的不是注重的不是T(n)的具体值，而是它的增长的具体值，而是它的增长率。即求出率。即求出T(n)随输入数据量随输入数据量n而增长的而增长的趋势趋势(极限极限)。称函数称函数f(n)f(n)是是T(n)T(n)增长率的上界，是增长率的上界，是指存在一个常数指存在一个常数M M和一个整数和一个整数n n0 0，当问题的，当问题的规模规模nnnn0 0时，时，T(n)MT(n)Mf(n)f(n)，记为，记为T T（n n）=O(f(n),=O(f(n),并称该算法的时间复杂度为并称该算法
19、的时间复杂度为O(f(n)O(f(n)。这时就称该算法的这时就称该算法的时间代价为时间代价为T(n)。人们通常采用大人们通常采用大O表示法来描述算表示法来描述算法分析的结果。法分析的结果。f(n)是某个值非负的函是某个值非负的函数，这种说法意味着：当数，这种说法意味着：当n充分大时，充分大时，该算法的复杂度不大于该算法的复杂度不大于f(n)的一个常数的一个常数倍。倍。评价算法的时间复杂性，就是设法评价算法的时间复杂性，就是设法找出找出 T(n)和和n的关系，即求出的关系，即求出T(n)一个算法所耗费的时间是算一个算法所耗费的时间是算法中所有语句执行时间之和，而法中所有语句执行时间之和，而每条语
20、句的执行时间是该语句的每条语句的执行时间是该语句的执行次数执行次数（频度）（频度）与该语句执行与该语句执行一次所需时间一次所需时间（略，因机器不同（略，因机器不同而不同）而不同）的乘积。的乘积。求时间复杂度方法：求时间复杂度方法：一般，求时间复杂度时，一般，求时间复杂度时，只考虑与程序规模有关的频只考虑与程序规模有关的频度最大的语句，如循环语句度最大的语句，如循环语句的循环体，多重循环的内循的循环体，多重循环的内循环等。环等。例例1.4 有下列三个程序段：x=x+1;s=0;频度为频度为1 for(i=1;i=n;i+)x=x+1;s=s+x;频度为频度为n for(j=1;j=n;j+)fo
21、r(k=1;k=n;k+)x=x+1;s=s+x;频度为频度为n2 它们含基本操作它们含基本操作“x加加1”的语句的频度分别为的语句的频度分别为1、n和和n2，因此，对于，因此，对于程序段程序段来说，其时间复杂度来说，其时间复杂度为为O(1)，程序段，程序段的时间复杂度为的时间复杂度为O(n)，程序段，程序段的时间复杂度为的时间复杂度为O(n2)。例例1.5 对n个记录进行升序排序的问题，采用最简单的选择排序方法。每次处理时，先从n个未排序的记录中选出一个最小记录，则第一次要经过n-1次比较，才能选出最小记录；第二次再从剩下的n-1个记录中经过n-2次比较，选出次小记录；如此反复，直到只剩两个
22、记录时，经过1次比较就可以确定它们的大小。整个排序过程的基本操作（即“原操作”）是“比较两个记录的大小”，含“比较”的语句的频度是：（n-1）+（n-2）+1=n（n-1）/2 因此，其时间复杂度为O（n2）。在同一个算法处理两个规模相同的问题，所花费的时间和空间代价也不一定相同。要全面分析一个算法，应该考虑它在最坏情况下的代价（即对同样规模的问题所花费的最大代价）、最好情况下的代价和平均情况下的代价等。然而，要全面准确地分析每个算法是相当困难的，因此，我们在分析算法时将主要考虑它们在最坏情况下的代价，个别地方也涉及到其他情况。通常有如下的函数关系排序：c log2 n n n log2 n
23、n2 n3 10 n 其中，c是与n无关的任意常数。上述函数排序与数学中对无穷大的分级完全一致，因为考虑的也是n值变化过程中的趋势，参见图1.4。例例1.6 要交换变量x和y中的内容，其程序段为 temp=x;x=y;y=temp;由于以上三条语句的频度均为1，说明该程序段的执行时间是一个与问题规模n无关的常数，因此，算法的时间复杂度为O（1）。例例1.7 有程序段如下：x=1;for(i=1;i=n;i+)for(j=1;j=n;j+)for(k=1;knext=q-next;free(q);return TRUE;特点：特点：在循环线性链表中，从在循环线性链表中，从表的任何一个结点出发都能
24、访表的任何一个结点出发都能访问到表中的所有结点。问到表中的所有结点。带头结点的单循环链表带头结点的单循环链表 int InsertCList(LinkList*L，int i，ElemType e)int j;LinkList*temp,*node;temp=L;j=1;while(jnext!=L)j+;temp=temp-next;/*无合适的插入位置无合适的插入位置*/*申请结点不成功申请结点不成功*/int DelCList(LinkList*L,int i)int j;LinkList *t1,*t2,j=1;t1=L-next;t2=L;if(t1=t2|i1)return FAL
25、SE;while(jnext;t2=t2-next;if(t1=L)return FALSE;t2-next=t1-next;free(t1);return TRUE;。在在C C语言中用标准函数语言中用标准函数来来执行内存分配执行内存分配,并用指针并用指针实现链表，因此称为动态链表。而实现链表，因此称为动态链表。而有的程序设计语言不支持指针类型，有的程序设计语言不支持指针类型，所以不能使用动态链表，为此引入所以不能使用动态链表，为此引入静态链表的概念。静态链表的概念。用数组描述的链表称为用数组描述的链表称为1A2B3C4D5E01A2B6C5D5E0X301234560123456data
26、next data next修改前的状态 修改后的状态#include“stdio.h”Typedef char datatype;typede struct nodenode datatypedatatype info;info;structstruct node node*next;next;NODE;定义表结点Info nextvoid joseph(int n,int s,intvoid joseph(int n,int s,int m)m)/*n n是链表中结点个数是链表中结点个数 */intint i,j;i,j;NODE NODE*creatlinklist(intcreatli
27、nklist(int););/*是建立带头结点单链表的是建立带头结点单链表的函数说明函数说明 */NODE NODE*h,h,*p,p,*q,q,*r;r;if(ns)return;if(ns)return;/*开始时表中结点数少于开始时表中结点数少于s s，即找不到第即找不到第s s个结点个结点*/h=creatlinklisth=creatlinklist(n);(n);/*函数调用函数调用,建立一个含有建立一个含有n n个结点的带表头的单链表个结点的带表头的单链表*/q=h;q=h;for(i=1;is;i+)for(i=1;inext;q=q-next;/*循环结束后循环结束后,q,q
28、指向第指向第s s结点的前趋结点结点的前趋结点*/p=q-next;p=q-next;/*p p指向第指向第s s个结点个结点*/for(i=1;in;i+)for(i=1;in;i+)for(j=1;jm;j+)for(j=1;jnext!=NULL)&(q-next!=NULL)if(p-next!=NULL)&(q-next!=NULL)/*如果当前指针如果当前指针p,qp,q所指的下一个结点都不是表尾所指的下一个结点都不是表尾,则向下移指针则向下移指针p p和和q q*/q=q-next;p=p-next;q=q-next;p=p-next;else else /*即指针即指针p,qp
29、,q的下一结点至少有一个是空的下一结点至少有一个是空*/if(p-next=NULL)if(p-next=NULL)/*p p所指的下一结点是空所指的下一结点是空,则其下一结点就是第一个则其下一结点就是第一个*/q=q-next;p=h-next;q=q-next;p=h-next;elseelse /*q q所指的下一结点是空所指的下一结点是空,则其下一结点就是第一个则其下一结点就是第一个*/q=h-next;p=p-next;q=h-next;p=p-next;printfprintf(“%cn”,p-info);(“%cn”,p-info);/*印要出列印要出列元素元素的信息的信息*/r
30、=p;r=p;/*让指针让指针r r指向要删的结点指向要删的结点p,p,准备释放准备释放*/if(p-next=NULL)if(p-next=NULL)/*如表中还有结点，且这时指针如表中还有结点，且这时指针p p的下一结的下一结*/*点为空，而点为空，而p p所指结点所指结点将被释放。将被释放。这表示这表示p p所指结点为链表尾所指结点为链表尾*/p=h-next;p=h-next;q-next=NULL;q-next=NULL;else else /*p p所指结点不为链表尾所指结点不为链表尾*/p=p-next;p=p-next;if(q-next!=NULL)if(q-next!=NU
31、LL)/*这表示这表示q q所指结点不为链表尾所指结点不为链表尾*/q-next=p;q-next=p;else else /*这表示这表示q q所指结点为链表尾所指结点为链表尾*/h-next=p;h-next=p;free(r);free(r);/*释放释放r r结点结点*/printfprintf(“%cn”,(h-next)-info);(“%cn”,(h-next)-info);/*输出最后输出最后出列的出列的结点结点*/NODE NODE*creatlinklist(intcreatlinklist(int n)n)/*建立含有建立含有n n个结点并带表头的单链表的函数个结点并带表
32、头的单链表的函数*/intint i;i;NODE NODE*head,head,*p,p,*q;q;if(n=0)if(n=0)return NULL;return NULL;head=(NODE head=(NODE*)malloc(sizeof)malloc(sizeof(head);(head);/*申请一个结点为表头申请一个结点为表头*/q=head;q=head;for(i=1;in;i+)for(i=1;inext=p;q-next=p;q=p;q=p;/*q q指向表尾指向表尾,准备链入下一个结点准备链入下一个结点*/p-next=NULL;p-next=NULL;/*将最后一个结点的链域置为将最后一个结点的链域置为NULLNULL*/return head;return head;main()int n,s,m;printf(“Please input n,s and m:n”);/*输入单链表的结点数输入单链表的结点数n n*/scanf(“%d%d%d”,&n,&s,&m);joseph(n,s,m);多项式多项式 3x6-5x5y2+6y6z 的链表表示的链表表示
