3124.软件学实验备课笔记

1、 实验一 基本算法实现一、实验目的1. 熟练掌握c语言及其调试开发环境；2. 积累用c语言编写调试程序的经验；3. 掌握基本算法有关的知识，具有较好的算法设计和分析的能力。二、实验设备：计算机三、实验要求：熟练掌握c语言及其上机调试环境(如tc2.0或vc6.0)的操作使用。四、实验内容百钱百鸡问题。中国古代数学家张丘建在他的算经中提出了著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何?问题分析与算法设计：这是一个典型的数值型问题，我们要首先建立这个问题的数学模型，数学模型也就是我们平时说的数学方程。假设：我们要买x只公鸡，y只母鸡，z只小鸡

2、，根据题目的意思可以得到两个方程：x+y+z=100 5x+3y+z/3=100 根据题目的意思，我们可以确定x和y的取值范围：0 = x、y、z = 100。我们可以采用穷举法进行求解。对于变量x,y,z的不同组合，看它们是否满足上面的两个方程，如果满足了，就是问题的一个解。如果不满足，就不是问题的解。我们可以采用三重嵌套的循环对变量x,y,z进行组合。我们可以写出程序1。程序1：#include main( )int x, y, z, j=0; /* j为计数器，记录解的数量 */ for (x=0; x=100; x+) /* 穷举变量x */ for (y=0; y=100; y+)

3、/* 穷举变量y */ for (z=0; z=100; z+) /* 穷举变量z */if ( x+y+z=100 & 5*x+3*y+z/3=100 ) /* 判断是否满足两个方程 */ printf(%2d:cock=%2d hen=%2d chicken=%2dn, +j, x, y, z);五、实验结果与讨论：讨论实验算法改进，分析实验结果并记录。实验二 线性表一、实验目的加深理解线性表的顺序表示与链式表示的意义和区别；掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。二、实验设备：计算机一台三、实验要求：（1）给出程序设计的基本思想、原

4、理和算法描述。（2）源程序给出注释。（3）记录程序的运行结果，并结合程序进行分析。四、实验内容1、从键盘上输入一个整数x 和一个顺序表l，在顺序表l中查找x的位置。若找到，则显示值x在l中的下标；否则显示“该数不存在”。查找算法示例程序：#include#define n 10 /* 定义顺序表中元素个数 */ main() int i,x; int an; /* 定义顺序表 */ clrscr(); /* 清屏 */ printf(请输入一个整数:n); /* 提示从键盘上输入整数 */ scanf(%d,&x); /* 从键盘输入一个整数 */ printf(请输入表元素:n); for(

5、i=0;i10;i+) /* 输入表元素 */ scanf(%d,&ai); for(i=0;i10;i+) if(ai=x) break; /*在顺序表中找到x就退出循环， 变量 i的值就是x在表中的位置*/ if(i10) printf(x在顺序表中的位置是:n%d,i); else printf(该数不存在!); /* 如果i值大于等于10的话，说明找不到该数 */ 2、在有序表中插入一个元素并保持该表仍然有序。（选做）题目要求：按用户输入的数据建立一个有序表（表中元素按递增有序）。将指定元素插入表中适当位置，并保持该表有序表的有序性。测试数据：s=10,23,34,5,61,72,29

6、,20运行结果：s=5,10,20,23,29,34,61,72插入值：25插入后：s=5,10,20,23,25,29,34,61,72#include datastru.h#include main( ) sequenlist a; int i, k, m, x; printf(请输入顺序表元素，元素为整型量，用空格分开，-99为结束标志 ：); a.last = 0; i = 0; scanf(%d,&i); while (i != -99) /*输入顺序表元素,建立有序表*/ k = a.last; while(k=1) & ( i= k+1; m-) a.datasm + 1 = a

7、.datasm; a.datask + 1 = i; a.last+; scanf(%d,&i); printf(输入要插入的元素值(整型) : ); scanf(%d,&x); printf(n插入前有序表元素列表 ：); for (i = 1; i = 1) & ( x = i + 1; m-) a.datasm + 1 = a.datasm; /*移动元素 */ a.datasi + 1 = x; /*新元素插入*/ a.last+; /*表长加1 */ printf(n插入后有序表元素列表 ：);for (i = 1; i = a.last; i+) printf(%4d,a.data

8、si); printf(n);3、两个有序表的合并（选做）题目要求：按用户输入的数据建立两个有序表la和lb（元素值和按递增有序），合并成一个新的递增有序的顺序表lc。在lc中值相同的元素均保留，即lc表长=la表长+lb表长。测试数据：la=10,23,34,5,61,72,29,20; lb=1,3,34,61,56,21,11运行结果：lc=1,3,10,11,20,21,23,29,34,34,56,61,61,72# include datastru.h# include void merge_sqlist(sequenlist la,sequenlist lb,sequenlist

