最新数据结构演讲(五篇)

在日常学习、工作或生活中，大家总少不了接触作文或者范文吧，通过文章可以把我们那些零零散散的思想，聚集在一块。范文书写有哪些要求呢？我们怎样才能写好一篇范文呢？下面我给大家整理了一些优秀范文，希望能够帮助到大家，我们一起来看一看吧。

数据结构演讲篇一

【实验目的】

学习掌握线性表的顺序存储结构、链式存储结构的设计与操作。对顺序表建立、插入、删除的基本操作，对单链表建立、插入、删除的基本操作算法。

【实验内容】

1.顺序表的实践

1)建立4个元素的顺序表s=sqlist[]={1，2，3，4，5}，实现顺序表建立的基本操作。

2)在sqlist []={1，2，3，4，5}的元素4和5之间插入一个元素9，实现顺序表插入的基本操作。

3)在sqlist []={1，2，3，4，9，5}中删除指定位置（i=5）上的元素9，实现顺序表的删除的基本操作。2.单链表的实践

3.1)建立一个包括头结点和4个结点的（5，4，2，1）的单链表，实现单链表建立的基本操作。

2)将该单链表的所有元素显示出来。

3)在已建好的单链表中的指定位置（i=3）插入一个结点3，实现单链表插入的基本操作。

4)在一个包括头结点和5个结点的（5，4，3，2，1）的单链表的指定位置（如i=2）删除一个结点，实现单链表删除的基本操作。5)实现单链表的求表长操作。

【实验步骤】

1.打开vc++。

2.建立工程：点file->new，选project标签，在列表中选win32 console application，再在右边的框里为工程起好名字，选好路径，点ok->finish。至此工程建立完毕。

3.创建源文件或头文件：点file->new，选file标签，在列表里选c++ source file。给文件起好名字，选好路径，点ok。至此一个源文件就被添加到了你刚创建的工程之中。

4．写好代码

5．编译－＞链接－＞调试

【实验心得】

线性是我们学习数据结构中，碰到的第一个数据结构。学习线性表的重点掌握顺序表和单链表的各种算法和时间性能分析。线性表右两种存储方式即顺序存储结构和链式存储结构。通过学习我知道了对线性表进行建立、插入、删除，同时单链表也是进行建立、插入、删除。而对于顺序表的插入删除运算，其平均时间复杂度均为0（n）.通过这次的学习，掌握的太熟练，主要是课本上的知识点没有彻底的理解，回去我会多看书，理解重要的概念。总之，这次实验我找到了自己的不足之处，以后会努力的。

实验二：栈的表示与实现及栈的应用

【实验目的】

（1）掌握栈的顺序存储结构及其基本操作的实现。（2）掌握栈后进先出的特点，并利用其特性在解决实际问题中的应用。（3）掌握用递归算法来解决一些问题。【实验内容】

1.编写程序，对于输入的任意一个非负十进制整数，输出与其等值的八进制数。

2.编写递归程序，实现n！的求解。3.编写递归程序，实现以下函数的求解。

n,n0,1fib(n) fib(n1)fib(n2),n1

4.编写程序，实现hanoi塔问题。【实验步骤】 1.打开vc++。

2.建立工程：点file->new，选project标签，在列表中选win32 console application，再在右边的框里为工程起好名字，选好路径，点ok->finish。至此工程建立完毕。

3.创建源文件或头文件：点file->new，选file标签，在列表里选c++ source file。给文件起好名字，选好路径，点ok。至此一个源文件就被添加到了你刚创建的工程之中。

4．写好代码

5．编译－＞链接－＞调试

【实验心得】

通过这次的学习我掌握了栈这种抽象数据类型的特点，并能在相应的应用任务中正确选用它；总的来说，栈是操作受限的线性表，是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶（top），相应地，表头端称为栈底（botton）；栈又称为后进先出（last in first out）的线性表,简称lifo结构，因为它的修改是按后进先出的原则进行的。

加上这个实验，我已经学了线性表（顺序表，单链表）和栈，知道它们都是线性表，而且对以后的学习有很大的作用，可以说这是学习以后知识的总要基础。

实验三：二叉树的建立及遍历

【实验目的】

（1）掌握利用先序序列建立二叉树的二叉链表的过程。（2）掌握二叉树的先序、中序和后序遍历算法。【实验内容】

1.编写程序，实现二叉树的建立，并实现先序、中序和后序遍历。如：输入先序序列abc###de###，则建立如下图所示的二叉树。

并显示其先序序列为：abcde 中序序列为：cbaed 后序序列为：cbeda 【实验步骤】 1.打开vc++。

2.建立工程：点file->new，选project标签，在列表中选win32 console application，再在右边的框里为工程起好名字，选好路径，点ok->finish。至此工程建立完毕。

3.创建源文件或头文件：点file->new，选file标签，在列表里选c++ source file。给文件起好名字，选好路径，点ok。至此一个源文件就被添加到了你刚创建的工程之中。

4．写好代码

5．编译－＞链接－＞调试

【实验心得】

这次试验是关于二叉树的常见操作，主要是二叉树的建立和遍历，在这次实验中我按先序方式建立二叉树的，而遍历方式则相对要多一些，有递归的先序、中序、后序遍历，和非递归的先序、中序、后序遍历，此外还有层次遍历.二叉树高度和叶子个数的计算和遍历相差不大，只是加些判断条件，总体来说，本次试验不太好做，期间出现了很多逻辑错误，变量初始化的问题等，不过经过仔细排查最后都一一解决了。

实验四：查找与排序

【实验目的】

（1）掌握折半查找算法的实现。（2）掌握冒泡排序算法的实现。【实验内容】

1.编写折半查找程序，对以下数据查找37所在的位置。5，13，19，21，37，56，64，75，80，88，92 2.编写冒泡排序程序，对以下数据进行排序。49，38，65，97，76，13，27，49 【实验步骤】 1.打开vc++。

2.建立工程：点file->new，选project标签，在列表中选win32 console application，再在右边的框里为工程起好名字，选好路径，点ok->finish。至此工程建立完毕。

3.创建源文件或头文件：点file->new，选file标签，在列表里选c++ source file。给文件起好名字，选好路径，点ok。至此一个源文件就被添加到了你刚创建的工程之中。

4．写好代码

5．编译－＞链接－＞调试

（1）查找算法的代码如下所示： #include “stdio.h” #include “malloc.h” #define overflow-1 #define ok 1 #define maxnum 100 #define n 10 typedef int elemtype;typedef int status;typedef struct {

elemtype *elem;

int length;}sstable;status initlist(sstable &st){ int i,n;

=

(elemtype*)

malloc(elemtype));

if(!)return(overflow);

printf(“输入元素个数和各元素的值:”);

scanf(“%dn”,&n);

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

(maxnum*sizeof

scanf(“%d”,&[i]);}

= n;

return ok;} int seq_search(sstable st,elemtype key){

int i;

[0]=key;

for(i=;[i]!=key;--i);

return i;} int binarysearch(sstable st,elemtype key){

int mid,low,high,i=1;

low=1;

high=;

while(low<=high)

{

mid=(low+high)/2;

if([mid]==key)

return mid;

else if(key

high=mid-1;

else

}

return 0;} void main(){ sstable st;initlist(st);

elemtype key;int n;printf(“ key= ”);

scanf(“%d”,&key);

printf(“nn”);

/*printf(“after seqsearch:: ”);

n=seq_search(st,key);

printf(“position is in %d nn”,n);*/

printf(“after binary search::”);

n=binarysearch(st,key);

low=mid+1;if(n)printf(“position is in %d nn”,n);else

} 实验结果如下所示：

（2）排序算法的代码如下所示： #include “stdio.h” #include “malloc.h” #define overflow-1 #define ok 1 #define maxnum 100 #define n 10 typedef int elemtype;typedef int status;typedef struct {

elemtype *elem;

int length;}sstable;status initlist(sstable &st)printf(“not in nn”);{ int i,n;

(elemtype));

if(!)return(overflow);

printf(“输入元素个数和各元素的值:”);

scanf(“%dn”,&n);

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

scanf(“%d”,&[i]);}

= n;

return ok;} void sort(sstable st){

int i,j,t;

for(i=1;i

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

if([i]>[j]){ t=[i];=

(elemtype*)

malloc

(maxnum*sizeof

}

} [i]=[j];[j]=t;void display(sstable st){ int i;

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

printf(“%d

”,[i]);}

} void main(){

sstable st;initlist(st);int n;printf(“before sort::n”);display(st);sort(st);printf(“nafter sort::n”);display(st);} 实验结果如下所示：

【实验心得】

通过这次实验,我明白了程序里的折半查找和冒泡查找.其实排序可以有很多种，但是其目的应该都是为了能够在海量的数据里迅速查找到你要的数据信息，折半查找是种比较快的方式，但前提是要是有 序的排序才可以。对于有序表，查找时先取表中间位置的记录关键字和所给关键字进行比较，若相等，则查找成功；如果给定值比该记录关键字大，则在后半部分继续进行折半查找；否则在前半部分进行折半查找，直到查找范围为空而查不到为止。折半查找的过程实际上死先确定待查找元素所在的区域，然后逐步缩小区域，直到查找成功或失败为止。算法中需要用到三个变量，low表示区域下界，high表示上界，中间位置mid=(low+high)/2.而冒泡查找则是从小到大的排序.

数据结构演讲篇二

云淡风清 http:///

第1章 数据结构概述

1.1概述

以下为某市部分院校的交通地图情况，要求找出从出发点到目的地之间的最短路径及其长度。

对于此问题，如果手工去做，速度慢(特别地，现实中实际地图信息要比此例复杂许多)，还容易出错，此时可借助于计算机完成。

计算机进行此类信息的处理时，涉及到两个问题：一是现实当中的信息在计算机中如何表示，二是如何对信息进行处理。

信息的表示和组织又直接关系到处理信息的程序的效率。随着应用问题不断复杂化，导致信息量剧增与信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，必须分析待处理问题中的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。

1.1.1编写解决实际问题的程序的一般流程

如何通过编写程序，以比手工更为高效精确的方式解决实际问题呢？一般流程如下：

1、由具体问题抽象出一个适当的数学模型；

2、分析问题所涉及的数据量大小及数据之间的关系；

3、确定如何在计算机中存储数据及体现数据之间的关系？

4、确定处理问题时需要对数据作何种运算？

5、确定算法并编写程序；

5、分析所编写的程序的性能是否良好？若性能不够好则重复以上步骤。

云淡风清 http:/// 上面所列举的问题基本上由数据结构这门课程来回答。

《数据结构》是计算机科学中的一门综合性专业基础课，是介于数学、计算机硬件、计算机软件三者之间的一门核心课程，不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。

1.1.2数据结构的例子

1、电话号码查询系统

设有一个电话号码薄，它记录了n个人的名字和其相应的电话号码。要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。

姓名

电话号码

陈伟海 *** 李四锋 ***。。

这是一种典型的线性结构。

2、磁盘目录文件系统

磁盘根目录下有很多子目录及文件，每个子目录里又可以包含多个子目录及文件，但每个子目录只有一个父目录，依此类推。

。。

本问题中各目录从上到小形成了一种一对多的关系，是一种典型的树形结构。

云淡风清 http:///

3、交通网络图

下图表明了若干个城市之间的联系：

从图中可看出，一个地方到另外一个地方可以有多条路径，是一种典型的网状结构，数据与数据成多对多的关系。

4、排序问题

对100000个整数进行降序排序。冒泡法程序： #include

#include

#include

#define n 100000 void main(){ int i,j;int a[n+1];srand(time(null));for(i=1;i<=n;i++)

printf(“%8d”,a[i]);system(“pause”);for(j=1;j

for(i=n;i>j;i--)

if(a[i]>a[i-1])

{

a[0]=a[i];

a[i]=a[i-1];

a[i-1]=a[0];

} printf(“n按新次序输出：n”);

云淡风清 http:/// for(i=1;i<=n;i++)

printf(“%8d”,a[i]);printf(“n”);} 快速排序程序： #include

#include

#include

#define n 100000

{

//将划分子集的元素(此处选中间元素)移动到最左边

temp=a[left];

a[left]=a[(left+right)/2];

a[(left+right)/2]=a[left];

last=left;//用last记录比关键字小的元素的最右位置

for(j=left+1;j<=right;j++)//划分子集

if(a[j]>a[left])

{

temp=a[last];

a[last]=a[j];

a[j]=temp;

last++;

}

//对形成的新子集递归进行快速排序

quick_sort(a,left,last-1);

quick_sort(a,last+1,right);} } void main(){ int i;int a[n+1];srand(time(null));for(i=1;i<=n;i++)

a[i]=rand();printf(“n按原序输出：n”);for(i=1;i<=n;i++)

printf(“%8d”,a[i]);system(“pause”);

云淡风清 http:/// quick_sort(a,1,n);printf(“n按新次序输出：n”);for(i=1;i<=n;i++)

printf(“%8d”,a[i]);printf(“n”);} 运行可知，两者速度差异非常明显，主要是排序所花的时间差别很大。可看出，同样的问题，采用不同方法进行处理，有可能呈现出非常大的性能方面的差异。

