第2章 顺序表及其运算.ppt

第二章第二章第二章第二章 线性表的顺序存储及其运算线性表的顺序存储及其运算线性表的顺序存储及其运算线性表的顺序存储及其运算 2.12.12.12.1 线性表的概念线性表的概念线性表的概念线性表的概念 一、线性表的结构特性一、线性表的结构特性 二、线性表的抽象数据类型二、线性表的抽象数据类型 2.22.22.22.2 顺序表及其运算顺序表及其运算顺序表及其运算顺序表及其运算 一、什么是顺序表一、什么是顺序表 二、顺序表的运算二、顺序表的运算 2.3 2.3 2.3 2.3 栈栈栈栈 一、栈的概念一、栈的概念 二、栈的抽象数据类型二、栈的抽象数据类型 三、顺序栈及其操作实现三、顺序栈及其操作实现 四、栈应用例四、栈应用例 第二章第二章第二章第二章 线性表的顺序存储及其运算线性表的顺序存储及其运算线性表的顺序存储及其运算线性表的顺序存储及其运算2.4 2.4 2.4 2.4 队列队列队列队列 一、队列及其抽象数据类型一、队列及其抽象数据类型 二、顺序队列及其操作实现二、顺序队列及其操作实现 三、队列应用例三、队列应用例 四、优先队列四、优先队列2.5 2.5 2.5 2.5 数组与矩阵的表示数组与矩阵的表示数组与矩阵的表示数组与矩阵的表示 一、数组的顺序分配一、数组的顺序分配 二、规则矩阵的压缩存储二、规则矩阵的压缩存储 三、稀疏矩阵的三元组顺序表表示三、稀疏矩阵的三元组顺序表表示2.1 2.1 2.1 2.1 线性表的概念线性表的概念线性表的概念线性表的概念 一、线性表的结构特性一、线性表的结构特性一、线性表的结构特性一、线性表的结构特性 属性相同的数据元素按某种关系排列的表属性相同的数据元素按某种关系排列的表 例：例：农历节气表农历节气表 (立春立春,雨水雨水,惊蛰惊蛰,春分春分,清明清明,大雪大雪,冬至冬至,小寒小寒,大寒大寒)表中元素是字符表中元素是字符 抗灾衣被捐赠登记表抗灾衣被捐赠登记表 按捐赠时间先后按捐赠时间先后 (单位单位,姓名姓名,棉被棉被,棉衣裤棉衣裤,毛衣裤毛衣裤,帽类帽类 )奥运会奥运会各国家队奖牌数统计表各国家队奖牌数统计表 按金牌、银牌、铜牌数多少按金牌、银牌、铜牌数多少 (国家国家,金牌数金牌数,银牌数银牌数,铜牌数铜牌数 )表中元素为记录表中元素为记录2.1 2.1 2.1 2.1 线性表的概念线性表的概念线性表的概念线性表的概念 线性表线性表线性表线性表(Linear List)Linear List)具有相同特性数据元素的有限序列；具有相同特性数据元素的有限序列；具有相同特性数据元素的有限序列；具有相同特性数据元素的有限序列；可描述为：可描述为：B=(D,R)D=ai|i=1,2,n ;R=(ai,ai+1)|i=1,2,n-1 ；也可以简单表示为：也可以简单表示为：B=(a1,a2,ai,an)表中元素个数表中元素个数 n n 表长度表长度表长度表长度，n=0 时称为空表；时称为空表；结构特性：结构特性：结构特性：结构特性：元素之间具有线性关系元素之间具有线性关系 (元素在位置上有序元素在位置上有序)；元素在表中的位置由其序号决定；元素在表中的位置由其序号决定；表长度可变；表长度可变；2.1 2.1 2.1 2.1 线性表的概念线性表的概念线性表的概念线性表的概念二、线性表的抽象数据类型二、线性表的抽象数据类型二、线性表的抽象数据类型二、线性表的抽象数据类型 数据部分：数据部分：数据部分：数据部分：数据元素，数据元素之间的关系描述；数据元素，数据元素之间的关系描述；操作部分：操作部分：操作部分：操作部分：根据应用需要确定根据应用需要确定 按照功能可以归纳为以下基本类型：按照功能可以归纳为以下基本类型：属性设置：确定类型的基本属性值；属性设置：确定类型的基本属性值；读取属性：读取类型的属性值；读取属性：读取类型的属性值；插入：在对象的指定位置加入新的数据元素；插入：在对象的指定位置加入新的数据元素；删除：删除对象中的指定数据元素；删除：删除对象中的指定数据元素；查找：在对象查找满足条件的数据元素；查找：在对象查找满足条件的数据元素；遍历：按某种方式不重复地访问对象中所有数据元素；遍历：按某种方式不重复地访问对象中所有数据元素；关系访问：访问对象中有特定关系的元素；关系访问：访问对象中有特定关系的元素；2.1 2.1 2.1 2.1 线性表的概念线性表的概念线性表的概念线性表的概念ADT LIST 数据：数据：数据：数据：线性表线性表 L=(a0,a1,an),n0；操作：操作：操作：操作：void InitList(*L);/初始化初始化 L指向的线性表指向的线性表 ElemType GetElemlist(*L,int pos);/得到表中第得到表中第pospos个元素个元素 int FindList(*L,ElemType item);/查找给定关键字元素查找给定关键字元素 /修改表中指定元素修改表中指定元素 int ModifyList(*L,ElemType item);2.1 2.1 2.1 2.1 线性表的概念线性表的概念线性表的概念线性表的概念 int InsertList(*L,ElemType item);/向表中插入元素向表中插入元素 int DeleteList(*L,ElemType item);/删除表中元素删除表中元素 int LenthList(*L);/求表的长度求表的长度 void SortList(*L);/按关键字值对表元素排序按关键字值对表元素排序 void TraverseList(*L);/对表进行遍历并输出对表进行遍历并输出 void ClearList (*L);/清除表中所有元素清除表中所有元素 2.2 2.2 2.2 2.2 顺序表及其运算顺序表及其运算顺序表及其运算顺序表及其运算 一、什么是顺序表一、什么是顺序表一、什么是顺序表一、什么是顺序表 顺序表顺序表顺序表顺序表线性表的顺序存储线性表的顺序存储线性表的顺序存储线性表的顺序存储（向量式存储向量式存储向量式存储向量式存储）存储方法存储方法:表中元素按逻辑顺序依次放在连续存储空间中表中元素按逻辑顺序依次放在连续存储空间中;每个元素所占存储单元长度相同；每个元素所占存储单元长度相同；例：例：利用数组实现线性表的顺序存储利用数组实现线性表的顺序存储,要求：要求：数组长度数组长度 表长度表长度 表中元素地址计算：表中元素地址计算：ADR(ai)=ADR(a1)+(i-1)*k k为每个元素所占字节数；为每个元素所占字节数；a1 an-1 a2 a3 an :a41234:n 2.2 2.2 2.2 2.2 顺序表及其运算顺序表及其运算顺序表及其运算顺序表及其运算 二、二、顺序表的运算顺序表的运算顺序表的运算顺序表的运算 若对表示顺序表的数组空间采用动态分配，若对表示顺序表的数组空间采用动态分配，对顺序表结构作如下定义：对顺序表结构作如下定义：#define MaxSize 100 typedef struct ElemType listMaxSize ;/存储线性表的数组存储线性表的数组 int len;/线性表长度线性表长度 SeqList；数据结构操作的实现与具体的存储结构有关数据结构操作的实现与具体的存储结构有关 以下考虑以以下考虑以SeqList为类型的顺序表基本操作为类型的顺序表基本操作（运算运算）的实现的实现 最基本的操作最基本的操作最基本的操作最基本的操作（运算运算运算运算）：(1)(1)在表中插入一个元素在表中插入一个元素在表中插入一个元素在表中插入一个元素 (2)(2)删除表中某个元素删除表中某个元素删除表中某个元素删除表中某个元素 2.2 2.2 2.2 2.2 顺序表及其运算顺序表及其运算顺序表及其运算顺序表及其运算 1.1.1.1.顺序表初始化顺序表初始化顺序表初始化顺序表初始化 为存储线性表动态分配数组空间，置初始线性表为空为存储线性表动态分配数组空间，置初始线性表为空 void InitList(SeqList*L )/动态分配存储空间动态分配存储空间 L-List=(ElemType*)malloc(MaxSize*sizeof(ElemType)；if(!L-list)printf(Memory allocation failure!n)；exit(1)；L-len=0；/置初始线性表为空置初始线性表为空 2.2.2.2.顺序表的插入运算顺序表的插入运算顺序表的插入运算顺序表的插入运算 在表中第在表中第 i个位置插入一个元素个位置插入一个元素 item 设表长为设表长为 len 插入前：插入前：A=(a0,a1,ai-1,ai,alen-1)表长为表长为 len 插入后：插入后：A=(a 0,a 1,a i-1,a a i i,a i+1,a len)表长为表长为 len+1 表首元素位置不变，表向后增长表首元素位置不变，表向后增长表首元素位置不变，表向后增长表首元素位置不变，表向后增长 ak 0 k i A与与A 的关系：的关系：a k=item k=i ak-1 i len=MaxSeze)/若表空间满，不能插入若表空间满，不能插入 printf(表满！n)；exit(1)；if(i L-len-1)i=L-len；for(j=L-len-1;j=i;j-)L-list j+1=L-list j；L-list i=item；L-len+；2.2 2.2 2.2 2.2 顺序表及其运算顺序表及其运算顺序表及其运算顺序表及其运算 算法分析：算法分析：算法分析：算法分析：时间复杂度：时间复杂度：时间复杂度：时间复杂度：决定本算法执行时间的主要操作：决定本算法执行时间的主要操作：数据元素移动次数；数据元素移动次数；数据元素移动次数；数据元素移动次数；设表长为设表长为n，表中第表中第i个位置插入，移动个位置插入，移动元素次数为：元素次数为：n i 设在各位置插入数据元素的概率为设在各位置插入数据元素的概率为Pi ，平均移动次为：平均移动次为：设各位置插入的概率相等，即：设各位置插入的概率相等，即：Pi=1/(n+1)，则有：则有：即：插入一元素的时间复杂度为：即：插入一元素的时间复杂度为：O(O(n n)空间复杂度：空间复杂度：空间复杂度：空间复杂度：原地工作原地工作原地工作原地工作(in place)思考：思考：思考：思考：在有序顺序表中插入一个数据元素，在有序顺序表中插入一个数据元素，在有序顺序表中插入一个数据元素，在有序顺序表中插入一个数据元素，算法？算法？算法？算法？2.2 2.2 2.2 2.2 顺序表及其运算顺序表及其运算顺序表及其运算顺序表及其运算 3.3.顺序表的删除运算顺序表的删除运算顺序表的删除运算顺序表的删除运算 在表中删除第在表中删除第pos个元素个元素 删除前删除前：(b0，b1，b bi i ，b bi+1i+1，bn-1)表长为表长为 n；删除后删除后：(b0，b1，b bi-1i-1，b bi+1i+1，bn-2)表长为表长为 n-1；算法考虑：算法考虑：算法考虑：算法考虑：表空表空(L-len=0)不能做删除不能做删除 下溢处理下溢处理；指定的删除位置不存在，要处理；指定的删除位置不存在，要处理；正常删除操作，表长正常删除操作，表长 n 减减 1；算法描述：算法描述：算法描述：算法描述：参考教材参考教材 算法分析：算法分析：算法分析：算法分析：与插入运算类似；与插入运算类似；平均时间复杂度：平均时间复杂度：O(n)；空间复杂度：空间复杂度：原地工作原地工作 思考：思考：思考：思考：在有序顺序表中删除指定元素，在有序顺序表中删除指定元素，在有序顺序表中删除指定元素，在有序顺序表中删除指定元素，算法？算法？算法？算法？2.2 2.2 2.2 2.2 顺序表及其运算顺序表及其运算顺序表及其运算顺序表及其运算4.4.顺序表的查找顺序表的查找顺序表的查找顺序表的查找从线性表中查找具有给定值的第一个元素从线性表中查找具有给定值的第一个元素设设L为无序表，实现算法：为无序表，实现算法：int FindList(SeqList*L,ElemType item)int i;for(i=0;ilen;i+)if (L-list i=item)return i;return-1;/-1查找失败标志查找失败标志 思考：思考：思考：思考：若若若若 L L为有序表，实现算法？为有序表，实现算法？为有序表，实现算法？为有序表，实现算法？2.2 2.2 2.2 2.2 顺序表及其运算顺序表及其运算顺序表及其运算顺序表及其运算 算法复杂度：算法复杂度：算法复杂度：算法复杂度：时间复杂度：时间复杂度：算法运行时间主要由比较元素的次数决定，当查找算法运行时间主要由比较元素的次数决定，当查找 元素在表中第元素在表中第 i 个位置时，其比较次数为：个位置时，其比较次数为：i+1 设表长为设表长为 n，若表中各元素被查找的概率相等，元素值不等若表中各元素被查找的概率相等，元素值不等，则查找一个元素的平均比较次数为：则查找一个元素的平均比较次数为：若没有查到所查元素若没有查到所查元素（查找失败查找失败）比较次数为比较次数为：n 即：即：其时间复杂度为其时间复杂度为：O(O(n n)空间复杂度：空间复杂度：原地工作原地工作原地工作原地工作(in place)in place)其他运算其他运算其他运算其他运算(操作操作操作操作)算法参考教材算法参考教材算法参考教材算法参考教材 2.2 2.2 2.2 2.2 顺序表及其运算顺序表及其运算顺序表及其运算顺序表及其运算 顺序表的主要优点顺序表的主要优点顺序表的主要优点顺序表的主要优点 ：容易实现容易实现；直观、易理解；直观、易理解；顺序表的限制：顺序表的限制：顺序表的限制：顺序表的限制：对存储对存储空间有要求；空间有要求；插入、删除操作的效率较低插入、删除操作的效率较低；2.3 2.3 2.3 2.3 栈栈栈栈 一、什么是栈一、什么是栈一、什么是栈一、什么是栈(Stack)Stack)问题问题问题问题1 1：要求正、逆过程保证严格的相反顺序要求正、逆过程保证严格的相反顺序 例：例：进入大沙漠考察与原路返回：进入大沙漠考察与原路返回：标志点标志点1标志点标志点1标志点标志点1标志点标志点2标志点标志点2标志点标志点3返返返返：返返返返1 1返返返返2 2返返返返3 3返返返返4 4标志点标志点1标志点标志点1标志点标志点1标志点标志点1标志点标志点2标志点标志点2标志点标志点2标志点标志点3标志点标志点3标志点标志点4进进进进：过过过过4 4过过过过3 3过过过过2 2过过过过1 12.3 2.3 2.3 2.3 栈栈栈栈 问题问题问题问题2 2 2 2：多级中断的进入与返回多级中断的进入与返回 假设某系统执行时遇有假设某系统执行时遇有4级中断，其保护各级中断现场与恢复级中断，其保护各级中断现场与恢复 现场的过程为：现场的过程为：(打印机打印机)(磁盘磁盘)(采集卡采集卡)(电源电源)1级中断级中断 2级中断级中断 3级中断级中断 4级中断级中断 保存现场保存现场1 保存现场保存现场2 保存现场保存现场3 a:b:c:end return return return 2.3 2.3 2.3 2.3 栈栈栈栈 为保证中断正确执行，须依次记住每层中断的现场及返回地址；为保证中断正确执行，须依次记住每层中断的现场及返回地址；进入中断进入中断进入中断进入中断 当各层中断当各层中断“返回返回”时，则要按记入的相反次序逐个恢复现场继时，则要按记入的相反次序逐个恢复现场继续执行；续执行；中断返回中断返回中断返回中断返回 现场现场1现场现场1现场现场2现场现场3现场现场2现场现场1现场现场1现场现场1现场现场22.3 2.3 2.3 2.3 栈栈栈栈 从从上述表的特点看上述表的特点看栈的结构特性栈的结构特性：表中元素有序表中元素有序线性表线性表 元素进入与退出顺序相反元素进入与退出顺序相反特殊性特殊性 栈栈栈栈限制插入、删除操作只能在一端进行的特殊线性表限制插入、删除操作只能在一端进行的特殊线性表限制插入、删除操作只能在一端进行的特殊线性表限制插入、删除操作只能在一端进行的特殊线性表 表中允许进行插入、删除操作的一端表中允许进行插入、删除操作的一端栈顶，栈顶，另一端另一端栈底；栈底；如：如：(a1，a2，a3，a4，an-1)栈底栈底 栈顶栈顶 栈结构特性：栈结构特性：栈结构特性：栈结构特性：栈中元素后进先出栈中元素后进先出(LIFO)结论：结论：可用于记忆正、逆顺序；可用于记忆正、逆顺序；2.3 2.3 2.3 2.3 栈栈栈栈 二、栈的抽象数据类型二、栈的抽象数据类型二、栈的抽象数据类型二、栈的抽象数据类型 ADT Stack 数据：数据：数据：数据：栈栈S 以以Stack 为存储类型；为存储类型；操作：操作：操作：操作：void Initstack(*s);/初始化初始化S指向的栈指向的栈 void Push(*s,ElemType item);/元素进栈元素进栈 ElemType Pop(*s);/元素退栈元素退栈 ElemType GetTop(*s);/读取栈顶元素值读取栈顶元素值 int Emptype Stack(*s);/判断栈是否空判断栈是否空 int FullStack(*s);/判断栈是否满判断栈是否满 void ClearStack(*s);/清空栈清空栈 2.3 2.3 2.3 2.3 栈栈栈栈 三、顺序栈三、顺序栈三、顺序栈三、顺序栈 栈的顺序存储栈的顺序存储顺序栈顺序栈 最先入栈的元素最先入栈的元素最先入栈的元素最先入栈的元素栈底栈底栈底栈底 最后入栈的元素最后入栈的元素最后入栈的元素最后入栈的元素栈顶栈顶栈顶栈顶 假定：以数组假定：以数组 stack MaxSize 存储栈，存储栈，数组空间采用动态分配；数组空间采用动态分配；用用 top 指示栈顶位置，指示栈顶位置，定义定义顺序栈顺序栈 SeqStack 的结构类型为：的结构类型为：#define MaxSize 100 typedef struct ElemType stackMaxSize；int top；SeqStack；a0 0a1 1:an-1如如：m-1栈底栈底top 栈顶栈顶2.3 2.3 2.3 2.3 栈栈栈栈 设定初始栈空设定初始栈空 top=-1，栈满栈满 top=MaxSize 1,考虑考虑顺序栈操作实现：顺序栈操作实现：1.1.1.1.栈初始化栈初始化栈初始化栈初始化 v void InitStack(SeqStack*s)s-stack=(ElemTpye*)malloc(MaxSize*sizeof(ElemType);if(!s-stack)printf(Memory allocation failure!n);exit(1);s-top=-1;/置栈空置栈空 2.3 2.3 2.3 2.3 栈栈栈栈 2.2.2.2.进栈操作进栈操作进栈操作进栈操作（入栈）（入栈）（入栈）（入栈）void Push(SeqStack*s,Elemtype item)if(s-top=MaxSize-1)/检查栈中是否还有空间检查栈中是否还有空间 printf(Stack Overflow!n“);exit(1);s-top+;/移动栈顶指针，使其指向新的栈顶位置移动栈顶指针，使其指向新的栈顶位置 s-stacks-top=item;/新元素入栈新元素入栈 注意注意注意注意:栈初始设定栈初始设定(初始化初始化)与运算操作保持一致。与运算操作保持一致。stack MaxSize为为栈空间，初始栈空间，初始 top=-1(开口开口“向上向上”)，也可以设，初始初始 top=MaxSize(开口开口“向下向下”)。若发现栈满，也可做动态扩大栈空间处理，如：若发现栈满，也可做动态扩大栈空间处理，如：if (s-top=s-MaxSize-1)AllocatStack(s);2.3 2.3 2.3 2.3 栈栈栈栈 3.3.3.3.退栈操作退栈操作退栈操作退栈操作 ElemType Pop(SeqStack*s)if(s-top=-1 /检查栈是否空检查栈是否空printf(Stack is empty!n);exit(1);s-top-;/栈顶指针退栈顶指针退1 1，使其指向新的栈顶位置，使其指向新的栈顶位置 return s-stacks-top+1 /返回栈顶元素值返回栈顶元素值 进栈、退栈操作的时间复杂度为进栈、退栈操作的时间复杂度为 O(1)4.4.读取栈顶元素值读取栈顶元素值读取栈顶元素值读取栈顶元素值ElemType GetTop(SeqStack*s)实现与退栈操作相似，只是不删除栈顶元素实现与退栈操作相似，只是不删除栈顶元素(栈顶指针不移动栈顶指针不移动)2.3 2.3 2.3 2.3 栈栈栈栈 5.5.清空栈清空栈清空栈清空栈 void ClearStack(SeqStack*s)s-top=-1;思考：思考：思考：思考：(1)如果上述存储栈空间不变如果上述存储栈空间不变,但设初始时但设初始时 top=MaxSize，栈栈满、栈空如何判断？满、栈空如何判断？进栈、退栈指针如何变化？进栈、退栈指针如何变化？(2)如果上述存储类型不变如果上述存储类型不变,初始时设初始时设 top=0,操作实现又有何变化？操作实现又有何变化？2.3 2.3 2.3 2.3 栈栈栈栈 6.6.6.6.双栈操作双栈操作双栈操作双栈操作 适用情况：适用情况：适用情况：适用情况：需要同时使用两个栈需要同时使用两个栈 方方方方 法：法：法：法：两个栈共同开辟一个存储空间，栈底设于两端两个栈共同开辟一个存储空间，栈底设于两端如如:优优优优 点点点点:两栈互补余缺两栈互补余缺,充分利用存储空间；充分利用存储空间；必要时可以定义其结构类型，定义和实现其操作；必要时可以定义其结构类型，定义和实现其操作；思考：思考：思考：思考：操作实现？操作实现？操作实现？操作实现？b1b2bs ana2a1栈栈2 2底底 栈栈2 2顶顶top2top2栈栈1 1顶顶top1top1栈栈1 1底底2.32.32.32.3 栈栈栈栈四、栈应用四、栈应用四、栈应用四、栈应用 1.1.1.1.用栈记忆处理层次用栈记忆处理层次用栈记忆处理层次用栈记忆处理层次 例，程序中括弧匹配检查例，程序中括弧匹配检查例，程序中括弧匹配检查例，程序中括弧匹配检查 程序的嵌套结构通常用多重大括弧来表示，一对括弧表示一层程序的嵌套结构通常用多重大括弧来表示，一对括弧表示一层 例如：例如：while(条件条件1 1)while(条件条件2)while(条件条件3)2.32.32.32.3 栈栈栈栈 序号序号 1 2 3 4 5 6 各个括弧的出现顺序为：各个括弧的出现顺序为：编译程序检查程序嵌套正确性的方法是：编译程序检查程序嵌套正确性的方法是：每遇一个左括弧，即每遇一个左括弧，即“期望期望”有一个右括弧出现与其匹配；有一个右括弧出现与其匹配；当出现一右括弧，将其与在它之前距离最近的左括弧匹配当出现一右括弧，将其与在它之前距离最近的左括弧匹配;即，最后出现的左括弧与在之其后最先出现的右括弧匹配；即，最后出现的左括弧与在之其后最先出现的右括弧匹配；实现实现实现实现:设置一个栈置为空，重复做：设置一个栈置为空，重复做：若读入为若读入为“”入栈；入栈；若读入为若读入为“”，栈不空栈不空,且且栈顶为栈顶为“”出栈；出栈；否则，匹配有错；否则，匹配有错；扫描结束时，栈应为空，否则括弧不匹配；扫描结束时，栈应为空，否则括弧不匹配；2.32.32.32.3 栈栈栈栈112toptop 初始栈空：初始栈空：思考：思考：算法描述？算法描述？算法描述？算法描述？toptop 1 2 3 1 2 1 遇括弧遇括弧 6 遇括弧遇括弧 1 遇括弧遇括弧 2 遇括弧遇括弧 3 遇括弧遇括弧 4 遇括弧遇括弧 5 toptop2.3 2.3 2.3 2.3 栈栈栈栈 例，例，例，例，印刷电路板布线问题印刷电路板布线问题印刷电路板布线问题印刷电路板布线问题 判断在印刷电路板的一面上设定的布线是否有交叉判断在印刷电路板的一面上设定的布线是否有交叉(短路短路)给定印刷板的矩形分布区，引脚在外围如图给定印刷板的矩形分布区，引脚在外围如图(a)所示所示(a)(b)(c)若给定连线的引脚对若给定连线的引脚对:(1,4),(2,3),(5,8),(6,7)判断能否合理布线判断能否合理布线?1 26 534871 26 534871 26 534872.32.32.32.3 栈栈栈栈 判断办法：判断办法：判断办法：判断办法：对每条引线检查是否有其他引线的两个引脚跨越其对每条引线检查是否有其他引线的两个引脚跨越其 划分的两个分区，对有其他引线划分的各层子分区做同样检查划分的两个分区，对有其他引线划分的各层子分区做同样检查 实现方法：实现方法：实现方法：实现方法：对所有引脚顺序编号对所有引脚顺序编号;设置一个栈设置一个栈,依次读入各引脚编号依次读入各引脚编号,并做并做:若栈空若栈空,所读引脚号入栈所读引脚号入栈;若栈不空若栈不空,栈顶引脚号与读入号属于一条引线栈顶引脚号与读入号属于一条引线,栈顶号退栈栈顶号退栈 若栈不空，且栈顶号与读入号不属一条引线，读入号入栈若栈不空，且栈顶号与读入号不属一条引线，读入号入栈 读入全部引脚号并处理完成后，若栈空则可布线，否则需调整读入全部引脚号并处理完成后，若栈空则可布线，否则需调整 如：如：读入引脚读入引脚1 读入引脚读入引脚2 2 读入引脚读入引脚3 3 读入引脚读入引脚4 41121toptoptoptop2.3 2.3 2.3 2.3 栈栈栈栈 例，例，例，例，算术表达式求值算术表达式求值算术表达式求值算术表达式求值 (1)(1)直接计算中缀表示式直接计算中缀表示式直接计算中缀表示式直接计算中缀表示式 中缀表示式中缀表示式 运算符位于两个操作数之间：运算符位于两个操作数之间：(a+b)*c;确定运算符的优先数确定运算符的优先数：运算符运算符运算符运算符:*/+-();优先数优先数优先数优先数:4 3 3 2 2 1 1 0 定义定义定义定义:操作数栈操作数栈操作数栈操作数栈，初始空初始空 记忆表达式中的操作数；记忆表达式中的操作数；运算符栈运算符栈运算符栈运算符栈，初始有结束符，初始有结束符“;”“;”记忆表达式中的运算符；记忆表达式中的运算符；从左向右扫描表达式从左向右扫描表达式 ，根据运算规则确定处理方法：，根据运算规则确定处理方法：操作数操作数入操作数栈；入操作数栈；扫描到的运算符优先级扫描到的运算符优先级 栈顶运算符优先级，运算符入栈；栈顶运算符优先级，运算符入栈；否则，处理栈顶运算符；否则，处理栈顶运算符；括弧、结束符单独处理；括弧、结束符单独处理；2.3 2.3 2.3 2.3 栈栈栈栈 (2)(2)后缀表达式求值后缀表达式求值后缀表达式求值后缀表达式求值 后缀表达式后缀表达式 逆波兰式；逆波兰式；后缀表示式的特点：后缀表示式的特点：运算符跟在运算对象之后；运算符跟在运算对象之后；不含括号；不含括号；中缀表示式中缀表示式 后缀表示式转换规则：运算符置于操作数之后后缀表示式转换规则：运算符置于操作数之后 例：例：中缀表达式：中缀表达式：X-Y 后缀表示式为：后缀表示式为：XY-中缀表达式：中缀表达式：X*Y-Z 后缀表示式为：后缀表示式为：XY*Z-中缀表达式：中缀表达式：X*(Y-Z)后缀表示式为：后缀表示式为：XYZ-*中缀表达式：中缀表达式：X-Y*(Z+U)/V 后缀表示式为：后缀表示式为：XYZU+*V/-2.3 2.3 2.3 2.3 栈栈栈栈计算后缀表示式的算法思路：计算后缀表示式的算法思路：计算后缀表示式的算法思路：计算后缀表示式的算法思路：设后缀表达式以设后缀表达式以 “；”结束，结束，操作数栈操作数栈操作数栈操作数栈 S S 初始为空；初始为空；从左到右依次扫描后缀表达式的每个词从左到右依次扫描后缀表达式的每个词 W，重复做：重复做：若若W为操作数，为操作数，W 进栈进栈 S，继续扫描下个词；继续扫描下个词；若若W为运算符，从栈为运算符，从栈 S 中依次退栈两个操作数中依次退栈两个操作数x、y，设当前运算符为设当前运算符为，则做则做 y x,结果入栈结果入栈 S，继续扫描；继续扫描；重复上述过程，直至扫描到结束符重复上述过程，直至扫描到结束符“；”，结果在栈结果在栈 S 中；中；如如,计算计算:A+B*(C-D)/E；ABCD-*E/+；2.32.32.32.3 栈栈栈栈 2.2.栈与回溯法栈与回溯法栈与回溯法栈与回溯法例，求解简单背包问题例，求解简单背包问题例，求解简单背包问题例，求解简单背包问题 设有总容量为设有总容量为T的背包和的背包和n 件体积分别为件体积分别为w w1 1,w,w2 2,w wn的物品，的物品，要求找出使其中的若干件物品正好装满背包的所有解。要求找出使其中的若干件物品正好装满背包的所有解。求解思路：求解思路：求解思路：求解思路：回溯法回溯法 逐件试装逐件试装逐件试装逐件试装 步骤：步骤：把把 n 件物品排列；件物品排列；若背包能容纳物品，依次将各物品装入背包；若背包能容纳物品，依次将各物品装入背包；当背包不能容纳某件物品时，放弃，继续选取下一件试；当背包不能容纳某件物品时，放弃，继续选取下一件试；若剩余物品中找不到合适物品，取出最后放入物品，若剩余物品中找不到合适物品，取出最后放入物品，继续选取下一件试；继续选取下一件试；重复重复 、，至求得所有解，或无解；至求得所有解，或无解；1 2 3 n2.32.32.32.3 栈栈栈栈 0 1 2 3 4 物体编号物体编号 i设：设：T=8，5 件物体体积分别为：件物体体积分别为：1,5,3,4,2 体积体积v(i)回溯回溯利用栈实现利用栈实现 有解：有解：(1,5,2)，(1,3,4)，(5,3)栈栈栈栈中状态：中状态：0 0 2 2 3 3 0 0 3 4 0 0 2 2 4 0 0 3 4 1 1 2 2 0 0 1 1 4 4 1 1 4 2 2 3 2 4 3 3 4 3 4栈空栈空取最后一件取最后一件 4 1 1 22.32.32.32.3 栈栈栈栈1 1 求得第求得第1 1组解的过程组解的过程:T=8,v(i):1,5,3,4,2 3 35 51 14 45 51 15 51 12 25 51 1 2.32.32.32.3 栈栈栈栈 参考算法：参考算法：参考算法：参考算法：void knapsack(int w,int T,int n)/w0wn-1 n 件物品体件物品体积积 int i=0;/从编号为从编号为0的物品开始试装的物品开始试装 InitStack(S);/栈初始化栈初始化 while(!EmptyStack(s)&i!=n)while(T0&i=0)/第第i 件物品可选件物品可选 Push(S,i);T-=wi;/i 入栈，给出背包剩余体入栈，给出背包剩余体积积 i+;/试装的下一物品试装的下一物品 if(T=0)输出栈中元素；/输出得到的一组解输出得到的一组解 i=Pop(S);T+=wi;/回溯，回溯，回溯，回溯，求栈顶物品退栈后背包的剩余体积求栈顶物品退栈后背包的剩余体积 i+;/继续试装下一物品继续试装下一物品 2.3 2.3 2.3 2.3 栈栈栈栈3.3.栈与递归栈与递归栈与递归栈与递归(1)(1)递归的概念递归的概念递归的概念递归的概念递推思路：递推思路：递推思路：递推思路：从初始条件出发，逐次推出结果从初始条件出发，逐次推出结果 (如：求如：求 n!)递归思路：递归思路：递归思路：递归思路：由算法自身到达递归边界由算法自身到达递归边界 (递归终止条件递归终止条件)递归方法用于解决：递归方法用于解决：递归方法用于解决：递归方法用于解决：可分解为结构自相似的问题可分解为结构自相似的问题结构自相似的问题结构自相似的问题构成问题的部分与问题本身结构相似构成问题的部分与问题本身结构相似 求解过程：求解过程：求解过程：求解过程：原问题原问题 递归求子问题递归求子问题 递归求更小子问题递归求更小子问题 有直接解或已知条件有直接解或已知条件 逆过程逐步回代求出结果逆过程逐步回代求出结果逆过程逐步回代求出结果逆过程逐步回代求出结果递归算法的表现形式：递归算法的表现形式：递归算法的表现形式：递归算法的表现形式：自己调用自己自己调用自己 (直接或间接直接或间接)递归算法的优点：递归算法的优点：递归算法的优点：递归算法的优点：结构清晰、简练结构清晰、简练 有直接解法的特殊情况有直接解法的特殊情况 始基始基与原问题与原问题“相似相似”的子问题的子问题 递递归归问题特点：问题特点：问题特点：问题特点：可分解为可分解为2.3 2.3 2.3 2.3 栈栈栈栈 (2)(2)分治法与递归分治法与递归分治法与递归分治法与递归 分治法的求解步骤分治法的求解步骤分治法的求解步骤分治法的求解步骤:划分划分划分划分:原问题原问题(规模规模n)划分为划分为k个个 子问题子问题(规模大致相等)；求解子问题：求解子问题：求解子问题：求解子问题：子问题解法经常与原问题相同子问题解法经常与原问题相同；合并：合并：合并：合并：合并各子问题的解合并各子问题的解;伪码描述：伪码描述：DividConquer(P)/求解规模为求解规模为n n的问题的问题 P if(P的规模足够小的规模足够小)直接求解直接求解 P;else 分解为分解为k个子问题个子问题 P1,P2,Pk;for(i=1;i=k;i+)yi=DividConquer(Pi);/求解子问题求解子问题 return Merger(y1,y2,yk)/合并子问题解得到原问题解合并子问题解得到原问题解 2.3 2.3 2.3 2.3 栈栈栈栈由分治法产生的子问题往往是原问题的较小模式由分治法产生的子问题往往是原问题的较小模式 ，即：，即：子问题与原问题求解方法相同，亦即：子问题与原问题求解方法相同，亦即：子问题与原问题求解方法相同，亦即：子问题与原问题求解方法相同，亦即：问题具有结构自相似的特征问题具有结构自相似的特征问题具有结构自相似的特征问题具有结构自相似的特征 适合采用递归算法解决；适合采用递归算法解决；适合采用递归算法解决；适合采用递归算法解决；结论：结论：结论：结论：分治策略与递归方法经常同时用于算法设计中分治策略与递归方法经常同时用于算法设计中分治策略与递归方法经常同时用于算法设计中分治策略与递归方法经常同时用于算法设计中例例例例，求数组中最大元素的递归算法求数组中最大元素的递归算法求数组中最大元素的递归算法求数组中最大元素的递归算法 思路描述：思路描述：思路描述：思路描述：if(待选元素个数待选元素个数2)选出大者；递归返回；选出大者；递归返回；else 对分选择元素；对分选择元素；递归选出前半部最大元素递归选出前半部最大元素 j；递归选出前半部最大元素递归选出前半部最大元素 k；比较比较 j、k；并返回大者并返回大者；2.3 2.3 2.3 2.3 栈栈栈栈算法描述算法描述算法描述算法描述:int Select_Max(int a,int low,int high)/找找alow ahigh中最大者中最大者 int mid,j,k;if(high-low=1)/只有两个元素返回大者只有两个元素返回大者,只有一个元素返回自身只有一个元素返回自身 if(alowk)return j;/返回两部分的最大元素返回两部分的最大元素 else return k;2.3 2.3 2.3 2.3 栈栈栈栈 (3)(3)递归算法设计的基本思路递归算法设计的基本思路递归算法设计的基本思路递归算法设计的基本思路 对于递归定义的问题，可根据定义得到递归算法对于递归定义的问题，可根据定义得到递归算法对于递归定义的问题，可根据定义得到递归算法对于递归定义的问题，可根据定义得到递归算法 例例例例6 6 6 6，