数据结构课件

第1章绪论

1.2算法及其描述

1.1什么是数据结构1.3算法分析

1.4

数据结构+算法=程序1.1.1数据结构的定义1.1.2逻辑结构类型

1.1.3存储结构类型1.1.4数据类型和数据结构1.1什么是数据结构

数据：是所有能被输入到计算机中,且能被计算机处理的符号的集合。它是计算机操作的对象的总称,也是计算机处理信息的某种特定的符号表示形式。例如,200902班全体学生记录的集合为一个班的学生数据。

数据元素：是数据(集合)中的一个“个体”,是数据的基本单位。

1.1.1数据结构的定义

例如,200902班全班为学生数据,而其中的每个学生的记录是一个个数据元素)。

数据结构：是指数据(即全体数据元素)以及数据元素相互之间的关系。可以看作是相互之间存在着某种特定关系的数据元素的集合。

因此,可以把数据结构看成是带结构的数据元素的集合。

数据结构包括如下几个方面：

(1)数据元素之间的逻辑关系,即数据的逻辑结构。

(2)数据元素及其关系在计算机存储器中的存储方式,即数据的存储结构,也称为数据的物理结构。

(3)施加在该数据上的操作,即数据的运算。

例1.1有一个学生表如表1.1所示。这个表中的数据元素是学生记录,每个数据元素由四个数据项(即学号、姓别、性别和班号)组成。学号姓名性别班号1张斌男99018刘丽女990234李英女990120陈华男990212王奇男990126董强男99025王萍女9901表1.1学生表(学生数据)

记录1记录2记录3记录4..............记录n

该表中的记录顺序反映了数据元素之间的逻辑关系,我们用学号标识每个学生记录,这种逻辑关系可以表示为：

<1,8>,<8,34>,<34,20>,<20,12>,<12,26>,<26,5>

其中尖括号“<ai,ai+1>”表示元素ai和ai+1之间是相邻的,即ai在ai+1之前,ai+1在ai之后。学号姓名性别班号1张斌男99018刘丽女990234李英女990120陈华男990212王奇男990126董强男99025王萍女9901将每行(一个学生)抽象为一个结点：模型：n个元素的集合及其内在关系构成了一个数据结构（叫线性表）1834265一个数据结构

这些数据在计算机存储器中的存储方式就是存储结构。通常可以采用C/C++语言中的结构体数组和链表两种方式实现其存储结构。存放学生表的结构体数组Stud定义为：

structStudent

{ intno;/*存储学号*/ charname[8];/*存储姓名*/ charsex[2];/*存储性别*/ charclass[4];/*存储班号*/};StudentStud[7]={{1,“张斌”,“男”,“9901”},……,{5,"王萍","女","9901"}};

结构体数组Stud各元素在内存中顺序存放,即第i(1≤i≤6)个学生对应的元素Stud[i]存放在第i+1个学生对应的元素Stud[i+1]之前,Stud[i+1]正好在Stud[i]之后。1张斌…8刘丽…34李英…20陈华…12王奇…26董强…5王萍…Stud[0]Stud[1]Stud[2]Stud[3]Stud[4]Stud[5]Stud[6]

存放学生表的链表的结点类型StudType定义为：

typedefstructstudnode{ intno; /*存储学号*/ charname[8]; /*存储姓名*/ charsex[2]; /*存储性别*/ charclass[4]; /*存储班号*/ structstudnode*next; /*存储指向下一个学生的指针*/}StudType；StudType*head;head1张斌男99018刘丽女990234李英女990120陈华男990212王奇男990126董强男99025王萍女9901∧

学生表构成的链表如右图所示。其中的head为第一个数据元素的指针。

学生表构成的链表

对于“学生表”这种数据结构,可以进行一系列的运算,例如,增加一个学生记录、删除一个学生记录、查找性别为“女”的学生记录、查找班号为“9902”的学生记录等等。从前面介绍的两种存储结构看到,同样的运算,在不同的存储结构中,其实现过程是不同的。

为了更确切地描述一种数据结构,通常采用二元组表示：

B=(D,R)

其中,B是一种数据结构,它由数据元素的集合D和D上二元关系的集合R所组成。其中：

D={di|1≤i≤n,n≥0}R={rj|1≤j≤m,m≥0}

其中di表示集合D中的第i个结点或数据元素,n为D中结点的个数,特别地,若n=0,则D是一个空集,因而B也就无结构可言。如：D={d1,d2,d3,d4,d5,d6,d7}

rj表示集合R中的第j个二元关系(后面均简称关系),m为R中关系的个数,特别地,若m=0,则R是一个空集,表明集合D中的元结点间不存在任何关系,彼此是独立的。如：R={r1,r2}

有2种不同的关系r1={<d1,d2>,<d2,d3>,…}r2={<d4,d1>,<d4,d5>,…}

例如,采用二元组表示例1.1的学生表。

