软件技术基础实验指导书Word格式.docx

软件技术基础实验指导书Word格式.docx

《软件技术基础实验指导书Word格式.docx》由会员分享，可在线阅读，更多相关《软件技术基础实验指导书Word格式.docx（14页珍藏版）》请在冰点文库上搜索。

stdio.h>

stdlib.h>

/*单链表的定义*/

typedefintDataType;

/*DataType可以是任何相应的数据类型如int,float或char*/

typedefstructnode/*结点类型定义*/

{DataTypedata;

/*结点的数据域*/

structnode*next;

/*结点的指针域*/

}ListNode;

typedefListNode*LinkList;

voidmain（）

{inti;

DataTypekey,x;

LinkListhead;

ListNode*p;

LinkListCreateList（void）;

voidPrintList（LinkListhead）;

LinkListLocateNode（LinkListhead,DataTypekey）;

LinkListGetNode（LinkListhead,inti）;

voidInsertList（LinkListhead,DataTypex,inti）;

voidDeleteList（LinkListhead,inti）;

head=CreateList（）;

/*建立单链表*/

PrintList（head）;

/*打印单链表*/

printf（"

输入要查找的值：

"

）;

scanf（"

%d"

&

key）;

p=LocateNode（head,key）;

/*单链表查找*/

请输入欲插入元素的位置：

i）;

请输入欲插入的元素：

x）;

InsertList（head,x,i）;

/*单链表插入*/

请输入欲删除结点的位置：

DeleteList（head,i）;

/*单链表删除*/

}

/*单链表的建立,从后向前生成*/

LinkListCreateList（void）

{

//在此插入必要语句

}

/*单链表的打印*/

voidPrintList（LinkListhead）

/*单链表的查找,输入一个整数，显示该结点的位置*/

LinkListLocateNode（LinkListhead,DataTypekey）

