软件学-实验备课笔记

软件学基础 实验备课笔记

实验一 基本算法实现

一、实验目的

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(\}

五、实验结果与讨论：讨论实验算法改进，分析实验结果并记录。

0

软件学基础 实验备课笔记

实验二 线性表

一、实验目的

加深理解线性表的顺序表示与链式表示的意义和区别；掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。 二、实验设备：计算机一台 三、实验要求：

（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(\从键盘输入一个整数 */ printf(\请输入表元素:\\n\

for(i=0;i<10;i++) /* 输入表元素 */ scanf(\for(i=0;i<10;i++)

if(a[i]==x) break; /*在顺序表中找到x就退出循环， 变量 i的值就是x在表中的位置*/

if(i<10) printf(\在顺序表中的位置是:\\n%d\

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}

1

软件学基础 实验备课笔记

#include \#include main( )

{ SEQUENLIST a; int i, k, m, x;

printf(\请输入顺序表元素，元素为整型量，用空格分开，-99为结束标志 ：\

a.last = 0; i = 0; scanf(\

while (i != -99) {/*输入顺序表元素,建立有序表*/ k = a.last;

while((k>=1) && ( i

for(m = a.last; m >= k+1; m--) a.datas[m + 1] = a.datas[m]; a.datas[k + 1] = i; a.last++;

scanf(\

printf(\输入要插入的元素值(整型) : \ scanf(\

printf(\插入前有序表元素列表 ：\ for (i = 1; i <= a.last; i++) printf(\ printf(\ 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(\插入后有序表元素列表 ：\for (i = 1; i <= a.last; i++) printf(\ printf(\}

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 \

2

软件学基础 实验备课笔记

# 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(\while (i != -99) {

/*输入la顺序表元素，建立有序表*/ k = la.last;

while((k>=1) && ( i

for(m = la.last; m >= k+1; m--) la.datas[m + 1] = la.datas[m]; la.datas[k + 1] = i; la.last++;

scanf(\

3

软件学基础 实验备课笔记

printf(\请输入lb顺序表元素，元素为整型量，用空格分开，-99为结束标志 ：\

lb.last = 0; i = 0; scanf(\while (i != -99) {

/*输入lb顺序表元素，建立有序表*/ k = lb.last;

while((k>=1) && ( i

for(m = lb.last; m >= k+1; m--) lb.datas[m + 1] = lb.datas[m]; lb.datas[k + 1] = i; lb.last++;

scanf(\

printf(\有序表元素列表 ：\for (i = 1; i <= la.last; i++) printf(\printf(\

printf(\有序表元素列表 ：\for (i = 1; i <= lb.last; i++) printf(\printf(\

merge_sqlist (la, lb, &lc);

printf(\合并后lc有序表元素列表 ：\for (i = 1; i <= lc.last; i++) printf(\printf(\}

五、实验结果与讨论：讨论实验算法改进，分析实验结果并记录。

4

软件学基础 实验备课笔记

实验五 二叉树的建立与遍历

一、实验目的

1、 进一步掌握指针变量、动态变量的含义；

2、 掌握二叉树的结构特征，以及各种存储结构的特点及适用范围； 3、 掌握用指针类型描述、访问和处理二叉树的运算。 二、实验设备：计算机一台

三、实验要求：编程实现二叉树的建立与遍历。 四、实验内容：

1）二叉树的建立：

2）已知以二叉链表作存储结构，试编写按层次顺序遍历二叉树的算法。 算法思想：本算法要采用一个队列q，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉树的目的。

编制程序实现：要求采用二叉链表作为存储结构，完成二叉树的建立算法、二叉树的非递归遍历的操作。

3）求二叉树深度。

五、实验结果与讨论：讨论实验算法改进，分析实验结果并记录。 六、参考程序 参考程序1：

BTCHINALR * createbt( ) { BTCHINALR *q;

struct node1 *s[30]; int j,i,x;

printf(\建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开\\n\\n\

printf(\ scanf(\ while(i != 0 && x != '$')

{q = (BTCHINALR*)malloc(sizeof(BTCHINALR)); /*建立一个新结点q*/ q->data = x; q->lchild = NULL; q->rchild = NULL; s[i] = q; /*q新结点地址存入s指针数组中*/ if(i != 1) /*i = 1，对应的结点是根结点*/ {j = i / 2; /*求双亲结点的编号j*/

if(i % 2 == 0) s[j]->lchild = q; /*q结点编号为偶数则挂在双亲结点j的左边*/

else s[j]->rchild = q;} /*q结点编号为奇数则挂在双亲结点j的右边*/

10

软件学基础 实验备课笔记

printf(\

scanf(\

return s[1]; /*返回根结点地址*/ }

参考程序2（1）：二叉树遍历 #include \#include \#define 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 ((all[i]==0)||i>16) {

*T=NULL; return OK; }

*T=new();

if(*T==NULL) return ERROR; (*T)->data=all[i];

CreateSubTree(&((*T)->l),all,2*i); CreateSubTree(&((*T)->r),all,2*i+1); }

CreateBiTree(BiTree *T) {

ElemType all[16]={0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,};

11

软件学基础 实验备课笔记

CreateSubTree(T,all,1); }

printelem(ElemType d) {

printf(\}

PreOrderTraverse(BiTree T,int (*Visit)(ElemType d)) {

if(T){

if(Visit(T->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 \#include #include \二叉树.c\

void inorder(BTCHINALR *bt) /*中序遍历二叉树(递归算法)*/ {if(bt != NULL)

{ inorder(bt->lchild); printf(\ inorder(bt->rchild); } }

void inorder_notrecursive(BTCHINALR *bt) /*中序遍历二叉树(非递归算法)*/

12

软件学基础 实验备课笔记

{BTCHINALR *q, *s[20]; int top = 0; int bool = 1;

q = bt;

do {while(q != NULL)

{ top ++; s[top] = q; q = q->lchild; } if(top == 0) bool = 0; else { q = s[top]; top --;

printf(\ q = q->rchild; } }while(bool); }

main( )

{ BTCHINALR *bt; char ch; int i;

bt = createbt(); i = 1; while(i) {

printf(\中序遍历二叉树(递归按y键，非递归按n键): \ fflush(stdin); scanf(\

if(ch == 'y') inorder(bt); else inorder_notrecursive(bt); printf(\

printf(\继续操作吗?(继续按1键，结束按0键): \ fflush(stdin); scanf(\ } }

参考程序3：求二叉树深度 #include #include \#include #include \二叉树.c\

int treehight(BTCHINALR *bt) { int lh, rh, h;

13

软件学基础 实验备课笔记

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(\二叉树深度 = %d\\n\\n\}

14

本文来源：https://www.bwwdw.com/article/avzf.html