西安建筑科技大学华清学院《数据结构与数据库原理》大作业报告书姓名：班级：通信工程1202学号：201206020229实验一线性数据结构一、上机目的掌握线性数据结构的基础认识二、上机实验原理链表是最简单的线性数据结构，对链表的掌握是以后课程学习的基础。
掌握链表的逻辑结构，存储结构，基本操作及其实现，应用链表实现简单的应用。
队列和栈都是存取受限的线性表，队列的特点是先进先出，栈的特点是先进后出。
掌握队列和栈的逻辑结构，存储结构，基本操作及其实现，应用队列或者栈实现简单的应用。
三、详细设计#include<stdio.h>#include<stdlib.h>struct node{int x;int z;struct node*next;};typedef struct node link;link*creatlink(){link*head,*s,*p;int num1,num2;head=NULL;p=head;printf(":\n");scanf("%d%d",&num1,&num2);while((num1!=0)||(num2!=0)){s=(link*)malloc(sizeof(link));s->x=num1;s->z=num2;if(head==NULL)head=s;elsep->next=s;p=s;scanf("%d%d",&num1,&num2);}if(head!=NULL)p->next=NULL;return head;}link*addlink(link*A,link*B){link*p,*q,*r,*s,*C;p=A;q=B;r=(link*)malloc(sizeof(link));C=r;while((p!=NULL)&&(q!=NULL)){if(p->z<q->z){s=(link*)malloc(sizeof(link));s->x=p->x;s->z=p->z;r->next=s;p=p->next;r=s;}else if(p->z>q->z){s=(link*)malloc(sizeof(link));s->x=q->x;s->z=q->z;r->next=s;q=q->next;r=s;}else if((p->x+q->x)!=0){s=(link*)malloc(sizeof(link));s->x=(p->x)+(q->x);s->z=p->z;r->next=s;p=p->next;q=q->nextr=s;}else{p=p->next;q=q->next;}}if(p==NULL)r->next=q;elser->next=p;return C;}void plink(link*A){link*t;t=A;for(;t->next!=NULL;t=t->next)printf("%dX^%d+",t->x,t->z);printf("%dX^%d\n",t->x,t->z);}int main(){link*A,*B，*C，*L；A=creatlink();printf("多项式A为:\n");plink(A);B=creatlink();printf("多项式B为:\n");plink(B);C=addlink(A,B);printf("相加后多项式C为:\n");C=C->next;for(;C->next!=NULL;C=C->next)printf("%dX^%d+",C->x,C->z);printf("%dX^%d\n",C->x,C->z);return 0;}四、调试分析五、总结线性结构是最简单且最常用的一种数据结构。
线性结构的基本特点的基本特点是数据元素有序并且是有限的。
数据结构是组织和访问数据的系统方法。
数据结构用来反映一个数据的内部构成首先在这个程序中，我们应该先寻找及比较相加项的幂指数，在幂指数相同的情况下，系数相加。
我们可以把多项式看成一个线性表，用线性表唯一代表一个多项式，下来我们就用链表来存储多项式，把相加的结果存放在另一个新链表中。
在高级程序设计语言中，现行数据结构是一个数据在数据分类中的归属。
实验二二叉树一、上机目的掌握二叉树的基本知识二、上机实验原理二叉树是非线性数据结构，是一种特殊的树，他特殊在最多只有左右两个分支，并且要严格区分左右，掌握二叉树的逻辑结构，存储结构，基本操作及其实现。
三、详细设计#include<stdio.h>#include<stdlib.h>struct tnode {char d;struct tnode*l,*r;};typedef struct tnode tree;void fp(tree*rt){if(rt!=NULL){printf("%c\n",rt->d);if((rt->l)!=NULL)fp(rt->r);if((rt->r)!=NULL)fp(rt->r);}}void mp(tree*rt){if(rt!=NULL){if((rt->l)!=NULL)mp(rt->l);printf("%c\n",rt->d);if((rt->r)!=NULL)mp(rt->r);}}void bp(tree*rt){if(rt!=NULL){if((rt->l)!=NULL)bp(rt->l);if((rt->r)!=NULL)bp(rt->r);printf("%c\n",rt->d);}}int main(){tree*t1,*t2,*t3,*t4,*t5,*t6,*t7,*t8,*t9;t1=(tree*)malloc(sizeof(tree));t2=(tree*)malloc(sizeof(tree));t3=(tree*)malloc(sizeof(tree));t4=(tree*)malloc(sizeof(tree));t5=(tree*)malloc(sizeof(tree));t6=(tree*)malloc(sizeof(tree));t7=(tree*)malloc(sizeof(tree));t1->d='A';t1->l=t2;t1->r=t3;t2->d='B';t2->l=t4;t2->r=NULL;t3->d='C';t3->l=t5;t3->r=NULL;t4->d='D';t4->l=NULL;t4->r=NULL;t5->d='E';t5->l=t6;t5->r=t7;t6->d='F';t6->l=NULL;t6->r=NULL;t7->d='G';t7->l=NULL;t7->r=NULL;printf("先序遍历序列为：\n");fp(t1);printf("中序遍历序列为：\n");mp(t1);printf("后序遍历序列为：\n");bp(t1);return 0;}四、调试分析五、总结二叉树是树形结构的一个非常重要的类型。
二叉树并非是树的特殊情形，二叉树的结点有左右之分，它的结点的最大度数为2。
二叉树的存储形式有很多种，最常用的是顺序存储结构和链式存储结构。
此二叉树实验，首先在键盘上输入（先序），以二叉树链表进行存储结构建立二叉树。
采用递归算法对其进行遍历（先序，中序，后序），将遍历结果打印输出，然后在采用非递归的方法实现先序和中序遍历，再将结果打印输出。
最后编写算法，交换二叉树上所有的节点的左右子树，并以缩格形式打印出交换后的序列。
相同元素，若其输入顺序不相同，则生成的二叉排序树也是不同的。
实验三查找与排序一、上机目的掌握查找与排序的基本方法二、上机实验原理查找与排序是计算机软件中最常用的方法，是其他复杂操作的基础。
掌握几种简单基本的查找与排序的方法。
三、详细设计#include<stdio.h>qpass(int r[],int low,int hig){int i,j;int x;i=low;j=hig;x=r[low];while(i<j){while((i<j)&&(r[j]>=x)){j--;}r[i]=r[j];while((i<j)&&(r[i]<=x)){i++;}r[j]=r[i];}r[i]=x;return i;}void qs(int r[],int low,int hig){int i;if(low<hig){i=qpass(r,low,hig);qs(r,low,i-1);qs(r,i+1,hig);}}int main(){int a[10];int i;printf("请输入要排序的十个数字: \n");for(i=0;i<10;i++){scanf("%d",&a[i]);}qs(a,0,9);printf("结果为： \n");for(i=0;i<10;i++){printf("%d\n",a[i]);}return 0;}四、调试分析五、总结查找又称为检索，它是数据处理中使用频繁的一种操作。
排序是数据处理中经常使用的一种重要的运算。
它将一个数据元素的无序序列调整为一个有序序列。
首先先输入一串数组，相邻两个数比较大小，小者往前移动，一趟比较完后，最小的数冒到最前面。
较大的数排列倒数组的后面，经过n-1趟比较，数组长的数便排列好了。