2019年计算机软件技术基础上机实验报告.doc

一、单链表实验内容：单链表的定义、创建、插入和删除操作，将数据显示出来。源程序 #include<stdio.h>#define null 0#define slnode struct nodeslnode /*定义结构体*/int data; slnode *next;slnode *h;slnode *create_sl() slnode *p,*s; int x; h=(slnode *)malloc(sizeof(slnode); p=h; h->next=null; /*初始化*/ x=get_data(); while(x!=-1) /*创建，以输入-1结束*/ s=(slnode *)malloc(sizeof(slnode); s->data=x; if(h->next=null) h->next=s; else p->next=s; p=s; x=get_data(); p->next=null; return h;get_data() /*获取数据元素*/int x; scanf("%d",&x); return x;slnode *insert(slnode *h,int i,int x) /*在第i个结点处插入数据元素x*/slnode *p,*s; int j;p=h;j=0; while(p->next!=null&&j<i-1) p=p->next;j+; if(j!=i-1) printf("i is invalid!"); return 0; else s=(slnode *)malloc(sizeof(slnode); s->data=x; s->next=p->next; p->next=s; return h;slnode *delete(slnode *h,int i) /*删除第i个结点*/slnode *p,*s; int j;p=h;j=0; while(p->next!=null&&j<i-1) p=p->next; j+; if(j!=i-1) printf("i is invalid!");return 0; else if(p->next=null) printf("i is invalid!"); return 0; else s=p->next; p->next=s->next; free(s); return h; void print(slnode *h) /*显示链表中的数据元素*/slnode *p; printf("nNow,These records are:n"); p=h->next; if(h!=null) do printf("%5d",p->data); p=p->next; while(p!=null);void main() /*主函数，调用各个函数*/slnode *h; int t,data,m; h=create_sl(); print(h); printf("n"); scanf("%d%d",&t,&data); h=insert(h,t,data); print(h); printf("n"); scanf("%d",&m); h=delete(h,m); print(h);二、栈2.1顺序栈实验内容：栈的顺序存储结构的定义、创建、插入和删除，将数据元素显示出来。 源程序#include<stdio.h>#define max 10Typedef struct /*定义结构体*/char stackmax; int top;qstype;qstype *s;initiateqs() /*初始化*/s->top=-1; return s;int push() /*入栈*/int x; if(s->top>=max-1) /*栈满则结束*/ return 0; else while(x=get_data()!=-1) s->top+; s->stacks->top=x; /*将x进栈*/ return 1; get_data() int x; scanf("%d",&x); return x;main()int sign; qstype *s; s=initiateqs(); sign=push(); if(sign=0) printf("overflow"); else int p; p=s->top; while(p!=-1) printf("%5d",s->stackp); /*将栈中元素显示出来同时不改变栈中元素*/ p-; printf("n"); if(s->top=-1) printf("null"); else while(s->top!=-1) printf("%5d",s->stacks->top); /*只能删除栈顶元素*/ s->top-; printf("n"); /*将栈中元素显示出来同时删除栈中元素*/2.2链式栈实验内容：栈的链式存储结构的定义、创建、插入和删除，将数据元素显示出来。 源程序#include<stdio.h>#define null 0typedef struct node /*定义结构体*/int data; struct node *next;slnode;slnode *h;initiatels() /*初始化*/h=(slnode *)malloc(sizeof(slnode); h->next=null; /*创建头结点*/ return h;pushls(slnode *h,int x) /*把数据元素插入栈中*/slnode *p; p=(slnode *)malloc(sizeof(slnode); p->data=x; p->next=h->next; h->next=p;main()int ch; slnode *h,*p; h=initiatels(); scanf("%d",&ch); while(ch!=-1) /*输入以-1结束*/ pushls(h,ch); scanf("%d",&ch); p=h->next; while(p->next!=null) /*输出栈中元素同时删除*/ p=h->next; h->next=p->next; ch=p->data; printf("%5d",ch); printf("n");三、队3.1顺序队实验内容：队的顺序存储结构的定义、创建、插入和删除，将数据元素显示出来。 源程序 #include<stdio.h>#define max 10typedef structint queuemax; int front;int rear;qqtype; qqtype *q;void *initiateqq() /*初始化*/q->front=-1; q->rear=-1;int enterqq(qqtype *q) /*入队*/int x; if(q->rear=max-1) /*队已满/ return 0; else while(x=get_data()!=-1) q->rear+;q->queueq->rear=x; return 1;get_data() /*输入数据元素*/ int x; scanf("%d",&x); return x;main()int sign; qqtype *q; q=initiateqq(); if(sign=enterqq(q)=1) printf("creat queue:n"); while(q->front!=q->rear) /*输出出对元素*/ q->front+; printf("%5d",q->queueq->front); printf("n");3.2链式队实验内容：队的链式存储结构的定义、创建、插入和删除，将数据元素显示出来。 源程序#include<stdio.h>#define null 0typedef struct nodeint data; struct node *next;slnode;typedef struct /*定义链式队列结构体*/slnode *h; slnode *rear;lqtype;void initiatelq(lqtype *q)q->h=(slnode *)malloc(sizeof(slnode); q->rear=q->h; q->h->next=null;void enterlq(lqtype *q) /*入队*/int x; while(x=get_data()!=-1) slnode *p; p=(slnode *)malloc(sizeof(slnode); p->data=x; p->next=null; if(q->h=null) q->h=p; q->rear->next=p; q->rear=p;get_data() /*输入数据元素*/ int x; scanf("%d",&x); return x;int deletelq(lqtype *q) /*出队*/slnode *p; int x; if(q->h->next=null) return -1; /*队以空*/ elsep=q->h->next;q->h->next=p->next;x=p->data;free(p); if(q->h->next=null) q->rear->next=null; return x; /*返回队头元素*/main()int t; lqtype *q; initiatelq(q); enterlq(q); printf("out queue:"); while(t=deletelq(q)!=-1) printf("%5d",t); printf("n"); 四、二叉树实验内容：二叉树的链式存储结构的数据定义、创建先序、中序和后序遍历，并将结果序列输出。源程序#include<stdio.h>#define null 0int counter=0;typedef struct btreenode /*定义二叉树结构体*/int data; struct btreenode *lchild; struct btreenode *rchild;bnode;bnode *p;bnode *creat(int x,bnode *lbt,bnode *rbt) /*建立一个只有根结点的二叉树*/bnode *p; p=(bnode *)malloc(sizeof(bnode); p->data=x; p->lchild=lbt; p->rchild=rbt; return p;bnode *ins_lchild(bnode *p,int x) /*以x作为左孩子插入*/bnode *q; if(p=null) printf("illegal insert."); else q=(bnode *)malloc(sizeof(bnode); q->data=x; q->lchild=null; q->rchild=null; if(p->lchild!=null) q->rchild=p->lchild; p->lchild=q;bnode *ins_rchild(bnode *p,int x) /*以x作为右孩子插入*/bnode *q; if(p=null) printf("illegal insert"); else q=(bnode *)malloc(sizeof(bnode); q->data=x; q->lchild=null; q->rchild=null; if(p->rchild!=null) q->lchild=p->rchild; p->rchild=q;void prorder(bnode *p) /*输出二叉树的结构*/if(p=null) return; printf("%dt%ut%dt%ut%un",+counter,p,p->data,p->lchild,p->rchild); if(p->lchild!=null) prorder(p->lchild); if(p->rchild!=null) prorder(p->rchild);void preorder(bnode *p) /*前序遍历二叉树*/if(p=null) return; printf("%5d",p->data); if(p->lchild!=null) preorder(p->lchild); if(p->rchild!=null) preorder(p->rchild);void inorder(bnode *p) /*中序遍历二叉树*/if(p=null) return; if(p->lchild!=null) inorder(p->lchild); printf("%5d",p->data); if(p->rchild!=null) inorder(p->rchild); void postorder(bnode *p) /*后序遍历二叉树*/if(p=null) return; if(p->lchild!=null) postorder(p->lchild); if(p->rchild!=null) postorder(p->rchild); printf("%5d",p->data);main()bnode *bt,*p,*q; int x; printf("Input root:"); /*建立排序二叉树*/ scanf("%d",&x); p=creat(x,null,null); bt=p; scanf("%d",&x); while(x!=-1) p=bt;q=p; while(x!=p->data&&q!=null) p=q; if(x<p->data) q=p->lchild; else q=p->rchild; if(x=p->data) printf("The data is exit.");return; else if(x<p->data) ins_lchild(p,x); else ins_rchild(p,x); scanf("%d",&x); p=bt; printf("structure of the binary tree:n"); printf("numbertaddresstdatatlchildtrchildn"); prorder(p); printf("preorder:"); preorder(p); printf("n"); printf("inorder:"); inorder(p); printf("n"); printf("postorder:"); postorder(p); printf("n");五、查找5.1顺序查找源程序#include<stdio.h>#define max 20int seq_search(int s,int k,int n) /*在序列s0sn-1中，从头开始顺序查找关键字为k的记录*/int i; sn=k; /*设置监视哨*/i=0;while(si!=k) i+;if(i<n)printf("find it."); return i; /*找到，返回位置值i*/else printf("not find it."); return -1; int getdata(int list) /*输入序列*/int num,i;printf("total=");scanf("%d",&num);for(i=0;i<num;i+) printf("data%d=",i); scanf("%d",&listi); return num; /*返回序列记录个数*/main()int listmax,n,index,x; n=getdata(list); printf("search key="); scanf("%d",&x); index=seq_search(list,x,n); if(index>=0) printf("data%d=%dn",index,x); else printf("%d:not found.n",x);5.2二分查找源程序#include<stdio.h>#define max 20int binary(int x,int list,int n) /*从list中查找x*/int low,high,mid; low=0; high=n-1; while(low<=high) mid=(low+high)/2; /*折半*/ if(x<listmid) /*在前部分查找*/ high=mid-1; else if(x>listmid) /*在后部分查找*/ low=mid+1; else return mid; return -1;int getdata(int list) /*输入数组list*/int num,i; printf("total="); scanf("%d",&num); for(i=0;i<num;i+) printf("data%d=",i); scanf("%d",&listi); return num;main()int listmax,n,index,x;n=getdata(list);printf("search key="); /*输入待查找数据*/scanf("%d",&x);index=binary(x,list,n);if(index>=0) printf("data%d=%dn",index,x);else printf("%d:not found.n",x);六、排序6.1插入排序源程序#include<stdio.h>#define max 40typedef structint key; char name;elemtype;elemtype xmax;void getsort(elemtype x,int n) /*输入记录的关键字*/int i; printf("Recorder:"); for(i=0;i<n;i+) scanf("%d",&xi.key);void insertsort(elemtype x,int n) /*用直接插入排序法排序*/int i,j,k,m; elemtype swap; for(i=0;i<n-1;i+) swap=xi+1; j=i; while(j>-1&&swap.key<xj.key) xj+1=xj; j-; xj+1=swap; m=i+1; printf("No%d insertsortt",m); for(k=0;k<n;k+) printf("%dt",xk.key); printf("n"); main()elemtype xmax; int n; printf("n="); scanf("%d",&n); getsort(x,n); insertsort(x,n);6.2选择排序源程序#include<stdio.h>#define max 40typedef structint key; char name;elemtype;elemtype xmax;void getsort(elemtype x,int n) /*输入待排序记录*/int i; printf("Recorder:"); for(i=0;i<n;i+) scanf("%d",&xi.key);void selectsort(elemtype x,int n) /*对记录序列进行直接选择排序*/int i,j,small,k,m; elemtype swap; for(i=0;i<n-1;i+) /*在剩余记录序列中选择关键字最小的记录*/ small=i; for(j=i;j<n;j+) if(xj.key<xsmall.key) small=j; if(small!=0) swap=xi; xi=xsmall; xsmall=swap; m=i+1; printf("No.%d selectsort:t",m); for(k=0;k<n;k+) printf("%dt",xk.key); printf("n"); main()elemtype xmax; int n; printf("n="); scanf("%d",&n); /*输入待排序的元素个数*/ getsort(x,n); /*输入待排序的元素*/ selectsort(x,n); /*直接选择排序*/6.3冒泡排序源程序#include<stdio.h>#define max 40typedef structint key; char name;elemtype;elemtype xmax;void getsort(elemtype x,int n) /*输入待排序记录*/int i; printf("Recorder:"); for(i=0;i<n;i+) scanf("%d",&xi.key);void hubblesort(elemtype x,int n) /*用冒泡法排序*/int i,j,k,flag; elemtype swap; flag=1; for(i=1;i<n&&flag=1;i+) flag=0; for(j=0;j<n-1;j+) if(xj.key>xj+1.key) /*比较两数的大小*/ flag=1; swap=xj; xj=xj+1; xj+1=swap; if(flag=0) return; main()elemtype xmax; int n,i; printf("n="); /*输入待排序记录的个数*/ scanf("%d",&n); getsort(x,n); hubblesort(x,n); printf("Output the number:"); for(i=0;i<n;i+) printf("%dt",xi); /*输出以排好的序列*/ printf("n");七、实验收获 通过这次的上机实验，我巩固和提高了大一时学的C语言编程能力，当时只是学的只是一些简单算法的实现，这次在之前的基础上涉及到了链表、队、栈、二叉树等数据结构，选择合适的数据结构可以提高在一定程度上降低时间和空间复杂度，提高运算效率，实现算法的最优化。链表可以根据需要随时开辟动态空间，提高内存的利用率，对于插入、删除操作也很简单。对于队和栈只能从固定的一端插入和删除，用于解决一些特殊的问题。二叉树的用途也极为广泛，以及由二叉树衍生出的排序、最优、线索二叉树。 在实验过程中也遇到了各种困难，从不知道怎么写声明区的编写如包含文件，宏定义，函数声明，全局变量声明，结构体等的定义到程序写完后的语法错误以及出现死循环等情况。只能抱着各种指导书，对照着程序去找错误，刚开始程序写得很慢，还要花很长时间去调试，后来慢慢地总结出经验，把这个过程分成四部分进行，一、定义，二、写被调用的子函数，三、主函数，四、调试，每一步的基础是理解，理解每种数据结构的存储方式、各个步骤的目的和原理，写完后开始调试，根据错误提示，有方向、有目的地去纠错，先检查是不是有语法错误，在深入检查。有时会碰到死循环的情况，这是因为没有设置好终止条件，如对于数据元素x的输入，以-1的输入作为终止的条件。我们往往写不出程序，这其中的原因我觉得是对程序的结构不是很了解，对实验的内容也不熟练的结果，数据结构给我们许多程序的算法和模型，对我们写程序的思维有很大的锻炼，我们应珍惜每次上机实验的机会去实践课堂上所学的东西并从中发现问题，从而达到提升写程序的能力。实验时不要以写完作为目的，当程序运行成功后，可以尝试用其他的方法，多想、多实践，如果把程序稍作改动会不会影响结果，为什么会影响，不要怕出现错误，这样才知道自己的哪些想法是错误的。这才是实验的真正目的，在实验中收获知识，提升自己。 15