软件基础实验指导(学生版)

计算机软件基础实验指导书PAGE计算机软件基础实验指导书－C语言实现孙旭霞张晋辉薛旭西安理工大学自动化与信息工程学院二0一一年六月计算机软件基础实验指导书目录实验大纲……...……………….……1实验报告要求……...……………….3实验一顺序表的基本操作………4实验二单链表的基本操作……………..……….….5实验三堆栈的基本操作……………..…………….10实验四循环队列的基本操作……………..…………..…………..14实验五稀疏矩阵的转置………...18实验六二叉排序树的建立与遍历………..……….22实验七直接插入排序………..…….24实验八直接选择排序……..……….26实验九顺序查找和折半查找……...28实验十二叉排序树查找…………………..……….32PAGE36《计算机软件基础》课程实验教学大纲一、制定实验教学大纲的依据根据本校最新指定的《计算机软件基础》课程教学大纲制定二、本课程实验教学在培养实验能力中的地位和作用〈计算机软件基础〉课程主要研究计算机处理数据时数据的结构及其实现方法，是一门有关计算机软件知识及开发技术的专业基础课。其主要任务是使学生深入了解计算机软件，正确选用与使用计算机软件，培养分析、设计新计算机软件的能力以及解决实际问题的能力。实验课是本课程重要的教学环节,其目的是使学生掌握常用的数据结构的使用方法，接受编制基本程序技能的训练，提高学生编制复杂程序的能力。三、应达到的实验能力标准1、掌握线性表的概念、线性表的顺序存储结构、线性表的链式存储结构及其操作运算。2、掌握堆栈和队列的概念、存储结构和操作运算的算法。3、了解数组的定义和存储结构及其操作运算的算法，学会矩阵的压缩存储方式。4、掌握二叉树的概念、性质及二叉树的遍历算法5、掌握插入排序算法，选择排序算法和交换排序算法。6、掌握顺序表的查找，树表的动态查找及哈希表查找算法。四、学时、教学文件学时：本课程总学时为54学时,其中实验为22学时,占总学时的24.5%。教学文件：校编〈软件基础实验指导书〉；实验报告学生自拟。要求学生实验前预习实验内容，按照每个实验任务要求画出软件流程图，编制相应的软件程序。指导教师指导学生解决在调试程序中出现的问题，具体软件的测试数据由学生独立完成。五、实验考核办法与成绩评定实验课成绩占本课程总成绩20%，对无故缺勤三次以上实验者，本课程不予通过。六、仪器设备及注意事项仪器设备：个人计算机注意事项：注意保护设备七、实验项目的设置及学时分配序号实验项目及内容学时性质要求适用专业1顺序表的插入和删除2验证必修信息类，通信类，控制类2链表的插入和删除2设计必修同上3堆栈的插入和删除2验证必修同上4队列的插入和删除2验证必修同上5对称矩阵和三角矩阵的压缩存储2验证必修同上6二叉树的遍历（前序遍历、中序遍历和后序遍历）4设计必修同上7插入排序和选择排序2验证必修同上8交换排序（冒泡排序和快速排序）2验证必修同上9顺序查找和二分查找2验证必修同上10二叉排序树查找2验证必修同上共计22同上实验报告要求实验目的；实验内容；程序流程图；设计部分程序；实验结果（要求检测所有情况的正确性，写出测试条件及相应的测试结果）；完成思考题。实验一顺序表的基本操作(2学时)一、实验目的了解顺序表的逻辑特征，掌握顺序表的描述方法、特点及有关的概念，掌握顺序表上的插入和删除等基本操作算法。二、实验内容在顺序表List[]中，实现顺序表的基本操作，包括：初始化顺序表，在表中插入元素、删除元素。基本要求：初始化顺序表；程序具有顺序表插入、删除和显示功能，可根据用户需要连续操作（插入、删除位置及要插入元素数值均从键盘输入）；任一操作结束后将顺序表中的内容输出；程序能检测并提示发生上溢或下溢错误。可由用户选择退出程序。三、实验要点及说明顺序表又称为线性表的顺序存储结构，它是用一组地址连续的存储单元依次存放线性表的各个元素。可按如下格式定义顺序表：#defineMAXLEN10/*定义顺序表最大元素个数50*/typedefintdatatype;typedefstruct{datatypeList[MAXLEN];/*定义顺序表List*/intNum;/*定义顺序表表长（1~MAXLEN）*/}Seqlist;模块划分：（1）initiq(Seqlist*la)函数：初始化顺序表操作前提：la为未初始化线性表。操作结果：将la初始化为空表。（2）insertq(la,i,e)函数：实现插入功能操作前提：表la已存在，e为合法元素值，1≤i≤ListLength(la)+1。操作结果：在la中第i个位置插入新的数据元素e，la的长度加1。（3）deleteq(la,i,e)函数：实现删除功能操作前提：表la已存在且非空，1≤i≤ListLength(la)。操作结果：删除la的第i个数据元素，并用e返回其值，la的长度减1。（4）print()函数：实现输出功能四、参考源程序#include<stdio.h>#defineMAXLEN10typedefintdatatype;typedefstruct{datatypeList[MAXLEN];intNum;//Num:1~MAXLEN}Seqlist;voidinitiq(Seqlist*la);intinsertq(Seqlist*la,inti,datatypee);intdeleteq(Seqlist*la,inti,datatype*e);intprint(Seqlist*la);voidmain(){Seqlistla;datatypee; ints,n,i;/*s选择操作功能，i插入或删除数据的位置*/ printf("请输入你的选择:1initiate2insert3delete4print5exit\nyourchoice="); scanf("%d",&s); while(s!=5) {if(s==1) {initiq(&la); printf("完成初始化!\n");} elseif(s==2) {printf("请输入待插入的数据位置:"); scanf("%d",&i); printf("请输入待插入的数据值:"); scanf("%d",&e); n=insertq(&la,i,e); if(n!=0) print(&la); } elseif(s==3) {printf("请输入待删除的数据位置:"); scanf("%d",&i); n=deleteq(&la,i,&e);if(n!=0) {printf("已删除的数据为:%d",e); print(&la); } } elseif(s==4) print(&la); else printf("你的选择是错误的!\n"); printf("请输入你的选择:1initiate2insert3delete4print5exit\nyourchoice="); scanf("%d",&s);}}/*初始化*/voidinitiq(Seqlist*la){}/*插入*/intinsertq(Seqlist*la,inti,datatypee)/*i插入位置:0~Num，*/{}/*删除*/intdeleteq(Seqlist*la,inti,datatype*e){}/*显示输出*/intprint(Seqlist*la){intm; if(la->Num<=0) {printf("顺序表为空!\n"); return0;} else {printf("当前的顺序表为:\n"); for(m=0;m<la->Num;m++) printf("List[%d]=%d",m,la->List[m]); printf("\n表长为%d\n",la->Num); return1;}}五、思考题1．在以上参考程序基础上，增加按数据元素值（key）前插入和删除功能。2．设顺序表L中的数据元素按递增排列，编写一个算法，将数据元素x插入到顺序表L的适当位置上，以保持顺序表的有序性。3．设计一算法实现删除顺序表a中第i个元素起的k个元素。typedefstruct{intdatatype[100];intlength;/*顺序表的长度*/}SqList;4．设已有线性表la的数据结构定义同上，编写一个算法，删除顺序表la中所有值为x的数据元素。5．编写一个算法，实现将两个不同的顺序表复制到一个顺序表中。实验二单链表的基本操作（2学时）一、实验目的了解链表的逻辑结构特征，掌握链表的描述方法、特点及有关概念，掌握链表的建立、插入、删除以及查找的基本操作算法。二、实验内容实现单链表的基本操作，包括：建立单链表，插入结点，删除结点，查找结点，打印输出单链表中的所有结点。基本要求：（1）初始化单链表；（2）程序具有单链表插入、删除和显示功能，可根据用户需要连续操作（插入位置、插入结点的数据及被删除结点的数据要从键盘输入）；（3）根据键盘输入的数据在单链表中查找结点；（4）任一操作结束后将单链表中的内容输出；（5）可由用户选择退出程序。三、实验要点及说明线性表的链式存储结构是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接的次序实现的。线性表的链式存储结构中只有一个指针域的链表称为单链表。可按如下格式定义单链表的结点结构：typedefstructnode{datatypedata;/*结点数据域*/structnode*next;/*结点指针域*/}slnode；划分各功能模块：（1）initiate(slnode**h)函数：初始化单链表（2）intCreat1(slnode*h,intn)函数：建立单链表（3）insert(slnode*h,inti,datatypex)函数：在带头结点的单链表h中第i个位置前插入新结点x。（4）delete(slnode*h,inti)函数：删除第i个位置的结点（5）search(slnode*h,inti)函数：查找第i个位置结点的值。（6）print(slnode*h)函数：显示输出单链表中的所有结点。四、参考源程序#include<stdio.h>#include<malloc.h>#include<stdlib.h>typedefintdatatype;typedefstructnode{datatypedata; structnode*next;}slnode;//intl;/*保存查找到的结点位置*/intinitiate(slnode**h);intCreat1(slnode*h);intinsert(slnode*h,inti,datatypex);intdeletet(slnode*h,inti,datatype*x);slnode*search(slnode*h,datatypex);voidprint(slnode*h);voidmain(){slnode*h,*s; intsel,state,x,i;/*sel操作选择，x要查找的结点数据，i结点位置*///initiate(&h); printf("请输入你的选择:1initiate2Creat3insert4delete5search6print7exit\nyourchoice="); scanf("%d",&sel);while(sel!=1) {printf("先进行初始化操作\n"); printf("请输入你的选择:1initiate2Creat3insert4delete5search6print7exit\nyourchoice="); scanf("%d",&sel); } while(sel!=7) {if(sel==1) {if(state=initiate(&h)==0) printf("操作失败");} elseif(sel==2) {if(state=Creat1(h)==1)print(h); elseprintf("操作失败");} elseif(sel==3) {printf("请输入待插入的结点位置:"); scanf("%d",&i); printf("请输入待插入的结点值:"); scanf("%d",&x); if(state=insert(h,i,x)==1) print(h); elseprintf("操作失败\n");} elseif(sel==4) {printf("请输入待删除结点的位置:"); scanf("%d",&i); if(state=deletet(h,i,&x)==1) {printf("被删除结点值:%d\n",x); print(h);}elseprintf("操作失败\n");} elseif(sel==5) {printf("请输入要查找的结点数据:"); scanf("%d",&x); s=search(h,x); if(s!=NULL) printf("查找成功，结点位置为：%d\n",s->data); elseprintf("操作失败\n"); } elseif(sel==6) {print(h);} else printf("你的选择是错误的!\n"); printf("请输入你的选择:1initiate2Creat3insert4delete5search6print7exit\nyourchoice="); scanf("%d",&sel);}}/*初始化*/intinitiate(slnode**h){}/*建立单链表*/intCreat1(slnode*h){}/*插入*/intinsert(slnode*h,inti,datatypex)/*i插入结点的位置*//*x插入结点的数据*/{}/*删除*/intdeletet(slnode*h,inti,datatype*x)/*x存放被删除结点的数据*/{}/*查找*/slnode*search(slnode*h,datatypex){}/*显示输出*/voidprint(slnode*h){slnode*p; inti; p=h->next; i=0; printf("\n当前的单链表数据内容为:\n"); while(p!=NULL) {i++; printf("第%d个数据：%d\n",i,p->data); p=p->next;} printf("\n线性表的表长为%d\n",i);}五、思考题在以上参考程序基础上，增加按数据元素值（key）前插入和删除功能。编写一个算法，删除单链表中值相同的多余结点。实现单链表的就地逆序，设其头结点指针为head，编写一个算法将单链表逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。假设现有一个带头结点的单链表head，试写出将单链表中结点数据值为偶数的结点，复制并放入另一个带头结点的单链表head1的头部的算法。设现有一个带头结点的单链表（头指针为head），试写出一算法，删除该单链表中数据为奇数的所有结点。修改print(slnode*h)函数，使其显示输出单链表中的所有结点的数据域和地址域。实验三堆栈的基本操作（2学时）一、实验目的了解堆栈的顺序逻辑结构特征，掌握堆栈的描述方法、特点及有关概念，掌握堆栈的建立、插入、删除等基本操作算法。二、实验内容实现顺序堆栈的基本操作，包括：初始化堆栈，进栈，出栈，取栈顶元素。基本要求：（1）顺序堆栈的元素个数可随意设定；（2）可连续测试任意多个元素的进栈、出栈操作；（3）可实现取栈顶元素；（4）任一操作结束后将顺序堆栈中的内容输出；（5）可由用户选择退出程序。三、实验要点及说明栈的逻辑结构和线性表相同，但运算规则与线性表相比有了更多的限制，故又称操作受限的线性表。栈是一种只允许在表的一端进行插入或删除操作的线性表。只允许插入，删除操作的一端称为栈顶，另一端称为栈底，栈顶当前位置是由一个栈顶指示器指示；插入操作称为进栈或入栈，删除操作称为出栈或退栈；当栈中没有任何元素时称为空栈。可按如下格式定义堆栈的顺序存储结构：#defineMAX10/*定义顺序堆栈最大元素个数*/typedefstruct{datatypestack[MAX];/*定义顺序堆栈stack*/inttop;/*定义栈顶指示器*/}seqstack;模块划分：（1）initiate()函数：初始化顺序堆栈（2）push()函数：进栈操作（3）pop()函数：出栈操作（4）stacktop()函数：取栈顶元素（5）print()函数：显示输出栈内元素四、参考源程序#include<stdio.h>#include<malloc.h>#defineMAX10typedefintdatatype;typedefstruct{datatypestack[MAX];inttop;}seqstack;voidinitiate(seqstack*s);intpush(seqstack*s,datatypex);intpop(seqstack*s,datatypex);intstacktop(seqstack*s);voidprint(seqstack*s);intmain(){seqstack*s; intsel,state;/*sel选择输入，state进栈或出栈数据成功与否的标志*/datatypex; if((s=(seqstack*)malloc(sizeof(seqstack)))==NULL) {printf("申请空间错误！\n"); return0;} initiate(s); printf("完成初始化!\n"); printf("请输入你的选择:1initiate2push3pop4stacktop5print6exit\nyourchoice="); scanf("%d",&sel); while(sel!=6) {if(sel==1) {initiate(s); printf("完成重新初始化!\n");} elseif(sel==2) {printf("请输入待进栈的数据值:"); scanf("%d",&x); if(state=push(s,x)==1) print(s); elseprintf("进栈失败!\n"); } elseif(sel==3) { if(state=pop(s,x)==1) print(s); elseprintf("出栈失败!\n"); } elseif(sel==4) {if(state=stacktop(s)==1) print(s); elseprintf("取栈顶元素失败!\n");} elseif(sel==5) {print(s);} else printf("你的选择是错误的!\n"); printf("请输入你的选择:1initiate2push3pop4stacktop5print6exit\nyourchoice="); scanf("%d",&sel);} return1;}/*初始化*/voidinitiate(seqstack*s){}/*进栈*/intpush(seqstack*s,datatypex){}/*出栈*/intpop(seqstack*s,datatypex){}/*取栈顶元素*/intstacktop(seqstack*s){}/*显示输出*/voidprint(seqstack*s){inti; if(s->top==-1) printf("栈空！\n"); else for(i=0;i<=s->top;i++) printf("stack[%d]为：%d\n",i,s->stack[i]);}五、思考题1.如果初始化栈指针s->top=0则进栈的push()函数应如何修改？2．若进栈函数采用intpush(seqstacks,datatype*x);和intpop(seqstacks,datatype*x)，程序应如何修改？3．设两个栈（stack1，stack2）共享一个一维数组空间s[m]，它们的栈底分别设在数组的两端，试编写一算法，从键盘输入一个整数x，该数大于100时放入stack2，否则放入stack1。stack1stack2stack1stack2top1top201m-1s[m]typedefstructstack{ints[m];inttop1;inttop2;}STACK;STACK*p;

