《北京邮电大学-数据结构讲义课件》由会员分享，可在线阅读，更多相关《北京邮电大学-数据结构讲义课件（269页珍藏版）》请在金锄头文库上搜索。
1、数据结构,题型(1),基本概念40 选择和判断，20个左右 简答或给定实例执行算法30（5-6个题目） 概念或者某些数据结构的性质 例如： 霍夫曼编码 直接插入/冒泡/快速/选择/堆排序等算法的执行 链地址法哈希表装填 根据二叉树遍历结果画出树 关于图的算法执行，等等,题型(2),算法设计题30 常见题型的范围（2-3题目) 简单题目（数组，单层或双层循环，条件判断） 单向链表或双向链表操作（插入/删除/转置/合并） 二分查找，简单排序算法的实现 二叉树（复制，相等，相似等，使用简单递归算法）,第一章 绪论,基本概念,学习数据结构的意义,是为研究和解决如何有效地组织和处理非数值数据而产生的理论
2、、技术和方法。 是计算机科学中的一门综合性的专业基础课。 涉及计算机软件、硬件以及数学等,基本术语,数据 被计算机加工处理的对象。 数据元素（记录、表目） 数据的基本单位，是数据集合中的一个有意义的个体。 数据项 一个数据元素可由若干个数据项组成。,组合项,原子项,基本术语2,数据对象 是性质相同的数据元素的集合，是数据的一个子集。 学号 姓名 班号 性别 出生日期 入学成绩 001 刘影 01 女 19840417 623 002 李恒 01 男 19831211 679 003 陈诚 02 男 19840910 638 数据结构 具有结构的数据元素的集合。它包括数据元素的逻辑结构、存储结构
3、和相适应的运算。,数据元素,数据元素之间的逻辑关系，与计算机无关。 可用一个二元组表示：Data_Structure = (D,R) D：数据元素的有穷集合，R：集合D上关系的有穷集合。 例 设有数据结构 B = (D,R) ， 其中 D= d1, d2, d3, d4, d5, d6， R=r， r=, , , , ， 试画出其逻辑结构图。,逻辑结构,（以班级学生关系为例） (1)集合结构 数据元素除了“属于同一集合”的联系之外，没有其它的关系。 (2)线性结构 数据元素之间存在一对一的关系。 (3)树型结构 数据元素之间存在一对多的关系。 (4)图状结构或网状结构 数据元素之间存在多对多的
4、关系。,成员关系,长幼关系,管理关系,朋友关系,四种基本的逻辑结构,数据的逻辑结构,存储结构：数据的逻辑结构在计算机中如何表示。 数据元素的映象 用二进制位(bit)的位串表示数据元素。 每个数据元素的映象称为结点 每个数据项的映象称为数据域 关系的映象 两种基本方法及其组合使用。 顺序映象：以相对的存储位置表示关系 链式映象：以附加信息(指针)表示关系 注意：数据的逻辑结构和存储结构的关系 可以用数组等线形存储的方式存储逻辑上的树形结构 也可以用树状的复杂的存储结构来存储逻辑上的集合关系以达到提高检索速度的目的,数据的存储结构,数据的逻辑结构+运算的定义-面向用户，需求分析 （抽象数据类型）
5、 概念层 数据的存储结构+运算的实现-面向计算机 实现层,数据的逻辑结构与存储结构,抽象数据类型,抽象数据类型(ADT) 一个数学模型以及定义在该模型上的一组操作 “抽象”是指数据类型的数学抽象特性，其定义仅仅取决于它的一组逻辑特性，而与在计算机内部的表示和实现无关,算法和算法分析,算法的概念 建立在数据结构基础上的、求解问题的一系列确切的步骤。 一个算法必须满足以下五个重要特性 有穷性：对任何合法输入执行有穷步后能结束。 确定性：每条指令必须有确切的含义。 可行性：算法的每一条指令均能执行。 输入：有零个或多个输入。 输出：有一个或多个输出。,算法的概念和特性,正确性（最重要的标准） 算法应
6、满足具体问题的需求 对于典型的、苛刻而带有刁难性的一组有效输入得到正确的结果 健壮性 算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙或随机的输出结果 可读性 算法应该好读。以有利于阅读者对程序的理解和维护 高效性：时间复杂度 算法执行占用的CPU时间，随问题规模n的变化函数 高效性：空间复杂度 算法执行占用的内存总量，随问题规模n的变化函数,评价算法优劣的基本标准,算法效率的度量,时间复杂度 空间复杂度,算法执行的时间,事后统计的方法 先运行依据算法的程序 所得时间的统计量依赖于计算机的硬件、软件等环境因素 收集此算法的执行时间和实际占用空间的统计资料。 事前分析
7、估算的方法 求出该算法的一个时间界限函数；,时间复杂度,n 问题规模，一般为数据的输入量 f(n) 算法中基本操作重复执行的次数频度 是问题规模n的某个函数 算法的时间量度、时间复杂度 算法中各语句的频度之和T(n) T(n)=O(f(n) 随问题规模的增大，执行时间的增长率和f(n)的增长率相同,时间复杂度曲线,常见的时间复杂度： O(1), O(log2n), O(n), O(n log2n), O(n2), O(n3), O(2n) O(1)O(log2n)O(n)O(nlog2n)(n2)O(n3)O(2n),空间复杂度,算法所需存储空间的度量 记作：S(n)=O(f(n) 其中n为问
8、题的规模(或大小) 存储密度d=数据本身存储量/实际所占存储量,第二章 线性表,线性结构的特点,在数据元素的非空有限集中 存在唯一的一个被称为“第一个”的数据元素 存在唯一的一个被称为“最后一个”的数据元素 除第一个之外，集合中每个数据元素均只有一个前驱 除最后一个之外，集合中每个数据元素均只有一个后继,顺序表,线性表的顺序存储结构,b b+l b+2l b+(i-1)l b+(n-1)l,顺序存储空间的获得：静态数组 在源程序中指定大小，编译时确定 运行时存储空间尺寸不可增减 有效数据限制在0-n 顺序存储空间的获得：动态申请 运行时通过malloc函数动态申请指定大小的存储空间 可以通过r
9、ealloc函数扩充或者缩小存储空间大小，但是，可能需要内存拷贝操作（开销大） 可以通过free函数释放申请的空间,线性表的顺序存储结构的优缺点,优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需要移动大量的元素； 预先分配空间需按最大空间分配，利用不充分； 表容量难以扩充,线性表的单向链式存储,线性表的链式存储结构与实现,线性表的链式存储结构 用一组任意的存储单元存储线性表的数据元素 数据元素可零散地分布在内存的任何位置上 链式存储结构的特点 链表中结点的逻辑次序和物理次序不一定相同。即：逻辑上相邻未必在物理上相邻。 结点之间的相对位置由链表中的指针域指示
10、，而结点在存储器中的存储位置是随意的。,线性表的链式存储结构,结点的组成 数据域 存放数据元素的值。 指针域（链域） 单向链表的每个结点都只有一个指针域。 存放下一个结点（直接后继）的地址 。 通过链域，可将n个结点按逻辑顺序链接在一起（不论其物理次序如何）。,单链表的类型定义,typedef struct LNode ElemType data; struct LNode *next; LNode, *LinkList;,不带头节点的单链表 struct LNode *L; 或者 LinkList L; 如果L为NULL标志空链表， 否则，L为指向链表首个元素的指针,带头节点的单链表,头结点
11、 在单链表的第一个结点之前附设的结点； 为了确定链表中第一个结点的位置而设立； 数据域可以不存储任何信息，也可以存放关于线性表的附加信息，如长度等； 尾结点 指针域为空（无后继），用NULL表示。,带头结点的单链表插入运算,具体操作,带头结点的单链表插入算法,将元素e插入到p节点之后 s = (LNode *)malloc(sizeof(LNode); s-data = e; s-next = p-next; p-next = s;,带头结点单链表的删除算法,具体操作,存储池,p q,带头结点单链表的删除算法,删除p节点之后的节点 q = p-next; if (q != NULL) p-ne
12、xt = q-next; free(q); ,不带头单链表的转置,pre = NULL; p = head; while (p != NULL) t = p-next; p-next = pre; pre = p; p = t; head = pre;,单链表的缺点,获取节点P的前驱的算法 删除节点p的算法 替换节点p的算法 在节点p之前插入新节点的算法,线性表的双向链式存储,双向链表,双链表的定义：每个节点有两个指针 typedef struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next; DuLNo
13、de, *DuLinkList;,结点的物理表示,带头结点双向循环链表的插入,将新元素e插入到双向链表中p节点前 s = (DuLNode *)malloc(sizeof(DuLNode); s-data = e; s-prior = p-prior; p-prior-next = s; s-next = p; p-prior = s;,带头结点双向循环链表的删除,删除节点p p-prior-next = p-next; p-next-prior = p-prior; free(p);,第三章 栈和队列,插入和删除操作受限的线性表,栈和队列都是线性表，只是在操作上做了限制 栈（stack） 后
14、进先出(LIFO:Last In First Out)的线性表 表头端称为栈底（bottom） 表尾端称为栈顶（top） 插入和删除都在栈顶进行 队列（queue） 先进先出(FIFO:First In First Out)的线性表 表头端称为队头（front） 表尾端称为队尾（rear） 插入在队尾进行，而删除则在队头进行,栈的定义和基本操作,栈的基本操作,InitStack( int top; 堆栈容量的设计：根据算法需要，分析算法的空间复杂度 编号系统 0(n-1)，top记载下个空位位置，或者说，元素个数 栈满和栈空（“上溢”与“下溢”）,顺序表方式的堆栈操作,#define Init
15、Stack() top = 0 #define StackEmpty() (top=0) Status push(elemType e) if (top = STACK_SIZE) return ERROR; stacktop+ = e; return OK; ,顺序表方式的堆栈操作,Status pop(elemType ,栈的链式存储结构以及操作,存储结构设计 不带头的单链表 类型定义 struct NODE ElemType data; struct NODE *next; ; struct NODE *stack; 操作算法 InitStack ClearStack: 释放所有节点 其
16、他操作：Push, Pop，StackEmpty,队列,队列的定义,队列是一种特殊的线性表 限定插入和删除操作分别在表的两端进行 具有先进先出(FIFOFirst In First Out)的特点。,队列的操作,主要操作 增加（入队） EnQueue(Q, e); 删除（出队） DeQueue(Q, 判断队列是否为空 QueueEmpty(Q) 其他操作 初始化队列InitQueue(Q) 获取队列长度 QueueLength(Q) 清除队列中的所有元素 ClearQueue(Q),队列的存储结构和实现,链表方式 顺序表方式,链式队列,链式队列的其它算法,存储结构 单链表，双向循环链表，带头节点
