数据结构课件

数据结构

——C++语言描述

1第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)c[i][j]+=a[i][k]*b[k][j];}例1-10for(i=1;i<=n;i=2*i) ++x;Ο(1)＜(log2n)＜(n)＜(nlog2n)＜(n2)＜(n3)＜…＜(2n)＜(n!)1.4算法及算法分析算法分析各增长率函数值的比较c<log2n<n<nlog2n<n2<n3<2n<3n<n!运行时间估计的例•假设CPU每秒处理106个指令，对于输入规模为=108的问题，时间代价为T(n)=2n2的算法要运行多长时间？–操作次数为

T(n)=T(108)=2×(108)2=2×1016–运行时间为

2×1016/106=2×1010秒–每天有86,400秒，因此需要231,480天(634年)运行时间估计的例（续）假设CPU每秒处理106个指令，对于输入规模为n=108的问题，时间代价为T(n)=nlogn的算法要运行多长时间？–操作次数为T(n)=T(108)=108×log108=2.66×109–运行时间为2.66×109/106=2.66×103秒，即44.33分规定时间内能解决的问题规模.假设CPU每秒处理106个指令，则每小时能够解决的最大问题规模T(n)/106≤3600T(n)=2n2，即2n2≤3600×106n≤42,426T(n)=nlogn，即nlogn≤3600×106n≤133,000,000加快硬件速度设CPU每秒处理108个指令(快100倍)处理时间都降为原来的1/100解决问题的规模T(n)=2n2，规模增加10倍T(n)=nlogn，规模增加75倍最好情况、最坏情况、平均情况例：在一维整型数组A[n]中顺序查找与给定值k相等的元素（假设该数组中有且仅有一个元素值为k）。

intFind(intA[],intn)

{for(i=0;i<n;i++)if(A[i]==k)break;returni; }1.4算法及算法分析基本语句的执行次数是否只和问题规模有关？——考虑输入不同的情况！最好情况：出现概率较大时分析最差情况：实时系统平均情况：已知输入数据是如何分布的，通常假设等概率分布结论：如果问题规模相同，时间代价与输入数据有关，则需要分析最好情况、最坏情况、平均情况。1.4算法及算法分析最好情况、最坏情况、平均情况2.1线性表的逻辑结构数据元素之间的关系是什么？2.1线性表的逻辑结构数据元素之间的关系是什么？现实生活中，许多问题抽象出的数据模型是线性表，如何存储这种线性结构并实现插入、删除、查找等基本操作呢？线性表的定义线性表：简称表，是n（n≥0）个具有相同类型的数据元素的有限序列。线性表的长度：线性表中数据元素的个数。空表：长度等于零的线性表，记为：L=()。非空表记为：L＝（a1,a2,…,ai-1,ai,…,an)2.1线性表的逻辑结构其中，ai（1≤i≤n）称为数据元素；下角标i表示该元素在线性表中的位置或序号。a1a3a4ana22.1线性表的逻辑结构线性表的特性1.有限性：线性表中数据元素的个数是有穷的。2.相同性：线性表中数据元素的类型是同一的。3.顺序性：线性表中相邻的数据元素ai-1和ai之间存在序偶关系(ai-1,ai)，即ai-1是ai的前驱，ai是ai-1的后继；a1无前驱，an无后继，其它每个元素有且仅有一个前驱和一个后继。

线性表的抽象数据类型定义ADTListData

线性表中的数据元素具有相同类型，相邻元素具有前驱和后继关系OperationInitList

前置条件：表不存在输入：无

功能：表的初始化输出：无

后置条件：建一个空表2.1线性表的逻辑结构DestroyList

前置条件：表已存在

输入：无

功能：销毁表

输出：无

后置条件：释放表所占用的存储空间Length

前置条件：表已存在

输入：无

功能：求表的长度

输出：表中数据元素的个数

后置条件：表不变2.1线性表的逻辑结构线性表的抽象数据类型定义Get

前置条件：表已存在

输入：元素的序号i

功能：在表中取序号为i的数据元素