还可以找到许多其它例子，如图书馆的书目检索系统自动化问题，教师资料档案管理系统，多叉路口交通灯的管理问题等。

1.2基本概念和术语 1.2.1数据(data)：

是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。

1.2.2数据元素(data element)：

是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。一个数据元素可由若干个数据项(data item)组成。数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。

1.2.3数据对象(data object)：

是性质相同的数据元素的集合，是数据的一个子集，其中的数据元素可以是有限的，也可以是无限的。如整数集合：n={0，±1，±2，…}，是无限集，而字符集合：c={ˊaˊ，bˊ，…，ˊzˊ}则为有限集。

1.2.4数据的逻辑结构：

指对数据元素之间逻辑关系的描述。

数据元素之间的关系可以是一种或多种。

数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的关系，这种自然或人为定义的“关系”称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。其要点有两个方面：一是元素本身，二是元素之间的关系。数据元素之间的逻辑结构有四种基本类型，如下：

云淡风清 http:///

①集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。②线性结构：结构中相邻的数据元素之间存在一对一的关系。③树型结构：结构中相邻的数据元素之间存在一对多的关系。

④图状结构或网状结构：结构中相邻的数据元素之间存在多对多的关系。数据结构数学形式的定义是一个二元组： datastructure=(d，s)其中：d是数据元素的有限集，s是d上关系的有限集。例：设数据逻辑结构b=(k，r)，其中： k={k1, k2, …, k9}

r={

，

，

，

，

，

，

，

，

，

，

} 画出这逻辑结构的图示，并确定哪些是起点，哪些是终点。

又称存储结构，指数据结构在计算机内存中的存储方式。

数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的存储。元素之间的关系在计算机中有两种不同的表示方法：顺序表示和非顺序表示。由此得出两种不同的存储结构：顺序存储结构和链式存储结构。

顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构(关系)。链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针(pointer)，用该指针来表示数据元素之间的逻辑结构(关系)。

例：设有数据集合a={3.0,2.3,5.0,-8.5,11.0}，两种不同的存储结构。顺序结构：数据元素存放的地址是连续的；

链式结构：数据元素存放的地址是否连续没有要求。

数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。

在c语言中，用一维数组表示顺序存储结构；通过结构体类型实现的链表来表示链式存储结构。

1.2.6数据结构(data structure)：

按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机存贮器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。

1.2.7数据结构的三个组成部分：

逻辑结构：数据元素之间逻辑关系的描述：d_s=(d，s)。

存储结构：数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。数据操作：对数据要进行的运算。

本课程中将要讨论的三种逻辑结构及其采用的存储结构如下图所示。

云淡风清 http:///

逻辑结构与所采用的存储结构

数据逻辑结构层次关系图

1.2.8数据类型(data type)：

指的是一个值的集合和定义在该值集上的一组操作的总称。

数据类型是和数据结构密切相关的一个概念。在c语言中数据类型有：基本类型(如int，float，double，char等)和构造类型(如数组，结构体，共用体等)。

数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。

1.3数据结构的运算

数据结构的主要运算包括： ⑴建立(create)一个数据结构； ⑵消除(destroy)一个数据结构；

⑶从一个数据结构中删除(delete)一个数据元素； ⑷把一个数据元素插入(insert)到一个数据结构中； ⑸对一个数据结构进行访问(access)；

⑹对一个数据结构(中的数据元素)进行修改(modify)； ⑺对一个数据结构进行排序(sort)； ⑻对一个数据结构进行查找(search)。

以上只列举了一些常见运算，实际应用当中可能会遇到许多其它运算。

云淡风清 http:/// 1.4抽象数据类型(abstract data type)1.4.1抽象数据类型简介：

简称adt，是指一个数学模型以及定义在该模型上的一组操作。adt的定义仅是一组逻辑特性描述，与其在计算机内的表示和实现无关。因此，不论adt的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。

adt的形式化定义是三元组：adt=(d，s，p)其中：d是数据对象，s是d上的关系集，p是对d的基本操作集。说明：

⑴adt和数据类型实质上是一个概念，其区别是：adt的范畴更广,它不再局限于系统已定义并实现的数据类型，还包括用户自己定义的数据类型。

⑵adt的定义是由一个值域和定义在该值域上的一组操作组成。包括定义，表示和实现三个部分。⑶adt的最重要的特点是抽象和信息隐蔽。抽象的本质就是抽取反映问题本质的东西，忽略非本质的细节，使所设计的结构更具有一般性，可以解决一类问题。信息隐蔽就是对用户隐藏数据存储和操作实现的细节，使用者了解抽象操作或界面服务，通过界面中的服务来访问这些数据。

adt不考虑物理结构以及算法的具体实现。

例：整数的数学概念和对整数所能进行的运算构成一个adt，c语言中的变量类型int就是对这个抽象数据类型的一种物理实现。

1.4.2adt的一般定义形式：

adt的一般定义形式是： adt<抽象数据类型名> { 数据对象：<数据对象的定义> 数据关系：<数据关系的定义> 基本操作：<基本操作的定义> }adt<抽象数据类型名> 其中数据对象和数据关系的定义用伪码描述。基本操作的定义是： <基本操作名>(<参数表>)初始条件：<初始条件描述> 操作结果：<操作结果描述> 说明：

初始条件：描述操作执行之前数据结构和参数应满足的条件；若不满足，则操作失败，返回相应的出错信息。

操作结果：描述操作正常完成之后，数据结构的变化状况和应返回的结果。

1.5算法(algorithm)1.5.1算法基本概念：

算法是对特定问题求解方法(步骤)的一种描述，是指令的有限序列，其中每一条指令表示一个或

云淡风清 http:/// 多个操作。

1.5.2算法的基本特征：

算法具有以下五个特性

①有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。

②确定性：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。

③可行性：一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。

④输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。

⑤输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。

1.5.3算法的基本描述方法：

一个算法可以用多种方法描述，主要有：使用自然语言描述；使用形式语言描述；使用计算机程序设计语言描述等。

1.5.4算法与程序的异同比较：

算法和程序是两个不同的概念。一个计算机程序是对一个算法使用某种程序设计语言的具体实现。算法必须可终止意味着不是所有的计算机程序都是算法。

1.5.5评价算法好坏的几个标准：

评价一个好的算法有以下几个标准

①正确性(correctness)：算法应满足具体问题的需求。

②可读性(readability)：算法应易于供人阅读和交流。可读性好的算法有助于对算法的理解和修改。

③健壮性(robustness)：算法应具有容错处理。当输入非法或错误数据时，算法应能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。

④通用性(generality)：算法应具有一般性，即算法的处理结果对于一般的数据集合都成立。⑤效率与存储容量需求：效率指的是算法执行的时间；存储容量需求指算法执行过程中所需要的最大存储空间。一般地，这两者与问题的规模有关。

1.6算法效率的度量

解决同一个问题的算法可能有多种，如何选择一个效率高的算法呢？应该来讲，与算法效率相关的因素有很多，如下：

云淡风清 http:///

1、算法选用何种策略；

2、问题的规模；

3、程序设计的语言；

4、编译程序所产生的机器代码的质量；

5、内存的大小；

6、外存的大小；

7、机器执行指令的速度；

8、其它。

而确定算法效率的方法通常有两种：

1.6.1事后统计：

先实现算法，然后运行程序，测算其时间和空间的消耗。缺点：

1、必须先依据算法编制程序并运行程序，耗费人力物力；

2、依赖软硬件环境，容易掩盖算法本身的优劣。由于算法的运行与计算机的软硬件等环境因素有关，不容易发现算法本身的优劣。同样的算法用不同的编译器编译出的目标代码数量不同，完成算法所需的时间也不同；若计算机的存储空间较小，算法运行时间也就会延长；

3、没有实际价值。测试花费不少时间但并没有解决现实中的实际问题。

1.6.2事前分析：

仅仅通过比较算法本身的复杂性来评价算法的优劣，不考虑其它的软硬件因素，通常考查算法所用的时间和所需的存储空间。

算法复杂性的度量可以分为时间复杂度和空间复杂度。

1.6.3算法的时间复杂度(time complexity)

1、算法的时间复杂度

算法的时间复杂度用于度量一个算法所用的时间。

算法所用的时间主要包括程序编译时间和运行时间。由于一个算法一旦编译成功可以多次运行，因此可以忽略编译时间，只讨论算法的运行时间。

