算法与数据结构讲义二数据结构

第十二课数据结构——线性表12.0数据结构概述12.1线性表12.2栈12.3队列12.4串 12.0数据结构概述是否掌握数据结构，是区分一个程序设计人员水平高低的标志，也是在高中阶段信息学竞赛中，能否获得一等奖的分水岭。无论在国内还是国外，《数据结构》一直是大学计算机专业的一门专业基础课，但是，对于学习程序设计的中学生，在学习完一门程序设计语言后，为了学习更多的算法以进一步提高编程能力，《数据结构》就成了必须突破的对象。掌握《数据结构》的目的，是充分利用数据之间的内在联系，降低数据的检索、插入、删除、更新、排序等操作的时间复杂度，从而提高算法的效率。从而，避免了大量的穷举式操作。一、什么是数据结构：简而言之，就是“数据+结构”1、 数据：数据是客观事物的符号表示。是我们在解决问题的过程中，对客观事物对象所进行的定量、定性的数值或文字表达，以便于我们输入计算机中进行模拟、计算、处理。例如：我们要对这次期中测试成绩进行总分计算、名次排序、优秀率等统计，就需要将测试结果用分数量化，并加上姓名等信息后，输入到计算机中进行处理，我们将所有输入的这些内容，成为一个“期中测试成绩数据”数据元素、数据项：数据项：数据中补课分割的最小单元。例如：上例中的某个学生的语文成绩。数据元素：是数据的基本单位，是由若干个数据项组成。例如：上例中某一个学生的测试各科成绩。2、 结构：数据中各数据元素之间的关系，分为逻辑结构和物理结构。逻辑结构：数据之间的内在关系。例如：一家人参加旅行团去某地旅游，在旅行车上，无论他们是否坐在一起，他们之间的父子、母子等内在关系依然存在。物理结构：数据在计算机中的存储方式，又称为存储结构。物理结构的种类：顺序存储、链式存储、索引存储、散式存储。顺序存储:把逻辑相邻的结点存储在物理相邻的存储单元内链式存储：结点之间的逻辑关系由附加指针来表示。索引存储：存储结点信息的同时，建立索引表。散列存储：按结点的关键字直接计算出存储地址。物理结构和逻辑结构之间的关系：（1） 逻辑结构是具体问题抽象出来的数学模型，物理结构是逻辑结构的计算机语言的实现。（2） 有什么样的逻辑结构，就应该选择相应的物理结构。（3） 选择的物理结构要方便基于逻辑结构上的数据运算。

（4）物理结构不等同于逻辑结构，反之，逻辑结构也不等于物理结构，因此，对数据结构的设计，不仅要进行逻辑结构的设计，也还要进行物理结构的设计。数据的运算：各种逻辑结构上的运算集合。常用的有：检索、插入、删除、更新、排序。、数据结构的分类:序号名称结构特点常用物理结构1集合无任何关系的一组数据例如：互不相识的若干人乘坐同一辆公父车。顺序索引2线性表兀素间存在严格的一对一的关系例如：按顺序排列的26个英文字母，B前面只能是A,后面只能是C。顺序散列3树兀素间严格的一对多关系例如：磁盘中的文件夹和文件。顺序索引、散列4图兀素间为多对多的关系例如：一个班级同学之间的关系。一个人可以有多个朋友，也可以是多个人的朋友。顺序索引12・1线性表一个线性表是n个数据元素的有限序列。线性表是最常用且最简单的一种数据结构。一、线性表的结构特点在数据元素的非空有限集中，（1） 存在唯一的一个被称做“第一个”的数据元素；（2） 存在唯一的一个被称做“最后一个”的数据元素；（3） 除第一个之外，集合中的每个数据元素均只有一个前驱；（4） 除最后一个之外，集合中每个数据元素均只有一个后继。a,a「a.a..a1i-1ii+1na是a的直接前驱元素，a是a的直接后继元素。i i+1 i+1 i线性表中元素的个数n定义为线性表的长度，为0时称为空表。在非空表中的每个数据元素都有一个确定的位置。a是第i个元素，把i称为数据元素a在线性中的i i位序。、线性表的操作：1、 求长度：L:=a[O];2、 清空：a[0]:=0;3、 判断线性表是否为空：（a[O]=O）=true4、 线性表存在且未满：a[O]vmaxn5、 插入操作：将b插入到线性表中第k个的前面ifa[0]<maxnthenbeginfori:=a[0]downtokdoa[i+1]:=a[i];a[k]:=b;inc（a[0]）;end;6、 删除操作：删除线性表中第k个元素fori:=ktoa[0]-1doa[i]:=a[i+1];dec(a[O]);7、 取表元：去除表中第k个元素c:=a[k];8、 按值查找：在表中查找值为b的元素，返回序号。如未找到，返回0functionfind(b:integer):integer;beginfind:=1;while(a[i]v>b)and(findv=a[0])doinc(find);iffind>a[0]thenfind:=0;end;三、线性表使用实例：1、 顺序表倒置：算法思路：把第一个元素和最后一个元素交换，把第二个元素和倒数第二个元素交换。一般地，把第i个元素和第ni个元素交换，i的取值范围是0到n/2(n为顺序表的长度)。procedureinvert;vari,tmp:integer;beginfori:=1toa[0]div2dobegintmp:=a[n-i+1];a[n_i+1]:=a[i];a[i]:=tmp;end;end;2、 两顺序表合并：proceduremerger(a,b:var;varc:arr);varp1,p2,p,i:integer;beginfillchar(c,sizeof(c),0);p1:=1;p2:=1;p:=0;while(p1v=a[0])and(p2v=b[0])doifa[p1]vb[p2]thenbegininc(p);c[p]:=a[p1];inc(p1);endelsebegininc(p);c[p]:=b[p2];inc(p2);end;ifp1v=a[0]thenfori:=p1toa[0]dobegininc(p);c[p]:=a[i];end;ifp2v=b[0]then