输出：若i合法，返回序号为i的元素值，否则抛出异常

后置条件：表不变Locate

前置条件：表已存在

输入：数据元素x

功能：在线性表中查找值等于x的元素

输出：若查找成功，返回x在表中的序号，否则返回0

后置条件：表不变2.1线性表的逻辑结构线性表的抽象数据类型定义线性表的抽象数据类型定义Insert

前置条件：表已存在

输入：插入i；待插x

功能：在表的第i个位置处插入一个新元素x

输出：若插入不成功，抛出异常

后置条件：若插入成功，表中增加一个新元素Delete

前置条件：表已存在

输入：删除位置i

功能：删除表中的第i个元素

输出：若删除成功，返回被删元素，否则抛出异常

后置条件：若删除成功，表中减少一个元素2.1线性表的逻辑结构线性表的抽象数据类型定义Empty

前置条件：表已存在

输入：无

功能：判断表是否为空

输出：若是空表，返回1，否则返回0

后置条件：表不变ADT进一步说明:（1）线性表的基本操作根据实际应用是而定；（2）复杂的操作可以通过基本操作的组合来实现；（3）对不同的应用，操作的接口可能不同。2.1线性表的逻辑结构2.2线性表的顺序存储结构及实现顺序表——线性表的顺序存储结构例：（34,23,67,43）342367434存储要点用一段地址连续的存储单元依次存储线性表中的数据元素2.2线性表的顺序存储结构及实现顺序表——线性表的顺序存储结构例：（34,23,67,43）34236743存储空间的起始位置4用什么属性来描述顺序表？顺序表的容量（最大长度）顺序表的当前长度2.2线性表的顺序存储结构及实现顺序表——线性表的顺序存储结构例：（34,23,67,43）342367434如何实现顺序表的内存分配？顺序表一维数组0…i-2i-1…n-1Max-1a1…ai-1ai…an空闲长度2.2线性表的顺序存储结构及实现顺序表一般情况下，(a1，a2，…,ai-1，ai,…,an)的顺序存储：数组的长度Max线性表的长度Length数组的长度大于等于当前线性表的长度如何求得任意元素的存储地址？0…i-2i-1…n-1Max-1a1…ai-1ai…an空闲长度2.2线性表的顺序存储结构及实现顺序表一般情况下，(a1，a2，…,ai-1，ai,…,an)的顺序存储：cLoc(ai)Loc(a1)0…i-2i-1…n-1Max-1a1…ai-1ai…an空闲长度Loc(ai)=Loc(a1)+(i-1)×c随机存取：在O(1)时间内存取数据元素2.2线性表的顺序存储结构及实现顺序表一般情况下，(a1，a2，…,ai-1，ai,…,an)的顺序存储：cLoc(ai)Loc(a1)2.2线性表的顺序存储结构及实现存储结构是数据及其逻辑结构在计算机中的表示；存取结构是在一个数据结构上对访问操作的时间性能的一种描述。存储结构和存取结构“顺序表是一种随机存取的存储结构”的含义为：在顺序表这种存储结构上进行的访问，其时间性能为O(1)。顺序表类的声明constintMaxSize=100;template<classDataType>//模板类classSeqList{public:SeqList();//构造函数

SeqList(DataTypea[],intn);~SeqList();//析构函数intLength();DataTypeGet(inti);intLocate(DataTypex);voidInsert(inti,DataTypex);DataTypeDelete(inti);private:DataTypedata[MaxSize];intlength;};2.2线性表的顺序存储结构及实现顺序表的实现——无参构造函数操作接口：SeqList()

算法描述：SeqList<DataType>

::SeqList(){length=0;}2.2线性表的顺序存储结构及实现

datalength0顺序表的实现——有参构造函数操作接口：SeqList(DataTypea[],intn)2.2线性表的顺序存储结构及实现顺序表

数组a351224334253512243342顺序表的实现——有参构造函数template<classDataType>SeqList<DataType>

