复习课1上海交通大学继续教育学院课件

1、复习课1上海交通大学继续教育学院,数据结构学位考复习课(1),主要内容： 1.第一部分 概述 2.第二部分 线性表、栈、队列,复习课1上海交通大学继续教育学院,第一部分：数据结构与算法的基本概念,考核内容及要求： 理解算法、算法正确性、复杂性的概念； 了解算法的时间与空间复杂性级别； 重点掌握数据类型、数据结构和表示、实现的概念； 掌握抽象数据类型的说明、高级语言对抽象数据类型的支持。,复习课1上海交通大学继续教育学院,基本概念和术语,数据(Data)： 数据元素(Data Element)： 数据的基本单位，计算机中通常作为一个整体来考虑，如一棵树中的一个结点、一个图中的一个结点。 一个数据

2、元素可以有若干个数据项(Data Item)组成。 数据对象(Data Object)：性质相同的数据元素的集合 数据结构：数据元素之间的关系结构 四种基本结构 集合 线性结构 树形结构 图状结构/网状结构 数据结构的形式定义： 一个二元组： Data_Structure=(D,S) 其中：D是数据元素的集合，S是D上的关系集合,复习课1上海交通大学继续教育学院,数据的逻辑、物理（存储）结构 逻辑结构：数据元素之间的逻辑关系 物理结构：数据元素在计算机中的存储方法（表现和实现） 数据结构的分类： 按照逻辑结构的不同分为：集合、线性结构、树状结构、网状结构 按照物理结构的不同分为： 顺序结构：利