学生表中共有7个结点,依次用d1～d7表示,则对应的二元组表示为B=(D,R),其中：

D={d1,d2,d3,d4,d5,d6,d7}R={r}

r={<d1,d2>,<d2,d3>,<d3,d4>,<d4,d5>,<d5,d6>,<d6,d7>}学号姓名性别班号d11张斌男9901d28刘丽女9902d334李英女9901d420陈华男9902d512王奇男9901d626董强男9902d75王萍女9901又例如,有如下数据即一个矩阵：

对应的二元组表示为B=(D,R),其中：D={2,6,3,1,8,12,7,4,5,10,9,11}R={r1,r2}其中,r1表示行关系,r2表示列关系r1={<2,6>,<6,3>,<3,1>,<8,12>,<12,7>,<7,4>,<5,10>,<10,9>,<9,11>}r2={<2,8>,<8,5>,<6,12>,<12,10>,<3,7>,<7,9>,<1,4>,<4,11>}

一种数据结构还能够利用图形形象地表示出来,图形中的每个结点对应着一个数据元素,两结点之间的连线对应着关系中的一个序偶。上述“学生表”数据结构用下图的图形表示。学生表数据结构图示数据的逻辑结构主要有以下几类：(1)集合集合是指数据的各个数据元素之间没有关系。即关系是空集。1.1.2逻辑结构类型

(2)线性结构所谓线性结构,该结构中的结点之间存在一对一的关系。其特点是开始结点和终端结点都是惟一的,除了开始结点和终端结点以外,其余结点都有且仅有一个前驱结点,有且仅有一个后继结点。顺序表就是典型的线性结构。

(3)非线性结构

所谓非线性结构,该结构中的结点之间存在一对多或多对多的关系。它又可以细分为树形结构和图形结构两类。

所谓树形结构,该结构中的结点之间存在一对多的关系。其特点是每个结点最多只有一个前驱,但可以有多个后继,可以有多个终端结点。树形结构简称为树。所谓图形结构,该结构中的结点之间存在多对多的关系。其特点是每个结点的前驱和后继的个数都可以是任意的。因此,可能没有开始结点和终端结点,也可能有多个开始结点、多个终端结点。图形结构简称为图。例

人机对奕问题树结构……..……..…...…...…...…...将每个棋局都抽象成一个结点：棋局1棋局2棋局3棋局4棋局5棋局6棋局7棋局8棋局9棋局10整体：是一个数据结构，叫“树结构”运算：遍历整棵树，找出“赢”的路线；等用二元组表示的数据结构BB={D,R)D={棋局1，棋局2，棋局3，.......,棋局n}R={r}r={<棋局1,棋局2>，<棋局1,棋局3>，<棋局1,棋局4>，......,<棋局4,棋局7>，<棋局4,棋局8>，......}例：田径赛的时间安排问题:

设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。姓名项目1项目2项目3丁一ABE马二CD

张三CEF李四DFA王五BFAEBFDC比赛时间比赛项目1A，C2B，D3E4F1.设代号代表不同的项目跳高跳远标枪

ABC铅球100米200米

DEF2.用顶点代表比赛项目:不能同时进行比赛的项目之间连上一条边。安排四个单位时间进行比赛AEBFDC用二元组表示的数据结构BB={D,R)D={A,B,C,D,E,F}R={r}r={<A,B>，<A,E>，<B,E>，<C,D>,<C,E>,<E.F><C,F>，<D,F>，<A,D>,<A,F>,<B,F>}AEBFDCAEBFDC(1)顺序存储方法(2)链式存储方法

(3)索引存储方法(4)散列存储方法

1.1.3存储结构类型

（具体细节略…)1数据类型

在用高级程序语言编写的程序中,必须对程序中出现的每个变量、常量或表达式,明确说明它们所属的数据类型。不同类型的变量,其所能取的值的范围不同,所能进行的操作不同。数据类型是一组性质相同的值的集合和定义在此集合上的一组操作的总称。1.1.4数据类型和数据结构

如C/C++中的int就是整型数据类型。它是所有整数的集合(在16位计算机中为－32768到32767的全体整数)和相关的整数运算(如＋、－、＊、／等)。C++的各种数据类型介绍略……如：float,long,char,指针类型，数组类型，结构体类型，共用体类型。自定义数据类型名称：用typedeftypedef旧数据类型新数据类型名如：typedefcharElemType则：ElemType就是char如：typedefstructstud{intno;charname[10];intscore;}

student;

定义变量时：

可用

studentx,y;

2抽象数据类型抽象数据类型(AbstractDataType简写为ADT)指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算,而不考虑计算机的具体存储结构和运算的具体实现算法。

