数据结构：第1章 绪论

数据结构

——C++语言描述1为什么要学习数据结构这门课程当今科学研究的三大手段：理论实验计算“计算”是随着计算技术的发展而出现的新型手段。

如用计算机进行模拟实验，而后确定方案——计算模拟是“计算”的特长之一：在制造某半导体时，用计算机模拟各种配方所得材料的特性，确定配方后再实际试验制造生物制药公司也是用计算模拟确定配方后再做实验验证(生化试剂昂贵啊)汽车碰撞也是先计算模拟碰撞，确定设计，再用车做碰撞实验核武器设计也采用计算模拟核武器爆炸可是，为什么要学习数据结构？为什么要学习数据结构这门课程现代社会计算和计算机无处不在：手机上网微信、QQ微博游戏、电影、动画各种智能家电：电视机似乎我们离不开计算机了可是，为什么要学习数据结构？3数据结构是一门什么课程数据结构是一门讲述如何在计算机中存储数据和处理数据的课程通俗的说，数据结构还是一门学习写程序的课——更高级的程序设计课程学编程的境界学会写程序学会高效地写程序学会写高效的程序学会设计算法学会设计有用的算法

本院各专业都与“计算”相关直接相关：信息与计算科学间接相关：数学与应用数学概率、统计学无论哪个专业，当需要使用计算机解决问题时，就会用到数据结构与算法6课程性质数据结构是计算科学学科及其相关学科的基础课

公共基础课、专业基础课、专业方向课、专业选修课在教学计划中的地位：核心、承上启下

前导课：高等数学、离散数学、程序设计语言后续课：算法设计、数据库、操作系统、计算机网络、编译原理……属于武术中的“练功”科目

“练武不练功，到头一场空”考研：专业课必考（初试或复试）教学目标掌握基本的数据结构

工具箱→复用、修改、重组培养算法设计能力、程序设计能力

算法——程序的灵魂问题求解过程：问题→想法→算法→程序程序设计研究的层次：算法→方法学→语言→工具培养算法分析能力

评价算法、改进算法学习要求循序渐进，切忌心浮气躁提高课外学习的时间和内容理解科学而不是背诵科学→读书正确对待考试做习题

华罗庚：“学数学不做习题等于入宝山而空返”

做实验

计算机学科是一门科学性与工程性并重的学科，表现为理论和实践紧密结合的特征。

学习要求循序渐进，切忌心浮气躁提高课外学习的时间和内容理解科学而不是背诵科学→读书正确对待考试作习题

有人说：“学数据结构不做习题和实验等于入宝山而空返”

作实验

计算机学科是一门科学性与工程性并重的学科，

表现为理论和实践紧密结合的特征。

主教材

王红梅,胡明,王涛.数据结构（C++版）第2版.清华大学出版社

辅导及实验教材

王红梅等.数据结构（C++版）学习辅导与实验指导（第2版）.

清华大学出版社

参考教材

1.严蔚敏.数据结构.清华大学出版社.1997

2.张铭.数据结构与算法.高等教育出版社.2008

3.曹宏庆译.如何求解问题.中国水利水电出版社.2003关于教材关于C++参考书林瑶等译，《

C++大学自学教程(第7版)》，AlStevens,Dr.Dobb‘sJournal

，电子工业出版社，2004年1月裘宗燕译，《C++程序设计语言（特别版）》，BjarneStroustrup（C++语言的作者）,机械工业出版社，2002-7-1

潘爱民等译，《C++Primer(3RD)中文版》，StanleyB.Lippman,JoseeLajoie，中国电力出版社,

2002-4-1

周靖等译，《C++编程金典（第3版）》，H.M.Deitel,P.J.Deitel，清华大学出版社，2002-9-1刘宗田等译，《C++编程思想》，BruceEckel，机械工业出版社，2000-1-1成绩组成理论课成绩平时成绩

10％~20%：出勤＋作业＋实验期中考试成绩

40％~50%期末考试成绩

40％~50%实验课成绩：出勤＋实验＋期末成绩：百分制有关通过网络交作业和实验的要求将作业或实验相关文件压缩打包上传，具体要求如下：压缩包文件命名格式：

<学号><姓名><作业或实验说明>

如：00281001王五实验2

00281001王五第一章作业不同的实验和作业用不同的压缩包文件上传，不要合在一个压缩包文件中；对实验压缩包，要求将该次实验工程所在目录中的所有文件（要包括目录,但要删除其中的debug目录）压缩，并按如上命名：