fori:=p2tob[0]dobegin

inc（p）;c[p]:=b[i];end;c[0]:=a[0]+b[0];end;3、构造包含已知顺序表中所有值不相同的数据元素：已知一个存储整数的顺序表a,试构造顺序表b,要求顺序表b中只包含顺序表a中所有值不相同的数据元素。算法思路：先把顺序表a的第1个元素赋给顺序表b，然后从顺序表a的第2个元素起，每一个元素和顺序表b中的每一个元素进行比较，如果不相同，则把该元素附加到顺序表b的末尾。procedurestruc（a:arr;varb:arr）;var[integer;beginb[0]:=1;b[1]:=a[1];fori:=2toa[0]doifa[i]v>b[b[0]]thenbegininc（b[0]）;b[b[0]]:=a[i];end;end;1、21、2、一、 栈的定义：栈（Stack）是操作限定在表的尾端进行的线性表。二、 栈的结构特点：栈是一种特殊的线性表。栈的一端（栈底）是封闭的，禁止进行任何操作。3、3、4、4、从以上特点可以看出，先入栈的元素将被压在后入栈的元素底下，只有后入栈的元素出栈后才能出栈。因此，栈又称为“先进后出表（LIFO）”或“后进先出表（FOLI）”。如右图，表的底端（栈底）是封闭的，进栈和出栈操作都只能在栈顶进行。我们只需要一个栈顶指针就可以了。当top=0时，称为空栈。、栈的物理结构：一般采用数组存储，a[l]为栈底，实现栈顶的进栈操作和出栈操作。四、栈的基本运算：1、 初始化空栈：top:=0;2、 求栈的长度：L:=top;

3、 判断栈是否溢出：(top>maxn)=true4、 判断栈是否为空：(top=0)=true5、 进栈操作：iftopvmaxnthenbegininc(top);a[top]:=b;end;6、 出栈操作：(为了便于维护栈的结构，一般不直接调用栈顶的数组单元)iftop<>0thenbeginb:=a[top];dec(top);end;7、 取栈顶元素：(只取栈顶数据，不改变栈的大小)iftop<>0thenb:=a[top];四、栈的使用实例：1、进位制转换：将十进制数转换成其它进制的数有一种简单的方法：例：十进制转换成八进制：(66)1。=(102)866/8=8余28/8=1余01/8=0余1结果为余数的逆序：102。先求得的余数在写出结果时最后写出，最后求出的余数最先写出，符合栈的先入后出性质，故可用栈来实现数制转换。算法过程：步骤1若n#0,则将nmod8压入栈中，执行步骤2；若n=0,则将栈的内容依次出栈，算法结束。步骤2：用ndiv8代替n,返回步骤1。proceduretrans(n:integer;vara:arr);vartop:integer;begintop:=0;whilen<>0dobegininc(top);a[top]:=nmod8;n:=ndiv8;end;end;2、行编辑：一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据,并存入用户的数据区。允许用户输入出错时可以及时更正。可以约定#为退格符，以表示前一个字符无效，@为退行符，表示当前行所有字符均无效。procedureeditline(varst:arr);vartop:integer;begintop:=0;repeatread(inf,ch);casechof'#':iftop〈〉0thendec(top);'@':top:=0;elsebegininc(top);

st[top]:=ch;end;end;untileof(inf);end;3、表达式求值：分析表达式并计算出结果。表达式的要素是运算符、操作数、算符优先级关系。例：1+2*3有+,*两个运算符，*的优先级高,1,2,3是操作数。算法基本思想：建立运算符栈oprt，分离表达式遇到运算符op时，如栈空或栈顶运算符优先级低于op,则将op压栈；否则，弹出栈顶算符并计算。然后再重复比较栈顶运算符和op,直至op可以进栈。建立操作数栈opnd，分离表达式遇到操作数时，无条件压栈。只有当运算符栈的栈顶运算符弹栈进行计算时，弹出栈顶两个操作数参加计算，并将结果压栈。算法过程：分离表达式，如果是数值，压进opnd栈；如果是算符，根据规则(1)处理。表达式分离完毕，将oprt栈中算符按顺序弹出并计算。输出opnd[1]oprogramexpression;varinf,outf:text;s,ss:string;data:array[1..maxn]oflongint;

sf:array[1..maxn]ofchar;topd,tops,num,l,a,b,c,code:longint;ch,cha:char;///////////////////procedurepushd(a:longint);beginiftopd<maxnthenbegininc(topd);data[topd]:=a;end;end;/////////////////procedurepushs(ch:char);beginiftopsvmaxnthenbegininc(tops);sf[tops]:=ch;end;end;////////////////functionpopd:longint;beginiftopdv>0thenbeginpopd:=data[topd];dec(topd);endelsepopd:=0;end;////////////////functionpops:char;beginpops:=sf[tops];dec(tops);end;//////////////////functionjisuan(a,b:longint;cha:char):longint;beginnum:=1;casechaof'+':jisuan:=a+b;'-':jisuan:=a-b;'*':jisuan:=a*b;'/':jisuan:=adivb;'A':beginforl:=1tobdonum:=num*a;jisuan:=num;end;end;end;

//////////////functionjibei(ch:char):longint;begincasechof'+','-':jibei:=l;'*',7':jibei:=2;'A':jibei:=3;end;end;//////////////procedureinit;beginassign(inf,'exp.in');assign(outf,'exp.out');reset(inf);rewrite(outf);readln(inf,s);topd:=0;tops:=0;end;///////////////////proceduremain;beginwhilesv>"dobegincode:=1;while(s[code]>='0')and(s[code]v=9)doinc(code);ifcode=1thenbeginch:=s[1];delete(s,1,1);if(ch<>'(')and(ch<>')')thenbeginif(jibei(ch)<=jibei(sf[tops]))and(tops<>0)and(sf[tops]<>'(')and(sf[tops]<>')')thenbegincha:=pops;a:=popd;b:=popd;c:=jisuan(b,a,cha);pushd(c);end;pushs(ch);end;ifch='('thenpushs(ch);ifch=')'thenbegin

while(sf[tops]v>'(')dobegincha:=pops;a:=popd;b:=popd;c:=jisuan(b,a,cha);pushd(c);end;dec(tops);end;endelsebeginss:=copy(s,l,code-l);delete(s,l,code-l);val(ss,a,code);pushd(a);end;end;whiletops<>0dobegincha:=pops;a:=popd;b:=popd;c:=jisuan(b,a,cha);pushd(c);end;end;////////////////procedureprint;beginwriteln(outf,data[1]);close(outf);end;////////////////////begininit;main;print;end.算法扩展：如何实现带括号的表达式计算？如何实现带绝对值号的表达式计算？如何实现带乘方、函数的表达式计算如何实现带字母的表达式计算？

五、利用栈模拟递归实现递归及回朔：从原理上，任何递归和建立在递归基础上的算法，都可以使用栈进行非递归实现。调用子程序是需要分配一定的内存空间用以存放参数、函数返回值和局部变量等数据的。Pascal提供了一个全局静态的栈结构的内存段用以存放这些数据，每次调用子程序都会把所需的数据压入栈中，子程序结束后就把数据从栈中取回。当栈没有足够的剩余空间来存放调用子程序所需的数据时，就会出现栈溢出错误。递归过程为：ProcedureDEF-GO(step)fori:=ltomaxdoif子结点符合条件then产生新的子结点入栈；if子结点是目标结点then输出elseDEF-GO(step+1)；栈顶结点出栈；endif；enddo；主程序为：ProgramDFS；初始状态入栈；DEF-GO(1)；proceduredfs(step);vari;beginfori:=1tomaxdoif产生的新结点符合条件thenbegin产生的新结点入栈；if子结点是目标结点then输出elsedfs(step+1);栈顶结点出栈；end;end;二、非递归ProgramDEF(step)；step:=0；repeatstep:=step+1；j:=0；p:=falserepeatj:=j+1；if结点符合条件then

产生子结点入栈；

if子结点是目标结点then输出elsep:=true；elseifj>=maxthen回溯p:=false；endif；untilp=true；untilstep=0；回溯过程如下：ProcedureBACK；step:=step-l；ifstep>0then栈顶结点出栈elsep:=true；procedureback; 〃回朔过程begindec(step);ifstep>0thenbegin栈顶结点出栈；p:=false;endelsep:=true;end;//////////////////////////////////////////////////////////////////////////////////////////////proceduredfs(step);beginstep:=0;repeatinc(step);j:=0;p:=false;repeatinc(j);if新产生结点复合条件thenbegin新产生结点入栈；if子结点是目标结点then输出elsep:=true;endelseifj>=maxthenback;untilp;untilstep=0;Borland/TurboPascal编译器是16位的编译器，最多只能设置64KB字节的栈空间，因此，使用模拟递归进行回朔是非常必要的。在Freepascal是32位的编译器，理论上栈空间是没有限制的，所以，现在已经不提倡使用结构复杂的模拟递归了。

12.3队列（Queue）―、队列的定义：队列是只允许在一端进行加入，而在另一端进行删除的运算受限的线性表。（1） 允许删除的一端称为队头（Front）。（2） 允许插入的一端称为队尾（Rear）。（3） 当队列中没有元素时称为空队列。（4） 队列亦称作先进先出（FirstInFirst）OU线性表，简称为FIFO表。队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾（即不允许〃加塞〃），每次离开的成员总是队列头上的（不允许中途离队）即当前〃最老的〃成员离队。为了便于队头和队尾位置的记录，需要开设两个下标指针变量：头指针:head,指向当前队头元素的前一个位置（即最后出队的元素位置）。尾指针：tai,l指向当前队尾元素所在的位置。初始化队列（置队空）：head:=0;tail:=0;判断队列是否为空：为了便于队头和队尾位置的记录，需要开设两个下标指针变量：头指针:head,指向当前队头元素的前一个位置（即最后出队的元素位置）。尾指针：tai,l指向当前队尾元素所在的位置。初始化队列（置队空）：head:=0;tail:=0;判断队列是否为空：head二tail二true判断是否已满（即是否溢出）队列溢出有两种：1、2、3、假性溢出:****maxnmm-1m-212真性溢出:******maxnmm-1m-2真性溢出:******maxnmm-1m-2hefd或.12tail**L**maxnmm-1m-2h$ad 击订此时，如果有新元素需要入队，由于数组以使用到最大下标无法入队，二实际上数组中仍有队头之前的m-1个空位置。这种溢出称为假性溢出。假性溢出的克服方法：采用环形数组，即使tai到达maxn时，自动返回到1。12ailhead 第一种情况为链式队列，队头指针指向1，而队尾指针已到达maxn，当再有元素需要入队时，因无法入队而发生溢出，其解决办法只有扩充maxn的值。第二种情况为使用循环队列，队头指针已循环到队尾指针的左边，并已把head前面的空位置占满，如果再有元素入队，则会发生叠加到队头元素上。其解决办法有二：扩充maxn和附加

备用队列。判断是否溢出操作：链式队列：tail>maxn=true循环队列：(head=tail)and(ring_headv>ring_tail)如果ring_head=ring_tail,则意味着队空。4、 入队操作：(join)ifnot(队满)thenbegininc(tail);a[tail]:=d;end;5、 出队操作：(dequeue)ifnot(队空)thenbegininc(head);d:=a[head];end;三、例1：有N张牌，记为1，2，...，N,应当怎样排放，才能使：翻开最上面一张是1,移走这张牌，然后把两张依次放在末尾；再翻开上面一张，刚好是2并移走，再依次把三张放在末尾，打开上面一张，刚好是3；如此继续下去，直至打开最后一张是N。写一个程序解决这个问题。programqueue_1;constmaxn=100;vara,b:array[1..maxn]ofinteger;inf,outf:text;head,tail,ring_head,ring_tail,d,n,i,j:integer;/////////////////////////////////////////////////procedureinit;beginassign(inf,'queue_1.in');assign(outf,'queue_1.out');reset(inf);read(inf,n);fori:=1tondoa[i]:=i;head:=0;tail:=n;end;/////////////////////////////////////////////////functiondeq:integer;begininc(head);ifhead>maxnthenbegininc(ring_head);head:=(head-1)modmaxn+1;end;deq:=a[head];

end;/////////////////////////////////////////////////procedurejoin(d:integer);begininc(tail);iftail>maxnthenbegininc(ring_tail);tail:=(tail-l)modmaxn+1;end;a[tail]:=d;end;/////////////////////////////////////////////////proceduremain;begind:=deq;b[d]:=1;fori:=2tondobeginforj:=1toidobegind:=deq;join(d);end;d:=deq;b[d]:=i;end;end;///////////////////////////////////////////////////procedureprint;beginrewrite(outf);fori:=1ton-1dowrite(outf,b[i],'');write(outf,b[n]);close(outf);end;/////////////////////////////////////////////////begininit;main;print;end.12.4串串是一种特殊的线性数据。一般对于串的操作既可以按数组的方式进行，也可以使用专用函数或过程，其时间代价基本相同。(1)求串长0(1) length

(2)两串连接O（n）加法远算(3)复制子串O(n)copy(4)插入子串O(n)insert(5)删除子串O(n)delete(6)数转串O(n)str(7)串转数O(n)val(8)串匹配O(mn)pos从以上看出，串的匹配算法时间复杂度非常大。这里学习对串的模式匹配的算法改进。一、pos函数的算法效率低下的原因：传统的字符串模式匹配算法（BF算法）就是对于主串和模式串双双自左向右，一个一个字符比较，如果不匹配，主串和模式串的位置指针都要回溯。这样的算法时间复杂度为O（n*m）,其中n和m分别为串s和串t的长度。例如：在串S="abcabcabdabba"中查找T="abcabd"先是比较S⑴和T⑴是否相等，然后比较S[2]和T[2]是否相等…我们发现一直比较到S[6]和T⑹才不等。如图一：图一当这样一个失配发生时，T下标必须回溯到开始，S下标回溯的长度和T相同，然后S下标增1,然后再次比较。如图：sbcabcsbcabcabdabba123456789101112131、X-1X-1S|a|b|c|a|b|c|a|b|d|a|b|b|a|VVVV/、zTabcabd\F12345678910111213123456abcabd123456极端的例子是：在S=“AAAAAA...AAB“（100个A）中查找T="AAAAAAAAAB",简单匹配算法每次都是比较到T的结尾，发现字符不同，然后T的下标回溯到开始，S的下标也要回溯相同长度后增1,继续比较，所以，时间复杂度为O（mn）。对传统算法的改良探讨图二中，S[6]和T⑹失配后，S和T的下标同时回朔是效率低下的根本原因（接下来的比较很多是无意义的），对比两个串发现，当发生失配时，下一次有效比较发生在S[4]和T[1]（如图三），而真正有意义的比较则发生在S[6]对T[3]。12345678910li1213SabCabCabdabbajbtIV、Tabcabd123456图三通过考察得出，最好的策略是：1、 S串的下标不回朔，停留在上次失配的位置i。2、 T串回朔k个位置，使T串和S串中对齐第i个字符之前的子串相配。

因此，只要能求出T串中每个位置的k值，就可以在模式匹配过程中，对S串从头扫描到尾（不回朔），当发生S[i]和T[j]失配时，只将T串回朔k个位，接下来就可以继续比较S[i]和T[k]，直到完全匹配或S串到末尾。就能实现O（n）的效率。KMP算法：1、求k值：当S[i]和T[j]失配时,T⑴〜T[j-1]和S[i-j+1]~S[i-1]一定已匹配成功，则两串的红色1 i-j+1 i-k+1 iciILST1j-k+1j区域完全相同：S[i-k+1]S[i-k+2]S[i-k+3]……S[i-1]=T[j-k+1]T[j-k+2]T[j-k+3]……T[j-1]。……（1）当T串回朔到下标为k的位置时，T[k]和S[i]对齐进行下一次比较，而S串中红色i-j+1 i-k+1i区域和T串中蓝色区域完全相同。即有：S[i-k+l]S[i-k+2]S[i-k+3]……S[i-1]=T[1]T[2]T[3]……T[k-1] ……(2)由(1)(2)两式得出：T[j-k+1]T[j-k+2]T[j-k+3]……T[j-1]=T[1]T[2]T[3]……T[k-1](3)即T串的蓝色区域和红色区域完全相同，由此得出，要求出T串中j位置的k值，只需要找出j位置前有多少个字符(红色区域)和自身串首的字符(蓝色区域)相同即可。 厂0 当j=1时K[j]=(max^Kkvj，且……匚1=片*厲*2……Tj-J-1 其它情况如上：T串：abcabdK[j]0 1 1 1 2 32、参考程序：programkmp;constmaxn=100000;varinf,outf:text;next:array[1..100000]oflongint; //保存k值的数组i