1、计算机软件技术基础上机实验报告一、单链表实验内容：单链表的定义、创建、插入和删除操作，将数据显示出来。源程序 #include#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=(s
2、lnode *)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&jnext;j+; if(j!=i-1) p
3、rintf(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&jnext; j+; if(j!=i-1) printf(i is invalid!);return 0; else if(p-next=null) printf(i is invali
4、d!); 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)
5、; 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#define max 10Typedef struct /*定义结构体*/char stackmax; int top;qstype;qstype *s;initiateqs() /*初始化*/s-top=-1; return s;int push() /*入栈*/int x;
6、 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); /*将栈中元素显示
7、出来同时不改变栈中元素*/ 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#define null 0typedef struct node /*定义结构体*/int data; struct node *next;slnode;slnode *h;i
8、nitiatels() /*初始化*/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)
9、; 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#define max 10typedef structint queuemax; int front;int rear;qqtype; qqtype *q;void *initiateqq() /*初始化*/q-front=-1; q
10、-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-r
11、ear) /*输出出对元素*/ q-front+; printf(%5d,q-queueq-front); printf(n);3.2链式队实验内容：队的链式存储结构的定义、创建、插入和删除，将数据元素显示出来。 源程序#include#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(s
12、lnode); 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;
13、 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); 四、二叉树实验内容：二叉树的链式存储结构的数据定义、创建
14、先序、中序和后序遍历，并将结果序列输出。源程序#include#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-
15、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
16、(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) prorde
17、r(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(%
18、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
19、); bt=p; scanf(%d,&x); while(x!=-1) p=bt;q=p; while(x!=p-data&q!=null) p=q; if(xdata) q=p-lchild; else q=p-rchild; if(x=p-data) printf(The data is exit.);return; else if(xdata) ins_lchild(p,x); else ins_rchild(p,x); scanf(%d,&x); p=bt; printf(structure of the binary tree:n); printf(numbertaddresstda
20、tatlchildtrchildn); prorder(p); printf(preorder:); preorder(p); printf(n); printf(inorder:); inorder(p); printf(n); printf(postorder:); postorder(p); printf(n);五、查找5.1顺序查找源程序#include#define max 20int seq_search(int s,int k,int n) /*在序列s0sn-1中，从头开始顺序查找关键字为k的记录*/int i; sn=k; /*设置监视哨*/i=0;while(si!=k)
21、i+;if(in)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=0) printf(data%d=%dn,index,x); else printf(%d:not found.n,x);5.2二分查找源程序#include#define max 20int binary(int x,int list,int n) /*从lis
22、t中查找x*/int low,high,mid; low=0; high=n-1; while(low=high) mid=(low+high)/2; /*折半*/ if(xlistmid) /*在后部分查找*/ 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=0) printf(data%d=%dn,index,x);else printf(%d:not found.n,x);六、排序6.1插
23、入排序源程序#include#define max 40typedef structint key; char name;elemtype;elemtype xmax;void getsort(elemtype x,int n) /*输入记录的关键字*/int i; printf(Recorder:); for(i=0;in;i+) scanf(%d,&xi.key);void insertsort(elemtype x,int n) /*用直接插入排序法排序*/int i,j,k,m; elemtype swap; for(i=0;i-1&swap.keyxj.key) xj+1=xj; j
24、-; xj+1=swap; m=i+1; printf(No%d insertsortt,m); for(k=0;kn;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#define max 40typedef structint key; char name;elemtype;elemtype xmax;void getsort(elemtype x,int n) /*
25、输入待排序记录*/int i; printf(Recorder:); for(i=0;in;i+) scanf(%d,&xi.key);void selectsort(elemtype x,int n) /*对记录序列进行直接选择排序*/int i,j,small,k,m; elemtype swap; for(i=0;in-1;i+) /*在剩余记录序列中选择关键字最小的记录*/ small=i; for(j=i;jn;j+) if(xj.keyxsmall.key) small=j; if(small!=0) swap=xi; xi=xsmall; xsmall=swap; m=i+1; printf(No.%d selectsort:t,m); for(k=0;kn;k+) printf(%dt,xk.key); printf(n); main()elemtype xmax; int