::SeqList(DataTypea[],intn){if(n>MaxSize)throw"参数非法";

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

data[i]=a[i];length=n;}2.2线性表的顺序存储结构及实现算法描述：顺序表的实现——插入操作接口：voidInsert(inti,DataTypex)插入前：(a1,…,ai-1,ai,…,an)插入后：(a1,…,ai-1,x

,ai,…,an)2.2线性表的顺序存储结构及实现ai-1和ai之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化33顺序表的实现——插入例：（35，12，24，42），在i=2的位置上插入33。表满：length>=MaxSize合理的插入位置：1≤i≤length+1（i指的是元素的序号）2.2线性表的顺序存储结构及实现435122442a1a2a3a401234422412335什么时候不能插入？注意边界条件算法描述——伪代码1.如果表满了，则抛出上溢异常;2.如果元素的插入位置不合理，则抛出位置异常;3.将最后一个元素至第i个元素分别向后移动一个位置；4.将元素x填入位置i处；5.表长加1；2.2线性表的顺序存储结构及实现顺序表的实现——插入顺序表的实现——插入template<classDataType>voidSeqList<DataType>::Insert(inti,DataTypex){if(length>=MaxSize)throw"上溢";

if(i<1||i>length+1)throw"位置";for(j=length;j>=i;j--)data[j]=data[j-1];data[i-1]=x;length++;}算法描述——C++描述2.2线性表的顺序存储结构及实现基本语句？顺序表的实现——插入最好情况（i=n+1）：基本语句执行0次，时间复杂度为O(1)。最坏情况（i=1）：基本语句执行n+1次，时间复杂度为O(n)。平均情况（1≤i≤n+1）：时间复杂度为O(n)。时间性能分析2.2线性表的顺序存储结构及实现å+-+=11)=1(niiinpå+-++=11)=1(11niinn2n=O(n)操作接口：DataTypeDelete(inti)删除前：(a1,…,ai-1,ai,ai+1,…,an)删除后：(a1,…,ai-1,ai+1,…,an)

顺序表的实现——删除2.2线性表的顺序存储结构及实现ai-1和ai之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化例：（35,33,12,24,42），删除i=2的数据元素。仿照顺序表的插入操作，完成：1.分析边界条件；2.分别给出伪代码和C++描述的算法；3.分析时间复杂度。2.2线性表的顺序存储结构及实现顺序表的实现——删除535a1a2a3a401234422412334a5122442顺序表的实现——按位查找操作接口：DataTypeGet(inti)

2.2线性表的顺序存储结构及实现0…i-2i-1…n-1Max-1a1…ai-1ai…an空闲

n算法描述：template<classDataType>DataTypeSeqList<DataType>

::Get(inti){

if(i>=1&&i<=length)returndata[i-1];}时间复杂度？顺序表的实现——按值查找操作接口：intLocate(DataTypex)

2.2线性表的顺序存储结构及实现535a1a2a3a40123442241233a5例：在（35,33,12,24,42）

中查找值为12的元素，返回在表中的序号。iii注意序号和下标之间的关系template<classDataType>intSeqList<DataType>

::Locate(DataTypex){for(i=0;i<length;i++)if(data[i]==x)returni+1;return0;}2.2线性表的顺序存储结构及实现顺序表的实现——按值查找算法描述：时间复杂度？顺序表类的声明constintMaxSize=100;template<classDataType>//模板类classSeqList{public:SeqList(intmaxlen=MaxSize);//构造函数

SeqList(DataTypea[],intn);~SeqList();//析构函数intLength();DataTypeGet(inti);intLocate(DataTypex);voidInsert(inti,DataTypex);DataTypeDelete(inti);private:

DataType*data;intlength;intmaxsize;

booladdSpace(intsize=10);};2.2线性表的顺序存储结构及实现(动态数组)顺序表的实现——构造函数操作接口：SeqList(int

maxlen=MaxSize)

算法描述：SeqList<DataType>

::SeqList(int

maxlen):length(0),maxsize(maxlen){if(maxlen<=0)throw“参数非法”; data=new

DataType[maxlen];}2.2线性表的顺序存储结构及实现(动态数组)