ADT抽象数据类型名{数据对象：D={一个个数据对象的描述}

数据关系：R={数据关系的描述}

基本运算：每一个基本运算的声明}ADT抽象对象类型名例如,抽象数据类型“复数”的定义：复数形式：e1+e2i或（e1，e2）ADTComplex{数据对象：

D={e1,e2|e1,e2均为实数}数据关系：

R={<e1,e2>|e1是复数的实数部分,e2是复数的虚数部分}基本运算：

AssignComplex(&Z,v1,v2)：构造复数Z,其实部和虚部分别赋以参数v1和v2的值。

DestroyComplex(&Z):复数Z被销毁。

GetReal(Z,&real):用real返回复数Z的实部值。

GetImag(Z,&Imag):用Imag返回复数Z的虚部值。

Add(z1,z2,&sum):用sum返回两个复数z1,z2的和值。}ADTComplex抽象数据类型=逻辑结构＋抽象运算抽象数据类型需要通过固有数据类型（也就是高级程序设计语言中已经实现的数据类型）如C++中的类来实现。数据类型=存储结构＋已实现的运算1.2算法及其描述

1.2.1什么是算法1.2.2算法描述1.2.1什么是算法

数据元素之间的关系有逻辑关系和物理关系,对应的操作有逻辑结构上的运算（抽象运算）和具体存储结构上的运算（抽象运算的实现）。通常把在具体存储结构上实现某个运算的步骤或过程称为算法。广义地说，算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每个指令表示计算机的一个或多个操作。算法的五个重要的特性

(1)有穷性:算法在执行有穷步骤之后结束，且每一步都可在有穷时间内完成。(2)确定性:算法的每条操作指令有确切的含义，读者理解时不会产生二义性；且在任何条件下，算法只有唯一的执行路径。

(3)可行性:每个算法中的操作都足够基本，可通过执行有限次已经实现的基本操作来实现。(4)有输入：有0个或多个外部输入作为算法加工的对象。若无外部输入，则算法的加工对象已被嵌入在算法中。

(5)有输出：有1个或多个输出，是算法进行信息加工的结果。

例考虑下列两段描述：(1)voidexam1(){intn;n＝2;while(n%2＝＝0)n＝n+2;cout<<n;}(1)算法是一个死循环,不能在有穷步后结束，违反了算法的有穷性特征。(2)voidexam2(){y=0;x=5/y;cout<<x<<“”<<y;}算法包含除零错误,停机了。这违反了算法的有穷性特征，不能在有穷时间内完成。getsum(intnum)//无输出的算法没有任何意义{

inti,sum=0;

for(i=1;i<=num;i++)

sum+=i;

}缺少：returnsum;或者：cout<<"sum=“<<sum;

1.2.2算法描述

本书中采用C/C++语言描述算法。

说明：C++语言中提供了一种引用运算符“&”,引用是个别名,当建立引用时,程序用另一个已定义的变量或对象(目标)的名字初始化它,从那时起,引用作为目标的别名而使用,对引用的改动实际就是对目标的改动。注意：TurboC不支持引用类型。返回

引用常用于函数形参中,采用引用型形参时,在函数调用时将形参的改变回传给实参,例如,有如下函数(其中的形参均为引用型形参)：

voidswap(int&x,int&y)/*形参前的“&”符号不是指针运算符*/{inttmp=x;x=y;y=tmp；

}

当用执行语句swap(a,b)时,a和b的值发生了交换。

反之，有以下函数swap1()

voidswap1(intx,inty){inttemp;temp=x;x=y;y=temp;}当用执行语句swap1(a,b)时,a和b的值不会发生了交换。

在C语言中，由于不支持引用类型，所以采用指针的方式来回传形参的值，需将上述函数改为：

intswap2(int*x,int*y){inttemp;temp=*x; /*将*x的值放在temp中*/ *x=*y; /*将*x所指的值改为*y*/*y=temp；/*将*y所指的值改为temp*/}

上述函数的调用改为swap2(&a,&b)，显然远不如采用引用方式简洁。所以本书后面很多算法都采用引用形参。

例编写一个算法,读入三个整数x,y和z的值,要求从大到小输出这三个数。

解：依次输入x,y和z这三个整数,通过比较交换后,使得x≥y≥z,然后输出x,y,z。在算法中应考虑对这三个元素作尽可能少的比较和移动,如下述算法在最坏的情况下只需进行3次比较和7次移动。voidDescending(){intx,y,z,temp;printf("输入x,y,z");//cout<<"输入x,y,z";

scanf("%d,%d,%d",&x,&y,&z);//cin>>x>>y>>z;if(x<y){temp=x;x=y;y=temp；/*交换x,y,使x>=y*/}if(y<z){temp=z;z=y;/*使temp>z*/if(x>=temp)y=temp；

else{y=x;x=temp;}}

printf("%d,%d,%d\n",x,y,z);//coutx<<y<<z<<“\n”;}另一写法：voidDescending(intx,inty,intz)//参数作为输入{if(x<y){temp=x;x=y;y=temp；/*交换x,y,使x>=y*/}if(y<z){temp=z;z=y;/*使temp>z*/if(x>=temp)y=temp；

