数据结构习题，求思路过程
点击联系发帖人
时间：2017-11-16 09:21
当前位置： >>
数据结构课习题参考答案
数据结构目录 一、 1.1 比较 2 个线性链表的 C 函数 ???????????????????????3 1.2 写一个倒置顺序存贮的线性表的 C 函数???????????????????31.3 写一个在线性表中，使线性表中没有值相同的结点的函数。??????????4 1.4 编写一个求解给定多项式的值的 C 函数。??????????????????5 1.5 实现多项式乘法?????????????????????????????6 1.7 车厢出站问题??????????????????????????????9 1.8 编写对任一栈作进栈和出栈运算的 C 函数?????????????????10 1.10 写出表达式等价的后缀表达式。?????????????????????12 1.11 编写一个统计给定的线性链表的结点个数的 C 函数。????????????15 1.12 编写一个将给定的线性链表逆转的 C 函数。????????????????16 1.13 编写一个插入值的 c 函数。???????????????????????18 1.14 编写一个删除链表中结点的前趋结点的 C 函数。??????????????19 1.15 试编写一个将两个链表归并成一个线性链表的 C 函数。???????????20 1.17 用环形链表解 1。6 题?????????????????????????23 1．18 将给定的线性链表改成环形链表????????????????????24 1． 19 将给定的线性链表改成一个带表头的环形链表??????????????25 1．20 编写用 hash 函数 h（Xi）＝Xi，对 X1，X2??X800 进行 hash 存储的程序?26 1． 21 求广义表的深度。??????????????????????????27 2．1 试编写一个在两个顺序字符串中寻找最大公共子串的 C 函数。????????29 2． 2 试编写一个实现 STRINS（S1，I，S2）的 C 函数。?????????????31 2．3 按照 2.2 题的要求，编一个实现 STRDEL（S，I，J）的 C 函数。???????32 3．1 编写一个二分插入排序的 C 程序?????????????????????33 3．2 编写一个对给定链表进行插入排序的 C 程序。???????????????34 3．5 采用顺序存储实现，即用数组存放排序过程中以排好序的链表的头指针。???36 3． 6 采用顺序存储的结构即数组实现。????????????????????38 3．7 编写一个实现快速排序的非递归的 C 函数。????????????????39 3．8 对于分别写出用下列排序方法对线性表进行排序的结果。??????????40 4．3 将 n 阶三对角阵（即半带宽为 1 的带状矩阵）A 按行序列序存放在一维数组 b[3*n-2]中。 若 aij(|i-j|&=1)存放在 b[k]中，请求出求解 k 的计算公式。?????????????42 4．4 如果把广义的 Anab 按行序列序存放在一维数组 b[(a+b-1)*n-(a+b-2)]中，元素 aij 存放在 b[k]中，那么请写出计算 k 的计算公式。????????????????????42 4．5 试编写一个求解两个三元数组相加的 C 函数。???????????????42 4．6 试编写一个将十字链表转置的 C 函数.???????????????????44 5．1 请分别给出对树进行前序、后序、层次序遍历后的结点序列。????????45 5．2 试叙述将 m 棵有序树组成的有序树林转换成相应的二叉树的逆变换。?????46 5．3 试编写一个把树中每个结点的左右子结点进行对换的 C 函数。????????47 5．4 编写一个利用栈来实现后序遍历一棵给定的二叉树的 C 函数。????????49 5．5 题目：????????????????????????????????51 试为下面各小题分别编写一个 C 函数： （1） 按前序输出 T 的结点值。 （2） 按后序输出 T 的结点值。 （3） 输出树 T 的叶子结点值。1 数据结构（4） 求出树 T 的次数。 5．6 试编写一个把树 T 按标准形式进行存贮的 C 函数。?????????????53 5．7 已知树 T 中结点的中序和后序，编写一个把 T 按标准形式存储的 C 函数????54 5．8 判断给定的二叉树是否为完全二叉树???????????????????55 5．9 判断两棵给定的二叉树是否相似?????????????????????55 5．10 把树 T 转换成由标准形式进行存储的树 T?????????????????55 5．11 试编写一个寻找结点 a 的父结点的 C 函数。????????????????56 5．12 试编写一个按前序遍历穿线树的 C 函数。?????????????????58 6．1 画出由集合中结点所构成的查找树，画出删除后的查找树。?????????60 6．2 试编写一个用平分法构造出由集合中结点所构成的丰满查找树的 C 函数。???60 6．5 编写一个判断给定二叉树 T 是否为平衡树的 C 函数。????????????62 6．6 试画出 Adelson 插入方法的右改组的转换图。???????????????65 6．9 试画出用 Hu-Tucker 算法构造出的最佳叶子查找树。????????????66 6．10 画出每次插入后的 B－树???????????????????????67 6．12 修改皇后问题????????????????????????????70 6．13 马的周游路线????????????????????????????76 7．1 对于图题 7.1（P235）的无向图，给出：?????????????????79 （1） 表示该图的邻接矩阵。 （2） 表示该图的邻接表。 （3） 图中每个顶点的度。 7．2 对于图题 7.1 的无向图，给出：?????????????????????79 （1）从顶点 1 出发，按深度优先搜索法遍历图时所得到的顶点序 （2）从顶点 1 出发，按广度优先法搜索法遍历图时所得到的顶点序列。 7．3 对于图题 7.3 的有向图，给出：?????????????????????84 （1） 表示该图的邻接矩阵。 （2） 表示该图的邻接表。 （3） 图中每个顶点的入度和出度。 7．4 对于图题 7.3 的有向图，给出：?????????????????????85 （1） 从顶点 1 出发，按深度优先搜索法遍历图时的所得的顶点序列。 （2） 从顶点 1 出发，按广度优先搜索法遍历图时的所得的定点序列。 7．5 对于图题 7.1 的无向图，试问它是（1）连通图吗？（2）完全图吗？?????85 7．6 对于图题 7.3 的有向图，试问它是（1）弱连通图吗？（2）强连通图吗？??86 7．7 图题 7-7 是有向图，试问其中哪个图是??????????????????86 （1） 弱连通的？ （2） 强连通的？ 7．8 具有 N 个顶点的连通无向图至少有几条边？????????????????86 7．9 具有 N 个顶点的强连通有向图至少有几条边？???????????????86 7．10 分别写出用深度和广度优先搜索法遍历完全无向图的顶点序列。?????? 87 7．11 改写以深度优先搜索法遍历给定的连通图的 dfs 程序。???????????87 7．12 在图题 7.1 中，从顶点 1 出发，分别画出其 dfs 生成树和 bfs 生成树。???882 数据结构1.1：比较 2 个线性链表的 C 函数1． 存储法：用两个数组存放线性表。 2． 存储结构：一般的顺序存储方式。 3． 源程序： int comp(int a[],int as,int b[],int bs) { int tmp=as&bs?as: for(i=0;i&i++) { if(a[i]&b[i]) return 1; if(a[i]&b[i]) return -1; } if(as&bs) return 1; if(bs&as) return -1; return 0; } 4.测试用例： 1． A[3]={1,2,3} B[3]={1,2,3} output : 0; 2． A[3]={1.2.3} B[3]={1,1,3} output: 1; 3． A[3]={1,2,3} B[3]={1,2,4} output: -1 4． A[3]={1,2,3} B[4]={1,2,3,0} output: -1; 5． A[4]={1,2,3,0} B[3]={1,2,3} output: 1; 6． A[4]={1,2,3,0} B[3]={1,3,2} output:-1;1.2写一个倒置顺序存贮的线性表的 C 函数。要求用最少的附加存贮空间来完成。 ? 分析：假设用数组 a 存贮一组 int 类型的数据，每次将 a[0]取出，其余数依次前移，然后 将 a[0]放到 尚未倒置的数据元素的最后，直至整个数组完成倒置。 （1） t=a[0]， 取 余下的 a[1]， （2） a[2]， ...a[n-1]依次前移一个位置； a[n-1]=t； ? 算法： （3）对由 a[0]，a[1]...a[n-2]组成的数组重复上述步骤。 ? 程序： # include&stdio.h& # define N 10 void reverse(a,n) int a[]; {int t,i,j=0; while(j&n-1) {t=a[0]; for(i=0;i&n-j-1;i++) a[i]=a[i+1];3 数据结构a[i]=t; j++; } } void main( ) {int a[N]; printf(&Input the array:\n&); for(i=0;i&N;i++) scanf(&%d&, &a[i]); reverse(a,N); printf(&The reversed array:\n&); for(i=0;i&N;i++); printf(&%d &,a[i]); printf(&\n&); } ? Sample: Input the array:
The reversed array: 1.3在具有 n 个结点的顺序存贮的线性表中，对值相同的结点只保留一个，把多余的结点删除 掉，使线性表中没有值相同的结点。试编写一个实现上述操作的 C 函数，并分析该程序的执 行时间。 解答： 首先应对线性表中每一个结点进行搜索，找到和他值相同的结点就把其删除，同时改变 原结点的个数。主要运用两层循环：最外层对线性表中的第 0 到第 n-2 个元素进行扫描，第 二层是对于第一层的每一个元素从其后面一个元素开始扫描，检查是否有和该元素值相同的 元素若有则删除该元素，若无则循环关键值+1 进行下一个元素比较，直到线性表最后一个元 素，然后在回到上层循环。如此继续，直到跳出所有循环时，所得线性表即为题目要求的线 性表。 下面给出实现的函数。Sq_delete()为删除一个结点的函数，i 表示所要删除的结点的下 标，del()为删除线性表中所有相同结点的函数。其中 list[]为进行操作的线性表，*p_m 和 *p_n 在两个函数中都表示线性表中结点个数。 #include&stdio.h& #define M 100 int sq_delete(int list[],int *p_m,int i) { if(i&0||i&=*p_m) return(1); for(j=i+1;j&*p_m;j++)4 数据结构list[j-1]=list[j]; (*p_m)--; return (0); } void del(int list[],int *p_n) { int i,j; for(i=0;i&((*p_n)-1);i++) for(j=i+1;j&(*p_n);j++) if(list[i]==list[j]){sq_delete(list,p_n,j);j--;} } main() { int list[M],i,n; printf(&Input the number of the data:\n&); scanf(&%d&,&n); for(i=0;i&n;i++){ printf(&Input data %d:\n&,i+1); scanf(&%d&,&list[i]); } del(list,&n); for(i=0;i&n;i++) printf(&%d &,list[i]); } 对于以上程序提供一组测试数据： Input the number of the data: 5L 输入一组数据为：13 23 33 13 23L 执行完毕后得到的输出结果为：13 23 33 对于该程序的时间复杂性分析： 主要是 del 和 sq_delete 两个函数中的循环语句的执行时间。 一种极端情况是线性表中 的数据没有一个重复，则只执行 del 中的循环体，(n-1)+(n-2)+??+1=O(n*n);另一种极端 情况是线性表中只有一个元素，其他都与它重复，此时 del 的内和外循环都只执行一次，主 要的执行时间用在了 sq_delete 上， 可以知道他的复杂性也是 O(n*n).故总的来说该程序的时 间复杂性是 O(n*n)。1.4编写一个求解给定多项式在 X=Xo(Xo 为指定的某个值)时的值的 C 函数。 存储法：定义结构数组 struct node { }; typedef struct node TERM #define max 1005 数据结构NODE a[max]; 算法步骤：1 令 sum=0, i=0 2 算出第 i 项的值，并与 sum 相加。 3 若 i&n, 则转 2，否则 return(sum) 程序： float cal ( float x, TERM a[ ], int n ) { int i, j, for ( i=0; i&n; i++ ) { for ( k=1, j=1; j&= a[i ]. E j++) k=k*x; sum+= a[i ].coef*k; } return(sum); } 测试用例： 令 x=2; 多项式为 3x6+8x4+5x2+9 结果为 349。1.5实现多项式乘法 一：存储结构： 多项式以线性链表存储，以增加其插入删除的效率。结果多项式与所给多项式采取相 同的存储结构，以方便实现多项式的连乘。 二：分析 多项式的加法书上有源程序，而乘法与加法相似，只是由于乘法的规则与加法不 同，因此我用了一个双重循环来实现（详见源程序） ，得到一个结果项之后，查找结果链 表，若已有，则看是否相加之后为 0，若为 0，则将该项删去，否则，就直接改系数，若 没有，则直接链上。 原本想用数组加链表的索引法来实现，但据分析后，认为并不能显著提高效率， 显得得不偿失，因此，我就使用了最原始的方法，请老师同学多多指教。 三：输入/输出 输入：先输入 A、B 多项式（根据提示） 输出：A、B、C（A×B） 四：源程序 #include&stdio.h& struct node{ struct node * }; typedef struct node NODE;6 数据结构int search(int exp,NODE *c,NODE **pc,NODE **qc) { *pc=NULL; *qc=c; if(c==NULL) return(0); while((*qc)-&exp&exp) {*pc=**qc=(*qc)-&} if((*qc)-&exp==exp) return(1); return(0); }NODE *multi(NODE *a,NODE *b) {NODE *pa,*pb,*pc,*qc,*p,*c=NULL; int exp,data, for(pa=a;pa!=NULL;pa=pa-&next) for(pb=b;pb!=NULL;pb=pb-&next) {exp=pa-&exp+pb-&data=pa-&data*pb-& if(data) {flag=search(exp,c,&pc,&qc); if(flag) if(!(data+qc-&data)) {pc-&next=qc-&free(qc);} else (qc-&data)+= else {p=(NODE *)malloc(sizeof(NODE)); p-&data=p-&exp= if(!pc) c=p; else pc-&next=p; p-&next= } } } return(c); }NODE* creat() {NODE *root,*p,*q; printf(&Do you want to creat a null one(Y/N)?\n&); scanf(&%c&,&ch); getchar(); if(ch=='y'||ch=='Y') return(NULL); p=NULL;7 数据结构ch='y'; for(i=0;ch=='y'||ch=='Y';i++) {q=(NODE*)malloc(sizeof(NODE)); if(p==NULL) root=q; else p-&next=q; printf(&\nPlease input the DATA of node %d:\n&,i); scanf(&%d&,&(q-&data)); getchar(); printf(&Please input the EXP of node %d:\n&,i); scanf(&%d&,&(q-&exp)); getchar(); printf(&Do you want to continue(Y/N)?\n&); scanf(&%c&,&ch); getchar(); p=q; } p-&next=NULL; return(root); } void print(NODE *root) {int i=0; if(!root) printf(&\n0&); while(i++,root!=NULL) {printf(&\nNODE %d:\tDATA:%d\tEXP:%d&,i,root-&data,root-&exp); root=root-& } }main() { NODE *a,*b,*c; clrscr(); printf(&Now please input A:\n&); a=creat(); printf(&Now please input B:\n&); b=creat(); printf(&\nA:\n&); print(a); printf(&\nB:\n&);8 数据结构print(b); c=multi(a,b); printf(&\n\n\nC:\n&); print(c); } 五：测试数据： 输入： A：5X^6+3X^4+2X B：7X^3+3X^2+5 输出： C：35X^9+15X^8+21X^7+34X^6+29X^4+6X^3+10X 输入： A：0 B：5X^3+2X^2 输出：0 输入： A：3X^2+5X^1 B：3X^1－5 C：01.7假设右边轨道排列有编号为 1，2，3,?,n 的 n 节车厢，它们依次被拖进站，从左边轨道依次 出站的号的排列顺序有 a n 种情况 。那么 a n 是用下列方法所形成的所有可能排列顺序的总 数：某时刻站中只剩下编号为 k+1 的车厢，而此时左边轨道是已出站的编号为 1，2，3，?,k 的车厢， 则排列顺序有 ak 种； 右边轨道是尚未进站的编号为 k+1， k+2,?,k+n 的 n-k-1 节车厢， 则可能有的排列顺序有 an-k-1 种。因此 给出了前 k 节车厢已出站的情况下所有的排列顺 序，我们应该取遍 k（0≤k≤n）的所有可能值，获得 akan-k-1 这样形式的所有项，然后把它 们相加起来，可得到如下的关系式： a0=1； a1=1； an=a0an-1+a1an-2+...+an-1a0( n&1)an=∑akan-k-1 (0≤k≤n-1) 为了求解排列顺序的数目，先求解这个递推关系： 令 g（x）=a0+a1x+?+anx? n&1 即 g（x）=∑akxk (k≥0) 让 g（x）自乘得 g2(x)=g(x)g(x) =(a0+a1x+a2x2+...)(a0+a1x+a2x2+...)9 数据结构=a0a0+(a0a1+a1a0)x+(a0a2+a1a1+a2a0)x2+... =Σ (Σ akan-k)x? (0≤n,0≤k≤n) 由上式可知，g2(x)的 xn 项的系数正好是 an＋1。因此有 g2(x)=∑an+1x? (n≥0) 如果我们用 x 乘 g2(x)，则有 xg2(x)=a1x+a2x2... 两边都加上 a0，又因为 a0=1，故有 1+x g2(x)=∑akxk 1+xg2(x)=g(x) 求解得 g（x）=[1±√(1-4x)]/2x 因为 a0=1，所以 g（x）=1-√(1-4x)]/2x 再根据二项式定理，将(1-4x)1/2 展开，得 g(x)=1/2x[1-∑(1n/2)(-4x)n] 令 n=m+1,则有 g(x)= ∑( 1/2m+1)(-1)m 22m+1xm 比较可知 an 是上式中 x?项的系数。 所以 an=(1n+1/2)(-1)n22n+1 化简得 an=1/(n+1)(2nn) n 节车厢出站有 1/(n+1)(2nn)种排列顺序。 (n≥0) (m≥0) (k≥0)所以， 当 n=3 时，有 5 种排列顺序，分别为 ①②③，①③②，②①③，②③①，③②①； 当 n=4 时，有 14 种排列顺序。 存储结构可采用栈实现。1_8. 假设 2 个栈共享一个数组 stack[n]，编写对任一栈作进栈和出栈运算的 C 函数，push(x,i) 和 pop(i),i=1,2。这里 i=1 表示左边的栈，＝2 则表示右边的栈。要求整个数组元素都被占用时才 产生溢出。 存储结构： 用一个数组存放 2 个栈。如图：(M 为数组元素个数) 3 2↑ ↑ ↑ ↑ tail1=0 head1 head2 tail2=M-1 head1,head2 分别为栈 1，栈 2 中下个元素入栈的位置，tail1，tail2 为两个栈底。 分析与算法步骤： 因为 tail1＝0,tail2＝M－1，一般情况下不会变动，所以省去这 2 个量。 初始值：head1＝0，head2＝M-1； 1．执行入栈时：10 数据结构（1） 若 head1-1+1＝head2+1，即 head1＝head2+1 时，整个数组满，溢出。 （2） 若对栈 1 入栈，把元素存入 stack[head1]，head1++； （3） 若对栈 2 入栈，把元素存入 stack[head2]，head2DD； 2．执行出栈时： （1）对栈 1： 若 head1＝0，栈空，出栈失败； 否则 head1DD； （2）对栈 2： 若 head2＝M－1，栈 2 空，出栈失败； 否则 head2++； tc 程序： include&stdio.h& #define M 10 int head1=0,head2=M-1; int stack[M]; void push(int x,int i) {if(head1==head2+1) {printf(&the stack is full.fail to push.\n&); } if(i==1) stack[head1++]=x; else stack[head2--]=x; } void pop(int i) {if(i==1) {if(head1==0) {printf(&the stack is empty.fail to pop.\n&); } *p=stack[--head1]; } else {if(head2==M－1) {printf(&the stack is empty.fail to pop.&); } *p=stack[++head2]; } }11 数据结构main() {int x,i,No=1; for(i=0;i&M;i++) stack[i]=0; while(No!=0) {printf(&seclect the operation:\npush:1;\npop:2;\nprint:3\nexit:0;\n&); scanf(&%d&,&No); switch(No) {case 1: printf(&input the number you want push and the team No,\n&); scanf(&%d %d&,&x,&i); if(i==1||i==2) push(x,i); else printf(&wrong number.select again.\n&); case 2: printf(&input the team you want to pop:\n&); scanf(&%d&,&i); if(i==1||i==2) pop(i); else printf(&wrong number,select again.\n&); case 3: for(i=head1-1;i&=0;i--) printf(&%d&,stack[i]); printf(&\n&); for(i=head2+1;i&M;i++) printf(&%d&,stack[i]); printf(&\n&); } } } 测试用例： 在 main 函数中，提供了操作的选择。1 为入栈，2 为出栈，3 为输出 2 个栈中的元素，0 为退出操作。 第一次进栈 1：1，2，3，4，5； 输出：12345 第二次进栈 2：6，7，8，9，10； 输出：678910 栈 1 连续出栈 5 次后，继续执行出栈，输出为 the stack is empty.fail to pop. 栈 2 连续出栈 3 次后，输出栈 2 中元素为 9101．10写出与下列表达式等价的后缀表达式： (1) a+b*c/d+e^f^g+h (2) (a+b)*(c/d)+(e^f)^(g+h)12 数据结构存储结构： 对于两个表达式采用字符数组存储形式，并以‘\0?作为结尾。 另外，使用一个栈来存放运算符，当遇到运算符,就把运算符入栈，直到某个适当的时机， 再让运算符出栈。 算法分析： 当前扫描到的字符按以下几种情况分别处理： a) 若当前的字符是变量，则立即将它输出。 b) 若当前的字符是?(?，则让?(?入栈。 c) 若当前的字符是运算符(?+?,?-?,?*?,?/?,?^?),则将它的（进栈前)优先级别与栈顶字符的（栈 中）优先级别相比较。如果当前的运算符的优先级别小于等于栈顶字符的优先级别，那 么退出栈顶字符并输出。 这样的过程一直进行到当前的运算符的优先级别大于栈顶字符 的为止，然后让当前的运算符入栈。 d) 若当前的字符是?)?，则从栈中依次退出运算符并输出，直到?(?为止，然后退出?(?，但不 输出?(?. e) 若当前的字符是?\0?,则从栈中依次退出所有的运算符并输出，直到?$?为止，?$”不退栈， 也不输出。 下面给出程序： #define MAXN 100 int icp(char c) { switch(c) { case '^':return(4); //进栈前的运算符的优先级 case '*': case '/':return(2); case '+': case '-':return(1); } } int isp(char c) { switch(c) { case '^':return(3); //栈中的运算符的优先级 case '*': case '/':return(2); case '+': case '-':return(1); case '(':return(0); case '$':return(-1);//置于栈底，保证后面的运算符能进栈 } } int ischar(char c) { if((c&='A'&&c&='Z')||(c&='a'&&c&='z')) return(1); else return(0);13 数据结构} int mid_to_pos(char midexpress[],char posexpress[]) {char stack[MAXN],c; int top,i,j; stack[0]='$'; top=0; j=0; i=0; c=midexpress[0]; while(c!='\0') { if(ischar(c)) posexpress[j++]=c; else switch(c) { case '+': case '-': case '*': case '/': case '^': while(icp(c)&=isp(stack[top])) posexpress[j++]=stack[top--]; stack[++top]=c; case '(': stack[++top]=c; case ')': while(stack[top]!='(') posexpress[j++]=stack[top--]; top--; default: return(1); } c=midexpress[++i]; } while(top&0) posexpress[j++]=stack[top--]; posexpress[j]='\0'; return(0); } 测试报告： void main()14 数据结构{char midexpress[MAXN],posexpress[MAXN],c; int i, i=0; printf(&\ninput the mid_expresstion:(end with '!')\n&); scanf(&%c&,&c); while(c!='!') { midexpress[i++]=c; scanf(&%c&,&c); } midexpress[i]='\0'; result=mid_to_pos(midexpress,posexpress); if(result==1) printf(&convertion fails!\n&); else { printf(&the pos_expresstion is:\n&); printf(&%s&,posexpress); } } 输入：(a+b*c)^d^(e*f/g)-h*i!(输入以?!?结尾) 输出：abc*+def*g/^^hi*输入：a+b*c/d+e^f^g+h! 输出：abc*d/+efg^^+h+ 输入：(a+b)*(c/d)+(e^f)^(g+h)! 输出：ab+cd/*ef^gh+^+1．11编写一个统计给定的线性链表的结点个数的 C 函数。 存储结构： 连表的结点采用： struct node{//关键字的类型自定 struct node *}; 算发分析： 利用链表的性质（结点中的指针指向下一个结点） ，逐步向表尾移动，以此计算出结点 数。 下面给出程序： typedef struct node{ struct node * }NODE; int count(NODE *head) {NODE *p;15 数据结构int c=0; p= while(p!=NULL) {p=p-& c++;} return(c); } 测试报告： void main() {NODE a[10]; int i=0; for(;i&9;i++) {a[i].data=i; a[i].link=&a[i+1];} a[i].data=i; a[i].link=NULL; printf(&the total amount of the linked node is:%d\n&,count(&a[0])); } 输入：|0---1---2---3---4---5---6---7---8---9^ 输出：the total amount of the linked node is:101．12编写一个将给定的线性链表逆转的 C 函数，只允许改变结点的指针值，不允许移动结点值。 算法如下： (1) 置 P 为链表首址，R,Q 为空； ，否则转（3） ； (2) 若 P 为空返回 NULL；算法结束，转（5） ，否则转（4） ； (3) 若链表只有一个结点，转（5） ，否则转（4） ； (4) R&=P,P&=P-&LINK,R-&LINK&=Q,置 Q=R,若 P-&LINK 为空，转（5） (5) P-&LINK&=R,返回 P,算法结束。 源程序如下： #include &stdio.h& typedef struct node{ struct node* }NODE; NODE* tranfer(head) NODE * { NODE *p,*q,*r; p= r=q=NULL; if(head==NULL) return(NULL);16 数据结构if(p-&link!=NULL) {do{ r=p; p=p-& r-&link=q; q=r; }while(p-&link!=NULL); } p-&link=r; return(p); } NODE* create(n)/*建立初始链表*/ { NODE *head,*p,*q; if(n==0) return(NULL); head=(NODE*)malloc(sizeof(NODE)); p= for(i=1;i&n;i++) { scanf(&%d&,&(p-&data)); q=(NODE*)malloc(sizeof(NODE)); p-&link=q; p=q; } scanf(&%d&,&(p-&data)); p-&link=NULL; return(head); } main() { NODE *head,*r,*p; int n=5; printf(&enter the data:\n&); head=create(n); p= while(p!=NULL) { printf(&%d &,p-&data); p=p-& }17 数据结构printf(&\n&); head=tranfer(head); p= printf(&now the list is:\n&); while(p!=NULL) { printf(&%d &,p-&data); p=p-& } printf(&\n&); } 输入：1 2 3 4 5 输出：5 4 3 2 11.13对于给定的线性链表,编写一个把值为 a 的结点插在值为 b 的结点的前面的 c 函数。若值为 b 的结点不在线性链表中，则把 a 插在表的最后。 [存储结构] 利用线形表的链接存储： typedef struct node{ struct node *}NODE; 定义指针 NODE **head,*p,*q,*t; [解题思路] 指针*head 指向链表的根结点，指针 p 指向值为 b 的结点，指针 t 指向它的前趋结 点，指针 q 指向插入结点 a。 (1) 如果头结点*head 为空，或*head 的结点值为 b，修改头指针，结束算法； (2) 查找值为 b 的结点，若找到，把值为 a 的结点插到 b 的前面； (3) 若找不到，把 a 结点插在链表最后；结束算法。 #include&stdio.h& [程序] typedef struct node{ struct node *}NODE; void insert(NODE **head,char a) {NODE *p,*q,*t; q=(NODE*)malloc(sizeof(NODE)); q-&data=a; if(*head==NULL||(*head)-&data=='b') {q-&link=* *head=q;} for(p=*p-&data!='b'&&p!=NULL;p=p-&link) t=p; q-&link=p; t-&link=q; } [测试用例 1] 原链表：b,c,d,e,g,h18 数据结构插入 a 结点后：a,b,c,d,e,f,g,h [测试用例 2] 原链表：c,d,e,f,g,h 插入 a 结点后:c,d,e,f,g,h,a [测试用例 3] 原链表：c,d,e,b,f,g,h 插入 a 结点后:c,d,e,a,b,f,g,h1-14对于给定的线性链表，编写一个删除链表中值为 a 的结点的前趋结点的 C 函数。 [存储结构] 线性链表采用标准形式存储的单链表，并使用如下的说明： typedef struct node{ struct node* }NODE; [算法] 假设给定的单链表的头指针为 head， 我们将指向 head 的指针 p_head 作为函数 fro_del 的参数。 为了删除值为 a 的结点的前趋结点，我们使用 3 个 NODE 类型的指针 p1，p2，p3。初始时， 置 p1=*p_head,p2=NULL,p3==NULL. 循环过程中,p1 不断向前探索，p2 始终指向 p1 的前趋结点，p3 又始终指向 p2 的前趋结点,直 到 p1-&data==?a?或 p1==NULL 结束。 （1） 若结束是由 p1==NULL 引起的，则未找到值为 a 的结点，删除失败，返回 1。 （2） 若结束是由 p1-&data==?a?引起的，并且此时 p2==NULL,则结点 a 为头结点，没有前趋 结点，故删除失败，返回 1。 （3） 否则，删除 p2 指向的结点,并返回 0。删除中，如果 p2 为头结点，置*p_head==p1;否 则，置 p3-&link==p1。删除成功。 [流程图] YP1=NULL n n P1-&data=aNY YP2=NULL ?NP3=p2N YP2=head?P2=p1 P1=p1-N&link*p_head=p1 返回 1P3-&link=p1返回 0[C 程序] int fro_del(NODE** p_head) {19 数据结构NODE * p1=*p_head,*p2=NULL,*p3==NULL; If(p1==NULL)return(1); Whie(p1!=NULL&&p1-&data!=?a?) { p3=p2; p2=p1; p1=p1-& } if(p1==NULL||p2==NULL)return(1); if(p2==*p_head)*p_head=p1; else p3-&link=p1; free(p2); return(0); } [测试] （1）如果原单链表为空或为 bcdef，则删除失败。 （2）如果原单链表为 a 或 abcdef，则删除失败。 （3）如果原单链表为 bacdef，则删除为 acdef。 （4）如果原单链表为 bcadef，则删除后变为 badef。1.15设 X=（x0,x1,…,xm-1）和 Y=(y0,y1,…yn-1)是两个线性链表。试编写一个将这两个链表归并 成一个线性链表 Z 的 C 函数，使得 m&=n 时 Z=（x0,y0,x1,y1,…,xm-1,ym-1,ym,…yn-1） m&n 时 Z=(x0,y0,x1,y1,…xn-1,yn-1,xn,…xm-1) 存储结构：#include&stdio.h& typedef struct node{ struct node * }NODE; 分析和算法操作： 需要一个由字符串生成链表的函数。 将两个链表归并成一个链表时在表头前附加一个虚结点，处理完后再将其释放掉。若无虚结 点归并时需分情况处理，比较复杂。 #include&stdio.h& typedef struct node{ struct node * }NODE; NODE *makelist(a) char a[]; {NODE *head,*p,*q; if(a[0]=='\0')return(NULL);20 数据结构head=(NODE *)malloc(sizeof(NODE)); head-&data=a[0]; head-&link=NULL; p= for(i=1;a[i]!='\0';i++) {q=(NODE *)malloc(sizeof(NODE)); q-&data=a[i]; q-&link=NULL; p-&link=q; p=q; } return(head); } NODE *linklist(p,q) NODE *p,*q; {NODE *head,*r,*s; head=(NODE *)malloc(sizeof(NODE)); head-&link=NULL; r= while(p!=NULL&&q!=NULL) {r-&link=p;s=p-& p-&link=q; r=q;p=s;q=q-& } while(p!=NULL) {r-&link=p;r=p;p=p-&} while(q!=NULL) {r-&link=q;r=q;q=q-&} s= head=head-& free(s); return(head); } main() {char a[100],b[100]; NODE *xhead,*yhead,* printf(&input a string:\n&); scanf(&%s&,a); printf(&input a string:\n&); scanf(&%s&,b); xhead=makelist(a); yhead=makelist(b); zhead=linklist(xhead,yhead); while(zhead!=NULL)21 数据结构{printf(&%c-&&,zhead-&data); zhead=zhead-& } } 测试用例： 输入：ABCDEF 和 GHIJKLMN 输出：A-&G-&B-&H-&C-&I-&D-&J-&E-&K-&F-&L-&M-&N1_15二．题目： 设 X= ?x0 , x1 ,...,xm?1 ? ,Y= ? y0 , y1 ,..., yn?1 ? 是两个线性链表，试编写一个将这两个线性链 表归并成一个线性链表 Z 的 C 函数，使得 Z= ??( x0 , y 0 , x1 , y1 ,?, xm?1 , y m?1 ,?, y n ?1 ) 当m ? n时 ? ( x0 , y 0 , x1 , y1 ,?, xn?1 , y n?1 ,?, y m?1 ) 当m ? n时三．算法分析： （1） 若 X 表或 Y 表为空，返回表 Y，否则进入（2） ； （2） 将 Y 表相应结点 y(i)插入 X 表中 x(i)与 x(i)-&link 之间； （3） 如果 Y 表仍有剩余，将其插入以上生成的 Z 表中。 四．程序如下： typedef struct T { struct T * }NODE; NODE *merge(NODE *x,NODE *y) { NODE *z=x,* if(x==NULL) if(y==NULL) while(x&&y){ yn=y-&/*yn:*/ y-&link=x-& x-&link=y; if(y-&link==NULL) x=y-& y= } if(y-&link==NULL) y-&link=22 数据结构 }1_171. 存贮结构: 按题目要求,采用环形链表实现. 2. 存储方式: 用链接存储的环形队列实现. 3. 源程序: #include &stdio.h& struct node { struct node * }; typedef struct node NODE; NODE *crearl(int n) { NODE *head,* head-&data=1; new= for(i=1;i&n;i++) { new-&link=(NODE *)malloc(sizeof(NODE)); new=new-& new-&data=i+1; } new-&link= } void printrl(NODE *head,int i,int k) { NODE *p,*q; p= if(i!=1) { q=NULL; while(p-&data!=i) { q=p; p=p-& } } else23 数据结构{ while(p-&link!=head) p=p-& q=p; p=p-& } for(a=0;a&k-1;a++) { q=p; p=p-& } printf(&the result is:&); while(p-&link!=p) { printf(&%d &,p-&data); q-&link=p-& free(p); p=q-& for(a=0;a&k-1;a++) { q=p; p=p-& } } printf(&%d &,p-&data); } void main() { int n,i,k; NODE * clrscr(); printf(&input n,i,k:&); scanf(&%d%d%d&,&n,&i,&k); head=crearl(n); printrl(head,i,k); } 4. 测试用例: n=10,I=1,k=3 output:3 6 9 2 7 1 8 5 10 4 n=10 I=5 k=12 output:6 9 3 10 8 2 1 7 5 41_181. 存储结构:按题目要求为一般线形链表 2. 存储方式:用链表实现24 数据结构3. 源程序: NODE *nltorl(NODE *head) { NODE *tmp= While(tmp-&link!=NULL) Tmp=tmp-& Tmp-&link= R } 4.测试用例: 经过将普通链表测试,可以转为环形链表.1_19假设给定的线性链表的结点值为整数。编写一个将给定的线性链表改造成一个带表头结点的 环形链表的 C 函数，并让表头结点的值等于原来线性链表中结点的个数。 ? 分析：先数出原链表中结点的个数，存入新开辟的表头结点中，将表头结点连到原链表表 头上，并将表尾指针指向表头结点，head 指向表头结点。 ? 程序： # include&stdio.h& typedef struct node{ struct node * }NODE; NODE* convert(NODE* t) /*t 为原链表的表头结点*/ {NODE *head,*p,*q,*k; int n=0; k=(NODE*)malloc(sizeof(NODE)); k-&data=n; k-&link=NULL; head=k; if(t==NULL) {k-&link=k;return(head);} p=t; k-&link=p; while(p!=NULL) {q=p;p=p-&n++;} q-&link=k; k-&data=n; return(head); } 在 main 中只需调用 convert 函数即可完成所要求的转化，函数返回值即为指向环形链 表表头的 head 指针。25 数据结构1_20y0=568731 yi=(15625*yi-1+22221)mod m xi=1000*yi/m (1&=i&=800) x1,x2,?,x800 是 0~999 之间的 800 个伪随机数。试按下面两种要求分别编写用 Hash 函 数 h（xi）=xi，对 x1,x2,?,x800 进行 Hash 存贮的程序： （1） 用开式寻址法解决冲突。 （2） 用拉链法解决冲突。 ? ? 分析：开式寻址法是在发生冲突时用循环地址探测序列进行线性探测，找出空位置可供 插入，而拉链法则是把具有相同 Hash 地址的的键值都存放在同一个链表中。 程序： 1） 开式寻址法： # include&stdio.h& # define M 1000 31 # define m 2 int x[801]; long int y[801]; int t[M]; void main( ) {int i,j,k; y[0]=568731; for(i=1;i&801;i++) {y[i]= (15625*y[i-1]+22221)% x[i]= 1000* y[i]/m; } for(i=0;i&M;i++) t[i]= -1; /* 因 x[i]是非负数，所以初始化 Hash 表时 t[i]全置为-1*/ for(i=1;i&801;i++) {j= x[i]; for(k=0;k&M&&t[(j+k)%M]&=0;k++); j=(j+k)%M; if(t[j]&0) t[j]= x[i]; } } 2） 拉链法 # include&stdio.h& # define M 1000 31 # define m 2 typedef struct node{ struct node* }NODE; 设 m=23126 数据结构int x[801]; long int y[801]; NODE *t[M]; void main( ) { NODE * p,*q,* y[0]=568731; for(i=1;i&801;i++) {y[i]= (15625*y[i-1]+22221)% x[i]= 1000* y[i]/m; } for(i=0;i&M;i++) t[i]= NULL; for(i=1;i&801;i++) {p=t[x[i]]; q=NULL; while(p!=NULL) {q=p;p=p-&} r=(NODE*)malloc(sizeof(NODE)); r-&key= x[i]; r-&link=NULL; if(q= =NULL) t[x[i]]=r; else q-&link=r; } }1_21求广义表的深度。我们规定空的广义表的深度为 0，而一般的有 0 若 s?是一个原子 depth(s)= { 1+max(depth(a0),? depth(an-1)) 若 s 是广义表（a0,a1,?an-1） 编写一个求解广义表 s 的深度的 C 函数。 解答： 有题目给出的深度的公式，很容易想到运用递归来实现所要求的功能。这里在主函数中简单 的采用直接构造各种类型的广义表法，为了测试算深度函数的有效性。 #include&stdio.h& struct node{ union{struct node * }27 数据结构struct node * }; typedef struct node NODE; int depth(NODE *p) { int max,t; if(p==NULL)return(0); if((p-&tag)==0)max=1; else max=depth(p-&dd.dlink)+1; t=depth(p-&link); return(t&max?t:max); } main() { NODE *head,*p; int d,i; char k='a'; head=NULL; /*(1)*/ d=depth(head); printf(&the depth is:%d\n&,d); head=(NODE *)malloc(sizeof(NODE)); /*(2)*/ head-&tag=0; head-&dd.data=k; head-&link=NULL; p= for(i=1;i&4;i++){ p-&link=(NODE*)malloc(sizeof(NODE)); p=p-& p-&tag=0; p-&dd.data=k+i; p-&link=NULL; } d=depth(head); printf(&the depth is:%d\n&,d); k='e'; /*(3)*/ p= for(i=1;i&4;i++){ p-&tag=1; p-&dd.dlink=(NODE*)malloc(sizeof(NODE)); p=p-&dd. p-&tag=0; p-&dd.data=k; p-&link=NULL; } d=depth(head); printf(&the depth is:%d\n&,d); }28 数据结构在主函数中构造了三种结构各异的广义表。 （1） 空的广义表，得到的深度为 0。 （2） 0,a,-&0,b-&0,c-&0,d，^ 得到的深度为 1。 （3） 1，K，-》0,b-&0,c-&0,d^ 得到的深度为 4。 1,K,^ 1,K^ 0,e,^2_1假设 s 和 t 分别是具有 m 个和 n 个字符的顺序存贮的串。试编写一个在 s 和 t 中寻找最大公 共子串的 C 函数。 解答： 该题的本质即为模式匹配，实际上是把 t 中所有可能长度的子串与 s 进行模式匹配，从最长 长度 n 开始，若匹配成功就直接输出当前子串，否则长度自减 1 后重新开始匹配。直到长度 减为 0，此时则说明没有公共子串。下面的 C 函数利用了书中列出的几个函数实现了题目所要 求的功能。 #include&stdio.h& #include&string.h& #define MAXN 100 char t[MAXN],s[MAXN]; int flink[MAXN]; int m,n; int strsub(char s1[],int i,int j,char s2[]) { int m,k; if(i&0||i&=(m=strlen(s1))) return(-1); if(j&0||i&m) return(-1); for(k=0;k&j;k) s2[k]=s1[i]; s2[k]='\0'; return(0); } void faillink(char p[],int flink[],int m) {int j,k; flink[0]=-1; j=1; while(j&m) { k=flink[j-1]; while(k!=-1&&p[k]!=p[j-1]) k=flink[k]; flink[j]=k;29 数据结构j; } } int kmp_match(char t[],char p[],int flink[],int n,int m) { int i,j; i=0; j=0; while(i&n) { while(j!=-1&&p[j]!=t[i]) j=flink[j]; if(j==m-1)return(i-m); } return (-1); } void search_max(char s[],char t[],int m,int n) { char temp[MAXN]; int i,j,k; i=n; while(i&0) { k=0; while(k1&n){ strsub(t,k,i,temp); faillink(temp,flink,i); if(kmp_match(s,temp,flink,m,i)!=-1) { printf(&The max match is:\n&); for(j=0;j&i;j) printf(&%c &,temp[j]); } } i--; } printf(&No match found!\n&); } main() { printf(&Input the length of S's string:\n&); scanf(&%d&,&m); printf(&Please input the S's string:\n&); scanf(&%s&,s); printf(&Input the length of T's string:\n&);30 数据结构scanf(&%d&,&n); printf(&Please input the T's string:\n&); scanf(&%s&,t); search_max(s,t,m,n); } 运行示例： Input the length of S’s string: 8L Please input the S’s string: adgabcdeL Input the length of T’s string: 6L Please input the T’s string: fabcdgL 最后输出：a b c d2_2假设所使用的串采用链接存储结构，链表中每个结点可存放 M（M=4）个字符。试编写一个实 现 STRINS（S1，I，S2）的 C 函数。为了减少移动字符的次数，结点中允许使用无效的特殊字 符，但一个结点至少含有一个有效的字符。 存储法：struct node { char data[4]; struct node * }; typedef struct node NODE; 算法步骤： 1． 通过 i/4 算出 所在的结点 2． 通过 k= i %4 算出 i 在该结点中的位置 3． 开设一新结点，把该结点中 k 后的字符赋给新结点 4． 把该结点中赋过的字符及新结点中未赋过值的都置成无效字符‘*’ ， 5． 使新结点指向该结点的后继，该结点指向 s2 首结点，并把 s2 的末结点中的‘\0’置 成’ ，末结点指向新结点。 ‘*’ void strins(NODE *s1, int i, NODE *s2) { int j, k, l, NODE *p, *q, *r; j=i/4; k=i%4; p=s1; for(l=0; l !=j; l++)p=p-& q=(NODE *)malloc(sizeof(NODE)); for(m=k;m&4&&p-&data[m]!='\0';m++)31 数据结构{ q-&data[m-k]=p-&data[m]; p-&data[m]='*'; /* '*'is invalid char */ } if(p-&data[m]=='\0')q-&data[m-k]='\0'; else for(l=k;l&4;l++)q-&data[l]='*'; r=s2; while(r-&link!=NULL)r=r-& for(m=0; r-&data[m]!=’\0’; m++); r-&data[m]=’*’; while( m&4) r-&data[++m]=’*’; q-&link=p-& p-&link=s2; r-&link=q; } 若 S1=“ABCDEFGHI” ；S2=“JKLMNOP” ；I=6； 则调用后得 “ABCDEF**JKLMNOP*GHI2_3按照 2.2 题的要求，编一个实现 STRDEL（S，I，J）的 C 函数。 存储法同 2.2 算法步骤： 1． 计算出 S 中结点的个数 L 2． 通过 I/4 计算出其在 S 中的哪个结点 3． 通过 I%4 算出其在该结点中的位置 4． 若（I+J-1）/4 &L 则置该位置为‘*’ ； 否则，将 I 位所在结点中的所在位及其后均置为‘*’ ； 并将（ I+J-1）/4 位所在结点中的所在位及其前均置为‘*’ ； 5． 最后使 I 位所在结点指向（ I+J-1）/4 位所在结点 void strdel(NODE *s, int I，int j) { int k,l,m,h; NODE *p, *q; k=i/4; h=i%4; q=p=s; l=0; while(p-&link!=NULL) { p=p-& l++; } for(m=0;m!=k;m++)p=p-& if((i+j-1)/4&l)p-&data[h]='\0'; else { for(m=0;m!=(i+j-1)/4;m++)q=q-&32 数据结构for(m=h;m&4;m++)p-&data[m]='*'; for(m=(i+j-1)%4;m&=0;m--)q-&data[m]='*'; /* '*' is invalid char */ p-&link=q; } } 若 S=“ABCDEFGHIJKLMNO” ，I=3, j=10 则调用后结果为 “ABC* ***LMNO”3_1编写一个二分插入排序的 C 程序 一：数据结构 用一个数组 a 来存储数据元素，线性存储可以方便存储。 二：具体分析 使用二分查找来代替线性查找来进行插入操作可以显著提高效率，因此， 编写了一个 bi_search 函数来进行查找， 返回一个需要插入的位置给 j， 然后将 a[j]以后的元素 都向后移一个位置，将 a[i]放入 a[j]的位置。本题难度不高。 三：源程序 int bi_search(int a[],int n,int v) {int i,j,m; i=0; j=n-1; while(i&=j) {m=(i+j)/2; if(v==a[m]) return(m); if(v&a[m]) j=m-1; else i=m+1; } } void bi_insertion_sort(a,n) int a[]; {int i,j,k,x; for(i=1;i&n;i++) { x=a[i]; j=bi_search(a,i,x); for(k=i;k&j;k--) a[k]=a[k-1];33 数据结构a[j]=x; } } main() { int a[]={46,26,22,68,48,42,36,84,66}; clrscr(); bi_insertion_sort(a,9); for(i=0;i&9;i++) printf(&%d &,a[i]); } 四：测试结果 输入：46，26，22，68，48，42，36，84，66 输出：22，26，36，42，46，48，66，68，84 输入：15，44，15，6 输出：6，15，15，443_2编写一个对给定链表进行插入排序的 C 程序。 一：数据结构 使用线性链表存储数据元素，这样插入元素会比较方便，可以不用像线性数组那样需要 移动元素。 二：具体分析 由于线性链表不利于查找，因此首先需要找到所需插入的元素指针 p 的位置 q，r 为 q 的 前一元素，当 r 为 NULL（未发生变化） ，则说明需插在首元素位置，此时需要相应改变指针 head，若不为 NULL，则要将 p 连在 r 后，q 连在 p 后，w 用来存储 p 的后一个数据，这样可 以继续往后排，直到 p 为 NULL。 三：源程序 #include&stdio.h& struct node{ struct node * }; typedef struct node NODE; NODE *link_insertion_sort(NODE *head) {34 数据结构NODE *p,*q,*r,*w; p=head-& head-&next=NULL; while(p) {t=p-& w=p-& q=r=NULL; p-&next=NULL; while(q-&data&=t&&q) {r=q;q=q-&} p-&next=q; if(!r) head=p; else r-&next=p; p=w; } return(head); } main() { int t, NODE *head,*p,*q=NULL; clrscr(); printf(&Do you want to end(y|n)?&); scanf(&%c&,&ch); getchar(); head=NULL; for(count=0;ch!='y'&&ch!='Y';count++) { printf(&Please input the data!&); scanf(&%d&,&t); getchar(); p=(NODE*)malloc(sizeof(NODE)); p-&data=t; p-&next=NULL; if(!q) head=p; else q-&next=p; q=p; printf(&Do you want to end(y|n)?&); scanf(&%c&,&ch); getchar(); } printf(&The original one is:\n&);35 数据结构p= while(p) {printf(&%d &,p-&data); p=p-& } printf(&\n&); head=link_insertion_sort(head); printf(&The sorted one is:\n&); p= while(p) {printf(&%d &,p-&data); p=p-& } printf(&\n&); } 四：测试 输入：46，26，22，68，48，42，36，84，66 输出：22，26，36，42，46，48，66，68，84 输入：空 输出：空 输入：3，5，5，4，8 输出：3，4，5，5，8 输入：5，4，3，2，1 输出：1，2，3，4，5 输入：3,3,3,3 输出：3,3,3,33_5采用顺序存储实现，即用数组存放排序过程中以排好序的链表的头指针。 #include&stdio.h& #define MAXN 100 struct node { struct node * }; typedef struct node NODE; NODE* listmerge(head1,head2) NODE *head1,*head2;36 数据结构{NODE *p,*q,*pp,* p=head1; q=head2; pq=pp=NULL; while(p!=NULL&&q!=NULL) {if(p-&data&=q-&data) {pp=p; p=p-& } else {pq=q; q=q-& pq-&link=p; if(p==head1) head1= else pp-&link= pp= } } if(q!=NULL) pp-&link=q; return head1; } NODE* listmpass(head) NODE * {NODE *t[MAXN],*p; int i,k; if(head==NULL) return NULL; p= for(i=0;p!=NULL;i++) {t[i]=p; p=p-& t[i]-&link=NULL; } while(i&1) {for(k=0;;k++) if(2*k&i&&2*k+1&i) t[k]=listmerge(t[2*k],t[2*k+1]); else if(2*k&i&&(2*k+1)==i) t[k]=t[2*k]; i=k; } return (t[0]);37 数据结构} 如果原来的链表为： head→24→46→36→42→68→84→22→48→66 则排序以后为 head→22→24→36→42→46→48→66→68→843_6采用顺序存储的结构即数组实现。 #include&stdio.h& #define MAX 100 void merge(a,b,l,m,n) int a[],b[]; int l,m,n; {int i,j,k; i=l; j=m+1; k=l; while(i&=m&&j&=n) if(a[i]&=a[j]) b[k++]=a[i++]; else b[k++]=a[j++]; while(i&=m) b[k++]=a[i++]; while(j&=n) b[k++]=a[j++]; } void merge_sort(a,n) int a[]; {int i,j,k, int b[MAX],tail[MAX]; head=0; k=0; for(i=0;i&n-1;i++) if(a[i]&a[i+1]) tail[k++]=i; tail[k]=n-1; for(j=0;j&=k-1;j++) {merge(a,b,head,tail[j],tail[j+1]); for(i=0;i&tail[j+1];i++) a[i]=b[i]; } }38 数据结构例：如数组存放了一组数为： 24，46，36，42，68，84，22，48，66， 经过排序以后为： 22，24，36，42，46，48，66，68，84，3_7编写一个实现快速排序的非递归的 C 函数。 一．存储结构： 每次调用子函数 quick 后，产生一个 low，up；用结构 S 存储 low 与 up，并 用一个栈存储排序过程中产生的结点 S。 二．算法分析： 快速排序用非递归的方法实现，可以用栈。每次出栈栈顶的 struct S 结点，并把 S-&low 和 S-&up 作为参数调用 quick 函数， quick 函数运行过程中若产生新的 S 结点， 在 则使之入栈。 这样循环直至栈空为止。 三．源程序 #include&stdio.h& #difein M 100 typedef struct stack {}S; S s[M]; int quick(int a[ ],int low,int up) {int i,j; if(low&up) { i= j= t=a[low]; while(i!=j) { while(i&j&&a[j]&t) j--; if(i&j) a[i++]=a[j]; while(i&j&&a[i]&=t) i++; if(i&j) a[j--]=a[i]; } a[i]=t; }39 数据结构return(i); } main() {int n,a[M]; int i,j,f; int l,u; printf(&input the length of the array:&); scanf(&%d&,&n); printf(&input the numbers:\n&); for(j=0;j&n;j++) scanf(&%d&,&a[j]); top=1; s[0].low=0; s[0].up=n-1; while(top&0) {top--; l=s[top]. u=s[top]. f=quick(a,l,u); if(l&f-1) s[top++].up=f-1; if(u&f+1) {s[top].low=f+1; s[top++].up=u; } } for(j=0;j&n;j++) printf(&%4d&,a[j]); } 四．测试用例 输入：数组元素个数：6 数组元素：8 9 5 2 1 6 输出：1 2 5 6 8 93_8对于给定的线性表 A＝〔12，2，16，30，8，28，4，10，20，6，18〕 ，试分别写出用下列排 序方法对 A 进行排序时，每一遍处理后的结果。 存储结构，算法分析，源程序：略 针对不同排序的方法使用不同的存储结构，因为算法分析与源程序书上已详细给出，因 此不重复叙述。40 数据结构输入要求排序的数：12，2，16，30，8，28，4，10，20，6，18 输出： 〔1〕插入排序： 2，12，16，30，8，28，4，10，20，6，18 2，12，16，30，8，28，4，10，20，6，18 2，12，16，30，8，28，4，10，20，6，18 2，8，12，16，30，28，4，10，20，6，18 2，8，12，16，28，30，4，10，20，6，18 2，4，8，12，16，28，30，10，20，6，18 2，4，8，10，12，16，28，30，20，6，18 2，4，8，10，12，16，20，28，30，6，18 2，4，6，8，10，12，16，20，28，30，18 2，4，6，8，10，12，16，18，20，28，30 〔2〕选择排序： 2，12，16，30，8，28，4，10，20，6，18 2，4，16，30，8，28，12，10，20，6，18 2，4，6，30，8，28，12，10，20，16，18 2，4，6，8，30，28，21，10，20，16，18 2，4，6，8，10，28，12，30，20，16，18 2，4，6，8，10，12，28，30，20，16，18 2，4，6，8，10，12，16，30，20，28，18 2，4，6，8，10，12，16，18，20，28，30 2，4，6，8，10，12，16，18，20，28，30 2，4，6，8，10，12，16，18，20，28，30 t=3，d[0]=4，d[1]=3，d[2]=1 8，2，4，10，12，6，16，30，20，28，18 8，2，4，10，12，6，16，18，20，28，30 2，4，6，8，10，12，16，18，20，28，30 2，12，16，8，28，4，10，20，6，18，30 2，12，8，16，4，10，20，6，18，28，30 2，8，12，4，10，16，6，18，20，28，30 2，8，4，10，12，6，16，18，20，28，30 2，4，8，10，6，12，16，18，20，28，30 2，4，8，6，10，12，16，18，20，28，30 2，4，6，8，10，12，16，18，20，28，30 2，12，16，30，8，28，4，10，6，20，18 2，12，16，30，4，8，10，28，6，18，20 2，4，8，10，12，16，28，30，6，18，20 2，4，6，8，10，12，16，18，20，28，30 6，2，10，4，8，12，28，30，20，16，18 4，2，6，10，8，12，28，30，20，16，18〔3〕希尔排序：〔4〕冒泡排序：〔5〕合并排序：〔6〕快速排序：41 数据结构2，4，6，10，8，12，28，30，20，16，18 2，4，6，8，10，12，28，30，20，16，18 2，4，6，8，10，12，18，16，20，28，30 2，4，6，8，10，12，16，18，20，28，30 〔7〕基数排序： 30，10，20，12，2，4，16，6，8，28，18 2，4，6，8，10，12，16，18，20，28，304_3将 n 阶三对角阵（即半带宽为 1 的带状矩阵）A 按行序列序存放在一维数组 b[3*n-2]中。若 aij(|i-j|&=1)存放在 b[k]中，请求出求解 k 的计算公式。 解： 在数组 b 中，此带状矩阵按如下方式存贮：除头一行和最后一行外，每一行都有三个元素， 将带状矩阵存储在 3n-2 个存储单元中。由分析知： &a[i][i]=&a[i-1][i-1]+3*s 可得 &a[i][i]=&a[0][0]+i*3*s &a[i][j]=&a[i][i]+(j-i)*s=&a[0][0]+[3i +(j-i)]*s (1) 若 aij 存放在 b[k]中， &b[k]=&b[0]+k*s (2) 又因为 &a[i][j]=&b[k] &a[0][0]==&b[0] 由(1)(2)式得 k=3i +(j-i)=2i+j 故 k=2i+j.4_4广义的带状矩阵 Anab 是在 n 阶方阵中只考虑最长主对角线下面的(a-1)条主对角线和最长主对 角线上面的（b-1）条主对角线及最长主对角线组成的带状区域。如果把广义的 Anab 按行序列序存放在一维数组 b[(a+b-1)*n-(a+b-2)]中，元素 aij 存放在 b[k]中，那么请写出计算 k 的计算公式。 解： 在数组 b 中，除头一行和最后一行外，每行都当作有(a+b-1)个元素，增补后即有下式成立 &a[i][i]=&a[i-1][i-1]+(a+b-1)*s 可得 &a[i][i]=&a[0][0]+i*( a+b-1)*s &a[i][j]=&a[i][i]+(j-i)*s=&a[0][0]+[i*( a+b-1)+(j-i)]*s (4) 若 aij 存放在 b[k]中， &b[k]=&b[0]+k*s (5) 又因为 &a[i][j]=&b[k] &a[0][0]==&b[0] 由(4)(5)式得 k=i*( a+b-1)+(j-i)4_5如果用三元组数组表示稀疏矩阵 A 和 B 试编写一个求解 A+B 的 C 函数(要求仍然用三元组数组 表示 A+B)42 数据结构[存储结构] 三元组数组 a[MAXN][3],b[MAXN][3],C[MAXN][3]分别用以存放稀疏矩阵 A,B,A+B [解题思路] (1) 判断 A 和 B 的行数,列数是否相等.若两者之中有一项不等,A+B 失败,返回 1;否则,转(2); (2) a[MAXN][3]和 b[MAXN][3]中的行号、列号都相等且相加不等于零的相应元素,将它们的 和存入 c[MAXN][3]; (3) a[MAXN][3]和 b[MAXN][3]中的行号相等,列号不等的元素,把两者之中列号较大的存入 c[MAXN][3]; (4) a[MAXN][3] 和 b[MAXN][3] 中 的 行 号 不 等 的 元 素 , 把 两 者 之 中 行 号 较 大 的 存 入 c[MAXN][3]; (5) 依照(2)(3)(4)的规则处理 a[MAXN][3]和 b[MAXN][3]中的元素,直到 a[MAXN][3]和 b[MAXN][3]的所有元素处理完.算法结束,返回 0. [c 程序] #define MAXN 20 int add_mat(int a[][3],int b[][3]) {int i=1,j=1,k=1; int c[MAXN][3]; if(a[0][0]!=b[0][0]||a[0][1]!=b[0][1]) return(1); c[0][0]=a[0][0]; c[0][1]=a[0][1]; c[0][2]=0; while(i&=a[0][2]&&j&=b[0][2]) if(a[i][0]==b[j][0]) if(a[i][1]==b[j][1]) if(a[i][2]+b[j][2]!=0) {c[k][0]=a[i][0]; c[k][1]=a[i][1]; c[k++][2]=a[i++][2]+b[j++][2]; c[0][2]+=1;} else {i++; j++;} else if(a[i][1]&b[j][1]) {c[k][0]=a[i][0]; c[k][1]=a[i][1]; c[k++][2]=a[i++][2]; c[0][2]+=1; } else {c[k][0]=b[j][0]; c[k][1]=b[j][1]; c[k++][2]=b[j++][2]; c[0][2]+=1; } else if(a[i][0]&b[j][0]) {c[k][0]=a[i][0]; c[k][1]=a[i][1]; c[k++][2]=a[i++][2]; c[0][2]+=1;} else {c[k][0]=b[j][0];43 数据结构c[k][1]=b[j][1]; c[k++][2]=b[j++][2]; c[0][2]+=1; while(i&=a[0][2]) {c[k][0]=a[i][0];c[k][1]=a[i][1];c[k++][2]=a[i++][2];c[0][2]+=1;} while(j&=b[0][2]) {c[k][0]=b[j][0];c[k][1]=b[j][1];c[k++][2]=b[j++][2];c[0][2]+=1;} for(i=0;i&=c[0][2];i++) printf(&%d %d %d\t&,c[i][0],c[i][1],c[i][2]); return(0); } [测试用例] A:a[MAXN][3]={{5,4,7},{0,0,12},{0,1,15},{2,0,36},{2,1,46},{2,3,52},{3,1,72}, {3,3,68}}; B:b[MAXN][3]={{5,4,6},{0,0,10},{1,1,20},{2,0,-36},{2,3,13},{3,3,4 },{4,1,15}}; A+B:c[MAXN][3]={{5,4,8},{0,0,22},{0,1,15},{1,1,20},{2,1,46},{2,3, 65},{3,1,72},{3,3,72},{4,1,15}}4_6假设 A 是用十字链表表示的稀疏矩阵,试编写一个将 A 转置的 C 函数.(要求仍然用十字链表表 示 A 的转置矩阵) [存储结构] 十字链表 NODE 表示 A: struct node{int row,col, struct node *right,*}; typedef struct node NODE; [解题思路] (1) 将原十字链表 A 中头指针 h 所指的结点的 row,col,val 存放在 A 的转置矩阵的头指针 h1 所指结点的 col,row,val 字段,并根据其各行(列)链表的表头结点; (2) 找到 A 各列结点,指针 p 指向其表头结点,以指针 q 指向该列各个结点,据指针 q 的 row,col 字段,把该结点插在 A 的转置矩阵的行号为 col,列号为 row 的相应位置.直到 A 中结 点全部插在其转置矩阵中. [c 程序] #include&stdio.h& typedef struct node{int row,col, struct node *right,*}NODE; NODE *search_row_last(NODE *a,int i) {NODE *p,*h; p=a; for(k=0;k&=i;k++) p=p-&44 数据结构h=p; while(p-&right!=h) p=p-& return(p);} NODE *search_col_last(NODE *a,int j) {NODE *p,*h; p=a; for(k=0;k&=j;k++) p=p-& h=p; while(p-&down!=h) p=p-& return(p);} NODE *convert(NODE *h) {NODE *h1,*p1,*q1,*p,*q,*r; h1=(NODE*)malloc(sizeof(NODE)); h1-&row=h-& h1-&col=h-& h1-&val=h-& h1-&right=h1; h1-&down=h1; p1=h1; for(k=0;k&h1-&k++) {q1=(NODE*)malloc(sizeof(NODE)); q1-&col=1000;q1-&right=q1;q1-&down=p1-& p1-&down=q1; p1=q1;} p1=h1; for(k=0;k&h1-&k++) {q1=(NODE*)malloc(sizeof(NODE)); q1-&row=1000;q1-&down=q1;q1-&right=p1-& p1-&right=q1; p1=q1;} for(p=h-&p!=h;p=p-&right) {for(q=p-&q!=p;q=q-&down) {r=(NODE*)malloc(sizeof(NODE)); r-&row=q-&r-&col=q-&r-&val=q-& p1=search_row_last(h1,r-&row); q1=search_col_last(h1,r-&col); r-&right=p1-& p1-&right=r; r-&down=q1-& q1-&down=r;} } return(h1);}5_1图题 5-1 是一棵结点值为字符的三次树。如果按前序、后序和层次序分别对该树进行遍历，那45 数据结构么请分别给出遍历后的结点序列。 ABCDEFGJMHIK 图题 5-1LNOPQ[解] 前序遍历：ABEFHIGCJKLDMNOQP 后序遍历：EHIFGBKLJCNQOPMDA 层次遍历：ABCDEFGJMHIKLNOPQ5_2试叙述将 m 棵有序树组成的有序树林转换成相应的二叉树的逆变换。已知图题 5-2 的二叉树 是由某 m 棵有序树林转换而来的。请使用你所给出的逆变换画出该二叉树所对应的树林。 [解] 临时结点 B0 临时结点 A0 * * ---------------------------------------------------------------------------------------------------------------------A B C B D E 图题 5-2 F G D 转换后的树林 E F A C G假设β （T）是已知的二叉树。我们为它设置一个临时的父结点 B0，使 T2 作为 B0 的左 子树，而右子树置空。同时，我们为要转换成的树林 T=（T0，T1，??Tm）也设置一个临时 的父结点 A0，使 T0，T1，??Tm 分别作为它的 m 个儿子。 变换的方法如下： 令 A=A0，B=B0.L=B-&lchild,R0=L-&rchild。 如果 Ri!=NULL,Ri+1=Ri-&rchild(I=0,1,…m-3);否则，Ri+1=NULL. 按下面方法构造结点 A： 如 果 L==NULL ， A-&child[0]=NULL; 否 则 ， A-&child[0]-&data=L-&data ， 并 令 A0=child[0],B0=L,重复上述变换过程。46 数据结构┊ 如 果 Ri==NULL ， A-&child[I+1]=NULL; 否 则 ， A-&child[I+1]-&data=Ri-&data ， 并 令 A0=A-&child[I+1],B0=Ri,重复上述变换过程。 ┊ 如果 Rm-2==NULL，A-&child[m-1]=NULL;否则，A-&child[m-1]-&data=Rm-2-&data，并令 A0=A-&child[m-1],B0=Rm-2,重复上述变换过程。 显然，这是一个递归的过程。经过变换，我们得到的 m 次树的根结点 A0 的 m 个儿子即 是所要求的树林。 运用上述变换方法，可将图题 5-2 的二叉树转换成右图的树林。5_3假设二叉树 T 是按标准形式存储的， 试编写一个把该树中每个结点的左右子结点进行对换的 C 函数。 存储结构： #include&stdio.h& typedef struct node{ struct node *lchild, }NODE; 算法： 将根结点的左右子结点对换，然后对根结点的左右子树进行递归调用。为了检验是否正确对 对换前后的树进行后序遍历。 程序：#include&stdio.h& typedef struct node{ struct node *lchild,* }NODE; NODE *settree(a,b,m,n) char a[],b[]; int m,n; {NODE *t; int i,j; if(m&n)return(NULL); t=(NODE *)malloc(sizeof(NODE)); t-&data=b[n]; for(i=m;a[i]!=b[n];i++); for(j=n-1;j&=i;j--)b[j+1]=b[j]; t-&lchild=settree(a,b,m,i-1); t-&rchild=settree(a,b,i+1,n); return(t); } void tradetree(t) NODE *t;47 数据结构{NODE *p; if(t==NULL) p=t-& t-&lchild=t-& t-&rchild=p; tradetree(t-&lchild); tradetree(t-&rchild); } void s_posorder(t) NODE *t; {NODE *s[100];int s1[100]; int top,i; if(t==NULL) s[0]=t;s1[0]=0;top=1; while(top&0) {t=s[--top]; i=s1[top]; if(i==2)printf(&%c&,t-&data); else if(i==0) {while(t-&lchild!=NULL){t=t-& s1[top]=1; s[++top]=t; s1[top]=0; } if(t-&rchild==NULL)printf(&%c&,t-&data); else ++ } else{s1[top]=2;++ t=t-& if(t!=NULL) {if(t-&lchild==NULL&&t-&rchild==NULL)printf(&%c&,t-&data); else{s[top]=t;s1[top++]=0;} } } } } main() {char a[100],b[100]; NODE *t; printf(&input midorder:\n&); scanf(&%s&,a); printf(&input posorder:\n&); scanf(&%s&,b);48 数据结构for(i=0;a[i]!='\0';i++); t=settree(a,b,0,i-1); s_posorder(t); tradetree(t); printf(&\n&); s_posorder(t); } 测试用例：输入 BAC BCA 输出：BCA CBA5_4编写一个利用栈来实现后序遍历一棵给定的二叉树的 C 函数。 存储结构：#include&stdio.h& typedef struct node{ struct node *lchild, }NODE; 算法：叶结点直接输出不压栈，非叶结点需要压栈，输出后向上回溯，应判别是从左边回上 去还是从右边回上去。 程序： #include&stdio.h& typedef struct node{ struct node *lchild,* }NODE; NODE *settree(a,b,m,n) char a[],b[]; int m,n; {NODE *t; int i,j; if(m&n)return(NULL); t=(NODE *)malloc(sizeof(NODE)); t-&data=b[n]; for(i=m;a[i]!=b[n];i++); for(j=n-1;j&=i;j--)b[j+1]=b[j]; t-&lchild=settree(a,b,m,i-1); t-&rchild=settree(a,b,i+1,n); return(t); } void tradetree(t) NODE *t; {NODE *p; if(t==NULL)49 数据结构p=t-& t-&lchild=t-& t-&rchild=p; tradetree(t-&lchild); tradetree(t-&rchild); } void s_posorder(t) NODE *t; {NODE *s[100];int s1[100]; int top,i; if(t==NULL) s[0]=t;s1[0]=0;top=1; while(top&0) {t=s[--top]; i=s1[top]; if(i==2)printf(&%c&,t-&data); else if(i==0) {while(t-&lchild!=NULL){t=t-& s1[top]=1; s[++top]=t; s1[top]=0; } if(t-&rchild==NULL)printf(&%c&,t-&data); else ++ } else{s1[top]=2;++ t=t-& if(t!=NULL) {if(t-&lchild==NULL&&t-&rchild==NULL)printf(&%c&,t-&data); else{s[top]=t;s1[top++]=0;} } } } } main() {char a[100],b[100]; NODE *t; printf(&input midorder:\n&); scanf(&%s&,a); printf(&input posorder:\n&); scanf(&%s&,b); for(i=0;a[i]!='\0';i++); t=settree(a,b,0,i-1);50 数据结构s_posorder(t); tradetree(t); printf(&\n&); s_posorder(t); } 测试用例： 输入：BAC BCA 输出：BCA5_5一． 题目： 如果 T 是一颗有序树，T?是与 T 相对应的二叉树。假定 T?已按标准形式被存贮，试为下 面各小题分别编写一个 C 函数： （1） 按前序输出 T 的结点值。 （2） 按后序输出 T 的结点值。 （3） 输出树 T 的叶子结点值。 （4） 求出树 T 的次数。二． 算法分析：本题主要应弄清楚 T 与 T?之间的关系。设 t 表示二叉树 T?的根结点，则 t-&lchild（如果 非空）为原先 T 的第一个子结点，而 t-&rchild，t-&rchild-&rchild, …（如果非空）则表示 T 的 第二、三??个子结点。 1． 按前序输出 T 的结点值： (1) 如果 t 为空，则直接返回； (2) 访问结点 t； (3) 如果 t 存在子结点，则访问 t 的第一个子结点（即 t-&lchild） ，再访问其它子结点 （即 t-&rchild，t-&rchild-&rchild, …） 。 2． 按后序输出 T 的结点值（方法类似 1） 3． 访问树 T 的叶子结点： 只需在遍历时增加是否为叶子结点的判断即可。 4． 求树 T 的次数： （1） 如果 t 为空，返回次数 0。 （2） 统计 t 的子结点数，记为 degree；同时求出各子树的次数的最大值，记为 subDegree； （3） 取 degree 与 subDegree 中较大的一个并返回。 三． 程序如下： struct NODE { NODE *lchild,* };51 数据结构void PreScan(NODE *t) /* 按前序输出 T 的结点值*/ { if(t==NULL) printf(“%d\t”,t-&data); if((t=t-&lchild)!=NULL){ PreScan(t); while((t=t-&rchild)!=NULL) PreScan(t); } } void PostScan(NODE *t) /*按后序输出 T 的结点值*/ { NODE *p; if(t==NULL) if((p=t-&lchild)!=NULL){ PostScan(p); while((p=p-&rchild)!=NULL) PostScan(p); } printf(“%d\t”,t-&data); } void LeafScan(NODE *t) /*输出树 T 的叶子结点值*/ { if(t==NULL) if(t-&lchild==NULL)/*is leaf*/ printf(“%d\t”,t-&data); else{ LeafScan(t=t-&lchild); while((t=t-&rchild)!=NULL) LeafScan(t); } } int GetDegree(NODE *t) /*得到树 T 的次数*/ { int degree=0,subDegree,d; NODE *p; if(t==NULL) return 0; if((t=t-&lchild)!=NULL){52 数据结构degree++; subDegree=GetDegree(t); for(p=t;(p=p-&rchild)!=NULL;){ degree++; d=GetDegree(p); if(subDegree&d) subDegree=d; } if(degree&subDegree) degree=subD } }5_6一.题目： 假设二叉树 T 的结点值是字符，已知树 T 中结点的前序和中序，试编写一个把树 T 按标 准形式进行存贮的 C 函数。 二.算法分析： 设前序遍历和中序遍历的结果在数组 pre[] 和 mid[]中，显然，pre[]中第一个元素（设为 data）即为根结点，而在 mid[]中，data 左右的元素分别是左子树和右子树中的元素。 （1） 当数组中元素个数 n 为非正数时，返回空。 （2） 以 pre[0]为数据生成根结点 roof，并找出它在 mid 数组中的位置 posi。 （3） pre[1]或 mid[0] 开始的 posi 个数据在左子树中， pre[1+posi]或 mid[posi+1] 开始的 posi 个数据在左子树中，分别转（1）构造左右子树（递归）,并返回根结点 roof。 三.程序如下： { NODE *lchild,* }; NODE *Create(char pre[],char mid[],int n) { NODE * if(n&=0) return NULL; roof=(NODE*)malloc(sizeof(NODE)); data=pre[0]; roof-&data= for(posi=0;posi&n&&mid[posi]!=posi++); roof-&lchild=Create(pre+1,mid,posi); roof-&rchild=Create(pre+1+posi,mid+posi+1,n-1-posi); }53 数据结构5_7递归算法： 数据结构 typedef struct node { struct node * struct node * }NODE; int pre[MAX],ind[MAX],aft[MAX]; int count_p=0,count_m=0,count_a=0; 算法分析： 通过递归把两数组分为头接点，左子树，右子数三部分； 后序序列和中序序列分别放在数组 aft[1,n]和 ind[1,n]中； NODE *bintree2(i,j,u,v) //I 后序的起始点,j 后序的终点,u 中序的起始点,v 中序的终点； int i,j,u,v; { int k,l; NODE *head,*s; head=NULL; if (j&=i) { head=(NODE *)malloc(sizeof(NODE )); head-&data=aft[j]; //生成头接点 k=u; while(ind[k]!=aft[j])k++;//找到当前头接点在中序中的位置 l=j+k-v; //右子树中最左边的接点在中序中的位置 if(k==u) //头接点等于中序的起始位置 head-&lchild=NULL; else { s=bintree2(i,l-1,u,k-1);//处理左子树部分 head-&lchild=s; } if (k==v)head-&rchild=NULL;//同理 else { s=bintree2(l,j-1,k+1,v);//同理 head-&rchild=s; } } return(head); }54 数据结构5_8int is_cdtree(t) NODE *t; { int flag=0; if (t==NULL) return(1); if (!((t-&lchild==NULL&&t-&rchild!=NULL)||(t-&lchild!=NULL&&t-&rchild==NULL))) // flag=1; return(flag&&is_cdtree(t-&lchild)&&is_cdtree(t-&rchild)); }5_91. 存贮方式: Typedef struct node { struct node * struct node * }NODE; 2. 存储结构: 本题采用递归,并用 1 代表真 0 代表假 3. 源程序 int islikebi(NODE *head1,NODE *head2) { NODE *p=head1; NODE *q=head2; int l=0,r=0; if(p==NULL&&q==NULL) return 1; if(p!=NULL&&q!=NULL) { l=islikebi(p-&lchild,q-&lchild); r=islikebi(p-&rchild,q-&rchild); return l*r; } return 0; } 4. 测试用例:经过测试(输入两棵树) 结果正确.5_101. 存贮结构:采用附带一个标志位和一个右指针来线形存储一棵树.55 数据结构2. 存储方式:用左标志直接找左孩子,用右指针找右孩子,程序用递归. Typedef struct node { struct node * struct node * }NODE; 3. 源程序 用 t 数组存放线形的树表示. NODE *creat(int i) { NODE *head=(NODE *)malloc(sizeof(NODE)); if(t[i].data==0) return NULL; else { head-&data=t[i]. if(t[i].ltag==0) head-&lchild=creat(i+1); else head-&lchild=NULL; if(t[i].rchild!=-1) head-&rchild=creat(t[i].rchild); else head-&rchild=NULL; } } 4. 测试用例:输入一组线形树,能够形成一棵标准存储的二叉树5_11假设二叉树 T 已按前序附加两个标志位的顺序存贮方法存放，且 a 是 T 中一个结点的值，试 编写一个寻找结点 a 的父结点的 C 函数。 分析：可按如下规律寻找结点 a 的父结点，假设二叉树由数组 p 给出，且 p[i]=结点 a （1） 若 p[i-1]的 ltag 为 0，则 p[i]是 p[i-1]的左孩子，p[i-1]即为 a 的父亲 （2） 若 p[i-1]的 ltag 为 1，而 rtag 为 0，则 p[i]是 p[i-1]的右孩子，p[i-1]即 为 a 的父亲 （3） 若 p[i-1]的 ltag 和 rtag 均为 1，则查找 p[i]之前的所有结点，并把 ltag 和 rtag 均为 0 的结点入栈， 同时计算满足 “前一个结点 ltag 和 rtag 均为 1” 这样条件的结点， 其个数记为 count， 出栈 count 次后的栈顶结点即为 a 的父 亲 程序 #include&stdio.h& typedef struct node{56 数据结构int ltag, }LRNODE; char find(LRNODE p[],int n,char a) {int i,j,top=0,count=0; char c[100]; for(i=0;i&n;i++) if(p[i].data==a) if(i==0||i==n){printf(¬ found!error!\n&); return('@');} if((p[i-1].ltag==0)||(p[i-1].ltag==1&&p[i-1].rtag==0)) return(p[i-1].data); for(j=0;j&i;j++) {if(p[j].ltag==0&&p[j].rtag==0) c[top++]=p[j]. if(p[j].ltag==1&&p[j].rtag==1&&j&i-1) count++; } i=top-count-1; return(c[i]); } void main() {LRNODE p[9]; for(i=0;i&9;i++) scanf(&%d%c%d&,&p[i].ltag,&p[i].data,&p[i].rtag); ch=find(p,9,'C'); printf(&%c\n&,ch); } 测试样例： 输入：(即为书 p.136 图 5.9.1 所示二叉树) 0A0 0B0 1D1 0E0 1G1 1H1 1C0 0F1 1I1 输出： A57 数据结构5_12假设二叉树 T 是一棵穿线树，试编写一个按前序遍历树 T 的 C 函数。 （不允许用递归程序，也 不允许使用数组，只允许增加个别变量） 分析：基本思想是在遍历时若结点有左孩子则尽量往左走，走到最左时利用穿线往右走一步， 若为右孩子则继续上述过程，若为其中序遍历的后一个结点则再往右一步后继续上述过程。 程序（程序中用穿线排序的方法产生一棵穿线树，preorder 为前序遍历的 C 函数） #include&stdio.h& typedef struct node{ struct node *lchild,* int ltag, }NODE; NODE* thread_sort_tree(a,n) char a[]; {NODE *root,*p,*r; if(n==0) return(NULL); root=(NODE*)malloc(sizeof(NODE)); root-&data=a[0]; root-&lchild=NULL; root-&rchild=NULL; root-<ag=0; root-<ag=0; for(i=1;i&n;i++) {r=(NODE*)malloc(sizeof(NODE)); r-&data=a[i]; p= while(1) {if(r-&data&=p-&data) if(p-<ag==0&&p-&lchild!=NULL) p=p-& else if(p-&rtag==0&&p-&rchild!=NULL) p=p-& } if(r-&data&p-&data) {r-&lchild=p-& r-<ag=p-& r-&rchild=p; r-&rtag=1;58 数据结构p-&lchild=r; p-<ag=0; } else if(r-&data&p-&data) {r-&rchild=p-& r-&rtag=p-& r-&lchild=p; r-<ag=1; p-&rchild=r; p-&rtag=0; } } return(root); } void preorder(root) NODE * {NODE *p,*q; p= while(p!=NULL) {if(p-<ag==0&&p-&lchild!=NULL) {q=p-& printf(&%c &,p-&data); p=q; } else {q=p-& printf(&%c &,p-&data); if(p-&rtag==0) p=q; else p=q-& } } } void main() {char a[8]={'E','B','H','C','F','A','D','G'}; NODE * root=thread_sort_tree(a,8); preorder(root); printf(&\n&); } 测试样例： 穿线树已在函数中初始化，不需输入（即为书 p.139 图 5.9.3 所示的穿线树） 输出为：59 数据结构EBACDHFG6_1假设结点序列 F=(60,30,90,50,120,70,40,80)，试用查找树的插入算法，用 F 中的结点依次 进行插入，画出由 F 中结点所构成的查找树 t1，再用查找树的删除算法，从查找树 t1 中依次 删除 40，70，60，画出删除后的查找树。 解答： 至于查找树的插入和删除算法在书中的第 6.1 节已明确给出，这里就不再赘述。 查找树的结点插入时，先查找该结点若以存在，则插入失败并返回；否则进行插入。插入时 先和根结点比较若比它大则往右边走，继续比较；否则往左边走，继续比较。直到遇到空指 针则该结点插入的位置即为该指针的位置。由上所述，每次结点都是插入后都成为树的叶结 点。给出树 t1 如下： 60 L K 30 90 K L K 50 70 120 L K 40 80 查找树删除算法的原理书上 P149 页有详细的分析。删除 40，70，60 后的树如下所示： 30 K 50 K 90 L K 80 126_2已知 F=(a0,a1,?,an-1)是一个已排序的整数结点序列，试编写一个用平分法构造出由 F 中结点所构成的丰满查找树的 C 函数。 解答： 很容易联想到用递归来解决这个问题。用函数 NODE *creat_tree(int a[],int m,int n) 来实现。每次调用时序列中间的一个数即为树根返回，m 指 a 数组开始的下标号，n 指 a 数组 结束的下标号，中间指用(m+n)/2 得到。具体实现的 C 函数如下：(这里假定用户输入的 F 数 组已由小到大按升序排好列了) #include&stdio.h& struct node { struct node * struct node * }; typedef struct node NODE;60 数据结构NODE * creat_tree(int a[],int m,int n) { NODE *t; if(n-m&0)return(NULL); k=(m+n)/2; t=(NODE *)malloc(sizeof(NODE)); t-&data=a[k]; t-&llink=creat_tree(a,m,k-1); t-&rlink=creat_tree(a,k+1,n); return(t); } void suc_order(NODE *t) { if(t!=NULL){ suc_order(t-&llink); suc_order(t-&rlink); printf(&%d &,t-&data);} } void mid_order(NODE *t) { if(t!=NULL){ mid_order(t-&llink); printf(&%d &,t-&data); mid_order(t-&rlink); } } main() { int n,i; int a[100]; NODE * printf(&\nInput the size of the array:\n&); scanf(&%d&,&n); getchar(); for(i=0;i&n;i++){ printf(&Input data %d:\n&,i+1); scanf(&%d&,&a[i]); } head=creat_tree(a,0,n-1); suc_order(head); printf(&\n&); mid_order(head); } 程序中用到了书中介绍的二叉树的后序和中序遍历是为了检查 creat_tree 函数的正确性而设 的，因为二叉树的后序和中序遍历能唯一确定一棵树，故我们在输入数组，建立了想要得到 的二叉树后可人工的写出它的后序和中序遍历并和程序输出的进行比较，若相同则说明 creat_tree 函数创建的正是题目所要求的查找树。 例如：61 数据结构输入已排好序的数组 30，40，50，60，70，80，90，120 人为的我们知道这样的一个数组用平分法能构成如下查找树： 60 L K 40 80 L K L K 30 50 70 90 K 120 程序输出该查找树的后序遍历为：30 50 40 70 120 90 80 60 中序遍历为：30 40 50 60 70 80 90 120 可知道程序创建的查找树即为上图所示的查找树，故程序正确。6_5编写一个判断给定二叉树 T 是否为平衡树的 C 函数。 解答： 一：存储结构 二叉树以一个 struct node 的形式存储，data 域存储结点的数据（char 类型） ，left、 right 域为二叉树中指向左右孩子的指针。二：具体实现 函数 creat 用来创建一个二叉树，首先输入数据元素，在输入节点类型，l 代表只有左孩子， r 代表只有右孩子，b 代表有两个孩子，e 代表没有孩子（叶子结点） ，函数 r_preorder 用来 进行前序遍历，便于测试，函数 is_batree 用来测试是否为平衡树，是即返回非 0，否则返回 0，该函数以递归实现。首先判断是否为空（递归跳出条件） ，然后看本结点的左、右子树是 否为平衡树，若是，则再看本结点是否符合平衡树的条件，若是，则返回本结点的深度。否 则，一律返回 0。三：源程序#include&stdio.h& struct node { struct node *left,* }; typedef struct node NODE; void creat(NODE *root) { printf(&\nPlease input the data!:\n&);62 数据结构getchar(); scanf(&%c&,&(root-&data)); getchar(); printf(&\nPlease input the type of the node:(l\\r\\b\\e)&); scanf(&%c&,&type); switch(type) {case 'l':root-&left=(NODE*)malloc(sizeof(NODE)); printf(&\nPlease input the left child:\n&); creat(root-&left);root-&right=NULL; case 'r':root-&right=(NODE*)malloc(sizeof(NODE)); printf(&\nPlease input the right child:\n&); creat(root-&right);root-&left=NULL; case 'e':root-&left=NULL;root-&right=NULL; case 'b':root-&left=(NODE*)malloc(sizeof(NODE)); printf(&\nPlease input the left child:\n&); creat(root-&left); root-&right=(NODE*)malloc(sizeof(NODE)); printf(&\nPlease input the right child:\n&); creat(root-&right); } } void r_preorder(NODE *t) {if(t!=NULL) {printf(& %c &,t-&data); r_preorder(t-&left); r_preorder(t-&right); } } int is_batree(NODE *root) {int da,db, if(!root) return(1); if(!((da=is_batree(root-&left))&&(db=is_batree(root-&right)))) return(0); dc=da&db? da-db:db- if(dc&1) return(0); return(da&db?da+1:db+1); }63 数据结构main() { NODE* printf(&\nAn empty tree?(y|n)\n&); scanf(&%c&,&ch); if(ch=='n') {printf(&\nPlease input the root node!\n&); root=(NODE*)malloc(sizeof(NODE)); creat(root); r_preorder(root); printf(&\nIt is &); if(!(is_batree(root))) printf(¬ &); printf(&a balance tree!&); } }四：测试结果 输入：结点类型 结点值 b a l b e c r d e e 输出：It is a balance tree!输入：结点类型 结点值 b a b b r c e d e e r f e g 输出：It is a balance tree!输入：结点类型 结点值 b b ra b c64 数据结构e e r l ed e f gh 输出：It is a not balance tree!输入：结点类型 结点值 b b r e b e e 输出：It is a not balancea b c d e f g tree!6_6试画出 Adelson 插入方法的右改组的转换图。 解答：右改组的画法与左改组的画法类似，如下图：65 数据结构ki ki A1t ki+2 A2t A3t+1 A3t-1 (a)新 结 点插 A3t+1中 在 A4t ki+1 A2tA1tki+1（b） 新 结 点插 A4t中 在kikiA1t ki+2 A3tki+1 A2t ki+2 A4t-1ki+1（c） 新 结 点插 A3t中 在（d） 新 结 点ki+2插 ki+1的 左边 在6_9给定结点 k0,k1,k2,k3,k4 的键值分别为 10，30，50，70，90，相对使用概率为 5，6，3， 4，7。 （1） 构造阶段中结点序列的变化情况： k0 k1 k2 k3 k4 ?6 ? 5 ?? ??? 3 ?7 ?? ?4 ?? k0 b1 k3 k4 ?5 ?? ?9 ?? ?7 ?? ?4 ?? k0 b1 b2 ?11 ? 9 ? 5 ?? b3 b2 ?11 ? 41 ?? b4 ?52 ?? （2） 构造阶段产生的树 b4?52 ??66 数据结构b3?41 ?? b2?11 ?? k0?5 ?? b1?9 ?? k3? 7 ??k4?4 ?? k1? 6 ??k2?3 ?? （3） 建造阶段结点序列的变化情况 k0 k1 k2 k3 k4 2??? 3??? 3??? 2??? 2??? k0 c1 k3 k4 2??? 2??? 2??? 2??? c2 k3 k4 1??? 2??? 2??? c2 c3 1??? 1??? c4 0??? （4） 建造阶段产生的树 0? ??c4 1? ??c2 1? ??c3 2? ??k0 2? ??c1 2? ??k3 2? ??k4 3? ??k1 3? ??k2 即为所求树。6_10（1）插入 200 100 200 100 200 250 100 150 200 250 150 100 120 200 250 150 100 110 120 200 250 150 200 220 250 100 110 120 15067 数据结构100 110 120 200 205 220 250150 210220 250 200 205 100 110 120150 210 200 205 90 100 110 120 220 250150 220 160 90210 250 200 205 100 110 120100 150 21080 110 160 22090 120 200 205 250100 150 210 80 90 160 170 200 205 220 25068 数据结构110 120100 150 200 210 160 110 80 202 220 170 120 90 205 250100 150 200 21080 110 160 202 22090 120 170 205 225 250100 150 200 21080 110 160 202 220 20090 120 170 205 225 240 250100 150 210 24080 160 202 245 11090 170 205 250 12069 数据结构220 225（2）删除 202 100 150 200 240 245 250 80 90 205 210 220 225 110 120 160 170100 160 205 240 （3）删除 150 170 200 245 250 80 90 210 220 225 110 120 （4）删除 200 100 160 210 240 245 250 80 110 170 220 90 120 205 2256_12算法分析： 在原来的寻找一个方法是用到的是一个 maxn*maxn 的栈，这样的话浪费了很大的空间不利 于处理棋局比较大的情况。这里用的是 maxn 的一个栈，这样的话机不能把每一行都压栈，这 里只能选者有用的节点压栈。其他的处理也是用得回朔的方法。 不同：1 节点进入时标准有所不同； 2 找到一种方法以后还要继续回朔，直到 所有的路径都被找完。 部分源程序： Int queens(n)70 数据结构 { NODE stack[MAXN]; int row[MAXN],col[MAXN],md[2*MAXN-1],sd[2*MAXN-1]; int str,stc,i; int is_First=1; int answer=0; top=0; str=-1; stc=-1; begain: for(i=0;i&n;i++) { row[i]=0; col[i]=0; } for(i=0;i&2*n-1;i++) { md[i]=0; sd[i]=0; } stack[0].tag=0; while (top&=0) { if (str&=n-1) if (stc&n-1) { stc++; if (is_First) { str++; is_First=0; } } else { stc=0; str++; } stack[top].r= stack[top].c= if (stack[top].tag==0&&(str==0||row[str-1])) 节点进入时标准有所不同；71 数据结构if (row[str]||col[stc]||md[str-stc+n-1]||sd[str+stc]) { stack[top].tag=0; } else { row[str]=1; col[stc]=1; md[str-stc+n-1]=1; sd[str+stc]=1; stack[top].tag=1; if (str==n-1) { answer++; printf (&%d solution is\n&,answer); for(i=0;i&=i++) if (stack[i].tag) printf (&%4d%3d;&,stack[i].r,stack[i].c); printf (&\n&); top++; /*critical*/ 找到一种方法以后还要继续回朔，直到 所有的路径都被找完。 } else stack[++top].tag=0; } else { loop: str=stack[--top].r; stc=stack[top].c; row[str]=0; col[stc]=0; md[str-stc+n-1]=0; sd[str+stc]=0; if (stc==n-1) stack[top].tag=0; } } return(answer); } 数据测试： 输入：472 数据结构输出 1 solution is 1: 0 1; 2: 2 solution is 1: 0 2; 2: 输入：5 输出： 1 solution is 1: 0 0; 2: 2 solution is 1: 0 0; 2: 3 solution is 1: 0 1; 2: 4 solution is 1: 0 1; 2: 5 solution is 1: 0 2; 2: 6 solution is 1: 0 2; 2: 7 solution is 1: 0 3; 2: 8 solution is 1: 0 3; 2: 9 solution is 1: 0 4; 2: 10 solution is 1: 0 4; 2: 输入：7 输出 1 solution is 1: 0 0; 6: 5 3; 2 solution is 1: 0 0; 6: 5 1; 3 solution is 1: 0 0; 6: 5 6; 4 solution is 1: 0 0; 6: 5 4; 5 solution is 1: 0 1;1 13; 0;3: 2 3: 20; 4: 3 3; 4: 32; 1;1 1 1 1 1 1 1 1 1 12; 3; 3; 4; 0; 4; 0; 1; 1; 2;3: 2 3: 2 3: 2 3: 2 3: 2 3: 2 3: 2 3: 2 3: 2 3: 24; 4: 3 1; 4: 3 0; 4: 3 2; 4: 3 3; 4: 3 1; 4: 3 2; 4: 3 4; 4: 3 3; 4: 3 0; 4: 31; 5: 4 4; 5: 4 2; 5: 4 0; 5: 4 1; 5: 4 3; 5: 4 4; 5: 4 2; 5: 4 0; 5: 4 3; 5: 43; 2; 4; 3; 4; 0; 1; 0; 2; 1;2: 1 7: 6 2: 1 7: 6 2: 1 7: 6 2: 1 7: 6 2: 12; 5; 3; 4; 4; 3; 5; 2; 3;3: 24; 4: 36; 5: 41;3: 26; 4: 32; 5: 45;3: 21; 4: 35; 5: 42;3: 23; 4: 31; 5: 46;3: 20; 4: 36; 5: 44;73 数据结构6: 5 2; 7: 6 solution is 1: 0 1; 2: 6: 5 4; 7: 7 solution is 1: 0 1; 2: 6: 5 2; 7: 8 solution is 1: 0 1; 2: 6: 5 3; 7: 9 solution is 1: 0 1; 2: 6: 5 2; 7: 10 solution is 1: 0 1; 2: 6: 5 0; 7: 11 solution is 1: 0 1; 2: 6: 5 5; 7: 12 solution is 1: 0 2; 2: 6: 5 6; 7: 13 solution is 1: 0 2; 2: 6: 5 6; 7: 14 solution is 1: 0 2; 2: 6: 5 5; 7: 15 solution is 1: 0 2; 2: 6: 5 3; 7: 16 solution is 1: 0 2; 2: 6: 5 0; 7: 17 solution is 1: 0 2; 2: 6: 5 1; 7: 18 solution is 1: 0 3; 2: 6: 5 6; 7: 19 solution is 1: 0 3; 2: 6: 5 2; 7: 20 solution is6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 65; 3; 6; 3: 2 5; 4: 3 0; 5: 4 2;4; 3: 2 5; 4; 5; 4; 5; 5; 4; 6; 3; 0; 3; 0; 4; 4; 0; 5; 6; 6; 4; 6; 5; 0; 4; 3: 20; 4: 33; 5: 46;2; 4: 30; 5: 46;3:}
数据结构课习题参考答案
数据结构目录 一、 1.1 比较 2 个线性链表的 C 函数 ???????????????????????3 1.2 写一个倒置顺序存贮的线性表的 C 函数???????????????????31.3 写一个在线性表中，使线性表中没有值相同的结点的函数。??????????4 1.4 编写一个求解给定多项式的值的 C 函数。??????????????????5 1.5 实现多项式乘法?????????????????????????????6 1.7 车厢出站问题??????????????????????????????9 1.8 编写对任一栈作进栈和出栈运算的 C 函数?????????????????10 1.10 写出表达式等价的后缀表达式。?????????????????????12 1.11 编写一个统计给定的线性链表的结点个数的 C 函数。????????????15 1.12 编写一个将给定的线性链表逆转的 C 函数。????????????????16 1.13 编写一个插入值的 c 函数。???????????????????????18 1.14 编写一个删除链表中结点的前趋结点的 C 函数。??????????????19 1.15 试编写一个将两个链表归并成一个线性链表的 C 函数。???????????20 1.17 用环形链表解 1。6 题?????????????????????????23 1．18 将给定的线性链表改成环形链表????????????????????24 1． 19 将给定的线性链表改成一个带表头的环形链表??????????????25 1．20 编写用 hash 函数 h（Xi）＝Xi，对 X1，X2??X800 进行 hash 存储的程序?26 1． 21 求广义表的深度。??????????????????????????27 2．1 试编写一个在两个顺序字符串中寻找最大公共子串的 C 函数。????????29 2． 2 试编写一个实现 STRINS（S1，I，S2）的 C 函数。?????????????31 2．3 按照 2.2 题的要求，编一个实现 STRDEL（S，I，J）的 C 函数。???????32 3．1 编写一个二分插入排序的 C 程序?????????????????????33 3．2 编写一个对给定链表进行插入排序的 C 程序。???????????????34 3．5 采用顺序存储实现，即用数组存放排序过程中以排好序的链表的头指针。???36 3． 6 采用顺序存储的结构即数组实现。????????????????????38 3．7 编写一个实现快速排序的非递归的 C 函数。????????????????39 3．8 对于分别写出用下列排序方法对线性表进行排序的结果。??????????40 4．3 将 n 阶三对角阵（即半带宽为 1 的带状矩阵）A 按行序列序存放在一维数组 b[3*n-2]中。 若 aij(|i-j|&=1)存放在 b[k]中，请求出求解 k 的计算公式。?????????????42 4．4 如果把广义的 Anab 按行序列序存放在一维数组 b[(a+b-1)*n-(a+b-2)]中，元素 aij 存放在 b[k]中，那么请写出计算 k 的计算公式。????????????????????42 4．5 试编写一个求解两个三元数组相加的 C 函数。???????????????42 4．6 试编写一个将十字链表转置的 C 函数.???????????????????44 5．1 请分别给出对树进行前序、后序、层次序遍历后的结点序列。????????45 5．2 试叙述将 m 棵有序树组成的有序树林转换成相应的二叉树的逆变换。?????46 5．3 试编写一个把树中每个结点的左右子结点进行对换的 C 函数。????????47 5．4 编写一个利用栈来实现后序遍历一棵给定的二叉树的 C 函数。????????49 5．5 题目：????????????????????????????????51 试为下面各小题分别编写一个 C 函数： （1） 按前序输出 T 的结点值。 （2） 按后序输出 T 的结点值。 （3） 输出树 T 的叶子结点值。1 数据结构（4） 求出树 T 的次数。 5．6 试编写一个把树 T 按标准形式进行存贮的 C 函数。?????????????53 5．7 已知树 T 中结点的中序和后序，编写一个把 T 按标准形式存储的 C 函数????54 5．8 判断给定的二叉树是否为完全二叉树???????????????????55 5．9 判断两棵给定的二叉树是否相似?????????????????????55 5．10 把树 T 转换成由标准形式进行存储的树 T?????????????????55 5．11 试编写一个寻找结点 a 的父结点的 C 函数。????????????????56 5．12 试编写一个按前序遍历穿线树的 C 函数。?????????????????58 6．1 画出由集合中结点所构成的查找树，画出删除后的查找树。?????????60 6．2 试编写一个用平分法构造出由集合中结点所构成的丰满查找树的 C 函数。???60 6．5 编写一个判断给定二叉树 T 是否为平衡树的 C 函数。????????????62 6．6 试画出 Adelson 插入方法的右改组的转换图。???????????????65 6．9 试画出用 Hu-Tucker 算法构造出的最佳叶子查找树。????????????66 6．10 画出每次插入后的 B－树???????????????????????67 6．12 修改皇后问题????????????????????????????70 6．13 马的周游路线????????????????????????????76 7．1 对于图题 7.1（P235）的无向图，给出：?????????????????79 （1） 表示该图的邻接矩阵。 （2） 表示该图的邻接表。 （3） 图中每个顶点的度。 7．2 对于图题 7.1 的无向图，给出：?????????????????????79 （1）从顶点 1 出发，按深度优先搜索法遍历图时所得到的顶点序 （2）从顶点 1 出发，按广度优先法搜索法遍历图时所得到的顶点序列。 7．3 对于图题 7.3 的有向图，给出：?????????????????????84 （1） 表示该图的邻接矩阵。 （2） 表示该图的邻接表。 （3） 图中每个顶点的入度和出度。 7．4 对于图题 7.3 的有向图，给出：?????????????????????85 （1） 从顶点 1 出发，按深度优先搜索法遍历图时的所得的顶点序列。 （2） 从顶点 1 出发，按广度优先搜索法遍历图时的所得的定点序列。 7．5 对于图题 7.1 的无向图，试问它是（1）连通图吗？（2）完全图吗？?????85 7．6 对于图题 7.3 的有向图，试问它是（1）弱连通图吗？（2）强连通图吗？??86 7．7 图题 7-7 是有向图，试问其中哪个图是??????????????????86 （1） 弱连通的？ （2） 强连通的？ 7．8 具有 N 个顶点的连通无向图至少有几条边？????????????????86 7．9 具有 N 个顶点的强连通有向图至少有几条边？???????????????86 7．10 分别写出用深度和广度优先搜索法遍历完全无向图的顶点序列。?????? 87 7．11 改写以深度优先搜索法遍历给定的连通图的 dfs 程序。???????????87 7．12 在图题 7.1 中，从顶点 1 出发，分别画出其 dfs 生成树和 bfs 生成树。???882 数据结构1.1：比较 2 个线性链表的 C 函数1． 存储法：用两个数组存放线性表。 2． 存储结构：一般的顺序存储方式。 3． 源程序： int comp(int a[],int as,int b[],int bs) { int tmp=as&bs?as: for(i=0;i&i++) { if(a[i]&b[i]) return 1; if(a[i]&b[i]) return -1; } if(as&bs) return 1; if(bs&as) return -1; return 0; } 4.测试用例： 1． A[3]={1,2,3} B[3]={1,2,3} output : 0; 2． A[3]={1.2.3} B[3]={1,1,3} output: 1; 3． A[3]={1,2,3} B[3]={1,2,4} output: -1 4． A[3]={1,2,3} B[4]={1,2,3,0} output: -1; 5． A[4]={1,2,3,0} B[3]={1,2,3} output: 1; 6． A[4]={1,2,3,0} B[3]={1,3,2} output:-1;1.2写一个倒置顺序存贮的线性表的 C 函数。要求用最少的附加存贮空间来完成。 ? 分析：假设用数组 a 存贮一组 int 类型的数据，每次将 a[0]取出，其余数依次前移，然后 将 a[0]放到 尚未倒置的数据元素的最后，直至整个数组完成倒置。 （1） t=a[0]， 取 余下的 a[1]， （2） a[2]， ...a[n-1]依次前移一个位置； a[n-1]=t； ? 算法： （3）对由 a[0]，a[1]...a[n-2]组成的数组重复上述步骤。 ? 程序： # include&stdio.h& # define N 10 void reverse(a,n) int a[]; {int t,i,j=0; while(j&n-1) {t=a[0]; for(i=0;i&n-j-1;i++) a[i]=a[i+1];3 数据结构a[i]=t; j++; } } void main( ) {int a[N]; printf(&Input the array:\n&); for(i=0;i&N;i++) scanf(&%d&, &a[i]); reverse(a,N); printf(&The reversed array:\n&); for(i=0;i&N;i++); printf(&%d &,a[i]); printf(&\n&); } ? Sample: Input the array:
The reversed array: 1.3在具有 n 个结点的顺序存贮的线性表中，对值相同的结点只保留一个，把多余的结点删除 掉，使线性表中没有值相同的结点。试编写一个实现上述操作的 C 函数，并分析该程序的执 行时间。 解答： 首先应对线性表中每一个结点进行搜索，找到和他值相同的结点就把其删除，同时改变 原结点的个数。主要运用两层循环：最外层对线性表中的第 0 到第 n-2 个元素进行扫描，第 二层是对于第一层的每一个元素从其后面一个元素开始扫描，检查是否有和该元素值相同的 元素若有则删除该元素，若无则循环关键值+1 进行下一个元素比较，直到线性表最后一个元 素，然后在回到上层循环。如此继续，直到跳出所有循环时，所得线性表即为题目要求的线 性表。 下面给出实现的函数。Sq_delete()为删除一个结点的函数，i 表示所要删除的结点的下 标，del()为删除线性表中所有相同结点的函数。其中 list[]为进行操作的线性表，*p_m 和 *p_n 在两个函数中都表示线性表中结点个数。 #include&stdio.h& #define M 100 int sq_delete(int list[],int *p_m,int i) { if(i&0||i&=*p_m) return(1); for(j=i+1;j&*p_m;j++)4 数据结构list[j-1]=list[j]; (*p_m)--; return (0); } void del(int list[],int *p_n) { int i,j; for(i=0;i&((*p_n)-1);i++) for(j=i+1;j&(*p_n);j++) if(list[i]==list[j]){sq_delete(list,p_n,j);j--;} } main() { int list[M],i,n; printf(&Input the number of the data:\n&); scanf(&%d&,&n); for(i=0;i&n;i++){ printf(&Input data %d:\n&,i+1); scanf(&%d&,&list[i]); } del(list,&n); for(i=0;i&n;i++) printf(&%d &,list[i]); } 对于以上程序提供一组测试数据： Input the number of the data: 5L 输入一组数据为：13 23 33 13 23L 执行完毕后得到的输出结果为：13 23 33 对于该程序的时间复杂性分析： 主要是 del 和 sq_delete 两个函数中的循环语句的执行时间。 一种极端情况是线性表中 的数据没有一个重复，则只执行 del 中的循环体，(n-1)+(n-2)+??+1=O(n*n);另一种极端 情况是线性表中只有一个元素，其他都与它重复，此时 del 的内和外循环都只执行一次，主 要的执行时间用在了 sq_delete 上， 可以知道他的复杂性也是 O(n*n).故总的来说该程序的时 间复杂性是 O(n*n)。1.4编写一个求解给定多项式在 X=Xo(Xo 为指定的某个值)时的值的 C 函数。 存储法：定义结构数组 struct node { }; typedef struct node TERM #define max 1005 数据结构NODE a[max]; 算法步骤：1 令 sum=0, i=0 2 算出第 i 项的值，并与 sum 相加。 3 若 i&n, 则转 2，否则 return(sum) 程序： float cal ( float x, TERM a[ ], int n ) { int i, j, for ( i=0; i&n; i++ ) { for ( k=1, j=1; j&= a[i ]. E j++) k=k*x; sum+= a[i ].coef*k; } return(sum); } 测试用例： 令 x=2; 多项式为 3x6+8x4+5x2+9 结果为 349。1.5实现多项式乘法 一：存储结构： 多项式以线性链表存储，以增加其插入删除的效率。结果多项式与所给多项式采取相 同的存储结构，以方便实现多项式的连乘。 二：分析 多项式的加法书上有源程序，而乘法与加法相似，只是由于乘法的规则与加法不 同，因此我用了一个双重循环来实现（详见源程序） ，得到一个结果项之后，查找结果链 表，若已有，则看是否相加之后为 0，若为 0，则将该项删去，否则，就直接改系数，若 没有，则直接链上。 原本想用数组加链表的索引法来实现，但据分析后，认为并不能显著提高效率， 显得得不偿失，因此，我就使用了最原始的方法，请老师同学多多指教。 三：输入/输出 输入：先输入 A、B 多项式（根据提示） 输出：A、B、C（A×B） 四：源程序 #include&stdio.h& struct node{ struct node * }; typedef struct node NODE;6 数据结构int search(int exp,NODE *c,NODE **pc,NODE **qc) { *pc=NULL; *qc=c; if(c==NULL) return(0); while((*qc)-&exp&exp) {*pc=**qc=(*qc)-&} if((*qc)-&exp==exp) return(1); return(0); }NODE *multi(NODE *a,NODE *b) {NODE *pa,*pb,*pc,*qc,*p,*c=NULL; int exp,data, for(pa=a;pa!=NULL;pa=pa-&next) for(pb=b;pb!=NULL;pb=pb-&next) {exp=pa-&exp+pb-&data=pa-&data*pb-& if(data) {flag=search(exp,c,&pc,&qc); if(flag) if(!(data+qc-&data)) {pc-&next=qc-&free(qc);} else (qc-&data)+= else {p=(NODE *)malloc(sizeof(NODE)); p-&data=p-&exp= if(!pc) c=p; else pc-&next=p; p-&next= } } } return(c); }NODE* creat() {NODE *root,*p,*q; printf(&Do you want to creat a null one(Y/N)?\n&); scanf(&%c&,&ch); getchar(); if(ch=='y'||ch=='Y') return(NULL); p=NULL;7 数据结构ch='y'; for(i=0;ch=='y'||ch=='Y';i++) {q=(NODE*)malloc(sizeof(NODE)); if(p==NULL) root=q; else p-&next=q; printf(&\nPlease input the DATA of node %d:\n&,i); scanf(&%d&,&(q-&data)); getchar(); printf(&Please input the EXP of node %d:\n&,i); scanf(&%d&,&(q-&exp)); getchar(); printf(&Do you want to continue(Y/N)?\n&); scanf(&%c&,&ch); getchar(); p=q; } p-&next=NULL; return(root); } void print(NODE *root) {int i=0; if(!root) printf(&\n0&); while(i++,root!=NULL) {printf(&\nNODE %d:\tDATA:%d\tEXP:%d&,i,root-&data,root-&exp); root=root-& } }main() { NODE *a,*b,*c; clrscr(); printf(&Now please input A:\n&); a=creat(); printf(&Now please input B:\n&); b=creat(); printf(&\nA:\n&); print(a); printf(&\nB:\n&);8 数据结构print(b); c=multi(a,b); printf(&\n\n\nC:\n&); print(c); } 五：测试数据： 输入： A：5X^6+3X^4+2X B：7X^3+3X^2+5 输出： C：35X^9+15X^8+21X^7+34X^6+29X^4+6X^3+10X 输入： A：0 B：5X^3+2X^2 输出：0 输入： A：3X^2+5X^1 B：3X^1－5 C：01.7假设右边轨道排列有编号为 1，2，3,?,n 的 n 节车厢，它们依次被拖进站，从左边轨道依次 出站的号的排列顺序有 a n 种情况 。那么 a n 是用下列方法所形成的所有可能排列顺序的总 数：某时刻站中只剩下编号为 k+1 的车厢，而此时左边轨道是已出站的编号为 1，2，3，?,k 的车厢， 则排列顺序有 ak 种； 右边轨道是尚未进站的编号为 k+1， k+2,?,k+n 的 n-k-1 节车厢， 则可能有的排列顺序有 an-k-1 种。因此 给出了前 k 节车厢已出站的情况下所有的排列顺 序，我们应该取遍 k（0≤k≤n）的所有可能值，获得 akan-k-1 这样形式的所有项，然后把它 们相加起来，可得到如下的关系式： a0=1； a1=1； an=a0an-1+a1an-2+...+an-1a0( n&1)an=∑akan-k-1 (0≤k≤n-1) 为了求解排列顺序的数目，先求解这个递推关系： 令 g（x）=a0+a1x+?+anx? n&1 即 g（x）=∑akxk (k≥0) 让 g（x）自乘得 g2(x)=g(x)g(x) =(a0+a1x+a2x2+...)(a0+a1x+a2x2+...)9 数据结构=a0a0+(a0a1+a1a0)x+(a0a2+a1a1+a2a0)x2+... =Σ (Σ akan-k)x? (0≤n,0≤k≤n) 由上式可知，g2(x)的 xn 项的系数正好是 an＋1。因此有 g2(x)=∑an+1x? (n≥0) 如果我们用 x 乘 g2(x)，则有 xg2(x)=a1x+a2x2... 两边都加上 a0，又因为 a0=1，故有 1+x g2(x)=∑akxk 1+xg2(x)=g(x) 求解得 g（x）=[1±√(1-4x)]/2x 因为 a0=1，所以 g（x）=1-√(1-4x)]/2x 再根据二项式定理，将(1-4x)1/2 展开，得 g(x)=1/2x[1-∑(1n/2)(-4x)n] 令 n=m+1,则有 g(x)= ∑( 1/2m+1)(-1)m 22m+1xm 比较可知 an 是上式中 x?项的系数。 所以 an=(1n+1/2)(-1)n22n+1 化简得 an=1/(n+1)(2nn) n 节车厢出站有 1/(n+1)(2nn)种排列顺序。 (n≥0) (m≥0) (k≥0)所以， 当 n=3 时，有 5 种排列顺序，分别为 ①②③，①③②，②①③，②③①，③②①； 当 n=4 时，有 14 种排列顺序。 存储结构可采用栈实现。1_8. 假设 2 个栈共享一个数组 stack[n]，编写对任一栈作进栈和出栈运算的 C 函数，push(x,i) 和 pop(i),i=1,2。这里 i=1 表示左边的栈，＝2 则表示右边的栈。要求整个数组元素都被占用时才 产生溢出。 存储结构： 用一个数组存放 2 个栈。如图：(M 为数组元素个数) 3 2↑ ↑ ↑ ↑ tail1=0 head1 head2 tail2=M-1 head1,head2 分别为栈 1，栈 2 中下个元素入栈的位置，tail1，tail2 为两个栈底。 分析与算法步骤： 因为 tail1＝0,tail2＝M－1，一般情况下不会变动，所以省去这 2 个量。 初始值：head1＝0，head2＝M-1； 1．执行入栈时：10 数据结构（1） 若 head1-1+1＝head2+1，即 head1＝head2+1 时，整个数组满，溢出。 （2） 若对栈 1 入栈，把元素存入 stack[head1]，head1++； （3） 若对栈 2 入栈，把元素存入 stack[head2]，head2DD； 2．执行出栈时： （1）对栈 1： 若 head1＝0，栈空，出栈失败； 否则 head1DD； （2）对栈 2： 若 head2＝M－1，栈 2 空，出栈失败； 否则 head2++； tc 程序： include&stdio.h& #define M 10 int head1=0,head2=M-1; int stack[M]; void push(int x,int i) {if(head1==head2+1) {printf(&the stack is full.fail to push.\n&); } if(i==1) stack[head1++]=x; else stack[head2--]=x; } void pop(int i) {if(i==1) {if(head1==0) {printf(&the stack is empty.fail to pop.\n&); } *p=stack[--head1]; } else {if(head2==M－1) {printf(&the stack is empty.fail to pop.&); } *p=stack[++head2]; } }11 数据结构main() {int x,i,No=1; for(i=0;i&M;i++) stack[i]=0; while(No!=0) {printf(&seclect the operation:\npush:1;\npop:2;\nprint:3\nexit:0;\n&); scanf(&%d&,&No); switch(No) {case 1: printf(&input the number you want push and the team No,\n&); scanf(&%d %d&,&x,&i); if(i==1||i==2) push(x,i); else printf(&wrong number.select again.\n&); case 2: printf(&input the team you want to pop:\n&); scanf(&%d&,&i); if(i==1||i==2) pop(i); else printf(&wrong number,select again.\n&); case 3: for(i=head1-1;i&=0;i--) printf(&%d&,stack[i]); printf(&\n&); for(i=head2+1;i&M;i++) printf(&%d&,stack[i]); printf(&\n&); } } } 测试用例： 在 main 函数中，提供了操作的选择。1 为入栈，2 为出栈，3 为输出 2 个栈中的元素，0 为退出操作。 第一次进栈 1：1，2，3，4，5； 输出：12345 第二次进栈 2：6，7，8，9，10； 输出：678910 栈 1 连续出栈 5 次后，继续执行出栈，输出为 the stack is empty.fail to pop. 栈 2 连续出栈 3 次后，输出栈 2 中元素为 9101．10写出与下列表达式等价的后缀表达式： (1) a+b*c/d+e^f^g+h (2) (a+b)*(c/d)+(e^f)^(g+h)12 数据结构存储结构： 对于两个表达式采用字符数组存储形式，并以‘\0?作为结尾。 另外，使用一个栈来存放运算符，当遇到运算符,就把运算符入栈，直到某个适当的时机， 再让运算符出栈。 算法分析： 当前扫描到的字符按以下几种情况分别处理： a) 若当前的字符是变量，则立即将它输出。 b) 若当前的字符是?(?，则让?(?入栈。 c) 若当前的字符是运算符(?+?,?-?,?*?,?/?,?^?),则将它的（进栈前)优先级别与栈顶字符的（栈 中）优先级别相比较。如果当前的运算符的优先级别小于等于栈顶字符的优先级别，那 么退出栈顶字符并输出。 这样的过程一直进行到当前的运算符的优先级别大于栈顶字符 的为止，然后让当前的运算符入栈。 d) 若当前的字符是?)?，则从栈中依次退出运算符并输出，直到?(?为止，然后退出?(?，但不 输出?(?. e) 若当前的字符是?\0?,则从栈中依次退出所有的运算符并输出，直到?$?为止，?$”不退栈， 也不输出。 下面给出程序： #define MAXN 100 int icp(char c) { switch(c) { case '^':return(4); //进栈前的运算符的优先级 case '*': case '/':return(2); case '+': case '-':return(1); } } int isp(char c) { switch(c) { case '^':return(3); //栈中的运算符的优先级 case '*': case '/':return(2); case '+': case '-':return(1); case '(':return(0); case '$':return(-1);//置于栈底，保证后面的运算符能进栈 } } int ischar(char c) { if((c&='A'&&c&='Z')||(c&='a'&&c&='z')) return(1); else return(0);13 数据结构} int mid_to_pos(char midexpress[],char posexpress[]) {char stack[MAXN],c; int top,i,j; stack[0]='$'; top=0; j=0; i=0; c=midexpress[0]; while(c!='\0') { if(ischar(c)) posexpress[j++]=c; else switch(c) { case '+': case '-': case '*': case '/': case '^': while(icp(c)&=isp(stack[top])) posexpress[j++]=stack[top--]; stack[++top]=c; case '(': stack[++top]=c; case ')': while(stack[top]!='(') posexpress[j++]=stack[top--]; top--; default: return(1); } c=midexpress[++i]; } while(top&0) posexpress[j++]=stack[top--]; posexpress[j]='\0'; return(0); } 测试报告： void main()14 数据结构{char midexpress[MAXN],posexpress[MAXN],c; int i, i=0; printf(&\ninput the mid_expresstion:(end with '!')\n&); scanf(&%c&,&c); while(c!='!') { midexpress[i++]=c; scanf(&%c&,&c); } midexpress[i]='\0'; result=mid_to_pos(midexpress,posexpress); if(result==1) printf(&convertion fails!\n&); else { printf(&the pos_expresstion is:\n&); printf(&%s&,posexpress); } } 输入：(a+b*c)^d^(e*f/g)-h*i!(输入以?!?结尾) 输出：abc*+def*g/^^hi*输入：a+b*c/d+e^f^g+h! 输出：abc*d/+efg^^+h+ 输入：(a+b)*(c/d)+(e^f)^(g+h)! 输出：ab+cd/*ef^gh+^+1．11编写一个统计给定的线性链表的结点个数的 C 函数。 存储结构： 连表的结点采用： struct node{//关键字的类型自定 struct node *}; 算发分析： 利用链表的性质（结点中的指针指向下一个结点） ，逐步向表尾移动，以此计算出结点 数。 下面给出程序： typedef struct node{ struct node * }NODE; int count(NODE *head) {NODE *p;15 数据结构int c=0; p= while(p!=NULL) {p=p-& c++;} return(c); } 测试报告： void main() {NODE a[10]; int i=0; for(;i&9;i++) {a[i].data=i; a[i].link=&a[i+1];} a[i].data=i; a[i].link=NULL; printf(&the total amount of the linked node is:%d\n&,count(&a[0])); } 输入：|0---1---2---3---4---5---6---7---8---9^ 输出：the total amount of the linked node is:101．12编写一个将给定的线性链表逆转的 C 函数，只允许改变结点的指针值，不允许移动结点值。 算法如下： (1) 置 P 为链表首址，R,Q 为空； ，否则转（3） ； (2) 若 P 为空返回 NULL；算法结束，转（5） ，否则转（4） ； (3) 若链表只有一个结点，转（5） ，否则转（4） ； (4) R&=P,P&=P-&LINK,R-&LINK&=Q,置 Q=R,若 P-&LINK 为空，转（5） (5) P-&LINK&=R,返回 P,算法结束。 源程序如下： #include &stdio.h& typedef struct node{ struct node* }NODE; NODE* tranfer(head) NODE * { NODE *p,*q,*r; p= r=q=NULL; if(head==NULL) return(NULL);16 数据结构if(p-&link!=NULL) {do{ r=p; p=p-& r-&link=q; q=r; }while(p-&link!=NULL); } p-&link=r; return(p); } NODE* create(n)/*建立初始链表*/ { NODE *head,*p,*q; if(n==0) return(NULL); head=(NODE*)malloc(sizeof(NODE)); p= for(i=1;i&n;i++) { scanf(&%d&,&(p-&data)); q=(NODE*)malloc(sizeof(NODE)); p-&link=q; p=q; } scanf(&%d&,&(p-&data)); p-&link=NULL; return(head); } main() { NODE *head,*r,*p; int n=5; printf(&enter the data:\n&); head=create(n); p= while(p!=NULL) { printf(&%d &,p-&data); p=p-& }17 数据结构printf(&\n&); head=tranfer(head); p= printf(&now the list is:\n&); while(p!=NULL) { printf(&%d &,p-&data); p=p-& } printf(&\n&); } 输入：1 2 3 4 5 输出：5 4 3 2 11.13对于给定的线性链表,编写一个把值为 a 的结点插在值为 b 的结点的前面的 c 函数。若值为 b 的结点不在线性链表中，则把 a 插在表的最后。 [存储结构] 利用线形表的链接存储： typedef struct node{ struct node *}NODE; 定义指针 NODE **head,*p,*q,*t; [解题思路] 指针*head 指向链表的根结点，指针 p 指向值为 b 的结点，指针 t 指向它的前趋结 点，指针 q 指向插入结点 a。 (1) 如果头结点*head 为空，或*head 的结点值为 b，修改头指针，结束算法； (2) 查找值为 b 的结点，若找到，把值为 a 的结点插到 b 的前面； (3) 若找不到，把 a 结点插在链表最后；结束算法。 #include&stdio.h& [程序] typedef struct node{ struct node *}NODE; void insert(NODE **head,char a) {NODE *p,*q,*t; q=(NODE*)malloc(sizeof(NODE)); q-&data=a; if(*head==NULL||(*head)-&data=='b') {q-&link=* *head=q;} for(p=*p-&data!='b'&&p!=NULL;p=p-&link) t=p; q-&link=p; t-&link=q; } [测试用例 1] 原链表：b,c,d,e,g,h18 数据结构插入 a 结点后：a,b,c,d,e,f,g,h [测试用例 2] 原链表：c,d,e,f,g,h 插入 a 结点后:c,d,e,f,g,h,a [测试用例 3] 原链表：c,d,e,b,f,g,h 插入 a 结点后:c,d,e,a,b,f,g,h1-14对于给定的线性链表，编写一个删除链表中值为 a 的结点的前趋结点的 C 函数。 [存储结构] 线性链表采用标准形式存储的单链表，并使用如下的说明： typedef struct node{ struct node* }NODE; [算法] 假设给定的单链表的头指针为 head， 我们将指向 head 的指针 p_head 作为函数 fro_del 的参数。 为了删除值为 a 的结点的前趋结点，我们使用 3 个 NODE 类型的指针 p1，p2，p3。初始时， 置 p1=*p_head,p2=NULL,p3==NULL. 循环过程中,p1 不断向前探索，p2 始终指向 p1 的前趋结点，p3 又始终指向 p2 的前趋结点,直 到 p1-&data==?a?或 p1==NULL 结束。 （1） 若结束是由 p1==NULL 引起的，则未找到值为 a 的结点，删除失败，返回 1。 （2） 若结束是由 p1-&data==?a?引起的，并且此时 p2==NULL,则结点 a 为头结点，没有前趋 结点，故删除失败，返回 1。 （3） 否则，删除 p2 指向的结点,并返回 0。删除中，如果 p2 为头结点，置*p_head==p1;否 则，置 p3-&link==p1。删除成功。 [流程图] YP1=NULL n n P1-&data=aNY YP2=NULL ?NP3=p2N YP2=head?P2=p1 P1=p1-N&link*p_head=p1 返回 1P3-&link=p1返回 0[C 程序] int fro_del(NODE** p_head) {19 数据结构NODE * p1=*p_head,*p2=NULL,*p3==NULL; If(p1==NULL)return(1); Whie(p1!=NULL&&p1-&data!=?a?) { p3=p2; p2=p1; p1=p1-& } if(p1==NULL||p2==NULL)return(1); if(p2==*p_head)*p_head=p1; else p3-&link=p1; free(p2); return(0); } [测试] （1）如果原单链表为空或为 bcdef，则删除失败。 （2）如果原单链表为 a 或 abcdef，则删除失败。 （3）如果原单链表为 bacdef，则删除为 acdef。 （4）如果原单链表为 bcadef，则删除后变为 badef。1.15设 X=（x0,x1,…,xm-1）和 Y=(y0,y1,…yn-1)是两个线性链表。试编写一个将这两个链表归并 成一个线性链表 Z 的 C 函数，使得 m&=n 时 Z=（x0,y0,x1,y1,…,xm-1,ym-1,ym,…yn-1） m&n 时 Z=(x0,y0,x1,y1,…xn-1,yn-1,xn,…xm-1) 存储结构：#include&stdio.h& typedef struct node{ struct node * }NODE; 分析和算法操作： 需要一个由字符串生成链表的函数。 将两个链表归并成一个链表时在表头前附加一个虚结点，处理完后再将其释放掉。若无虚结 点归并时需分情况处理，比较复杂。 #include&stdio.h& typedef struct node{ struct node * }NODE; NODE *makelist(a) char a[]; {NODE *head,*p,*q; if(a[0]=='\0')return(NULL);20 数据结构head=(NODE *)malloc(sizeof(NODE)); head-&data=a[0]; head-&link=NULL; p= for(i=1;a[i]!='\0';i++) {q=(NODE *)malloc(sizeof(NODE)); q-&data=a[i]; q-&link=NULL; p-&link=q; p=q; } return(head); } NODE *linklist(p,q) NODE *p,*q; {NODE *head,*r,*s; head=(NODE *)malloc(sizeof(NODE)); head-&link=NULL; r= while(p!=NULL&&q!=NULL) {r-&link=p;s=p-& p-&link=q; r=q;p=s;q=q-& } while(p!=NULL) {r-&link=p;r=p;p=p-&} while(q!=NULL) {r-&link=q;r=q;q=q-&} s= head=head-& free(s); return(head); } main() {char a[100],b[100]; NODE *xhead,*yhead,* printf(&input a string:\n&); scanf(&%s&,a); printf(&input a string:\n&); scanf(&%s&,b); xhead=makelist(a); yhead=makelist(b); zhead=linklist(xhead,yhead); while(zhead!=NULL)21 数据结构{printf(&%c-&&,zhead-&data); zhead=zhead-& } } 测试用例： 输入：ABCDEF 和 GHIJKLMN 输出：A-&G-&B-&H-&C-&I-&D-&J-&E-&K-&F-&L-&M-&N1_15二．题目： 设 X= ?x0 , x1 ,...,xm?1 ? ,Y= ? y0 , y1 ,..., yn?1 ? 是两个线性链表，试编写一个将这两个线性链 表归并成一个线性链表 Z 的 C 函数，使得 Z= ??( x0 , y 0 , x1 , y1 ,?, xm?1 , y m?1 ,?, y n ?1 ) 当m ? n时 ? ( x0 , y 0 , x1 , y1 ,?, xn?1 , y n?1 ,?, y m?1 ) 当m ? n时三．算法分析： （1） 若 X 表或 Y 表为空，返回表 Y，否则进入（2） ； （2） 将 Y 表相应结点 y(i)插入 X 表中 x(i)与 x(i)-&link 之间； （3） 如果 Y 表仍有剩余，将其插入以上生成的 Z 表中。 四．程序如下： typedef struct T { struct T * }NODE; NODE *merge(NODE *x,NODE *y) { NODE *z=x,* if(x==NULL) if(y==NULL) while(x&&y){ yn=y-&/*yn:*/ y-&link=x-& x-&link=y; if(y-&link==NULL) x=y-& y= } if(y-&link==NULL) y-&link=22 数据结构 }1_171. 存贮结构: 按题目要求,采用环形链表实现. 2. 存储方式: 用链接存储的环形队列实现. 3. 源程序: #include &stdio.h& struct node { struct node * }; typedef struct node NODE; NODE *crearl(int n) { NODE *head,* head-&data=1; new= for(i=1;i&n;i++) { new-&link=(NODE *)malloc(sizeof(NODE)); new=new-& new-&data=i+1; } new-&link= } void printrl(NODE *head,int i,int k) { NODE *p,*q; p= if(i!=1) { q=NULL; while(p-&data!=i) { q=p; p=p-& } } else23 数据结构{ while(p-&link!=head) p=p-& q=p; p=p-& } for(a=0;a&k-1;a++) { q=p; p=p-& } printf(&the result is:&); while(p-&link!=p) { printf(&%d &,p-&data); q-&link=p-& free(p); p=q-& for(a=0;a&k-1;a++) { q=p; p=p-& } } printf(&%d &,p-&data); } void main() { int n,i,k; NODE * clrscr(); printf(&input n,i,k:&); scanf(&%d%d%d&,&n,&i,&k); head=crearl(n); printrl(head,i,k); } 4. 测试用例: n=10,I=1,k=3 output:3 6 9 2 7 1 8 5 10 4 n=10 I=5 k=12 output:6 9 3 10 8 2 1 7 5 41_181. 存储结构:按题目要求为一般线形链表 2. 存储方式:用链表实现24 数据结构3. 源程序: NODE *nltorl(NODE *head) { NODE *tmp= While(tmp-&link!=NULL) Tmp=tmp-& Tmp-&link= R } 4.测试用例: 经过将普通链表测试,可以转为环形链表.1_19假设给定的线性链表的结点值为整数。编写一个将给定的线性链表改造成一个带表头结点的 环形链表的 C 函数，并让表头结点的值等于原来线性链表中结点的个数。 ? 分析：先数出原链表中结点的个数，存入新开辟的表头结点中，将表头结点连到原链表表 头上，并将表尾指针指向表头结点，head 指向表头结点。 ? 程序： # include&stdio.h& typedef struct node{ struct node * }NODE; NODE* convert(NODE* t) /*t 为原链表的表头结点*/ {NODE *head,*p,*q,*k; int n=0; k=(NODE*)malloc(sizeof(NODE)); k-&data=n; k-&link=NULL; head=k; if(t==NULL) {k-&link=k;return(head);} p=t; k-&link=p; while(p!=NULL) {q=p;p=p-&n++;} q-&link=k; k-&data=n; return(head); } 在 main 中只需调用 convert 函数即可完成所要求的转化，函数返回值即为指向环形链 表表头的 head 指针。25 数据结构1_20y0=568731 yi=(15625*yi-1+22221)mod m xi=1000*yi/m (1&=i&=800) x1,x2,?,x800 是 0~999 之间的 800 个伪随机数。试按下面两种要求分别编写用 Hash 函 数 h（xi）=xi，对 x1,x2,?,x800 进行 Hash 存贮的程序： （1） 用开式寻址法解决冲突。 （2） 用拉链法解决冲突。 ? ? 分析：开式寻址法是在发生冲突时用循环地址探测序列进行线性探测，找出空位置可供 插入，而拉链法则是把具有相同 Hash 地址的的键值都存放在同一个链表中。 程序： 1） 开式寻址法： # include&stdio.h& # define M 1000 31 # define m 2 int x[801]; long int y[801]; int t[M]; void main( ) {int i,j,k; y[0]=568731; for(i=1;i&801;i++) {y[i]= (15625*y[i-1]+22221)% x[i]= 1000* y[i]/m; } for(i=0;i&M;i++) t[i]= -1; /* 因 x[i]是非负数，所以初始化 Hash 表时 t[i]全置为-1*/ for(i=1;i&801;i++) {j= x[i]; for(k=0;k&M&&t[(j+k)%M]&=0;k++); j=(j+k)%M; if(t[j]&0) t[j]= x[i]; } } 2） 拉链法 # include&stdio.h& # define M 1000 31 # define m 2 typedef struct node{ struct node* }NODE; 设 m=23126 数据结构int x[801]; long int y[801]; NODE *t[M]; void main( ) { NODE * p,*q,* y[0]=568731; for(i=1;i&801;i++) {y[i]= (15625*y[i-1]+22221)% x[i]= 1000* y[i]/m; } for(i=0;i&M;i++) t[i]= NULL; for(i=1;i&801;i++) {p=t[x[i]]; q=NULL; while(p!=NULL) {q=p;p=p-&} r=(NODE*)malloc(sizeof(NODE)); r-&key= x[i]; r-&link=NULL; if(q= =NULL) t[x[i]]=r; else q-&link=r; } }1_21求广义表的深度。我们规定空的广义表的深度为 0，而一般的有 0 若 s?是一个原子 depth(s)= { 1+max(depth(a0),? depth(an-1)) 若 s 是广义表（a0,a1,?an-1） 编写一个求解广义表 s 的深度的 C 函数。 解答： 有题目给出的深度的公式，很容易想到运用递归来实现所要求的功能。这里在主函数中简单 的采用直接构造各种类型的广义表法，为了测试算深度函数的有效性。 #include&stdio.h& struct node{ union{struct node * }27 数据结构struct node * }; typedef struct node NODE; int depth(NODE *p) { int max,t; if(p==NULL)return(0); if((p-&tag)==0)max=1; else max=depth(p-&dd.dlink)+1; t=depth(p-&link); return(t&max?t:max); } main() { NODE *head,*p; int d,i; char k='a'; head=NULL; /*(1)*/ d=depth(head); printf(&the depth is:%d\n&,d); head=(NODE *)malloc(sizeof(NODE)); /*(2)*/ head-&tag=0; head-&dd.data=k; head-&link=NULL; p= for(i=1;i&4;i++){ p-&link=(NODE*)malloc(sizeof(NODE)); p=p-& p-&tag=0; p-&dd.data=k+i; p-&link=NULL; } d=depth(head); printf(&the depth is:%d\n&,d); k='e'; /*(3)*/ p= for(i=1;i&4;i++){ p-&tag=1; p-&dd.dlink=(NODE*)malloc(sizeof(NODE)); p=p-&dd. p-&tag=0; p-&dd.data=k; p-&link=NULL; } d=depth(head); printf(&the depth is:%d\n&,d); }28 数据结构在主函数中构造了三种结构各异的广义表。 （1） 空的广义表，得到的深度为 0。 （2） 0,a,-&0,b-&0,c-&0,d，^ 得到的深度为 1。 （3） 1，K，-》0,b-&0,c-&0,d^ 得到的深度为 4。 1,K,^ 1,K^ 0,e,^2_1假设 s 和 t 分别是具有 m 个和 n 个字符的顺序存贮的串。试编写一个在 s 和 t 中寻找最大公 共子串的 C 函数。 解答： 该题的本质即为模式匹配，实际上是把 t 中所有可能长度的子串与 s 进行模式匹配，从最长 长度 n 开始，若匹配成功就直接输出当前子串，否则长度自减 1 后重新开始匹配。直到长度 减为 0，此时则说明没有公共子串。下面的 C 函数利用了书中列出的几个函数实现了题目所要 求的功能。 #include&stdio.h& #include&string.h& #define MAXN 100 char t[MAXN],s[MAXN]; int flink[MAXN]; int m,n; int strsub(char s1[],int i,int j,char s2[]) { int m,k; if(i&0||i&=(m=strlen(s1))) return(-1); if(j&0||i&m) return(-1); for(k=0;k&j;k) s2[k]=s1[i]; s2[k]='\0'; return(0); } void faillink(char p[],int flink[],int m) {int j,k; flink[0]=-1; j=1; while(j&m) { k=flink[j-1]; while(k!=-1&&p[k]!=p[j-1]) k=flink[k]; flink[j]=k;29 数据结构j; } } int kmp_match(char t[],char p[],int flink[],int n,int m) { int i,j; i=0; j=0; while(i&n) { while(j!=-1&&p[j]!=t[i]) j=flink[j]; if(j==m-1)return(i-m); } return (-1); } void search_max(char s[],char t[],int m,int n) { char temp[MAXN]; int i,j,k; i=n; while(i&0) { k=0; while(k1&n){ strsub(t,k,i,temp); faillink(temp,flink,i); if(kmp_match(s,temp,flink,m,i)!=-1) { printf(&The max match is:\n&); for(j=0;j&i;j) printf(&%c &,temp[j]); } } i--; } printf(&No match found!\n&); } main() { printf(&Input the length of S's string:\n&); scanf(&%d&,&m); printf(&Please input the S's string:\n&); scanf(&%s&,s); printf(&Input the length of T's string:\n&);30 数据结构scanf(&%d&,&n); printf(&Please input the T's string:\n&); scanf(&%s&,t); search_max(s,t,m,n); } 运行示例： Input the length of S’s string: 8L Please input the S’s string: adgabcdeL Input the length of T’s string: 6L Please input the T’s string: fabcdgL 最后输出：a b c d2_2假设所使用的串采用链接存储结构，链表中每个结点可存放 M（M=4）个字符。试编写一个实 现 STRINS（S1，I，S2）的 C 函数。为了减少移动字符的次数，结点中允许使用无效的特殊字 符，但一个结点至少含有一个有效的字符。 存储法：struct node { char data[4]; struct node * }; typedef struct node NODE; 算法步骤： 1． 通过 i/4 算出 所在的结点 2． 通过 k= i %4 算出 i 在该结点中的位置 3． 开设一新结点，把该结点中 k 后的字符赋给新结点 4． 把该结点中赋过的字符及新结点中未赋过值的都置成无效字符‘*’ ， 5． 使新结点指向该结点的后继，该结点指向 s2 首结点，并把 s2 的末结点中的‘\0’置 成’ ，末结点指向新结点。 ‘*’ void strins(NODE *s1, int i, NODE *s2) { int j, k, l, NODE *p, *q, *r; j=i/4; k=i%4; p=s1; for(l=0; l !=j; l++)p=p-& q=(NODE *)malloc(sizeof(NODE)); for(m=k;m&4&&p-&data[m]!='\0';m++)31 数据结构{ q-&data[m-k]=p-&data[m]; p-&data[m]='*'; /* '*'is invalid char */ } if(p-&data[m]=='\0')q-&data[m-k]='\0'; else for(l=k;l&4;l++)q-&data[l]='*'; r=s2; while(r-&link!=NULL)r=r-& for(m=0; r-&data[m]!=’\0’; m++); r-&data[m]=’*’; while( m&4) r-&data[++m]=’*’; q-&link=p-& p-&link=s2; r-&link=q; } 若 S1=“ABCDEFGHI” ；S2=“JKLMNOP” ；I=6； 则调用后得 “ABCDEF**JKLMNOP*GHI2_3按照 2.2 题的要求，编一个实现 STRDEL（S，I，J）的 C 函数。 存储法同 2.2 算法步骤： 1． 计算出 S 中结点的个数 L 2． 通过 I/4 计算出其在 S 中的哪个结点 3． 通过 I%4 算出其在该结点中的位置 4． 若（I+J-1）/4 &L 则置该位置为‘*’ ； 否则，将 I 位所在结点中的所在位及其后均置为‘*’ ； 并将（ I+J-1）/4 位所在结点中的所在位及其前均置为‘*’ ； 5． 最后使 I 位所在结点指向（ I+J-1）/4 位所在结点 void strdel(NODE *s, int I，int j) { int k,l,m,h; NODE *p, *q; k=i/4; h=i%4; q=p=s; l=0; while(p-&link!=NULL) { p=p-& l++; } for(m=0;m!=k;m++)p=p-& if((i+j-1)/4&l)p-&data[h]='\0'; else { for(m=0;m!=(i+j-1)/4;m++)q=q-&32 数据结构for(m=h;m&4;m++)p-&data[m]='*'; for(m=(i+j-1)%4;m&=0;m--)q-&data[m]='*'; /* '*' is invalid char */ p-&link=q; } } 若 S=“ABCDEFGHIJKLMNO” ，I=3, j=10 则调用后结果为 “ABC* ***LMNO”3_1编写一个二分插入排序的 C 程序 一：数据结构 用一个数组 a 来存储数据元素，线性存储可以方便存储。 二：具体分析 使用二分查找来代替线性查找来进行插入操作可以显著提高效率，因此， 编写了一个 bi_search 函数来进行查找， 返回一个需要插入的位置给 j， 然后将 a[j]以后的元素 都向后移一个位置，将 a[i]放入 a[j]的位置。本题难度不高。 三：源程序 int bi_search(int a[],int n,int v) {int i,j,m; i=0; j=n-1; while(i&=j) {m=(i+j)/2; if(v==a[m]) return(m); if(v&a[m]) j=m-1; else i=m+1; } } void bi_insertion_sort(a,n) int a[]; {int i,j,k,x; for(i=1;i&n;i++) { x=a[i]; j=bi_search(a,i,x); for(k=i;k&j;k--) a[k]=a[k-1];33 数据结构a[j]=x; } } main() { int a[]={46,26,22,68,48,42,36,84,66}; clrscr(); bi_insertion_sort(a,9); for(i=0;i&9;i++) printf(&%d &,a[i]); } 四：测试结果 输入：46，26，22，68，48，42，36，84，66 输出：22，26，36，42，46，48，66，68，84 输入：15，44，15，6 输出：6，15，15，443_2编写一个对给定链表进行插入排序的 C 程序。 一：数据结构 使用线性链表存储数据元素，这样插入元素会比较方便，可以不用像线性数组那样需要 移动元素。 二：具体分析 由于线性链表不利于查找，因此首先需要找到所需插入的元素指针 p 的位置 q，r 为 q 的 前一元素，当 r 为 NULL（未发生变化） ，则说明需插在首元素位置，此时需要相应改变指针 head，若不为 NULL，则要将 p 连在 r 后，q 连在 p 后，w 用来存储 p 的后一个数据，这样可 以继续往后排，直到 p 为 NULL。 三：源程序 #include&stdio.h& struct node{ struct node * }; typedef struct node NODE; NODE *link_insertion_sort(NODE *head) {34 数据结构NODE *p,*q,*r,*w; p=head-& head-&next=NULL; while(p) {t=p-& w=p-& q=r=NULL; p-&next=NULL; while(q-&data&=t&&q) {r=q;q=q-&} p-&next=q; if(!r) head=p; else r-&next=p; p=w; } return(head); } main() { int t, NODE *head,*p,*q=NULL; clrscr(); printf(&Do you want to end(y|n)?&); scanf(&%c&,&ch); getchar(); head=NULL; for(count=0;ch!='y'&&ch!='Y';count++) { printf(&Please input the data!&); scanf(&%d&,&t); getchar(); p=(NODE*)malloc(sizeof(NODE)); p-&data=t; p-&next=NULL; if(!q) head=p; else q-&next=p; q=p; printf(&Do you want to end(y|n)?&); scanf(&%c&,&ch); getchar(); } printf(&The original one is:\n&);35 数据结构p= while(p) {printf(&%d &,p-&data); p=p-& } printf(&\n&); head=link_insertion_sort(head); printf(&The sorted one is:\n&); p= while(p) {printf(&%d &,p-&data); p=p-& } printf(&\n&); } 四：测试 输入：46，26，22，68，48，42，36，84，66 输出：22，26，36，42，46，48，66，68，84 输入：空 输出：空 输入：3，5，5，4，8 输出：3，4，5，5，8 输入：5，4，3，2，1 输出：1，2，3，4，5 输入：3,3,3,3 输出：3,3,3,33_5采用顺序存储实现，即用数组存放排序过程中以排好序的链表的头指针。 #include&stdio.h& #define MAXN 100 struct node { struct node * }; typedef struct node NODE; NODE* listmerge(head1,head2) NODE *head1,*head2;36 数据结构{NODE *p,*q,*pp,* p=head1; q=head2; pq=pp=NULL; while(p!=NULL&&q!=NULL) {if(p-&data&=q-&data) {pp=p; p=p-& } else {pq=q; q=q-& pq-&link=p; if(p==head1) head1= else pp-&link= pp= } } if(q!=NULL) pp-&link=q; return head1; } NODE* listmpass(head) NODE * {NODE *t[MAXN],*p; int i,k; if(head==NULL) return NULL; p= for(i=0;p!=NULL;i++) {t[i]=p; p=p-& t[i]-&link=NULL; } while(i&1) {for(k=0;;k++) if(2*k&i&&2*k+1&i) t[k]=listmerge(t[2*k],t[2*k+1]); else if(2*k&i&&(2*k+1)==i) t[k]=t[2*k]; i=k; } return (t[0]);37 数据结构} 如果原来的链表为： head→24→46→36→42→68→84→22→48→66 则排序以后为 head→22→24→36→42→46→48→66→68→843_6采用顺序存储的结构即数组实现。 #include&stdio.h& #define MAX 100 void merge(a,b,l,m,n) int a[],b[]; int l,m,n; {int i,j,k; i=l; j=m+1; k=l; while(i&=m&&j&=n) if(a[i]&=a[j]) b[k++]=a[i++]; else b[k++]=a[j++]; while(i&=m) b[k++]=a[i++]; while(j&=n) b[k++]=a[j++]; } void merge_sort(a,n) int a[]; {int i,j,k, int b[MAX],tail[MAX]; head=0; k=0; for(i=0;i&n-1;i++) if(a[i]&a[i+1]) tail[k++]=i; tail[k]=n-1; for(j=0;j&=k-1;j++) {merge(a,b,head,tail[j],tail[j+1]); for(i=0;i&tail[j+1];i++) a[i]=b[i]; } }38 数据结构例：如数组存放了一组数为： 24，46，36，42，68，84，22，48，66， 经过排序以后为： 22，24，36，42，46，48，66，68，84，3_7编写一个实现快速排序的非递归的 C 函数。 一．存储结构： 每次调用子函数 quick 后，产生一个 low，up；用结构 S 存储 low 与 up，并 用一个栈存储排序过程中产生的结点 S。 二．算法分析： 快速排序用非递归的方法实现，可以用栈。每次出栈栈顶的 struct S 结点，并把 S-&low 和 S-&up 作为参数调用 quick 函数， quick 函数运行过程中若产生新的 S 结点， 在 则使之入栈。 这样循环直至栈空为止。 三．源程序 #include&stdio.h& #difein M 100 typedef struct stack {}S; S s[M]; int quick(int a[ ],int low,int up) {int i,j; if(low&up) { i= j= t=a[low]; while(i!=j) { while(i&j&&a[j]&t) j--; if(i&j) a[i++]=a[j]; while(i&j&&a[i]&=t) i++; if(i&j) a[j--]=a[i]; } a[i]=t; }39 数据结构return(i); } main() {int n,a[M]; int i,j,f; int l,u; printf(&input the length of the array:&); scanf(&%d&,&n); printf(&input the numbers:\n&); for(j=0;j&n;j++) scanf(&%d&,&a[j]); top=1; s[0].low=0; s[0].up=n-1; while(top&0) {top--; l=s[top]. u=s[top]. f=quick(a,l,u); if(l&f-1) s[top++].up=f-1; if(u&f+1) {s[top].low=f+1; s[top++].up=u; } } for(j=0;j&n;j++) printf(&%4d&,a[j]); } 四．测试用例 输入：数组元素个数：6 数组元素：8 9 5 2 1 6 输出：1 2 5 6 8 93_8对于给定的线性表 A＝〔12，2，16，30，8，28，4，10，20，6，18〕 ，试分别写出用下列排 序方法对 A 进行排序时，每一遍处理后的结果。 存储结构，算法分析，源程序：略 针对不同排序的方法使用不同的存储结构，因为算法分析与源程序书上已详细给出，因 此不重复叙述。40 数据结构输入要求排序的数：12，2，16，30，8，28，4，10，20，6，18 输出： 〔1〕插入排序： 2，12，16，30，8，28，4，10，20，6，18 2，12，16，30，8，28，4，10，20，6，18 2，12，16，30，8，28，4，10，20，6，18 2，8，12，16，30，28，4，10，20，6，18 2，8，12，16，28，30，4，10，20，6，18 2，4，8，12，16，28，30，10，20，6，18 2，4，8，10，12，16，28，30，20，6，18 2，4，8，10，12，16，20，28，30，6，18 2，4，6，8，10，12，16，20，28，30，18 2，4，6，8，10，12，16，18，20，28，30 〔2〕选择排序： 2，12，16，30，8，28，4，10，20，6，18 2，4，16，30，8，28，12，10，20，6，18 2，4，6，30，8，28，12，10，20，16，18 2，4，6，8，30，28，21，10，20，16，18 2，4，6，8，10，28，12，30，20，16，18 2，4，6，8，10，12，28，30，20，16，18 2，4，6，8，10，12，16，30，20，28，18 2，4，6，8，10，12，16，18，20，28，30 2，4，6，8，10，12，16，18，20，28，30 2，4，6，8，10，12，16，18，20，28，30 t=3，d[0]=4，d[1]=3，d[2]=1 8，2，4，10，12，6，16，30，20，28，18 8，2，4，10，12，6，16，18，20，28，30 2，4，6，8，10，12，16，18，20，28，30 2，12，16，8，28，4，10，20，6，18，30 2，12，8，16，4，10，20，6，18，28，30 2，8，12，4，10，16，6，18，20，28，30 2，8，4，10，12，6，16，18，20，28，30 2，4，8，10，6，12，16，18，20，28，30 2，4，8，6，10，12，16，18，20，28，30 2，4，6，8，10，12，16，18，20，28，30 2，12，16，30，8，28，4，10，6，20，18 2，12，16，30，4，8，10，28，6，18，20 2，4，8，10，12，16，28，30，6，18，20 2，4，6，8，10，12，16，18，20，28，30 6，2，10，4，8，12，28，30，20，16，18 4，2，6，10，8，12，28，30，20，16，18〔3〕希尔排序：〔4〕冒泡排序：〔5〕合并排序：〔6〕快速排序：41 数据结构2，4，6，10，8，12，28，30，20，16，18 2，4，6，8，10，12，28，30，20，16，18 2，4，6，8，10，12，18，16，20，28，30 2，4，6，8，10，12，16，18，20，28，30 〔7〕基数排序： 30，10，20，12，2，4，16，6，8，28，18 2，4，6，8，10，12，16，18，20，28，304_3将 n 阶三对角阵（即半带宽为 1 的带状矩阵）A 按行序列序存放在一维数组 b[3*n-2]中。若 aij(|i-j|&=1)存放在 b[k]中，请求出求解 k 的计算公式。 解： 在数组 b 中，此带状矩阵按如下方式存贮：除头一行和最后一行外，每一行都有三个元素， 将带状矩阵存储在 3n-2 个存储单元中。由分析知： &a[i][i]=&a[i-1][i-1]+3*s 可得 &a[i][i]=&a[0][0]+i*3*s &a[i][j]=&a[i][i]+(j-i)*s=&a[0][0]+[3i +(j-i)]*s (1) 若 aij 存放在 b[k]中， &b[k]=&b[0]+k*s (2) 又因为 &a[i][j]=&b[k] &a[0][0]==&b[0] 由(1)(2)式得 k=3i +(j-i)=2i+j 故 k=2i+j.4_4广义的带状矩阵 Anab 是在 n 阶方阵中只考虑最长主对角线下面的(a-1)条主对角线和最长主对 角线上面的（b-1）条主对角线及最长主对角线组成的带状区域。如果把广义的 Anab 按行序列序存放在一维数组 b[(a+b-1)*n-(a+b-2)]中，元素 aij 存放在 b[k]中，那么请写出计算 k 的计算公式。 解： 在数组 b 中，除头一行和最后一行外，每行都当作有(a+b-1)个元素，增补后即有下式成立 &a[i][i]=&a[i-1][i-1]+(a+b-1)*s 可得 &a[i][i]=&a[0][0]+i*( a+b-1)*s &a[i][j]=&a[i][i]+(j-i)*s=&a[0][0]+[i*( a+b-1)+(j-i)]*s (4) 若 aij 存放在 b[k]中， &b[k]=&b[0]+k*s (5) 又因为 &a[i][j]=&b[k] &a[0][0]==&b[0] 由(4)(5)式得 k=i*( a+b-1)+(j-i)4_5如果用三元组数组表示稀疏矩阵 A 和 B 试编写一个求解 A+B 的 C 函数(要求仍然用三元组数组 表示 A+B)42 数据结构[存储结构] 三元组数组 a[MAXN][3],b[MAXN][3],C[MAXN][3]分别用以存放稀疏矩阵 A,B,A+B [解题思路] (1) 判断 A 和 B 的行数,列数是否相等.若两者之中有一项不等,A+B 失败,返回 1;否则,转(2); (2) a[MAXN][3]和 b[MAXN][3]中的行号、列号都相等且相加不等于零的相应元素,将它们的 和存入 c[MAXN][3]; (3) a[MAXN][3]和 b[MAXN][3]中的行号相等,列号不等的元素,把两者之中列号较大的存入 c[MAXN][3]; (4) a[MAXN][3] 和 b[MAXN][3] 中 的 行 号 不 等 的 元 素 , 把 两 者 之 中 行 号 较 大 的 存 入 c[MAXN][3]; (5) 依照(2)(3)(4)的规则处理 a[MAXN][3]和 b[MAXN][3]中的元素,直到 a[MAXN][3]和 b[MAXN][3]的所有元素处理完.算法结束,返回 0. [c 程序] #define MAXN 20 int add_mat(int a[][3],int b[][3]) {int i=1,j=1,k=1; int c[MAXN][3]; if(a[0][0]!=b[0][0]||a[0][1]!=b[0][1]) return(1); c[0][0]=a[0][0]; c[0][1]=a[0][1]; c[0][2]=0; while(i&=a[0][2]&&j&=b[0][2]) if(a[i][0]==b[j][0]) if(a[i][1]==b[j][1]) if(a[i][2]+b[j][2]!=0) {c[k][0]=a[i][0]; c[k][1]=a[i][1]; c[k++][2]=a[i++][2]+b[j++][2]; c[0][2]+=1;} else {i++; j++;} else if(a[i][1]&b[j][1]) {c[k][0]=a[i][0]; c[k][1]=a[i][1]; c[k++][2]=a[i++][2]; c[0][2]+=1; } else {c[k][0]=b[j][0]; c[k][1]=b[j][1]; c[k++][2]=b[j++][2]; c[0][2]+=1; } else if(a[i][0]&b[j][0]) {c[k][0]=a[i][0]; c[k][1]=a[i][1]; c[k++][2]=a[i++][2]; c[0][2]+=1;} else {c[k][0]=b[j][0];43 数据结构c[k][1]=b[j][1]; c[k++][2]=b[j++][2]; c[0][2]+=1; while(i&=a[0][2]) {c[k][0]=a[i][0];c[k][1]=a[i][1];c[k++][2]=a[i++][2];c[0][2]+=1;} while(j&=b[0][2]) {c[k][0]=b[j][0];c[k][1]=b[j][1];c[k++][2]=b[j++][2];c[0][2]+=1;} for(i=0;i&=c[0][2];i++) printf(&%d %d %d\t&,c[i][0],c[i][1],c[i][2]); return(0); } [测试用例] A:a[MAXN][3]={{5,4,7},{0,0,12},{0,1,15},{2,0,36},{2,1,46},{2,3,52},{3,1,72}, {3,3,68}}; B:b[MAXN][3]={{5,4,6},{0,0,10},{1,1,20},{2,0,-36},{2,3,13},{3,3,4 },{4,1,15}}; A+B:c[MAXN][3]={{5,4,8},{0,0,22},{0,1,15},{1,1,20},{2,1,46},{2,3, 65},{3,1,72},{3,3,72},{4,1,15}}4_6假设 A 是用十字链表表示的稀疏矩阵,试编写一个将 A 转置的 C 函数.(要求仍然用十字链表表 示 A 的转置矩阵) [存储结构] 十字链表 NODE 表示 A: struct node{int row,col, struct node *right,*}; typedef struct node NODE; [解题思路] (1) 将原十字链表 A 中头指针 h 所指的结点的 row,col,val 存放在 A 的转置矩阵的头指针 h1 所指结点的 col,row,val 字段,并根据其各行(列)链表的表头结点; (2) 找到 A 各列结点,指针 p 指向其表头结点,以指针 q 指向该列各个结点,据指针 q 的 row,col 字段,把该结点插在 A 的转置矩阵的行号为 col,列号为 row 的相应位置.直到 A 中结 点全部插在其转置矩阵中. [c 程序] #include&stdio.h& typedef struct node{int row,col, struct node *right,*}NODE; NODE *search_row_last(NODE *a,int i) {NODE *p,*h; p=a; for(k=0;k&=i;k++) p=p-&44 数据结构h=p; while(p-&right!=h) p=p-& return(p);} NODE *search_col_last(NODE *a,int j) {NODE *p,*h; p=a; for(k=0;k&=j;k++) p=p-& h=p; while(p-&down!=h) p=p-& return(p);} NODE *convert(NODE *h) {NODE *h1,*p1,*q1,*p,*q,*r; h1=(NODE*)malloc(sizeof(NODE)); h1-&row=h-& h1-&col=h-& h1-&val=h-& h1-&right=h1; h1-&down=h1; p1=h1; for(k=0;k&h1-&k++) {q1=(NODE*)malloc(sizeof(NODE)); q1-&col=1000;q1-&right=q1;q1-&down=p1-& p1-&down=q1; p1=q1;} p1=h1; for(k=0;k&h1-&k++) {q1=(NODE*)malloc(sizeof(NODE)); q1-&row=1000;q1-&down=q1;q1-&right=p1-& p1-&right=q1; p1=q1;} for(p=h-&p!=h;p=p-&right) {for(q=p-&q!=p;q=q-&down) {r=(NODE*)malloc(sizeof(NODE)); r-&row=q-&r-&col=q-&r-&val=q-& p1=search_row_last(h1,r-&row); q1=search_col_last(h1,r-&col); r-&right=p1-& p1-&right=r; r-&down=q1-& q1-&down=r;} } return(h1);}5_1图题 5-1 是一棵结点值为字符的三次树。如果按前序、后序和层次序分别对该树进行遍历，那45 数据结构么请分别给出遍历后的结点序列。 ABCDEFGJMHIK 图题 5-1LNOPQ[解] 前序遍历：ABEFHIGCJKLDMNOQP 后序遍历：EHIFGBKLJCNQOPMDA 层次遍历：ABCDEFGJMHIKLNOPQ5_2试叙述将 m 棵有序树组成的有序树林转换成相应的二叉树的逆变换。已知图题 5-2 的二叉树 是由某 m 棵有序树林转换而来的。请使用你所给出的逆变换画出该二叉树所对应的树林。 [解] 临时结点 B0 临时结点 A0 * * ---------------------------------------------------------------------------------------------------------------------A B C B D E 图题 5-2 F G D 转换后的树林 E F A C G假设β （T）是已知的二叉树。我们为它设置一个临时的父结点 B0，使 T2 作为 B0 的左 子树，而右子树置空。同时，我们为要转换成的树林 T=（T0，T1，??Tm）也设置一个临时 的父结点 A0，使 T0，T1，??Tm 分别作为它的 m 个儿子。 变换的方法如下： 令 A=A0，B=B0.L=B-&lchild,R0=L-&rchild。 如果 Ri!=NULL,Ri+1=Ri-&rchild(I=0,1,…m-3);否则，Ri+1=NULL. 按下面方法构造结点 A： 如 果 L==NULL ， A-&child[0]=NULL; 否 则 ， A-&child[0]-&data=L-&data ， 并 令 A0=child[0],B0=L,重复上述变换过程。46 数据结构┊ 如 果 Ri==NULL ， A-&child[I+1]=NULL; 否 则 ， A-&child[I+1]-&data=Ri-&data ， 并 令 A0=A-&child[I+1],B0=Ri,重复上述变换过程。 ┊ 如果 Rm-2==NULL，A-&child[m-1]=NULL;否则，A-&child[m-1]-&data=Rm-2-&data，并令 A0=A-&child[m-1],B0=Rm-2,重复上述变换过程。 显然，这是一个递归的过程。经过变换，我们得到的 m 次树的根结点 A0 的 m 个儿子即 是所要求的树林。 运用上述变换方法，可将图题 5-2 的二叉树转换成右图的树林。5_3假设二叉树 T 是按标准形式存储的， 试编写一个把该树中每个结点的左右子结点进行对换的 C 函数。 存储结构： #include&stdio.h& typedef struct node{ struct node *lchild, }NODE; 算法： 将根结点的左右子结点对换，然后对根结点的左右子树进行递归调用。为了检验是否正确对 对换前后的树进行后序遍历。 程序：#include&stdio.h& typedef struct node{ struct node *lchild,* }NODE; NODE *settree(a,b,m,n) char a[],b[]; int m,n; {NODE *t; int i,j; if(m&n)return(NULL); t=(NODE *)malloc(sizeof(NODE)); t-&data=b[n]; for(i=m;a[i]!=b[n];i++); for(j=n-1;j&=i;j--)b[j+1]=b[j]; t-&lchild=settree(a,b,m,i-1); t-&rchild=settree(a,b,i+1,n); return(t); } void tradetree(t) NODE *t;47 数据结构{NODE *p; if(t==NULL) p=t-& t-&lchild=t-& t-&rchild=p; tradetree(t-&lchild); tradetree(t-&rchild); } void s_posorder(t) NODE *t; {NODE *s[100];int s1[100]; int top,i; if(t==NULL) s[0]=t;s1[0]=0;top=1; while(top&0) {t=s[--top]; i=s1[top]; if(i==2)printf(&%c&,t-&data); else if(i==0) {while(t-&lchild!=NULL){t=t-& s1[top]=1; s[++top]=t; s1[top]=0; } if(t-&rchild==NULL)printf(&%c&,t-&data); else ++ } else{s1[top]=2;++ t=t-& if(t!=NULL) {if(t-&lchild==NULL&&t-&rchild==NULL)printf(&%c&,t-&data); else{s[top]=t;s1[top++]=0;} } } } } main() {char a[100],b[100]; NODE *t; printf(&input midorder:\n&); scanf(&%s&,a); printf(&input posorder:\n&); scanf(&%s&,b);48 数据结构for(i=0;a[i]!='\0';i++); t=settree(a,b,0,i-1); s_posorder(t); tradetree(t); printf(&\n&); s_posorder(t); } 测试用例：输入 BAC BCA 输出：BCA CBA5_4编写一个利用栈来实现后序遍历一棵给定的二叉树的 C 函数。 存储结构：#include&stdio.h& typedef struct node{ struct node *lchild, }NODE; 算法：叶结点直接输出不压栈，非叶结点需要压栈，输出后向上回溯，应判别是从左边回上 去还是从右边回上去。 程序： #include&stdio.h& typedef struct node{ struct node *lchild,* }NODE; NODE *settree(a,b,m,n) char a[],b[]; int m,n; {NODE *t; int i,j; if(m&n)return(NULL); t=(NODE *)malloc(sizeof(NODE)); t-&data=b[n]; for(i=m;a[i]!=b[n];i++); for(j=n-1;j&=i;j--)b[j+1]=b[j]; t-&lchild=settree(a,b,m,i-1); t-&rchild=settree(a,b,i+1,n); return(t); } void tradetree(t) NODE *t; {NODE *p; if(t==NULL)49 数据结构p=t-& t-&lchild=t-& t-&rchild=p; tradetree(t-&lchild); tradetree(t-&rchild); } void s_posorder(t) NODE *t; {NODE *s[100];int s1[100]; int top,i; if(t==NULL) s[0]=t;s1[0]=0;top=1; while(top&0) {t=s[--top]; i=s1[top]; if(i==2)printf(&%c&,t-&data); else if(i==0) {while(t-&lchild!=NULL){t=t-& s1[top]=1; s[++top]=t; s1[top]=0; } if(t-&rchild==NULL)printf(&%c&,t-&data); else ++ } else{s1[top]=2;++ t=t-& if(t!=NULL) {if(t-&lchild==NULL&&t-&rchild==NULL)printf(&%c&,t-&data); else{s[top]=t;s1[top++]=0;} } } } } main() {char a[100],b[100]; NODE *t; printf(&input midorder:\n&); scanf(&%s&,a); printf(&input posorder:\n&); scanf(&%s&,b); for(i=0;a[i]!='\0';i++); t=settree(a,b,0,i-1);50 数据结构s_posorder(t); tradetree(t); printf(&\n&); s_posorder(t); } 测试用例： 输入：BAC BCA 输出：BCA5_5一． 题目： 如果 T 是一颗有序树，T?是与 T 相对应的二叉树。假定 T?已按标准形式被存贮，试为下 面各小题分别编写一个 C 函数： （1） 按前序输出 T 的结点值。 （2） 按后序输出 T 的结点值。 （3） 输出树 T 的叶子结点值。 （4） 求出树 T 的次数。二． 算法分析：本题主要应弄清楚 T 与 T?之间的关系。设 t 表示二叉树 T?的根结点，则 t-&lchild（如果 非空）为原先 T 的第一个子结点，而 t-&rchild，t-&rchild-&rchild, …（如果非空）则表示 T 的 第二、三??个子结点。 1． 按前序输出 T 的结点值： (1) 如果 t 为空，则直接返回； (2) 访问结点 t； (3) 如果 t 存在子结点，则访问 t 的第一个子结点（即 t-&lchild） ，再访问其它子结点 （即 t-&rchild，t-&rchild-&rchild, …） 。 2． 按后序输出 T 的结点值（方法类似 1） 3． 访问树 T 的叶子结点： 只需在遍历时增加是否为叶子结点的判断即可。 4． 求树 T 的次数： （1） 如果 t 为空，返回次数 0。 （2） 统计 t 的子结点数，记为 degree；同时求出各子树的次数的最大值，记为 subDegree； （3） 取 degree 与 subDegree 中较大的一个并返回。 三． 程序如下： struct NODE { NODE *lchild,* };51 数据结构void PreScan(NODE *t) /* 按前序输出 T 的结点值*/ { if(t==NULL) printf(“%d\t”,t-&data); if((t=t-&lchild)!=NULL){ PreScan(t); while((t=t-&rchild)!=NULL) PreScan(t); } } void PostScan(NODE *t) /*按后序输出 T 的结点值*/ { NODE *p; if(t==NULL) if((p=t-&lchild)!=NULL){ PostScan(p); while((p=p-&rchild)!=NULL) PostScan(p); } printf(“%d\t”,t-&data); } void LeafScan(NODE *t) /*输出树 T 的叶子结点值*/ { if(t==NULL) if(t-&lchild==NULL)/*is leaf*/ printf(“%d\t”,t-&data); else{ LeafScan(t=t-&lchild); while((t=t-&rchild)!=NULL) LeafScan(t); } } int GetDegree(NODE *t) /*得到树 T 的次数*/ { int degree=0,subDegree,d; NODE *p; if(t==NULL) return 0; if((t=t-&lchild)!=NULL){52 数据结构degree++; subDegree=GetDegree(t); for(p=t;(p=p-&rchild)!=NULL;){ degree++; d=GetDegree(p); if(subDegree&d) subDegree=d; } if(degree&subDegree) degree=subD } }5_6一.题目： 假设二叉树 T 的结点值是字符，已知树 T 中结点的前序和中序，试编写一个把树 T 按标 准形式进行存贮的 C 函数。 二.算法分析： 设前序遍历和中序遍历的结果在数组 pre[] 和 mid[]中，显然，pre[]中第一个元素（设为 data）即为根结点，而在 mid[]中，data 左右的元素分别是左子树和右子树中的元素。 （1） 当数组中元素个数 n 为非正数时，返回空。 （2） 以 pre[0]为数据生成根结点 roof，并找出它在 mid 数组中的位置 posi。 （3） pre[1]或 mid[0] 开始的 posi 个数据在左子树中， pre[1+posi]或 mid[posi+1] 开始的 posi 个数据在左子树中，分别转（1）构造左右子树（递归）,并返回根结点 roof。 三.程序如下： { NODE *lchild,* }; NODE *Create(char pre[],char mid[],int n) { NODE * if(n&=0) return NULL; roof=(NODE*)malloc(sizeof(NODE)); data=pre[0]; roof-&data= for(posi=0;posi&n&&mid[posi]!=posi++); roof-&lchild=Create(pre+1,mid,posi); roof-&rchild=Create(pre+1+posi,mid+posi+1,n-1-posi); }53 数据结构5_7递归算法： 数据结构 typedef struct node { struct node * struct node * }NODE; int pre[MAX],ind[MAX],aft[MAX]; int count_p=0,count_m=0,count_a=0; 算法分析： 通过递归把两数组分为头接点，左子树，右子数三部分； 后序序列和中序序列分别放在数组 aft[1,n]和 ind[1,n]中； NODE *bintree2(i,j,u,v) //I 后序的起始点,j 后序的终点,u 中序的起始点,v 中序的终点； int i,j,u,v; { int k,l; NODE *head,*s; head=NULL; if (j&=i) { head=(NODE *)malloc(sizeof(NODE )); head-&data=aft[j]; //生成头接点 k=u; while(ind[k]!=aft[j])k++;//找到当前头接点在中序中的位置 l=j+k-v; //右子树中最左边的接点在中序中的位置 if(k==u) //头接点等于中序的起始位置 head-&lchild=NULL; else { s=bintree2(i,l-1,u,k-1);//处理左子树部分 head-&lchild=s; } if (k==v)head-&rchild=NULL;//同理 else { s=bintree2(l,j-1,k+1,v);//同理 head-&rchild=s; } } return(head); }54 数据结构5_8int is_cdtree(t) NODE *t; { int flag=0; if (t==NULL) return(1); if (!((t-&lchild==NULL&&t-&rchild!=NULL)||(t-&lchild!=NULL&&t-&rchild==NULL))) // flag=1; return(flag&&is_cdtree(t-&lchild)&&is_cdtree(t-&rchild)); }5_91. 存贮方式: Typedef struct node { struct node * struct node * }NODE; 2. 存储结构: 本题采用递归,并用 1 代表真 0 代表假 3. 源程序 int islikebi(NODE *head1,NODE *head2) { NODE *p=head1; NODE *q=head2; int l=0,r=0; if(p==NULL&&q==NULL) return 1; if(p!=NULL&&q!=NULL) { l=islikebi(p-&lchild,q-&lchild); r=islikebi(p-&rchild,q-&rchild); return l*r; } return 0; } 4. 测试用例:经过测试(输入两棵树) 结果正确.5_101. 存贮结构:采用附带一个标志位和一个右指针来线形存储一棵树.55 数据结构2. 存储方式:用左标志直接找左孩子,用右指针找右孩子,程序用递归. Typedef struct node { struct node * struct node * }NODE; 3. 源程序 用 t 数组存放线形的树表示. NODE *creat(int i) { NODE *head=(NODE *)malloc(sizeof(NODE)); if(t[i].data==0) return NULL; else { head-&data=t[i]. if(t[i].ltag==0) head-&lchild=creat(i+1); else head-&lchild=NULL; if(t[i].rchild!=-1) head-&rchild=creat(t[i].rchild); else head-&rchild=NULL; } } 4. 测试用例:输入一组线形树,能够形成一棵标准存储的二叉树5_11假设二叉树 T 已按前序附加两个标志位的顺序存贮方法存放，且 a 是 T 中一个结点的值，试 编写一个寻找结点 a 的父结点的 C 函数。 分析：可按如下规律寻找结点 a 的父结点，假设二叉树由数组 p 给出，且 p[i]=结点 a （1） 若 p[i-1]的 ltag 为 0，则 p[i]是 p[i-1]的左孩子，p[i-1]即为 a 的父亲 （2） 若 p[i-1]的 ltag 为 1，而 rtag 为 0，则 p[i]是 p[i-1]的右孩子，p[i-1]即 为 a 的父亲 （3） 若 p[i-1]的 ltag 和 rtag 均为 1，则查找 p[i]之前的所有结点，并把 ltag 和 rtag 均为 0 的结点入栈， 同时计算满足 “前一个结点 ltag 和 rtag 均为 1” 这样条件的结点， 其个数记为 count， 出栈 count 次后的栈顶结点即为 a 的父 亲 程序 #include&stdio.h& typedef struct node{56 数据结构int ltag, }LRNODE; char find(LRNODE p[],int n,char a) {int i,j,top=0,count=0; char c[100]; for(i=0;i&n;i++) if(p[i].data==a) if(i==0||i==n){printf(¬ found!error!\n&); return('@');} if((p[i-1].ltag==0)||(p[i-1].ltag==1&&p[i-1].rtag==0)) return(p[i-1].data); for(j=0;j&i;j++) {if(p[j].ltag==0&&p[j].rtag==0) c[top++]=p[j]. if(p[j].ltag==1&&p[j].rtag==1&&j&i-1) count++; } i=top-count-1; return(c[i]); } void main() {LRNODE p[9]; for(i=0;i&9;i++) scanf(&%d%c%d&,&p[i].ltag,&p[i].data,&p[i].rtag); ch=find(p,9,'C'); printf(&%c\n&,ch); } 测试样例： 输入：(即为书 p.136 图 5.9.1 所示二叉树) 0A0 0B0 1D1 0E0 1G1 1H1 1C0 0F1 1I1 输出： A57 数据结构5_12假设二叉树 T 是一棵穿线树，试编写一个按前序遍历树 T 的 C 函数。 （不允许用递归程序，也 不允许使用数组，只允许增加个别变量） 分析：基本思想是在遍历时若结点有左孩子则尽量往左走，走到最左时利用穿线往右走一步， 若为右孩子则继续上述过程，若为其中序遍历的后一个结点则再往右一步后继续上述过程。 程序（程序中用穿线排序的方法产生一棵穿线树，preorder 为前序遍历的 C 函数） #include&stdio.h& typedef struct node{ struct node *lchild,* int ltag, }NODE; NODE* thread_sort_tree(a,n) char a[]; {NODE *root,*p,*r; if(n==0) return(NULL); root=(NODE*)malloc(sizeof(NODE)); root-&data=a[0]; root-&lchild=NULL; root-&rchild=NULL; root-<ag=0; root-<ag=0; for(i=1;i&n;i++) {r=(NODE*)malloc(sizeof(NODE)); r-&data=a[i]; p= while(1) {if(r-&data&=p-&data) if(p-<ag==0&&p-&lchild!=NULL) p=p-& else if(p-&rtag==0&&p-&rchild!=NULL) p=p-& } if(r-&data&p-&data) {r-&lchild=p-& r-<ag=p-& r-&rchild=p; r-&rtag=1;58 数据结构p-&lchild=r; p-<ag=0; } else if(r-&data&p-&data) {r-&rchild=p-& r-&rtag=p-& r-&lchild=p; r-<ag=1; p-&rchild=r; p-&rtag=0; } } return(root); } void preorder(root) NODE * {NODE *p,*q; p= while(p!=NULL) {if(p-<ag==0&&p-&lchild!=NULL) {q=p-& printf(&%c &,p-&data); p=q; } else {q=p-& printf(&%c &,p-&data); if(p-&rtag==0) p=q; else p=q-& } } } void main() {char a[8]={'E','B','H','C','F','A','D','G'}; NODE * root=thread_sort_tree(a,8); preorder(root); printf(&\n&); } 测试样例： 穿线树已在函数中初始化，不需输入（即为书 p.139 图 5.9.3 所示的穿线树） 输出为：59 数据结构EBACDHFG6_1假设结点序列 F=(60,30,90,50,120,70,40,80)，试用查找树的插入算法，用 F 中的结点依次 进行插入，画出由 F 中结点所构成的查找树 t1，再用查找树的删除算法，从查找树 t1 中依次 删除 40，70，60，画出删除后的查找树。 解答： 至于查找树的插入和删除算法在书中的第 6.1 节已明确给出，这里就不再赘述。 查找树的结点插入时，先查找该结点若以存在，则插入失败并返回；否则进行插入。插入时 先和根结点比较若比它大则往右边走，继续比较；否则往左边走，继续比较。直到遇到空指 针则该结点插入的位置即为该指针的位置。由上所述，每次结点都是插入后都成为树的叶结 点。给出树 t1 如下： 60 L K 30 90 K L K 50 70 120 L K 40 80 查找树删除算法的原理书上 P149 页有详细的分析。删除 40，70，60 后的树如下所示： 30 K 50 K 90 L K 80 126_2已知 F=(a0,a1,?,an-1)是一个已排序的整数结点序列，试编写一个用平分法构造出由 F 中结点所构成的丰满查找树的 C 函数。 解答： 很容易联想到用递归来解决这个问题。用函数 NODE *creat_tree(int a[],int m,int n) 来实现。每次调用时序列中间的一个数即为树根返回，m 指 a 数组开始的下标号，n 指 a 数组 结束的下标号，中间指用(m+n)/2 得到。具体实现的 C 函数如下：(这里假定用户输入的 F 数 组已由小到大按升序排好列了) #include&stdio.h& struct node { struct node * struct node * }; typedef struct node NODE;60 数据结构NODE * creat_tree(int a[],int m,int n) { NODE *t; if(n-m&0)return(NULL); k=(m+n)/2; t=(NODE *)malloc(sizeof(NODE)); t-&data=a[k]; t-&llink=creat_tree(a,m,k-1); t-&rlink=creat_tree(a,k+1,n); return(t); } void suc_order(NODE *t) { if(t!=NULL){ suc_order(t-&llink); suc_order(t-&rlink); printf(&%d &,t-&data);} } void mid_order(NODE *t) { if(t!=NULL){ mid_order(t-&llink); printf(&%d &,t-&data); mid_order(t-&rlink); } } main() { int n,i; int a[100]; NODE * printf(&\nInput the size of the array:\n&); scanf(&%d&,&n); getchar(); for(i=0;i&n;i++){ printf(&Input data %d:\n&,i+1); scanf(&%d&,&a[i]); } head=creat_tree(a,0,n-1); suc_order(head); printf(&\n&); mid_order(head); } 程序中用到了书中介绍的二叉树的后序和中序遍历是为了检查 creat_tree 函数的正确性而设 的，因为二叉树的后序和中序遍历能唯一确定一棵树，故我们在输入数组，建立了想要得到 的二叉树后可人工的写出它的后序和中序遍历并和程序输出的进行比较，若相同则说明 creat_tree 函数创建的正是题目所要求的查找树。 例如：61 数据结构输入已排好序的数组 30，40，50，60，70，80，90，120 人为的我们知道这样的一个数组用平分法能构成如下查找树： 60 L K 40 80 L K L K 30 50 70 90 K 120 程序输出该查找树的后序遍历为：30 50 40 70 120 90 80 60 中序遍历为：30 40 50 60 70 80 90 120 可知道程序创建的查找树即为上图所示的查找树，故程序正确。6_5编写一个判断给定二叉树 T 是否为平衡树的 C 函数。 解答： 一：存储结构 二叉树以一个 struct node 的形式存储，data 域存储结点的数据（char 类型） ，left、 right 域为二叉树中指向左右孩子的指针。二：具体实现 函数 creat 用来创建一个二叉树，首先输入数据元素，在输入节点类型，l 代表只有左孩子， r 代表只有右孩子，b 代表有两个孩子，e 代表没有孩子（叶子结点） ，函数 r_preorder 用来 进行前序遍历，便于测试，函数 is_batree 用来测试是否为平衡树，是即返回非 0，否则返回 0，该函数以递归实现。首先判断是否为空（递归跳出条件） ，然后看本结点的左、右子树是 否为平衡树，若是，则再看本结点是否符合平衡树的条件，若是，则返回本结点的深度。否 则，一律返回 0。三：源程序#include&stdio.h& struct node { struct node *left,* }; typedef struct node NODE; void creat(NODE *root) { printf(&\nPlease input the data!:\n&);62 数据结构getchar(); scanf(&%c&,&(root-&data)); getchar(); printf(&\nPlease input the type of the node:(l\\r\\b\\e)&); scanf(&%c&,&type); switch(type) {case 'l':root-&left=(NODE*)malloc(sizeof(NODE)); printf(&\nPlease input the left child:\n&); creat(root-&left);root-&right=NULL; case 'r':root-&right=(NODE*)malloc(sizeof(NODE)); printf(&\nPlease input the right child:\n&); creat(root-&right);root-&left=NULL; case 'e':root-&left=NULL;root-&right=NULL; case 'b':root-&left=(NODE*)malloc(sizeof(NODE)); printf(&\nPlease input the left child:\n&); creat(root-&left); root-&right=(NODE*)malloc(sizeof(NODE)); printf(&\nPlease input the right child:\n&); creat(root-&right); } } void r_preorder(NODE *t) {if(t!=NULL) {printf(& %c &,t-&data); r_preorder(t-&left); r_preorder(t-&right); } } int is_batree(NODE *root) {int da,db, if(!root) return(1); if(!((da=is_batree(root-&left))&&(db=is_batree(root-&right)))) return(0); dc=da&db? da-db:db- if(dc&1) return(0); return(da&db?da+1:db+1); }63 数据结构main() { NODE* printf(&\nAn empty tree?(y|n)\n&); scanf(&%c&,&ch); if(ch=='n') {printf(&\nPlease input the root node!\n&); root=(NODE*)malloc(sizeof(NODE)); creat(root); r_preorder(root); printf(&\nIt is &); if(!(is_batree(root))) printf(¬ &); printf(&a balance tree!&); } }四：测试结果 输入：结点类型 结点值 b a l b e c r d e e 输出：It is a balance tree!输入：结点类型 结点值 b a b b r c e d e e r f e g 输出：It is a balance tree!输入：结点类型 结点值 b b ra b c64 数据结构e e r l ed e f gh 输出：It is a not balance tree!输入：结点类型 结点值 b b r e b e e 输出：It is a not balancea b c d e f g tree!6_6试画出 Adelson 插入方法的右改组的转换图。 解答：右改组的画法与左改组的画法类似，如下图：65 数据结构ki ki A1t ki+2 A2t A3t+1 A3t-1 (a)新 结 点插 A3t+1中 在 A4t ki+1 A2tA1tki+1（b） 新 结 点插 A4t中 在kikiA1t ki+2 A3tki+1 A2t ki+2 A4t-1ki+1（c） 新 结 点插 A3t中 在（d） 新 结 点ki+2插 ki+1的 左边 在6_9给定结点 k0,k1,k2,k3,k4 的键值分别为 10，30，50，70，90，相对使用概率为 5，6，3， 4，7。 （1） 构造阶段中结点序列的变化情况： k0 k1 k2 k3 k4 ?6 ? 5 ?? ??? 3 ?7 ?? ?4 ?? k0 b1 k3 k4 ?5 ?? ?9 ?? ?7 ?? ?4 ?? k0 b1 b2 ?11 ? 9 ? 5 ?? b3 b2 ?11 ? 41 ?? b4 ?52 ?? （2） 构造阶段产生的树 b4?52 ??66 数据结构b3?41 ?? b2?11 ?? k0?5 ?? b1?9 ?? k3? 7 ??k4?4 ?? k1? 6 ??k2?3 ?? （3） 建造阶段结点序列的变化情况 k0 k1 k2 k3 k4 2??? 3??? 3??? 2??? 2??? k0 c1 k3 k4 2??? 2??? 2??? 2??? c2 k3 k4 1??? 2??? 2??? c2 c3 1??? 1??? c4 0??? （4） 建造阶段产生的树 0? ??c4 1? ??c2 1? ??c3 2? ??k0 2? ??c1 2? ??k3 2? ??k4 3? ??k1 3? ??k2 即为所求树。6_10（1）插入 200 100 200 100 200 250 100 150 200 250 150 100 120 200 250 150 100 110 120 200 250 150 200 220 250 100 110 120 15067 数据结构100 110 120 200 205 220 250150 210220 250 200 205 100 110 120150 210 200 205 90 100 110 120 220 250150 220 160 90210 250 200 205 100 110 120100 150 21080 110 160 22090 120 200 205 250100 150 210 80 90 160 170 200 205 220 25068 数据结构110 120100 150 200 210 160 110 80 202 220 170 120 90 205 250100 150 200 21080 110 160 202 22090 120 170 205 225 250100 150 200 21080 110 160 202 220 20090 120 170 205 225 240 250100 150 210 24080 160 202 245 11090 170 205 250 12069 数据结构220 225（2）删除 202 100 150 200 240 245 250 80 90 205 210 220 225 110 120 160 170100 160 205 240 （3）删除 150 170 200 245 250 80 90 210 220 225 110 120 （4）删除 200 100 160 210 240 245 250 80 110 170 220 90 120 205 2256_12算法分析： 在原来的寻找一个方法是用到的是一个 maxn*maxn 的栈，这样的话浪费了很大的空间不利 于处理棋局比较大的情况。这里用的是 maxn 的一个栈，这样的话机不能把每一行都压栈，这 里只能选者有用的节点压栈。其他的处理也是用得回朔的方法。 不同：1 节点进入时标准有所不同； 2 找到一种方法以后还要继续回朔，直到 所有的路径都被找完。 部分源程序： Int queens(n)70 数据结构 { NODE stack[MAXN]; int row[MAXN],col[MAXN],md[2*MAXN-1],sd[2*MAXN-1]; int str,stc,i; int is_First=1; int answer=0; top=0; str=-1; stc=-1; begain: for(i=0;i&n;i++) { row[i]=0; col[i]=0; } for(i=0;i&2*n-1;i++) { md[i]=0; sd[i]=0; } stack[0].tag=0; while (top&=0) { if (str&=n-1) if (stc&n-1) { stc++; if (is_First) { str++; is_First=0; } } else { stc=0; str++; } stack[top].r= stack[top].c= if (stack[top].tag==0&&(str==0||row[str-1])) 节点进入时标准有所不同；71 数据结构if (row[str]||col[stc]||md[str-stc+n-1]||sd[str+stc]) { stack[top].tag=0; } else { row[str]=1; col[stc]=1; md[str-stc+n-1]=1; sd[str+stc]=1; stack[top].tag=1; if (str==n-1) { answer++; printf (&%d solution is\n&,answer); for(i=0;i&=i++) if (stack[i].tag) printf (&%4d%3d;&,stack[i].r,stack[i].c); printf (&\n&); top++; /*critical*/ 找到一种方法以后还要继续回朔，直到 所有的路径都被找完。 } else stack[++top].tag=0; } else { loop: str=stack[--top].r; stc=stack[top].c; row[str]=0; col[stc]=0; md[str-stc+n-1]=0; sd[str+stc]=0; if (stc==n-1) stack[top].tag=0; } } return(answer); } 数据测试： 输入：472 数据结构输出 1 solution is 1: 0 1; 2: 2 solution is 1: 0 2; 2: 输入：5 输出： 1 solution is 1: 0 0; 2: 2 solution is 1: 0 0; 2: 3 solution is 1: 0 1; 2: 4 solution is 1: 0 1; 2: 5 solution is 1: 0 2; 2: 6 solution is 1: 0 2; 2: 7 solution is 1: 0 3; 2: 8 solution is 1: 0 3; 2: 9 solution is 1: 0 4; 2: 10 solution is 1: 0 4; 2: 输入：7 输出 1 solution is 1: 0 0; 6: 5 3; 2 solution is 1: 0 0; 6: 5 1; 3 solution is 1: 0 0; 6: 5 6; 4 solution is 1: 0 0; 6: 5 4; 5 solution is 1: 0 1;1 13; 0;3: 2 3: 20; 4: 3 3; 4: 32; 1;1 1 1 1 1 1 1 1 1 12; 3; 3; 4; 0; 4; 0; 1; 1; 2;3: 2 3: 2 3: 2 3: 2 3: 2 3: 2 3: 2 3: 2 3: 2 3: 24; 4: 3 1; 4: 3 0; 4: 3 2; 4: 3 3; 4: 3 1; 4: 3 2; 4: 3 4; 4: 3 3; 4: 3 0; 4: 31; 5: 4 4; 5: 4 2; 5: 4 0; 5: 4 1; 5: 4 3; 5: 4 4; 5: 4 2; 5: 4 0; 5: 4 3; 5: 43; 2; 4; 3; 4; 0; 1; 0; 2; 1;2: 1 7: 6 2: 1 7: 6 2: 1 7: 6 2: 1 7: 6 2: 12; 5; 3; 4; 4; 3; 5; 2; 3;3: 24; 4: 36; 5: 41;3: 26; 4: 32; 5: 45;3: 21; 4: 35; 5: 42;3: 23; 4: 31; 5: 46;3: 20; 4: 36; 5: 44;73 数据结构6: 5 2; 7: 6 solution is 1: 0 1; 2: 6: 5 4; 7: 7 solution is 1: 0 1; 2: 6: 5 2; 7: 8 solution is 1: 0 1; 2: 6: 5 3; 7: 9 solution is 1: 0 1; 2: 6: 5 2; 7: 10 solution is 1: 0 1; 2: 6: 5 0; 7: 11 solution is 1: 0 1; 2: 6: 5 5; 7: 12 solution is 1: 0 2; 2: 6: 5 6; 7: 13 solution is 1: 0 2; 2: 6: 5 6; 7: 14 solution is 1: 0 2; 2: 6: 5 5; 7: 15 solution is 1: 0 2; 2: 6: 5 3; 7: 16 solution is 1: 0 2; 2: 6: 5 0; 7: 17 solution is 1: 0 2; 2: 6: 5 1; 7: 18 solution is 1: 0 3; 2: 6: 5 6; 7: 19 solution is 1: 0 3; 2: 6: 5 2; 7: 20 solution is6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 65; 3; 6; 3: 2 5; 4: 3 0; 5: 4 2;4; 3: 2 5; 4; 5; 4; 5; 5; 4; 6; 3; 0; 3; 0; 4; 4; 0; 5; 6; 6; 4; 6; 5; 0; 4; 3: 20; 4: 33; 5: 46;2; 4: 30; 5: 46;3:}
我要回帖
更多推荐
- ·能打骚扰电话的软件很多是不是玩了这种赚钱小游戏获取你的手机号他们再卖出去？
- ·rtx2000r7 200显卡能玩什么游戏游戏吗，能开多高？
- ·航海狼人杀背包栏隐藏饥荒海难海盗帽怎么获得办
- ·魔兽争霸洛丹伦的夏天3冰封王座重回洛丹伦的文件名是什么？
- ·魔兽争霸洛丹伦的夏天3冰封王座重回洛丹伦文件名是什么？
- ·胃整个胃大部切除术了，术后7天喝水肚子胀痛怎么回事
- ·如何查找身边的安全隐患消防隐患
- ·伊宁市有哪些银行没有招商银行
- ·奥美拉唑 胃炎胶囊，阿莫西林胶囊，甲硝唑片能不能治疗胃炎
- ·心慌乏力，喘气费力，年轻人胸口压迫感闷痛闷痛能吃参松养心胶囊吗
- ·浸渍胶膜纸饰面胶合板的加固技术特性有哪些
- ·剑网三赔付3首创信用赔付 会是怎么样的呢
- ·不会英文，一个人薄荷岛去杜马盖地地能行吗
- ·髋关节疼痛的症状求帮助.马拉松前最多一次最多跑了
- ·发热了，什么情况下需要发烧能捂汗吗，怎么情况下需要物理降温
- ·每日能量摄入计算公式受哪些因素影响
- ·0.25米比五十厘米化成7.2 3.6最简整数比比
- ·ppt文字被覆盖盖
- ·设3阶参数方程二阶导数公式A等于d(a00,00b,0c0),其中abcd不等于0,则A的-1等于多少
- ·怎么制定孩子的学习方向
- ·数据结构习题，求思路过程
- ·怎样在守财龙招标网查看招标信息呀？一定要注册才能看吗？
- ·易信公众平台登录号注册用户是否关注验证是什么意思
- ·我在斑马学车交了钱没回复报了名,想参加考试,该如何缴费?
- ·孙大霞日语原来如此怎么说怎么说
- ·求一起：SSC时时彩预测最准的网站站
- ·论文中一些原料写着工业级什么意思
- ·报销单如何出口退税核销单
- ·这题如果写3个4可以吗？对不对
- ·为什么用205焊条重庆防水补漏cqbuding却还是漏,而302补过却不漏
- ·励志奋进的五年的句子楹联出处
- ·合肥经开区合肥平面设计培训训班，合肥哪家合肥平面设计培训训好
- ·艾草种植的时候需要打农药在什么时候打最吗
- ·康师傅水晶葡萄饮料请问一岁以内的孩子可以喝康师傅的水
- ·我是学霸手抄报谁会做感恩节的手抄报，帮帮我找找内容吧
- ·(10÷x)×5=50