datalength0顺序表的实现——分配空间操作接口：booladdSpace(int

size=10)

算法描述：boolSeqList<DataType>

::addSpace(int

size){if(size<=0)returnfalse;tmpdata=data;maxlen+=size;data=new

DataType[maxlen];for(i=0;i<length;i++)data[i]=tmpdata[i];delete[]tmpdata;returntrue;}2.2线性表的顺序存储结构及实现(动态数组)顺序表的优缺点顺序表的优点：⑴无需为表示表中元素之间的逻辑关系而增加额外的存储空间；⑵随机存取：可以快速地存取表中任一位置的元素。

顺序表的缺点：⑴插入和删除操作需要移动大量元素；⑵表的容量难以确定，表的容量难以扩充；⑶造成存储空间的碎片。

2.2线性表的顺序存储结构及实现单链表：线性表的链接存储结构。存储思想：用一组任意的存储单元存放线性表的元素。2.3线性表的链接存储结构及实现单链表静态存储分配顺序表事先确定容量链表动态存储分配运行时分配空间连续不连续零散分布0200020803000325…………存储特点：逻辑次序和物理次序不一定相同。

2.元素之间的逻辑关系用指针表示。2.3线性表的链接存储结构及实现例：(a1,a2

,a3,a4)的存储示意图单链表a10200a20325a30300a4∧2.3线性表的链接存储结构及实现单链表0200020803000325…………a10200a20325a30300a4∧结点数据域指针域单链表是由若干结点构成的；单链表的结点只有一个指针域。data：存储数据元素next：存储指向后继结点的地址datanext单链表的结点结构：数据域指针域template<classDataType>structNode{DataTypedata;Node<DataType>*next;};

2.3线性表的链接存储结构及实现单链表datanext单链表的结点结构：如何申请一个结点？s=newNode<int>;template<classDataType>structNode{DataTypedata;Node<DataType>*next;};

2.3线性表的链接存储结构及实现单链表datanext单链表的结点结构：……sNodes=newNode<int>;2.3线性表的链接存储结构及实现单链表datanext……sNode如何引用数据元素？s->data;*s.data;data如何引用指针域？nexts->next;2.3线性表的链接存储结构及实现单链表0200020803000325…………a10200a20325a30300a4∧firsta1a2an∧非空表first=NULL空表重点在数据元素之间的逻辑关系的表示，所以，将实际存储地址抽象。什么是存储结构？2.3线性表的链接存储结构及实现单链表0200020803000325…………a10200a20325a30300a4∧firsta1a2an∧非空表first=NULL空表头指针：指向第一个结点的地址。尾标志：终端结点的指针域为空。2.3线性表的链接存储结构及实现单链表0200020803000325…………a10200a20325a30300a4∧firsta1a2an∧非空表first=NULL空表空表和非空表不统一，缺点？如何将空表与非空表统一？对第一个结点的操作与对其他结点的操作，使用语句可一致？头结点：在单链表的第以一个元素结点之前附设一个类型相同的结点，以便空表和非空表处理统一，并且可统一对任意位置的结点的操作实现。

2.3线性表的链接存储结构及实现单链表非空表firsta1a2an∧空表first∧template<classDataType>classLinkList{public:LinkList()；LinkList(DataTypea[],intn);~LinkList();intLength();DataTypeGet(inti);intLocate(DataTypex);voidInsert(inti,DataTypex);DataTypeDelete(inti);voidPrintList();private:Node<DataType>*first;};单链表类的声明2.3线性表的链接存储结构及实现单链表的实现——遍历操作操作接口：

voidPrintList();核心操作（关键操作）：工作指针后移。从头结点（或开始结点）出发，通过工作指针的反复后移而将整个单链表“审视”一遍的方法称为扫描（或遍历）。2.3线性表的链接存储结构及实现firsta1pa2pan∧aippp单链表的实现——遍历操作操作接口：

voidPrintList();2.3线性表的链接存储结构及实现template<classDataType>voidLinkList<DataType>::PrintList(){p=first->next;while(p!=NULL){cout<<p->data;p=p->next;}}p++能否完成指针后移？a1a2pp++p->next单链表的实现——按位查找操作接口：