00281001王五实验2.rar将压缩文件上传到指定的目录即可；实验提交和作业提交地址：6/

提交时用户名：student密码：123456

实验课要求到实验室上机课件下载地址：

6/

用户名：zsuzyd密码：123456

下载请用FTP软件FileZillaQQ:413393491，E-Mail:用qq邮箱（通常处于潜水状态，有问题请留言。）第1章绪论数据结构在程序设计中的作用本课程讨论的主要内容数据结构的基本概念算法及算法分析本章的基本内容是：1938年出生，25岁毕业于加州理工学院数学系，博士毕业后留校任教，28岁任副教授。30岁时，加盟斯坦福大学计算机系，任教授。从31岁起，开始出版他的历史性经典巨著：TheArtofComputerProgramming，他计划共写7卷，然而出版三卷之后，已震惊世界，使他获得计算机科学界的最高荣誉——图灵奖，此时，他年仅36岁。数据结构的创始人——克努思1.1数据结构在程序设计中的作用程序设计的实质是什么?数据表示：将数据存储在计算机（内存）中数据处理：处理数据，设计方案（算法）数据结构问题起源于程序设计

1.1数据结构在程序设计中的作用利用计算机求解问题的一般过程?计算机不能分析问题并产生问题的解决方案，必须由人来分析问题，确定问题的解决方案，编写程序，然后让计算机执行程序最终获得问题的解。1.1数据结构在程序设计中的作用例1-1手机电话号码查询问题将电话号码集合组织成线性结构和树结构，查找操作的效率不同，当数据量较大时差别就更大。1.2本课程讨论的主要内容计算机求解问题:

问题→抽象出问题的模型→求模型的解问题——数值问题、非数值问题数值问题→数学方程非数值问题→数据结构例1-2学籍管理问题完成什么功能?各表项之间是什么关系？1.2本课程讨论的主要内容例1-3人——机对弈问题如何实现对弈?各格局之间是什么关系？1.2本课程讨论的主要内容例1-4七巧板涂色问题

如何表示区域之间的邻接关系？1.2本课程讨论的主要内容本课程讨论非数值问题的数据组织和处理，主要内容如下：（1）数据的逻辑结构：线性表、树、图等数据结构，其核心是如何组织待处理的数据以及数据之间的关系；（2）数据的存储结构：如何将线性表、树、图等数据结构存储到计算机的存储器中，其核心是如何有效地存储数据以及数据之间的逻辑关系；（3）算法：如何基于数据的某种存储结构实现插入、删除、查找等基本操作，其核心是如何有效地处理数据；（4）常用数据处理技术：查找技术、排序技术、索引技术等。1.2本课程讨论的主要内容1.3数据结构的基本概念数据：所有能输入到计算机中并能被计算机程序识别和处理的符号集合。数值数据：整数、实数等非数值数据：图形、图象、声音、文字等数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据项：构成数据元素的不可分割的最小单位。数据结构的基本概念学号姓名性别出生日期政治面貌0001陆宇男1986/09/02团员0002李明男1985/12/25党员0003汤晓影女1986/03/26团员数据项数据元素数据、数据元素、数据项之间的关系包含关系：数据由数据元素组成，数据元素由数据项组成。数据元素是讨论数据结构时涉及的最小数据单位，其中的数据项一般不予考虑。1.3数据结构的基本概念数据结构数据元素关系数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑关系的整体。1.3数据结构的基本概念数据结构的基本概念关联方式或邻接关系数据的逻辑结构是从具体问题抽象出来的数据模型学籍管理问题中，表项之间的逻辑关系指的是什么？人机对弈问题中，格局之间的逻辑关系指的是什么？教学计划编排问题中，课程之间的逻辑关系指的是什么？数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑关系的整体。1.3数据结构的基本概念数据结构的基本概念数据的逻辑结构在形式上可定义为一个二元组：Data_Structure=(D,R)其中D是数据元素的有限集合，R是D上关系的集合。数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑关系的整体。1.3数据结构的基本概念数据结构的基本概念Data_Structure=(D,R)其中D={A,B,C,D,E,F,G}R={R1}，R1={<A,B>,<A,E>,<A,F>,<B,C>,<B,D>,<C,D>,<D,E>,<D,G>,<E,F>,<E,G>}数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑关系的整体。存储结构：又称为物理结构，是数据及其逻辑结构在计算机中的表示。1.3数据结构的基本概念数据结构的基本概念内存存储结构实质上是内存分配，在具体实现时依赖于计算机语言。数据结构从逻辑上分为四类：⑴集合：数据元素之间就是“属于同一个集合”；1.3数据结构的基本概念数据结构的基本概念数据结构从逻辑上分为四类：⑴集合：数据元素之间就是“属于同一个集合”；⑵线性结构：数据元素之间存在着一对一的线性关系；1.3数据结构的基本概念数据结构的基本概念数据结构从逻辑上分为四类：⑴集合：数据元素之间就是“属于同一个集合”；⑵线性结构：数据元素之间存在着一对一的线性关系；⑶树结构：数据元素之间存在着一对多的层次关系；1.3数据结构的基本概念数据结构的基本概念数据结构从逻辑上分为四类：⑴集合：数据元素之间就是“属于同一个集合”；⑵线性结构：数据元素之间存在着一对一的线性关系；⑶树结构：数据元素之间存在着一对多的层次关系；⑷图结构：数据元素之间存在着多对多的任意关系。1.3数据结构的基本概念数据结构的基本概念通常有两种存储结构：1.顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。…batcateat…起始地址例：（bat,cat,eat）1.3数据结构的基本概念数据结构的基本概念通常有两种存储结构：1.顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。2.链接存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。例：（bat,cat,eat）1.3数据结构的基本概念数据结构的基本概念0200020803000325…………bat0200cat0325eat∧逻辑结构和存储结构之间的关系数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是面向计算机的。一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。

