数据结构课习题参考答案.doc 88页

'数据结构目录一、1.1比较2个线性链表的C函数……………………………………………………………31.2写一个倒置顺序存贮的线性表的C函数…………………………………………………31.3写一个在线性表中，使线性表中没有值相同的结点的函数。…………………………41.4编写一个求解给定多项式的值的C函数。………………………………………………51.5实现多项式乘法……………………………………………………………………………61.7车厢出站问题………………………………………………………………………………91.8编写对任一栈作进栈和出栈运算的C函数……………………………………………101.10写出表达式等价的后缀表达式。………………………………………………………121.11编写一个统计给定的线性链表的结点个数的C函数。………………………………151.12编写一个将给定的线性链表逆转的C函数。…………………………………………161.13编写一个插入值的c函数。……………………………………………………………181.14编写一个删除链表中结点的前趋结点的C函数。……………………………………191.15试编写一个将两个链表归并成一个线性链表的C函数。……………………………201.17用环形链表解1。6题…………………………………………………………………231．18将给定的线性链表改成环形链表……………………………………………………241．19将给定的线性链表改成一个带表头的环形链表……………………………………251．20编写用hash函数h（Xi）＝Xi，对X1，X2……X800进行hash存储的程序…261．21求广义表的深度。……………………………………………………………………272．1试编写一个在两个顺序字符串中寻找最大公共子串的C函数。……………………292．2试编写一个实现STRINS（S1，I，S2）的C函数。…………………………………312．3按照2.2题的要求，编一个实现STRDEL（S，I，J）的C函数。…………………323．1编写一个二分插入排序的C程序………………………………………………………333．2编写一个对给定链表进行插入排序的C程序。………………………………………343．5采用顺序存储实现，即用数组存放排序过程中以排好序的链表的头指针。………363．6采用顺序存储的结构即数组实现。……………………………………………………383．7编写一个实现快速排序的非递归的C函数。…………………………………………393．8对于分别写出用下列排序方法对线性表进行排序的结果。…………………………404．3将n阶三对角阵（即半带宽为1的带状矩阵）A按行序列序存放在一维数组b[3*n-2]中。若aij(|i-j|<=1)存放在b[k]中，请求出求解k的计算公式。…………………………………424．4如果把广义的Anab按行序列序存放在一维数组b[(a+b-1)*n-(a+b-2)]中，元素aij存放在b[k]中，那么请写出计算k的计算公式。……………………………………………………424．5试编写一个求解两个三元数组相加的C函数。………………………………………424．6试编写一个将十字链表转置的C函数.…………………………………………………445．1请分别给出对树进行前序、后序、层次序遍历后的结点序列。……………………455．2试叙述将m棵有序树组成的有序树林转换成相应的二叉树的逆变换。……………465．3试编写一个把树中每个结点的左右子结点进行对换的C函数。……………………475．4编写一个利用栈来实现后序遍历一棵给定的二叉树的C函数。……………………495．5题目：……………………………………………………………………………………51试为下面各小题分别编写一个C函数：（1）按前序输出T的结点值。（2）按后序输出T的结点值。（3）输出树T的叶子结点值。88 数据结构（1）求出树T的次数。5．6试编写一个把树T按标准形式进行存贮的C函数。…………………………………535．7已知树T中结点的中序和后序，编写一个把T按标准形式存储的C函数…………545．8判断给定的二叉树是否为完全二叉树…………………………………………………555．9判断两棵给定的二叉树是否相似………………………………………………………555．10把树T转换成由标准形式进行存储的树T’…………………………………………555．11试编写一个寻找结点a的父结点的C函数。…………………………………………565．12试编写一个按前序遍历穿线树的C函数。……………………………………………586．1画出由集合中结点所构成的查找树，画出删除后的查找树。………………………606．2试编写一个用平分法构造出由集合中结点所构成的丰满查找树的C函数。………606．5编写一个判断给定二叉树T是否为平衡树的C函数。………………………………626．6试画出Adelson插入方法的右改组的转换图。………………………………………656．9试画出用Hu-Tucker算法构造出的最佳叶子查找树。………………………………666．10画出每次插入后的B－树……………………………………………………………676．12修改皇后问题…………………………………………………………………………706．13马的周游路线…………………………………………………………………………767．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）完全图吗？……………857．6对于图题7.3的有向图，试问它是（1）弱连通图吗？（2）强连通图吗？……867．7图题7-7是有向图，试问其中哪个图是………………………………………………86（1）弱连通的？（2）强连通的？7．8具有N个顶点的连通无向图至少有几条边？…………………………………………867．9具有N个顶点的强连通有向图至少有几条边？………………………………………867．10分别写出用深度和广度优先搜索法遍历完全无向图的顶点序列。………………877．11改写以深度优先搜索法遍历给定的连通图的dfs程序。……………………………877．12在图题7.1中，从顶点1出发，分别画出其dfs生成树和bfs生成树。………8888 数据结构1.1：比较2个线性链表的C函数1．存储法：用两个数组存放线性表。2．存储结构：一般的顺序存储方式。3．源程序：intcomp(inta[],intas,intb[],intbs){inttmp=as>bs?as:bs;inti;for(i=0;ib[i])return1;if(a[i]bs)return1;if(bs>as)return-1;return0;}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:-14．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]，a[2]，...a[n-1]依次前移一个位置；（2）a[n-1]=t；（3）对由a[0]，a[1]...a[n-2]组成的数组重复上述步骤。·程序：#include#defineN10voidreverse(a,n)inta[];intn;{intt,i,j=0;while(j#defineM100intsq_delete(intlist[],int*p_m,inti){intj;if(i<0||i>=*p_m)return(1);for(j=i+1;j<*p_m;j++)88 数据结构list[j-1]=list[j];(*p_m)--;return(0);}voiddel(intlist[],int*p_n){inti,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(){intlist[M],i,n;printf("Inputthenumberofthedata:n");scanf("%d",&n);for(i=0;istructnode{intexp;intdata;structnode*next;};typedefstructnodeNODE;88 数据结构intsearch(intexp,NODE*c,NODE**pc,NODE**qc){*pc=NULL;*qc=c;if(c==NULL)return(0);while((*qc)->exp>exp){*pc=*qc;*qc=(*qc)->next;}if((*qc)->exp==exp)return(1);return(0);}NODE*multi(NODE*a,NODE*b){NODE*pa,*pb,*pc,*qc,*p,*c=NULL;intexp,data,flag;for(pa=a;pa!=NULL;pa=pa->next)for(pb=b;pb!=NULL;pb=pb->next){exp=pa->exp+pb->exp;data=pa->data*pb->data;if(data){flag=search(exp,c,&pc,&qc);if(flag)if(!(data+qc->data)){pc->next=qc->next;free(qc);}else(qc->data)+=data;else{p=(NODE*)malloc(sizeof(NODE));p->data=data;p->exp=exp;if(!pc)c=p;elsepc->next=p;p->next=qc;}}}return(c);}NODE*creat(){NODE*root,*p,*q;charch;inti;printf("Doyouwanttocreatanullone(Y/N)?n");scanf("%c",&ch);getchar();if(ch=="y"||ch=="Y")return(NULL);p=NULL;88 数据结构ch="y";for(i=0;ch=="y"||ch=="Y";i++){q=(NODE*)malloc(sizeof(NODE));if(p==NULL)root=q;elsep->next=q;printf("nPleaseinputtheDATAofnode%d:n",i);scanf("%d",&(q->data));getchar();printf("PleaseinputtheEXPofnode%d:n",i);scanf("%d",&(q->exp));getchar();printf("Doyouwanttocontinue(Y/N)?n");scanf("%c",&ch);getchar();p=q;}p->next=NULL;return(root);}voidprint(NODE*root){inti=0;if(!root)printf("n0");while(i++,root!=NULL){printf("nNODE%d:tDATA:%dtEXP:%d",i,root->data,root->exp);root=root->next;}}main(){charch;NODE*a,*b,*c;clrscr();printf("NowpleaseinputA:n");a=creat();printf("NowpleaseinputB:n");b=creat();printf("nA:n");print(a);printf("nB:n");88 数据结构print(b);c=multi(a,b);printf("nnnC:n");print(c);}五：测试数据：输入：A：5X^6+3X^4+2XB：7X^3+3X^2+5输出：C：35X^9+15X^8+21X^7+34X^6+29X^4+6X^3+10X输入：A：0B：5X^3+2X^2输出：0输入：A：3X^2+5X^1B：3X^1－5C：01.7假设右边轨道排列有编号为1，2，3,…,n的n节车厢，它们依次被拖进站，从左边轨道依次出站的号的排列顺序有an种情况。那么an是用下列方法所形成的所有可能排列顺序的总数：某时刻站中只剩下编号为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+...)88 数据结构=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+xg2(x)=∑akxk(k≥0)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≥0)令n=m+1,则有g(x)=∑(1/2m+1)(-1)m22m+1xm(m≥0)比较可知an是上式中x?项的系数。所以an=(1n+1/2)(-1)n22n+1化简得an=1/(n+1)(2nn)n节车厢出站有1/(n+1)(2nn)种排列顺序。所以，当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为数组元素个数)32↑↑↑↑tail1=0head1head2tail2=M-1head1,head2分别为栈1，栈2中下个元素入栈的位置，tail1，tail2为两个栈底。分析与算法步骤：因为tail1＝0,tail2＝M－1，一般情况下不会变动，所以省去这2个量。初始值：head1＝0，head2＝M-1；1．执行入栈时：88 数据结构（1）若head1-1+1＝head2+1，即head1＝head2+1时，整个数组满，溢出。（2）若对栈1入栈，把元素存入stack[head1]，head1++；（3）若对栈2入栈，把元素存入stack[head2]，head2――；2．执行出栈时：（1）对栈1：若head1＝0，栈空，出栈失败；否则head1――；（2）对栈2：若head2＝M－1，栈2空，出栈失败；否则head2++；tc程序：include#defineM10inthead1=0,head2=M-1;intstack[M];voidpush(intx,inti){if(head1==head2+1){printf("thestackisfull.failtopush.n");return;}if(i==1)stack[head1++]=x;elsestack[head2--]=x;}voidpop(inti){if(i==1){if(head1==0){printf("thestackisempty.failtopop.n");return;}*p=stack[--head1];}else{if(head2==M－1){printf("thestackisempty.failtopop.");return;}*p=stack[++head2];}}88 数据结构main(){intx,i,No=1;for(i=0;i=0;i--)printf("%d",stack[i]);printf("n");for(i=head2+1;i="A"&&c<="Z")||(c>="a"&&c<="z"))return(1);elsereturn(0);88 数据结构}intmid_to_pos(charmidexpress[],charposexpress[]){charstack[MAXN],c;inttop,i,j;stack[0]="$";top=0;j=0;i=0;c=midexpress[0];while(c!=""){if(ischar(c))posexpress[j++]=c;elseswitch(c){case"+":case"-":case"*":case"/":case"^":while(icp(c)<=isp(stack[top]))posexpress[j++]=stack[top--];stack[++top]=c;break;case"(":stack[++top]=c;break;case")":while(stack[top]!="(")posexpress[j++]=stack[top--];top--;break;default:return(1);}c=midexpress[++i];}while(top>0)posexpress[j++]=stack[top--];posexpress[j]="";return(0);}测试报告：voidmain()88 数据结构{charmidexpress[MAXN],posexpress[MAXN],c;inti,result;i=0;printf("ninputthemid_expresstion:(endwith"!")n");scanf("%c",&c);while(c!="!"){midexpress[i++]=c;scanf("%c",&c);}midexpress[i]="";result=mid_to_pos(midexpress,posexpress);if(result==1)printf("convertionfails!n");else{printf("thepos_expresstionis: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函数。存储结构：连表的结点采用：structnode{intdata;//关键字的类型自定structnode*link;};算发分析：利用链表的性质（结点中的指针指向下一个结点），逐步向表尾移动，以此计算出结点数。下面给出程序：typedefstructnode{intdata;structnode*link;}NODE;intcount(NODE*head){NODE*p;88 数据结构intc=0;p=head;while(p!=NULL){p=p->link;c++;}return(c);}测试报告：voidmain(){NODEa[10];inti=0;for(;i<9;i++){a[i].data=i;a[i].link=&a[i+1];}a[i].data=i;a[i].link=NULL;printf("thetotalamountofthelinkednodeis:%dn",count(&a[0]));}输入：|0---1---2---3---4---5---6---7---8---9^输出：thetotalamountofthelinkednodeis:101．12编写一个将给定的线性链表逆转的C函数，只允许改变结点的指针值，不允许移动结点值。算法如下：(1)置P为链表首址，R,Q为空；(2)若P为空返回NULL；算法结束，转（5），否则转（3）；(3)若链表只有一个结点，转（5），否则转（4）；(4)R<=P,P<=P->LINK,R->LINK<=Q,置Q=R,若P->LINK为空，转（5），否则转（4）；(5)P->LINK<=R,返回P,算法结束。源程序如下：#includetypedefstructnode{intdata;structnode*link;}NODE;NODE*tranfer(head)NODE*head;{NODE*p,*q,*r;p=head;r=q=NULL;if(head==NULL)return(NULL);88 数据结构if(p->link!=NULL){do{r=p;p=p->link;r->link=q;q=r;}while(p->link!=NULL);}p->link=r;return(p);}NODE*create(n)/*建立初始链表*/intn;{inti;NODE*head,*p,*q;if(n==0)return(NULL);head=(NODE*)malloc(sizeof(NODE));p=head;for(i=1;idata));q=(NODE*)malloc(sizeof(NODE));p->link=q;p=q;}scanf("%d",&(p->data));p->link=NULL;return(head);}main(){NODE*head,*r,*p;intn=5;printf("enterthedata:n");head=create(n);p=head;while(p!=NULL){printf("%d",p->data);p=p->link;}88 数据结构printf("n");head=tranfer(head);p=head;printf("nowthelistis:n");while(p!=NULL){printf("%d",p->data);p=p->link;}printf("n");}输入：12345输出：543211.13对于给定的线性链表,编写一个把值为a的结点插在值为b的结点的前面的c函数。若值为b的结点不在线性链表中，则把a插在表的最后。[存储结构]利用线形表的链接存储：typedefstructnode{chardata;structnode*link;}NODE;定义指针NODE**head,*p,*q,*t;[解题思路]指针*head指向链表的根结点，指针p指向值为b的结点，指针t指向它的前趋结点，指针q指向插入结点a。(1)如果头结点*head为空，或*head的结点值为b，修改头指针，结束算法；(2)查找值为b的结点，若找到，把值为a的结点插到b的前面；(3)若找不到，把a结点插在链表最后；结束算法。[程序]#includetypedefstructnode{chardata;structnode*link;}NODE;voidinsert(NODE**head,chara){NODE*p,*q,*t;q=(NODE*)malloc(sizeof(NODE));q->data=a;if(*head==NULL||(*head)->data=="b"){q->link=*head;*head=q;return;}for(p=*head;p->data!="b"&&p!=NULL;p=p->link)t=p;q->link=p;t->link=q;}[测试用例1]原链表：b,c,d,e,g,h88 数据结构插入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函数。[存储结构]线性链表采用标准形式存储的单链表，并使用如下的说明：typedefstructnode{chardata;structnode*link;}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。删除成功。[流程图]P1=NULLYNnnP1->data=aYNP2=NULL?P3=p2P2=p1P1=p1->linkYNP2=head?YNP3->link=p1*p_head=p1返回1返回0[C程序]intfro_del(NODE**p_head){88 数据结构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->link;}if(p1==NULL||p2==NULL)return(1);if(p2==*p_head)*p_head=p1;elsep3->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)存储结构：#includetypedefstructnode{chardata;structnode*link;}NODE;分析和算法操作：需要一个由字符串生成链表的函数。将两个链表归并成一个链表时在表头前附加一个虚结点，处理完后再将其释放掉。若无虚结点归并时需分情况处理，比较复杂。#includetypedefstructnode{chardata;structnode*link;}NODE;NODE*makelist(a)chara[];{NODE*head,*p,*q;inti;if(a[0]=="")return(NULL);88 数据结构head=(NODE*)malloc(sizeof(NODE));head->data=a[0];head->link=NULL;p=head;for(i=1;a[i]!="";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=head;while(p!=NULL&&q!=NULL){r->link=p;s=p->link;p->link=q;r=q;p=s;q=q->link;}while(p!=NULL){r->link=p;r=p;p=p->link;}while(q!=NULL){r->link=q;r=q;q=q->link;}s=head;head=head->link;free(s);return(head);}main(){chara[100],b[100];NODE*xhead,*yhead,*zhead;printf("inputastring:n");scanf("%s",a);printf("inputastring:n");scanf("%s",b);xhead=makelist(a);yhead=makelist(b);zhead=linklist(xhead,yhead);while(zhead!=NULL)88 数据结构{printf("%c->",zhead->data);zhead=zhead->link;}}测试用例：输入：ABCDEF和GHIJKLMN输出：A->G->B->H->C->I->D->J->E->K->F->L->M->N1_15一．题目：设X=,Y=是两个线性链表，试编写一个将这两个线性链表归并成一个线性链表Z的C函数，使得Z=二．算法分析：（1）若X表或Y表为空，返回表Y，否则进入（2）；（2）将Y表相应结点y(i)插入X表中x(i)与x(i)->link之间；（3）如果Y表仍有剩余，将其插入以上生成的Z表中。三．程序如下：typedefstructT{intdata;structT*link;}NODE;NODE*merge(NODE*x,NODE*y){NODE*z=x,*yn;if(x==NULL)returny;if(y==NULL)returnx;while(x&&y){yn=y->link;/*yn:saveoriginallink;*/y->link=x->link;x->link=y;if(y->link==NULL)break;x=y->link;y=yn;}if(y->link==NULL)y->link=yn;88 数据结构returnz;}1_171.存贮结构:按题目要求,采用环形链表实现.2.存储方式:用链接存储的环形队列实现.3.源程序:#includestructnode{intdata;structnode*link;};typedefstructnodeNODE;NODE*crearl(intn){inti;NODE*head,*new;head->data=1;new=head;for(i=1;ilink=(NODE*)malloc(sizeof(NODE));new=new->link;new->data=i+1;}new->link=head;returnhead;}voidprintrl(NODE*head,inti,intk){inta;NODE*p,*q;p=head;if(i!=1){q=NULL;while(p->data!=i){q=p;p=p->link;}}else88 数据结构{while(p->link!=head)p=p->link;q=p;p=p->link;}for(a=0;alink;}printf("theresultis:");while(p->link!=p){printf("%d",p->data);q->link=p->link;free(p);p=q->link;for(a=0;alink;}}printf("%d",p->data);}voidmain(){intn,i,k;NODE*head;clrscr();printf("inputn,i,k:");scanf("%d%d%d",&n,&i,&k);head=crearl(n);printrl(head,i,k);}1.测试用例:n=10,I=1,k=3output:36927185104n=10I=5k=12output:693108217541_181.存储结构:按题目要求为一般线形链表2.存储方式:用链表实现88 数据结构1.源程序:NODE*nltorl(NODE*head){NODE*tmp=head;While(tmp->link!=NULL)Tmp=tmp->link;Tmp->link=head;Returnhead;}4.测试用例:经过将普通链表测试,可以转为环形链表.1_19假设给定的线性链表的结点值为整数。编写一个将给定的线性链表改造成一个带表头结点的环形链表的C函数，并让表头结点的值等于原来线性链表中结点的个数。·分析：先数出原链表中结点的个数，存入新开辟的表头结点中，将表头结点连到原链表表头上，并将表尾指针指向表头结点，head指向表头结点。·程序：#includetypedefstructnode{intdata;structnode*link;}NODE;NODE*convert(NODE*t)/*t为原链表的表头结点*/{NODE*head,*p,*q,*k;intn=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->link;n++;}q->link=k;k->data=n;return(head);}在main中只需调用convert函数即可完成所要求的转化，函数返回值即为指向环形链表表头的head指针。88 数据结构1_20设m=231y0=568731yi=(15625*yi-1+22221)modmxi=1000*yi/m(1<=i<=800)x1,x2,…,x800是0~999之间的800个伪随机数。试按下面两种要求分别编写用Hash函数h（xi）=xi，对x1,x2,…,x800进行Hash存贮的程序：（1）用开式寻址法解决冲突。（2）用拉链法解决冲突。l分析：开式寻址法是在发生冲突时用循环地址探测序列进行线性探测，找出空位置可供插入，而拉链法则是把具有相同Hash地址的的键值都存放在同一个链表中。l程序：1）开式寻址法：#include#defineM1000#definem231intx[801];longinty[801];intt[M];voidmain(){inti,j,k;y[0]=568731;for(i=1;i<801;i++){y[i]=(15625*y[i-1]+22221)%m;x[i]=1000*y[i]/m;}for(i=0;i=0;k++);j=(j+k)%M;if(t[j]<0)t[j]=x[i];}}2）拉链法#include#defineM1000#definem231typedefstructnode{intkey;structnode*link;}NODE;88 数据结构intx[801];longinty[801];NODE*t[M];voidmain(){inti;NODE*p,*q,*r;y[0]=568731;for(i=1;i<801;i++){y[i]=(15625*y[i-1]+22221)%m;x[i]=1000*y[i]/m;}for(i=0;ilink;}r=(NODE*)malloc(sizeof(NODE));r->key=x[i];r->link=NULL;if(q==NULL)t[x[i]]=r;elseq->link=r;}}1_21求广义表的深度。我们规定空的广义表的深度为0，而一般的有0若s?是一个原子depth(s)={1+max(depth(a0),…depth(an-1))若s是广义表（a0,a1,…an-1）编写一个求解广义表s的深度的C函数。解答：有题目给出的深度的公式，很容易想到运用递归来实现所要求的功能。这里在主函数中简单的采用直接构造各种类型的广义表法，为了测试算深度函数的有效性。#includestructnode{inttag;union{structnode*dlink;chardata;}dd;88 数据结构structnode*link;};typedefstructnodeNODE;intdepth(NODE*p){intmax,t;if(p==NULL)return(0);if((p->tag)==0)max=1;elsemax=depth(p->dd.dlink)+1;t=depth(p->link);return(t>max?t:max);}main(){NODE*head,*p;intd,i;chark="a";head=NULL;/*(1)*/d=depth(head);printf("thedepthis:%dn",d);head=(NODE*)malloc(sizeof(NODE));/*(2)*/head->tag=0;head->dd.data=k;head->link=NULL;p=head;for(i=1;i<4;i++){p->link=(NODE*)malloc(sizeof(NODE));p=p->link;p->tag=0;p->dd.data=k+i;p->link=NULL;}d=depth(head);printf("thedepthis:%dn",d);k="e";/*(3)*/p=head;for(i=1;i<4;i++){p->tag=1;p->dd.dlink=(NODE*)malloc(sizeof(NODE));p=p->dd.dlink;p->tag=0;p->dd.data=k;p->link=NULL;}d=depth(head);printf("thedepthis:%dn",d);}88 数据结构在主函数中构造了三种结构各异的广义表。（1）空的广义表，得到的深度为0。（2）0,a,->0,b->0,c->0,d，^得到的深度为1。（3）1，↘，-》0,b->0,c->0,d^得到的深度为4。1,↘,^1,↘^0,e,^2_1假设s和t分别是具有m个和n个字符的顺序存贮的串。试编写一个在s和t中寻找最大公共子串的C函数。解答：该题的本质即为模式匹配，实际上是把t中所有可能长度的子串与s进行模式匹配，从最长长度n开始，若匹配成功就直接输出当前子串，否则长度自减1后重新开始匹配。直到长度减为0，此时则说明没有公共子串。下面的C函数利用了书中列出的几个函数实现了题目所要求的功能。#include#include#defineMAXN100chart[MAXN],s[MAXN];intflink[MAXN];intm,n;intstrsub(chars1[],inti,intj,chars2[]){intm,k;if(i<0||i>=(m=strlen(s1)))return(-1);if(j<0||i>m)return(-1);for(k=0;k0){k=0;while(k1link;q=(NODE*)malloc(sizeof(NODE));for(m=k;m<4&&p->data[m]!="";m++)88 数据结构{q->data[m-k]=p->data[m];p->data[m]="*";/*"*"isinvalidchar*/}if(p->data[m]=="")q->data[m-k]="";elsefor(l=k;l<4;l++)q->data[l]="*";r=s2;while(r->link!=NULL)r=r->link;for(m=0;r->data[m]!=’’;m++);r->data[m]=’*’;while(m<4)r->data[++m]=’*’;q->link=p->link;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中结点的个数L2．通过I/4计算出其在S中的哪个结点3．通过I%4算出其在该结点中的位置4．若（I+J-1）/4>L则置该位置为‘*’；否则，将I位所在结点中的所在位及其后均置为‘*’；并将（I+J-1）/4位所在结点中的所在位及其前均置为‘*’；5．最后使I位所在结点指向（I+J-1）/4位所在结点voidstrdel(NODE*s,intI，intj){intk,l,m,h;NODE*p,*q;k=i/4;h=i%4;q=p=s;l=0;while(p->link!=NULL){p=p->link;l++;}for(m=0;m!=k;m++)p=p->link;if((i+j-1)/4>l)p->data[h]="";else{for(m=0;m!=(i+j-1)/4;m++)q=q->link;88 数据结构for(m=h;m<4;m++)p->data[m]="*";for(m=(i+j-1)%4;m>=0;m--)q->data[m]="*";/*"*"isinvalidchar*/p->link=q;}}若S=“ABCDEFGHIJKLMNO”，I=3,j=10则调用后结果为“ABC****LMNO”3_1编写一个二分插入排序的C程序一：数据结构用一个数组a来存储数据元素，线性存储可以方便存储。二：具体分析使用二分查找来代替线性查找来进行插入操作可以显著提高效率，因此，编写了一个bi_search函数来进行查找，返回一个需要插入的位置给j，然后将a[j]以后的元素都向后移一个位置，将a[i]放入a[j]的位置。本题难度不高。三：源程序intbi_search(inta[],intn,intv){inti,j,m;i=0;j=n-1;while(i<=j){m=(i+j)/2;if(v==a[m])return(m);if(vj;k--)a[k]=a[k-1];88 数据结构a[j]=x;}}main(){inti;inta[]={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。三：源程序#includestructnode{intdata;structnode*next;};typedefstructnodeNODE;NODE*link_insertion_sort(NODE*head){88 数据结构NODE*p,*q,*r,*w;intt;p=head->next;head->next=NULL;while(p){t=p->data;w=p->next;q=head;r=NULL;p->next=NULL;while(q->data<=t&&q){r=q;q=q->next;}p->next=q;if(!r)head=p;elser->next=p;p=w;}return(head);}main(){charch;intt,count;NODE*head,*p,*q=NULL;clrscr();printf("Doyouwanttoend(y|n)?");scanf("%c",&ch);getchar();head=NULL;for(count=0;ch!="y"&&ch!="Y";count++){printf("Pleaseinputthedata!");scanf("%d",&t);getchar();p=(NODE*)malloc(sizeof(NODE));p->data=t;p->next=NULL;if(!q)head=p;elseq->next=p;q=p;printf("Doyouwanttoend(y|n)?");scanf("%c",&ch);getchar();}printf("Theoriginaloneis:n");88 数据结构p=head;while(p){printf("%d",p->data);p=p->next;}printf("n");head=link_insertion_sort(head);printf("Thesortedoneis:n");p=head;while(p){printf("%d",p->data);p=p->next;}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#defineMAXN100structnode{intdata;structnode*link;};typedefstructnodeNODE;NODE*listmerge(head1,head2)NODE*head1,*head2;88 数据结构{NODE*p,*q,*pp,*pq;p=head1;q=head2;pq=pp=NULL;while(p!=NULL&&q!=NULL){if(p->data<=q->data){pp=p;p=p->link;}else{pq=q;q=q->link;pq->link=p;if(p==head1)head1=pq;elsepp->link=pq;pp=pq;}}if(q!=NULL)pp->link=q;returnhead1;}NODE*listmpass(head)NODE*head;{NODE*t[MAXN],*p;inti,k;if(head==NULL)returnNULL;p=head;for(i=0;p!=NULL;i++){t[i]=p;p=p->link;t[i]->link=NULL;}while(i>1){for(k=0;;k++)if(2*k#defineMAX100voidmerge(a,b,l,m,n)inta[],b[];intl,m,n;{inti,j,k;i=l;j=m+1;k=l;while(i<=m&&j<=n)if(a[i]<=a[j])b[k++]=a[i++];elseb[k++]=a[j++];while(i<=m)b[k++]=a[i++];while(j<=n)b[k++]=a[j++];}voidmerge_sort(a,n)inta[];intn;{inti,j,k,head;intb[MAX],tail[MAX];head=0;k=0;for(i=0;ia[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;ilow和S->up作为参数调用quick函数，在quick函数运行过程中若产生新的S结点，则使之入栈。这样循环直至栈空为止。三．源程序#include#difeinM100typedefstructstack{intlow;intup;}S;Ss[M];inttop;intquick(inta[],intlow,intup){inti,j;intt;if(lowt)j--;if(i0){top--;l=s[top].low;u=s[top].up;f=quick(a,l,u);if(lf+1){s[top].low=f+1;s[top++].up=u;}}for(j=0;jtypedefstructnode{introw,col,val;structnode*right,*down;}NODE;NODE*search_row_last(NODE*a,inti){NODE*p,*h;intk;p=a;for(k=0;k<=i;k++)p=p->down;h=p;88 数据结构while(p->right!=h)p=p->right;return(p);}NODE*search_col_last(NODE*a,intj){NODE*p,*h;intk;p=a;for(k=0;k<=j;k++)p=p->right;h=p;while(p->down!=h)p=p->down;return(p);}NODE*convert(NODE*h){NODE*h1,*p1,*q1,*p,*q,*r;intk;h1=(NODE*)malloc(sizeof(NODE));h1->row=h->col;h1->col=h->row;h1->val=h->val;h1->right=h1;h1->down=h1;p1=h1;for(k=0;krow;k++){q1=(NODE*)malloc(sizeof(NODE));q1->col=1000;q1->right=q1;q1->down=p1->down;p1->down=q1;p1=q1;}p1=h1;for(k=0;kcol;k++){q1=(NODE*)malloc(sizeof(NODE));q1->row=1000;q1->down=q1;q1->right=p1->right;p1->right=q1;p1=q1;}for(p=h->right;p!=h;p=p->right){for(q=p->down;q!=p;q=q->down){r=(NODE*)malloc(sizeof(NODE));r->row=q->col;r->col=q->row;r->val=q->val;p1=search_row_last(h1,r->row);q1=search_col_last(h1,r->col);r->right=p1->right;p1->right=r;r->down=q1->down;q1->down=r;}}return(h1);}5_1图题5-1是一棵结点值为字符的三次树。如果按前序、后序和层次序分别对该树进行遍历，那么请分别给出遍历后的结点序列。88 数据结构IHEFGBNLKJQPOMDCA图题5-1[解]前序遍历：ABEFHIGCJKLDMNOQP后序遍历：EHIFGBKLJCNQOPMDA层次遍历：ABCDEFGJMHIKLNOPQ5_2试叙述将m棵有序树组成的有序树林转换成相应的二叉树的逆变换。已知图题5-2的二叉树是由某m棵有序树林转换而来的。请使用你所给出的逆变换画出该二叉树所对应的树林。[解]*ADBECFGBEDAGFC*临时结点B0临时结点A0----------------------------------------------------------------------------------------------------------------------图题5-2转换后的树林假设β（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,重复上述变换过程。┊88 数据结构如果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函数。存储结构：#includetypedefstructnode{chardata;structnode*lchild,rchild;}NODE;算法：将根结点的左右子结点对换，然后对根结点的左右子树进行递归调用。为了检验是否正确对对换前后的树进行后序遍历。程序：#includetypedefstructnode{chardata;structnode*lchild,*rchild;}NODE;NODE*settree(a,b,m,n)chara[],b[];intm,n;{NODE*t;inti,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);}voidtradetree(t)NODE*t;{NODE*p;88 数据结构if(t==NULL)return;p=t->lchild;t->lchild=t->rchild;t->rchild=p;tradetree(t->lchild);tradetree(t->rchild);}voids_posorder(t)NODE*t;{NODE*s[100];ints1[100];inttop,i;if(t==NULL)return;s[0]=t;s1[0]=0;top=1;while(top>0){t=s[--top];i=s1[top];if(i==2)printf("%c",t->data);elseif(i==0){while(t->lchild!=NULL){t=t->lchild;s1[top]=1;s[++top]=t;s1[top]=0;}if(t->rchild==NULL)printf("%c",t->data);else++top;}else{s1[top]=2;++top;t=t->rchild;if(t!=NULL){if(t->lchild==NULL&&t->rchild==NULL)printf("%c",t->data);else{s[top]=t;s1[top++]=0;}}}}}main(){chara[100],b[100];NODE*t;inti;printf("inputmidorder:n");scanf("%s",a);printf("inputposorder:n");scanf("%s",b);for(i=0;a[i]!="";i++);88 数据结构t=settree(a,b,0,i-1);s_posorder(t);tradetree(t);printf("n");s_posorder(t);}测试用例：输入BACBCA输出：BCACBA5_4编写一个利用栈来实现后序遍历一棵给定的二叉树的C函数。存储结构：#includetypedefstructnode{chardata;structnode*lchild,rchild;}NODE;算法：叶结点直接输出不压栈，非叶结点需要压栈，输出后向上回溯，应判别是从左边回上去还是从右边回上去。程序：#includetypedefstructnode{chardata;structnode*lchild,*rchild;}NODE;NODE*settree(a,b,m,n)chara[],b[];intm,n;{NODE*t;inti,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);}voidtradetree(t)NODE*t;{NODE*p;if(t==NULL)return;p=t->lchild;88 数据结构t->lchild=t->rchild;t->rchild=p;tradetree(t->lchild);tradetree(t->rchild);}voids_posorder(t)NODE*t;{NODE*s[100];ints1[100];inttop,i;if(t==NULL)return;s[0]=t;s1[0]=0;top=1;while(top>0){t=s[--top];i=s1[top];if(i==2)printf("%c",t->data);elseif(i==0){while(t->lchild!=NULL){t=t->lchild;s1[top]=1;s[++top]=t;s1[top]=0;}if(t->rchild==NULL)printf("%c",t->data);else++top;}else{s1[top]=2;++top;t=t->rchild;if(t!=NULL){if(t->lchild==NULL&&t->rchild==NULL)printf("%c",t->data);else{s[top]=t;s1[top++]=0;}}}}}main(){chara[100],b[100];NODE*t;inti;printf("inputmidorder:n");scanf("%s",a);printf("inputposorder:n");scanf("%s",b);for(i=0;a[i]!="";i++);t=settree(a,b,0,i-1);s_posorder(t);88 数据结构tradetree(t);printf("n");s_posorder(t);}测试用例：输入：BACBCA输出：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中较大的一个并返回。三．程序如下：structNODE{intdata;NODE*lchild,*rchild;};voidPreScan(NODE*t)88 数据结构/*按前序输出T的结点值*/{if(t==NULL)return;printf(“%dt”,t->data);if((t=t->lchild)!=NULL){PreScan(t);while((t=t->rchild)!=NULL)PreScan(t);}}voidPostScan(NODE*t)/*按后序输出T的结点值*/{NODE*p;if(t==NULL)return;if((p=t->lchild)!=NULL){PostScan(p);while((p=p->rchild)!=NULL)PostScan(p);}printf(“%dt”,t->data);}voidLeafScan(NODE*t)/*输出树T的叶子结点值*/{if(t==NULL)return;if(t->lchild==NULL)/*isleaf*/printf(“%dt”,t->data);else{LeafScan(t=t->lchild);while((t=t->rchild)!=NULL)LeafScan(t);}}intGetDegree(NODE*t)/*得到树T的次数*/{intdegree=0,subDegree,d;NODE*p;if(t==NULL)return0;if((t=t->lchild)!=NULL){degree++;88 数据结构subDegree=GetDegree(t);for(p=t;(p=p->rchild)!=NULL;){degree++;d=GetDegree(p);if(subDegreedata=data;for(posi=0;posilchild=Create(pre+1,mid,posi);roof->rchild=Create(pre+1+posi,mid+posi+1,n-1-posi);returnroof;}5_788 数据结构递归算法：数据结构typedefstructnode{intdata;structnode*lchild;structnode*rchild;}NODE;intpre[MAX],ind[MAX],aft[MAX];intcount_p=0,count_m=0,count_a=0;算法分析：通过递归把两数组分为头接点，左子树，右子数三部分；后序序列和中序序列分别放在数组aft[1,n]和ind[1,n]中；NODE*bintree2(i,j,u,v)//I后序的起始点,j后序的终点,u中序的起始点,v中序的终点；inti,j,u,v;{intk,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);}88 数据结构5_8intis_cdtree(t)NODE*t;{intflag=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.存贮方式:Typedefstructnode{intdata;structnode*lchild;structnode*rchild;}NODE;2.存储结构:本题采用递归,并用1代表真0代表假3.源程序intislikebi(NODE*head1,NODE*head2){NODE*p=head1;NODE*q=head2;intl=0,r=0;if(p==NULL&&q==NULL)return1;if(p!=NULL&&q!=NULL){l=islikebi(p->lchild,q->lchild);r=islikebi(p->rchild,q->rchild);returnl*r;}return0;}4.测试用例:经过测试(输入两棵树)结果正确.5_101.存贮结构:采用附带一个标志位和一个右指针来线形存储一棵树.2.存储方式:用左标志直接找左孩子,用右指针找右孩子,程序用递归.88 数据结构Typedefstructnode{intdata;structnode*lchild;structnode*rchild;}NODE;1.源程序用t数组存放线形的树表示.NODE*creat(inti){NODE*head=(NODE*)malloc(sizeof(NODE));if(t[i].data==0)returnNULL;else{head->data=t[i].data;if(t[i].ltag==0)head->lchild=creat(i+1);elsehead->lchild=NULL;if(t[i].rchild!=-1)head->rchild=creat(t[i].rchild);elsehead->rchild=NULL;}returnhead;}2.测试用例:输入一组线形树,能够形成一棵标准存储的二叉树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的父亲程序#includetypedefstructnode{chardata;intltag,rtag;88 数据结构}LRNODE;charfind(LRNODEp[],intn,chara){inti,j,top=0,count=0;charc[100];for(i=0;itypedefstructnode{chardata;structnode*lchild,*rchild;intltag,rtag;}NODE;NODE*thread_sort_tree(a,n)chara[];intn;{NODE*root,*p,*r;inti;if(n==0)return(NULL);root=(NODE*)malloc(sizeof(NODE));root->data=a[0];root->lchild=NULL;root->rchild=NULL;root->ltag=0;root->ltag=0;for(i=1;idata=a[i];p=root;while(1){if(r->data<=p->data)if(p->ltag==0&&p->lchild!=NULL)p=p->lchild;elsebreak;elseif(p->rtag==0&&p->rchild!=NULL)p=p->rchild;elsebreak;}if(r->datadata){r->lchild=p->lchild;r->ltag=p->ltag;r->rchild=p;r->rtag=1;p->lchild=r;88 数据结构p->ltag=0;}elseif(r->data>p->data){r->rchild=p->rchild;r->rtag=p->rtag;r->lchild=p;r->ltag=1;p->rchild=r;p->rtag=0;}}return(root);}voidpreorder(root)NODE*root;{NODE*p,*q;p=root;while(p!=NULL){if(p->ltag==0&&p->lchild!=NULL){q=p->lchild;printf("%c",p->data);p=q;}else{q=p->rchild;printf("%c",p->data);if(p->rtag==0)p=q;elsep=q->rchild;}}}voidmain(){chara[8]={"E","B","H","C","F","A","D","G"};NODE*root;root=thread_sort_tree(a,8);preorder(root);printf("n");}测试样例：穿线树已在函数中初始化，不需输入（即为书p.139图5.9.3所示的穿线树）输出为：EBACDHFG88 数据结构6_1假设结点序列F=(60,30,90,50,120,70,40,80)，试用查找树的插入算法，用F中的结点依次进行插入，画出由F中结点所构成的查找树t1，再用查找树的删除算法，从查找树t1中依次删除40，70，60，画出删除后的查找树。解答：至于查找树的插入和删除算法在书中的第6.1节已明确给出，这里就不再赘述。查找树的结点插入时，先查找该结点若以存在，则插入失败并返回；否则进行插入。插入时先和根结点比较若比它大则往右边走，继续比较；否则往左边走，继续比较。直到遇到空指针则该结点插入的位置即为该指针的位置。由上所述，每次结点都是插入后都成为树的叶结点。给出树t1如下：60↙↘3090↘↙↘5070120↙↘4080查找树删除算法的原理书上P149页有详细的分析。删除40，70，60后的树如下所示：30↘50↘90↙↘80126_2已知F=(a0,a1,…,an-1)是一个已排序的整数结点序列，试编写一个用平分法构造出由F中结点所构成的丰满查找树的C函数。解答：很容易联想到用递归来解决这个问题。用函数NODE*creat_tree(inta[],intm,intn)来实现。每次调用时序列中间的一个数即为树根返回，m指a数组开始的下标号，n指a数组结束的下标号，中间指用(m+n)/2得到。具体实现的C函数如下：(这里假定用户输入的F数组已由小到大按升序排好列了)#includestructnode{intdata;structnode*llink;structnode*rlink;};typedefstructnodeNODE;NODE*creat_tree(inta[],intm,intn)88 数据结构{NODE*t;intk;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);}voidsuc_order(NODE*t){if(t!=NULL){suc_order(t->llink);suc_order(t->rlink);printf("%d",t->data);}}voidmid_order(NODE*t){if(t!=NULL){mid_order(t->llink);printf("%d",t->data);mid_order(t->rlink);}}main(){intn,i;inta[100];NODE*head;printf("nInputthesizeofthearray:n");scanf("%d",&n);getchar();for(i=0;istructnode{chardata;structnode*left,*right;};typedefstructnodeNODE;voidcreat(NODE*root){chartype;printf("nPleaseinputthedata!:n");getchar();88 数据结构scanf("%c",&(root->data));getchar();printf("nPleaseinputthetypeofthenode:(l\r\b\e)");scanf("%c",&type);switch(type){case"l":root->left=(NODE*)malloc(sizeof(NODE));printf("nPleaseinputtheleftchild:n");creat(root->left);root->right=NULL;break;case"r":root->right=(NODE*)malloc(sizeof(NODE));printf("nPleaseinputtherightchild:n");creat(root->right);root->left=NULL;break;case"e":root->left=NULL;root->right=NULL;break;case"b":root->left=(NODE*)malloc(sizeof(NODE));printf("nPleaseinputtheleftchild:n");creat(root->left);root->right=(NODE*)malloc(sizeof(NODE));printf("nPleaseinputtherightchild:n");creat(root->right);break;}}voidr_preorder(NODE*t){if(t!=NULL){printf("%c",t->data);r_preorder(t->left);r_preorder(t->right);}}intis_batree(NODE*root){intda,db,dc;if(!root)return(1);if(!((da=is_batree(root->left))&&(db=is_batree(root->right))))return(0);dc=da>db?da-db:db-da;if(dc>1)return(0);return(da>db?da+1:db+1);}main()88 数据结构{charch;intflag;NODE*root;printf("nAnemptytree?(y|n)n");scanf("%c",&ch);if(ch=="n"){printf("nPleaseinputtherootnode!n");root=(NODE*)malloc(sizeof(NODE));creat(root);r_preorder(root);printf("nItis");if(!(is_batree(root)))printf("not");printf("abalancetree!");}}四：测试结果输入：结点类型结点值balbecrdee输出：Itisabalancetree!输入：结点类型结点值babbrcedeerfeg输出：Itisabalancetree!输入：结点类型结点值babbrced88 数据结构eerflgeh输出：Itisanotbalancetree!输入：结点类型结点值babbrcedbeefeg输出：Itisanotbalancetree!6_6试画出Adelson插入方法的右改组的转换图。解答：右改组的画法与左改组的画法类似，如下图：88 数据结构6_9给定结点k0,k1,k2,k3,k4的键值分别为10，30，50，70，90，相对使用概率为5，6，3，4，7。（1）构造阶段中结点序列的变化情况：k0k1k2k3k4ٱ5ٱ6ٱ3ٱ7ٱ4k0b1k3k4ٱ5ٱ9ٱ7ٱ4k0b1b2ٱ5ٱ9ٱ11b3b2ٱ14ٱ11b4ٱ25（2）构造阶段产生的树b4ٱ2588 数据结构b3ٱ14b2ٱ11k0ٱ5b1ٱ9k3ٱ7k4ٱ4k1ٱ6k2ٱ3（1）建造阶段结点序列的变化情况k0k1k2k3k42ٱ3ٱ3ٱ2ٱ2ٱk0c1k3k42ٱ2ٱ2ٱ2ٱc2k3k41ٱ2ٱ2ٱc2c31ٱ1ٱc40ٱ（2）建造阶段产生的树0ٱc41ٱc21ٱc32ٱk02ٱc12ٱk32ٱk43ٱk13ٱk2即为所求树。6_10（1）插入20010020010020025010015020025015010012020025015010011012020025015020022025010011012015088 数据结构10011012020020522025015021022025020020510011012015021020020590100110120220250150210220250160200205901001101201001502108090110120160200205220250100150210809016017020020522025088 数据结构110120100150200210160170110120809020220522025010015020021080901101201601702022052202252501001502002108090110120160170202205220225240250200100150210240809016017020220524525011012088 数据结构220225（2）删除2021001502002402452508090205210220225110120160170100160205240（3）删除1501702002452508090210220225110120（4）删除20010016021024024525080901101201702052202256_12算法分析：在原来的寻找一个方法是用到的是一个maxn*maxn的栈，这样的话浪费了很大的空间不利于处理棋局比较大的情况。这里用的是maxn的一个栈，这样的话机不能把每一行都压栈，这里只能选者有用的节点压栈。其他的处理也是用得回朔的方法。不同：1节点进入时标准有所不同；2找到一种方法以后还要继续回朔，直到所有的路径都被找完。部分源程序：Intqueens(n)88 数据结构intn;{NODEstack[MAXN];inttop;introw[MAXN],col[MAXN],md[2*MAXN-1],sd[2*MAXN-1];intstr,stc,i;intis_First=1;intanswer=0;top=0;str=-1;stc=-1;begain:for(i=0;i=0){if(str<=n-1)if(stcn||sy<1||sy>n)flag=0;return(flag&&maze[sx][sy]==0&&mark[sx][sy]==0);}voidsetmove(){mv[0].a=-2;mv[0].b=1;mv[1].a=-1;mv[1].b=2;mv[2].a=1;mv[2].b=2;mv[3].a=2;mv[3].b=1;mv[4].a=2;mv[4].b=-1;mv[5].a=1;mv[5].b=-2;mv[6].a=-1;mv[6].b=-2;mv[7].a=-2;mv[7].b=-1;}intIs_Finish(intn){inti;intj;intnum=1;for(i=1;i<=n;i++)for(j=1;j<=n;j++)88 数据结构{if(mark[i][j]==0)num++;if(num>1)return(0);}return(1);}intgetmazepath(m,n,w)intm,n;{inti,j,k,g,h,t;if(maze[1][1]!=0||maze[m][n]!=0)return(1);s[0].x=m;s[0].y=n;s[0].d=-1;top=1;mark[m][n]=1;while(top>0){i=s[--top].x;j=s[top].y;k=s[top].d;while(k<7){g=i+mv[++k].a;h=j+mv[k].b;if(enable_move(g,h,w)){mark[g][h]=1;s[top].x=i;s[top].y=j;s[top++].d=k;i=g;j=h;k=-1;if(Is_Finish(w)){printf("pathinmaze:n");for(t=0;t#defineMAXN50#defineMAXM100typedefstructl_node{intver;structl_node*link;}L_NODE;typedefstructe_node{intver1;intver2;}E_NODE;voidcreat_adj_list(L_NODE*head[],intn,E_NODEe[],intm){inti,u,v;L_NODE*p,*q;for(i=1;i<=n;i++)head[i]=NULL;for(i=0;iver=v;p->link=NULL;if(head[u]==NULL)head[u]=p;else{q=head[u];while(q->link!=NULL)q=q->link;q->link=p;}p=(L_NODE*)malloc(sizeof(L_NODE));p->ver=u;p->link=NULL;if(head[v]==NULL)head[v]=p;else{q=head[v];while(q->link!=NULL)q=q->link;q->link=p;}}}88 数据结构voidinit(intvisit[],intn){inti;for(i=1;i<=n;i++)visit[i]=0;}voiddfs(intu,L_NODE*head[],intvisit[]){L_NODE*t;visit[u]=1;printf("%4d",u);t=head[u];while(t!=NULL){if(visit[t->ver]==0)dfs(t->ver,head,visit);t=t->link;}}测试报告：voidmain(){L_NODE*head[MAXN];intvisit[MAXN],n,m,u;E_NODEe[12];e[0].ver1=1;e[0].ver2=3;e[1].ver1=1;e[1].ver2=4;e[2].ver1=1;e[2].ver2=2;e[3].ver1=2;e[3].ver2=4;e[4].ver1=2;e[4].ver2=5;e[5].ver1=3;e[5].ver2=6;e[6].ver1=3;e[6].ver2=4;e[7].ver1=4;e[7].ver2=6;e[8].ver1=4;e[8].ver2=7;e[9].ver1=4;e[9].ver2=5;e[10].ver1=5;e[10].ver2=7;e[11].ver1=6;e[11].ver2=7;creat_adj_list(head,7,e,12);init(visit,7);dfs(head,visit,1);printf("n");}输出结果：1364257（1）BFS法：存储结构：本题采用邻接表作为图的存储结构，邻接表中的各个链表的结点形式由类型L_NODE规定，而各个链表的头指针存放在数组head中。88 数据结构数组e中的元素e[0],e[1],…..,e[m-1]给出图中的m条边，e中结点形式由类型E_NODE规定。visit[i]数组用来表示顶点i是否被访问过。遍历前置visit各元素为0，若顶点i被访问过,则置visit[i]为1.另外，使用一个队列QTYPE来存储已经访问过的顶点。算发分析：首先访问出发顶点v，然后访问与顶点v邻接的全部顶点w1,w2,…,wi,再依次访问与w1,w2,…,wi,邻接的全部顶点（已访问的顶点除外），再从这些已访问的顶点出发，依次与它们邻接的全部顶点（已访问的顶点除外）。依次类推，直到图中或v所在的连通分量的所有顶点都被访问到为止，广度优先搜索结束。下面给出程序:#include#defineMAXN50#defineMAXM100typedefstructl_node{intver;structl_node*link;}L_NODE;typedefstructe_node{intver1;intver2;}E_NODE;voidcreat_adj_list(L_NODE*head[],intn,E_NODEe[],intm){inti,u,v;L_NODE*p,*q;for(i=1;i<=n;i++)head[i]=NULL;for(i=0;iver=v;p->link=NULL;if(head[u]==NULL)head[u]=p;else{q=head[u];while(q->link!=NULL)q=q->link;q->link=p;}p=(L_NODE*)malloc(sizeof(L_NODE));p->ver=u;p->link=NULL;if(head[v]==NULL)head[v]=p;else{q=head[v];while(q->link!=NULL)q=q->link;q->link=p;}}}88 数据结构voidinit(intvisit[],intn){inti;for(i=1;i<=n;i++)visit[i]=0;}voidbfs(intu,L_NODE*head[],intvisit[]){typedefstructqueuetype{intqa;intqe;intitem[MAXN];}QTYPE;intv,w;L_NODE*t;QTYPEqueue;printf("%4d",u);visit[u]=1;queue.qa=0;queue.qe=0;queue.item[0]=u;while(queue.qa<=queue.qe){v=queue.item[queue.qa++];t=head[v];while(t!=NULL){w=t->ver;if(visit[w]==0){printf("%4d",w);visit[w]=1;queue.item[++queue.qe]=w;}t=t->link;}}}测试报告：voidmain(){L_NODE*head[MAXN];intvisit[MAXN],n,m,u;E_NODEe[12];e[0].ver1=1;e[0].ver2=3;e[1].ver1=1;e[1].ver2=4;e[2].ver1=1;e[2].ver2=2;e[3].ver1=2;e[3].ver2=4;e[4].ver1=2;e[4].ver2=5;e[5].ver1=3;e[5].ver2=6;e[6].ver1=3;e[6].ver2=4;88 数据结构e[7].ver1=4;e[7].ver2=6;e[8].ver1=4;e[8].ver2=7;e[9].ver1=4;e[9].ver2=5;e[10].ver1=5;e[10].ver2=7;e[11].ver1=6;e[11].ver2=7;creat_adj_list(head,7,e,12);init(visit,7);bfs(1,head,visit);printf("n");}输出结果：134267567351247_3对于图题7.3的有向图，给出：（1）表示该图的邻接矩阵。（2）表示该图的邻接表。（3）图中每个顶点的入度和出度。解：（1）邻接矩阵如下：0101000图题7.3000010010000000000110000000100100000000010(2)邻接表如下：5^1^57^3^6^6^24^12388 数据结构4567（1）设各顶点入度和出度分别为ri,ci:r1=1,c1=2r2=1,c2=1r3=1,c3=1r4=1,c4=2r5=2,c5=1r6=2,c6=1r7=1,c7=17_4对于图题7.3的有向图，给出：（1）从顶点1出发，按深度优先搜索法遍历图时的所得的顶点序列。（2）从顶点1出发，按广度优先搜索法遍历图时的所得的定点序列。解：（1）1－2－5－7－6－3－4（2）1－2－4－5－6－7－37_5对于图题7.1的无向图，试问它是（1）连通图吗？（2）完全图吗？1234567（1）该图是连通图。判断无向图是否为连通图，即判断该图中是否每对顶点之间都有路径。（2）88 数据结构该图不是完全图。判断无向图是否为完全图，即判断图中是否每对顶点之间都有边。7_6对于图题7.3的有向图，试问它是（1）弱连通图吗？（2）强连通图吗？1234567(1)该图是弱连通图。判断有向图是否为弱连通图，即需判断图中是否每对顶点v和w之间有一个由不同顶点组成的顶点序列（v0,v1,……vk），其中v0=v，vk=w，且（vi，vi+1）或（vi+1，vi）属于图的边集。(2)该图是强连通图。判断有向图是否为强连通图，即需判断图中是否每对顶点之间有一条路径。7_7图题7-7是有向图，试问其中哪个图是（1）弱连通的？（2）强连通的？43211243(a)(b)[解]（1）(b)图是弱连通的。（2）(a)图是强连通的。7_8具有N个顶点的连通无向图至少有几条边？[解]具有N个顶点的连通无向图至少应有N—1条边。7_9具有N个顶点的强连通有向图至少有几条边？2N条边。88 数据结构7_10分别写出用深度和广度优先搜索法遍历具有六个顶点的完全无向图的顶点序列。（假设都以顶点1出发）。深度优先：1，2，3，4，5，6广度优先：1，2，3，4，5，67_11题目：改写以深度优先搜索法遍历给定的连通图的dfs程序，要求不用递归方法，而用一个栈来实现。算法分析：用栈保存由结点V出发可到达的结点，并作上标记，以使下次遇到时不会重复输出。当一路结点访问完后，向前回溯（利用出栈）并访问其他结点，直到所有结点均已遍历。程序的流程：结点进栈à结点出栈à访问并标记结点à相联结点进栈à……。（相联结点进栈后，执行相同的步骤）当栈空时，遍历完成。程序：#defineMAXN50typedefstructnode{intdata;structnode*link;};voiddfs(NODE*head[],intver,intv){ints[MAXN],visit[MAXN];inttop,i;for(i=1;i<=ver;i++)visit[i]=0;s[0]=v;top=0;while(top>=0){v=s[top--];if(visit[v]==0){printf("%dt",v);visit[v]=1;}for(p=head[v];p;p=p->link){if(visit[p->data]==0)s[++top]=p->data;}}printf("n");}88 数据结构7_12题目：在图题7.1中，从顶点1出发，分别画出其dfs生成树和bfs生成树。1254376分析：根据dfs遍历和bfs遍历的顺序，记录所得到的点和边的集合，即可得到生成树和生成树。dfs遍历：（1，2，4，3，6，7，5），边分别为：（1，2），（2，4），（4，3），（3，6），（6，7），（7，5）。bfs遍历：（1，2，3，4，5，6，7），边分别为：（1，2），（1，3），（1，4），（2，5），（3，6），（4，7）。解答：dfs生成树：125437612bfs生成树：5437688'