数据结构实验指导书及练习题曲.doc

数据结构实验指导书自动化学院电子系 曲卫芬 编 实验指导教师 曲卫芬 于瑞涛2007年9月一前言1、 数据结构课程实验的地位与作用 “数据结构”是理工科专业一门重要的专业技术基础课程。是将来驾驭计算机，指挥计算机，为自己的工作服务的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。由于以下原因，使得掌握这门课程具有较大的难度：（1） 内容丰富，学习量大，给学习带来困难；（2） 贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点；（3） 所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度；（4）相关的程序设计基础C语言的学习尤其重要。但我们学生的C语言的学习是在大一就开设的，加上是公共课，对数据结构里用的指针和结构体等方面的知识讲解的很少，学生反映考试又不考相关内容，就没有足够的重视和学习，也可以说，就没学这部分的内容，这更加大了这门课的学习难度。（5） 隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据数据结构课程课程本身的技术特性，设置数据结构课程实验实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。由于学分的限制，安排上课40学时，实验安排9学时。2、 数据结构课程实验的目的和要求不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术，掌握数据结构中稍微复杂一些的算法设计中可能同时用到的多种技术和方法，如算法设计的构思方法，链表、栈、队列、树等算法的编码，递归技术，与特定问题相关的技术等。在数据结构中要求重点掌握线性链表、二叉树和树、图、数组等结构相关算法的设计。在掌握基本算法的基础上，提高分析、解决实际问题的能力。3、 数据结构课程实验对相关课程的要求 要求认真复习C语言的程序设计，复习和自学数组，指针、结构体、函数等内容，建立起程序设计思想，锻炼独立编写程序的能力。二实验题目 实验一 约瑟夫环的程序实现【实验目的】（1）进一步掌握线性表的各种链式存储结构，包括单链表与循环链表，熟悉各种操作。（2）认真分析实际项目的内容，将其中的算法付诸实现，目的是练习利用线性表的链表结构来解决实际应用问题的能力，掌握线性表的实际应用。【实验内容与要求】问题描述：编号是1,2,n(n0)的n个人按照顺时针方向围坐一圈，每人持有一正整数密码。开始时任选一个正整数作为报数上限值m，从某个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。令n最大值取30。设计一个程序来求出出列顺序，并输出结果。 基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各人的编号。【知识要点】 关于单循环链表的概念请参见课本中所学的知识要点。循环链表上的运算与单链表上运算基本一致，区别只在于最后一个结点的判断(即循环的条件不同)，但利用循环链表实现某些运算较单链表方便(从某个结点出发能求出它的直接前驱，而单链表是不行的，只能从头出发)。图1-1给出带头结点的循环链表的两种结构。 头 a1 a2 an head (b) 非空循环表 图1-1 带头结点的单循环链表示意图 (a) 空循环表 头 head 【实现提示】 由于该问题是由古罗马著名史学家Josephus提出的问题演变而来，所以通常称之为Josephus问题。Josephus问题的解决需要采用循环链表，先构造一个有n个结点的单循环链表，再给出一个报数上限值m(假设m1)，在链表的首结点开始从1计数，计到m时，对应的结点从链表中删除，然后在被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。 本设计采用的是不带头结点的循环链表，问题简化成固定密码，从键盘上输入人数N和密码M，开始报数，出列，直到结束。其中循环链表中结点的结构如下： typedef struct int num; struct node *next; linklist;该问题可由两部分组成，分别由如下两个算法完成：（1）建立一个由头指针head指示的有n个结点的约瑟夫单循环链表函数creat。（2）寻找、输出和删除head所指的单循环链表的第m个结点函数select。该算法由如下具体步骤组成：在head中的第一个结点起循环记数找第m个结点；输出该结点的num值；删除该结点；转去执行,直到所有结点被删除为止。【参考程序】 程序和定义内容如下： #includetypedef struct node int num; struct node *next; linklist; /* 建立单循环链表函数 */ linklist *creat(int n) int k; linklist *head, *r, *p; p=(linklist *)malloc(sizeof(linklist); head=p; p-num=1; r=p; p-next=p; for(k=2;knum=k; r-next=p; r=p; p-next=head;return(head); /* 选择出列编号 */linklist *select(linklist *head, int m) linklist *p,*q; int k;q=head;k=1;p=q-next; /q为p的前趋指针,p指向当前报数的人while(q!=p) k=k+1; /报一次数 if(k=m) printf(%d ，,p-num); q-next=p-next; /对应的结点从链表中删除 free(p); k=0; p=q-next; elseq=p; p=p-next; / p指向当前报数的人 head=p;return(head);void main() int n,m;linklist *head;printf(Input N and M:n);scanf(%d%d,&n,&m);head=creat(n);head=select(head,m);printf(%dn,head-num);假设n=5,m=3,则程序的出列编号顺序为3，1，5，2，4 。【实验的具体要求】1.调试上面的程序，给出以下3组数据：n=5,m=3，n=7,m=20，n=15,m=9给出程序的执行结果。2.若输入的起始密码是1（如n=5,m=1）检查结果是否正确？若不正确，如何修改此程序？3.修改上面的问题要求：要求每个人手里都有一个密码，每次出列后，用此人手中的密码继续报数，直到结束。写出数据结构的定义并编写程序，调试并写出实验数据和执行结果。实验测试数据假设n=7,m=20,7个人的密码依次为3,1,7,2,4,8,4,则程序的出列编号顺序为6,1,4,7,2,3,5。【问题的其他方法】1、定义循环链表采用“头结点”，程序又该怎样编写？请注意空表和非空表的界限。2、不用循环链表，采用顺序表结构编程实现上述问题。实验二 算术表达式求值【实验目的】（1）掌握顺序栈的基本操作：初始化栈、判栈空否、入栈、出栈、取栈顶数据元素等运算以及程序实现方法。 （2）栈的用途极为广泛，在源程序编译中表达式的计算、过程的嵌套调用和递归调用等都要用到栈。（3）认真分析实际项目的内容，将其中的算法付诸实现，目的是练习利用顺序栈的结构来解决实际应用问题的能力，掌握栈的实际应用。【实验内容与要求】问题描述：表达式计算是实现程序设计语言的基本问题之一，也是栈的一个典型应用实例。设计一个程序，实现用运算符优先法对算术表达式求值。基本要求：以字符序列的形式从终端输入语法正确的、不含变量的整数表达式，只包含加、减、乘、除、括号运算，并且键盘中输入的表达式都是正确，以#作为结束符。编程实现对算术四则混合运算表达式的求值。【知识要点】关于栈的概念请参见课本中所学的知识要点。 栈是只能在某一端插入和删除的特殊线性表。一个栈可以用定长为StackSize的数组来表示，用一个栈指针TOP指向栈顶。若TOP0，表示栈空，TOP=StackSize时栈满。进栈时TOP加。退栈时TOP减。当TOP0时为下溢。栈指针在运算中永远指向栈顶。一个程序设计语言应该允许设计者根据需要用表达式描述计算过程，编译器则应该能分析表达式并计算出结果。表达式计算是栈的典型应用之一。【实现提示】分析表达式要素包含有：运算符、操作数、界定符、运算符优先级关系。界定符有括号和表达式结束符（设为#）等。可设置两个栈：OPTR用于寄存运算符，OPND用于寄存操作数或运算结果。顺序栈的类型定义如下： # define StackSize 100 typedef int datatype; typedef struct datatype dataStackSize; int top; SeqStack;算法基本思想：先置操作数栈OPND为空栈，表达式起始符为运算符栈的栈底元素；依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符，则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕。（即OPTR栈的栈顶元素和当前读入的字符均为#）比较优先权后作相应操作如下：2.1若栈顶运算符优先权低， 则当前读来的运算符进栈，读下一个字符； 2.2若2个运算符优先权相等， 则脱括号，读下一个字符； 2.3若栈顶运算符优先权高， 则取操作数栈顶的2个元素，取运算法栈的栈顶元素，进行运算，将结果进操作数栈。【参考程序】# define StackSize 100#include#include typedef int datatype;typedef struct datatype dataStackSize; int top; seqstack;void initstack(seqstack *s) s-top=0;int stackempty(seqstack *s)return(s-top=0);int stackfull(seqstack *s) return(s-top=StackSize);void push(seqstack *s,datatype x) if (stackfull(s) printf(stack overflow!); exit(); s-datas-top+=x;void pop(seqstack *s,datatype *e) if(stackempty(s) printf(stack underflow!); exit(); s-top-; *e=s-datas-top;datatype gettop(seqstack *s) if(stackempty(s) printf(stack is enpty!); exit();return (s-datas-top-1);char op=+-*/()#;int in(char c,char *op) if(strchr(op,c) return(1); else return(0);int priority(char c) /*将运算符转换成优先级，设置优先级用整型数表示：#其优先级为0；（其优先级为1；+、-其优先级为2 *、/其优先级为3；）其优先级为4*/ switch(c) case #:return(0); case (:return(1); case +: case -: return(2); case *: case /: return(3); case ): return(4); char precede(char c1,char c2) /*pri1,pri2为栈顶运算符和当前运算符的优先级，比较2个运算符的优先级大小，若pri1=1且pri2=4,返回=；若pri1=0且pri2=0,返回=;若pri2=1,返回;若pri1=pri2,返回;若pri1pri2,返回*/ int pri1,pri2; pri1=priority(c1); pri2=priority(c2); if (pri1=1&pri2=4) return(=); if (pri1=0&pri2=0) return(=); if (pri2=1) return(); if (pri1=pri2) return(); if (pri1pri2) return(); return(0);int operate(int a,char theta,int b)/*计算a theta b 返回计算结果。注：theta为运算符*/ switch(theta) case +: return(a+b); case -:return(a-b); case *:return(a*b); case /:return(a/b); char change(int c)/*将运算符栈弹出的内容转换成相应的运算符*/ switch(c) case 35: return(#); case 40: return(); case 41: return(); case 42: return(*); case 43: return(+); case 45: return(-); case 47: return(/); int evaluate(char *s) /*算术表达式求值的算符优先算法。 设OPTR和OPND分别是运算符栈 和操作数栈，OP为运算符集合*/char c,e,theta; int a,b;int c1,c3,i=0,explen;seqstack optr ,opnd;initstack(&optr); push(&optr,35);initstack(&opnd);explen=strlen(s); /*求表达式的长度*/while(si!=#|gettop(&optr)!=35) c=si; if(!in(c,op) c1=c-48; /*将字符型数据转换成数字型数据*/ push(&opnd,c1);if(iexplen) i+; else switch(precede(gettop(&optr),c) case : push(&optr,c); if(iexplen) i+; break; case =: pop(&optr,&e);if(i: pop(&optr,&c1); theta=change(c1); pop(&opnd,&b); pop(&opnd,&a); push(&opnd,operate(a,theta,b); break; c1=gettop(&opnd); /*destroystack(optr); destroystack(opnd);*/ return c1;main() int val,i; char ss80; printf(nExp: ); scanf(%s,ss); val=evaluate(ss); printf(nval=%dn,val); 本程序中除了设计栈的相关运算函数外，还包括以下函数：1 求优先级函数int priority(char c)：c为运算符，返回一个整型数表示运算符的优先级。此函数为了能够实现运算符的比较，即书上P53的算符间的优先关系。 运算符 优先级 # 0 （ 1 +，- 2 *，/ 3 ） 42 运算符比较函数char precede(char c1,char c2)：c1为运算符栈顶元素，c2为当前读来的运算符，返回两个运算符之间关系的符号。即、=或。3 计算函数int operate(int a,char theta,int b)： a、b分别为2个运算数，theta为运算符，此函数计算 a theta b ，返回计算结果。4 运算符转换函数char change(int c):c为栈中弹出的运算符，返回运算符相应的字符型。由于栈的元素类型定义成int，而运算符为字符型，在压栈时将其字符的ASCP（整型数）进栈，但使用时要转换成相应的运算符。思考：不用转换也可以，但要修改计算函数，在判断theta为哪个运算符时就应该和ASCP码进行比较。5 按运算符优先计算中缀表达式的值函数int evaluate(char *s)：s为字符型的表达式，返回表达式的值。6 主函数是从键盘输入一个合法的表达式，调用int evaluate(char *s)进行计算，得到表达式的值。 ASCP码表： ASCP值 字符35 #40 （41 ）42 *43 +45 -47 /48 049 156 857 9【实验的具体要求】1. 调试上面的程序，根据给出的测试数据，写出执行结果。 【测试数据】（1）输入表达式 7-2*3（2）输入表达式 7*3-5*4（3）输入表达式 2*(62*(3+6)（4）输入表达式 (6+6)*6+3)*2+6)*22.若输入的表达式为 (16+60)*6+3)*28+6)*2 检查执行结果是否正确？不正确，如何修改程序？提示：上面的算法只能处理只有一位数的四则运算，若是多位数据，则在识别出运算数的同时，要将其前面字符序列形式的数字转换成整型数压栈。修改此程序要求对含有多位数的表达式也能处理。实验三 二叉树的构造和遍历【实验目的】（1）熟练掌握二叉树的二叉链表存储结构 ；（2）掌握二叉树的非线性和递归性特点 ；（3）熟练掌握二叉树的递归遍历操作的实现方法；（4）加深对二叉树结构和性质的理解逐步培养解决实际问题的编程能力。【实验内容与要求】问题描述：树型结构是一类重要的非线性数据结构，尤其二叉树应用最广泛。基本实验内容：1.定义二叉树的链式存储结构；2.实现二叉树的基本操作：建空树、生成二叉树(先序,中序或后序)、判二叉树是否为空等基本算法；3.实现二叉树的递归(先序、中序或后序)遍历算法。【知识要点】 关于二叉树的链式存储结构定义、基本运算、先序遍历、中序遍历、后序遍历等概念请参见课本中所学的知识要点。图3-1给出二叉树的二叉链表存储表示。 图3-1二叉树的二叉链表存储结构【实现提示】 该问题分3部分：（1）定义二叉树的结构；（2）通过键盘输入二叉树的节点信息，建立二叉树。（3）按先序或中序或后序的原则遍历二叉树。【参考程序】 程序和定义内容如下： /* 二叉树遍历的递归算法*/#include#includetypedef char DataType;struct BinTreeNode; /* 二叉树中结点 */typedef struct BinTreeNode *PBinTreeNode; /* 结点的指针类型 */struct BinTreeNode DataType info; /* 数据域 */ PBinTreeNode lchild; /* 指向左子女 */ PBinTreeNode rchild; /* 指向右子女 */;typedef struct BinTreeNode *BinTree;typedef BinTree *PBinTree;PBinTreeNode root_btree(PBinTree t) return *t;/*以下算法是先将二叉树扩充为扩充的二叉树，即每个节点都有2个子树，若没有子树，就用字符代替。然后按先根次序周游的顺序输入结点的信息,生成一个双链存储的二叉树的过程*/PBinTreeNode createRest_BTree() /* 递归创建从根开始的二叉树 */ PBinTreeNode pbnode; char ch; scanf( %c,&ch); if ( ch = ) pbnode = NULL; else pbnode = (PBinTreeNode )malloc(sizeof(struct BinTreeNode); if (pbnode = NULL) printf(Out of space!n); return pbnode; pbnode-info = ch; pbnode-lchild = createRest_BTree();/* 构造左子树 */ pbnode-rchild = createRest_BTree();/* 构造右子树 */ return pbnode;PBinTree create_BTree( void ) /* 创建完整的二叉树 */ PBinTree pbtree = (PBinTree)malloc(sizeof(BinTree); if (pbtree != NULL) *pbtree = createRest_BTree( ); /* 递归创建从根开始的二叉树 */ return pbtree;void visit(PBinTreeNode p) printf(%c ,p-info); void preOrder(PBinTreeNode p) /*按先序递归遍历二叉树*/ if (p = NULL) return; visit(p); preOrder(p-lchild); preOrder(p-rchild); int main() /*主函数，先生成二叉树，然后先序遍历它*/ PBinTree tree; printf(create tree: ); tree=create_BTree(); printf(npreOrder: ); preOrder(*tree); putchar(n); return 0;【实验的具体要求】1.调试上面的程序，给出以下3组数据的给出程序的执行结果,并画出二叉树，写出三种遍历结果。1）键盘输入 abcdegf2）键盘输入 cbagdegf3) 键盘输入 abdefghik2.编写中序（后序）遍历的算法程序，上机调试通过，写出试验执行结果。【问题的其他方法和内容】 1、先序、中序、后序遍历的非递归算法的实现 2、 扩展实验内容：求某一个结点的双亲结点, 求某一个结点的左孩子（或右孩子）结点；求某一个孩子的左兄弟（或右兄弟）算法；利用栈，实现二叉树的非递归(先序、中序或后序)遍历算法；利用队列，实现层序递归遍历二叉树；定义线索二叉树的链式存储结构，建立线索二叉树，实现线索二叉树的插入和删除操作。实验四 排序方法的比较：冒泡排序法和快速排序法【实验目的】（1）掌握有序表、无序表查找的基本思想及存储、运算的实现（2）熟练掌握常用排序算法的基本思想及实现（3）深刻理解各种算法的特点，并加以灵活应用 （4）加深对查找和排序的理解，逐步培养解决实际问题的编程能力。【实验内容与要求】问题描述：排序是计算机程序设计中的一种重要操作，也是查找的基础。掌握各种排序算法是提高程序设计能力的关键。在随机生成的无序表上实现“冒泡”排序法和快速排序法。基本要求：建立一个无序表并实现其上的排序：实现冒泡排序和快速排序的基本算法，并比较他们的运行时间。 【知识要点】 关于表的存储和实现，以及“冒泡”排序法和快速排序法的基本思想参见书的内容。【实现提示】 该实验包括以下几部分：（1）编写一个产生随机数的函数，将数据保存起来。（2）利用产生的数据，实现“冒泡”法排序。（3）利用产生的数据，实现“快速”法排序。补充内容：1、随机数的产生 产生随机数的方法很多，最简单的一种方法是利用C语言的产生随机数函数random(n),产生一个小于n的随机数。该函数包含在头文件：#include 2、利用C语言的时间函数计算程序运行时间：有关时间函数请查阅：time(),ctime(),ftime(),difftime()等，请同学思考并查阅该用哪个函数，如何使用等相关问题。【实验的具体要求】产生1000个随机整数，分别用“冒泡”法和快速法编制程序进行排序，并比较他们的运行时间：（1） 编写一个程序产生1000个0-999的随机整数，并依次存入一个数组中。（2） 编写一个程序，将数组中的1000个数据用“冒泡”法进行排序，并保存结果。运行这个程序，并记下运行时间（3） 编写一个程序，将数组中的1000个数据用快速法进行排序，并保存结果。（4） 运行这个程序，并记下运行时间（5） 编写一个主程序，调用子函数，并输出排序前和排序后的各结果，以及运行时间，进行比较。【问题的其他方法和内容】1、在建立的无序表上实现顺序查找；在建立的有序表上实现折半查找等；充分理解排序和查找等各种算法2、构造哈希函数，实现哈希查找；建立二叉排序树并在其上查找指定关键字。附录一 参考实验报告模板实验报告包括以下7个内容： 1、需求分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？并明确规定：(1) 输入的形式和输入值的范围；(2) 输出的形式；(3) 程序所能达到的功能； (4) 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。2、概要设计说明本程序中用到的数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。3、详细设计实现程序模块的具体算法。4、调试分析内容包括：a调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；b算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想；c经验和体会等。5、用户使用说明说明如何使用你编写的程序，详细列出每一步的操作步骤。6.、测试结果列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。7、附录带注释的源程序。附录二补充习题第一章 绪论1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。1.2试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。1.3常用的存储表示方法有哪几种?1.4设三个函数f,g,h分别为 f(n)=100n3+n2+1000 , g(n)=25n3+5000n2 , h(n)=n1.5+5000nlgn 请判断下列关系是否成立：(1) f(n)=O(g(n)(2) g(n)=O(f(n)(3) h(n)=O(n1.5)(4) h(n)=O(nlgn)1.5设有两个算法在同一机器上运行，其执行时间分别为100n2和2n,要使前者快于后者，n至少要多大?1.6设n为正整数，利用大O记号，将下列程序段的执行时间表示为n的函数。(1) i=1; k=0; while(in) k=k+10*i;i+; (2) i=0; k=0; dok=k+10*i; i+; while(in);(3) i=1; j=0; while(i+jj) j+; else i+; (4)x=n; / n1 while (x=(y+1)*(y+1) y+;(5) x=91; y=100;while(y0) if(x100) x=x-10;y-; else x+;1.7算法的时间复杂度仅与问题的规模相关吗?1.8按增长率由小至大的顺序排列下列各函数：2100, (3/2)n，(2/3)n， nn ,n0.5 , n! ，2n ，lgn ,nlgn, n(3/2)第二章 线性表一、基础知识题2.1试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。 2.2何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 2.3在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素? 2.4为什么在单循环链表中设置尾指针比设置头指针更好? 2.5在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少? 2.6下述算法的功能是什么?LinkList Demo(LinkList L) / L 是无头结点单链表 ListNode *Q,*P; if(L&L-next) Q=L;L=L-next;P=L; while (P-next) P=P-next; P-next=Q; Q-next=NULL; return L;/ Demo 二、算法设计题2.7设线性表的n个结点定义为(a0,a1,.an-1)，重写顺序表上实现的插入和删除算法：InsertList 和DeleteList。 2.8试分别用顺序表和单链表作为存储结构，实现将线性表(a0,a1,.an-1)就地逆置的操作，所谓就地指辅助空间应为O(1)。 2.9设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。 2.10设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。 2.11写一算法在单链表上实现线性表的ListLength(L)运算。 2.12已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。 2.13设 A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)，请分析算法的时间复杂度。 2.14设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零。每当在链表进行一次LocateNode(L,x)运算时，令元素值为x的结点中freq域的值加1，并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法。 第三章 栈和队列一、基础知识题3.1设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：(1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)?(2) 能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。(3)请分析 1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。 3.2循环队列的优点是什么? 如何判别它的空和满? 3.3设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢?3.4指出下述程序段的功能是什么?(1) void Demo1(SeqStack *S) int i; arr64 ; n=0 ; while ( StackEmpty(S) arrn+=Pop(S); for (i=0, i n; i+) Push(S, arri); /Demo1(2) SeqStack S1, S2, tmp; DataType x; ./假设栈tmp和S2已做过初始化 while ( ! StackEmpty (&S1) x=Pop(&S1) ; Push(&tmp,x); while ( ! StackEmpty (&tmp) ) x=Pop( &tmp); Push( &S1,x); Push( &S2, x); (3) void Demo2( SeqStack *S, int m) / 设DataType 为int 型 SeqStack T; int i; InitStack (&T); while (! StackEmpty( S) if( i=Pop(S) !=m) Push( &T,i); while (! StackEmpty( &T) i=Pop(&T); Push(S,i); (4)void Demo3( CirQueue *Q) / 设DataType 为int 型 int x; SeqStack S;InitStack( &S); while (! QueueEmpty( Q )x=DeQueue( Q); Push( &S,x); while (! StackEmpty( &s) x=Pop(&S); EnQueue( Q,x ); / Demo3(5) CirQueue Q1, Q2; / 设DataType 为int 型 int x, i , n= 0; . / 设Q1已有内容， Q2已初始化过 while ( ! QueueEmpty( &Q1) ) x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); n+; for (i=0; i n; i+) x=DeQueue(&Q2) ;EnQueue( &Q1, x) ; EnQueue( &Q2, x); 二、算法设计题 3.5回文是指正读反读均相同的字符序列，如abba和abdba均是回文，但good不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈) 3.6利用栈的基本操作，写一个将栈S中所有结点均删去的算法void ClearStack( SeqStack *S)，并说明S为何要作为指针参数? 3.7利用栈的基本操作， 写一个返回S中结点个数的算法 int StackSize( SeqStack S),并说明S为何不作为指针参数? 3.8设计算法判断一个算术表达式的圆括号是否正确配对。 (提示： 对表达式进行扫描，凡遇到(就进栈，遇)就退掉栈顶的(，表达式被扫描完毕，栈应为空。 3.9一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。 试为此双向栈设计初始化InitStack ( S ) 、入栈Push( S , i , x) 和出栈Pop( S , i )等算法， 其中i为0 或1， 用以表示栈号。 3.10 Ackerman 函数定义如下：请写出递归算法。 n+1 当m=0时AKM ( m , n ) = AKM( m-1 ,1) 当m0 ，n=0时 AKM( m-1, AKM( m,n-1) 当m0, n 0时 3.11用第二种方法 ，即少用一个元素空间的方法来区别循环队列的队空和队满，试为其设计置空队，判队空，判队满、出队、入队及取队头元素等六个基本操作的算法。 3.12假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法