数据结构 课件 第1章 绪论

1/48review复习#include<bits/stdc++.h>intmain(){ inta[10]={89,23,45,13,67,90,35,68,33,67}; inti,j,temp; for(i=0;i<10;i++) printf("%d",a[i]); printf("\n");

for(i=1;i<10;i++) { temp=a[i]; j=i-1; while(j>=0&&temp<a[j]) { a[j+1]=a[j]; j--;

} a[j+1]=temp; } for(i=0;i<10;i++) printf("%d",a[i]); printf("\n"); return0;}2/48review复习voidswap(int*a,int*b){ inttemp; temp=*a; *a=*b; *b=temp;}intmain(){ inta,b; scanf("%d%d",&a,&b); swap(&a,&b); printf("a=%d,b=%d",a,b); return1;}3/48voidswap(int&a,int&b){ inttemp; temp=a; a=b; b=temp;}intmain(){ inta,b; scanf("%d%d",&a,&b); swap(a,b); printf("a=%d,b=%d",a,b); return1;}review复习1.1什么是数据结构1.2算法及算法分析4/48第1章绪论数据：所有能够输入到计算机中，且能被计算机处理的符号的集合。1.1.1数据结构的定义数据结构中的几个概念5/48数据结构：逻辑结构+存储结构+算法1.1什么是数据结构Word文档图像文档都是数据而数据结构中主要讨论结构化数据。6/48学号姓名C语言程序设计成绩1001张梦871002李华961003陈烨951004张强891005赵娟781006王生90一个学生成绩表示例7/48typedefstructstudent{ intnumber; charname[8]; intscore;}st;typedefstructstlist{ stdata; intlength;}stl;//结构体定义数据中可包含结构体类型变量数据结构化数据示例数据元素：是数据（集合）中的一个“个体”，它是数据的基本单位。数据项：数据项是用来描述数据元素的，它是数据的最小单位。数据项(用于描述数据元素)数据元素8/48学号姓名C语言程序设计成绩1001张梦871002李华961003陈烨951004张强891005赵娟781006王生901班学生数据张三男101班李四计科系北京…数据元素（类型不相同）不是数据对象数据对象：具有相同性质的若干个数据元素的集合，如整数数据对象是所有整数的集合。2班学生数据张三男101班李四男102班…数据元素（类型相同）是数据对象默认情况下，数据结构中讨论的数据都是数据对象。9/48不相邻相邻10/48数据结构中讨论的元素关系主要是指相邻关系或邻接关系。学号姓名C语言程序设计成绩1001张梦871002李华961003陈烨951004张强891005赵娟781006王生90逻辑结构存储结构数据运算数据元素之间的逻辑关系

数据的逻辑结构。数据元素及其关系在计算机中的存储方式

数据的存储结构（或物理结构）。施加在该数据上的操作

数据运算。11/48数据结构的3个方面：数据的逻辑结构是从数据元素的逻辑关系上描述数据的。是指数据元素之间的逻辑关系的整体，通常是从求解问题中提炼出来的。数据逻辑结构与数据的存储无关，是独立于计算机的。12/481.1.1逻辑结构数据的逻辑结构是面向用户的，它有多种表示形式。

学生成绩表的逻辑结构表示1-图表直接来源于现实世界13/481、数据的逻辑结构表示学号姓名C语言程序设计成绩1001张梦871002李华961003陈烨951004张强891005赵娟781006王生9010011002100310041005100614/48学号姓名C语言程序设计成绩1001张梦871002李华961003陈烨951004张强891005赵娟781006王生90一个二元组表示为：

B=(D，R)

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

D={di|1≤i≤n，n≥0}：数据元素的集合

R={rj|1≤j≤m，m≥0}：关系的集合

二元组是一种通用的逻辑结构表示方法15/48学生表的逻辑结构表示2-二元组序偶<x，y>（x，y∈D）

x为第一元素，y为第二元素。x为y的前驱元素。y为x的后继元素。若某个元素没有前驱元素，则称该元素为开始元素；若某个元素没有后继元素，则称该元素为终端元素。序偶<x，y>表示x、y是有向的，序偶(x，y)表示x、y是无向的每个关系rj的用若干个序偶来表示：16/48二元组逻辑表示：