else{y=x;x=temp;}}

printf("%d,%d,%d\n",x,y,z);}再一种写法：voidDescending(int&x,int&y,int&z)//

引用参数既作为输入，又作为输出{if(x<y){temp=x;x=y;y=temp；/*交换x,y,使x>=y*/}if(y<z){temp=z;z=y;/*使temp>z*/if(x>=temp)y=temp；

else{y=x;x=temp;}}}1.3算法分析

1.3.1算法设计的目标

1.3.2算法效率分析

1.3.3算法存储空间分析

设计的目标：•正确性。要求算法能正确地执行,实现预先规定的功能和性能要求。•可使用性。要求算法能方便地使用。也叫用户友好性。•可读性。算法应该易于理解。•健壮性。能对异常数据作出特殊处理，不会造成异常中断或死机。•高效率和低存储量需求。1.3.1算法设计的目标

衡量算法效率的方法：事后统计法：----执行程序，计算时间。事前分析估算法。

一个算法是由控制结构(顺序、分支和循环三种)和原操作(指固有数据类型的操作)构成的,则算法时间取决于两者的综合效果。1.3.2算法效率分析

例1.8求两个n阶方阵的加法#defineMAX20voidmatrixadd(intn,intA[][MAX],B[][MAX],C[][MAX]){inti,j;for(i=0;i<n;i++)循环结构1for(j=0;j<n;j++)循环结构2C[i][j]=A[i][j]+B[i][j];基本运算(原操作)}算法的执行时间=循环结构1的总时间+循环结构2总时间

+基本运算的总时间

算法执行时间大致为基本运算所需的时间与其执行次数(也称为频度)的乘积。为简便，取每个基本运算的时间=1执行时间=基本运算的执行次数例1.8求两个n阶方阵的加法#defineMAX20voidmatrixadd(intn,intA[][MAX],B[][MAX],C[][MAX]){inti,j;for(i=0;i<n;i++)n+1次

for(j=0;j<n;j++)n(n+1)次

C[i][j]=A[i][j]+B[i][j];n2次

}算法的执行时间T(n)=循环结构1的总频度+循环结构2总频度

+基本运算的总频度

=n+1+n(n+1)+n2=2n2+2n+1算法中基本运算执行次数T(n)是问题规模n的函数，T(n)的数量级是函数f(n),记作：

T(n)=O(f(n))读作“大O”,意指数量级将O(f(n))称为算法的时间复杂度例如,T(n)=3n2-5n+10000=O(n2)T(n)的数量级是n2,时间复杂度是O(n2)主要反映n值很大时算法的时间性能

记号“O”读作“大O”,它表示随问题规模n的增大算法执行时间T(n)的增长率和f(n)的增长率相同。“O”的形式定义为：若f(n)是正整数n的一个函数,则T(n)=O(f(n))表示存在一个正的常数M,使得当n≥n0时都满足：

|T(n)|≤M|f(n)|

也就是只求出T(n)的最高阶,忽略其低阶项和常系数,这样既可简化T(n)的计算,又能比较客观地反映出当n很大时,算法的时间性能。例如,T(n)=3n2-5n+10000=O(n2)例.求两个n阶方阵的乘积#definen100MATRIXMLT(floatA[][n],B[][n],C[][n]);{inti,j,k;语句频度

for(i=0;i<n;i++)n+1for(j=0;j<n;j++)n(n+1){C[i][j]=0;n2for(k=0;k<n;k++)n2(n+1)C[i][j]=C[i][j]+A[i][k]*B[k][j];n3}}语句频度之和：T(n)=2n3+3n2+2n+1该算法的时间复杂度T(n)=2n3+3n2+2n+1=O(n3)一般地，估算算法中频度最大的语句

该算法中的基本运算是三重循环中最深层的语句C[i][j]=C[i][j]+A[i][j]*B[i][j],分析它的频度,即：

T(n)==O(n3)

例1.8求两个n阶方阵的相加C=A+B的算法如下,分析其时间复杂度。

#defineMAX20/*定义最大的方阶*/

voidmatrixadd(intn,intA[MAX][MAX],intB[MAX][MAX],intC[MAX][MAX]){ inti,j; for(i=0;i<n;i++) for(j=0;j<n;j++) C[i][j]=A[i][j]+B[i][j];}

该算法中的基本运算是两重循环中最深层的语句C[i][j]=A[i][j]+B[i][j],分析它的频度,即：

T(n)==O(n2)例分析以下算法的时间复杂度。

intfun(intn){inti,j,k,s;s=0;for(i=0;i<=n;i++)for(j=0;j<=i;j++) for(k=0;k<=j;k++)s++;return(s);}

解：该算法的基本操作是语句s++,其频度：

