3124.软件学实验备课笔记.doc

软件学基础 实验备课笔记 实验一 基本算法实现一、实验目的1. 熟练掌握C语言及其调试开发环境；2. 积累用C语言编写调试程序的经验；3. 掌握基本算法有关的知识，具有较好的算法设计和分析的能力二、实验设备：计算机三、实验要求：熟练掌握C语言及其上机调试环境(如TC2.0或VC6.0)的操作使用四、实验内容百钱百鸡问题中国古代数学家张丘建在他的《算经》中提出了著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何?问题分析与算法设计：这是一个典型的数值型问题，我们要首先建立这个问题的数学模型，数学模型也就是我们平时说的数学方程假设：我们要买x只公鸡，y只母鸡，z只小鸡，根据题目的意思可以得到两个方程：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++) /* 穷举变量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=%2d\n", ++j, x, y, z);}五、实验结果与讨论：讨论实验算法改进，分析实验结果并记录实验二 线性表一、实验目的加深理解线性表的顺序表示与链式表示的意义和区别；掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算二、实验设备：计算机一台三、实验要求：（1）给出程序设计的基本思想、原理和算法描述2）源程序给出注释3）记录程序的运行结果，并结合程序进行分析。

四、实验内容1、从键盘上输入一个整数x 和一个顺序表L，在顺序表L中查找x的位置若找到，则显示值x在L中的下标；否则显示“该数不存在”查找算法示例程序：#include#define N 10 /* 定义顺序表中元素个数 */ main() { int i,x; int a[N]; /* 定义顺序表 */ clrscr(); /* 清屏 */ printf("请输入一个整数:\n"); /* 提示从键盘上输入整数 */ scanf("%d",&x); /* 从键盘输入一个整数 */ printf("请输入表元素:\n"); for(i=0;i<10;i++) /* 输入表元素 */ scanf("%d",&a[i]); for(i=0;i<10;i++) if(a[i]==x) break; /*在顺序表中找到x就退出循环， 变量 i的值就是x在表中的位置*/ if(i<10) printf("x在顺序表中的位置是:\n%d",i); else printf("该数不存在!"); /* 如果i值大于等于10的话，说明找不到该数 */ } 2、在有序表中插入一个元素并保持该表仍然有序。

选做）题目要求：按用户输入的数据建立一个有序表（表中元素按递增有序）将指定元素插入表中适当位置，并保持该表有序表的有序性测试数据：s={10,23,34,5,61,72,29,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.datas[m + 1] = a.datas[m]; a.datas[k + 1] = i; a.last++; scanf("%d",&i); } printf("输入要插入的元素值(整型) : "); scanf("%d",&x); printf("\n插入前有序表元素列表 ："); for (i = 1; i <= a.last; i++) printf("%4d",a.datas[i]); printf("\n"); i = a.last; while ((i >= 1) && ( x < a.datas[i])) i--; /*查找插入位置i */ for(m = a.last; m >= i + 1; m--) a.datas[m + 1] = a.datas[m]; /*移动元素 */ a.datas[i + 1] = x; /*新元素插入*/ a.last++; /*表长加1 */ printf("\n插入后有序表元素列表 ：");for (i = 1; i <= a.last; i++) printf("%4d",a.datas[i]); 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 *lc){/*两有序表合并*/ int i , j , k ; i = j = k = 1 ; while( i <= la.last && j <= lb.last ) if( la.datas[i] <= lb.datas[j]) {lc->datas[k] = la.datas[i] ; k++ ; i++ ; } else {lc->datas[k] = lb.datas[j] ; k++ ; j++ ; } while( i <= la.last ) { lc->datas[k] = la.datas[i] ; k++ ; i++ ;} while( j <= lb.last ) { lc->datas[k] = lb.datas[j] ; k++ ; j++ ;} lc->last = k - 1; return;}main( ){ SEQUENLIST la, lb, lc; 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.datas[m + 1] = la.datas[m]; la.datas[k + 1] = i; la.last++; scanf("%d",&i); }printf("\n\n请输入lb顺序表元素，元素为整型量，用空格分开，-99为结束标志 ：");lb.last = 0; i = 0; scanf("%d",&i);while (i != -99) {/*输入lb顺序表元素，建立有序表*/ k = lb.last; while((k>=1) && ( i= k+1; m--) lb.datas[m + 1] = lb.datas[m]; lb.datas[k + 1] = i; lb.last++; scanf("%d",&i); }printf("\nla有序表元素列表 ：");for (i = 1; i <= la.last; i++) printf("%4d",la.datas[i]);printf("\n");printf("\nlb有序表元素列表 ：");for (i = 1; i <= lb.last; i++) printf("%4d",lb.datas[i]);printf("\n");merge_sqlist (la, lb, &lc);printf("\n合并后lc有序表元素列表 ：");for (i = 1; i <= lc.last; i++) printf(" %d",lc.datas[i]);printf("\n");}五、实验结果与讨论：讨论实验算法改进，分析实验结果并记录。

实验三 栈与队列一、实验目的掌握栈与队列的基本操作，并能对其进行简单应用二、实验设备：计算机一台三、实验要求：（1）给出程序设计的基本思想、原理和算法描述2）源程序给出注释3）记录程序的运行结果，并结合程序进行分析四、实验内容（1）利用栈的基本操作将一个十进制的正整数转换成二进制数据，并将其转换结果输出2）利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Right”，否则输出“Wrong”3）假设循环队列中只设rear和quelen来分别表示队尾元素的位置和队中元素的个数，写出相应的入队和出队程序五、实验结果与讨论：讨论实验算法改进，分析实验结果并记录六、实验参考程序参考程序1：#define N 32 /* 定义栈的大小 */ #include"stdio.h"main() { int i,x; /* i为循环变量，x为十进制正整数变量 */ int m,n; /* m表示商，n表示余数 */ 。