桂电数据结构实验

桂电数据结构作业数据结构是一门非常重要的学科，一定要努力学习啊。希望同学们在使用本实验指示书及进行实验的过程中，对本实验指导书中的不足之处提出建议，使《数据结构B》课程的教学得到不断的改进和提高。本实验指导书在编写过程中，参考了原来的电子工程系的数据结构实验指导书、计算机系的实验指导书课题一的具体实验内容1、构造元素类型为整型的线性表，将以下元素插入分别插入线性表：34562091552、查找表中是否存在元素20，实现元素20与元素9的交换；3、按照课题要求编写函数，实现线性表元素3456920155的倒置，即倒置后的表应为5152095634。#includestdio.h#includestdlib.h#defineNULL0structnode{intnum;structnode*next;};voidmain(){inti;structnode*L,*s,*p,*h,*q,*k;L=(node*)malloc(sizeof(structnode));//L-num=NULL;p=L;printf(请输入\n);for(i=0;i6;i++){s=(node*)malloc(sizeof(structnode));scanf(%d,&s-num);p-next=s;p=s;}p-next=NULL;//以上为链表的建立和输入//以下为元素的交换p=L;while(p-next-num!=20)p=p-next;h=p-next;p-next=p-next-next;h-next=p-next-next;p-next-next=h;p-next-next-next=h-next;//free(h);//以下为链表的输出p=L-next;printf(交换后输出\n);while(p!=NULL){printf(%d\n,p-num);p=p-next;}//以下为链表的倒置p=L;while(p-next-next!=NULL)p=p-next;q=p-next;q-next=p;p-next=NULL;p=L;for(i=0;i4;i++){while(p-next-next!=NULL)p=p-next;k=p-next;k-next=p;p-next=NULL;p=L;}L-next=q;//倒置后链表的输出p=L-next;printf(倒置后输出\n);while(p!=NULL){printf(%d,p-num);p=p-next;}}实验课题一：将一个十进制数转换成另外一个P进制数字符串（可以是二进制到十六进制）。转换函数的原型为：voidConvert(intn,charstr[],unsignedP);n：输入，待转换的数str：输出，转换好的P进制字符串P：输入，要转换的进制，取值可从2到16。如果在这范围之外，可认为输入错，不做转换。将一个整数转换成P进制的数，我们可以采用如下的方法：例：十进制转换成八进制（P等于8）：(66)10=(102)866/8=8余28/8=1余01/8=0余1当商为0时转换结束，转换结果为上述过程余数序列的逆序：102。先求得的余数在写出结果时最后写出，最后求出的余数最先写出，符合栈的LIFO性质，故可用栈来实现数制转换。#includestdio.h#includestdlib.h#definemaxsize100typedefstruct{chardata[maxsize];inttop;}sqstack,*Stack;Stackinitstack(){Stacks;s=(Stack)malloc(sizeof(sqstack));s-top=-1;returns;}intpush(Stacks,charch){if(s-top=maxsize)return0;else{s-data[++s-top]=ch;return1;}}intpop(Stacks,char*ch){if(s-top==-1)return0;else{*ch=s-data[s-top--];return1;}}voidConvert(intn,charstr[],unsignedp)//十进制数据n向p进制转换{Stacks;inti=0;s=initstack();while(n){if(n%p10)push(s,n%p+'0');elsepush(s,n%p+'A'-10);n=n/p;}while(s-top!=-1)pop(s,&str[i++]);str[i]='\0';}voidmain(){intn;charstr[maxsize];unsignedp;printf(请输入数据n\n);scanf(%d,&n);printf(请输入数据p\n);scanf(%d,&p);Convert(n,str,p);printf(%s\n,str);}实验3实验课题一：实验课题一：回文（palindrome）是指一个字符串从前面读和从后面读都一样，仅使用若干栈和队列、栈和队列的ADT函数以及若干个int类型和char类型的变量，设计一个算法来判断一个字符串是否为回文。假设字符串从标准输入设备一次读入一个字符，算法的输出结果为true或者false。可以用一些字符串测试输出结果，如：abcdeabcde，madamimadam等#includestdio.h#includestdlib.h#definem100typedefstruct{charstack[m];inttop;}stackstru;typedefstruct{charqueue[m];intfront;intrear;}queuestru;void{main()intstinit(stackstru*s);//初始化顺序栈intstempty(stackstru*s);//判断栈是否为空intstpush(stackstru*s,charx);//入栈charstpop(stackstru*s);//出栈intquinit(queuestru*q);//初始化循环队列intquempty(queuestru*q);//判断队列是否为空intenqueue(queuestru*q,chare);//入队chardequeue(queuestru*q);//出队charc;intflag=0;stackstru*s=(stackstru*)malloc(sizeof(stackstru));queuestru*q=(queuestru*)malloc(sizeof(queuestru));stinit(s);quinit(q);printf(Inputastring:\n);while((c=getchar())!='!'){putchar(c);stpush(s,c);enqueue(q,c);}printf(\n);printf(Endinput!\n);while(stempty(s)){if(stpop(s)==dequeue(q)){flag=1;continue;}else{flag=0;break;}}if(flag==1)printf(Thisstringispalindrome!\n);elseprintf(Thisstringisn'tpalindrome!\n);}intstinit(stackstru*s){s-top=0;return1;}//初始化栈intstempty(stackstru*s){if(s-top==0){return0;}else{return1;}}//判断栈是否空intstpush(stackstru*s,charx){if(s-top==m)//栈满{printf(Thestackisoverflow!\n);return0;}else//栈未满{s-top=s-top+1;//栈顶后移s-stack[s-top]=x;//字符入栈return1;}}//入栈操作charstpop(stackstru*s){chary;if(s-top==0)//栈为空{printf(Thestackisempty!\n);return'';//返回空格}else//栈不为空{y=s-stack[s-top];//取出栈顶元素s-top=s-top-1;//栈顶指示移动returny;}}//出栈操作intquinit(queuestru*q){q-front=0;q-rear=0;return1;}//初始化为一个空的循环队列intquempty(queuestru*q){if(q-front==q-rear)//队头和队尾相等{return0;}else{return1;}}//判断队列是否为空intenqueue(queuestru*q,chare){if((q-rear+1)%m==q-front)//队列已满{printf(Thequeueisoverflow!\n);//提示信息return0;}else{q-queue[q-rear]=e;//入队q-rear=(q-rear+1)%m;//移动队尾指针return1;}}//入队操作chardequeue(queuestru*q){charf;if(q-front==q-rear)//队列为空{printf(Thequeueisempty!\n);//提示信息return0;}else{f=q-queue[q-front];//取出队首元素q-front=(q-front+1)%m;//移动对头指针returnf;}}//出队操作实验4实验课题一实验课题一：将下图中的二叉树用二叉链表表示：ABDFGEHC1用三种遍历算法遍历该二叉树，给出对应的输出结果；2写一个函数对二叉树搜索，若给出一个结点，根据其是否属于该树，输出true或者false。3写函数完成习题4.31（C++版）或4.28（C版教科书）。#includestdio.h#includemalloc.htypedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;BiTreeCreate(BiTreeT){charch;ch=getchar();if(ch=='#')T=NULL;else{T=(BiTNode*)malloc(sizeof(BiTNode));T-data=ch;T-lchild=Create(T-lchild);T-rchild=Create(T-rchild);}returnT;}intnode(BiTreeT){intsum1=0,a,b;if(T){if(T!=NULL)sum1++;a=node(T-lchild);sum1+=a;b=node(T-rchild);sum1+=b;}returnsum1;}intmnode(BiTreeT){intsum2=0,e,f;if(T){if((T-lchild!=NULL)&&(T-rchild!=NULL))sum2++;e=mnode(T-lchild);sum2+=e;f=mnode(T-rchild);sum2+=f;}returnsum2;}voidPreorder(BiTreeT){if(T){printf(%c,T-data);Preorder(T-lchild);Preorder(T-rchild);}}intSumleaf(BiTreeT){intsum=0,m,n;if(T){if((!T-lchild)&&(!T-rchild))sum++;m=Sumleaf(T-lchild);sum+=m;n=Sumleaf(T-rchild);sum+=n