{/*在不带头结点的单链表head中查找其值为key的结点*/

//在此插入必要语句

/*单链表的查找2，在不带头结点的单链表head中查找第i个结点*/

LinkListGetNode（LinkListhead,inti）

/*单链表的插入*/

voidInsertList（LinkListhead,DataTypex,inti）

{/*将值为x的新结点插入到不带头结点的单链表head的第i个结点的位置上*/

/*单链表的删除，删除不带头结点的单链表中的第i个结点*/

voidDeleteList（LinkListhead,inti）

六、思考题

如果生成带头结点的单链表，程序应如何修改？

七、实验报告要求

具体内容包含以下几项：

实验题目、实验目的、实验环境、实验内容与完成情况（要求附上自主设计的源程序）、实验中出现的问题、对问题的解决方案、完成思考题、实验总结等。

实验二二叉树的建立和遍历

1．掌握二叉树的建立算法

2．掌握二叉树的前序、中序和后序遍历算法。

复习二叉树的生成及遍历算法，编写完整的程序。

要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。

分别利用前序遍历、中序遍历、后序遍历所建二叉树。

二叉树的建立算法思路：

主要利用二叉树的性质：

在编号的完全二叉树中，编号为i的结点如果存在左孩子，则其编号为2i；

若其存在右孩子，则其编号为2i+1；

若存在父结点，则其编号为i/2取整。

对任意二叉树，先按满二叉树对其进行编号，算法中使用一个辅助向量s来存放指向树结点的指针。

如s[i]中存放编号为i的结点的指针，即为该结点的地址。

当结点编号i=1时，所产生的结点为根结点，同时将指向该结点的指针存入s[1]。

当结点编号i>

1时，产生一个新的结点后，也要将指向该结点的指针存入s[i]，由上述性质可知：

j=i/2为它的双亲结点编号。

如果i为偶数，则它是双亲结点的左孩子，即让s[j]->

lch=s[i]；

若i为奇数，则它是双亲结点的右孩子，即让s[j]->

rch=s[i]。

这样就将新输入的结点逐一与其双亲结点相连，生成二叉树。

二叉树的遍历算法可以使用递归算法实现，也可采用非递归算法实现，可参考教材上算法实现。

请思考其它的二叉树建立算法。

实验三二叉排序树的建立和查找

1．掌握二叉排序树的建立算法

2．掌握二叉排序树查找算法。

复习二叉排序树的生成及查找算法，编写完整的程序。

实现二叉排序树上的查找算法。

用二叉链表做存储结构，输入键值序列，建立一棵二叉排序树并在二叉排序树上实现查找算法。

typedefintInfoType;

typedefintKeyType;

/*假定关键字类型为整数*/

typedefstructnode/*结点类型*/

{

KeyTypekey;

/*关键字项*/

InfoTypeotherinfo;

/*其它数据域，InfoType视应用情况而定下面不处理它*/

structnode*lchild,*rchild;

/*左右孩子指针*/

}BSTNode;

typedefBSTNode*BSTree;

/*BSTree是二叉排序树的类型*/

BSTNode*SearchBST（BSTreeT,KeyTypekey）;

voidInsertBST（BSTree*Tptr,KeyTypekey）;

BSTreeCreateBST（void）;

voidListBinTree（BSTreeT）;

/*用广义表表示二叉树*/

BSTreeT;

BSTNode*p;

intkey;

请输入关键字（输入0为结束标志）：

\n"

T=CreateBST（）;

ListBinTree（T）;

请输入欲查找关键字：

p=SearchBST（T,key）;

if（p==NULL）

printf（"

没有找到%d！

key）;

else

找到%d！

ListBinTree（p）;

BSTNode*SearchBST（BSTreeT,KeyTypekey）

{/*在二叉排序树T上查找关键字为key的结点，成功时返回该结点位置，否则返回NULL*/

if（T==NULL||key==T->

key）/*递归的终结条件*/

returnT;

/*若T为空，查找失败；

否则成功，返回找到的结点位置*/

if（key<

T->

key）

returnSearchBST（T->

lchild,key）;

rchild,key）;

/*继续在右子树中查找*/

voidInsertBST（BSTree*Tptr,KeyTypekey）

{/*若二叉排序树*Tptr中没有关键字为key，则插入，否则直接返回*/

BSTNode*f,*p=*Tptr;

/*p的初值指向根结点*/

while（p）{/*查找插入位置*/

if（p->

key==key）return;

/*树中已有key，无须插入*/

f=p;

/*f保存当前查找的结点*/

p=（key<

p->

key）?

p->

lchild:

rchild;

/*若key<

key，则在左子树中查找，否则在右子树中查找*/

p=（BSTNode*）malloc（sizeof（BSTNode））;

key=key;

lchild=p->

rchild=NULL;

/*生成新结点*/

if（*Tptr==NULL）/*原树为空*/

*Tptr=p;

/*新插入的结点为新的根*/

else/*原树非空时将新结点*p作为*f的左孩子或右孩子插入*/

if（key<

f->

f->

lchild=p;

elsef->

rchild=p;

BSTreeCreateBST（void）

{/*输入一个结点序列，建立一棵二叉排序树，将根结点指针返回*/

BSTreeT=NULL;

/*初始时T为空树*/

/*读入一个关键字*/

while（key）{/*假设key=0是输入结束标志*/

InsertBST（&

T,key）;

/*将key插入二叉排序树T*/

scanf（"

/*读入下一关键字*/

returnT;

/*返回建立的二叉排序树的根指针*/

请思考采用其他存储结构实现的二叉排序树建立算法。

实验四windows操作系统及应用

1．用Windows2000自带的工具观察内存空间的使用情况；

2．了解Windows2000注册表的作用，熟悉注册表编辑器；

　　3．熟悉Windows2000注册表中5个主要根键的内容与作用；

　　4．了解备份注册表的重要性，掌握备份注册表的基本方法；

5．学会通过修改注册表，屏蔽桌面“回收站”图标的方法。

6．通过VC++中的跟踪调试技术，了解内存的分配

windows操作系统操作系统和visualc++6.0环境

搜集注册表相关内容，了解内存分配策略

1．观察内存使用情况用Windows2000自带的工具观察内存空间的使用情况，观察并写出屏幕显示的内容。

2．使用Windows2000的注册表屏蔽桌面上的“回收站”。

具体内容：

（1）备份注册表（或者打开后导出注册表）。

（2）运行regedit命令打开注册表。

（3）选择注册表中“HKEY_LOCAL_MACHINE”子窗口（即找到此根键），定位到“HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Explorer\Desktop\NameSpace”分支，在该分支下有多个子键对应桌面上的某些系统图标。

（4）删除键值为RecycleBin的子键，如子键645FF040-5081-1-1B-9F08-00AA002F954E。

（5）重新启动计算机。

（6）根据备份的注册表内容，恢复注册表中被删除的子键，重新启动计算机。

（7）观察两次重启后的情况，总结备份、修改和恢复注册表的一般过程。

3．通过VC++中的跟踪调试技术，了解内存的分配在VC++环境下，编写一个简单计算程序，要求声明的变量中有单个变量、数组、指针变量，等。

在变量赋值后设置断点，跟踪程序，在调度窗口中观察变量的值和存储地址。

观察数组元素的顺序关系与存储地址之间的关系；

观察链式存储的元素的地址关系。

五、思考题

练习注册表的其他用法。

六、实验报告要求

实验五数据库设计与应用

（一）

1．熟练掌握用SQL语句实现基本表的创建。

2．熟练掌握用SQL语句实现数据插入、数据更新和数据查询。

3．熟练掌握用SQL语句实现数据的简单查询和连接查询。

SQLServer2000

SQLServer2000的查询分析器和企业管理器的使用，SQL数据定义和数据操纵语言。

1.用SQL语句建立如下SPJ数据库，包括S，P，J，和SPJ四个基本表（教材第二章习题5中的四个表）。

要求实现关系的三类完整性。

S（SNO,SNAME,STATUS,CITY）;

P（PNO,PNAME,COLOR,WEIGHT）;

J（JNO,JNAME,CITY）;

SPJ（SNO,PNO,JNO,QTY）

供应商表S由供应商代码（SNO）、供应商姓名（SNAME）、供应商状态（STATUS）、供应商所在城市（CITY）组成。

零件表P由零件代码（PNO）、零件名（PNAME）、颜色（COLOR）、重量（WEIGHT）组成。

工程项目表J由工程项目代码（JNO）、工程项目名（JNAME）、工程项目所在城市（CITY）组成。

供应情况表SPJ由供应商代码（SNO）、零件代码（PNO）、工程项目代码（JNO）、供应数量（QTY）组成，表示某供应商供应某种零件给某工程项目的数量为QTY。

2.利用Insert语句将习题中给出的示例记录插入各表。

3.利用Update更新表中的记录：

（1）将p表中的所有红色零件的重量增加5。

（2）将spj表中所有天津供应商的QTY属性值减少10。

用子查询。

4.完成下面的简单查询：

（1）查询所有“天津”的供应商明细；

（2）查询所有“红色”的14公斤以上的零件。

（3）查询工程名称中含有“厂”字的工程明细

5.自然连接：

查询所有的供应明细，要求显示供应商、零件和工程的名称，并按照供应、工程、零件排序。

如何用SQL语句实现关系的三类完整性？

实验六数据库设计与应用

（二）

1．熟练掌握用SQL语句实现视图操作。

2．理解触发器的含义，并初步掌握用SQL语句实现触发器的编写。

3．理解存储过程的含义，并初步掌握用SQL语句实现存储过程的编写。

SQLServer2000的查询分析器和企业管理器的使用，存储过程和触发器的含义。

1.定义如下视图：

（1）查询北京的供应商的编号、名称和城市。

（2）查询S1供应商的所有供应明细。

（3）查询各工程名称使用的各种颜色零件的个数。

查询上面定义的视图。

2.触发器编写。

为S表的删除操作定义一个触发器，在删除一个供应商记录时，将这个供应商的所有供应情况从spj表中删除。

3.存储过程编写编写一个存储过程，定义四个参数接收供应商的四个属性的值，然后插入S表中。

如何通过系统的设置实现类似的功能，而不需触发器？