算法的运行时间依赖于加、减、乘、除、等基本的运算以及参加运算的数据量的大小，另外，与计算机硬件和操作环境等也有关系。要想准确地估算时间是不可行的，而影响算法时间最为主要的因素是问题的规模，即输入量的多少。同等条件下，问题的规模越大，算法所花费的时间也就越长。例如，求1+2+3+„+n的算法，即n个整数的累加求和，这个问题的规模为n。因此，运行算法所需的时间t是问题规模n的函数，记作t(n)。

同等条件下，相同或类似的基本操作在真正程序运行过程中所花费的时间也差不多，这样，如果两个不同算法中一个所含基本操作多而另一个所含基本操作少，则包含基本操作少的算法其花费时间也就较少。因此，通常用算法中基本语句的执行次数来作为度量算法速度快慢的依据，而这种度量时间复杂度的方法得出的不是时间量，而是一种增长趋势的度量，即当问题规模n增大时，t(n)也随之变大。换言之，当问题规模充分大时，算法中基本语句的执行次数为在渐进意义下的阶，称为算法的渐进时间复杂度，简称时间复杂度，通常用大o记号表示。用数学语言通常描述为：若当且仅当存在正整数n和n0，对于任意n≥n0，都有t(n)≤c×f(n)，则称该算法的渐进时间复杂度为t(n)=o(f(n))。

一般地，常用最内层循环内的语句中的原操作的执行频度(重复执行的次数)来表示时间复杂度。

2、时间复杂度分析举例： 例：两个n阶方阵的乘法。

云淡风清 http:/// 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];} 分析：由于是一个三重循环，每个循环从1到n，则总次数为： n×n×n=n3，时间复杂度为t(n)=o(n3)。

例： { ++x;s=0;} 分析：将x自增看成是基本操作，则语句频度为1，即时间复杂度为o(1)。

如果将s=0也看成是基本操作，则语句频度为2，其时间复杂度仍为o(1)，即常量阶。只要t(n)不是问题规模n的函数，而是一个常数，它的时间复杂度则均为o(1)。例：以下程序段： for(i=1;i<=n;++i){ ++x;s+=x;} 分析：基本语句的语句频度为：n，其时间复杂度为：o(n)，即为线性阶。例：以下程序段： for(i=1;i<=n;++i)for(j=1;j<=n;++j){

++x;

s+=x;} 分析：基本语句的语句频度为：n2，其时间复杂度为：o(n2)，即为平方阶。

定理：若t(n)=amnm+am-1nm-1+„+a1n+a0是一个m次多项式，则t(n)=o(nm)，即复杂度表达式只取一个n趋向于无穷大时的同阶无穷小表达式即可。

通过对算法复杂度的分析，总结出这样一条结论，在计算任何算法的复杂度时，可以忽略所有低次幂和最高次幂的系数，这样可以简化算法分析，并使注意力集中在增长率上。

从本质上来讲，此种策略也就是只考虑对算法复杂度影响最大的因素而忽略次要因素。例：以下程序段：

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

for(j=2;j<=i-1;++j)

{

++x;

a[i,j]=x;

}

云淡风清 http:/// 分析：基本语句的语句频度为： 1+2+3+„+n-2 =(1+n-2)×(n-2)/2

=(n-1)×(n-2)/2 =(n2-3n+2)/2 按上述定理，时间复杂度为o(n2)，即此算法的时间复杂度为平方阶。

一个算法时间复杂度为o(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数(即零次多项式)来界定。而一个时间为o(n2)的算法则由一个二次多项式来界定。

3、常见表示时间复杂度的阶： o(1)：常量时间阶 o(n)：线性时间阶 o(㏒n)：对数时间阶

o(n㏒n)：线性对数时间阶 o(nk)：k≥2，k次方时间阶

4、常见时间复杂度大小关系分析：

以下六种计算算法时间复杂度的多项式是最常用的，其大小关系通常为： o(1)

当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。

有的情况下，算法中基本操作重复执行的次数还随输入数据集的不同而不同。例：素数的判断算法。

void prime(int n)//n是一个正整数 { int i=2;while((n%i)!=0 && i*1.0

i++;if(i*1.0>sqrt(n))

printf(“&d 是一个素数n”,n);else

printf(“&d 不是一个素数n”,n);} 此例中执行频率最高的语句为i++;，此语句最少执行0次，最多执行sqrt(n)次，对于不同的n，执行次数不确定。

对于此类算法，如果输入数据不同，则算法运行时间也不同，因此要全面分析一个算法，需要考虑算法在最好、最坏、平均情况下的时间消耗。由于最好情况出现的概率太小，因此不具代表性，但是，当最好情况出现的概率大时，应该分析最好情况；虽然最坏情况出现的概率也太小，不具代表性，但是分析最坏情况能够让人们知道算法的运行时间最坏能到什么程度，这一点在实时系统中很重要；分析平均情况是比较普遍的，特别是同一个算法要处理不同的输入时，通常假定输入的数据是等概率分布的。

例：冒泡排序法。

void bubble_sort(int a[],int n)

云淡风清 http:/// { int temp;change=false;for(i=n-1;change=ture;i>1 && change;--i)

for(j=0;j

if(a[j]>a[j+1])

{

temp=a[j];

a[j]=a[j+1];

a[j+1]=temp;

change=ture;

} } 最好情况：0次

最坏情况：1+2+3+⋯+n-1=n(n-1)/2平均时间复杂度为：o(n2)1.6.4算法的空间复杂度(space complexity)

1、算法的空间复杂度

算法的空间复杂度是指在算法的执行过程中需要的辅助空间数量。辅助空间数量指的不是程序指令、常数、指针等所需要的存储空间，也不是输入数据所占用的存储空间，辅助空间是除算法本身和输入输出数据所占据的空间外，算法临时开辟的存储空间。算法的空间复杂度分析方法同算法的时间复杂度相似，设s(n)是算法的空间复杂度，通常可以表示为：

s(n)=o(f(n))其中：n为问题的规模(或大小)。该存储空间一般包括三个方面： 指令常数变量所占用的存储空间； 输入数据所占用的存储空间； 辅助(存储)空间。

一般地，算法的空间复杂度指的是辅助空间。如：

一维数组a[n]：空间复杂度o(n)二维数组a[n][m]：空间复杂度o(n*m)例：数组a中有10000个数，要求将所有数据逆置(即顺序倒过来存放)。为达到逆置目的，有以下两种方案： 方案一：

int a[10000],b[10000],i;for(i=0;i<10000;i++)b[10000-i-1]=a[i];for(i=0;i<10000;i++)a[i]=a[b];方案二：

int a[10000],t,i;for(i=0;i<10000/2;i++)

云淡风清 http:/// { t=a[i];a[i]=a[10000-i-1];a[10000-i-1]=t;} 很明显，方案二中的辅助空间数量为1，而方案一中的辅助空间数量为10000，方案二的空间复杂度优于方案一。

在算法的时间复杂度和空间复杂度中，我们更注重算法的时间性能。因此，在对算法性能的分析当中，通常均主要针对算法时间性能进行分析。

1.6.5学习算法的原因

讲述了这么多关于算法的基础知识，究竟为什么要学习算法呢？

首先，算法无处不在。算法不仅出现在数学和计算机程序中，更普遍地出现在我们的生活中，在生活中做什么事情都要有一定的顺序，然而不同的顺序带来的效率和成果可能都会不同，只有学好了算法，才能让生活更有趣、更有效率。

其次，算法是程序的灵魂。学习计算机编程，必须要掌握好其灵魂，否则，写出来的程序就像是没有灵魂的躯体。

再次，算法是一种思想。掌握了这种思想，能够拓展思维，使思维变得清晰、更具逻辑性，在生活以及编程上的很多问题，也就更易解决。

最后，算法的乐趣。学习算法不仅仅是为了让它帮助人们更有效地解决各种问题，算法本身的趣味性很强，当通过烦琐的方法解决了一个问题后会感觉到有些疲惫，但是面对同一个问题，如若学会使用算法，更简单有效地解决了这个问题，会发现很有成就感，算法的速度、思想会让人觉得很奇妙。每一个奇妙的算法都是智慧的结晶。

学习算法的理由成千上万，不同的人可能出于不同的目的去学习算法，希望大家能够通过对课程的学习对算法有进一步的理解。

习题一

1、简要回答术语：数据，数据元素，数据结构，数据类型。

2、数据的逻辑结构？数据的物理结构？逻辑结构与物理结构的区别和联系是什么？

3、数据结构的主要运算包括哪些？

4、算法分析的目的是什么？算法分析的主要方面是什么？

云淡风清 http:///

第2章 线性表

下表为某电台提供给听众的若干首英文歌曲名及相关点播情况统计信息：

由于实际的歌曲库可能很大，手工管理效率低，不方便，现请设计一个软件系统实现对此类歌曲库的管理。

分析：

此例中相邻的两首歌之间是一种一对一的关系，属于典型的线性结构，可按线性结构进行组织及管理。

2.1线性结构与线性表 2.1.1线性结构

如果一个数据元素序列满足：

⑴除第一个和最后一个数据元素外，每个数据元素只有一个直接前驱数据元素和一个直接后继数据元素；

⑵第一个数据元素没有前驱数据元素； ⑶最后一个数据元素没有后继数据元素。则称这样的数据结构为线性结构。

线性表、栈、队列、串和数组都属于线性结构。如下图：

云淡风清 http:/// 2.1.2线性表

线性表(linear list)是一种最简单、最常用的线性结构，是一种可以在任意位置进行插入和删除数据元素操作的、由n(n≥0)个相同类型数据元素a1，a2，„，an组成的线性结构。在这种结构中：

⑴存在一个唯一的被称为“第一个”的数据元素； ⑵存在一个唯一的被称为“最后一个”的数据元素； ⑶除第一个元素外，每个元素均有唯一一个直接前驱； ⑷除最后一个元素外，每个元素均有唯一一个直接后继。线性表中的数据元素的个数n称为线性表的长度。当n=0时，称为空表。空线性表用符号()表示。

当n>0时，将非空的线性表记作：(a1，a2，„an)，其中符号ai(1≤i≤n)表示第i个抽象数据元素。

a1称为线性表的第一个(头)结点，an称为线性表的最后一个(尾)结点。a1，a2，„ai-1都是ai(2≤i≤n)的前驱，其中ai-1是ai的直接前驱；

ai+1，ai+2，„an都是ai(1≤i ≤n-1)的后继，其中ai+1是ai的直接后继。

线性结构是最常用、最简单的数据结构，而线性表是一种典型的线性结构，其基本特点是可以在任意位置进行插入和删除等操作，且数据元素是有限的。

线性表可以用顺序存储结构或链式存储结构实现。用顺序存储结构实现的线性表称为顺序表，用链式存储结构实现的线性表称为链表。链表主要有单链表、循环单链表和循环双链表三种。顺序表和链表各有优缺点，并且优缺点刚好相反，在实际应用中要根据情况选择对操作及性能有利的存储结构。