<1001,1002>，<1002,1003>，<1003,1004>，<1004,1005>，<1005,1006>每个学生记录用学号标识17/48学号姓名C语言程序设计成绩1001张梦871002李华961003陈烨951004张强891005赵娟781006王生90例如，如下数据为一个矩阵：

对应的二元组表示为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>，<8,12>，<12,10>，<2,7>，<7,9>,

<7,4>，

<4,11>}26318127451091118/48元素之间关系：无。特点：数据元素之间除了“属于同一个集合”的关系外，别无其他逻辑关系。是最松散的，不受任何制约的关系。各种各样的数据呈现出不同的逻辑结构，归纳为4种。1）集合19/482、逻辑结构类型元素之间关系：一对一。特点：开始元素和终端元素都是唯一的，除此之外，其余元素都有且仅有一个前驱元素和一个后继元素。…20/482）线性结构元素之间关系：一对多。

特点：开始元素唯一，终端元素不唯一。除终端元素以外，每个元素有一个或多个后续元素；除开始元素外，每个元素有且仅有一个前驱元素。21/483）树形结构【例1-3】有一种数据结构B2=（D，R），其中D={48，25，64，57，82，36，75}R={r1，r2}

r1={<25，36>，<36，48>，<48，57>，<57，64>，

<64，75>，<75，82>}

r2={<48，25>，<48，64>，<64，57>，<64，82>，

<25，36>，<82，75>}画出其逻辑结构表示，指出是什么类型？22/4848253664578275r2关系表示r1关系表示解：B2的逻辑结构图如下。r1为线性结构r2为树形结构23/48元素之间关系：多对多。

特点：所有元素都可能有多个前驱元素和多个后继元素。24/484）图形结构线性结构树形结构图形结构线性表栈队列串数组树二叉树图25/48数据结构课程按逻辑结构类型分类学习一个一个数据结构的!数据逻辑结构在计算机中的存储表示称为数据的存储结构，也称为物理结构。

逻辑结构存储结构映射设计存储结构的这种映射应满足两个要求：存储逻辑结构中的所有元素存储数据元素间的逻辑关系26/481.1.2存储结构顺序存储结构链式存储结构索引存储结构哈希（散列）存储结构在软件开发中，人们设计了各种存储结构。归纳为4种基本的存储结构。27/48struct{intno; //存储学号

charname[8]; //存储姓名

intscore; //存储成绩

}Stud[6]={{1001,“张梦”,87},…,{1006,"王生",90}};存放学生成绩表的结构体数组Stud定义如下：28/48学生成绩表顺序存储结构－结构体数组学号姓名C语言程序设计成绩1001张梦871002李华961003陈烨951004张强891005赵娟781006王生90Stud数组起始地址…存储结构建立完毕学生成绩表的逻辑结构Stud[0]1001张梦8729/48Stud[1]1002李华96Stud[5]1006王生90顺序存储结构的特点：所有元素占用一整块内存空间。逻辑上相邻的元素，物理上也相邻。Stud[i]Stud[i+1]两个逻辑上相邻元素存储空间也相邻30/48直接映射typedefstructscore{intnum;charname[10];intC_score;}StuScore;typedefstructstudentscore{StuScoredata;structstudentscore*next;}LN_score;//链式存储结构定义学生成绩表存放学生表的链表的结点类型StudType声明如下：31/48学生表链式存储结构－链表学生成绩表的逻辑结构32/48链式存储学生成绩表在内存中的表示学生成绩表采用链式存储结构在内存中如图表示，其中内存地址用十进制表示。学生成绩表的逻辑结构33/48链式存储结构的特点：链式存储结构不具有随机存储特性，如果要查找某一个元素，需要通过指针遍历整个节点，直到找到该元素为止。同时，链式存储结构便于数据修改，如在某个元素前插入或删除元素时，不需要移动节点，只需修改相应节点对应的指针域地址即可，如删除一个元素操作示例如图1.13所示。图