DataTypeGet(inti);2.3线性表的链接存储结构及实现firsta1a2an∧aipp查找失败1.工作指针p初始化;累加器count初始化;2.重复执行下述操作，直到p为空：

2.1工作指针p后移;2.2count++;3.返回p->data的值；pcount=1pcount=2p查找成功count=itemplate<classDataType>DataTypeLinkList<DataType>::Get(inti){p=first->next;count=1;while(p!=NULL){if(count==i)returnp->data;p=p->next;count++;}throw“参数错误”;Node<DataType>tmp;returntmp.data;}2.3线性表的链接存储结构及实现单链表的实现——按位查找算法描述——C++描述template<classDataType>intLinkList<DataType>::Length(){p=first->next;count=0;while(p!=NULL){p=p->next;count++;}returncount;//注意count的初始化和返回值之间的关系}2.3线性表的链接存储结构及实现单链表的实现——按位查找——计算表长算法描述——C++描述template<classDataType>intLinkList<DataType>::Locate(DataTypex){p=first->next;count=1;

while(p!=NULL){if(p->data==x)returncount;//查找成功，返回序号p=p->next;count++;}return0;//退出循环表明查找失败}2.3线性表的链接存储结构及实现单链表的实现——按值查找算法描述——C++描述单链表的实现———插入操作接口：

voidInsert(inti,DataTypex);

2.3线性表的链接存储结构及实现如何实现结点ai-1、x和ai之间逻辑关系的变化？pxsfirsta1ai-1an∧ai算法描述：s=newNode<DataType>;s->data=x;s->next=p->next;p->next=s;注意分析边界情况——表头、表尾。

单链表的实现———插入2.3线性表的链接存储结构及实现firsta1an∧aipxs算法描述：s=newNode<DataType>;s->data=x;s->next=p->next;p->next=s;pxs∧由于单链表带头结点，表头、表中、表尾三种情况的操作语句一致。

算法描述——伪代码

1.工作指针p初始化；

2.查找第i-1个结点并使工作指针p指向该结点；

3.若查找不成功，则插入位置不合理，抛出插入位置异常；否则，3.1生成一个元素值为x的新结点s；

3.2将新结点s插入到结点p之后；2.3线性表的链接存储结构及实现单链表的实现———插入

template<classDataType>voidLinkList<DataType>::Insert(inti,DataTypex){p=first;count=0;//工作指针p应指向头结点

while(p!=NULL&&count<i-1)//查找第i–1个结点

{p=p->next;

count++;}if(p==NULL)throw"位置";//没有找到第i–1个结点

else{s=newNode;s->data=x;//申请一个结点ss->next=p->next;p->next=s;//结点s插入结点p之后

}}2.3线性表的链接存储结构及实现单链表的实现———插入基本语句？时间复杂度？单链表的实现———无参构造函数操作接口：LinkList()构造空表，即仅构造头结点。算法描述：first=newNode<DataType>;first->next=NULL;2.3线性表的链接存储结构及实现初始化first∧template<classDataType>LinkList<DataType>::LinkList(){ first=newNode<DataType>; first->next=NULL;}单链表的实现———构造函数操作接口：LinkList(DataTypea[],intn)头插法：将待插入结点插在头结点的后面。算法描述：first=newNode<DataType>;first->next=NULL;2.3线性表的链接存储结构及实现数组a3512243342初始化first∧单链表的实现———构造函数操作接口：LinkList(DataTypea[],intn)头插法：将待插入结点插在头结点的后面。2.3线性表的链接存储结构及实现数组a3512243342算法描述：s=newNode<DataType>;s->data=a[0];s->next=first->next;first->next=s;插入第一个元素结点first∧35s∧单链表的实现———构造函数操作接口：LinkList(DataTypea[],intn)头插法：将待插入结点插在头结点的后面。2.3线性表的链接存储结构及实现数组a3512243342算法描述：s=newNode<DataType>;s->d