线性表中的数据元素ai所代表的具体含义随实际应用领域的不同而不同，在线性表的定义中，只不过是一个抽象的表示符号。

◆线性表中的结点可以是单值元素(每个元素只有一个数据项)。例1：26个英文字母组成的字母表：(a，b，c、„、z)例2：某校从1978年到1983年各种型号的计算机拥有量的变化情况：(6，17，28，50，92，188)例3：一副扑克的点数：(2，3，4，„，j，q，k，a)◆线性表中的结点可以是记录型元素，每个元素含有多个数据项，每个项称为结点的一个域。每个元素有一个可以唯一标识每个结点的数据项组，称为关键字。

例4：某校2001级同学的基本情况：{(‘2001414101’，‘张里户’，‘男’，06/24/1983)，(‘2001414102’，‘张化司’，‘男’，08/12/1984)„，(‘2001414102’，‘李利辣’，‘女’，08/12/1984)} ◆若线性表中的结点是按值(或按关键字值)由小到大(或由大到小)排列的，称线性表是有序的。◆线性表是一种相当灵活的数据结构，其长度可根据需要增长或缩短。

◆对线性表的基本操作如下(实际应用中要根据需要选择相应操作或者添加未列出的操作)： ⑴建立空表l ⑵返回表l的长度，即表中元素个数 ⑶取线性表l中位置i处的元素(1≤i≤n)⑷取i的直接前驱元素 ⑸取i的直接后继元素

⑹查询元素x在l中的逻辑位置

⑺在线性表l的位置i处插入元素x，原位置元素后移一个位置 ⑻从线性表l中删除位置i处的元素 ⑼判断线性表是否为空 ⑽清空已存在的线性表 ⑾遍历所有元素

云淡风清 http:/// ⑿根据所给关键字查询元素并返回其详细信息 ⒀修改表中元素

⒁对所有元素按条件排序

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