链式存储结构删除操作链式存储结构删除操作过程描述：先定义一个指针指向要删除的节点，以免该节点丢失在内存中成为野指针，将所要删除的节点前面的指针域地址修改为要删除节点后面节点的地址，最后释放要删除的节点指针。一个逻辑元素用一个结点存储，每个结点单独分配，所有结点的地址不一定是连续的。用指针来表示逻辑关系。34/48链式存储结构的特点：学号（关键字）地址100101002510032100441005110063主数据表学生表的逻辑结构地址学号姓名成绩01001张梦8711005赵娟7821003陈烨9531006王生9041004张强8951002李华96索引表索引存储结构=主数据表

+索引表。索引表中所有关键字有序排列（如递增）。35/48学生成绩表索引存储结构学号姓名C语言程序设计成绩1001张梦871005赵娟781003陈烨951006王生901004张强891002李华96查找关键字（如学号）为k的元素时：先在索引表中快速查找（因为索引表中按关键字有序排列，可以采用二分查找）到相应的关键字k。然后通过对应地址在主数据表中找到元素。36/48学号（关键字）地址100101002510032100441005110063主数据表地址学号姓名成绩01001张梦8711005赵娟7821003陈烨9531006王生9041004张强8951002李华96索引表通过索引表按关键字查找速度快增加索引表

存储空间较大37/48索引存储结构特点：哈希存储结构=哈希函数+解决冲突方法。哈希函数h(key)将关键字为key的元素存放在该地址。查找关键字为key的元素时，先计算h(key)，由该值和解决冲突方法来确定其存储地址。38/48学生表哈希存储结构学号姓名性别班号1张斌男99018刘丽女990234李英女990120陈华男990212王奇男990126董强男99025王萍女9901学生表的逻辑结构n=7,m=10哈希函数：h(key)=key%10地址学号姓名性别班号020陈华男990211张斌男9901212王奇男99013434李英女990155王萍女9901626董强男9902788刘丽女99029学号(key)h(key)11%10=188%10=83434%10=42020%10=01212%10=22626%10=655%10=539/48学生表哈希存储结构地址学号姓名性别班号020陈华男990211张斌男9901212王奇男99013434李英女990155王萍女9901626董强男9902788刘丽女99029哈希函数：h(key)=key%10查找关键字（如学号）为k的元素时：先计算d=h(k)。在d地址比较关键字k，若相同，表示找到了！40/48学生表哈希存储结构按关键字查找速度快需要解决冲突但不适合任何数据的存储41/48哈希存储结构的特点同一逻辑结构可以对应多种存储结构。结论：42/48数据运算是对数据的操作。数据运算分为两个层次：运算定义（或运算描述）和运算实现。逻辑结构、存储结构和运算三者之间的关系：运算定义逻辑结构存储结构映射运算实现43/481.1.3数据运算对于“学生成绩表”这种数据结构，可以进行一系列的运算：查找学号为1002的学生姓名增加一个学生记录；删除一个学生记录；查找性名为“赵娟”的学生记录；查找成绩大于90的学生记录；……运算描述44/48学号姓名C语言程序设计成绩1001张梦871005赵娟781003陈烨951006王生901004张强891002李华96Stud数组起始地址……直接找到Stud[1]元素，返回李华45/48顺序存储结构中实现“查找序号为2的学生姓名”Stud[0]1001张梦87Stud[1]1002李华96head1001张梦87i=1，pi2i=2，pi=2找到序号为2的记录，返回刘丽46/48思考并讨论：顺序存储结构和链式存储结构的区别（如插入、删除、查找等）链式存储结构中实现“查找序号为2的学生姓名”1002李华961003陈烨951004张强891005赵娟781006王生90∧同一逻辑结构可以对应多种存储结构。同样的运算，在不同的存储结构中，其实现过程是不同的。结论：47/4848/48#include<bits/stdc++.h>typedefstructLinknode{ intdata; structLinknode*next;}Linkstd;intmain(){ Linkstd*L; L=(Linkstd*)malloc(sizeof(Linkstd)); Linkstd*p,*s; inta; p=L; scanf("%d",&a);

while(a!=0) { s=(Linkstd*)malloc(sizeof(Linkstd)); s->data=a; p->next=s; p=p->next; s->next=NULL; scanf("%d",&a); } p=L; while(p->next!=NULL) { printf("%d",p->next->data); p=p->next; } return0;}分析算法占用的资源CPU时间内存空间时间性能分析空间性能分析算法分析目的：分析算法的时空效率以便改进算法性能。

