数据结构实验复习

实验一C语言数据类型的使用［实验目的］复习C语言的使用方法，特别是指针、结构体的内容，同时也为以后的各个实验做准备。［实验内容及要求］1．建立一个简单链表(静态链表)，它由3个学生数据的结点组成，每个结点包括学号和成绩。输出各结点中的数据。(根据题目完善程序)#defineNULL0structstudent{longnum；floatscore；structstudent*next；}stu；typedefstructstudentstu;main(){stua,b,c,*head,*p；num=99101；a.score=89.5；num=99103；b.score=90；num=99107；c.score=85；head=&a；next=&b；next=&c；next=NULL；p=head；do{printf(“％ld%5.1f\n”, )；/*输出学号和成绩*/p=p->next；}while( )；}输出：2．建立一个动态链表，它由3个学生数据的结点组成，每个结点包括学号和成绩。输出各结点中的数据。#defineNULL0#defineLENsizeof(structstudent)structstudent{longnum；floatscore；structstudent*next；}；intn；structstudent*creat(void)/*尾插法建立链表*/{structstudent*head；structstudent*p1,*p2；n=0；p1=p2=(structstudent*)malloc(sizeof(structstudent))；scanf(“%ld,%f”,&p1->num,&p1->score)；head=NULL；while(p1->num!=0){n=n+1；if(n==1)head=p1；elsep2->next=p1；p2=p2->next ；p1=(structstudent*)malloc(LEN)；scanf(“%ld,%f”,&p1->num,&p1->score)；}p2->next=NULL；return(head)；}voidprint(structstudent*head){structstudent*p；printf(“\nNow,These%drecordsare：\n”,n)；p=head；if(head!=NULL)do{printf(“%ld%5.1f\n”,p->num,p->score)；}while(p!=NULL)；}main(){structstudent*head；printf（“inputrecords：\n”）；head=creat（）；print（head）；}输入： 输出： ［思考题］1．将上题链表中学生的成绩从低到高排列输出，要求每行一个，包括学号和成绩。2．设计一个可进行复数运算的演示程序。要求：实现下列六种基本运算：1）由输入的实部和虚部生成一个复数；2）两个复数求和；3）两个复数求差；4）两个复数求积；5）从已知复数中分离出实部；6）从已知复数中分离出虚部。运算结果以相应的复数或实数的表示形式显示。3．设计一个可进行有理数运算的演示程序。要求：实现两个有理数相加、相减、相乘以及求分子或求分母的运算（选做）。［实验报告要求］打印或保存程序清单，分析和总结程序调试过程中获得的经验或不足，记录程序出错位置并分析原因。［参考资料］1．《数据结构题集》（第二版）严蔚敏吴伟敏编著北京清华大学出版社1998.122．《数据结构》（第二版）严蔚敏吴伟敏编著北京清华大学出版社1998.123.《C语言程序设计》（第二版）谭浩强编著北京清华大学出版社1999.12实验二线性表[实验目的]1.掌握数据结构中表的基本概念。2．熟练掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的实现。3.熟练掌握链表的各种操作和应用。[实验内容及要求]顺序表的基本运算的算法：创建顺序表：输出顺序表；插入运算；删除运算；查找运算单链表的基本运算的算法：创建一个单链表；输出一个单链表；求单链表的长度；查找第I个结点；插入一个结点；删除一个结点；1•设有一个顺序表A,包含n个元素，要求写出一个将该表逆置的算法，并只允许在原表的存储空间外再增加一个附加的工作单元。(根据题目完善程序)#include<stdio.h>#defineMaxLen50typedefintelemtype;typedefelemtypesqlist[MaxLen];intcreate(sqlistA){inti,n;printf("创建一个顺序表\n");printf("输入元素个数：")；scanf("%d",&n);for(i=0;i<n;i++){printf("输入第％d个元素值："，i);scanf("%d",&n);}returnn;}voidinvert(sqlistA，intn){intm=n/2，i;elemtypetemp;for(i=0;i<m;i++){temp=A[i];A[i]=A[n-i-1];A[n-i-1]=temp;/*交换*/}}voiddisp(sqlistA，intn){inti;for(i=0;i<n;i++)printf("%d",A[i]);printf("\n");}voidmain(){sqlistA;intn;n=create(A);disp(A,n);invert(A,n);disp(A,n);}创建一个顺序表输入元素个数：5输入第1个元素值：2输入第2个元素值：6输入第3个元素值：3输入第4个元素值：1输入第5个元素值：8输出一个顺序表输出一个顺序表2•有一个单链表的第一个结点指针为head，编写一个函数将该单链表逆置，即最后一个结点变成第一个结点,原来倒数第二个结点变成第二个结点。在逆置中不能建立新的单链表(根据题目填空完善程序)#include<stdio.h>#include<malloc.h>#defineNULL0typedefintelemtype;typedefstructlinknode{elemtypedata;structlinknode*next;}nodetype;nodetype*create(){elemtyped;nodetype*h,*s,*t;inti=1;h=NULL;printf("建立一个单链表\n");while(1){printf("输入第％d节点data域值:"，i);scanf("%d",&d);if(d==0)break; /*以0表示输入结束跳出循环，如果returnNULL，怎么生成头结点*/if(i==1) /*建立第一个结点*/{h=(nodetype*)malloc(sizeof(nodetype));h->data=d;h->next=NULL;t=h;}else{s=(nodetype*)malloc(sizeof(nodetype));s-〉data=d;t-〉next=s;//注意应该没有s-〉next=NULL;t=s;/*t始终指向生成的单链表的最后一个结点*/}i++;}t-〉next=NULL;//加上这一条。returnh;}voiddisp(nodetype*h){nodetype*p=h;printf("输出一个单链表：\n");辻(p==NULL)printf("空表")；while(p!=NULL){printf("%d"，p-〉data);p=p-〉next;}printf("\n");getch();}intlen(nodetype*h){inti=0;nodetype*p=h;while(p){i++;p=p->next;}return(i);}nodetype*invert(nodetype*h){nodetype*p,*q,*r;if(len(h)<=1){printf("逆置的单链表至少有2个节点\n");return(NULL);}else{p=h;q=p->next;while(q!=NULL){r=q->next;q->next=p;p=q;q=r;}h->next=NULL;h=p;returnh;}}voidmain(){nodetype*head;head=create();disp(head);head=invert(head);disp(head);}建立一个单链表输入第1个节点data域的值：1输入第2个节点data域的值：2输入第3个节点data域的值：3输入第4个节点data域的值：4输入第5个节点data域的值：5输入第6个节点data域的值：0输出一个单链表： 3.将两个非递减有序的单链表归并为一个非递减有序的单链表(根据题目填空完善程序)#include“stdio.h”#include“alloc.h”structnode{chardata；structnode*next；}listnode；typedefstructnode*link；voidprint(linkhead){structnode*p；printf(“\n”)；printf(“\n”)；p=head->next；while(p){printf(“％c”，p-〉data)； ；}}linkcreat()/*头插法建立单链表*/{linkhead,s；charch；head=malloc(sizeof(listnode))；head->next=NULL；while((ch=getchar())!='\n'){s=malloc(sizeof(listnode))；s->data=ch；s-〉next= ； =s；}returnhead；}linkmerge(linka,linkb){linkp,q,s,c；c=malloc(sizeof(listnode))；c-〉next=NULL；p=a；q=b；while(p-〉next&&q-〉next){if(p-〉next-〉data<q-〉next-〉data){s=p-〉next；p-〉next=s-〉next；}else{s=q-〉next；q-〉next=s-〉next；}s-〉next=c-〉next；c-〉next=s；}while(p-〉next){s=p-〉next；p-〉next=s-〉next；s->next=c->next；c->next=s；}while(q->next){s=q->next；q->next=s->next；s->next=c->next；c->next=s；}free(p)；free(q)；returnc；}main(){linka,b,c；a=creat()；b=creat()；print(a)；print(b)；c=merge( )；print(c)；printf(“\n”)；}输入：ysplhdzyxrmhb输出 ［思考题］•设计一个算法求A和B两个单链表表示的集合的交集。提示：A和B中相同的结点的集合。•设计一个算法求A和B两个单链表表示的集合的并集。提示：将A和B合并。3.设计一个算法求A和B两个单链表表示的集合的差集。(每个单链表中不存在重复的元素)提示：即在A中而不在B中的结点的集合。4•用头插法把单链表b中在单链表a中未出现的结点合并到单链表a中。（选做）A,B,C为三个单链表，要求删除A表中、在B表和C表中同时出现的结点。（选做）设A=（al,a2,…,an）和B=（bl,b2,…,bm）是两个不带哨兵的单链表.若n=m,且ai=bi（I=1,„,n）,则称A=B；若ai=bi（I=l,…，j）且aj+l〈bj+l（j〈n〈二m）,则称A<B；其它情况下称为A〉B.试编写一个比较A和B的算法，当A〈B、A=B或A>B时分别输出-1、0或1。（选做）提示：算法comp（）的思想是先找出A和B单链表中对应位置相同值的结点，pa和pb分别指向A和B单链表中对应位置不相同的结点。然后根据pa和pb的情况得到A和B单链表的比较结果。设计一个统计选票的算法，输出每个候选的得票结果（假设采用单链表存放选票，候选人编号依次为1,2,3,…，N,且每张选票选且只选一人）。（选做）提示：以单链表存放选票，每个结点的data域存放该选票所选的候选人。用一个数组a统计得票结果。假设一个循环单链表，其结点有left,data和right三个域，其中data为数据域，存放元素的有效信息,right为指针域，它指向后继结点，left为指针域，它的值为NULL.编写一个算法将此表改为循环双链表。（选做）提示：本题算法依次从左向右遍历每个结点，并设置每个结点的left值。编写一个算法实现两个有序（从小到大）顺序表合并为一个顺序表，合并后的结果放在第一个顺序表中，不另设新的顺序表存储（假设两个单链表中没有相同的元素）（根据题目填空完善程序）提示：两个顺序表A和B的合并过程是从A和B中的最后一个元素逐个向前进行比较，将较大的元素先定位在A中。（选做）Joseph问题的一种描述是：编号为1，2,…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。测试数据：m的初值为20；n=7,7各人的密码依次为：3,1,7,2,4,8,4,首先m值为6（正确的出列顺序应为6，1，4，7，2，3，5）。（选做）［实验报告要求］打印或保存程序清单,分析和总结程序调试过程中获得的经验或不足,记录程序出错位置并分析原因。［参考资料］《数据结构题集》（第二版）严蔚敏吴伟敏编著北京清华大学出版社1998.12《数据结构》（第二版）严蔚敏吴伟敏编著北京清华大学出版社1998.12《C语言程序设计》（第二版）谭浩强编著北京清华大学出版社1999.12实验三栈和队列[实验目的]了解栈和队列的特性，以便灵活应用。熟练掌握栈和有关队列的各种操作和应用。[实验内容]栈的基本运算：初始化栈；进栈；退栈；判断栈是否为空栈；获取栈顶元素；输出栈的所有元素；队列的基本运算：初始化队列；入队列；出队列；判断队列是否为空；判断队列头元素；1.设单链表中存放n个字符，设计一个算法,使用栈判断该字符串是否中心对称，如abccba即为中心对称字符串.(根据题目填空完善程序)提示：先用create()函数从用户输入的字符串创建相应的单链表，然后调用bj()函数判断是否为中心对称字符串。在bj()函数中先将字符串进栈，然后将栈中的字符逐个与单链表中字符进行比较。include<stdio.h>include<malloc.h>defineMaxLen100typedefstructnode{chardata；structnode*next；}cnode；cnode*create(chars[]){intI=0；cnode*h,*p,*r；while(s[I]!='\0'){p=(cnode*)malloc(sizeof(cnode))；p->data=s[I]；p->next=NULL；if(I==0){h=p； ； /*r始终指向最后一个结点*/}else{r->next=p；r=p；}I++；}returnh；}intjudge(cnode*h){charst[MaxLen]；inttop=0；cnode*p=h；while(p!=NULL){st[top]=p->data；top++；p=p->next；}p=h；while(p!=NULL){top--；if(p->data==st[top])p=p->next；elsebreak；}if(p==NULL)return ；elsereturn ；}voidmain(){charstr[maxlen]；cnode*h；printf(“输入一个字符串：”)；scanf(“%c”,str)；h=create( )；if(judge(h)==1)printf(“str是中心对称字符串\n”)；elseprintf(“str不是中心对称字符串\n”)；}输入一个字符串：abccba输出： 2•假设以数组sequ[O..MaxSize-l]存放环形队列的元素，同时设变量rear和len分别指示环形队列中队尾元素的位置和内含元素的个数。试写出此环形队列队满的条件，并设计相应入队和出队的算法。(根据题目填空完善程序)提示：该环形队列对满的条件为：len二二MaxSize，队空的条件为：len二=0。由rear,len求队列头指针front的过程为：front=rear-len+1；if(front<0)front=front+MaxSize；即front=(rear-len+1+MaxSize)%MaxSizeinclude<stdio.h>definemaxsize6typedefcharqueue[maxsize]；intrear=0,len=0；intenqueue(queuequ,charx){if(len==maxsize)return0；else{rear=(rear+1)%maxsize；qu[rear]=x；len++；return1；}intdequeue(queuequ,char*x){intfront；if(len==0)return0；else{front=(rear-len+1+maxsize)%maxsize；*x=qu[front]；len--；return1；}}voidmain(){charx；queuequ；printf(“a入队\n”)；enqueue(qu,‘a')；printf(“b入队\n”)；enqueue(qu,‘b')；printf(“c入队\n”)；enqueue(qu,‘c')；printf(“出队一次：”)；dequeue(qu,&x)；printf(“%c\n”,x)；printf(“d入队\n”)；enqueue(qu,‘d')；printf(“e入队\n”)；enqueue(qu,‘e')；printf(“出队一次：”)；dequeue(qu,&x)；printf(“%c\n”,x)；printf(“f入队\n”)；enqueue(qu,‘f')；printf(“g入队\n”)；enqueue(qu,‘g')；printf(“出队一次：”)；dequeue(qu,&x)；printf(“%c\n”,x)；printf(“余下元素出列：”);while(len>0){dequeue(qu,&x)；printf(“%c\n”,x)；}printf(“\n”)；}输出：.入队 .入队 出队一次：.入队 .入队 出队一次.入队 .入队 出队一次： 余下元素出列： ［思考题］1．设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个算法判断其中的括号是否匹配。提示：本题使用一个运算符栈st,当遇到的('、'［'、或'{'时进栈，当遇到时判断栈顶是否为相应的括号，若是退栈继续执行；否则算法结束。2．到医院看病的过程是，患者先排队等候，排队过程中主要重复两件事：(1)病人到达诊室时，将病历交给护士，排到等候队列中候诊。（2）护士从等候队列中取出下一个患者的病历，该患者进入诊室就诊。在排队时按照”先到先服务”的原则。设计一个算法模拟病人等候就诊的过程。其中”病人到达”用命令'A'（'a'）表示，”护士让下一位患者就诊”用命令'N'‘丫）表示，命令'Q'（'q'）表示不再接受病人排队。提示：这里采用一个队列，有”病人到达”命令时即入队，有”护士让下一位患者就诊”命令时即出队，命令'Q'即队列中所有元素出队。3．设计一个程序，演示用算符优先法对算术表达式求值的过程。（选做）基本要求：以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。利用教科书表3.1给出的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教科书的例3_1演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。测试数据：3*（7-2）［实验报告要求］打印或保存程序清单，分析和总结程序调试过程中获得的经验或不足，记录程序出错位置并分析原因。［参考资料］1．《数据结构题集》（第二版）严蔚敏吴伟敏编著北京清华大学出版社1998.122．《数据结构》（第二版）严蔚敏吴伟敏编著北京清华大学出版社1998.123.《C语言程序设计》（第二版）谭浩强编著北京清华大学出版社1999.12实验四串［实验目的］1．掌握串的基本概念，存储方法及主要运算。2．将串的运算应用到文本编辑中。［实验内容］串的基本运算：创建一个串；串的复制；求串的长度；求子串；输入一个自串；删除一个子串；连接两个串；输出串。下列是一个置换函数，采用顺序存储方式存储串，将串si中的第I个字符开始的j个字符(包括第I个字符)构成的子串用s2串进行替换，函数名为replace(s1,I,j,s2)。例如：replace(“abcd”，l,3,'xyz”)返回”xyzd”。(填空)提示：先提取si中位置I之前的所有字符构成的子串str1,再提取位置I+j-1及之后的所有字符构成的子串str2,最后将str1,s2,str2连接起来便构成了结果串。include<stdio.h>include<string.h>#defineMaxLen20typedefstruct{charch［MaxLen］；intlen；}strtype；voidcreate(strtype*s,charstr［］){strcpy(s->ch,str)；s->len=strlen(str)；}voiddisp(strtype*s){if(s->len==0)printf(“空串\n”)；elseprintf(“%c\n”,s->ch)；}strtypereplace(strtype*sl,intI,intj,strtype*s2){strtypes；intn,k；if(I+j-1<=s1->len){for(n=0；n<I-1；n++)s.ch[n]=s1->ch[n]；for(n=0；n<s2->len；n++)s.ch[I+n-1]=s2->ch[n]；s.len=I+s2->len-1；for(n=s.len,k=I+j-1；k<s1-len；n++.k++)s.ch[n]=s1->ch[k]；s.len=n；s.ch[s.len]='\0'；}else{s.ch[0]='\0'；s.len=0；}return(s)；}voidmain(){strtypes,s1,s2；intpos,n；charstr[maxlen]；printf(“字符串：”)；gets(str)；create(&s1,str)；printf(“位置：”)；scanf(“％d”，& )；printf(“长度：”)；scanf(“%d”，& )；printf(“子串：”)；gets( )；create(&s2,str)；s=replace(&s1,pos,n,&s2)；disp(&s)；}输出：字符串：12345678位置：3长度：4子串：abcdefgh2．设计一个算法将串中所有的字符倒过来重新排列。(填空)#include<stdio.h>#include<string.h>#defineMaxLen20typedefstruct{charch[MaxLen]；intlen；}strtype；voidcreate(strtype*s,charstr[]){strcpy(s->ch,str)；s->len=strlen(str)；}voiddisp(strtype*s){if(s->len==0)printf(“空串\n”)；elseprintf(“%c\n”，s->ch)；strtypereverse(strtype*s){intI；strtypet；for(I=0；I<s->len；I++)t.ch[ ]=s-〉ch[I]；t.len二 ；t.ch[t.len]='\0'；returnt；}voidmain(){strtypes,t；charstr[maxlen]；printf(“输入一个串：”)；gets(str)；create(&s,str)；t=reverse(&s)；printf(“原串：”)；disp(& )；printf(“逆置串：”)；disp(& )；}输入一个原串：hijklmn输出：原串 逆串 [思考题]米用顺序结构存储串，编写一个函数index(sl,s2),用于s2是否是si的子串。若是，返回其在主串中的位置；否则返回-1。提示：设si二''ala2„am”； s2二“blb2„bn”从si中找出与bl匹配的字符ai,若ai=b1,则判断是否ai+1=b2,…，ai+n-1二bn，若都相等，s2为s1的子串，否则继续比较ai之后的字符。字符串：xhyjzdxyakxyz子串：xyz子串位置：利用串的基本运算，编写一个算法删除串si中所有s2子串。提示：本题利用3题的index（）函数和删除子串函数循环实现。已知s=“（xyz）+*”，t=“（x+z）*y”。试利用连接、求子串和置换等操作，将s转化为t。（选做）［实验报告要求］打印或保存程序清单，分析和总结程序调试过程中获得的经验或不足，记录程序出错位置并分析原因［参考资料］《数据结构题集》（第二版）严蔚敏吴伟敏编著北京清华大学出版社1998.12《数据结构》（第二版）严蔚敏吴伟敏编著北京清华大学出版社1998.12《C语言程序设计》（第二版）谭浩强编著北京清华大学出版社1999.12实验五数组和广义表[实验目的]1．熟练掌握数组的存储表示和实现。2．熟悉广义表的存储结构的特性。[实验内容]数组的基本运算：定义数组；数组转制；数组相加；数组相乘；广义表的基本运算：创建广义表；输出广义表；查找广义表元素；1.设数组R[O..n-l]的n个元素中有多个0元素，设计一个算法，将R中所有的非0元素依次移动到R数组的前端。(填空)提示：用I指向不为0元素应放的下标，j遍历R,当R[j]不为0是，在I与j不相同时将R[I]与R[j]交换。Voidmove(intR[],intn){intI=-1,j,temp；for(j=0；j<n；j++)if(R[j]!=0){I++；If(I!=j){temp= ； ; 二temp；}}}voidmain(){intn=10,I；intr[]={9,0,8,0,7,0,6,0,5,0}；printf(“移动前：”)；for(I=0；I<n；I++)printf(“%d”,r[I])；printf(“\n”)；move(r,n)；printf(“移动后：”)；for(I=0,I<n；I++)printf(“%d”,r[I])；printf(“\n”)；}移动前： 移动后： 根据表头和表尾的定义，设计分别实现求表头和表尾操作的head()和tail()函数，并编写一个求广义表表头和表尾的程序。(填空)提示：一个广义表的表头指的是该广义表的第一个元素。一个广义表的表尾指的是除去该广义表的第一个元素后的所有剩余的部分。include<stdio.h>include<string.h>include<malloc.h>#definemaxlen100typedefstructnode{inttag；structnode*link；union{chardata；structnode*slist；}val；}gnode；voiddisastr(chars[],charhstr[]){intI=0,j=0,k=o,r=0；charrstr[maxlen]；while(s[I]&&(s[I]!=', ‘IIk)){if(s[I]=='(‘)k++；elseif(s[I]==')')k--；if(s[I]!=',‘||s[I]==',‘&&k){hstr[j]=s[I]；I++；j++；}}hstr[j]='\0'；if(s[I]==',‘)I++；while(s[I]){rstr[r]=s[I]；r++；I++；}rstr[r]='\0'；strcpy(s,rstr)；}gnode*create(chars[]){gnode*p,*q,*r,*gh；charsubs[maxlen],hstr[maxlen]；intlen；len= (s)；if(!strcmp(s,”()”))gh= ；elseif(len==1){gh=(gnode*)malloc(sizeof(gnode))；gh->tag=0'gh->val.data=*s；gh->link=NULL；}else{gh=(gnode*)malloc(sizeof(gnode))；gh->tag=；p=gh；s++;strncpy(subs,s,len-2)；subs[len-2]='\0'；do{disastr(subs,hstr)；r=create(hstr)；p->val.slist=r；q=p；len=strlen(subs)；if(len>0){p=(gnode*)malloc(sizeof(gnode))；p->tag=1；q->link=p；}}while( )；q->link=NULL；}return(gh)；}voiddisp(gnode*h){gnode*p,*q；printf(“(“)；if(h){p=h->val.slist；q=h->link；while(q&&p&&!p->tag){printf(“%c,”,p->val.data)p=q->val.slist；q=q->link；}if(p&&!p->tag){printf(“%c”,p->val.data)；break；}else{if(!p)printf(“()”)；elsedisp(p)；if(q)printf(“,”)；h=q；}}while(h)；printf(“)”)；}gnode*head(gnode*p){return(p->val.slist)；}gnode*tail(gnode*p){return(p->link)；}voidmain(){gnode*g,*h,*t；charstr［maxlen］；printf(“输入广义表表达式：”)；scanf(“%c”,str)；g=create(str)；printf(“广义表：”)；disp(g)；printf(“\n”)；if(g==NULL||g->tag==0||g->val.slist==NULL)printf(“原子或空表不能取表头尾\n”)；else{h=head(g)；if( )printf(“表头：％c\n”，h-〉val.data)；else{printf(“表头：”)；disp(h)；printf(“\n”)；}t=tail(g)；printf(“表尾：”)；disp(t)；printf(“\n”)；}}［思考题］试设计一个算法，将A［O..n-l］中所有奇数移到偶数之前。要求不另增加存储空间，且时间复杂度为O(n)。提示：i从左向右遍历，指向A左边的一个偶数，j从右向左遍历，指向A右边的一个奇数，然后将A［i］与A［j］交换。如此循环直到i大于等于jo编写一个函数将两个广义表合并成一个广义表。合并是指元素的合并，例如两个广义表((a,b),(c))与(a,(e,f))合并后的结果是((a,b),(c),a,(e,f))°(选做)提示：先找到第一个广义表的最后一个结点，将其链接到第二个广义表的首元素上即可。编写一个函数删除广义表中所有值为x的元素。例如删除广义表((a,b),a,(d,a))中所有a的结果是广义表((b),(d))°(选做)4．稀疏矩阵运算器。（选做）基本要求：以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。［实验报告要求］打印或保存程序清单，分析和总结程序调试过程中获得的经验或不足，记录程序出错位置并分析原因。［参考资料］1．《数据结构题集》（第二版）严蔚敏吴伟敏编著北京清华大学出版社1998.122．《数据结构》（第二版）严蔚敏吴伟敏编著北京清华大学出版社1998.123．《C语言程序设计》（第二版）谭浩强编著北京清华大学出版社1999.12实验六树［实验目的］掌握二叉树，二叉树排序数的概念及存储方法。掌握二叉树的遍历算法。熟练掌握编写实现树的各种运算的算法。［实验内容］树的基本运算：创建二叉树；输出二叉树；先序、中序、后序遍历二叉树；求二叉树的深度；创建二叉排序树；二叉排序树的查找；二叉排序树的删除；创造哈夫曼树；输出哈夫曼树；1、建立一棵二叉树并中序遍历。(填空)#include“stdio.h”#include“malloc.h”structnode{chardata；structnode*lchild,*rchild；}bnode；typedefstructnode*blink；blinkadd(blinkbt,charch){if(bt==NULL){bt=nalloc(sizeof(bnode))；bt->data=ch；bt->lchild=bt->rchild=NULL；}elseif(ch<bt->data)bt->lchild=add(bt->lchid,ch)；elsebt->rchild=add(bt->rchild,ch)；returnbt；}voidinorder(blinkbt){if(bt){inorder(bt-〉 )；printf(“％c”， )；inorder(bt-〉 )；}}main(){blinkroot=null；inti,n；charx；scanf(“%c”，&n)；for(i=1；i<=n；i++){x=getchar()；root=add(root,x)；}inorder(root)；printf(“\n”)；}输入：ephqsbma输出：2．求二叉树的结点数和叶子数(填空)#include“stdio.h”#include“alloc.h”structnode{chardata；structnode*lchild,*rchild；}bnode；typedefstructnode*blink；intn=0,no=0；voidpreorder(blinkbt){if(bt){n++；if(bt->lchild==NULL&&bt->rchild==NULL)no++；preorder(bt-〉 ；)preorder(bt-〉 ；)}}blinkcreat(){blinkbt；charch；ch=getchar()；if(ch!='#'){bt=nalloc(sizeof(bnode))；bt-〉data=ch；bt-〉lchild= ；bt-〉rchild二 ；}elsebt=NULL；returnbt；}main(){blinkroot；root=creat()；preorder(root)；no)；printf(“numberofnode：%dnumberofleaf：%d\n”,n,}no)；输入：ab##cd###输出：［思考题］1．编写程序，实现按层次遍历二叉树。2．编写程序，对二叉树进行先序遍历，并打印层号。3．编写程序，实现二叉树的先序、中序、后序遍历，并求深度。［实验报告要求］打印或保存程序清单，分析和总结程序调试过程中获得的经验或不足，记录程序出错位置并分析原因［参考资料］1．《数据结构题集》（第二版）严蔚敏吴伟敏编著北京清华大学出版社1998.122．《数据结构》（第二版）严蔚敏吴伟敏编著北京清华大学出版社1998.123．《C语言程序设计》（第二版）谭浩强编著北京清华大学出版社1999.12实验七图［实验目的］熟悉图的各种存储方法。掌握遍历图的递归和非递归的算法。理解图的有关算法。［实验内容］图的基本运算有：创建图；图的输出；深度优先遍历；广度优先遍历设计一个算法，判断无向图G是否连通。若连通则返回1；否则返回0。（填空）提示：采用遍历方式判断无向图G是否连通。这里用dfs,先给visited［］数组置初值0,然后从0顶点开始遍历该图，之后，若所有顶点I的visited［I］均为1,则该图是连通的；否则不连通。include<stdio.h>include<malloc.h>#definevnum20typedefstructarcmode{intadjvex；structarcnode*nextarc；}arcnode；typedefstructvexnode{intvertex；arcnode*firstarc；}adjlist［vnum］；typedefstructgraphs{adjlistadjlist；intvexnum,arcnum；}graph；voidcreate（graph*g）{intn,e,I,j,k；arcnode*p；printf（“创建一个图：\t”）；printf（“顶点数：”）；scanf（“%d”,&n）；printf（“\t\t边数：”）；scanf（“%d”,&e）；g->vexnum=n；g->arcnum=e；for（I=0；I<n；I++）{g->adjlist[I].vertex=I；g->adjlist[I].firstarc=NULL；}for（k=0；k<e；k++）{printf（“第%d+l条边（节点号从0到％d-l）：”，k,n）；scanf（“%d,%d”,&I,&j）；p=（arcnode*）malloc（sizeof（arcnode））；p->adjvex=j；p->nextarc=g->adjlist[I].firstarc；g->adjlist[I].firstarc=p；}}voiddisp（graph*g）{intI,have；arcnode*p；printf（“输出图：\n“）；for（I=0；I<g->vexnum；I++）{p=g->adjlist[I].firstarc；have=0；while（p!=NULL）{printf（“（%d,%d）”,i,p->adjvex）；p=p->nextarc；have=1；}if(have==1)printf(\n；}}voiddfs(graphg,intv,intvisited[]){arcnode*p；printf(“%d”,v)；visited[v]=1；p=g.adjlist[v].firstarc；while(p!=NULL){if(!visited[p->adjvex])dfs(g,p->adjvex,visited)；p=p->nextarc；}}graphcreatng(){intn=4,e=10,I,j,k；graphg；arcnode*p；intedge[][2]={{0,3},{3,0},{0,1}{1,0},{1,2},{2,1},{2,3},{3,2},{0,2},{2,；0}}g.vexnum=n；g.arcnum=e；for(I=0/I<n；I++){g.adjlist[I].vertex=I；g.adjlist[I].firstarc=NULL；}for(k=0；k<e；k++){I=edge[k][0]；J=edge[k][1]；P=(arcnode*)malloc(sizeof(arcnode))；p->nextarc=g.adjlist[I].firstarc；g.adjlist[I].firstarc=p；}returng；}intconnect(graphg){intI,flag=1；intvisited[vnum]；for(I=0；I<g.vexnum；I++)visited[I]=0；dfs(g,0,visited)；for(I=0；I<g.vexnum；I++)if(visit3ed[I]==0){flag=0；break；}returnflag；}voidmain(){graphg；g=creatng()；disp(&g)；printf(“深度优先搜索顺序：”)；”该图不连通”)\n”)；printf(“(connect(g)==1?”该图不连通”)\n”)；输出图(0，2)(0，1)(0，3)(1，2)(1，0)(2，0)(2，3)(2，1)(3，2)(3，0)深度优先搜索顺序：［思考题］1．编写程序，实现无向图的深度优先搜索。有一个邻接表存储的图G,分别设计实现以下要求的算法：求出图中每个顶点的出度；计算图中出度为0的顶点数。设计一个算法创建一个带权（路径）的无向图，输出从V0到其它各个顶点的最短路径长度和路径。提示：采用Dijstra算法求一个顶点到其它所有顶点的最短路径。（选做）最小生成树问题。（选做）基本要求：利用克鲁斯卡尔算法求网的最小生成树，输出构造生成树过程中的连通分量，以文本形式输出生成树中各条边以及他们的权值。［实验报告要求］打印或保存程序清单，分析和总结程序调试过程中获得的经验或不足，记录程序出错位置并分析原因［参考资料］《数据结构题集》（第二版）严蔚敏吴伟敏编著北京清华大学出版社1998.12《数据结构》（第二版）严蔚敏吴伟敏编著北京清华大学出版社1998.12《C语言程序设计》（第二版）谭浩强编著北京清华大学出版社1999.12实验八查找[实验目的]掌握顺序查找，