计算机软件基础二实验指导书文档格式.docx
《计算机软件基础二实验指导书文档格式.docx》由会员分享，可在线阅读，更多相关《计算机软件基础二实验指导书文档格式.docx（22页珍藏版）》请在冰点文库上搜索。
若计数变量n的值小于给定的参数i，则指针变量p后移（即指向下一个结点），且计数变量增一（计数变量n的值始终是指针变量p所指结点的序号）。
故只需在每次执行“p后移”操作之前，增加一个判断条件，判断计数变量n是否小于给定的参数i。
此条件若成立，说明尚未数到给定位置，应该继续往下“数”（即指针变量p后移，计数变量n增一），直到条件不成立（n的值与给定序号相同，即数到位了，或给定的序号的值大于表中结点的总个数），则返回。
查找指定位置结点的算法如下：
structpointer*find_list（head,i）
structpointer*head;
inti;
{structpointer*p;
p=head;
n=1;
while（p->
next!
=NULL&
&
n<
i）
{n++;
p=p->
next;
if（i==n）
return（p）;
elsereturn（NULL）;
3．在查找到的指定位置上插入新元素．
在第i位置之前插入一个值为x的结点，其基本步骤如下：
第一步：
在单链表上找到插入的位置，使得指针p指向第i-1个结点位置，这可用find_list算法实现，如图2-6；
然后生成一个新结点，指针s指向该结点，并将数据x赋给其数据域。
第二步：
将新结点链入到指针p所指结点之后，其操作步骤为：
（1）将结点*s的指针域指向结点*p的后继结点，语句为：
s->
next=p->
（2）将结点*p的指针域的值改为指向新结点，语句为：
next=s;
至此，插入操作完成。
算法如下：
voidinsert（head,x,i）
/*head为线性链表的头指针，x为待插入的数据，i为插入位置*/
structpointer*head;
datatypex;
/*在头指针为head的线性链表的第i个位置上插入一个值为x的新结点*/
{structpointer*s,*p;
p=find_list（head,i-1）;
/*先找到第i-1个结点的位置，并让p指向该结点*/
if（p!
=NULL）
{s=（structpointer*）malloc（LEN）;
/*生成一个新结点*/
s->
data=x;
/*将值x赋给新结点的数据域*/
/*将新结点连接到指针p所指结点之后（即第i个位置上）*/
elseprintf（“不存在第%d位置\n”,i）;
4．在查找到的指定位置上删除结点
删除链表中第i个结点的基本步骤如下：
找到第i-1个结点，并使得指针p指向该结点。
这一
步可通过调用find_list算法实现。
从链表上删除第i个结点，其操作如下
（1）将指针q指向指针p所指结点的下一个结点，即第i个结点，使用语句：
q=p->
（2）将*q的指针域的值（*q的后继结点的地址）赋值给*p的指针域，语句为：
next=q->
第三步：
将指针q所指结点（*q）回收，语句为：
free（q）；
删除链表中第i个结点的算法如下：
voiddelete_list（head,i）
/*head是线性链表的头指针，i为待删除的结点的序号*/
/*本算法是将头指针为head的线性链表中的第i个结点删除*/
{structpointer*q,*p;
/*先找到待删除结点的前趋结点，让指针p指向该结点*/
if（p!
next!
=NULL）
{q=p->
neat;
/*删除该结点*/
free（q）;
/*释放已被删除的结点*/
elseprintf（“不存在第%d个结点\n”,i）;
四、实验报告要求
1、认真阅读和掌握本实验内容所给的程序。
2、将本实验上机运行。
3、结合运行结果，对程序进行分析。
实验二二叉排序树
一、实验目的
掌握二叉树的链式存储结构，二叉树的遍历方法和二叉排序树的方法。
1.实现二叉树的链式存储。
2.二叉树的遍历算法
3.二叉排序树
1、二叉链表的生成
二叉链表的生成，是指根据给定的二叉树在计算机中建立该树的链式存储结构
（1）输入根结点的值；
（2）若左子树不空，则输入左子树，否则输入一个结束符（可用空格表示）；
（3）若右子树不空，则输入右子树，否则输入一个结束符；
如图：
是要创建的二叉树，按上述原则输入的字符顺序应为：
ABCDEGF
其中“”表示空格。
生成二叉树链表的算法：
首先定义链表的结点类型为
structnode{chardata；
structnode*lchild；
structnode*rchild；
}；
structnodecreatebinarytree（）
{structnode*t;
charch;
scanf（“%c”,&
ch）；
/*依次输入二叉树中结点的值（一个字符），空格字符表示空树*/
scanf（"
%c"
&
ch）;
if（ch==’'
）t=NULL;
else
{t=（structnode*）malloc（sizeof（structnode））;
if（t==NULL）
{printf（"
outofmemory\n"
）;
exit（0）;
}
t->
data=ch;
lchild=creattree（）;
rchild=creattree（）;
returnt;
先序遍历DLR二叉树的操作可定义为：
若二叉树为空，则返回。
否则
（１）访问根结点；
（２）先序遍历左子树；
（３）先序遍历右子树；
（４）返回。
其递归算法如下：
voidpreorder（t）
structnode*t；
{if（t！
＝NULL）
{visite（t－>
data）；
preorder（t－>
lchild）；
preorder（t－>
rchild）;
中序遍历二叉树LDR的操作可定义为：
（1）中序遍历左子树；
（2）访问根结点；
（3）中序遍历右子树；
（4）返回。
structnode
{anytypedata；
voidinorder（t）
/*t为指向二叉树根结构的指针*/
{if（t!
=NULL）
{inorder（t->
lchild）;
visite（t->
data）;
inorder（t->
rchild）;
后根遍历的算法也可归纳为四个步骤，如下描述：
否则：
（1）后序次遍历左子树；
（2）后序遍历右子树；
（3）访问根结点；
根据以上的递归定义，递归算法如下：
voidpostorder（t）
structnode*t；
{ift！
＝NULL
{postorder（t－>
postorder（t－>
rchild）；
visite（tT－>
data）；
实验三排序实验
一、实验目的
使学生更进一步比较各种排序方法。
掌握选择排序、冒泡排序和快速排序方法。
1、选择排序算法分析
选择排序是一种常用的排序方法。
选择排序是不断的从待排序的记录序列中选取关键字最小的记录，依次放到已排好序的序列的后面。
这里用的是简单选择排序
第一趟从所有的n个记录中，通过顺序比较各关键字的值，选取关键字值最小的记录与第一个记录交换；
第二趟从剩余的n-1个记录中选取关键字值最小的记录与第二个记录交换；
即第i趟排序就是从剩余的n-i+1个记录中（无序区）选取关键字值最小的记录，与第i个记录交换；
经过n-1趟排序后，整个序列就成为有序序列。
对3385641573564220关键字序列，用简单选择排序法排序的过程如下。
如下图所示。
假设[…]为有序区，{…}为无序区。
初始关键字：
{3385641573564220}
第一趟排序后：
[15]{85643373564220}
第二趟排序后：
[1520]{643373564285}
第三趟排序后：
[152033]{6473564285}
第四趟排序后：
[15203342]{73566485}
第五趟排序后：
[1520334256]{736485}
第六趟排序后：
[152033425664]{7385}
第七趟排序后：
[15203342566473]{85}
最后结果：
[1520334256647385]
算法描述：
voidselectionsort（intR[],intn）
{inti,j,k;
for（i=1;
i<
=n-1;
i++）
{k=i;
for（j=i+1;
j<
=n;
j++）
if（R[j]<
R[k]）k=j;
if（i!
=k）
{R[0]=R[k];
R[k]=R[i];
R[i]=R[0];
2.冒泡排序算法分析
在待排序的记录序列中，从第一个待排序的记录R1开始，依次比较两个相邻记录R1和R2，若R1>
R2，则交换记录R1和R2，否则不交换。
然后再对R2和R3进行同样的比较，依次类推，直到序列中的最后两个记录处理完为止。
这样的一个过程就叫做一趟冒泡排序。
这样，在一趟比较完毕后，关键字值最大的记录就被交换到最后，然后再对前面的n-1个记录执行上述过程，如此重复n-1次。
voidbubblesort（intR[],intn）
{inti,j;
for（i=1;
for（j=1;
=n-i;
if（R[j]>
R[j+1]）
{R[0]=R[j];
R[j]=R[j+1];
R[j+1]=R[0];
}
※算法存在的问题：
上述算法中，对n个记录进行排序需要进行n-1趟排序。
实际上，除非是逆序的情况，一般情况下不需要进行n-1趟冒泡就能排好序。
如果当前数据已排好序，则应该结束排序过程。
那么计算机如何才能知道当前数据已排好序了呢？
一个显而易见的办法就是在每一趟“冒泡”中，记录当前数据中是否存在逆序。
如不存在逆序则说明数据已排好序，否则，不能确定是否已排好序，还需进行下一趟“冒泡”。
假设用变量flag来记录一趟排序过程中是否有记录交换，在每一趟排序之前，flag的值设为0，每次交换记录之后，flag的值改为1。
每趟排序后，判别flag的值，若为1，继续下一趟排序；
若为0，表明这一趟没有进行过任何交换记录的操作，说明已排好序，排序结束。
3.快速排序算法分析
一趟快速排序采用从两头向中间扫描的办法，同时交换与基准记录逆序的记录。
在待排序的记录序列中任取一个记录Ri（一般可取第一个记录R1），以该记录作为比较基准，将待排序序列划分成左右两部分，所有比该记录关键字值小的记录放到左边，所有比它大的放到右边，并把该记录排在这两部分的中间，这一个过程称为一趟快速排序。
之后对所划分的两部分分别重复上述过程，直到每一部分的记录个数为1为止。
一趟快速排序描述：
intqkonepass（intR[],intLow,intHigh）
{inti,j;
i=Low;
j=High;
R[0]=R[i];
while（i<
j）
{while（i<
j&
R[j]>
=R[0]）
j=j-1;
R[i]=R[j];
R[i]<
i=i+1;
R[j]=R[i];
R[i]=R[0];
return（i）;
四、实验内容
1、选择排序
2、设关键字序列为｛3385641573564220｝，用选择排序方法和冒泡进行排序。
五、实验报告要求
实验四查找
使学生掌握线性查找和二分查找。
1.线性查找：
已知含有10个整数的线性表如下：
（9，13，15，7，45，32，56，89，60，36），从键盘上输入一个整数，用线性查找的方法在线性表中查找该整数。
若存在，输出该元素的下标值，否则，给出相应的信息。
2.二分查找：
对有一个11个记录的有序表的关键字值进行二分查找：
812263745566472818995
1.线性查找算法分析：
从查找表的一端开始，逐个将记录的关键字值和给定值进行比较，如果某个记录的关键字值和给定值相等，则称查找成功；
否则，说明查找表中不存在关键字值为给定值的记录，则称查找失败。
算法描述：
intseqsearch（intR[],intk）
/*在查找表R中查找关键字为k的记录，查找成功，返回下标值，否则返回0*/
{inti;
R[0]=k;
i=N;
while（R[i]!
i--;
return（i）;
/*若i为0，表示查找失败，否则R[i]为要找的记录*/
实验程序：
#defineN10
main（）
{inti,x,p;
inta[N+1]={0,9,13,15,7,45,32,56,89,60,36};
scanf（"
%d"
x）;
p=seqsearch（a,k）;
/*调用顺序查找算法*/
if（p==0）
printf（"
Thisnumberdoesnotexistinthisarray.\n"
else
a[%d]=%d\n"
i,x）;
2.二分查找算法分析
先取查找表的中间位置的关键字值与给定关键字值作比较，若它们的值相等，则查找成功；
如果给定值比该记录的关键字值大，说明要查找的记录一定在查找表的后半部分，则在查找表的后半部分继续使用折半查找；
若给定值比该记录的关键字值小，说明要查找的记录一定在查找表的前半部分，则在查找表的前半部分继续使用折半查找。
直到查找成功，或者直到确定查找表中没有待查找的记录为止，即查找失败。
对有序列：
812263745566472818995
现在要查找关键字值为26和75的记录。
假设指针low和high分别指示待查元素所在区间的下界和上界，指针mid指示区间的中间位置。
给定值26的查找过程：
lowmidhigh
取mid位置的关键字值56与26作比较，显然26<
56，故要查找的26应该在前半部分，所以下次的查找区间应变为[1，5]，即low值不变仍为1，high的值变为mid-1=5。
再次求得mid的值为3。
lowmidhigh
取mid指示位置的关键字值26与给定值26作比较，显然是相等的，说明查找成功。
所查元素在查找表中的位置即为mid所指示的值。
查找关键字值为75的记录的过程：
lowmidhigh
取mid位置的关键字值56与75作比较，显然75>
56，说明要查找的记录在后半部分，待查区间变为[7，11]。
lowmidhigh
再取mid位置的关键字值81与75作比较，显然75<
81，说明待查记录在前半部分。
待查区间再次变为[7，8]。
low,midhigh
此时75>
64，low=mid+1=8，待查区间变为[8，8]。
low,high,mid
显然75>
72，待查区间变为low=mid+1=9，high=8，此时high<
low，说明查找表中没有关键字值为75的记录，查找失败。
intbinsearch（intR[],intk）
{intlow,high,mid,find=0;
low=1;
high=n;
/*置区间初值*/
while（（low<
=high）&
（!
find））
{mid=（low+high）/2;
/*求中点值*/
if（k==R[mid]）
find=1;
/*已查到*/
else
if（k>
R[mid]）
low=mid+1;
/*在后半区查找*/
high=mid-1;
/*在前半区查找*/
if（find）
return（mid）;
/*查找成功，返回找到的元素位置*/
return（-1）;
/*查找失败，返回-1*/
实验五数据库的建立
使学生掌握在VisualFoxPro下建立和修改数据库表的方法。
1.创建职工工资管理数据库
2.录入职工基本情况及工资数据记录
3．编辑修改职工基本情况及工资数据记录
1．启动项目管理器，选择新建项目，创建《职工工资管理》
2．在项目文件：
职工工资管理.PJX下，创建数据库ZGJBQK.DBC
3．在数据库ZGJBQK.DBC文件下创建数据表ZGJBQKB.DBF
4．在一表设计器下创建数据表ZGJBQKB.DBF的内容：
表结构：
字段名（标题）
字段类型
字段宽度
小数位
Gh工号
C
9
Xm姓名
10
Xb性别
2
Csrq出生日期
D
8
Hyzk婚姻状况
L
1
Gz工资
N
7
Zc职称
12
Jl简历
M
4
5．输入记录：
工号
姓名
性别
出生日期
婚姻状况
工资
职称
简历
2001052121
黄波
男
1976-01-22
T
2130．50
高级工程师
2001052125
张晓强
1975-05-14
F
1890．20
工程师
2001053523
汪雅智
女
1973-02-24
2215．00
2001095426
卢津
1976-12-02
2025．50
2001095566
张春燕
1978-06-25
1850．00
2003015478
张宸铭
1976-08-11
1980．10
助理工程师
2003046825
黄显辉
1972-08-25
2560．00
2005062548
来国群
1982-09-13
1840．50
助理工程师
2005065462
杨历
1983-01-03
1820．30
技术员
2005032546
曾令剑
1981-02-22
2050．00
助理技术员
2004542401
李小林
1979-05-24
1970．20
6．完成以下操作
a.给至少两个员工添加简历
升级会员 