1.3数据结构的基本概念抽象数据类型1.数据类型（DataType）：一组值的集合以及定义于这个值集上的一组操作的总称。

例如：C++中的整型变量

2.抽象（Abstract）:抽出问题本质的特征而忽略非本质的细节。

例如：地图、驾驶汽车3.抽象数据类型（AbstractDataType，ADT）:一个数据结构以及定义在该结构上的一组操作的总称。1.3数据结构的基本概念1.3数据结构的基本概念抽象数据类型在设计ADT时，把ADT的定义、设计和实现分开来。定义部分只包含数据的逻辑结构和所允许的操作集合，一方面，ADT的使用者依据这些定义来使用ADT，即通过操作集合对该ADT进行操作；另一方面，ADT的实现者依据这些定义来完成该ADT各种操作的具体实现。ADT抽象数据类型名Data数据元素之间逻辑关系的定义Operation

操作1

前置条件：执行此操作前数据所必须的状态

输入：执行此操作所需要的输入

功能：该操作将完成的功能

输出：执行该操作后产生的输出

后置条件：执行该操作后数据的状态操作2

…………操作n……endADT

1.3数据结构的基本概念抽象数据类型1.3数据结构的基本概念（小结）数据的操作：插入、删除、修改、检索、排序等数据的逻辑结构数据的存储结构顺序存储链式存储集合线性结构树结构图结构非数值问题数据表示算法的相关概念1.算法（Algorithm）:是对特定问题求解步骤的一种描述，是指令的有限序列。2.

算法的五大特性：⑴

输入：一个算法有零个或多个输入。⑵输出：一个算法有一个或多个输出。⑶有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。⑷确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。⑸可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。1.4算法及算法分析1.4算法及算法分析“好”算法的衡量指标正确性能解决问题，获得正确结果健壮性（鲁棒性）简单性容易理解和实现抽象分级：如将算法分成多个模块，每个模块又可细分方便好用和可读性强：人类短期记忆的对象数=7±2个高效性时间和空间效率

欧几里德算法（有穷性、确定性、可行性）mnr算法的例：欧几里德算法——辗转相除法求两个自然数m

和n

的最大公约数1.4算法及算法分析算法的描述方法——自然语言优点：容易理解缺点：冗长、二义性使用方法：粗线条描述算法思想

注意事项：避免写成自然段1.4算法及算法分析步骤1：将m除以n得到余数r；步骤2：若r等于0，则n为最大公约数，算法结束；否则执行步骤3；步骤3：将n的值放在m中，将r的值放在n中，重新执行步骤1；例：欧几里德算法自然语言1.4算法及算法分析优点：流程直观缺点：缺少严密性、灵活性使用方法：描述简单算法注意事项：注意抽象层次。可按抽象层次分级描述算法的描述方法——流程图1.4算法及算法分析N开始输入m和n