实验四循环队列的基本操作（2学时）一、实验目的了解循环队列的顺序逻辑结构的定义及基本操作，掌握队列的描述方法、特点及有关概念。二、实验内容实现顺序循环队列的基本操作，包括：建立循环队列，元素入队，元素出队等。基本要求：（1）正确判断循环队列队满、队空的情况；（2）可连续测试任意多个元素的入队、出队操作；（3）可实现取队头元素；（4）任一操作结束后将队列中的内容输出；（5）可由用户选择退出程序。三、实验要点及说明队列是一种只允许在表的一端进行插入操作而在另一端进行删除操作的线性表。队列的插入操作通常称为进队或入队，队列的删除操作通常称为退队或出队。表中允许进行插入操作的一端称为队尾，允许进行删除操作的一端称为队头，队头和队尾分别由队头指针q->front和队尾指针q->rear指示。当队列中没有数据元素时称为空队。解决顺序队列假溢出的方法是采用循环队列，即将队列的首尾相接。当q->rear=q->front时，队列为空；当(q->rear+1)%maxnum=q->front时，队列为满，即牺牲一个数据元素空间作为队满标志。可按如下格式定义顺序循环队列结构：#defineMAX10/*定义顺序循环队列最大元素个数10*/typedefstruct{datatypequeue[MAX];/*定义顺序循环队列queue*/intfront;/*定义队头指示器*/intrear;/*定义队尾指示器*/}sequeue;模块划分：（1）initiate(sequeue*s)函数：初始化顺序循环队列（2）intaddqueue(sequeue*s,datatypex)函数：入队操作（3）intdelqueue(sequeue*s,datatypex)函数：出队操作（4）intgettop(sequeue*s)函数：取队头元素（5）print()函数：显示输出四、参考源程序#include<stdio.h>#include<malloc.h>#include<stdlib.h>#defineMAX4typedefintdatatype;typedefstruct{datatypequeue[MAX]; intfront; intrear;}sequeue;voidinitiate(sequeue*s);intaddqueue(sequeue*s,datatypex);intdelqueue(sequeue*s,datatypex);intgettop(sequeue*s);voidprint(sequeue*s);intmain(){sequeue*s; intsel,state;/*sel选择输入，state：进队或出队数据成功*/datatypex; if((s=(sequeue*)malloc(sizeof(sequeue)))==NULL) {printf("申请空间错误！\n"); return0;} initiate(s); printf("完成初始化!\n"); printf("\n请输入你的选择:1initiate2addqueue3delqueue4gettop5print6exit\nyourchoice="); scanf("%d",&sel); while(sel!=6) {if(sel==1) {initiate(s); printf("完成初始化!\n");} elseif(sel==2) {printf("\n请输入待入队的数据值:"); scanf("%d",&x); if(state=addqueue(s,x)==1) print(s); elseprintf("进队失败!\n"); } elseif(sel==3) {if( state=delqueue(s,x)==1) print(s); elseprintf("出队失败!\n"); } elseif(sel==4) {if(state=gettop(s)==1) print(s); elseprintf("取队头元素失败!\n"); } elseif(sel==5) print(s); else printf("你的选择是错误的!\n"); printf("\n请输入你的选择:1initiate2addqueue3delqueue4gettop5print6exit\nyourchoice="); scanf("%d",&sel);} return1;}/*初始化*/voidinitiate(sequeue*s){}/*入队*/intaddqueue(sequeue*s,datatypex){}/*出队*/intdelqueue(sequeue*s,datatypex){}/*取队头元素*/intgettop(sequeue*s){}/*显示输出队*/voidprint(sequeue*s){intm; m=s->front;/*下标*/ if(s->front==s->rear)/*判队空条件*/ printf("队空!无显示输出!\n"); else {while(m!=s->rear) {m=(m+1)%MAX; printf("queue[%d]数据为：%d\n",m,s->queue[m]);} }}五、思考题1．除了循环队列，还有哪些方法可以解决顺序队列“假溢出”的问题？2．如果循环队列的下标不是从0到n-1，而是从1到n，那么入队、出队操作应如何修改？判断队满的条件又应如何修改？实验五稀疏矩阵的转置一、实验目的熟悉数组的有关概念，能熟练掌握稀疏矩阵的三元组存储结构的转置方法。二、实验内容用三元组顺序表存储结构存储稀疏矩阵，实现稀疏矩阵的转置运算。基本要求：（1）稀疏矩阵通过键盘输入；（2）建立稀疏矩阵的三元组顺序表；（3）实现稀疏矩阵三元组顺序表的转置；（4）输出转置前后的稀疏矩阵；（5）可由用户选择退出程序。三、实验要点及说明以二维数组的形式从键盘输入稀疏矩阵，由程序完成三元组顺序表、顺序表的转置。原稀疏矩阵三元组顺序表按先行序后列序的次序存放，转置后的稀疏矩阵三元组顺序表仍然按先行序后列序的次序存放。可按如下格式定义三元组顺序表结构：typedefstruct{intp;/*行号*/intq;/*列号*/datatypex;/*元素值*/}List;三元组顺序表的控制数据结构：typedefstruct{intmd;/*行数*/intnd;/*列数*/inttd;/*非零元素个数*/}tabletype;模块划分：（1）input()函数：输入稀疏矩阵（2）setup()函数：建立三元组顺序表（3）transition()函数：转置（4）print1()函数：矩阵输出（5）print2()函数：三元组顺序表输出四、参考源程序#include<stdio.h>#include<malloc.h>#definemaxsize50typedefintdatatype;typedefstruct{intp,q;datatypex;}List;typedefstruct{intmd,nd,td;}tabletype;intn,m;/*稀疏矩阵的行数、列数*/voidinput(datatypea[maxsize][maxsize]);voidsetup(datatypea[maxsize][maxsize],Listta[],tabletype*ta1);voidtransition(tabletype*ta1,tabletype*tb1,Listta[],Listtb[]);voidprint1(datatypea[maxsize][maxsize]);voidprint2(Lista[],intnn);intmain(){datatypea[maxsize][maxsize];/*稀疏矩阵*/ Listta[maxsize],tb[maxsize];/*三元组顺序表*/ tabletype*ta1,*tb1; intsel;/*选择输入*/ if((ta1=(tabletype*)malloc(sizeof(tabletype)))==NULL) {printf("申请空间错误！\n"); return0;}if((tb1=(tabletype*)malloc(sizeof(tabletype)))==NULL) {printf("申请空间错误！\n"); return0;} printf("请输入你的选择：1开始其它选择为退出\nyourchoice="); scanf("%d",&sel); while(sel==1) {input(a); setup(a,ta,ta1); transition(ta1,tb1,ta,tb); printf("\n原稀疏矩阵：\n"); print1(a); printf("\n原三元组顺序表：\n"); print2(ta,ta1->td); printf("\n转置后的三元组顺序表：\n"); print2(tb,tb1->td); printf("请输入你的选择：1开始其它选择为退出\nyourchoice="); scanf("%d",&sel);} return1;}/*输入*/voidinput(datatypea[maxsize][maxsize]){inti,j; printf("\n预输入的稀疏矩阵的行数＝"); scanf("%d",&n);printf("\n预输入的稀疏矩阵的列数＝"); scanf("%d",&m); for(i=0;i<n;i++) for(j=0;j<m;j++) {printf("\n请输入数据a[%d][%d]=",i,j); scanf("%d",&a[i][j]);}}/*建立*/voidsetup(datatypea[maxsize][maxsize],Listta[],tabletype*ta1){inti,j; ta1->td=0;/*初始化非零元素个数*/ for(i=0;i<n;i++) for(j=0;j<m;j++) if(a[i][j]!=0) {ta[ta1->td].p=i; ta[ta1->td].q=j; ta[ta1->td].x=a[i][j]; ta1->td++;} ta1->md=n; ta1->nd=m;}/*转置*/voidtransition(tabletype*ta1,tabletype*tb1,Listta[],Listtb[]){inti,j,nn=0; tb1->md=ta1->nd; tb1->nd=ta1->md;tb1->td=ta1->td; if(ta1->td!=0) for(i=0;i<ta1->nd;i++)/*i原矩阵的列下标*/ for(j=0;j<ta1->td;j++)/*j原三元组顺序表的下标*/ if(ta[j].q==i)/*寻找原矩阵中最小列下标*/ {tb[nn].p=ta[j].q; tb[nn].q=ta[j].p; tb[nn].x=ta[j].x; nn++;}}/*矩阵输出*/voidprint1(datatypea[maxsize][maxsize]){inti,j; for(i=0;i<n;i++) {for(j=0;j<m;j++) printf("%d",a[i][j]); printf("\n");}}/*三元组顺序表输出*/voidprint2(Lista[],intnn){inti; printf("\t行号\t列号\t元素值\n"); for(i=0;i<nn;i++) printf("\t%d\t%d\t%d\n",a[i].p,a[i].q,a[i].x);}五、思考题1．修改上面的实验程序，增加显示转置后的矩阵输出功能。2．采用三元组存储稀疏矩阵的目的是什么？3．稀疏矩阵A和B（分别为m×n和n×1矩阵）采用三元组表示，用程序实现C=A*B的计算,要求C也采用三元组表示。实验六二叉树的建立、插入、删除与遍历（4学时）一、实验目的了解二叉树的定义及基本运算，掌握二叉树的描述方法、特点、性质及存储结构；掌握二叉树的基本操作算法（包括查找、插入、删除和遍历等操作）。二、实验内容根据用户通过键盘给定数据建立二叉树，并对此二叉树进行查找、插入、删除和遍历等操作，遍历方式有前序、中序、后序遍历三种。基本要求：（1）用户可通过键盘任意选择各种操作；（2）用户可由键盘给定数据建立二叉树；（3）分别显示树型结构和存储地址；（4）查找某结点的地址；（5）插入或删除某结点；（6）进行二叉树遍历，遍历方式可由用户选择；（7）输出遍历结果；（8）可由用户选择退出程序。三、实验要点及说明用链式存储结构存储一个二叉树，首先应建立根结点，其他结点可根据用户选择插入到根结点的左右子树中。二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且只被访问一次。常用的二叉树遍历方法如下：前序遍历：访问次序：根→左→右，中序遍历：访问次序：左→根→右，后序遍历：访问次序：左→右→根。要求用户操作界面如图所示：可按如下格式定义二叉树的链式存储结构：typedefstructbtreenode{datatypedata;structbtreenode*lchild;structbtreenode*rchild;}nodetype;模块划分：（1）intinitiate(nodetype**bt)：初始化（2）nodetype*create(nodetype*bt,elemtypex)：建立只有根结点的二叉树（3）nodetype*insertl(elemtypex,nodetype*parent)：将结点x插入到结点parent的左孩子结点（4）nodetype*insertr(elemtypex,nodetype*parent)：将结点x插入到结点parent的右孩子结点（5）nodetype*insert(nodetype*bt)：（6）nodetype*deleted(nodetype*bt)：删除（7）voidprinttree(nodetype*bt,intn)：屏幕显示树（凹入表形式）voidprintftree(nodetype*bt)：屏幕显示树的存储结构（8）preorder(nodetype*bt)：前序遍历（9）inorder(nodetype*bt)：中序遍历（10）postorder(nodetype*bt)：后续遍历这个实验作为设计性实验，参考程序中只给出模块函数，需自己编写主函数和遍历函数，并进行功能调试。四、参考源程序/*建立只有根结点的二叉树*//*初始化*/intinitiate(nodetype**bt){ }/*创建二叉树*/nodetype*create(nodetype*bt,elemtypex){}/*前序遍历二叉树*/voidpreorder(nodetype*bt){ }/*查找数据*/nodetype*search(nodetype*bt,elemtypex){ }/*插入*/nodetype*insertl(elemtypex,nodetype*parent)/*将结点x插入到结点parent的左孩子结点*/{ }nodetype*insertr(elemtypex,nodetype*parent)/*将结点x插入到结点parent的右孩子结点*/{}nodetype*insert(nodetype*bt){ charx,y,z;nodetype*parent,*p; printf("输入您要插入的字符.\n"); scanf("%s",&x); printf("请选择您要插入的结点的双亲.\n"); scanf("%s",&y); parent=search(bt,y); printf("left(l)orright(r).\n"); scanf("%s",&z); if(z=='l'){ if((p=insertl(x,parent))==NULL) { printf("\n内存不够"); exit(0); } } if(z=='r'){ if((p=insertr(x,parent))==NULL) { printf("\n内存不够"); exit(0); } } returnp;}/*删除*/nodetype*deleted(nodetype*bt){ }/*屏幕显示树*/voidprinttree(nodetype*bt,intn){ inti; if(bt==NULL)return; printtree(bt->rchild,n+1); for(i=0;i<n-1;++i)printf(""); if(n>=1)printf("---"); printf("%c\n",bt->data); printtree(bt->lchild,n+1);}voidprintftree(nodetype*bt){ if(bt==NULL)return; printf("%-20c%-20p%-20p%-20p\n",bt->data,bt,bt->lchild,bt->rchild); printftree(bt->lchild); printftree(bt->rchild);}五、思考题1．请用先序、中序、后序遍历算法中的任一算法改成统计二叉树中数据元素值为x的结点个数的算法。2．请用先序、中序、后序遍历算法中的任一算法改成统计二叉树中叶子结点个数的算法。3.编写计算二叉树深度的算法。实验七直接插入排序（2学时）一、实验目的掌握直接插入排序的基本思想、排序过程及其实现的算法。二、实验内容对于一组给定关键字序列，用直接插入排序算法对其进行排序并显示结果。基本要求：（1）给定关键字序列通过键盘任意输入；（2）输出排序结果；（3）可由用户选择退出程序。三、实验要点及说明直接插入排序就是顺序地把待排序列的各个元素按其关键字的大小插入到已排序序列的适当位置。当待排序列元素个数为n时，只需进行n-1次比较，所以，关键字的选取从待排序列的第二个元素开始，直到最后一个元素结束。可按如下格式定义记录的结构：typedefstruct{intkey;Chardata;}datatype;模块划分：（1）getsort()函数：输入记录的关键字（2）insertsort()函数：直接插入排序四、参考源程序#include<stdio.h>#defineMAX50typedefstruct{intkey;chardata;}datatype;intgetsort(datatypex[]);voidinsertsort(datatypex[],intn);voidmain(){datatypex[MAX]; intn,sel,i;/*sel输入选择，n排序记录的长度*/ printf("请输入你的选择：1开始其它选择为退出\nyourchoice="); scanf("%d",&sel); while(sel==1) {printf("\n请输入关键字序列，以-1结束输入："); n=getsort(x); printf("\n排序前的结果为："); for(i=0;i<n;i++) printf("%d\t",x[i].key); printf("\n"); insertsort(x,n); printf("\n直接插入排序后的结果为："); for(i=0;i<n;i++) printf("%d\t",x[i].key); printf("\n"); printf("请输入你的选择：1开始其它选择为退出\nyourchoice="); scanf("%d",&sel);}}/*输入记录的关键字*/intgetsort(datatypex[]){inti=0; scanf("%d",&x[i].key); while(x[i].key!=-1) {i++;scanf("%d",&x[i].key);} returni;}/*直接插入排序*/voidinsertsort(datatypex[],intn){}五、思考题1．直接插入排序的时间复杂度为多少？，在什么情况排序速度最快？2．直接插入排序是否是稳定排序算法？实验八直接选择排序（2学时）一、实验目的掌握直接选择排序的基本思想、排序过程及其实现的算法。二、实验内容对于一组给定关键字序列，用直接选择排序算法对其进行排序并显示结果。基本要求：（1）给定关键字序列通过键盘任意输入；（2）输出排序结果；（3）可由用户选择退出程序。三、实验要点及说明直接选择排序就是不断地从待排序的序列中选取关键字最小的记录放到已排序记录序列的后面，直到序列中所有记录都已排序为止。当待排序列元素个数为n时，第一次排序要进行n-1次比较，第二次排序要进行n-2次比较，每进行一次排序比较次数减小一次，参考程序中，外循环用于控制排序趟数，内循环用于查找当前关键字最小的记录。可按如下格式定义记录的结构：typedefstruct{intkey;Chardata;}datatype;模块划分：（1）getsort()函数：输入记录的关键字（2）selectsort()函数：直接选择排序四、参考源程序#include<stdio.h>#defineMAX50typedefstruct{intkey;chardata;}datatype;intgetsort(datatypex[]);voidselectsort(datatypex[],intn);voidmain(){datatypex[MAX]; intn,sel,i;/*sel输入选择，n排序记录的长度*/ printf("请输入你的选择：1开始其它选择为退出\nyourchoice="); scanf("%d",&sel); while(sel==1) {printf("\n请输入关键字序列，以-1结束输入："); n=getsort(x); printf("\n排序前的结果为："); for(i=0;i<n;i++) printf("%d\t",x[i].key); printf("\n"); selectsort(x,n); printf("\n直接选择排序后的结果为："); for(i=0;i<n;i++) printf("%d\t",x[i].key); printf("\n"); printf("请输入你的选择：1开始其它选择为退出\nyourchoice="); scanf("%d",&sel);}}/*输入记录的关键字*/intgetsort(datatypex[]){inti=0; scanf("%d",&x[i].key); while(x[i].key!=-1) {i++;scanf("%d",&x[i].key);} returni;}/*直接选择排序*/voidselectsort(datatypex[],intn){}五、思考题1.直接选择排序的时间复杂度为多少？是否是稳定排序算法？实验九顺序查找和折半查找（2学时）一、实验目的掌握顺序查找和折半查找的基本思想，查找过程及其实现的算法。二、实验内容对已知关键字序列分别进行顺序查找和折半查找。基本要求：（1）给定关键字序列通过键盘任意输入；（2）查找方式可由用户选择；（3）输出查找记录的位置；（4）可由用户选择退出程序。三、实验要点及说明顺序查找是一种简单的查找方法，数据记录顺序存放在某顺序表中。顺序表查找的方法是：从顺序表的一端开始，用给定值逐个顺序地与表中各记录的关键字相比较，如在表中找到某个记录的关键字与给定值相等，表明查找成功；折半查找又称二分查找，它要求待查找的顺序表必须是有序表，即表中各记录按其关键字值的大小顺序存储。可按如下格式定义记录的结构：typedefstruct{intkey;Chardata;}datatype;模块划分：（1）getsort()函数：输入记录的关键字（2）seqsearch()函数：顺序查找（3）binsearch()函数：折半查找（4）insertsort()函数：直接插入排序（5）print()函数：显示输出四、参考源程序#include<stdio.h>#defineMAXLEN50typedefstruct{ intkey; chardata;}datatype;intgetsort(datatypex[]);intseqsearch(datatypex[],intkey,intn);intbinsearch(datatypex[],intkey,intn);voidinsertsort(datatypex[],intn);voidprint(datatypex[],intn);voidmain(){intsel,n,s,key,i;/*sel输入选择，n记录长度，s查找方法的选择，key查找关键字给定值，i目标记录的下标*/ datatypex[MAXLEN]; printf("请输入你的选择：1开始其他选择为退出\nyourchoice="); scanf("%d",&sel); while(sel==1) {printf("\n输入关键字序列，以－1结束输入："); n=getsort(x); printf("请输入选择的查找方法：1顺序查找2折半查找3-退出查找\nyourchoice="); scanf("%d",&s); while(s!=3) {printf("请输入查找关键字给定值key＝"); scanf("%d",&key); if(s==1) {printf("\n原关键字序列为："); print(x,n); i=seqsearch(x,key,n); if(i==-1) printf("\n没有给定值记录！\n"); else printf("\n查找的结果为表中的第%d条记录!\n",i+1);} elseif(s==2) {i=binsearch(x,key,n); if(i==-1) printf("\n没有给定值记录！\n"); else printf("\n查找的结果为表中的第%d条记录!\n",i+1);} else printf("选择错误！\n"); printf("请输入选择的查找方法：1顺序查找2折半查找3-退出查找\nyourchoice="); scanf("%d",&s);} printf("请输入你的选择：1开始其他选择为退出\nyourchoice="); scanf("%d",&sel);}}/*输入记录的关键字*/intgetsort(datatypex[]){inti=0; scanf("%d",&x[i].key); while(x[i].key!=-1) {i++; scanf("%d",&x[i].key);} returni;}/*顺序查找*/intseqsearch(datatypex[],intkey,intn){}/*折半查找*/intbinsearch(datatypex[],intkey,intn){}/*直接插入排序*/voidinsertsort(datatypex[],intn){}/*显示输出*/voidprint(datatypex[],intn){inti; for(i=0;i<n;i++) printf("%d\t",x[i]); printf("\n");}五、思考题顺序查找和折半查找的平均查找长度各为多少？实验十二叉排序树查找（2学时）一、实验目的熟悉二叉排序树的构造，掌握二叉排序