adt list { 数据对象：d = { ai | ai∈elemset, i=1,2,„,n, n≥0 } 数据关系：r = { | ai-1, ai∈d, i=2,3,„,n } 基本操作： initlist(&l)初始条件：无

操作结果：构造一个空的线性表l； listlength(l)初始条件：线性表l已存在；

操作结果：返回线性表中的元素个数； getelem(l,i,e)初始条件：线性表l已存在，1≤i≤listlength(l)； 操作结果：用e返回l中第i个数据元素的值； listinsert(l,i,e)初始条件：线性表l已存在，1≤i≤listlength(l)+1，线性表未满；

操作结果：在线性表l中的第i个位置插入元素e，原来位置及以后的元素都后移； listlocate(l,e)初始条件：线性表l已存在；

操作结果：返回元素e在l中的逻辑位置，不存在则返回0； listdelete(l,i)初始条件：线性表l已存在，1≤i≤listlength(l)； 操作结果：从表l中删除位置i处的元素； listclear(l)初始条件：线性表l已存在； 操作结果：清空已存在的表； listtraverse(l)初始条件：线性表l已存在； 操作结果：遍历输出所有元素； listupdate(l,i,e)初始条件：线性表l已存在,1≤i≤listlength(l)； 操作结果：将线性表l中第i个位置的值置为e； listsort(l)初始条件：线性表l已存在；

操作结果：按一定条件对所有元素重新排序； listdestroy(l)初始条件：线性表l已存在； 操作结果：释放线性表空间； …

云淡风清 http:/// } adt list 2.2线性表的顺序存储 2.2.1线性表的顺序存储结构

顺序存储：把线性表的结点按逻辑顺序依次存入地址连续的一组存储单元里。用这种方法存储的线性表简称顺序表。

顺序存储的线性表的特点：

◆线性表的逻辑顺序与物理顺序一致；

◆数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现的。设有非空的线性表：(a1，a2，„an)。顺序存储如下图所示。

在具体的机器环境下，设线性表的每个元素需占用len个存储单元，以所占的第一个单元的存储地址作为数据元素的存储位置，则线性表中第i+1个数据元素的存储位置loc(ai+1)和第i个数据元素的存储位置loc(ai)之间满足下列关系：

loc(ai+1)=loc(ai)+l 线性表的第i个数据元素ai的存储位置为： loc(ai)=loc(a1)+(i-1)*len 高级语言中同一个数组的各个元素占用连续存储单元，具有随机存取(指存取同一数组各元素的时间开销相同，不受所处位置的限制)的特性，故而在高级语言中通常用数组来存储顺序表。除了用数组来存储线性表的元素之外，顺序表还应该表示线性表的长度属性以方便某些操作，所以用结构体类型来定义顺序表类型。

#include

#include

#define ok #define error

typedef int elemtype;//元素类型，可根据实际需要更改 typedef struct sqlist { elemtype *elem_array;//线性表存储空间地址

int length;//线性表长度 } sqlist;注意：c语言中数组的下标值是从0开始，第i个元素的下标值是i-1。

2.2.2顺序表的基本操作

顺序存储结构中，很容易实现线性表的一些操作：初始化、赋值、查找、修改、插入、删除、求长度等。

以下将对几种主要的操作进行讨论。#include

#define ok #define error

typedef int elemtype;//元素类型，可根据实际需要更改 typedef struct sqlist { elemtype elem_array[max_size];//线性表存储空间地址

int length;//线性表长度 } sqlist;/*

1、初始化

构造一个空的线性表 */ status init_sqlist(sqlist *l){ l->length=0;return ok;} /*

2、测长度

返回线性表中的元素个数 */ int length_sqlist(sqlist *l){ return l->length;} /*

3、取元素

用e返回l中第i个数据元素的值，1≤i≤listlength(l)*/ status get_sqlist(sqlist *l,int i,elemtype *e){ if((i>=1)&&(i<=l->length)){

*e=l->elem_array[i-1];//i位置对应的元素下标为i-1

return ok;} else

return error;}

云淡风清 http:/// /*

4、顺序线性表的插入

在线性表l中的第i个位置插入元素e，原来位置及以后的元素都后移。要求1≤i≤listlength(l)+1，线性表未满。实现步骤：

(1)将线性表l中的第i个至第n个结点后移一个位置。(2)将结点e插入到结点ai-1之后。

(3)线性表长度加1。*/ status insert_sqlist(sqlist *l,int i,elemtype e){ int j;if((i<1)||(i>l->length+1))//位置错误

return error;else

if(l->length>=max_size)//线性表上溢

//实际开发中达到空间上限时可用remalloc()函数重新分配空间，扩大空间容量

return error;

else

{

//i-1位置以后的所有结点后移

for(j=l->length-1;j>=i-1;--j)

l->elem_array[j+1]=l->elem_array[j];

l->elem_array[i-1]=e;//在i-1位置插入结点

l->length++;//线性表长度增1

return ok;

} } /* 时间复杂度分析：

在线性表l中的第i个位置插入新结点，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。

设在线性表l中的第i个位置插入结点的概率为pi，不失一般性，设各个位置插入是等概率，则pi=1/(n+1)，而插入时移动结点的次数为n-i+1。

总的平均移动次数：einsert=∑pi*(n-i+1)(1≤i≤n)计算得：einsert=n/2。

即在顺序表上做插入运算，平均要移动表上一半结点，当表长n较大时，算法的效率相当低。因此算法的平均时间复杂度为o(n)。

*/ /*

5、线性表元素位置查询

返回元素e在l中的逻辑位置，不存在则返回0

云淡风清 http:/// */ int locate_sqlist(sqlist *l,elemtype e){ int i,found=0;//found用于表示是否找到，0：未找到 1：找到

i=0;//从第一个开始查询

while((i

length)&&(found==0))

found=1;

else

i++;if(found==1)

return i+1;//返回逻辑位置编号

else

return 0;//未找到，返回0 } /*

6、删除指定位置元素 在线性表：

l=(a1，„ai-1，ai，ai+1，„，an)中删除结点ai(1≦i≦n)，使其成为线性表： l=(a1，„ai-1，ai+1，„，an)要求1≤i≤listlength(l)，线性表未空。实现步骤：

(1)将线性表l中的第i+1个至第n个结点依此向前移动一个位置。(2)线性表长度减1。*/ status delete_sqlist(sqlist *l,int i){ int k;if(l->length==0)//线性表空

{

printf(“线性表l为空!n”);

return error;} else

if(i<1||i>l->length)//指定位置不合适

{

printf(“要删除的数据元素不存在!n”);

return error;

}

else

{

//i位置以后的所有结点前移

for(k=i;k

length;k++)

云淡风清 http:///

l->length--;//线性表长度减1

return(ok);

} } /* 时间复杂度分析：

删除线性表l中的第i个元素，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。

设在线性表l中删除第i个元素的概率为pi，不失一般性，设删除各个位置是等概率，则pi=1/n，而删除时移动结点的次数为n-i。

则总的平均移动次数：edelete=∑pi*(n-i)

(1≤i≤n)计算得：edelete=(n-1)/2 即在顺序表上做删除运算，平均要移动表上一半结点，当表长n较大时，算法的效率相当低，因此算法的平均时间复杂度为o(n)。

*/ /*

7、清空 */ status clear_sqlist(sqlist *l){ l->length=0;return ok;} /*

8、遍历 以输出为例 */ status traverse_sqlist(sqlist *l){ int i;printf(“共有%d个元素，以下为具体内容：n”,l->length);for(i=0;i

length;i++)

9、修改

将线性表l中第i个位置的值置为e。要求线性表l已存在且1≤i≤listlength(l)。*/ status update_sqlist(sqlist *l,int i,elemtype e){ if((i<1)||(i>l->length))//位置错误

云淡风清 http:///

return error;else {

l->elem_array[i-1]=e;//放置新数据

return ok;} } /*

10、排序

按要求对线性表中元素排序。*/ status sort_sqlist(sqlist *l){ int i,j;elemtype temp;for(i=1;i<=l->length-1;i++)

for(j=0;j<=l->length-i-1;j++)

{

if(l->elem_array[j]

elem_array[j+1])

temp=l->elem_array[j];

l->elem_array[j]=l->elem_array[j+1];

l->elem_array[j+1]=temp;

}

} return ok;} /* 主函数 */ void main(){ int xz=1,i;sqlist l;elemtype e;while(xz!=0){

printf(“

1、初始化n

2、测长度n

3、取元素n

4、插入n

5、查询n

6、删除n

7、清空n

8、遍历n

9、修改n10、排序n 0、结束n请选择：”);

scanf(“%d”,&xz);

switch(xz)

{

case 1:

if(init_sqlist(&l)==ok)

云淡风清 http:///

printf(“初始化成功！n”);else

printf(“初始化未成功！n”);break;case 2: printf(“线性表长度为：%dn”,length_sqlist(&l));break;case 3: printf(“请输入要取元素的位置：”);scanf(“%d”,&i);if(get_sqlist(&l,i,&e)==ok)

printf(“指定位置上的元素为：%dn”,e);else

printf(“error！n”);break;case 4: printf(“请输入要插入的位置：”);scanf(“%d”,&i);printf(“请输入要插入的元素内容：n”);scanf(“%d”,&e);if(insert_sqlist(&l,i,e)==ok)

printf(“插入成功n”);else

printf(“error！n”);break;case 5: printf(“请输入要查询的元素内容：”);scanf(“%d”,&e);printf(“此元素逻辑位置为：%d(0表示未找到)。n”,locate_sqlist(&l,e));break;case 6: printf(“请输入要删除元素的位置：”);scanf(“%d”,&i);if(delete_sqlist(&l,i)==ok)

printf(“删除成功n”);else

printf(“error！n”);break;case 7: clear_sqlist(&l);break;case 8: traverse_sqlist(&l);break;

云淡风清 http:///

case 9:

printf(“请输入要修改的元素位置：”);

scanf(“%d”,&i);

printf(“请输入元素的新内容：n”);

scanf(“%d”,&e);

if(update_sqlist(&l,i,e)==ok)

printf(“修改成功n”);

else

printf(“error！n”);

break;

case 10:

sort_sqlist(&l);

printf(“排序完成！n”);

break;

case 0:

printf(“谢谢使用，再见！n”);

break;

default:

printf(“输入错误！n”);

break;

} } } 需要说明的是，本例没有实现空间的动态分配，若要实现动态分配，可参照第三章“栈的动态顺序存储结构”的做法。

2.2.3顺序存储线性表的特点

优点：表中任意一个结点的存取很方便，可以进行随机存取，处于不同位置上的结点的存取时间从理论上来说相同，也能进行插入和删除操作。

缺点：

(1)插入和删除不方便。为保持连续存放，操作中需要移动大量元素。

(2)会造成空间的浪费以及不易扩充。所占空间通常情况下大小固定，处理长度变化较大的线性表时，分配空间大小不够，会造成溢出；分配空间太大，会造成浪费。

2.3线性表的链式存储 2.3.1线性表的链式存储结构

链式存储：用一组任意(即不必要连续)的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表。

链表中结点所占用的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的，链表中结点的逻辑顺序和物理顺序不一定相同。

为了正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其直接后继结点的

云淡风清 http:/// 地址(或位置)，称为指针(pointer)或链(link)，这两部分组成了链表中的结点结构，如下图所示。

data：数据域，存放结点的值。

next：指针域，存放结点的直接后继的地址。

链表通过每个结点的指针域将线性表的n个结点按其逻辑次序链接在一起。每一个结点只包含一个指针域的链表，称为单链表。

为操作方便，总是在链表的第一个结点之前附设一个头指针变量head指向第一个结点。头结点的数据域可以不存储任何信息(或存放链表长度等辅助信息)，此时通常称为带头结点的单链表。当然，也可以让头结点的数据域存放有效数据，此时称为不带头结点的单链表。相对而言，带头结点的单链表浪费了一个结点的数据域，但会给编程带来一定方便。

带头结点的单链表其基本结构如下：

说明：

(1)整个链表由若干个结点组成，一个结点占用一个内存块，而每个结点又分为两大部分：数据域和指针域，其中数据域存放用户数据，指针域用于存放后一个结点的地址，通过指针域将逻辑上前后相邻的结点连接起来，这样，通过前一个结点指针域中存放的地址就可以找到后一个结点。可看出，每个结点的指针域实际上充当了指针变量的角色，只要结点数可变，则意味着指针变量数也可变，而事实上结点所对应的这些内存块完全可以多次动态分配，这也就意味着指针域(相当于指针变量)的个数可以根据需要动态调整，这就解决了前述的“程序中变量个数固定，但问题本身所需变量个数不定”的矛盾。

(2)设置一个头指针变量指向首结点，在带头结点的单链表中，此结点不存放有效数据。(3)末尾结点的指针域设置为空“null”表示链表的结束，相当于字符串中的''。

(4)在没有用户数据的情况下，此链表只有一个结点，此结点既是首结点，又是末结点，结点的指针域为“null”，此时表示链表为逻辑“空”，也就是说，链表的初始状态应该如下图所示。

单链表是由表头唯一确定的，因此单链表可以用头指针的名字来命名。例

1、线性表l=(bat，cat，eat，fat，hat)其带头结点的单链表的逻辑状态和物理存储方式如下图所示。

云淡风清 http:///

1、结点的描述与实现

c语言中用带指针的结构体类型来描述 typedef int elemtype;typedef struct lnode { elemtype

data;//数据域，保存结点的值

struct

lnode *next;//指针域，保存后继结点地址 }lnode;

//结点的类型

2、结点空间分配及回收的实现

结点存储空间是通过动态内存分配和释放来实现的，即需要时分配，不需要时释放。在c语言中可通过标准函数：malloc()，realloc()，sizeof()，free()等来实现分配。

动态分配：p=(lnode*)malloc(sizeof(lnode));函数malloc分配了一个类型为lnode的结点变量的空间，并将其首地址放入指针变量p中。动态释放：free(p);系统回收由指针变量p所指向的内存区。p必须是最近一次调用malloc()函数时的返回值。动态重新分配：p=(lnode*)realloc(p,newsize);先判断当前的指针是否有足够的连续空间，如果有，扩大p指向的地址，并且将p返回，如果空间不够，先按照newsize指定的大小分配空间，将原有数据从头到尾拷贝到新分配的内存区域，而后释放原来p所指内存区域，同时返回新分配的内存区域的首地址，即重新分配存储器块的地址。返回值：如果重新分配成功则返回指向被分配内存的指针，否则返回空指针null。

3、最常用的基本操作 ⑴ 结点的赋值 lnode *p;p=(lnode*)malloc(sizeof(lnode));p->data=20;p->next=null;讲课时板书教案上的几种常见的指针操作。效果如下图。

⑵常见的指针操作 ①q=p;

云淡风清 http:/// ②q=p->next;

③p=p->next;

④q->next=p;

⑤q->next=p->next;

云淡风清 http:///

2.3.2单链式的基本操作

以带头结点的单链表为例。#define ok #define error

-1 typedef int status;//状态 #include “stdlib.h” #include “stdio.h” typedef int elemtype;typedef struct lnode { elemtype

data;//数据域，保存结点的值

struct

lnode *next;//指针域，保存后继结点地址 }lnode;

//结点的类型

/*

1、链表初始化(建立空链表)*/ lnode * init_linklist(void){ lnode *l;l=(lnode *)malloc(sizeof(lnode));//给头结点分配空间

if(l!=null)

l->next=null;//指针域置为空以作为结束标记

return l;} /*

2、头插入法建表

从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止，每次插入的结点都作为链表的第一个数据结点。

*/

云淡风清 http:/// status create1_linklist(lnode *l){ elemtype data;char sfjx=1;//0：结束 1：继续

lnode *p;while(sfjx!=0){

p=(lnode *)malloc(sizeof(lnode));//给新结点分配空间

if(p==null)

return error;//空间分配不成功

else

{

printf(“请输入元素内容：”);

scanf(“%d”,&data);//读入值

p->data=data;//数据域赋值

//钩链，新创建的结点总是作为第一个数据结点

p->next=l->next;

l->next=p;

}

printf(“是否继续(0：结束 1：继续)：”);

scanf(“%d”,&sfjx);} return ok;} /*

3、尾插入法建表

头插入法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。

该方法是将新结点插入到当前链表的表尾，使其成为当前链表的尾结点。*/ status create2_linklist(lnode *l){ elemtype data;char sfjx=1;//0：结束 1：继续

lnode *p,*q;//找到已有链表的末结点

q=l;while(q->next!=null)

q=q->next;while(sfjx!=0){

p=(lnode *)malloc(sizeof(lnode));//给新结点分配空间

if(p==null)

云淡风清 http:///

return error;//空间分配不成功

else

{

printf(“请输入元素内容：”);

scanf(“%d”,&data);//读入值

p->data=data;//数据域赋值

//钩链，新创建的结点总是作为最后一个结点

q->next=p;

q=p;//q重新指向末结点

}

printf(“是否继续(0：结束 1：继续)：”);

scanf(“%d”,&sfjx);} q->next=null;//重设链表结束标记

return(ok);} /*

4、按序号查找，取单链表中的第i个元素。

对于单链表，不能象顺序表中那样直接按序号i访问结点，而只能从链表的头结点出发，沿链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。

设单链表的长度为n，要查找表中第i个结点，仅当1≦i≦n时，i的值是合法的。*/ status get_linklist(lnode *l,int i,elemtype *e){

int j=1;lnode *p;p=l->next;//使p指向第一个结点

while((p!=null)&&(j

p=p->next;//移动指针p

j++;

//j计数

} if(p==null)//找不到

return(error);else {

*e=p->data;

return(ok);} } /*

云淡风清 http:///

5、按值查找

按值查找是在链表中，查找是否有结点值等于给定值key的结点? 若有，则返回首次找到的值为key的结点的存储位置；否则返回null。

*/ lnode *locate_linklist(lnode *l,elemtype key){ lnode *p;p=l->next;while((p!=null)&&(p->data!=key))

p=p->next;if(p!=null)//找到了

return p;else//找不到

return(null);} /*

6、单链表的插入，插入到指定位置

在以l为头结点的单链表的第i个位置插入值为e的结点。

插入运算是将值为e的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1所在的结点p，然后生成一个数据域为e的新结点q，q结点作为p的直接后继结点。

*/ status insert_linklist(lnode *l,int i,elemtype e){ int j=0;lnode *p,*q;p=l;//找待插入位置的前一个结点位置

while((p!=null)&&(j

p=p->next;

j++;} if((j!=i-1)||(p==null))//位置不合适

{

printf(“位置不合适，无法插入！n”);

return error;} else {

q=(lnode *)malloc(sizeof(lnode));//给新结点分配空间

if(q==null)

return error;

else

云淡风清 http:///

{

//实现插入

q->data=e;

q->next=p->next;

p->next=q;

return ok;

} } } /*

7、按序号删除

删除单链表中的第i个结点。

为了删除第i个结点ai，必须找到结点的存储地址。该存储地址是在其直接前趋结点ai-1的next域中，因此，必须首先找到ai-1的存储位置p，然后令p->next指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间，将其归还给“存储池”。设单链表长度为n，则删去第i个结点仅当1≤i≤n时是合法的。则当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，是终端结点。故判断条件之一是p->next!=null。显然此算法的时间复杂度也是o(n)。

*/ status delete1_linklist(lnode *l,int i){ int j=1;lnode *p,*q;p=l;q=l->next;//找待删除位置的前一个结点位置

while(q!=null && j

p=q;

q=q->next;

j++;} if((q==null)||(i<=0)){

printf(“位置不合适，无法删除！n ”);

return error;} else {

//实现删除

p->next=q->next;

free(q);

return ok;} }

云淡风清 http:/// /*

8、按值删除

删除单链表中值为key的第一个结点。

与按值查找相类似，首先要查找值为key的结点是否存在? 若存在，则删除；否则返回null。*/ status delete2_linklist(lnode *l,int key){ lnode *p=l,*q=l->next;//找待删除结点位置，q指向其位置，p指向其前驱结点

while(q!=null && q->data!=key){

p=q;

q=q->next;} if(q!=null)//找到了

{

//实现删除

p->next=q->next;

free(q);

return ok;} else {

printf(“所要删除的结点不存在！n”);

return error;} } /*

9、删除单链表中值为key的所有结点

与按值查找相类似，但比前面的算法更简单。

基本思想：从单链表的第一个结点开始，对每个结点进行检查，若结点的值为key，则删除之，然后检查下一个结点，直到所有的结点都检查。

*/ void delete3_linklist(lnode *l,int key){ lnode *p=l,*q=l->next;//p始终指向q的前驱，以方便删除操作的实现

while(q!=null){

if(q->data==key)

{

p->next=q->next;

云淡风清 http:///

free(q);

q=p->next;

}

else

{

p=q;

q=q->next;

} } } /*

10、删除单链表中所有值重复的结点，使得所有结点的值都不相同 与按值查找相类似，但比前面的算法更复杂。

基本思想：从单链表的第一个结点开始，对每个结点进行检查：检查链表中该结点的所有后继结点，只要有值和该结点的值相同，则删除之；然后检查下一个结点，直到所有的结点都检查。

*/ void delete4_linklist(lnode *l){ lnode *p=l->next,*q,*ptr;while(p!=null)//检查链表中所有结点

{

q=p;

ptr=p->next;

while(ptr!=null)//检查结点p的所有后继结点ptr

{

if(ptr->data==p->data)

{

q->next=ptr->next;

free(ptr);

ptr=q->next;

}

else

{

q=ptr;

ptr=ptr->next;

}

}

p=p->next;} } /*

云淡风清 http:///

11、修改指定位置的数据 */ status modify_linklist(lnode *l,int i,elemtype e){ int j=1;lnode *p;p=l->next;//找待修改结点位置

while(p!=null && j

p=p->next;

j++;} if((p==null)||(i<=0))//找不到

{

printf(“位置不合适，无法修改！n ”);

return error;} else {

p->data=e;

return ok;} } /*

12、单链表遍历 以输出为例 */ void traverse_linklist(lnode *l){ lnode *p;p=l->next;while(p!=null){

printf(“%8d”,p->data);

p=p->next;} printf(“n”);} /*

13、单链表的合并

设有两个有序的单链表，它们的头指针分别是la、lb，将它们合并为以lc为头指针的有序链表。算法说明：算法中pa，pb分别是待考察的两个链表的当前结点，pc是合并过程中合并的链表的最后一个结点。

云淡风清 http:///

合并了值为-7，-2的结点后示意图如下图所示。

*/ lnode *merge_linklist(lnode *la,lnode *lb){ lnode *lc,*pa,*pb,*pc,*ptr;lc=la;pc=la;//指向新链表的末结点

pa=la->next;pb=lb->next;while(pa!=null && pb!=null){

if(pa->data

data)//将pa所指的结点合并，pa指向下一个结点

{

pc->next=pa;

pc=pa;

pa=pa->next;

}

else

if(pa->data>pb->data)//将pb所指的结点合并，pb指向下一个结点

{

pc->next=pb;

pc=pb;

pb=pb->next;

云淡风清 http:///

}

else//将pa所指的结点合并，pb所指结点删除

{

pc->next=pa;

pc=pa;

pa=pa->next;

ptr=pb;

pb=pb->next;

free(ptr);

} } //将剩余的结点链上

if(pa!=null)

pc->next=pa;else

pc->next=pb;

free(lb);return(lc);} /*

14、单链表的排序

采用插入排序方法，以升序为例 */ void sort_linklist(lnode *l){ lnode *p,*q,*r,*s;p=l->next;l->next=null;while(p!=null){

q=l->next;

r=l;

while((q!=null)&&(p->data>q->data))

{

q=q->next;

r=r->next;

}

s=p->next;

r->next=p;

p->next=q;

p=s;} }

云淡风清 http:/// /*

15、单链表的释放 */ void release_linklist(lnode *l){ lnode *p,*q;p=l;//指向头结点，从此结点开始释放

while(p!=null){

q=p->next;

free(p);

p=q;} } void main(){ int xz=1,i;lnode *l,*l1,*l2;elemtype e;while(xz!=0){

printf(“

1、链表初始化n

2、头插入法建表n

3、尾插入法建表n

4、按序号查找n

5、按值查找n

6、单链表的插入n”);

printf(“

7、按序号删除n

8、按值删除n

9、删除单链表中指定值的所有结点n10、删除单链表中所有值重复的结点n”);

printf(“

11、修改指定位置的数据n12、单链表遍历n13、单链表的合并n14、单链表的排序n15、单链表的释放n 0、结束n请选择：”);

scanf(“%d”,&xz);

switch(xz)

{

case 1:

l=init_linklist();

if(l!=null)

printf(“初始化成功！n”);

break;

case 2:

if(create1_linklist(l)==ok)

printf(“建立成功！n”);

else

printf(“建立不成功！n”);

break;

case 3:

if(create2_linklist(l)==ok)

printf(“建立成功！n”);

云淡风清 http:///

else

printf(“建立不成功！n”);break;case 4: printf(“请输入要查找元素的序号：”);scanf(“%d”,&i);if(get_linklist(l,i,&e)==ok)

printf(“%dn”,e);else

printf(“找不到！n”);break;case 5: printf(“请输入要查找元素的关键字：”);scanf(“%d”,&e);l1=locate_linklist(l,e);if(l1!=null)

printf(“%dn”,l1->data);else

printf(“找不到！n”);break;case 6: printf(“请输入要插入元素的内容：”);scanf(“%d”,&e);printf(“请输入插入位置：”);scanf(“%d”,&i);if(insert_linklist(l,i,e)==ok)

printf(“插入成功！n”);else

printf(“插入不成功！n”);break;case 7: printf(“请输入要删除元素的位置：”);scanf(“%d”,&i);if(delete1_linklist(l,i)==ok)

printf(“成功删除！n”);else

printf(“未成功删除！n”);break;case 8: printf(“请输入要元素的内容：”);scanf(“%d”,&e);if(delete2_linklist(l,e)==ok)

printf(“成功删除！n”);else

云淡风清 http:///

printf(“未成功删除！n”);break;case 9: printf(“请输入要元素的内容：”);scanf(“%d”,&e);delete3_linklist(l,e);printf(“成功删除！n”);break;case 10: delete4_linklist(l);printf(“成功删除！n”);

break;case 11: printf(“请输入修改位置：”);scanf(“%d”,&i);printf(“请输入元素的新内容：”);scanf(“%d”,&e);if(modify_linklist(l,i,e)==ok)

printf(“修改成功！n”);else

printf(“修改不成功！n”);break;case 12: traverse_linklist(l);

break;case 13: l1=init_linklist();l2=init_linklist();if((l1==null)||(l2==null))

printf(“初始化不成功！n”);else {

printf(“请建立第一个链表：n”);

create2_linklist(l1);

printf(“请建立第二个链表：n”);

create2_linklist(l2);

sort_linklist(l1);

sort_linklist(l2);

l=merge_linklist(l1,l2);

printf(“合并后的结果如下：n”);

traverse_linklist(l);} break;case 14:

云淡风清 http:///

}

} sort_linklist(l);break;case 15: release_linklist(l);

break;case 0: printf(“谢谢使用，再见！n”);break;default: printf(“输入错误！n”);break;} 2.4循环链表

循环链表(circular linked list)：是一种头尾相接的链表，其特点是最后一个结点的指针域指向链表的头结点，整个链表的指针域链接成一个环，这样，从循环链表的任意一个结点出发都可以找到链表中的其它结点，使得表处理更加方便灵活。

下图是带头结点的单循环链表的示意图。

循环链表的操作：

对于带头结点的单循环链表，除链表的合并外，其它操作和单线性链表基本上一致，仅仅需要在单线性链表操作算法基础上做以下简单修改：

1、判断是否是空链表 head->next==head;

2、判断是否是表尾结点 p->next==head;例：有m个人围成一圈，顺序排号。从第一个人开始报数，凡报到3的人退出圈子，问最后留下的那位是原来的第几号？

根据问题描述可知，该问题中m个人围坐在一起形成首尾相接的环，比较自然的一种思路是用循环链表模拟这个环。从第3个人开始出圈，相当于从链表中删除一个结点。该程序主要由三个模块组成：

1、建立循环单链表存放初始各人编号；

2、报数并按顺序输出出圈人的编号；

3、输出剩下的人的编号。具体步骤如下：

云淡风清 http:/// 第一步：输入人员总数；

第二步：创建循环链表并向单链表中填入人员编号； 第三步：找第一个开始报数的人；

第四步：数到3让此人出圈(删除对应结点)；

第五步：接着开始报数，重复第四步，直到圈中剩余一个为止； 第六步：输出剩下结点中的编号，即为最终所要求的编号。程序源代码： #include “stdio.h” #include “stdlib.h” #define maxn 100 //最大个数 struct node { int data;struct node *next;};void main(){ struct node *head, *s, *q, *t;int n, m, count=0, i;do//输入总个数

{ printf(“请输入总个数(1－%d)：”,maxn);scanf(“%d”,&m);}while((m<1)||(m>maxn));do//输入出圈时要数到的个数

{ printf(“要数到的个数(1--%d)：”,m);scanf(“%d”,&n);}while((n<1)||(n>m));for(i=0;i

{ s=(struct node *)malloc(sizeof(struct node));s->data=i+1;s->next=null;if(i==0){ head=s;q=head;} else

{ q->next=s;q=q->next;}

云淡风清 http:/// } q->next=head;//形成圈

//以下代码输出原始状态

printf(“原始状态：n”);q=head;while(q->next!=head){ printf(“%4d”,q->data);q=q->next;} printf(“%4dn”,q->data);q=head;//以下代码实现出圈

printf(“出圈顺序：n”);do { count++;if(count==n-1){ t=q->next;q->next=t->next;count=0;printf(“%4d”,t->data);free(t);} q=q->next;}while(q->next!=q);printf(“n剩下的是%4dn”,q->data);} 注意：此程序采用的是不带头结点的单链表，以免在循环链表中由于不存放有效数据的头结点的存在而影响计数。

2.5双向链表

双向链表是为了克服单链表的单向性的缺陷而引入的。单链表只

数据结构演讲篇三

《数据结构》教案

课程性质和任务

本课程是计算机专业的主要专业基础课程之一。本课程的参考教学时数为54学时，实际讲课学时为35，实验学时为16。其主要内容包括顺序表、链表、栈、队、串、树和图的结构，以及查找和排序技术。通过本课程的教学，使学生理解计算机软件系统所必须的数据结构及算法的内部逻辑，掌握在软件工程中大量存在的查找和排序技术，并通过大量的上机实习，实现各种数据结构的算法，以便为后续课程的学习提供专业基础知识，同时增强学生编制程序的能力。

课程教学目标

通过本课程的学习，应达到以下目标：

 深刻理解数据结构中线性表、栈、队和链的概念、算法及其基本应用。

 理解树的基本概念，学会建立二叉树，并在二叉树上进行查找、插入和删除等各种运算。

 理解图的基本结构和算法，了解图的路径问题。

 熟练掌握几种重要的内部排序和查找技术，了解外部排序的一般过程。

 能熟练地运用c语言，准确、清晰地编制与本课程有关的算法，并能上机调试通过。

新疆农业大学数据结构课程教案

第一讲 绪论(对应教材p1—p17)

一、教学目的和要求

要求掌握数据结构中基本概念的定义，理解数据结构研究的主要内容，了解抽象数据类型的表示和实现，理解算法评价的两个指标。

二、授课主要内容

1.数据结构研究的主要内容 2.数据结构中涉及的基本概念

3.算法的概念、描述方法以及评价标准

三、教学重点难点

数据结构中的基本概念、算法的概念、描述方法以及评价标准

四、授课内容和方法

【口述】当今计算机应用的特点：所处理的数据量大且具有一定的关系；对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。

一、什么是数据结构

我们大家知道许多非数值计算问题的数学模型常常是数学方程，如线性方程组、微分方程。所以这类非数值计算问题的解决就归结于对数学模型设计算法、编写程序。然而在现实社会中存在着许多非数值计算问题，其数学模型难以用数学方程描述。

1、举例说明

 图书馆的书目检索自动化问题----计算机处理的对象之间存在着线性关系，称为线性的数据结构。

 人机对奕问题----计算机处理的对象是一个个格局。所有可能出现的格局是一棵倒置的树。

 多岔路口交通灯的管理问题----数学模型是图的数学结构。

【由以上举例引出下列结论：】

非数值计算问题的数学模型是表、树和图之类的数据结构。【总结出定义】 数据结构：是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间关系和操作的一门学科。（三个要素：对象、关系及操作（运算））

2、《数据结构》课程的介绍

1968年美国克努特教授开创了数据结构的最初体系： 数据的逻辑结构和存储结构及其操作。

数据结构是一门综合性的专业课程，是一门介于数学、计算机硬件、计算机软件之间的一门核心课程。是设计和实现编译系统、操作系统、数据库系统及其他系统程序和大型应用程序的基础。

二、基本概念和术语

1、数据 数据：是指所有能输入到计算机中并被计算机程序处理的符号的总称。是计算机

加工的“原料”。

数据元素:是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据项:有时，一个数据元素可由多个数据项组成。数据项是数据的不可分割的最小单位。

2、数据对象、数据结构

数据对象：是性质相同的数据元素的集合，是数据的一个子集。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。四类基本结构：集合、线性结构、树形结构、图形结构或网状结构。数据结构的形式定义：数据结构是一个二元组

data_structure=(d,s)其中，d 是数据元素的有限集，s 是d上关系的有限集。

例：复数 complex=(c,r)例：课题小组 group=(p,r)p={t,g1,„,gn,s11,„,snm}1≤n≤3，1≤m≤2，r={r1,r2} r1={

|1≤i≤n, 1≤n≤3,} r2={

|1≤i≤n, 1≤j≤m,1≤m≤2,} 数据结构一般包括三方面的内容：

② 存储结构(物理结构)：数据元素及其关系在计算机存储器的表示。用于表示数据元素的位串称之为元素或结点。用于表示数据项的位串称之为数据域。

③ 数据的运算：对数据施加的操作。

算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构。

3、数据的两种存储结构： 顺序存储结构：把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。通常顺序存储结构是借助于语言的数组来描述的。

链式存储结构：不要求逻辑上相邻的结点物理上也相邻，结点间的逻辑关系是由附加的指针字段表示的，通常要借助于语言的指针类型来描述。

*

4、数据类型、抽象数据类型

数据类型:是一个值的集合和定义在这个值集上的所有的操作。例如，整数类型。数据类型可分为：非结构的原子类型和结构类型。

原子类型的值是不可分解的，结构类型的值是由若干成分按某种结构组成的。

抽象数据类型:是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型和数据类型实质上是一个概念，它仅取决于数据类型的逻辑性，而与其在计算机内部如何表示和实现是无关的。

抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。抽象数据类型按其值的不同特性，分为三种类型： ① 原子类型:变量的值是不可分解的。

② 固定聚合类型:变量的值由确定数目的成分按某种结构组成。③ 可变聚合类型:其值的成分数目不确定。

抽象数据类型的形式定义：我们用一个三元组来表示一个抽象数据类型。

（d，s，p）

d是数据对象，s是d上的关系集，p是对d的基本操作。

格式：

adt 抽象数据类型名{ 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 }adt 抽象数据类型名。

数据对象和数据关系的定义用伪码描述。数据基本操作的定义格式：

基本操作名（参数表）

初始条件：〈初始条件描述〉

操作结果：〈操作结果描述〉 例：

adt triplet{ 数据对象：d={e1，e2,e3 |e1,e2,e3∈elemset(定义了关系运算的某个集合)} 数据关系：r1={〈e1,e2>,

〉 基本操作：

min(t,&e)

}adt triplet 多形数据类型:是其值的成分不确定的数据类型。

三、抽象数据类型的表示与实现

抽象数据类型可通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。

1、类c语言

精选了c 的一个子集，扩充修改，增强了语言的描述功能。 预定义常量和类型

 数据结构的表示：存储结构用类型（typedef）定义来描述。

数据元素类型约定为elemtype. 基本操作的算法用函数描述：

函数类型 函数名（函数参数表）{ //算法说明

语句序列

}//函数名

增加了引用调用的参数传递方式。

 赋值语句、选择语句、循环语句、结束语句、输入输出语句、注释语句  基本函数  逻辑运算约定

例：triplet的表示和实现

//采用动态分配的顺序存储结构

typedef elemtype * triplet://由inittriplet分配三个元素存储空间 //基本操作的函数原型说明

status inittriplet(triplet &t,elemtype v1, elemtype v2, elemtype v3)status destroytriplet（&t）status get（t,i,&e）status put(&t,i,e)status isascending(t)status isdescending(t)status max(t,&e)status min(t,&e)//基本操作的实现

status inittriplet(triplet &t, elemtype v1, elemtype v2, elemtype v3){ //构造三元组t，依次置t 的三个元素的处值为v1,v2和v3。

t=(elemtype)malloc(3*sizeof(elemtype));//分配三个元素的存储空间

if(!t)exit(overflow);//分配存储空间失败 t[0]=v1;t[1]=v2;t[2]=v3;return ok;}//inittriplet status destroytriplet（triplet &t）{ //销毁三元组t。······

}//min

四、算法和算法分析

1、算法（algorithm）

是对特定问题求解步骤的一种描述，它是指令的有限序列。算法具有五个重要特性：有穷性、确定性、可行性、输入、输出

2、算法设计的要求

正确性、可读性、健壮性和效率与低存储量要求

3、算法效率的度量

算法时间是由控制结构和原操作的决定的。做法：选取一种是基本操作的原操作，以该基本操作重复的次数作为算法的时间量度。

时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数f（n），t（n）=o（f（n））

它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长绿相同。

语句的频度：是该语句重复执行的次数。

例：求两个n阶方阵的乘积c=a×b，其算法如下： #define n 100 void matrixmultiply(int a[n][n],int b[n][n],int c[n][n]){ int i,j,k for(i=1;i<=n;++i)n+1

for(j=1;j<=n;++j)n*(n+1)

c[i][j]=0;n2

for(k=1;k<=n,k++)n2(n+1)

3c[i][j]=c[i][j]+a[i][k]*b[k][j];n

} } t(n)=2n3+3n2+2n+1 3limt(n)/ n=2 t(n)=o(n3)例：

（a）{++x;s=0;}（b）for(i=1;i<=n;++i){++x;s+=x;}（c）for(j=1;j<=n;++j)for(k=1;k<=n;k++){++x;s+=x;} 含基本操作“x增1”的语句的频度分别为1,n和n2 时间复杂度是o(1),o(n)和o(n2)。时间复杂度有时与输入有关。

4、算法的存储空间需求

空间复杂度：s（n）=o（f（n））

五、作业布置

复习回顾c语言中关于结构体和指针部分的内容，以便于后期学习。

六、教学后记

按2 学时讲完。

以前教学中反映出学生对抽象数据类型掌握不好，结构体知识基本不懂，所以要求学生课下自学，下次课抽1学时学习结构体和指针。

学生读程序能力差，循环嵌套分析不出执行次数。考虑布置了一道题目练习。

数据结构演讲篇四

数据结构参考题目

一、选择

1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（）

a.栈 b.队列 c.树 d.图 2.下面程序段的时间复杂度为（）for(i=0;i

next =hl;b.p->next=hl;hl=p;c.p->next=hl;p=hl;d.p->next=hl->next;hl->next=p;4.两个字符串相等的条件是（）

c.都是非空串 d.串的长度相等且对应的字符相同 5．若以s和x分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（）

xx sx sx xx 6.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（）a.0 b.1 c.48 d.49 7.已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为

（35，51，24，13，68，56，42，77，93）

（35，24，13，51，56，42，68，77，93）所采用的排序方法是（）

a.插入排序 b.冒泡排序 c.快速排序 d.归并排序

8.已知散列表的存储空间为t[0..16]，散列函数h（key）=key%17,并用二次探测法处理冲突。散列表中已插入下列关键字：t[5]=39，t[6]=57和t[7]=7，则下一个关键字23插入的位置是（）

a.t[2] b.t[4] c.t[8] d.t[10] 9.如果将矩阵an×n的每一列看成一个子表，整个矩阵看成是一个广义表l，即l=((a11,a21,…,an1),(a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素，则求得a21的运算是（）(tail(head(l)))(head(head(l)))(head(tail(l)))(head(tail(l)))10.在一个具有n个顶点的有向图中，所有顶点的出度之和为dout，则所有顶点的入度之和为（）

-1 +1 d.n 11．从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（）a线性结构 b.树形结构 c.线性结构和树型结构 d.线性结构和图状结构

12．栈的插入和删除操作在()进行。

a．栈顶 b.栈底 c.任意位置 d指定位置 13．由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）a.24 b.71 c.48 d.53 14．一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是()a.2 3 1 b.3 2 1 c.3 1 2 d.1 2 3 15．关于栈和队列的说法中正确的是（）

a．栈和队列都是线性结构 b.栈是线性结构，队列不是线性结构 c.栈不是线性结构，队列是线性结构 d.栈和队列都不是线性结构 16．关于存储相同数据元素的说法中正确的是（）a．顺序存储比链式存储少占空间 b.顺序存储比链式存储多占空间

c.顺序存储和链式存储都要求占用整块存储空间 d.链式存储比顺序存储难于扩充空间

17．已知一个单链表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（）a.q→next=s；p→next=s； b.q→next=s；s→next=p； c.q→next=s；q→next=p； d.q→next=s；s→next=q；

18．设一组记录的关键字key值为{62，50，14，27，19，35，47，56，83}，散列函数为h(key)=key mod 13，则它的开散列表中散列地址为1的链中的结点个数是（）a.1 b.2 c.3 d.4 19．执行下面程序段时，s语句被执行的次数为：（）for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)s;a.n*n b.n*n/2 c.n(n+1)d.n(n+1)/2 20．在长度为n的线性表中删除一个指针p所指结点的时间复杂度是（）a．o(n)b.o(1)c.o(log2n)d.o(n2)21．设一个栈的输入序列是a，b，c，d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是（）

a.a，b，c，d b.a，b，d，c c.d，c，b，a d.c，d，a，b 22．关于串的叙述中，正确的是（）a．空串是只含有零个字符的串 b.空串是只含有空格字符的串

c.空串是含有零个字符或含有空格字符的串

d.串是含有一个或多个字符的有穷序列

23．在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（）

a．front==rear

b.(front+1)%m==rear

+1==front

d.(rear+1)%m==front 24．设有二维数组

1a［n］［n］表示如下：23456，则a［i］［i］（0≤i≤n-1）的d.i2/2 值为（）

a．i*(i-1)/2 b.i*(i+1)/2 c.(i+2)*(i+1)/2 25．高度为h的完全二叉树中，结点数最多为（）

ha．2h-1 b.2h+1 c.2-1 d.2h 26．由m棵结点数为n的树组成的森林，将其转化为一棵二叉树，则该二叉树中根结点的右子树上具有的结点个数是（）

-1 c.n(m-1)d.m(n-1)27．在一个具有n个顶点的无向图中，每个顶点度的最大值为（）a.n b.n-1 c.n+1 d.2(n-1)28．关于无向图的邻接矩阵的说法中正确的是（）a.矩阵中非全零元素的行数等于图中的顶点数

b.第i行上与第i列上非零元素总和等于顶点vi的度数 c.矩阵中的非零元素个数等于图的边数

d.第i行上非零元素个数和第i列上非零元素个数一定相等

29．设一组记录的关键字key值为{62，50，14，28，19，35，47，56，83}，散列函数为h(key)=key mod 13，则它的开散列表中散列地址为1的链中的结点个数是（）a.1 b.2 c.3 d.4 30．设有一组初始关键字值序列为（49，81，55，36，44，88），则利用快速排序的方法，以第一个关键字值为基准得到的一次划分为（）

a.36，44，49，55，81，88 b.44，36，49，55，81，88 c.44，36，49，81，55，88 d.44，36，49，55，88，81

二、填空题

1.数据是计算机加工处理的对象（）。2.数据结构的概念包括数据的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面()。

3.线性表是由n≥0个相同类型组成的有限序列（）。4.栈是一种后进先出的线性表（）。

5.从循环链表的某一结点出发，只能找到它的后继结点，不能找到它的前驱结点（）。6.单链表设置头结点的目的是为了简化运算（）。7.树的最大特点是一对多的层次结构（）。8.组成数据的基本单位称为数据元素（）。

9.从非循环链表的某一结点出发，既能找到它的后继结点，又能找到它的前驱结点（）。

10.单链表结点的指针域是用来存放其直接后继结点的首地址的（）

11.数据的存储结构是数据的逻辑结构的存储映象（）。

12.用顺序表来存储线性表时，不需要另外开辟空间来保存数据元素之间的相互关系（）。

13.在非线性结构中，至少存在一个元素不止一个直接前驱或不止一个直接后驱（）。14.树的最大特点是一对多的层次结构（）。15.队列的特点是先进先出（）。

16.由后序遍历序列和中序遍历序列能唯一确定一颗二叉树（）。17.数据的存储结构独立于计算机（）。18.线性表简称为”顺序表”。（）

19.对数据的任何运算都不能改变数据原有的结构特性（）。20.从循环单链表的任一结点出发，可以找到表中的所有结点（）。21.栈是一种先进先出的线性表（）。22.链表的主要缺点是不能随机访问（）。23.二叉树是树的特殊形式（）。24.冒泡排序法是稳定的排序（）。25.算法是对解题方法和步骤的描述（）。26.算法可以用任意的符号来描述（）。

27.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型（）。

28.线性表的顺序存储方式是按逻辑次序将元素存放在一片地址连续的空间中（）。29.栈是一种先进后出的线性表（）。

30.将插入和删除限定在表的同一端进行的线性表是队列（）。

三、画图题

1.请根据下列二元组画出相应的数据结构

k={15,11,20,8,14,13 } r={<15,11>,<15,20>,<11,8>,<11,14>,<14,13>} 2.请根据下列二元组画出相应的数据结构

k={a,b,c,d,e,f,g,h,i,j} r={,,

,

,

,

,

,

,

} 3．请根据下列二元组画出相应的数据结构 k={1,2,3,4,5,6,7} r={<1,2>,<1,3>,<1,4>,<2,1>,<2,4>,<3,5>,<3,6>,<3,7>,<4,1>,<4,5>,<5,1>,<5,3>,<5,4>,<6,5>,<6,7>,<7,3>} 4.请根据下列二元组画出相应的数据结构

k={1,2,3,4,5,6,7} r={(1,2),(1,3),（2,3），(2,4),(2,5),(3,7),(4,6),(5,6)，（6,7）}

四、运算题

1．已知一个图的顶点集v和边集h分别为：

v＝{0，1，2，3，4，5，6，7}

e＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；

按照克鲁斯卡尔算法得到最小生成树，拭写出在最小生成树中依次得到的各条边。______，______，______，______，______，______，______。

2.一个线性表为b=（12，23，45，57，20，03，78，31，15，36），设散列表为ht[0..12]，散列函数为h（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。

平均查找长度：（写出计算过程）

3．已知一个图的顶点集v和边集h分别为：

v＝{0，1，2，3，4，5，6，7}

e＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；

按照普里姆算法得到最小生成树，试写出在最小生成树中依次得到的各条边。（从顶点2出发）

____

__，___

_，___

___，__

____，___ ___，__ ____，___ ___。4.写出下图所示的二叉树的前中后序遍历结果：

前序： 中序： 后序：

5.设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起，逐个输入各个数据而生成的二叉排序树。

五、编程题

1.请编写一个算法，实现十进制整数与二进制数的转换。void shi_to_er(unsigned x){ 2.写出二分法查找的算法：

int search_bin(keytype k,sstable st){ 3.请编写一个算法，实现单链表的就地逆置（单链表不带头结点）。linklist *invertlink(linklist *h){

数据结构演讲篇五

数据结构】二叉排序树的建立，查找，插入和删除实践题 /*sy53.c*/

#include

typedef struct node{

keytype key;

struct node *lchild,*rchild;

}bstnode;

typedef bstnode *bstree;

bstree createbst(void);

void searchbst(bstree t,keytype key);

void insertbst(bstree *tptr,keytype key);

void delbstnode(bstree *tptr,keytype key);

void inorderbst(bstree t);

main()

{bstree t;

char ch1,ch2;

keytype key;

printf(“建立一棵二叉排序树的二叉链表存储n”);

t=createbst();

ch1='y';

while(ch1=='y' || ch1=='y')

{printf(“请选择下列操作：n”);

printf(“1------------------更新二叉排序树存储n”);

printf(“2------------------二叉排序树上的查找n”);

printf(“3------------------二叉排序树上的插入n”);

printf(“4------------------二叉排序树上的删除n”);

printf(“5------------------二叉排序树中序输出n”);

printf(“6------------------退出n”);

scanf(“n%c”,&ch2);

switch(ch2)

{case '1':t=createbst();break;

case '2':printf(“n请输入要查找的数据：”);

scanf(“n%d”,&key);

searchbst(t,key);

printf(“查找操作完毕。n”);break;

case '3': printf(“n请输入要插入的数据：”);

scanf(“n%d”,&key);

insertbst(&t,key);

printf(“插入操作完毕。n”);break;

case '4': printf(“n请输入要删除的数据：”);

scanf(“n%d”,&key);

delbstnode(&t,key);

printf(“删除操作完毕。n”);break;

case '5': inorderbst(t);

printf(“n二叉排序树输出完毕。n”);break;

case '6':ch1='n';break;

default:ch1='n';

}

}

}

bstree createbst(void)

{bstree t;

keytype key;

t=null;

printf(“请输入一个关键字(输入0时结束输入)：n”);scanf(“%d”,&key);

while(key)

{insertbst(&t,key);

printf(“请输入下一个关键字(输入0时结束输入)：n”);scanf(“n%d”,&key);

}

return t;

}

void searchbst(bstree t, keytype key)

{ bstnode *p=t;

while(p)

{if(p->key==key)

{printf(“已找到n”);

return;

}

p=(key

key)? p->lchild:p->rchild;

}

printf(“没有找到n”);

}

void insertbst(bstree *t,keytype key)

{bstnode *f,*p;

p=(*t);

while(p)

{if(p->key==key)

{printf(“树中已有key不需插入n”);

return;

}

f=p;

p=(key

key)?p->lchild:p->rchild;

}

p=(bstnode*)malloc(sizeof(bstnode));

p->key=key;

p->lchild=p->rchild=null;

if((*t)==null)(*t)=p;

else if(key

key)f->lchild=p;

}/*insertbst*/

void delbstnode(bstree *t,keytype key)

{bstnode *parent=null, *p, *q,*child;

p=*t;

while(p)

{if(p->key==key)break;

parent=p;

p=(key

key)?p->lchild:p->rchild;

}

if(!p){printf(“没有找到要删除的结点n”);return;}

q=p;

if(q->lchild && q->rchild)

for(parent=q,p=q->rchild;p->lchild;parent=p,p=p->lchild);child=(p->lchild)?p->lchild:p->rchild;

if(!parent)*t=child;

else {if(p==parent->lchild)

parent->lchild=child;

else parent->rchild=child;

if(p!=q)

q->key=p->key;

}

free(p);

}

void inorderbst(bstree t){ if(t!=null)

{inorderbst(t->lchild);printf(“%5d”,t->key);inorderbst(t->rchild);}

}