r=m%nr=0m=n；n=r输出n结束Y流程图例：欧几里德算法1.4算法及算法分析优点：能由计算机执行缺点：抽象性差，对语言要求高使用方法：算法需要验证注意事项：将算法写成子函数。按抽象层次分级——算法函数用下一层的子函数描述算法的描述方法——程序设计语言1.4算法及算法分析#include<iostream.h>intCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}voidmain(){cout<<CommonFactor(63,54)<<endl;}程序设计语言例：欧几里德算法1.4算法及算法分析伪代码（Pseudocode）：介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。优点：表达能力强，抽象性强，容易理解使用方法：7±2——抽象分级算法的描述方法——伪代码1.4算法及算法分析1.r=m%n;2.循环直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.输出n;伪代码上述伪代码再具体一些，用C++的函数来描述。例：欧几里德算法1.4算法及算法分析intCommonFactor(intm,intn){r=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}1.4算法及算法分析对C++语言进行了如下简化：⑴局部变量可以不声明；⑵写出子函数即可，子函数不用在主函数中调用，省略主函数；⑶所有的包含函数（头函数.h）可以省略；⑷交换两个变量的语句可以简写为a←→b。算法分析度量算法效率的方法：

事后统计：将算法实现，测算其时间和空间开销。

缺点：⑴编写程序实现算法将花费较多的时间和精力；⑵所得实验结果依赖于计算机的软硬件等环境因素。

事前分析：对算法所消耗资源的一种估算方法。1.4算法及算法分析1.4算法及算法分析方法在算法中的某些部位插装时间函数time()测定算法在一组已给输入下完成某一功能所花费的时间事后统计测定顺序搜索算法seqsearch的效率

行

int

seqsearch(

inta[],

constintn,

constintx)

//a[0],…,a[n-1]

1

{

2

inti=0;

3

while(i<n

&&a[i]!=x)

4

i++;

5

if(i==n)return-1;

6

return

i;

7

}1.4算法及算法分析事后统计的例——顺序搜索(SequenialSearch)插装time()的计时程序

void

TimeSearch()

{//在1到1000中搜索0

inta[1001],n[20];//n[i]存放要搜索的元素个数

for

(

intj=1;j<=1000;j++)

a[j]=j;//a[1]=1,a[2]=2,…

for(j=0;j<10;j++)

{

n[j]=10*j;//n[0]=0,n[1]=10,n[2]=20

n[j+10]=100*(j+1);

}//n[10]=100,n[11]=200,n[12]=300...cout

<<"ntime"<<

endl;

for

(j=0;j<20;j++){

long

start,stop;

time(start);

int

k=seqsearch(a,n[j],0);

time(stop);

longrunTime=stop-start;

cout

<<""<<n[j]<<""<< runTime<<

endl;

}

cout

<<"Timesareinhundredthsofa second."<<

endl;}程序测试结果输出测定顺序搜索算法的效率

——插装时间函数time()后就行了？

改进的计时程序void

TimeSearch()

{inta[1001],n[20];

constlongr[20]={300000,300000,200000,200000,100000,100000,100000,80000,80000,50000,50000,25000,15000,15000,10000,7500,7000,6000,5000,5000};

for(

intj=1;j<=1000;j++)

a[j]=j;

for(j=0;j<10;j++){

n[j]=10*j;n[j+10]=100*(j+1);

}cout<<"ntotalTimerunTime"<<

endl;for

(j=0;j<20;j++){

long

start,stop;

time(start);

//开始计时

for(

longb=1;b<=r[j];b++)

intk=seqsearch(a,n[j],0

);

//执行r[j]次

time(stop);

//停止计时

longtotalTime=stop-start;

float

runTime=

(float)(totalTime)/(float)(r[j]);

cout

<<""<<n[j]<<""<<totalTime<<""<<runTime<<

endl;

}}程序测试结果输出算法分析算法分析（AlgorithmAnalysis）：对算法所需要的计算机资源——时间和空间进行（事前）估算。时间复杂性（TimeComplexity）空间复杂性（SpaceComplexity）1.4算法及算法分析算法的时间复杂度分析1.4算法及算法分析算法分析算法的执行时间＝每条语句执行时间之和执行次数×执行一次的时间指令系统、编译的代码质量单位时间每条语句执行次数之和for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;基本语句的执行次数问题规模：输入量的多少。基本语句：是执行次数与整个算法的执行次数成正比的操作指令。for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;问题规模：n基本语句：x++1.4算法及算法分析算法分析空间复杂度

