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

数据结构学位考数据结构学位考复习课复习课(1)主要内容：主要内容：主要内容：主要内容：1.1.第一部分第一部分第一部分第一部分 概述概述概述概述2.2.第二部分第二部分第二部分第二部分 线性表、栈、队列线性表、栈、队列线性表、栈、队列线性表、栈、队列第一部分：第一部分：数据结构与算法的基本概念数据结构与算法的基本概念考核内容及要求：考核内容及要求：n n理解算法、算法正确性、复杂性的概念；理解算法、算法正确性、复杂性的概念；n n了解算法的时间与空间复杂性级别；了解算法的时间与空间复杂性级别；n n重点掌握数据类型、数据结构和表示、实现的重点掌握数据类型、数据结构和表示、实现的概念；概念；n n掌握抽象数据类型的说明、高级语言对抽象数掌握抽象数据类型的说明、高级语言对抽象数据类型的支持。据类型的支持。基本概念和术语基本概念和术语n n数据数据数据数据(Data)(Data)：n n数据元素数据元素数据元素数据元素(Data Element)(Data Element)：qq数据的基本单位，计算机中通常作为一个整体来考虑，如一棵树中数据的基本单位，计算机中通常作为一个整体来考虑，如一棵树中的一个结点、一个图中的一个结点。的一个结点、一个图中的一个结点。qq一个数据元素可以有若干个一个数据元素可以有若干个数据项数据项数据项数据项(Data Item)(Data Item)组成。组成。n n数据对象数据对象数据对象数据对象(Data Object)(Data Object)：性质相同的数据元素的集合性质相同的数据元素的集合n n数据结构：数据结构：数据结构：数据结构：数据元素之间的关系数据元素之间的关系结构结构qq四种基本结构四种基本结构n n集合集合 线性结构线性结构 树形结构树形结构 图状结构图状结构/网状网状结构结构qq数据结构的形式定义：数据结构的形式定义：数据结构的形式定义：数据结构的形式定义：n n一个二元组：一个二元组：一个二元组：一个二元组：Data_Structure=(D,S)Data_Structure=(D,S)其中：其中：其中：其中：D D是数据元素的集合，是数据元素的集合，是数据元素的集合，是数据元素的集合，S S是是是是D D上的关系集合上的关系集合上的关系集合上的关系集合n n数据的逻辑、物理（存储）结构数据的逻辑、物理（存储）结构qq逻辑结构：数据元素之间的逻辑关系逻辑结构：数据元素之间的逻辑关系逻辑结构：数据元素之间的逻辑关系逻辑结构：数据元素之间的逻辑关系qq物理结构：数据元素在计算机中的存储方法（表物理结构：数据元素在计算机中的存储方法（表物理结构：数据元素在计算机中的存储方法（表物理结构：数据元素在计算机中的存储方法（表现和实现）现和实现）现和实现）现和实现）n n数据结构的分类：数据结构的分类：qq按照按照按照按照逻辑结构逻辑结构逻辑结构逻辑结构的不同分为：集合、线性结构、树的不同分为：集合、线性结构、树的不同分为：集合、线性结构、树的不同分为：集合、线性结构、树状结构、网状结构状结构、网状结构状结构、网状结构状结构、网状结构qq按照按照按照按照物理结构物理结构物理结构物理结构的不同分为：的不同分为：的不同分为：的不同分为：n n顺序结构：利用在存储器中的物理关系来表示逻辑关系。顺序结构：利用在存储器中的物理关系来表示逻辑关系。顺序结构：利用在存储器中的物理关系来表示逻辑关系。顺序结构：利用在存储器中的物理关系来表示逻辑关系。n n链式结构：用在存储器中附加指针的方式来表示逻辑关链式结构：用在存储器中附加指针的方式来表示逻辑关链式结构：用在存储器中附加指针的方式来表示逻辑关链式结构：用在存储器中附加指针的方式来表示逻辑关系。系。系。系。n n算法：对特定问题求解步骤的一种描述，是指算法：对特定问题求解步骤的一种描述，是指令的有序序列令的有序序列n n算法的五个特性：有穷性、确定性、可行性、算法的五个特性：有穷性、确定性、可行性、输入、输出输入、输出n n算法设计的要求：时间复杂度，空间复杂度算法设计的要求：时间复杂度，空间复杂度n n时间复杂度：算法执行时间随规模增长而增时间复杂度：算法执行时间随规模增长而增长的趋势长的趋势 T(n)=O(f(n)f(n)算法规模，算法规模，T(n)称算法复杂度称算法复杂度 估算办法：以算法中重复执行的次数作估算办法：以算法中重复执行的次数作 为算法时间复杂度的依据。为算法时间复杂度的依据。三种最常见时间复杂度：三种最常见时间复杂度：O(1)常量级常量级 O(n)线性级线性级 O(n2)平方级平方级n n算法的空间复杂度算法的空间复杂度 S(n)=O(f(n)算法执行过程中所需的最大空间算法执行过程中所需的最大空间 估算方法：输入数据所占空间估算方法：输入数据所占空间+程序所占空间程序所占空间+辅助变量所占空间辅助变量所占空间 第二部分第二部分 线性表、栈、队列线性表、栈、队列n n考核内容及要求：考核内容及要求：考核内容及要求：考核内容及要求：qq熟练掌握顺序分配、链接分配的表示及实现方法；熟练掌握顺序分配、链接分配的表示及实现方法；熟练掌握顺序分配、链接分配的表示及实现方法；熟练掌握顺序分配、链接分配的表示及实现方法；qq熟练掌握各种链表：单链、双链、多链、循环链表；熟练掌握各种链表：单链、双链、多链、循环链表；熟练掌握各种链表：单链、双链、多链、循环链表；熟练掌握各种链表：单链、双链、多链、循环链表；qq理解栈、队列、双向队列的顺序、链式表示及其算理解栈、队列、双向队列的顺序、链式表示及其算理解栈、队列、双向队列的顺序、链式表示及其算理解栈、队列、双向队列的顺序、链式表示及其算法复杂度分析；法复杂度分析；法复杂度分析；法复杂度分析；qq熟练掌握表达式计算原理。熟练掌握表达式计算原理。熟练掌握表达式计算原理。熟练掌握表达式计算原理。1.线性表的顺序表示和实现线性表的顺序表示和实现n n线性表的存储结构：顺序存储、链接存储线性表的存储结构：顺序存储、链接存储线性表的存储结构：顺序存储、链接存储线性表的存储结构：顺序存储、链接存储n n顺序存储：用一组地址连续的存储单元依次存储线性表的顺序存储：用一组地址连续的存储单元依次存储线性表的顺序存储：用一组地址连续的存储单元依次存储线性表的顺序存储：用一组地址连续的存储单元依次存储线性表的数据元素。数据元素。数据元素。数据元素。a1a2aianbb+lb+(i-1)lb+(n-1)lb+nl存储地址存储地址存储地址存储地址存储内容存储内容存储内容存储内容顺序存储结构顺序存储结构顺序存储结构顺序存储结构基地址：起始位置基地址：起始位置基地址：起始位置基地址：起始位置第第第第i i个元素的位置个元素的位置个元素的位置个元素的位置LOC(aLOC(ai i)=LOC(a)=LOC(a1 1)+(i-1)*l)+(i-1)*ll l：每个元素占用的存储单元：每个元素占用的存储单元：每个元素占用的存储单元：每个元素占用的存储单元顺序表的特点顺序表的特点（1 1 1 1）利用数据元素的存储位置表示线性表中相邻数据元素）利用数据元素的存储位置表示线性表中相邻数据元素）利用数据元素的存储位置表示线性表中相邻数据元素）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的之间的前后关系，即线性表的之间的前后关系，即线性表的之间的前后关系，即线性表的逻辑结构于存储结构逻辑结构于存储结构逻辑结构于存储结构逻辑结构于存储结构（物理（物理（物理（物理结构）结构）结构）结构）一致一致一致一致；（2 2 2 2）在访问线性表时，可以利用上述给出的数学公式，快）在访问线性表时，可以利用上述给出的数学公式，快）在访问线性表时，可以利用上述给出的数学公式，快）在访问线性表时，可以利用上述给出的数学公式，快速计算任何一个数据元素的存储地址。即速计算任何一个数据元素的存储地址。即速计算任何一个数据元素的存储地址。即速计算任何一个数据元素的存储地址。即访问每个数据元访问每个数据元访问每个数据元访问每个数据元素所花费的时间相等素所花费的时间相等素所花费的时间相等素所花费的时间相等。（3 3 3 3）这种存取元素的方法被称为）这种存取元素的方法被称为）这种存取元素的方法被称为）这种存取元素的方法被称为随机存取随机存取随机存取随机存取法。使用这种存法。使用这种存法。使用这种存法。使用这种存取方法的存储结构被称为随机存储结构。取方法的存储结构被称为随机存储结构。取方法的存储结构被称为随机存储结构。取方法的存储结构被称为随机存储结构。表示方法表示方法表示方法表示方法：在高级语言中，用一维数组表示：在高级语言中，用一维数组表示：在高级语言中，用一维数组表示：在高级语言中，用一维数组表示：表示方法：表示方法：表示方法：表示方法：const LIST_INIT_SIZE=100;/const LIST_INIT_SIZE=100;/表初始分配空间表初始分配空间表初始分配空间表初始分配空间 const LISTINCREMENT=10;/const LISTINCREMENT=10;/空间分配增量空间分配增量空间分配增量空间分配增量 typedef struct ElemType*elem;typedef struct ElemType*elem;/存储空间存储空间存储空间存储空间 int length;/int length;/当前长度当前长度当前长度当前长度 int listsize;/int listsize;/当前存储容量当前存储容量当前存储容量当前存储容量 int LISTINCREMENT;/int LISTINCREMENT;/可增加存储空间可增加存储空间可增加存储空间可增加存储空间 SqList;SqList;注意：注意：注意：注意：1.1.数组指针数组指针数组指针数组指针elemelem指示线性表的基地址，指示线性表的基地址，指示线性表的基地址，指示线性表的基地址，length:length:线性表的当前线性表的当前线性表的当前线性表的当前长度。长度。长度。长度。2.C2.C语言数组的下标从语言数组的下标从语言数组的下标从语言数组的下标从0 0开始，即数组中的第开始，即数组中的第开始，即数组中的第开始，即数组中的第i i个元素为个元素为个元素为个元素为L.elemi-1L.elemi-12.线性表的链式表示和实现线性表的链式表示和实现n n顺序表的局限：插入、删除时要移动大量的元素，耗顺序表的局限：插入、删除时要移动大量的元素，耗顺序表的局限：插入、删除时要移动大量的元素，耗顺序表的局限：插入、删除时要移动大量的元素，耗费大量时间。费大量时间。费大量时间。费大量时间。n n链式表示：用一组链式表示：用一组链式表示：用一组链式表示：用一组任意的任意的任意的任意的存储单元存储线性表存储单元存储线性表存储单元存储线性表存储单元存储线性表qq存储单元不要求连续：物理结构不反应逻辑结构存储单元不要求连续：物理结构不反应逻辑结构存储单元不要求连续：物理结构不反应逻辑结构存储单元不要求连续：物理结构不反应逻辑结构qq不可以随机存取，但插入和删除方便不可以随机存取，但插入和删除方便不可以随机存取，但插入和删除方便不可以随机存取，但插入和删除方便qq需要两个域：一个表示数据本身；一个表示数据元素间的先需要两个域：一个表示数据本身；一个表示数据元素间的先需要两个域：一个表示数据本身；一个表示数据元素间的先需要两个域：一个表示数据本身；一个表示数据元素间的先后关联。后关联。后关联。后关联。一个一个一个一个结点结点结点结点。qq结点中表示关联的部分为指针域，内部存放指针或链。结点中表示关联的部分为指针域，内部存放指针或链。结点中表示关联的部分为指针域，内部存放指针或链。结点中表示关联的部分为指针域，内部存放指针或链。n n个个个个结点链接成一个结点链接成一个结点链接成一个结点链接成一个链表。链表。链表。链表。线性链表线性链表n n线性链表的物理存储结构线性链表的物理存储结构线性链表的物理存储结构线性链表的物理存储结构qq(Zhao,Qian,Sun,Li,Zhou,Wu,Zheng,Wang)(Zhao,Qian,Sun,Li,Zhou,Wu,Zheng,Wang)ZhaoZhaoQianQianSunSunLiLiWangWangZhengZhengWuWuZhouZhou数据域数据域数据域数据域指针域指针域指针域指针域存储地址存储地址存储地址存储地址1 17 713131919252531313737434349493131头指针头指针头指针头指针LZhaoZhaoQianQianSunSunWangWangn n线性链表（单链表）的定义：线性链表（单链表）的定义：线性链表（单链表）的定义：线性链表（单链表）的定义：typedef struct LNode typedef struct LNode ElemType data;ElemType data;struct Lnode *next;struct Lnode *next;Lnode,*LinkList Lnode,*LinkListL La a1 1a ai ia ai-1i-1a an n L La a1 1a ai ia ai-1i-1a an n n n带带带带头结点头结点头结点头结点的链表的链表的链表的链表 循环链表循环链表n n循环链表：线性表的另一种链式存储结构。循环链表：线性表的另一种链式存储结构。循环链表：线性表的另一种链式存储结构。循环链表：线性表的另一种链式存储结构。HHa1a1ananHHqq特点：特点：特点：特点：n n从表的任何位置出发，都可以找到其他结点；从表的任何位置出发，都可以找到其他结点；从表的任何位置出发，都可以找到其他结点；从表的任何位置出发，都可以找到其他结点；qq操作与单链表的差别：操作与单链表的差别：操作与单链表的差别：操作与单链表的差别：n n判断表尾的条件：判断表尾的条件：判断表尾的条件：判断表尾的条件：P-next=HP-next=H空表空表空表空表循环链表循环链表循环链表循环链表 双向链表双向链表n n每一个结点有两个指针域：一个指向直接后继；另一个指每一个结点有两个指针域：一个指向直接后继；另一个指每一个结点有两个指针域：一个指向直接后继；另一个指每一个结点有两个指针域：一个指向直接后继；另一个指向直接前驱。向直接前驱。向直接前驱。向直接前驱。Ha1a1a2a2 H 双向链表存储结构：双向链表存储结构：双向链表存储结构：双向链表存储结构：typedef struct DuLNode typedef struct DuLNode ElemType data;ElemType data;struct DuLNode *prior;struct DuLNode *prior;struct DuLNode *next;struct DuLNode *next;DuLNode,*DuLinkList;DuLNode,*DuLinkList;n n双向循环链表双向循环链表Ha1a1 a2a2 H2个结点的双向循环链表个结点的双向循环链表空的双向循环链表空的双向循环链表3.栈的表示和实现栈的表示和实现n n栈的表示：栈的表示：（1 1）顺序栈：栈的顺序存储）顺序栈：栈的顺序存储（2 2）链栈：栈的动态存储）链栈：栈的动态存储 顺序栈的表示和实现顺序栈的表示和实现 顺序表示顺序表示顺序表示顺序表示#define STACK_INIT_SIZE 100;#define STACK_INIT_SIZE 100;#define STACKINCREMENT 10;#define STACKINCREMENT 10;typedef struct typedef struct SElemType*base;SElemType*base;SElemType *top;SElemType *top;int stacksize;int stacksize;SqStack;SqStack;其中其中其中其中stacksizestacksize表示栈当前可以使用的最大容量。表示栈当前可以使用的最大容量。表示栈当前可以使用的最大容量。表示栈当前可以使用的最大容量。basebase为栈底，为栈底，为栈底，为栈底，toptop为栈顶。栈顶指针指向栈顶元素的下一个位置（即下次压为栈顶。栈顶指针指向栈顶元素的下一个位置（即下次压为栈顶。栈顶指针指向栈顶元素的下一个位置（即下次压为栈顶。栈顶指针指向栈顶元素的下一个位置（即下次压栈时元素所放的位置）栈时元素所放的位置）栈时元素所放的位置）栈时元素所放的位置）n n顺序栈的结构顺序栈的结构toptop指向压栈时下一个元素将要存放的位置。指向压栈时下一个元素将要存放的位置。指向压栈时下一个元素将要存放的位置。指向压栈时下一个元素将要存放的位置。toptop减一指向弹栈时下一个元素的取值位置。减一指向弹栈时下一个元素的取值位置。减一指向弹栈时下一个元素的取值位置。减一指向弹栈时下一个元素的取值位置。栈空的条件：栈空的条件：栈空的条件：栈空的条件：top=basetop=base栈满的条件：栈满的条件：栈满的条件：栈满的条件：top-base=stacksizetop-base=stacksizetoptopbase空栈base非空非满栈topABCABCbase满栈DE链栈的结构和表示链栈的结构和表示n n定义栈结构定义栈结构定义栈结构定义栈结构Typedef struct stack_nodeTypedef struct stack_node elemtype data;elemtype data;struct stack_node*next;struct stack_node*next;STKPTR;STKPTR;STKPTR*stk;STKPTR*stk;问：在这里为什么没有用到问：在这里为什么没有用到问：在这里为什么没有用到问：在这里为什么没有用到toptop指针？这样对栈结构指针？这样对栈结构指针？这样对栈结构指针？这样对栈结构的定义有否影响？的定义有否影响？的定义有否影响？的定义有否影响？1728S栈顶栈底4.队列的表示和实现队列的表示和实现 链式队列链式队列链式队列链式队列 typedeftypedef structstruct QnodeQnode QElemTypeQElemType data;data;structstruct QnodeQnode*next;*next;QnodeQnode,*,*QueuePtrQueuePtr;typedeftypedef structstruct QueuePtrQueuePtr front;front;QueuePtrQueuePtr rear;rear;LinkQueueLinkQueue;课堂练习：链队列的操作入对课堂练习：链队列的操作入对课堂练习：链队列的操作入对课堂练习：链队列的操作入对列、出队列列、出队列列、出队列列、出队列Q.frontQ.rear链队列结构链队列结构链队列结构链队列结构顺序队列#define MAXQSIZE 100#define MAXQSIZE 100 typedef struct typedef struct QElemType*base;QElemType*base;int front;int front;int rear;int rear;SqQueue;SqQueue;其中其中basebase为连续空间首地址，为连续空间首地址，frontfront为队首，为队首，rearrear为队为队尾。尾。为什么用循环队列来实现顺序队列？为什么用循环队列来实现顺序队列？rearfront空队front非空非满队1rearABCC满队DECfront非空非满队2Drearrearfront顺序队列的结构顺序队列的结构循环队列：循环队列：空队：初始化队列时，两个指针空队：初始化队列时，两个指针空队：初始化队列时，两个指针空队：初始化队列时，两个指针rearrearfrontfront0 0入队：队尾插入元素，尾指针入队：队尾插入元素，尾指针入队：队尾插入元素，尾指针入队：队尾插入元素，尾指针rearrear后移后移后移后移出队：队头删除元素，头指针出队：队头删除元素，头指针出队：队头删除元素，头指针出队：队头删除元素，头指针frontfront后移后移后移后移循环队列：循环队列：实现循环队列的操作：实现循环队列的操作：实现循环队列的操作：实现循环队列的操作：关键问题关键问题关键问题关键问题1 1：rearrear和和和和frontfront指针后移指针后移指针后移指针后移(Q.rear+1)mod MAXSIZE(Q.rear+1)mod MAXSIZE (Q.front+1)mod MAXSIZE(Q.front+1)mod MAXSIZEMaxsize-1 01frontrear Q.rear Q.rear 指向入队时下一个指向入队时下一个指向入队时下一个指向入队时下一个元素的存放位置元素的存放位置元素的存放位置元素的存放位置Q.frontQ.front指向出队时下一个指向出队时下一个指向出队时下一个指向出队时下一个元素的存放位置元素的存放位置元素的存放位置元素的存放位置关键问题关键问题关键问题关键问题2 2 2 2：出队时，判断空队出队时，判断空队出队时，判断空队出队时，判断空队 Q.rear=Q.frontQ.rear=Q.front;入队时，判断满队入队时，判断满队入队时，判断满队入队时，判断满队 (Q.rear+1)mod MAXSIZE=Q.front;(Q.rear+1)mod MAXSIZE=Q.front;10rearfront空队列10frontrear满队列典型例题典型例题1.1.顺序表中逻辑上相邻的元素物理位置顺序表中逻辑上相邻的元素物理位置顺序表中逻辑上相邻的元素物理位置顺序表中逻辑上相邻的元素物理位置 相邻，相邻，相邻，相邻，单链表中逻辑上相邻的元素物理位置单链表中逻辑上相邻的元素物理位置单链表中逻辑上相邻的元素物理位置单链表中逻辑上相邻的元素物理位置 相邻。相邻。相邻。相邻。2.2.已知已知已知已知P P为单链表中的非首尾结点，在为单链表中的非首尾结点，在为单链表中的非首尾结点，在为单链表中的非首尾结点，在P P结点后结点后结点后结点后插入插入插入插入S S结点的语句为：结点的语句为：结点的语句为：结点的语句为：3.在在在在单单单单链链链链表表表表中中中中，指指指指针针针针P P所所所所指指指指的的的的节节节节点点点点为为为为最最最最后后后后一一一一个个个个节节节节点点点点的条件是：的条件是：的条件是：的条件是：4.4.设设设设headhead指指指指向向向向单单单单链链链链表表表表的的的的表表表表头头头头，p p指指指指向向向向单单单单链链链链表表表表的的的的表表表表尾尾尾尾结结结结点，则执行点，则执行点，则执行点，则执行p-next=headp-next=head后，该单链表构成后，该单链表构成后，该单链表构成后，该单链表构成 P-next=NULLP-next=NULL循环链表循环链表循环链表循环链表也也也也不一定不一定不一定不一定S-next=P-next;S-next=P-next;P-next=SP-next=S2.5 2.5 画出执行下列各行语句后各指针及链表的示意图画出执行下列各行语句后各指针及链表的示意图画出执行下列各行语句后各指针及链表的示意图画出执行下列各行语句后各指针及链表的示意图L=(LinkList)malloc(sizeof(LNode);P=L;L=(LinkList)malloc(sizeof(LNode);P=L;for(i=1;i=4;i+)for(i=1;inext=(LinkList)malloc(sizeof(LNode);P-next=(LinkList)malloc(sizeof(LNode);P=P-next;P-data=i*2-1;P=P-next;P-data=i*2-1;P-next=NULL;P-next=NULL;for(i=4;i=1;i-)Ins_LinkLIst(L,i+1;i*2);for(i=4;i=1;i-)Ins_LinkLIst(L,i+1;i*2);for(i=1;i=3;i+)Del_LinkList(L,i);for(i=1;inext=P-next;S-prior=P;(2)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);(5)P-prior-next=P-next;P-next-prior=P-prior;free(R);n n设设rear是是指指向向非非空空带带头头节节点点的的单单循循环环链链表表的的尾尾指针，则写出删除表首结点的操作的语句序列指针，则写出删除表首结点的操作的语句序列答案：答案：答案：答案：P=rear-next-next;Rear-next-next=p-next;Free(P);n n2.332.332.332.33已知一个线性链表表示的线性表中含有三类字符的数已知一个线性链表表示的线性表中含有三类字符的数已知一个线性链表表示的线性表中含有三类字符的数已知一个线性链表表示的线性表中含有三类字符的数据元素（如字母、数字、和其他），试编写算法将该线性据元素（如字母、数字、和其他），试编写算法将该线性据元素（如字母、数字、和其他），试编写算法将该线性据元素（如字母、数字、和其他），试编写算法将该线性链表分割为三个循环链表，其中每个循环链表表示的线性链表分割为三个循环链表，其中每个循环链表表示的线性链表分割为三个循环链表，其中每个循环链表表示的线性链表分割为三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。表中均只含一类字符。表中均只含一类字符。表中均只含一类字符。qq要求：充分用原来的存储空间；要求：充分用原来的存储空间；要求：充分用原来的存储空间；要求：充分用原来的存储空间；qq问题：如果要求建立问题：如果要求建立问题：如果要求建立问题：如果要求建立3 3 3 3个单链表；也利用原来的存储空间个单链表；也利用原来的存储空间个单链表；也利用原来的存储空间个单链表；也利用原来的存储空间Status D_S_2.33(LinkList&L;DuLinkList&La;L;DuLinkList&Lb;Status D_S_2.33(LinkList&L;DuLinkList&La;L;DuLinkList&Lb;L;DuLinkList&Lc)L;DuLinkList&Lc)if(!(La=(DuLinkList)malloc(sizeof(DuNode)return ERROR;if(!(La=(DuLinkList)malloc(sizeof(DuNode)return ERROR;if(!(Lb=(DuLinkList)malloc(sizeof(DuNode)return ERROR;if(!(Lb=(DuLinkList)malloc(sizeof(DuNode)return ERROR;Lc=L;a=La;b=Lb;Lc=L;a=La;b=Lb;q=L;p=L-next;q=L;p=L-next;while(p)while(p)if(p-data IN if(p-data IN 字母字符集字母字符集字母字符集字母字符集)q=p;p=p-next)q=p;p=p-nextif(p-data IN if(p-data IN 数字字符集数字字符集数字字符集数字字符集)q-next=p-next;q-next=p-next;/将将将将p p结点从结点从结点从结点从L L中删除中删除中删除中删除 a-next=p;a-next=p;a=p;a=p;/将将将将p p结点插入到结点插入到结点插入到结点插入到LaLa的末尾；的末尾；的末尾；的末尾；p=q-next;/p=q-next;/重置指针重置指针重置指针重置指针p pif(p-data IN if(p-data IN 其他字符集其他字符集其他字符集其他字符集)q-next=p-next;q-next=p-next;/将将将将p p结点从结点从结点从结点从L L中删除中删除中删除中删除b-next=p;b=p;/b-next=p;b=p;/将将将将p p结点插入到结点插入到结点插入到结点插入到LbLb的末尾；的末尾；的末尾；的末尾；p=q-next /p=q-next /重置指针重置指针重置指针重置指针p p q-next=Lc;/q-next=Lc;/使使使使LcLc为循环链表为循环链表为循环链表为循环链表a-next=La;/a-next=La;/使使使使LaLa为循环链表为循环链表为循环链表为循环链表b-next=Lb;/b-next=Lb;/使使使使LbLb为循环链表为循环链表为循环链表为循环链表 n n2.22 单链表的就地逆置：利用原来的存储空间。单链表的就地逆置：利用原来的存储空间。Status D_S_2.22(LinkList&L)Status D_S_2.22(LinkList&L)p=L-next;L-next=null;p=L-next;L-next=null;while(p)while(p)q=p;p=p-next;q=p;p=p-next;答案：答案：答案：答案：q-next=L-next;L-next=q;算法设计题算法设计题 顺序表：顺序表：顺序表：顺序表：#define LIST_INIT_SIZE 100#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define LISTINCREMENT 10 typedef struct typedef struct ElemType *elem;ElemType *elem;int length;int length;int listsize;int listsize;SqList;SqList;单链表单链表单链表单链表 typedef struct Lnode typedef struct Lnode ElemType data;ElemType data;Struct Lnode Struct Lnode *next;*next;Lnode,*LinkList;Lnode,*LinkList;线性表类型定义线性表类型定义4.(2.19)4.(2.19)已知线性单链表中的元素以值递增有序排列，已知线性单链表中的元素以值递增有序排列，已知线性单链表中的元素以值递增有序排列，已知线性单链表中的元素以值递增有序排列，试写一个高效的算法，删除表中所有介于试写一个高效的算法，删除表中所有介于试写一个高效的算法，删除表中所有介于试写一个高效的算法，删除表中所有介于（mink,maxkmink,maxk）的元素。（）的元素。（）的元素。（）的元素。（*）cegioqL L(mink,maxk)=(h,o)(mink,maxk)=(h,o)查找第一个大于查找第一个大于查找第一个大于查找第一个大于minkmink的结点的结点的结点的结点P-nextP-nextP Pwhile(P-next-datanext-datanextP-nextStatus LL_DEL(LinkList&L,ElemType mink,ElemType maxk)Status LL_DEL(LinkList&L,ElemType mink,ElemType maxk)/删除大于删除大于删除大于删除大于minkmink小于小于小于小于maxkmaxk的所有元素的所有元素的所有元素的所有元素,L,L是带头结点的单链表是带头结点的单链表是带头结点的单链表是带头结点的单链表P=L;P=L;while(P-next!=NULL&while(P-next!=NULL&P-next-datanext-datanext;/P=P-next;/找出第一个大于找出第一个大于找出第一个大于找出第一个大于minkmink的元素的元素的元素的元素if P-next=NULL return error;if P-next=NULL return error;Q=P-next;Q=P-next;while(!Q&Q-datadatanext=Q-next;dispose(Q);Q=P-next;P-next=Q-next;dispose(Q);Q=P-next;/LL_DEL/LL_DELcegioqL L(mink,maxk)=(h,o)(mink,maxk)=(h,o)n n5.(2.24)5.(2.24)假设有两个按值递增有序排列的单链表假设有两个按值递增有序排列的单链表假设有两个按值递增有序排列的单链表假设有两个按值递增有序排列的单链表A A和和和和B B，编写算法归并，编写算法归并，编写算法归并，编写算法归并A A和和和和B B成成成成C C，使得，使得，使得，使得C C是按值递减有序排是按值递减有序排是按值递减有序排是按值递减有序排列（允许有值重复的结点），并且列（允许有值重复的结点），并且列（允许有值重复的结点），并且列（允许有值重复的结点），并且C C利用利用利用利用A A、B B原来的原来的原来的原来的结点空间。（结点空间。（结点空间。（结点空间。（*）35719A A46820B B43C CpqStatus UNIT_A_B(LinkList&A,&B,&C)Status UNIT_A_B(LinkList&A,&B,&C)/合并合并合并合并A A和和和和B B成成成成C C，C C利用利用利用利用A A、B B原来的结点空间。原来的结点空间。原来的结点空间。原来的结点空间。P=A-next;q=B-next;C=B,C-next=NULL;free(A);/P=A-next;q=B-next;C=B,C-next=NULL;free(A);/初始化初始化初始化初始化C CWhile(!p&!q)While(!p&!q)if(p-datadata)s=p;p=p-nextif(p-datadata)s=p;p=p-nextelses=q;q=q-nextelses=q;q=q-nexts-next=C-next;C-next=s;/ss-next=C-next;C-next=s;/s结点插入到结点插入到结点插入到结点插入到C C的首结点之前；的首结点之前；的首结点之前；的首结点之前；if(!q)p=q;if(!q)p=q;While(!p)s=p;p=p-next;s-next=C-next;C-next=sWhile(!p)s=p;p=p-next;s-next=C-next;C-next=s/UNIT_A_B/UNIT_A_B 栈与队列的相关习题栈与队列的相关习题1.1.栈与线性表的差别栈与线性表的差别栈与线性表的差别栈与线性表的差别2.2.队列与栈两种数据类型的相同点和差异队列与栈两种数据类型的相同点和差异队列与栈两种数据类型的相同点和差异队列与栈两种数据类型的相同点和差异3.(3.4)3.(3.4)分析以下算法的功能分析以下算法的功能分析以下算法的功能分析以下算法的功能(SElemType(SElemType为为为为int)int)(1)(1)Status algo1(Stack S)Status algo1(Stack S)(2)(2)intint I,n,A255;I,n,A255;(3)(3)n=0;n=0;(4)(4)while(!while(!