T(n)==O(n3)则该算法的时间复杂度为O(n3)。例1.9算法：在数组a[0]....a[n-1]中查找值kvoidfun(inta[],intn,intk){inti;i=0;while(i<n&&a[i]!=k)i++;returni;｝例1.10递归算法：voidfun(inta[],intn,intk){inti;if(k==n-1){for(i=0;i<n;i++)cout<<a[i]<<endl;}else{for(i=k;i<n;i++)a[i]=a[i]+i*i;fun(a,n,k+1);//递归调用

}｝调用函数：fun(a,n,0),求其时间复杂度。设fun(a,n,k)的执行时间为T1(n,k)fun(a,n,0)的时间复杂度T(n)=T1(n,0)=O(n2)

一个没有循环的算法的基本运算次数与问题规模n无关,记作O(1),也称作常数阶。一个只有一重循环的算法的基本运算次数与问题规模n的增长呈线性增大关系,记作O(n),也称线性阶。其余常用的还有平方阶O(n2)、立方阶O(n3)、对数阶O(log2n)、指数阶O(2n)等。

各种不同数量级对应的值存在着如下关系：

O(1)<O(log2n)<O(n)<O(n*log2n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)当n取得很大时，指数阶算法和多项式时间算法在所需时间上非常悬殊。多项式时间算法解决的问题叫P问题；指数阶算法解决的问题叫NP问题。世界难题：NP问题=P问题若有人能将现有NP问题中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。？例：多项式时间算法与指数时间算法的执行时间比较。假设算法P1的时间复杂度为T1(n)=n2，算法P2的时间复杂度为T2(n)=2n,计算机的运算速度是1微秒（即每秒1000000次运算）。

nP1运算次数P1运算时间P2运算次数P2运算时间101000.0001秒10240.001024秒204000.0004秒10485761.049秒309000.0009秒107374802417.9分钟4016000.0016秒1099511627776305.42小时6036000.0036秒115292150460684697636558.9年例：多项式时间算法与指数时间算法的执行时间比较。假设算法P1的时间复杂度为T1(n)=n2，算法P2的时间复杂度为T2(n)=n!,计算机的运算速度是每秒4亿亿次运算---天河二号超级计算机）。

nP1运算次数P1运算时间P2运算次数P2运算时间101003628800204002.43×101860.8秒309002.65×10322亿1千万年

空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度,一般也作为问题规模n的函数,以数量级形式给出,记作：

S(n)=O(g(n))

若所需额外空间相对于输入数据量来说是常数,则称此算法为原地工作。若所需存储量依赖于特定的输入,则通常按最坏情况考虑。1.3.3算法存储空间分析

返回

例分析下例的空间复杂度。#defineMAX20/*定义最大的方阶*/

voidmatrixadd(intn,intA[MAX][MAX],intB[MAX][MAX],intC[MAX][MAX]){ inti,j; for(i=0;i<n;i++) for(j=0;j<n;j++) C[i][j]=A[i][j]+B[i][j];}

解：由于这个算法中临时变量的个数与问题规模n无关,所以空间复杂度均为O(1)。1.4数据结构+算法=程序N.Wirth提出：数据结构+算法=程序程序设计的本质是：对要处理的问题选择好的数据结构，在此结构上施加好的算法。N.Wirth（1934年～），瑞士计算机科学家，1960年获加利福尼亚大学伯克利分校博士学位。曾任斯坦福大学、苏黎世联邦理工学院教授。发明多种计算机语言（包括Pascal、Modula和Oberon等），并为软件工程领域作出过开拓性的贡献。于1980年获得计算机科学界最高奖－图灵奖（/wiki/Turing_Award）。数据是程序要计算处理的“原料”。将数据按某种要求组成一种数据结构，对设计出简明、高效的程序是大有益处的。沃思指出：程序就是在数据的某些特定的表示方法和结构的基础上，对抽象算法的具体表述，所以说程序离不开数据结构。1.4.1程序和数据结构1.4.2算法和程序由程序设计语言描述的算法就是计算机程序。对一个求解问题而言，算法就是解题的方法，没有算法，程序就成了无本之末，无源之水。有了算法，将它表示成程序是不困难的。算法是程序的核心。算法在程序设计，也可以说软件开发，甚至可以说在整个计算机科学中的地位都是极其重要的。1.4.3算法和数据结构求解的问题可以通过抽象数据类型描述，它由数据的逻辑结构和抽象运算两部分组成。一种数据的逻辑结构可以映射成多种存储结构，抽象运算在不同的存储结构上实现可以对应多种算法，在同一种存储结构上实现也可能有多种算法，通过算法的时间复杂度和空间复杂度等分析，可以得到好的算法。例电话公司的电话号码查询服务。方案1：数据结构是线性表。TelName13100001张三13600002李四………………………………通过姓名查询号码的算法采用顺序查询算法，时间=n/2方案2：采用树结构查询算法的时间T(n)≈log2n当n=1000000时，方案1的关键字比较次数=n/2=500000

方案2的关键字比较次数=log21000000≈2013611111111刘三...................................................................................问题描述：有若干学生数据（学生数小于50），每个学生数据包含学号（每个学生学号是唯一的，但学生记录不一定按学号顺序存放）、姓名、班号和若干门课程成绩（每个学生所选课程数目可能不等，但最多不超过6门）。要求：设计一个程序输出每个学生的学号、姓名和平均分以及每门课程（课程编号从1～6）的平均分。一个典型示例

设计方案1：将学生的全部数据项放在一个表中，一个学生的全部数据对应一条记录。由于课程最多可选6门，对应的成绩项也应有6个。对应的数据结构如下：

structstud

{

intno; //学号

charname[10]; //姓名

intbno; //班号

intdeg1; //课程1分数

intdeg2; //课程2分数

intdeg3; //课程3分数

intdeg4; //课程4分数

intdeg5; //课程5分数

intdeg6; //课程6分数

};设计方案1的特点：

存储空间：中（若学生没有选该课程，对应空间仍存在）算法时间：少算法简洁性差：算法完全依赖数据结构存储结构1nonamebnodeg1deg2deg3deg4deg5deg61张斌99017882-19285838刘丽990265-172-18079………………………

设计方案2：将学生的全部数据项放在一个表中，但一个学生的一门课程成绩对应一条记录。这样成绩项只需要一个，为了区分不同课程成绩，需增加一个课程编号项。对应的数据结构如下：

structstud

{

intno; //学号

charname[10]; //姓名

intbno; //班号

intcno; //课程编号

intdeg; //课程分数

};存储结构2nonamebnocnodeg1张斌99011781张斌99012821张斌99014921张斌99015851张斌99016838刘丽99021658刘丽99023728刘丽99025808刘丽9902679……………设计方案2的特点：

存储空间：大算法时间：多算法简洁性：好

设计方案3：将学生的学号、姓名和班号放在一个表中，将成绩数据放在另一个表中，两者通过学号关联。前者一个学生对应一个记录，后者一门课程成绩对应一条记录。对应的数据结构如下：

structstud1

{

intno; //学号

charname[10]; //姓名

intbno; //班号

};

structstud2

{

intno; //学号

intcno; //课程编号

intdeg; //分数

};nonamebno1张斌99018刘丽9902………关联存储结构3nocnodeg117812821492158516838165837285808679………设计方案3的特点：

存储空间：少。算法时间：中。算法简洁性：好。最佳方案综合分析的结果本章小结

本章介绍了数据结构的基本概念,主要学习要点如下：

(1)数据结构的定义,数据结构包含的逻辑结构、存储结构和运算三方面的相互关系。

(2)各种逻辑结构即线性结构、树形结构和图形结构之间的差别。返回2.1线性表及其逻辑结构

2.1.1线性表的定义2.1.2线性表的抽象数据类型描述2.1.1线性表的定义

线性表是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度,用n表示,n≥0。当n=0时,表示线性表是一个空表,即表中不包含任何元素。设序列中第i(i表示位序)个元素为ai(1≤i≤n)。线性表的一般表示为:(a1,a2,…ai,ai+1,…,an)

其中a1为第一个元素,又称做表头元素,a2为第二个元素,an为最后一个元素,又称做表尾元素。例如,在线性表

(1,4,3,2,8,10)中,1为表头元素,10为表尾元素。2.1.2线性表的抽象数据类型描述

线性表的基本运算如下:(1)初始化线性表InitList(&L):构造一个空的线性表L。(2)销毁线性表DestroyList(&L):释放线性表L占用的内存空间。

(3)判线性表是否为空表ListEmpty(L):若L为空表,则返回真,否则返回假。

(4)求线性表的长度ListLength(L):返回L中元素个数。

(5)输出线性表DispList(L):当线性表L不为空时,顺序显示L中各结点的值域。

(6)求线性表L中指定位置的某个数据元素

GetElem(L,i,&e):用e返回L中第i个元素的值

(1≤i≤ListLength(L))。

(7)定位查找LocateElem(L,e):

返回L中第1个值域与e相等的位序。若这样的元素不存在,则返回值为0。

(8)插入数据元素ListInsert(&L,i,e):

在L的第i(1≤i≤ListLength(L)+1)个元素之前插入新的元素e,L的长度增1。

(9)删除数据元素ListDelete(&L,i,&e):

删除L的第i(1≤i≤ListLength(L))个元素,并用e返回其值,L的长度减1。定义线性表的抽象数据类型ADTList{数据对象：D={a1,a2,a3,…,an}

数据关系：R1={<a1,a2>,<a2,a3>,…,<an-1,an>}

基本运算：

InitList(&L);DestroyList(&L);……..ListDelete(&L,i,&e)}

例2.2假设有两个集合A和B分别用两个线性表LA和LB表示,即线性表中的数据元素即为集合中的成员。编写一个算法求一个新的集合C=A∪B,即将两个集合的并集放在线性表LC中。

解:本算法思想是:先初始化线性表LC,将LA的所有元素复制到LC中,然后扫描线性表LB,若LB的当前元素不在线性表LA中,则将其插入到LC中。算法如下:voidunionList(ListLA,ListLB,List&LC){intlena,lenc,i;ElemTypee;

InitList(LC);for(i=1;i<=ListLength(LA);i++) /*将LA的所有元素插入到Lc中*/{ GetElem(LA,i,e);

ListInsert(LC,i,e);}lena=ListLength(LA);/*求线性表的长度*/lenb=ListLength(LB);

for(i=1;i<=lenb;i++) {

GetElem(LB,i,e); /*取LB中第i个数据元素赋给e*/ if(!LocateElem(LA,e))

ListInsert(LC,++lena,e); /*LA中不存在和e相同者,则插入到LC中*/ }}

由于LocateElem(LA,e)运算的时间复杂度为O(ListLength(LA)),所以本算法的时间复杂度为:O(ListLength(LA)*ListLength(LB))。2.2线性表的顺序存储结构2.2.1线性表的顺序存储结构—顺序表2.2.2顺序表基本运算的实现2.2.1线性表的顺序存储结构—顺序表

线性表的顺序存储结构就是:把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中。这样,线性表中第一个元素的存储位置就是指定的存储位置,第i+1个元素(1≤i≤n-1)的存储位置紧接在第i个元素的存储位置的后面。

假定线性表的元素类型为ElemType,则每个元素所占用存储空间大小(即字节数)为sizeof(ElemType),整个线性表所占用存储空间的大小为:

n*sizeof(ElemType)其中,n表示线性表的长度。顺序表示意图

在定义一个线性表的顺序存储类型时,需要定义一个数组来存储线线表中的所有元素和定义一个整型变量来存储线性表的长度。

假定数组用data[MaxSize]表示,长度整型变量用length表示,并采用结构体类型表示,则元素类型为通用类型标识符ElemType的线性表的顺序存储类型可描述如下:#defineMaxSize50typedefstruct{ ElemTypedata[MaxSize]; intlength;}SqList;/*顺序表类型*/

其中,data成员存放元素,length成员存放线性表的实际长度。或者：structSqList{ElemTypedata[MaxSize];intlength;};例如：LA=(23,75,41,38,54,62,17)顺序表内存示意图：SqListQ;Q就是顺序表23754138546217data[0]lengthdata[1023]data[6]7Q第1个数据元素：Q.data[0]第i个数据元素：Q.data[i-1]表长：Q.length例如：LA=(23,75,41,38,54,62,17)用指针变量指向顺序表：SqList*L;第1个数据元素：(*L).data[0]或L->data[0]第i个数据元素：(*L).data[i-1]或L->data[i-1]表长：(*L).length或L->length23754138546217data[0]lengthdata[1023]data[6]7L→

2.2.2顺序表基本运算的实现

一旦采用顺序表存储结构,我们就可以用C/C++语言实现线性表的各种基本运算。为了方便,假设ElemType为char类型,使用如下自定义类型语句:typedefcharElemType;typedefstruct{ElemTypedata[MaxSize];intlength;}SqList;1.建立顺序表将含有n个元素的数组的每个元素依次放入到顺序表中。voidCreateList(SqList*&L,ElemTypea[],intn){inti;L=newSqList;//或L=(SqList*)malloc(sizeof(SqList));for(i=0;i<n;i++)L->data[i]=a[i];L->length=n;}本算法的时间复杂度为O(n)。(1)初始化线性表InitList(L)

该运算的结果是构造一个空的线性表L。实际上只需将length成员设置为0即可。

voidInitList(SqList*&L)//引用型指针

{L=(SqList*)malloc(sizeof(SqList));//或L=newSqList;

/*分配存放线性表的空间*/L->length=0;}本算法的时间复杂度为O(1)。2.顺序表基本运算算法(2)销毁线性表DestroyList(L)

该运算的结果是释放线性表L占用的内存空间。

voidDestroyList(SqList*&L){free(L);//或deleteL;}

本算法的时间复杂度为O(1)。(3)判定是否为空表ListEmpty(L)

该运算返回一个值表示L是否为空表。若L为空表,则返回1,否则返回0。

intListEmpty(SqList*L){ return(L->length==0);}本算法的时间复杂度为O(1)。(4)求线性表的长度ListLength(L)

该运算返回顺序表L的长度。实际上只需返回length成员的值即可。

intListLength(SqList*L){ return(L->length);}

本算法的时间复杂度为O(1)。(5)输出线性表DispList(L)

该运算当线性表L不为空时,顺序显示L中各元素的值。

voidDispList(SqList*L){ inti; if(ListEmpty(L))return; for(i=0;i<L->length;i++) printf("%c",L->data[i]);//或cout<<L->data[i]; printf(“\n”);//或cout<<endl;}

时间复杂度：O(L->length)或O(n)(6)求某个数据元素值GetElem(L,i,e)

该运算返回L中第i(1≤i≤ListLength(L))个元素的值,存放在e中。

boolGetElem(SqList*L,inti,ElemType&e){ if(i<1||i>L->length)returnfalse; e=L->data[i-1]; returntrue;}

本算法的时间复杂度为O(1)。(7)按元素值查找LocateElem(L,e)

该运算顺序查找第1个值域与e相等的元素的位序。若这样的元素不存在,则返回值为0。

intLocateElem(SqList*L,ElemTypee){ inti=0; while(i<L->length&&L->data[i]!=e)i++; if(i>=L->length) return0; elsereturni+1;}

本算法中基本运算为while循环中的i++语句,故时间复杂度与e的值有关:若e=L->data[0],循环0次；若e=L->data[1],循环1次；若e=L->data[2],循环2次；……若e=L->data[n-1],循环n-1次；平均次数：O(n)或O(L->length)(8)插入数据元素ListInsert(L,i,e)

该运算在顺序表L的第i个位置(1≤i≤ListLength(L)+1)上插入新的元素e。思路：如果i值不正确,则显示相应错误信息；否则将顺序表原来第i个元素及以后元素均后移一个位置,腾出一个空位置插入新元素,顺序表长度增1。a1a2

…ai-1ai

…ana1a2

…ai-1

data[0]data[L->length-1]第i个结点：data[i-1]需要移动的结点:(共n-(i-1)个）

ai~anL->data[i-1]

~L->data[L->length-1]

//结点右移

for(j=L->length;j>i;j--)L->data[j]=L->data[j-1];L->data[i-1]=e;

L->length++;

ean…ai

boolListInsert(SqList*&L,inti,ElemTypee){intj;if(i<1||i>L->length+1) returnfalse;i--;/*将顺序表逻辑位序转化为data下标即物理位序*/for(j=L->length;j>i;j--)L->data[j]=L->data[j-1];/*将data[i]及后面元素后移一个位置*/L->data[i]=e;L->length++;/*顺序表长度增1*/returntrue;}

对于本算法来说,元素移动的次数不仅与表长L.length=n有关,而且与插入位置i有关:当i=n+1时,移动次数为0；当i=1时,移动次数为n,达到最大值。在线性表L中共有n+1个可以插入元素的地方。假设pi(=)是在第i个位置上插入一个元素的概率,则在长度为n的线性表中插入一个元素时所需移动元素的平均次数为:

因此插入算法的平均时间复杂度为O(n)。(9)删除数据元素ListDelete(L,i,e)

该运算删除顺序表L的第i个元素(1≤i≤ListLength(L))。思路：如果i值不正确,则显示相应错误信息；否则将线性表第i个元素以后元素均向前移动一个位置,这样覆盖了原来的第i个元素,达到删除该元素的目的,最后顺序表长度减1。boolListDelete(SqList*&L,inti,ElemType&e){intj;if(i<1||i>L->length) returnfalse;i--; /*将顺序表逻辑位序转化为data下标即物理位序*/e=L->data[i];for(j=i;j<L->length-1;j++)L->data[j]=L->data[j+1];/*将data[i]之后的元素前移一个位置*/L->length--; /*顺序表长度减1*/returntrue;}

对于本算法来说,元素移动的次数也与表长n和删除元素的位置i有关:当i=n时,移动次数为0；当i=1时,移动次数为n-1。在线性表sq中共有n个元素可以被删除。假设pi(pi=)是删除第i个位置上元素的概率,则在长度为n的线性表中删除一个元素时所需移动元素的平均次数为:

因此删除算法的平均时间复杂度为O(n)。例设计一个算法,将两个元素有序(从小到大)的顺序表合并成一个有序顺序表。

思路:将两个顺序表进行二路归并。例如:

顺序表p:(1,3,5)←i扫描p

顺序表q:(2,4,10,20)←j扫描q

归并到顺序表r中←k记录r中元素个数

r:(1,2,3,4,5,10,20)data[0][1][2][3][4][5][6][7]Length

表p1353data[0][1][2][3][4][5][6][7]Length

表q2410204data[0][1][2][3][4][5][6][7]Length

表r0ijkdata[0][1][2][3][4][5][6][7]Length

表p1353data[0][1][2][3][4][5][6][7]Length

表q2410204data[0][1][2][3][4][5][6][7]Length

表r10ijkikdata[0][1][2][3][4][5][6][7]Length

表p1353data[0][1][2][3][4][5][6][7]Length

表q2410204data[0][1][2][3][4][5][6][7]Lengt