1.3.1算法分析概述49/211.3算法分析算法分析的目的是（）。A.找出数据结构的合理性B.研究算法中输入和输出的关系C.分析算法的效率以求改进D.分析算法的易读性和可行性答：C。示例50/21算法中的基本操作一般是最深层循环内的原操作。算法执行时间大致=基本操作所需的时间×其运算次数。

在算法分析时，计算T(n)时仅仅考虑基本操作的运算次数。转化51/21简化的算法时间复杂度分析算法运行时间=一个简单操作所需的时间×简单操作次数每条语句执行一次所需要的时间，随机器而异。取决于机器的指令性能，速度以及编译代码的质量。是由及其本身软硬件环境决定的，与算法无关。所以，可以假设执行每条语句的时间均为单位时间，在讨论算法运行时间时不予考虑。所以，算法的运行时间取决于简单操作次数，用T（n）表示，执行简单操作次数越多，其执行时间就相对越多。为了便于比较不同算法的时间效率，我们仅比较算法简单操作次数的数量级，数量级越大，算法时间复杂度越高。算法的时间复杂度就是用T（n）的数量级来表示，记作O（f（n））。52/21intmain(){ inti,j,n,m=0; scanf("%d",&n); for(i=0;i<n;i++) for(j=0;j<n;j++) m++; printf("%d",m); return0;}基本操作【例1.2】分析下面算法的时间复杂度53/21这种简化的时间复杂度分析方法得到的结果相同，但分析过程更简单。

解：该算法中的基本操作是两重循环中最深层的语句m++，分析它的频度，即：

54/21

所以，该算法的时间复杂度为

55/21请自行计算如下算法的时间复杂度voidfun(intn){ inti,x=0; for(i=1;i<n;i++) for(j=i+1;j<=n,j++) x++;}下列程序段的时间复杂度是（）。A.O(log2n) B.O(n)C.O(nlog2n) D.O(n2)count=0;for(k=1;k<=n;k*=2)for(j=1;j<=n;j++)count++;说明：本题为2014年全国考研题基本操作示例56/21解：该算法中的基本操作是两重循环中最深层的语句count++，由于外层循环和内层循环之间没有交叉，符合乘积关系，先分析外层循环的执行次数为：

...满足条件内层循环的执行次数为：所以整个算法的时间复杂度为：57/21voidfun(intn) { inti,x=0; for(i=1;i<n;i++) for(j=i+1;j<=n,j++) x++; }58/21【例1.3】分析下面算法的时间复杂度基本操作解：该算法中的基本操作是两重循环中最深层的语句x++，分析它的执行次数，即：

所以，该算法的时间复杂度为voidfn(intn){ inty=0; while(y*y<=n) y++;}59/21【例1.4】分析下面算法的时间复杂度

所以，该算法的时间复杂度为解：该算法中的基本操作是y++，分析它的执行次数与y值的变化关系，再根据条件约束，计算出执行次数与n的关系，进而分析该算法的时间复杂度。...满足条件y*y<=n

所以，voidfun1(intn){ i=1,k=100; while(i<=n) { k=k+1; i+=2; }}60/21【例1.6】分析下面算法的时间复杂度解：该算法中的基本操作是while循环中最深层的语句i+=2，分析该循环的执行次数为：...满足条件所以整个算法的时间复杂度为：intFind(inta[],ints,intt,intx){intm=(s+t)/2;if(s<=t){if(a[m]==x)returnm;elseif(x<a[m])returnFind(a,s,m-1,x);elsereturnFind(a,m+1,t,x);}return-1;}61/21【例1.7】以折半查找为例分析递归算法的时间复杂度解：分析递归算法的时间复杂度前先要分析该算法的执行次数递归方程。该算法的执行次数递归方程为：T(n)=1

当n=1T(n)=T(n/2)+1

当n>1只有当n=1时，即才能到达出口，使得此时，所以，整个算法的时间复杂度为：于是：62/21

各种不同算法时间复杂度的比较