实用数据结构电子教案数组与线性表省公共课一等奖全国赛课获奖课件.pptx

数据结构第二章 数组与线性表第1页第二章 数组与线性表 知 识 点 数组基本特点及寻址方式线性数据结构基本特征和基本运算堆栈定义和基本运算队列定义和基本运算循环队列特征，运算以及判断溢出条件与普通队列差异堆栈、队列简单应用 难 点 循环队列特点及判断溢出条件利用本章基本知识设计有效算法处理与线性相关应用问题 第二章 数组与线性表第2页要 求 熟练掌握以下内容：线性表基本运算堆栈特征、基本运算并能设计简单算法队列、循环队列特征、基本运算并能设计简单算法 了解以下内容：线性表运算时间复杂性分析堆栈、队列实际应用 第二章 数组与线性表第3页第二章目录2.1 数组及其次序存放结构2.2 线性表及其运算 2.3 堆栈及其应用2.4 队列及其应用2.5 应用实例及分析小 结习题与练习第二章 数组与线性表第4页2.1.1 数组数组是由一些单元组成，每个单元对应着一组下标值和一个数组元素。n维数组每个单元对应n个下标值。数组元素能够是基本数据类型，如整数型、实数型、字符型等，也能够是有多个数据项一个结构。同一数组中各个元素必须是同一数据类型，每个数组元素都占有相同数量存放单元，才能用下标来唯一确实定数组中元素。第二章 数组与线性表第5页2.1.2 数组次序存放结构 在计算机中，表示数组是采取一组连续存放单元次序地存放各数组元素。能够用下标值随机访问该数组任意一个元素。计算数组元素存放地址公式称为寻址公式。设数组为A，每个数组元素占s个存放单元，一旦定义了它维数和各维上、下界，就能够得到计算数组元素地址寻址公式。第二章 数组与线性表第6页1.一维数组寻址公式对于一维数组，若其下标下界为LB，上界为UB，第一元素（其下标为LB）地址为Loc(LB)，下标为i数组元素Ai地址为Loc(i)，则计算Loc(i)寻址公式为：Loc(i)=Loc(LB)+(i-LB)*s 在C语言中，数组下标下界为0，则数组中任意一元素Ai寻址公式为：Loc(i)=Loc(0)+i*s 0in-1 第二章 数组与线性表第7页2.二维数组寻址公式在C语言中，采取矩阵元素以行为主存放，即同一行元素连续存放，存放完一行再存放下一行。设二维数组Amn，m、n分别表示数组行和列，用Loc(i,j)表示数组元素Aij地址，每个单元占用s个存放单元，则寻址公式为：Loc(i,j)=Loc(0,0)+(i*n+j)*s 0im-1,0jn-1 第二章 数组与线性表第8页定义一A23数组，对应矩阵以下：数组元素A12，其下标i=1，j=2，故它前面已经有i=1行，每行有3个元素，另外本行有j=2个元素，所以在元素A12之前，本数组已经有5个元素。第二章 数组与线性表第9页3.三维数组寻址公式三维数组Amnp可分解为p个m*n二维数组。按行为主存放数组元素Aijk寻址公式为：Locijk=Loc000+(i*n*p+j*p+k)*s 0im-1,0jn-1，0pp-1 对于更多维数组，数组元素在内存中存放能够这类推。返回第二章 数组与线性表第10页2.2.1 线性表（Linear List）线性表是由有限数目标相同类型元素组成序列。表中数据元素，除了第一个和最终一个以外，都有一个且只有一个前驱元素，同时也都有一个且只有一个后继元素；第一个元素只有一个后继元素而无前驱元素；最终一个元素只有一个前驱元素而无后继元素。线性表元素个数n称为这个表长度，当n=0时，这个表叫做空表。第二章 数组与线性表第11页线性表在计算机内存中采取各元素次序存放方式，这种存放结构叫做向量。每个线性表元素叫做这个向量一个分量。假如已知线性表第一个元素地址和每个元素占用存放单元数，由任一元素序号就能够计算出该元素在内存中地址。在编程时以一维数组表示线性表最简单，用也最普遍。第二章 数组与线性表第12页2.2.2 线性表运算对于给定线性表，可进行以下基本运算：1.求线性表长度n；2.在第i个数据元素前面插入一个新数据元素；3.删除第i个数据元素；4.存取或更新线性表第i个元素；5.将两个或两个以上线性表合并成一个线性表；6.将一个线性表拆成多个线性表；7.将线性表中各数据元素按某个域值（如关键字）递增或递减次序重新排列；8.在线性表中查找满足某种条件数据元素；第二章 数组与线性表第13页1.数据元素插入(insert)设用一个一维数组An表示此线性表，原来有m个元素（mn），元素值已给定。要求数组下标从1开始，即这里数据元素对应数组下标从1到n。要求在第i个元素前插入一个新数据元素，值为G，因原线性表数据元素是连续排列，中间没有空单元，所以第i个元素及其后面各元素均需向后移动一个单元位置，这么才能将G插入到i位置，且元素总数由m增加为（m+1）。第二章 数组与线性表第14页插入函数 void insert(A,int n,m,i,G)int j;if(in+1)printf(“i值错！n”);else for(j=m;j=i;j-)Aj+1=Aj;/*将第i个元素及其后面元素后移*/Ai=G;m+;/*线性表长度加1*/第二章 数组与线性表第15页插入函数分析在循环语句中，当i=1时，须循环m次，表示元素插入线性表头前面，则原线性表中m个元素均须向后移动一个单元，这是最不利情况。当i=m+1时，则循环一次也不进行，这时元素直接插入到线性表尾后面，所以线性表全部m个元素均不移动，这是最好情况。第二章 数组与线性表第16页2.数据元素删除(Delete)设用一个一维数组An表示此线性表，原来有n个元素，元素值已给定。要求删除第i个数据元素，因为线性表元素在数组中必须连续排列，中间不能有空单元，故将此元素删除后，它后面全部元素都需要向前移动一个单元，且数据元素总数由原来n降低到n-1.第二章 数组与线性表第17页删除函数 void delete(A,int n,i)int j;if(in)printf(“i值错！n”);else for(j=i;j=n;j+)Aj=Aj+1;n-;第二章 数组与线性表第18页删除函数分析在循环语句中，当i=1时，需循环(n-1)次，这是要删除线性表表头元素，是最不利情况；当i=n时，则循环一次也不执行，只是将元素数目n比原来降低一个，而第n个数据元素无须再考虑，其余各单元元素均维持不变，这是最好情况。第二章 数组与线性表第19页3.算法时间复杂性 能够用数据元素移动次数来度量这两个算法时间复杂性。插入时，最少循环0次，最多循环n次，如i各种取值概率相同，则平均循环次数为n/2；删除时最少循环次数为0次，最多为n-1次，当i取值概率相同时，平均循环次数为(n-1)/2。用数量级形式表示线性表插入、删除运算时间复杂性均为O(n)。返回第二章 数组与线性表第20页2.3.1 堆栈(Stack)堆栈也简称为栈，是限定在表一端进行插入或删除操作线性表。进行插入或删除操作一段称为栈顶（top），另一端称为栈底（bottom）。插入元素又称为入栈（push），删除元素操作称为出栈（pop）。不含元素栈称为空栈。堆栈元素插入和删除只在栈顶进行，总是后进去元素先出来，所以堆栈又称为后进先出线性表或LIFO（Last-In-First-Out）表。第二章 数组与线性表第21页堆栈表示堆栈最简单表示方法是采取一维数组，为形象起见，普通在图中将堆栈画成竖直。设数组名为STACK，其下标下界为1，上界为n。普通需用一个变量top统计当前栈顶下标值，top也叫做栈指针。第二章 数组与线性表第22页本例中top=4 topADCB4753216STACK第二章 数组与线性表第23页1.入栈（push）入栈主要操作是先将栈顶指针加1；然后将入栈元素放到栈顶指针所指示下标值位置上。设用下标从1到n数组ST表示堆栈，入栈元素值为G，则可得到入栈函数以下：第二章 数组与线性表第24页入栈函数 void push(ST,int n,top,G)if(top=n)printf(“栈溢出!n”);/*显示栈满信息*/else top=top+1;STtop=G;第二章 数组与线性表第25页2.出栈（Pop）出栈运算时，先将栈顶元素值赋给某个变量，以备后面运算应用；然后栈顶指针减1，将栈顶位置下移。假设已指定变量为x，则出栈函数以下：第二章 数组与线性表第26页出栈函数void pop(ST,int top,x)if(top=0)printf(“空栈!n”);/*栈为空显示对应信息*/else x=STtop;top=top-1;/*栈顶位置下移*/第二章 数组与线性表第27页2.3.2 堆栈应用 1.堆栈在函数调用中应用:设有三个函数A1，A2，A3，这三个函数有以下调用关系：函数A1在其函数体某处r调用函数A2，函数A2又在其函数体某处t调用函数A3，函数A3不调用其它函数。rtA1A2A3第二章 数组与线性表第28页函数嵌套调用A1调用A2，A2调用A3时返回地址在堆栈中情况如右图所表示。toprtSTACK第二章 数组与线性表第29页2.堆栈在表示式计算中应用 一个算术表示式，比如A+B，其中加号“+”称作运算符，而A，B称为运算数。对于由两个运算数和一个运算符组成表示式，习惯上是将运算符写在两个运算数中间，这叫做中缀形式。计算机处理表示式时，常把运算符放在两个运算数后面或前面。1.把运算符放在两个运算数后面，比如 AB+，称为后缀形式，也叫做波兰式。2.把运算符放在两个运算数前面，比如+AB，则称做前缀形式，也叫做逆波兰表示式。第二章 数组与线性表第30页算术表示式不一样运算符有不一样运算优先次序，如，在没有括号时，乘除运算（*或/）要比加减运算（+或-）优先进行。下面用一个简单例子说明编译系统在处理算术表示式时，是怎样应用堆栈这种数据结构。假定表示式运算数都是使用单个字母表示，式中无括号且只有加、减、乘、除4种运算，而没有更复杂运算，比如表示式 X+Y*Z。第二章 数组与线性表第31页使用S1和S2两个堆栈，S1用于存放运算数，S2用于存放运算符。编译系统处理时，将表示式从左向右逐一扫视一遍，并依据不一样情况按以下标准处理:1)若是运算数，则将其压入S1栈；2)若是运算符且S2栈是空栈则将其压入 S2栈；3)若是运算符且S2栈为非空栈，且此运算符级别高于S2栈顶运算符级别，则将此运算符压入S2栈；4)凡不属于上面三条情况，则将S2栈顶运算符与S1栈最上面两个运算数出栈进行运算，并将运算结果压入S1栈。第二章 数组与线性表第32页图中每一步上面括号中数字表示该步是按哪一条标准处理。返回第二章 数组与线性表第33页2.4.1 队列（Queue）队列是一个运算受限制线性表，元素添加在表一端进行，而元素删除在表另一端进行。允许添加元素一端称为队尾（Rear）；允许删除元素一端称为队头（Front）。向队列添加元素称为入队，从队列中删除元素称为出队。新入队元素只能添加在队尾，出队元素只能是删除队头元素，队列特点是先进入队列元素先出队，所以队列也称作先进先出表或FIFO（First-In-First-Out）表。第二章 数组与线性表第34页队列表示与堆栈类似，队列也能够简单用一维数组表示。设数组名为Queue，其下标下界为1，上界为n。普通使用一个变量r指示队尾下标值，叫做队尾指针；用另一个变量f指示队头下标值，称为队头指针。队列中元素数目等于零称为空队列，此时队头指针和队尾指针均为零，即f=r=0。第二章 数组与线性表第35页假定有AF 6个元素先后进入队列，但A、B两个元素已陆续出队了，故队尾指针r=6，而队头指针f=3。第二章 数组与线性表第36页1.入队（insert）当给队列插入元素时，队尾指针r后移而队头指针不动，但有一个情况例外，即当向空队列插入第一个元素时，队头指针与队尾指针同时由0变为1。设用下标从1到n数组Q表示队列，且已知待添加元素在变量x中。第二章 数组与线性表第37页入队函数 void insert(Q,int n,f,r,x)if(r=n)printf(“溢出!n”);/*判断是否已到数组末端*/else r=r+1；Qr=x;/*插入元素*/if(f=0)f=1;/*判断原来是否为空队列*/第二章 数组与线性表第38页2.出队（Delete）当从队列删除元素时，队头指针f后移而队尾指针r不动，但也有一个情况例外，即当删除了最终一个元素，队列成为了空队列时，队头指针与队尾指针同时变为0。假设要求将出队元素值赋给变量x。第二章 数组与线性表第39页出队函数void Delete(Q,int f,r,n,x)if(f=0)printf(“下溢出!n”);/*判断是否为空队列*/else x=Qf;/*取队头元素给x赋值*/if(f=r)f=0;/*若出队是最终一个元素，变成空队列*/r=0;else f=f+1;/*队头指针后移*/第二章 数组与线性表第40页3.队列存在问题 因为队列入队操作是在两端进行，伴随元素不停插入，删除，两端都向后移动，队列会很快移动到数组末端造成溢出，而前面单元无法利用。处理方法：1)每次删除一个元素后，将整个队列向前移动一个单元，保持队列头总固定在数组第一个单元。2)将所用数组想象成是头尾相接圆环，当队列尾端抵达数组末端（第n个单元）时，假如再插入元素可继续使队列向数组前端（第1个单元）延长，此队列称为循环队列。第二章 数组与线性表第41页2.4.2 循环队列图中阴影部分为队列中元素。怎样判断一个循环队列是满还是空？第二章 数组与线性表第42页判断循环队列是否满或空 满：队尾经过一个循环而抵达队首前一个单元时，这种情况下假如再插入新元素时，新元素就要把原队头元素覆盖，所以，当r=f时，插入新元素会造成队列首尾重合；空：在队列进行删除运算时，当f=r时表明删除是队列最终一个元素，删除这个元素后，队列就变成空队列。第二章 数组与线性表第43页循环队列入队函数void insert(Q,int n,f,r,i)if(r=n)r=1;/*抵达数组末端则向前端延长*/else r=r+1;if(r=f)printf(“溢出！n”);else Qr=i;/*插入新元素*/if(f=0)f=1;/*判定是否原来是空队列*/第二章 数组与线性表第44页循环队列出队函数void Delete(Q,int n,f,r,x)if(f=0)printf(“是空队列！n”);/*是否为空*/else x=Qf;/*取队头元素赋给变量x*/if(f=r)f=0;r=0;else if(f=n)f=1;/*由数组末端移到前端*/else f=f+1;/*队头指针后移*/第二章 数组与线性表第45页2.4.3 队列应用 对于各种含有“先进先出”需排队处理问题，都能够应用队列来处理。比如，操作系统在管理和分配系统资源时，大量应用了队列这种数据结构。1)队列在输入/输出管理中应用 2)对CPU分配管理 返回第二章 数组与线性表第46页例2.1 一个双向栈是将两个栈用一个数组组成，它们栈底分别设在数组两端。当一个栈中元素数目小于n/2时，另一个栈对应能够大于n/2。试写出以数组高端为底栈入栈和出栈算法。第二章 数组与线性表第47页例2.1解答这个栈栈顶指针top2是按相反方向移动，所以算法有所不一样：入栈时为：top2=top2-1出栈时为：top2=top2+1 两个栈在进栈过程中预防溢出条件是：top2=top1+1。出栈过程中预防下溢出及判断空栈条件分别为：top1=0，top2=（n+1）。第二章 数组与线性表第48页入栈算法 void push(ST,int n,top1,top2,G)if(top2=top1+1)printf(“溢出!n”);else top2=top2-1;STtop2=G;/*插入新元素*/第二章 数组与线性表第49页出栈算法void pop(ST,int n,top1,top2,x)if(top2=n+1)printf(“下溢出!n”);else x=STtop2;top2=top2+1;第二章 数组与线性表第50页例2.2 对于循环队列，试写出求队列长度算法。解1：设队列最大元素个数为n，设一个计数器，将其初始值设为0。从队首开始，沿着队列次序搜索，每走过一个元素，计数器加1，直到队尾，则计数器最终值即为队列长度。解2：利用队头指针与队尾指针也可求出队列长度：当rf时，length=r-f；当r=f)length=r-f;else length=(r+n+1)-f;return(length);返回第二章 数组与线性表第53页小 结 本章主要介绍了采取次序存放结构线性表及实现各种基本运算算法。数组线性表 堆栈队列 返回第二章 数组与线性表第54页习题与练习 一、基本知识题 1.什么是数组？数组主要特点是什么？2.什么是线性表？线性表主要运算有哪些？3.什么是栈？什么是队列？它们各自特点是什么？4.线性表、栈、队列有什么异同？5.简述栈入栈、出栈操作过程。6.在循环队列中简述入队、出队操作过程。7.在什么情况下，才能使用栈、队列等数据结构？8.有A、B、C三个数组：A8，B47，C586，试计算它们元素个数是多少？第二章 数组与线性表第55页二、算法设计题 1.设有一n个元素线性表，用一维数组An表示。试设计一个算法，使此线性表元素排队次序颠倒过来但仍存放于原数组中。2.设用一维数组stackn表示一个堆栈，若堆栈中一个元素需占用length个数组单元（length 1），试写出其入栈、出栈操作算法。第二章 数组与线性表第56页3.试编写一个遍历及显示队列中元素算法。4.设一循环队列Queue，只有头指针front，不设尾指针，另设一个内含元素个数计数器，试写出对应入队、出队算法。5.设计一算法能判断一个算术表示式中圆括号配对是否正确。（提醒：对表示式进行扫描，凡碰到“（”就进栈，碰到“）”就退出栈顶“（”，表示式扫描完成时栈若为空则圆括号配对正确。）返回第二章 数组与线性表第57页谢谢收看 返回第二章 数组与线性表第58页