9、 *lc)/*两有序表合并*/ int i , j , k ; i = j = k = 1 ; while( i = la.last & j = lb.last ) if( la.datasi datask = la.datasi ; k+ ; i+ ; else lc-datask = lb.datasj ; k+ ; j+ ; while( i datask = la.datasi ; k+ ; i+ ; while( j datask = lb.datasj ; k+ ; j+ ; lc-last = k - 1; return;main( ) sequenlist la, lb, lc

10、; int i, k, m;printf(请输入la顺序表元素，元素为整型量，用空格分开，-99为结束标志 ：);la.last = 0; i = 0; scanf(%d,&i);while (i != -99) /*输入la顺序表元素，建立有序表*/k = la.last;while(k=1) & ( i= k+1; m-) la.datasm + 1 = la.datasm;la.datask + 1 = i;la.last+;scanf(%d,&i); printf(nn请输入lb顺序表元素，元素为整型量，用空格分开，-99为结束标志 ：);lb.last = 0; i = 0; sca

11、nf(%d,&i);while (i != -99) /*输入lb顺序表元素，建立有序表*/k = lb.last;while(k=1) & ( i= k+1; m-) lb.datasm + 1 = lb.datasm;lb.datask + 1 = i;lb.last+;scanf(%d,&i); printf(nla有序表元素列表 ：);for (i = 1; i = la.last; i+) printf(%4d,la.datasi);printf(n);printf(nlb有序表元素列表 ：);for (i = 1; i = lb.last; i+) printf(%4d,lb.da

12、tasi);printf(n);merge_sqlist (la, lb, &lc);printf(n合并后lc有序表元素列表 ：);for (i = 1; i =0;i-) printf(%d,ai); printf(n);参考程序2：非负十进制整数转换为八进制数的非递归算法#include datastru.h#include void initstack(seqstack *s) /*顺序栈初始化*/ s-top = 0; datatype1 gettop(seqstack *s) /*返回栈顶元素*/ datatype1 x; if(s-top = 0) printf(栈空n); x

13、= 0; else x = (s-data)s-top; return x; int push(seqstack *s, datatype1 x)/*元素x入栈*/ if(s-top = maxsize - 1) printf(栈满n); return 0; else s-top +; (s-data)s-top = x; return 1;datatype1 pop(seqstack *s) /*返回栈顶元素并删除栈顶元素*/ datatype1 x; if(s-top = 0) printf(栈空n); x = 0; else x = (s-data)s-top; s-top-; retu

14、rn x;main( )seqstack stack, *s;int n;s = &stack;initstack(s);n = 0;printf(输入一非负整数(十进制) ：);scanf(%d,&n);push(s,#);while(n != 0) push(s, n % 8); /* %为求余数运算符, 余数入栈*/ n = n / 8; /* /为求整数商运算符,商不为零,继续运行*/printf(nn对应的八进制数为 ：);while(gettop(s) != #) printf(%d,pop(s);printf(n);实验四 递归程序设计一、实验目的：训练递归程序的设计方法。二、实

15、验设备：计算机一台三、实验要求（1）先认真阅读本实验的程序，再将其补充完整后运行。（2）保存和打印出程序的运行结果，并结合程序进行分析。（3）重新改写主程序并运行，打印出文件清单和运行结果四、实验内容1、有如下递归函数：void print(int w) int i; if (w!=0) print(w-1); for ( i=1;i0) printf(%6dn,n %10); printrv(n/10);调用语句printrv(12345)。（2）void pc(int m,int n,int *k)if ( n= =0 )*k=1;else pc( m-1, n-1, k);*k=*k*m

16、 / n ;调用语句pc(10,4,&m) ;printf (“%d”, m ) ;（3）intss ( int n)if ( n= =0 )return 100;else return ss( n-1)+n*n; 调用语句printf( “%d”, ss (6 )（4）int acm ( int m , int n )if (m0 | n0 ) printf(“ error”);else if ( m= =0)acm=n+1;else if (n= =0)return acm(m-1,1) ;elsereturn acm (m-1 , acm( m , n-1);调用语句printf(“%d

17、”,acm (2,2) ;参考程序1：非负十进制整数转换为八进制数的递归算法#include void d_to_or(int x)/*非负十进制整数转换为八进制数的递归算法*/ if(x / 8 != 0)d_to_or(x / 8); printf(%d,x % 8);main( ) int x;printf(输入一非负整数(十进制) ：);scanf(%d,&x);printf(nn对应的八进制数为 ：);d_to_or(x);printf(nn);五、实验结果与讨论：讨论实验算法，分析实验结果并记录。实验五 二叉树的建立与遍历一、实验目的1、 进一步掌握指针变量、动态变量的含义；2、

18、掌握二叉树的结构特征，以及各种存储结构的特点及适用范围；3、 掌握用指针类型描述、访问和处理二叉树的运算。二、实验设备：计算机一台三、实验要求：编程实现二叉树的建立与遍历。四、实验内容：1）二叉树的建立：2）已知以二叉链表作存储结构，试编写按层次顺序遍历二叉树的算法。算法思想：本算法要采用一个队列q，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉树的目的。编制程序实现：要求采用二叉链表作为存储结构，完成二叉树的建立算法、二叉树的非递归遍历的操作。3）

19、求二叉树深度。五、实验结果与讨论：讨论实验算法改进，分析实验结果并记录。六、参考程序参考程序1：btchinalr * createbt( )btchinalr *q;struct node1 *s30;int j,i,x;printf(建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开nn);printf(i,x = );scanf(%d,%c,&i,&x);while(i != 0 & x != $) q = (btchinalr*)malloc(sizeof(btchinalr); /*建立一个新结点q*/ q-data = x; q-lchild = null; q-rchil

20、d = null; si = q; /*q新结点地址存入s指针数组中*/ if(i != 1) /*i = 1，对应的结点是根结点*/ j = i / 2; /*求双亲结点的编号j*/ if(i % 2 = 0) sj-lchild = q; /*q结点编号为偶数则挂在双亲结点j的左边*/ else sj-rchild = q; /*q结点编号为奇数则挂在双亲结点j的右边*/ printf(i,x = ); scanf(%d,%c,&i,&x);return s1; /*返回根结点地址*/参考程序2（1）：二叉树遍历#include malloc.h#include stdio.h#defin

21、e error 0;#define ok 1;typedef int elemtype;typedef struct binarytree elemtype data; struct binarytree *l; struct binarytree *r;*bitree,binode;binode * new() return( (binode *)malloc(sizeof(binode) );createsubtree(bitree *t,elemtype *all,int i) if (alli=0)|i16) *t=null; return ok; *t=new(); if(*t=nu

22、ll) return error; (*t)-data=alli; createsubtree(&(*t)-l),all,2*i); createsubtree(&(*t)-r),all,2*i+1);createbitree(bitree *t) elemtype all16=0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,; createsubtree(t,all,1);printelem(elemtype d) printf(%dn,d);preordertraverse(bitree t,int (*visit)(elemtype d) if(t) if(visit(t

23、-data) if(preordertraverse(t-l,visit)if(preordertraverse(t-r,visit) return ok; return error; else return ok;main() bitree root; createbitree(&root); preordertraverse(root,printelem);参考程序2（2）：二叉树中序遍历的递归算法#include #include datastru.h#include #include 二叉树.cvoid inorder(btchinalr *bt)/*中序遍历二叉树(递归算法)*/if

24、(bt != null)inorder(bt-lchild);printf(%c ,bt-data);inorder(bt-rchild);void inorder_notrecursive(btchinalr *bt)/*中序遍历二叉树(非递归算法)*/btchinalr *q, *s20; int top = 0; int bool = 1; q = bt; do while(q != null) top +; stop = q; q = q-lchild; if(top = 0) bool = 0; else q = stop; top -; printf(%c ,q-data); q

25、= q-rchild; while(bool); main( ) btchinalr *bt; char ch; int i; bt = createbt(); i = 1; while(i) printf(n中序遍历二叉树(递归按y键，非递归按n键): ); fflush(stdin); scanf(%c,&ch); if(ch = y) inorder(bt); else inorder_notrecursive(bt); printf(n); printf(n继续操作吗?(继续按1键，结束按0键):); fflush(stdin); scanf(%d,&i); 参考程序3：求二叉树深度#

26、include #include datastru.h#include #include 二叉树.cint treehight(btchinalr *bt)int lh, rh, h;if(bt = null)h = 0;else lh = treehight(bt-lchild);rh = treehight(bt-rchild);h = (lh rh ? lh : rh) + 1;return h;main( ) btchinalr *bt; int treeh; bt = createbt( ); treeh = treehight(bt); printf(n二叉树深度 = %dnn,t

27、reeh);实验六 图的遍历一、实验目的1、 掌握图的基本存储方法；2、 掌握有关图的操作算法并用高级语言实现；3、 熟练掌握图的两种搜索路径的遍历方法。二、实验设备：计算机三、实验要求：四、实验内容假设以一个带权有向图表示某一区域的公交线路网，图中顶点代表一些区域中的重要场所，弧代表已有的公交线路，弧上的权表示该线路上的票价（或搭乘所需时间），试设计一个交通指南系统，指导前来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。算法思想：下面是r、w、floyd求每对顶点之间最短路径算法的c语言程序，程序中矩阵a用来进行n次迭代，矩阵p用来记录路径，pij为迭代过程中当前已经求得的从

28、顶点i到顶点j的最短路径上最后被插入的那个顶点。算法实现：typedef struct node int no; float wgt; struct node *next;edgenode;typedef struct char vtx; edgenode *link; vexnode;typedef vexnode graphn;void floyd(graph g, float ann, int pnn) int i, j, k; for (i=0; in; i+) for(j=0;jn;j+) aij=gij; pij=-1; for (k=0; kn; k+) for (i=0; in

29、; i+) for (j=0; jn; j+) if(aik +akjaij) pij=k; aij=aik+akj; 参考程序2：连通图上实现广度优先遍历#include datastru.h#include #include adjgraph creat_adjgraph()edgenode *p;int i, s, d;adjgraph adjg;adjg.kind = 2;printf(nn输入顶点数和边数(用逗号隔开) : );scanf(%d,%d, &s, &d);fflush(stdin);adjg.vexnum = s; /*存放顶点数在adjg.vexnum中 */adjg

30、.arcnum = d; /*存放边点数在adjg.arcnum中*/printf(nn);for(i = 0; i adjg.vexnum; i+) printf(输入顶点 %d 的值 : , i + 1); scanf(%d, &adjg.adjlisti.vertex); /*输入顶点的值*/ fflush(stdin); adjg.adjlisti.link = null;printf(nn);for(i = 0; i adjg.arcnum; i+) printf(输入第 %d 条边的起始顶点和终止顶点(用逗号隔开): , i + 1); scanf(%d,%d, &s, &d);

31、/*输入边的起始顶点和终止顶点*/ fflush(stdin); while(s adjg.vexnum | d adjg.vexnum) printf(输入错，重新输入: ); scanf(%d,%d, &s, &d); s -; d -; p = malloc(sizeof(edgenode); /*建立一个和边相关的结点*/ p-adjvex = d; p-next = adjg.adjlists.link; /*挂到对应的单链表上*/ adjg.adjlists.link = p; p = malloc(sizeof(edgenode); /*建立另一个和边相关的结点*/ p-adjv

32、ex = s; p-next = adjg.adjlistd.link; /*挂到对应的单链表上*/ adjg.adjlistd.link = p;return adjg;void initlinkqueue(linkqueue *q)/*初始化广度遍历中用到的链队列*/q-front = malloc(sizeof(linkqlist);(q-front)-next = null;q-rear = q-front;int emptylinkqueue(linkqueue *q)/*判队列是否为空？*/int v;if(q-front = q-rear)v = 1;elsev = 0;retu

33、rn v;void enlinkqueue(linkqueue *q, datatype1 x)/*元素x入队列*/(q-rear)-next = malloc(sizeof(linkqlist);q-rear = (q-rear)-next;(q-rear)-data = x;(q-rear)-next = null;datatype1 dellinkqueue(linkqueue *q)/*删除队头元素*/linkqlist *p;datatype1 v;if(emptylinkqueue(q) printf(队列空.n);v = 0;else p = (q-front)-next;(q-

34、front)-next = p-next;if(p-next = null) q-rear = q-front;v = p-data;free(p);return v;void bfs(adjgraph adjg, int vi)/*连通图的广度遍历算法：从vi顶点出发*/int visitedmaxlen;int i, v;edgenode *p;linkqueue que, *q;q = &que;initlinkqueue(q);for(i = 0; i adjvex = 0) visitedp-adjvex = 1; printf( %d, adjg.adjlistp-adjvex.v

35、ertex); enlinkqueue(q, (p-adjvex)+1); /*遍历到的结点编号入队列*/ p = p-next; main()adjgraph ag;int j; printf(n连通图的广度遍历n); ag = creat_adjgraph(); /*建立连通图的邻接链表结构*/ printf(nn输入深度遍历起始顶点(1 - %d) : ,ag.vexnum); scanf(%d,&j); printf(nn广度遍历结果序列 : ); bfs(ag,j); /*连通图的广度遍历算法*/ printf(nn);五、实验结果与讨论：讨论实验算法改进，分析实验结果并记录。实验七

36、 查找一、实验目的掌握数据结构中查找的基本算法思想，并能进行应用。二、实验设备：计算机一台三、实验要求（1）给出程序设计的基本思想、原理和算法描述。（2）对源程序给出注释。（3）记录程序的运行结果，并结合程序进行分析四、实验内容：（1）编制顺序查找和对分查找算法，理解两者的区别。（2）查找表的存储结构为有序表，即表中记录按关键字大小排序存放。要求建立一个有序表，记录从下标为1的单元开始放入。输入待查纪录的关键字进行查找。五、实验结果与讨论：讨论实验算法改进，分析实验结果并记录。六、参考程序：参考程序1：顺序查找#include #include #define n 100typedef int

37、 keytype;typedef structkeytype key;nodetype;typedef nodetype seqlistn+1;seqlist r;main()int m,i,j;keytype k;printf(1-randam datan);printf(2-inscree datan);printf(3-descree datan);printf(4-input datan);scanf(%d,&j);if (j=1) randoming();if (j=2) for(i=1;i=n;i+) ri.key=i;if (j=3) for(i=1;i=n;i+) ri.key

38、=n-i+1;if (j=4)printf(input %n keys:n,n);for (i=1;i=n;i+)scanf(%d,&(ri.key);for(i=1;i=n;i+)printf(%d-%d ,i,ri.key);printf(n);printf(input k:n);scanf(%d,&k);printf(search position is:%dn,seqsearch(r,k);int seqsearch(seqlist r,keytype k)int i;r0.key=k;for(i=n;ri.key!=k;-i);return i;randoming()int i;ra

39、ndomize();i=1;while(i+=n)ri.key=random(1000);参考程序2：有序表上二分法查找元素#include datastru.h#include int search_bin(keytype k, sstable *st) /*有序表上二分法查找*/ int low, high, mid; low = 1; high = st-len; /*low = 1 表示元素从下标为1的单元放起*/ /*high = st-len 表示最后一个元素所在下标*/ while(low = high) /*low rmid.key) return mid; /*k = st-

40、rmid.key 表示查找成功*/ else if(k rmid.key) /*否则继续二分查找*/ high = mid - 1; else low = mid + 1; return 0; /*查找不成功，返回0*/main( ) sstable a; int i, j, k;printf(请输入有序表元素，元素为整型量（从小到大输入），用空格分开，-99为结束标志 ：);j = 0; k = 1; i = 0; scanf(%d,&i);while (i != -99) j+; a.rk.key = i; k+; scanf(%d,&i); /*输入有序表元素*/a.len = j;pr

41、intf(n有序表元素列表显示 ：);for (i = 1; i=a.len; i+) printf(%d ,a.ri);printf(n);printf(n输入待查元素关键字 : );scanf(%d,&i);k = search_bin(i, &a);if (k = 0) printf(表中待查元素不存在nn);else printf(表中待查元素存在nn);实验八 排序一、实验目的1、 掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；2、 深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；3、 了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。二、实验设备：计算机三、实验要求（1）给出程序设计的基本思想、原理和算法描述。（2）对源程序给出注释。（3）记录程序的运行结果，并结合程序进行分析四、实验内容1、将输入的若干整数按堆排序算法从小到大排序，数据从数组的1单元放起。2、将输入的若干整数按简单选择排序算法从小到大排序，数据从数组的1单元放起。*3、给定一含20个整型数据的数组，利用希尔排序方法将其进行非降序排列。