3、用在存储器中的物理关系来表示逻辑关系。 链式结构：用在存储器中附加指针的方式来表示逻辑关系。,复习课1上海交通大学继续教育学院,算法：对特定问题求解步骤的一种描述，是指令的有序序列 算法的五个特性：有穷性、确定性、可行性、输入、输出 算法设计的要求：时间复杂度，空间复杂度,复习课1上海交通大学继续教育学院,时间复杂度：算法执行时间随规模增长而增长的趋势 T(n)=O(f(n) f(n)算法规模，T(n)称算法复杂度 估算办法：以算法中重复执行的次数作 为算法时间复杂度的依据。 三种最常见时间复杂度： O(1) 常量级 O(n) 线性级 O(n2) 平方级,复习课1上海交通大学继续教育学院,算法

4、的空间复杂度 S(n)=O(f(n) 算法执行过程中所需的最大空间 估算方法：输入数据所占空间+ 程序所占空间+ 辅助变量所占空间,复习课1上海交通大学继续教育学院,第二部分 线性表、栈、队列,考核内容及要求： 熟练掌握顺序分配、链接分配的表示及实现方法； 熟练掌握各种链表：单链、双链、多链、循环链表； 理解栈、队列、双向队列的顺序、链式表示及其算法复杂度分析； 熟练掌握表达式计算原理。,复习课1上海交通大学继续教育学院,1. 线性表的顺序表示和实现,线性表的存储结构：顺序存储、链接存储 顺序存储：用一组地址连续的存储单元依次存储线性表的数据元素。,复习课1上海交通大学继续教育学院,顺序表的特

5、点,（1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构于存储结构（物理结构）一致； （2）在访问线性表时，可以利用上述给出的数学公式，快速计算任何一个数据元素的存储地址。即访问每个数据元素所花费的时间相等。 （3）这种存取元素的方法被称为随机存取法。使用这种存取方法的存储结构被称为随机存储结构。,复习课1上海交通大学继续教育学院,表示方法： 在高级语言中，用一维数组表示： 表示方法： const LIST_INIT_SIZE=100; /表初始分配空间 const LISTINCREMENT=10;/空间分配增量 typedef struct ElemTyp

6、e *elem;/存储空间 int length; /当前长度 int listsize; /当前存储容量 int LISTINCREMENT;/可增加存储空间 SqList; 注意： 1. 数组指针elem指示线性表的基地址，length:线性表的当前长度。 2. C语言数组的下标从0开始，即数组中的第i个元素为L.elemi-1,复习课1上海交通大学继续教育学院,2. 线性表的链式表示和实现,顺序表的局限：插入、删除时要移动大量的元素，耗费大量时间。 链式表示：用一组任意的存储单元存储线性表 存储单元不要求连续：物理结构不反应逻辑结构 不可以随机存取，但插入和删除方便 需要两个域：一个表示

7、数据本身；一个表示数据元素间的先后关联。一个结点。 结点中表示关联的部分为指针域，内部存放指针或链。n个结点链接成一个链表。,复习课1上海交通大学继续教育学院,线性链表,线性链表的物理存储结构 (Zhao,Qian,Sun,Li,Zhou,Wu,Zheng,Wang),复习课1上海交通大学继续教育学院,线性链表（单链表）的定义： typedef struct LNode ElemType data; struct Lnode *next; Lnode, *LinkList,带头结点的链表,复习课1上海交通大学继续教育学院,循环链表,循环链表：线性表的另一种链式存储结构。,特点： 从表的任何位置

8、出发，都可以找到其他结点； 操作与单链表的差别： 判断表尾的条件：P-next=H,空表,循环链表,复习课1上海交通大学继续教育学院,双向链表,每一个结点有两个指针域：一个指向直接后继；另一个指向直接前驱。,双向链表存储结构： typedef struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next; DuLNode, *DuLinkList;,复习课1上海交通大学继续教育学院,双向循环链表,2个结点的双向循环链表,空的双向循环链表,复习课1上海交通大学继续教育学院,3.栈的表示和实现,栈的表示： （1）

9、顺序栈：栈的顺序存储 （2）链栈：栈的动态存储,复习课1上海交通大学继续教育学院,顺序栈的表示和实现 顺序表示 #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack; 其中stacksize表示栈当前可以使用的最大容量。base为栈底，top为栈顶。栈顶指针指向栈顶元素的下一个位置（即下次压栈时元素所放的位置）,复习课1上海交通大学继续教育学院,顺序栈的结构,top指向压栈时下一个元素将要存放的位

10、置。 top减一指向弹栈时下一个元素的取值位置。 栈空的条件：top=base 栈满的条件：top-base = stacksize,top,复习课1上海交通大学继续教育学院,链栈的结构和表示,定义栈结构 Typedef struct stack_node elemtype data; struct stack_node *next; STKPTR; STKPTR *stk; 问：在这里为什么没有用到top指针？这样对栈结构的定义有否影响？,栈顶,栈底,复习课1上海交通大学继续教育学院,4.队列的表示和实现 链式队列 typedef struct Qnode QElemType data; s

11、truct Qnode *next; Qnode, *QueuePtr; typedef struct QueuePtr front; QueuePtr rear; LinkQueue; 课堂练习：链队列的操作入对列、出队列,链队列结构,复习课1上海交通大学继续教育学院,顺序队列 #define MAXQSIZE 100 typedef struct QElemType *base; int front; int rear; SqQueue; 其中base为连续空间首地址，front为队首，rear为队尾。,复习课1上海交通大学继续教育学院,为什么用循环队列来实现顺序队列？,front,空队,

12、C,满队,D,E,C,front,非空非满队2,D,rear,rear,front,顺序队列的结构循环队列：,空队：初始化队列时，两个指针rearfront0 入队：队尾插入元素，尾指针rear后移 出队：队头删除元素，头指针front后移,复习课1上海交通大学继续教育学院,循环队列：,实现循环队列的操作： 关键问题1：rear和front指针后移 (Q.rear+1) mod MAXSIZE (Q.front+1) mod MAXSIZE,Q.rear 指向入队时下一个元素的存放位置 Q.front指向出队时下一个元素的存放位置,复习课1上海交通大学继续教育学院,关键问题2： 出队时，判断空

13、队 Q.rear = = Q.front; 入队时，判断满队 (Q.rear+1)mod MAXSIZE= = Q.front;,空队列,满队列,复习课1上海交通大学继续教育学院,典型例题,1. 顺序表中逻辑上相邻的元素物理位置 相邻， 单链表中逻辑上相邻的元素物理位置 相邻。 2. 已知P为单链表中的非首尾结点，在P结点后 插入S结点的语句为：,3. 在单链表中，指针P所指的节点为最后一个节点的条件是： 4.设head指向单链表的表头，p指向单链表的表尾结点，则执行p-next=head后，该单链表构成,P-next=NULL,循环链表,也,不一定,S-next=P-next; P-next

14、=S,复习课1上海交通大学继续教育学院,2.5 画出执行下列各行语句后各指针及链表的示意图 L=(LinkList)malloc(sizeof(LNode); P=L; for (i=1;inext=(LinkList) malloc(sizeof(LNode); P=P-next; P-data=i*2-1; P-next=NULL; for (i=4;i=1;i-) Ins_LinkLIst(L,i+1;i*2); for (i=1;i=3;i+) Del_LinkList(L,i);,复习课1上海交通大学继续教育学院,2.8 已知P结点是双向链表的中间结点，试写出下列操作的语句序列： (

15、1)在P结点后插入s结点 (2)在P结点前插入s结点 (3)删除P结点的直接后继结点 (4)删除P结点的直接前驱结点 (5)删除P结点,S-next=P-next; S-prior=P; p-next-prior=S; P-next=S;,(2) S-next=P; S-prior=P-prior; p -prior -next=S; P-prior=S;,(3) R=P-next;P-next=R-next; R-next-prior=R-prior; free(R);,(4) R=P-prior;P-prior=R-prior; R -prior -next=R-next; free(R)

16、;,(5) P-prior-next=P-next; P-next-prior=P-prior; free(R);,复习课1上海交通大学继续教育学院,设rear是指向非空带头节点的单循环链表的尾指针，则写出删除表首结点的操作的语句序列,答案： P=rear-next-next; Rear-next-next=p-next; Free(P);,复习课1上海交通大学继续教育学院,2.33已知一个线性链表表示的线性表中含有三类字符的数据元素（如字母、数字、和其他），试编写算法将该线性链表分割为三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。 要求：充分用原来的存储空间； 问题：如果要求建

17、立3个单链表；也利用原来的存储空间,复习课1上海交通大学继续教育学院,Status D_S_2.33(LinkList /使Lb为循环链表 ,复习课1上海交通大学继续教育学院,2.22 单链表的就地逆置：利用原来的存储空间。 Status D_S_2.22(LinkList ,答案： q-next=L-next; L-next=q;,复习课1上海交通大学继续教育学院,算法设计题,顺序表： #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct ElemType *elem; int length; int lists

18、ize; SqList;,单链表 typedef struct Lnode ElemType data; Struct Lnode *next; Lnode, *LinkList;,线性表类型定义,复习课1上海交通大学继续教育学院,4.(2.19) 已知线性单链表中的元素以值递增有序排列，试写一个高效的算法，删除表中所有介于（mink,maxk）的元素。（*）,(mink,maxk)=(h,o),查找第一个大于mink的结点P-next,P,while (P-next-datanext,复习课1上海交通大学继续教育学院,Status LL_DEL(LinkList /LL_DEL,(mink,

19、maxk)=(h,o),复习课1上海交通大学继续教育学院,5.(2.24) 假设有两个按值递增有序排列的单链表A和B，编写算法归并A和B成C，使得C是按值递减有序排列（允许有值重复的结点），并且C利用A、B原来的结点空间。（*）,复习课1上海交通大学继续教育学院,Status UNIT_A_B(LinkList C-next=s /UNIT_A_B,复习课1上海交通大学继续教育学院,栈与队列的相关习题,1.栈与线性表的差别 2.队列与栈两种数据类型的相同点和差异 3.(3.4)分析以下算法的功能(SElemType为int) Status algo1(Stack S) int I,n,A255

20、; n=0; while (! StackEmpty(S)n+;Pop(S,An); for (i=1;i=n;i+) Push(S,Ai); ,栈与队列,算法功能：将栈S中的元素逆置,复习课1上海交通大学继续教育学院,(2)Status algo2（Stack S,int e） Stack T; int d; InitStack(T); while (! StackEmpty(S) Pop(S,d); if (d!=e) Push(T,d); while(! StackEmpty(T) Pop(T,d); Push(S,d); ,算法功能：删除栈S中与e相等的元素,复习课1上海交通大学继续教

21、育学院,4.（3.13）简述下列算法的功能 void algo3(Queue ,算法功能：将队列Q中的元素逆置,复习课1上海交通大学继续教育学院,类型定义： 顺序栈 #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack,算法设计题,复习课1上海交通大学继续教育学院,顺序循环队列： #define MAXQSIZE 100; typedef struct QElemType *base; int front; int rear; SqQueue;,复习课1上海交通大学继续教育学院,3.15 假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。试编写实现这两个双向栈的操作的算法：初始化inistack(tws)、入栈push(tws,i,x)、出栈pop(tws,i)。并讨论按过程或函数设计这些操作算法各有什么优缺点。 分析：,Length=100; Typedef struct d