当问题规模由1增至n时，算法所需空间也由S(1)增至S(n)（按某个单位计算），则S(n)称为此算法的空间复杂度时间复杂度

当问题规模由1增至n时，算法所耗时间也由T(1)增至T(n)（按某个单位计算），则T(n)称为此算法的时间复杂度问题规模：输入量的多少。1.4算法及算法分析算法分析空间复杂度估算存储空间的固定部分

程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占的空间可变部分

尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用的空间、通过new和delete命令动态使用的空间例：floatabc(floata,floatb,floatc){returna+b+b*c+(a+b-c)/(a+b)}

//占用的空间数为常数floatsum(floata[],constintn){floats=0.0;for(inti=0;i<n;i++)s+=a[i];returns;}

//占用的空间数为常数;数组a[]在此函数中仅占用一个空间(首地址)floatrsum(floata[],constintn){if(n<=0)return0;elsereturnrsum(a,n-1)+a[n-1];}

//占用的空间数为4(n+1);此为递归函数，深度=n+1，每层保留两个参数、函数返回值和返回地址共四个存储单位时间复杂度估算算法指令的执行时间程序步语法上或语义上有意义的一段指令序列执行时间与实例特性无关例如：

注释：程序步数为0

声明语句：程序步数为0

表达式：程序步数为1程序步确定方法

1）插入计数全局变量count（称为插桩）

2）建表，列出每个语句的程序步

例以迭代方式求累加和的函数行

float

sum(float

a[],

constint

n)

1

{

2

floats=0.0;

3

for(inti=0;i<n;i++)

4s+=a[i];

5

returns;

6

} 在求累加和程序中加入count语句

floatsum(

floata[],constintn){floats=0.0;count++; //count统计执行语句条数

for(

inti=0;i<n;i++)

{

count++; //针对for语句

s+=a[i]; count++;//针对赋值语句

}

count++;//针对for的最后一次

count++;

//针对return语句

returns;}

//执行结束得程序步数count=2*n+3注意：例如：赋值语句

x=sum(R,n);

本身的程序步数为1；

一次执行对函数

sum(R,n)的调用需要的程序步数为2*n+3；

一次执行的程序步数为 1+2*n+3=2*n+4■不同语句的执行时间不同，但是如果它们的执行时间差一个与实例特性无关(包括与问题规模无关)的常数时，仍将它们看成一样的程序步。由此，最终结果也差常数倍。

■一个语句本身的程序步数可能不等于该语句一次执行所具有的程序步数——可能与问题规模有关。程序步数计算工作表格时间复杂度估算有时我们仅估算算法中某一种运算(操作)的数目：加减法数目，乘除法数目数据交换或移动的次数定义

若存在两个正的常数c和n0，对于任意n≥n0，都有|T(n)|≤c×f(n)，则称T(n)=O(f(n))。n0问题规模n执行次数n0之前的情况无关紧要T(n)c×f(n)当问题规模充分大时在渐近意义下的阶。1.4算法及算法分析算法分析——大O符号（大O表示法

）加法规则

针对并列程序段

T(n,m)=T1(n)+T2(m)=O(f(n))+O(g(m)) =O(max(f(n),g(m)))

=O(f(n)+g(m))

乘法规则

针对嵌套程序段

T(n,m)=T1(n)*T2(m)=O(f(n))*O(g(m))

=O(f(n)*g(m))渐进的空间复杂度(记号同时间)

S(n)=O(f(n))

算法分析——大O符号（大O表示法

）运算规则1.4算法及算法分析定理：若A(n)=amnm+am-1nm-1++a1n+a0是一个m次多项式，且m是与n无关的常数，则A(n)=O(nm)。说明：在计算算法时间复杂度时，可以忽略所有低次幂和最高次幂的系数。1.4算法及算法分析算法分析——大O符号例1-5

++x;例1-6

for(i=1;i<=n;++i)++x;例1-7for(i=1;i<=n;++i)for(j=1;j<=n;++j)++x;

例1-8for(i=1;i<=n;++i)for(j=1;j<=i-1;++j)++x;1.4算法及算法分析算法分析例1-9for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i][j]=0;for(k=1;k<=n;++k)