数据结构实验与习题

1数据结构实验与习题2要的环节。目前各种“数据结构”教材较为注重理论的叙述与介绍，算法描述上的原因编写了这本“数据结构实验与习题”。本参考书包括C语言基础知识、上机实验习题和书面作业练习题三部分。在C语言基础知识部分，主要介绍了输入/输出、函数及参数传递和结构体的概念应用。这部分内容非常重要，掌握的是否熟练会直接影响“数据结构“的学习。在实验部分，包括有完整的C语言源程序例题，介绍了一些设计数据结构题目所需程序，或者扩充已经给出的源程序，也有需独立思考设计的综合实验题。答分析题。并且配有部分练习题的答案供学生自学、练习、参考。由于时间仓足、水平有限，书中难免存在错误和不妥之处，敬请读者指正。3 1 3 5 8 10 12 20 28 30 32 34 40 42第三部分书面作业练习题 48 51 54 57 58 60 69 75 784言，由于该语言语法规范、严谨，非常适用于数据结构课程教学。在Windows环境下涌现出一系列的功能强大、面向对象的程序开发工具，如：VisualC++,BorlandC++,VBasic,VisualFoxpro等。由于VisualDelphi法描述工具。近年来在计算机科学研究、系统开发、教学以及应用开发中，C语言的使用越来越广泛。因此，本教材采用类C语言进行算法描述。基础好，可以越过这一部分内容不看。算法程序，如果数据不能正确输入，算法设计得再好也无法正常运行。C语言的输入是由系统提供的scanf()等函数实现，在程序的首部一般要求写入：函数scanf()的功能很丰富，输入格式也是多种多样，这是大家较为熟悉的知识，这里不做详细介绍。在使用中需要注意以下几个问题。（1）一条scanf()语句有多个变量、并且都是数值型（int,float,double）时，在输入数据时应该在一行之内键入多个数据，数据之间空格分隔。例如：scanf(“%d%f”,&n,&x);就是在两个数据之间使用空格键为分隔符，最后打回车键。5如果语句中在%d和%f之间有一个逗号：（2）在需要字符型变量或字符串输入时，要单独写一条输入语句，这样不易出错。如果在同一条scanf()语句中将字符型和数值型混合输入常常会出错。因为键盘输入时在数符，而不能起到‘分隔符’的作用。所以将它们混在一起容易出错。（3）在scanf()语句中变量写法应该是该变量的地址，这一点常被忽视。请看下列程序：4:printf(“\n请输入姓名：”);scanf(“%s”,n5:printf(“\n请输入性别：”);scanf(6:printf(“\n请输入学号和成绩：”);scanf}为了方便说明问题程序中加了行号，运行时当然不允许行号。一般情况下在scanf()语句中的变量名之前要加上求地址符&，上述程序第5，6行之中就是这地址，是该数组的首地址，所以name前面不加&。在本程序中把字符串、字符、数值型变量分别写入不同的scanf()语句，输入数据的具体形式如下：被忽略，还会影响后面的输入语句无法正确读入数据。因此，应该充分重视数据的输入技术。C语言的输出是由系统提供的printf()等函数来实现，在程序的首部一般要求写入：输出函数printf()的语法一般容易掌握，这里强调的是怎样合理巧妙的使用它。1.在连续输出多个数据时，数据之间一定要有间隔，不能连在6行符。这样使光标与提示信息出现在同一行上，光标停在问号后边：X=?。。几个数据在同一行输出，不能换行掉这些辅助输出语句。者之之所以感到编程难，就是忽视了这个基倡模块化结构化程序设计，不论BASIC、FONFTRAN、PASCAL还是其他高级语言，最终要涉及到子函数的设计和使用。C语言的源程序是由一个主函数和若干（或零个）子函数构成函数直接或间接的调用自身时，这样的函数称为递归函数。是否能够熟练的设计和使用函数，是体现一个有必要回顾和复习C语言函数的基本概念。函数设计的一般格式是：而函数体内所需处理的数据往往通过形参表传送，函数也可以不设形参表，此时写为：例1.2设计一个函数计算三个整数之和，再设计一个函数7调用两个函数。intsumx(inta,intb,intc)}}voidmain()printf(“\nsum=%d”,sumx(x,y,z));printf(“\n%6d%6d%6d”,x,y,z);printf(“\n“sum=%d”,sa);printf(“\n%6d%6d%6d”,x,y,z);运行结果：/*在赋值语句中调用函数sumx()函数在被调用时，由主调程序提供实参，将信息传递给形参。在调法通常分为传值和传址两大类。相同。传值调用的主要特点是数据的单向传递，由实参通过形参将数据代入被调用函数，不论在调用期间形参值是否改变，调用结束返回主调函数之后，实参值都不会改变。8在不同的算法语言中，传址调用的语法有所不同。在PASCAL语言中用变参实现传址。不变，但是该地址中的数据发生相应改变。这就是数据的双向传递。现看一例题：例1.3设计一个函数实现两个数据的交换，在主程序中调用。voidmain()printf(“\n%6d%6d”,x,y);}运行结果：参地址中的内容，而作为主函数变量x,y的地址仍然没有改变。从整数交换的角度看，本例题实现了双向数据传递。若从指针地址角度看，调用前后指针地址不变。如果需要在函数体中改变指针的地址，这就需要在原指针基础之上再加一级指针：杂。不如PASCAL的变量参数简便，也不如C++是数据结构程序设计的重要语法基础。定义结构体的一般格式：9{变量名2；ⅆⅆ结构体类型的变量，声明创建一个结构体变量的方法是：例如：structElemTypestructElemType使得书写更加简便。例如：typedefstructElemType就是一个新的类型名，并且是结构体类型名。声明变量x的语一个结构体中可以包含多个数据子域。数据子域的类型名一般指基本数据类型（intchar等也可是已经定义的另一结构体名。数据子域变量名可以是简单变量，也可以是数组。它们也可以称为结构体的数据成员。通过“结构体变量名.数据子域”可以访问数据子域。例1.6设计Student结构体，在主程序中运用。typedefstruct/*定义结构体Student*/voidmain()s1.num=1001;printf(“\n姓名：%s”,s1.nprintf(“\n学号：%d”,s1.}}构体的指针，通过以下语句段可以说明结构体指针的一般用法。p->num=101;p->x=83;printf(“\n%10s%6d%6d”,p->name,p->num,p->x);}设计一个一维数组，每个数组元素是Student结构体类型，通过以下语句段可以说明结构体数组的一般用法。可以通过“结构体数组名[下标].数据子域”访问数据域。/inti;printf(“\nprintf(“\n姓名：%s”,a[i].name)；printf(“\n}}以上是关于结构体的基本概念和简单运用。第二部分上机实验习题），体实习步骤如下：充分地分析和理解问题本身，弄清要求做什么（而不是怎么做），限制条件是什么。？），），结构设计。详细设计是对函数（模块）的进一步求精，用伪高级语言（写出算法框架，这时不必确定很多结构和变量。编码，即程序设计，是对详细设计结果的进一步求精，即用某种差错矫正，在程序成功后再删去它们。熟悉高级语言用法，如C语言。熟悉机器（即操作系统），基本的查主要有两条路径，一是用一组测试数据手工执行程序（或分模块进行二是通过阅读言。如果程序中逻辑概念清楚，后者将比前者有效。序，表面上的麻烦工作可以大大降低调试时所面临的复杂性，提高工作效率。在上机实开始之前要充分准备实验数据，在上机实践过程中要及时记录实验数据，在上机实践完成之后必须及时总结分析。写出实验报告。一般性、较小规模的上机实验题，必须遵循下列要求。养成良好的习惯。实验者必须重视这一环节，否则等同于没有完成实验任务。这里可以体现个人特色、何解决的；经验和体会等。二、实验习报告的提高要求：阶段性、较大规模的上机实验题，应该遵循下列要求。养成科学的习惯。a.设计思想：存储结构（题目中限定的要描述）；主要算法基本思可以通过调用关系图表达。c.实现注释：各项功能的实现程度、在完成基本要求的基础上还有什么功能。（3）用户手册：即使用说明。时间复杂度、空间复杂度分析；改进设想；经验和体会等。1.了解抽象数据类型（ADT）的基本概念，及描述2.通过对复数抽象数据类型ADT的实现，熟悉C语言语法及程序设计。学习打下基础。复数抽象数据类型ADT的描述及实现。数据对象：D={c1,c2c1,c2□FloatSet}数据关系：R={<c1,c2>c1/*存储表示，结构体类型的定义*/typedefstructfloaty;voidoutputc(compa);compadd(compk,comph);printf("输入实部realx=?");scanfprintf("输入虚部xvpuy=?");scanfvoidoutputc(compa){printf("\n%f+%fi\n\n",a.x,a.y);}compadd(compk,comph)l.x=k.x+h.x;l.y=必需的语句（例如函数原型声明、主函数中的调用等）。提示：//求两个复数相乘之积的函数再次调试运行程序。输入数据，记录结果，最后完成实验报告。1.了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储2.重点是线性表的基本操作在两种存储结构上的实现；其中以链表的操作为侧重点；并进一步学习结构化的程序设计方法。1.线性表的顺序存储表示（结构）及存储地址中也是相邻的,既地址连续。不同的教材有不同的表示，有的直接采用一维数组，typedefstructintlength;/}SqList;（2）本程序是一个完整的、子函数较多的源程序。目的为学生提供一个示范，提供顺序存储表示的资料，供学生参考。比如，主函数中简单“菜技术，同学们可以在main()函数中直接写几个简单的调用语句，就象前面的复中的main()一样。但是随着学习的深入，尽早学会使用“菜单设计”技术，会明显提高编程和运行效率。#defineMAXSIZE20typedefintElemType;/*数据元素类型typedefstructintlength;/}SqList;voidout_list(SqListLvoidinsert_sq(SqList*L,inti,ElemTypee);ElemTypedelete_sq(SqList*L,inti);intlocat_sq(SqListL,ElemTyp{inti,k,loc;ElemTypee,x;charch;printf("\n1.建立线性表");printf("\nprintf("\n3.删除第iprintf("\nprintf("\n6.结束程序运行");printf("\n======================================");case2:{printf("\ni,e=?");scanf("%d,%d",&i,&e);insert_sq(&a,i,e);out_case3:{printf("\ni=?");scanf("%d",&i);x=delete_sq(&a,i);out_listprintf("\nx=%d",x);case4:{printf("\ne=?");scanf("%d",&e);if(loc==-1)printf("\n未找到%d",locprintf("\n再见！");printf(“\n打回车键，返回。“);ch=getch();/*建立线性表*/{inti;printf("\nn=?");scanf("%d",&L->length);for(i=0;i<L->length;i++){printf("\ndata}voidout_list(SqList{inti;charch;printf("\n");for(i=0;i<=L.length-1;i++)printf("%10dprintf("\n\n打回车键，继续。“);ch=getch();voidinsert_sq(SqList*L,inti,ElemTypee){intj;if(L->length==MAXSIZE)printf("\noverflow!");elseif(i<1||i>L->length+1)printf("\nerroei!");else{for(j=L->length-1;j>i-1;j--)L->a[j+1]=L-L->a[i-1]=e;}ElemTypedelete_sq(SqList*L,inti){ElemTypex;intj;if(L->length==0)printf("\n是空表。underflow!");elseif(i<1||i>L->length){printf("\nerrori!");for(j=i;j<=L->length-1;j++)L->a[j-1]=L->a[j];}intlocat_sq(SqListL,Ele{inti=0;while(i<=L.length-1&&L.a[i]!=e)i+if(i<=L.length-1)retur2.线性表的链表存储表示（结构）及实现。存储地址中可以不相邻,既地址不连续。不同的教材的表示基本是一致的。typedefstructLNode（2）本程序是一个完整的、子函数较多的源程序。目的为学生提供一个示范，提供关于链表操作的资料，供学生参考。可以看到本程序的main(结构十分相似。稍加改动还可为其他题目的源程序所用。typedefintElemType;typedefstructLNodevoidinsert_L(LNode*L,inti,ElemTypee);ElemTypedelete_L(LNode*L,inti);{inti,k,loc;ElemTypee,x;charch;printf("\n\n1.建立线性链表");printf("\n\nprintf("\n\n3.删除第iprintf("\n\nprintf("\n\n5.结束程序运行");printf("\n======================================");printf("\n请输入您的选择(1,2,3,4,5)")case2:{printf("\ni,e=?");scanf("%d,%d",&i,&e);insert_L(L,i,e);ocase3:{printf("\ni=?");scanf("%d",&i);x=delete_L(L,i);out_L(L); if(x!=-1)printf("\nx=%d\n",x);case4:{printf("\ne=?");scanf("%d",&e);if(loc==-1)printf("\n未找到%d",locprintf("\n----------------");printf("\nprintf(“\n/*建立线性链表再见！"); p=h;printf("\ndata=?");scanf("%d",&x);p->next=s;p=s;□printf("data=?(-111end)");scanf("%d",&x);}□ □建成后的链表h/*输出单链表中的数据元素*/p=L->next;printf("\n\n");while(p!=NULL){pprintf("\n\n打回车键，继续。“);ch=getch();voidinsert_L(LNode*L,inti,ElemTypee){LNode*s,*p,*q;intj;j=0;while(p!=NULL&&j<i-1)if(p==NULL||j>i-1)printf("\niERROR!");p->next=s;}ElemTypedelete_L(LNode*L,inti){LNode*p,*q;intj;ElemTypex;p=L;j=0;while(p->next!=NULL&&j<i-1){p=p->next;j++;}if(p->next==NULL){printf("\niERROR!");return(p->next=q->next;free(q);}{LNode*p;intj=1;p=L->next;while(p!=NULL&&p->data!=e)if(p!=NULL)return(j);elseretu3.约瑟夫问题的一种描述：编号为1，2，ⅆⅆ,n的n个人按顺时针方向围坐一圈，开始按顺时针方向自1开始顺序报数。方法1．报m的人出列（将其删除从他在顺时针方向上的下一个人开始重新从一报数，ⅆⅆ,如此下去，直到所有人全部出列为止。试设计一个程序求出出列顺序。要求利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号和此人密码。方法2.报m的人出列（将其删除将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从一报数，ⅆⅆ,如此下去，直到所有人全部出列为止。试设计一出各人的编号和此人密码。typedefstructnode/*结点的结构定义//*密码子域/*指针域/voidouts(JOS*h,intm);printf(“\nenterthebeginsecretcode,m=（m>1）”);scanf(“%d”,&m);h=(JOS*)malloc(sizeof(JOS));h->link=h;pre=h;printf(“\n个人密码=?”);scanf(“%d”,i++;new->num=i;new->sm=mi;/*结点送值*/pre->link=new;pre=new;/*形成循环链表*/printf(“\n个人密码=?”);spre->link=h->link;free(h);h=pre->link;return(h);/*头指voidouts(JOS*h,intm){inti;JOS*q=h,p;printf(“\n“);printf(“%6d%6d”,q->num,q->sm);p->link=q->link;free(q);}printf(“%6d%6d\n”,q->num,q->sm);麻烦同学们可以试一试，加进头结点如何实现并不是任何时候有头结点都能使程序操作简化，要根据实际情况，决定用是否使用头结点。感兴趣的同学可以设计一个程序实现约瑟夫环的方在一般情况下默认使用头结点。不论是单向链表还是循环链表，头指针不能丢。1.用顺序存储表示（数组）实现约瑟夫环2.一个线性表有n个元素（n<MAXSIZE,MAXSIZE指线性表的最大长度且递增序实现。要求：采用顺序存储表示实现；采用链式存储表示方法实现；比劣。要求1）指定的值x由键盘输入2）程序能处理空链表的情况。4.用链表建立通讯录。通讯录内容有：姓名、通讯地址、电话号码。要求1）通讯录是按姓名项的字母顺序排列的；（2）能查找通讯录中某人的信息；[提示]可用链表来存放这个通讯录，一个中的‘当前结点’的数据小，就插在其前面。否则，再看后面是否还有结点，若没有结点了就插在其后面成为末结点；若后面还有结点，再与后面的结点逐一比较处理。5.超长正整数的加法，设计一个程序实现放在链表的最后一个结点中，表头结点值规定位-1。例如：大整数“567890987654321”可用如下的头结点的链表表示：按照此数据结构，可以从两个表头结点开始，顺序依次对应相加，求出所需要的进位后，将其代入下一个结点进行运算。1.掌握栈这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。2.掌握队列这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。3.了解和掌握递归程序设计的基本原理和方法。详细。为了减轻学生上机实验的困难，在此给出几个例题供参考。1.栈的顺序存储结构及实现。#defineMAXSIZE20typedefintElemType;/*数据元素类型typedefstruct{ElemTypea[MAXSIZE];inttop;/*}SqStack;voidout_s(SqStacks);{intk;ElemTypee,x;charch;init_s(&s1);printf("\n\n2.出栈一个元素，返回其值")；printf("\n\n3.结束程序运行");printf("\n======================================");printf("\nprintf("\n----------------");printf("\n再见！")printf(“\n打回车键，返回。“);ch=getch(); voidout_s(SqStacks){charch;inti;/*千万不能修改栈顶指针top*/if(s->top==-1)printf(“\nStackisNwhile(i!=-1){printf(“\ndata=%d”,s->a[i}printf(“\n打回车键，继续。“);ch=getch();{if(s->top==MAXSIZE-1)printf}if(s->top==-1){printf(“\nStackisUnderf2.循环队列（即队列的顺序存储结构）实现。typedefintElemType;typedefstructvoidout_Q(SqQueueQvoidEnQueue(SqQueu{intk;ElemTypee,x;charch;init_Q(&Q1);printf("\n\n2.出队一个元素，返回其值")；printf("\n\n3.结束程序运行");printf("\n======================================");printf("\nEnQueue(SqQueue&Q1,e);out_printf("\n----------------");printf("\n再见！");printf(“\n打回车键，返回。“);ch=getch(); {charch;inti;45350201if(Q->front==Q->rear)printf(“\nQueueisNULL.“);else{i=(Q->front+1)%while(i!=Q->rear){printf(“\ndata=%d”,Q->a[i]);printf(“\ndata=%d”,Q->a[i]);}printf(“\n打回车键，继续。“);ch=getch();voidEnQueue(SqQueu{if((Q->rear+1)%MAXSIZE==Q->front)printelse{Q->rear=(Q->rear+1)%}400}}typedefintElemType;typedefstructQNodetypedefstruct}L_Queue;voidout_Q(L_QueueQvoidEnQueue(L_QueueQ,ElemTypee);ElemTypeDeQueue(L_Queue{intk;ElemTypee,x;charch;init_Q(&Q1);printf("\n\n2.出队一个元素，返回其值")；printf("\n\n3.结束程序运行");printf("\n======================================");printf("\nEnQueue(SqQueue&Q1,e);out_printf("\n----------------");printf("\n再见！");printf(“\n打回车键，返回。“);ch=getch(); p->next=NULL;∧∧voidout_Q(L_QueueQ){QNode*p;charch;p=Q.front->next;p=p->next;}printf(“\n打回车键，继续。“);ch=getch();voidEnQueue(L_QueueQ,ElemTypeQ.rear->next=s;ElemTypeDeQueue(L_QuIf(Q.rear==p)Q.rear=Q基础上修改程序，实现十进制数据M向N进制（2或8或（1）采用顺序存储结构实现栈。（2）采用链表结构实现栈。2.阿克曼函数（Ackermann’sfunction）定义如下：人们之所以研究该函数，是因为m和n值的较小增长都会引起函数值的极快增长。（1）设计运用递归算法的源程序，上机运行。（2）写一个非递归算法的源程序，上机运行。并进行比较。3．二项式(a+b)n展开后，其系数构成杨辉三角形，利用队列写出打印杨辉三角形的前n行的程序。11.熟悉串类型的实现方法，了解简单文字处理的设计2.熟悉C语言的字符和把字符串处理的原理和方法。下面(1)字符：charch;ch是单个字符变量ch=’a’;’(2）字符串：S2=(char)malloc(si个串最多容10个字符；下列赋值语句是错误的：应该使用串拷贝函数：strcpy(S1,“abcdefghi”);strcpy(S3[0],”123456789”);strcpy(S3[1],”用双引号括起来的是字符串常量，在处理字符串常量时，注意总是有一个字符‘\0’作是1，ⅆⅆ,s3[0][8]里是9,s3[0][9]里是‘\0’（串尾标志）。(3)常见的字符函数：当str1<str2，函数结果<0；接后的新串。实现字符串置换操作。{intk;char*s,t[]="abc",*v="%%%";printf("\ns=?");gets(s);printf("\ns=%s\n",s);printf("\nt=%sv=%s\n",t,v);replace(s,t,v);printf("\n\nnewstring=%s\n",s);{inti,j,k,po,sl,tl;printf("\nsl=%dtl=%d\n",sl,tl);po=0;printf("\nk=%2d",k);po=k+tl;printf("pos=%2d",po);}{inti,j,sl,tl;i=pos;j=1;sl=strlen(s);tl=strlen(t);while(i<=sl&&j<=tl)字符串常量的提供有多种手段。可以在定义串类型同时初始化串值：的方法修改、调试、运行程序。熟悉稀疏矩阵的“三元组表”和“十字链表”存储结构，运用它们进行矩阵简单运算处理。稀疏矩阵的十字链表存储与输出。#include<stdio.h>#include<stdltypedefintEtype;typedefstructOLnode{inti,j;/*行号、列号域*/Etypee;}OLnode;typedefstruct}Crosslist;voidout_M(CrosslistMvoidout_M(Crosslist{inti;OLnode*p;charch；printf("\nm=%dn=%dt=%d\n",M.mu,M.nu,M.tu);if(p){printf("\ni=%d",i);while(p){printf("(%3d%3d%4d)",p=p->right;}}printf("\n");}printf(“\n打回车键，返回。“);ch=getch();}printf("\nm,n,t=?");scanf("%d,%d,%d",&m,&n,&t);for(i=1;i<=m;i++)M->rfor(j=1;j<=n;j++)M->ch[j]=NULL;M->mu=m;M->nu=n;M->tu=t;/*建立成空十字链表*/{printf("\ni,j,e=?");scp->i=row;p->j=col;p->e=va;q=M->rh[row];s=q;while(q!=NULL&&q->j<col){s=q;q=p->right=q;if(q==M->rh[row])M->rh[row]=p;elses->rwhile(q&&q->i<row){s=q;q=q->dowp->down=q;if(q==M->ch[col])M->ch[col]=p;elses-1.编写用“三元组表”存储（参见教科书P98页）稀疏矩阵，进行矩阵处理的程序。（1）矩阵转置（2）矩阵加2.上机调试上面给出的十字链表的程序，在此基础上增加查找功能：3.实现迷宫求解程序。1.熟练掌握二叉树在二叉链表存储结构中的常用遍历方法：先序递归遍历、中序递递归遍历。2.用树解决实际问题，如哈夫曼编码等。加深对“数据结构+算法=程序”的理解和认识，提高编写较复杂程序的能力。的序号（按满二叉树编号）和数据同时给出：序号数据元素。结合下图的二叉树数的输要输入。结合下图的二叉树数的输入据顺序应该是：点的左右子树。下列程序中的统计二叉树结点的函数，是对二叉树遍历方法的应用模仿练习。#include<stdio.h>/#include<stdlib.h>typedefstructBiTNode/*树结点结构*/\/\typedefstructBiTNode/*树结点结构*/\/\BiTNode*t;intn,n0,n1,n2,;{charch;intk;printf("\n\n1.建立二叉树方法1");printf("\n\n2.建立二叉树方法2");printf("\n\n3.中序递归遍历二叉树");printf("\n\n4.计算树中结点个数");printf("\n\n5.结束程序运行");printf("\n======================================");printf("\n请输入您的选择(1,2,3,4,5,6)"){case1:t=creat_bt1()case2:t=creat_bt2();break;/*调用递归建立二叉树算法printf("\n\n打回车键，继续。“);ch=getch();printf(“\n二叉树结点总数n=%d”,nprintf(“\n二叉树叶子结点数n0=%d”,n0printf(“\n度为2的结点printf("\n\n打回车键，继续。“);ch=getch();printf("\n----------------");printf("\n再见！");printf(“\n打回车键，返回。“);ch=getch();/*利用二叉树性质5，借助一维数组V建立二叉树*/{BiTNode*t,*p,*v[20];inti;Etypee;printf("\ni,data=?");scanf("%d%d",&i,&e);p->data=e;p->lch=NULL;p->rch=NULL;v[i]=p;if(i==1)t=p;else{j=i/2;if(i%2==0)v[j]->lch=p;/*序号为偶数elsev[j]->rch=p;/*序号为}printf("\ni,data=?");scanf("%d,%d",&i,&e);}printf("\ndata=");scanf("%d",&e);if(e==0)t=NULL;t->lch=creat_bt2(); t->rch=creat_bt2();}printf("%3d",p->data);}/*读者可以试着运用先序或后序递归if(p->lch==NULL&&p->lch==NULLif((p->lch==NULL&&p->lch!(p->lch!=NULL&&p->lch==Nif(p->lch!=NULL&&p->lch!=NULL}1.建立一棵二叉树，要求用先序非递归方法遍历二叉树。2.建立一棵二叉树，要求用“按层遍历”的方法遍历二叉树”的函数。3.给定一组值，建立一棵二叉树，求二叉数的树深。4.哈夫曼树问题。利用哈夫曼编码进行通讯可以大大提高信道利用率，缩短信息传输时间，的数据进行解码（复原）对于双工信道（即可以双向传输的信道每端都要有一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编译码系统。文，再输出该文的二进制码。[测试数据]用下表中给出的字符集和频度的实际统计数据建ABCDEFGHIJKLMN15OPQRSTUVWXYZ1811并实现以下报文的译码和输出：“THISPROGRAMISMYFAVORITE”。度优先遍历和广度优先遍历。进一步掌握递归算法的设计方法。程设计。（边上带权值的图）的邻接矩阵表示。typedefintVexType;typedefVexTypeMgraph[MAX][MAX];/*Mgraph是二维数组类型标识符*/voidcreat_mg(Mgraphvoidout_mg(MgraphMgraphG1;/*建立邻接矩阵*/voidcreat_mg(Mgraph{inti,j,k;for(j=1;j<=n;j++)G/*如果是网，G[i][j]=0该为G[i][j]=32767for(k=1;k<=e;k++)scanf(“%d%d”,&i,&j);G[i][j]=1;G[j][i]=1;}{inti,j,k;charch;for(i=1;i<=n;i++)for(j=1;j<=n;j++)printf(“%5d”}if(G[i][j]==1)printf(“\n存在边<%d,%d>printf("\n\n打回车键，继续。“);ch=getch();2.图的邻接链表存储及递归深度优先遍历。typedefintVexType;typedefstructVnode}Vnode;typedefVnodeLgraph[MAX];/*Lgraph是一维数组类型标识符*/voidcreat_L(Lgraphvoidout_L(LgraphGvoiddfsL(LgraphG,intv);LgraphGa;for(i=0;i<MAX;i++)vis[i]=0;/*顶点访问的标志数组*/creat_L(Ga);/*建立图邻接链表Ga*/out_L(Ga);printf("\n\n打回车键，继续。“);ch=getch();/*建立邻接链表*/voidcreat_L(Lgraph{Vnode*p,*q;inti,j,k;printf("输入n,e=?");scanf("%d,%d",&n,&ep->data=i;p->next=G[j].next;G[j].next=p;/*p结点链接到第j条链*/}voidout_L(LgraphG){inti;Vnode*p;charch;{printf("\ni=%d",i);p=G[i].next;}printf("\n\n打回车键，继续。“);ch=getch();voiddfsL(LgraphG,intv) printf("%3d",G[v].data);p=G[v].next;p=p->next;的更加具体详细）供参考。voidbfsL(Lgraphg,int{charch;printf("\n%d",g[v].data);vis[v]=1;enque(Q,v);while(Q.front!=Q.rep=g[x].next;vis[v]=1;enque(Q,}p=p->next;}}printf("\n\n打回车键，继续。“);ch=getch();1.阅读理解上面第一个关于图的邻接矩阵的程序，做下列题目。提示：无向图的邻接矩阵是对称的，而有向图的邻接矩阵是非对称的。提示：城市名暂时用代号（1，2，ⅆⅆ)表示，在程序中以数组的下标表示城市名。它的邻接矩阵如下：12345670∞∞∞0∞615∞∞∞∞∞02.调试运行上面第二个程序，即图的邻接链表存储的程序。解决下列问题。提示：有向图的邻接链表分为正邻接链表和逆邻接链表。运行调试程序。法的特点、使用范围和效率有进一步的了解。typedefintEtype;typedefstructBiTNode/*BiTNode*t;intn,n0,n1,n2,;{charch;intk;t=creat_bt();/*inorder(t);printf("\n输入data:");scanprintf(“\n打回车键，返回。“);ch=getch();33{intk;BiTNode*t=NULL,*s;{intk;BiTNode*t=NULL,*s;/inti,e; printf(“\nkey=?”);scanf(“%d”,&k);inti,e; {s=(BiTNode*)malloc(sizeof(BiTNode));建立后的二叉排序树s->data=k;s->lch=NULL;f=search(t,k);/*调用查找算法，f是待找结点的父结点指elsef->rch=s;}printf(“\nKey=?”);scanf(“%d”,&k);}/*查找算法，返回的是待找结点（e）的父结点指针，为插入提供条件*/p=NULL;q=root;}return(p);/*返回值是待voidsearchx(BiTNode*root,inte)p=NULL;q=root;elseif(k<=q->data)q=q->lch;}if(tag==1)printf(“\nyes!”);elseprintf(“\nno!”);/*中根遍历二叉排序树，结果应该是有printf(“name:%s\ttel:%s\n”,t□name,t□tel);display(t□rc);2.设有一组关键字(19,14,23,1,68,20,84,27,56,11,10,79)建,立一个哈希查找表。法解决冲突。熟悉几种典型的排序方法，并对各种算法的特点、使用范围了解。有广泛的应用。下面给出的是冒泡排序、快速排序的实现与比较。/*源程序的头文件sort.hvoidgetrandat(Dataary[],intcount)/*{longinta=100001;inti;for(i=0;i<count;i++){a=(a*125}voidprdata(Dataary[],intcount){inti;charch;printf(“\n”);for(i=0;i<count;i++)printf(“%6d”,arprintf(“\n”);printf(“\n\n打回车键，结束显示。“);ch=getch();#defineMAX1000typedefintElemType;/*关键字的类型typedefstructintshu;}Data;Dataar[MAX],br[Typedefstruct{intlo,hi;}Selem;typedefstructinttop;/*}SqStack;voidbubble(Dataary[],intn)voidqksort(Dataary[],intn)voidhoare(Dataary[],intl,inth)voidpush(SqStack*s,Seleme)/*进栈一个元素*/intempty(SqStacks){intk,n,j;j;charch;printf("\n\n1.printf("\n\n2.一般情况的起泡排序")；printf("\n\n3.有序情况的起泡排序")；printf("\n\n4.一般情况的快速排序")；printf("\n\n5.有序情况的快速排序")；printf("\n\n6.结束程序运行");printf("\n======================================");for(j=0;j<n;j++)br[j]prdata(ar,n);case2:{for(j=0;j<n;j++)ar[j]=br[j];bubble(ar,n);prdata(ar,n);prdata(ar,n);case4:{for(j=0;j<n;j++)ar[j]qksort(ar,n);prdata(ar,n);case5:{qksort(ar,n);prdata(ar,n);printf("\n----------------");printf("\n再见！")printf(“\n打回车键，返回。“);ch=getch();voidbubble(Dataary[],intn){inti,j,tag;Dtatax;if(ary[j].key>ary[j+1].key)voidqksort(Dataary[],intn)init_s(&s1);push(&s1,x);}}voidhoare(intary[],intl,inth){inti,j;Datax;i=l;j=h;x=ary[l];do{while((i<j)&&ary[j]>=x)j--;while((i<j)&&ary[i]<=x)iary[i]=x;return(i);/voidinit_s(SqStack*s)voidpush(SqStack*s,Seleme){if(s->top==MAX-1)prin}if(s->top==0){printf(“\nsatckEmpty!\n”);} 中左分区中的数据均小于等于ary[i].key，而右分区中的数据均大于等于ary[i].key（l≤i≤例：入栈时，要两个参数即右区首、尾指针组成的结构体变量入栈。快速排序的最坏情况亦即各元素已有序时，再进行快速排序，这种情况下录关键字无序的情况。排序因其应用广泛，所以人们在排序找方面的研究经久不衰。1.编写程序实现简单选择排序、堆排序（或归并排序），进行比较分析。2.编写程序实现简单插入排序、希尔排序（或基数排序），进行比较分析，第三部分书面作业练习题1.数据结构是一门研究非数值计算的程序设计问题中计算机的□以及它们之间的□和运算等的学科。2.数据结构被形式地定义为（K，R其中K是□的有限集合，R是K上的□有限集合。3.在数据结构中，从逻辑上可以把数据结构分成□。4.线性表的顺序存储结构是一种□的存储结构，线性表的链式存储结构是一种□的存储结构。5.算法分析的目的是□,算法分析的两个主要方面是□。A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性6.计算机算法指的是□,它必具备输入、输出和□等五个特性。□A.计算方法B.排序C.解决问题的有限运算序列D.调度方法□A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是一致的，这种说法□。8.线性表若采用链式存储结构时，要求内存中可用存储单元的地址□。C.一定是不连续的D.连续或不连续都可以9.在以下的叙述中，正确的是□。B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法□。1.数据逻辑结构包括□、□和□三种类型，树形结构和图形结构合称为□。2.在线性结构中，第一个结点□前驱结点，其余每个结点有且只有□个前驱结点；最后一个结点□后续结点，其余每个结点有且只有□个后续结点。3.在树形结构中，树根结点没有□结点，其余每个结点有且只有□个前驱结点，叶子结点没有□结点，其余每个结点的后续结点可以□。4.在图形结构中，每个结点的前驱结点数和后续结点数可以□。5.线性结构中元素之间存在□关系，树形结构中元素之间存在□关系，图形结构中元素之间存在□关系。6.算法的五个重要特性是。8.下面程序段的时间复杂度是□。}1.21.线性结构、 1A.iBA.顺序存储结构和链式存储结构B.散列方式和索引方式C.链表存储结构和数组A.QU—>rear—QU—>frontB.QU—>rear—QU—>front-1==m0C.QU—>front==QU—>rearD.QU—>front==QU—A.((QU—>rear-QU—>front)+Maxsize)%Maxsize==m0A.(rear-front+m)%mB.rear-fronC.rear-front-1D.r2.2填空题（将正确的答案填在2.向一个长度为n的向量的第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移动____个元素。3.向一个长度为n的向量中删除第i个元素（1≤i≤n）时，需向前移动____个元素。4.向栈中压入元素的操作是___