《数据结构》.doc

《数据结构》基本操作指导绍兴文理学院计算机系二○一一年八月目录指导一、单链表的操作-----------------------------------------------------2指导二、栈及其应用-------------------------------------------------------10指导三、串的基本操作----------------------------------------------------16指导四、二叉树的基本操作----------------------------------------------21指导五、图的存储和遍历-------------------------------------------------31指导六、查找---------------------------------------------------------------41指导七、排序---------------------------------------------------------------49指导一、单链表的操作一、指导目的1、掌握线性表的链式存储结构。2、掌握利用链式存储结构实现线性表的基本操作。3、掌握链式存储结构中的算法实现。二、指导内容1、建立带头结点的单链表,并输出该单链表。2、实现带头结点的单链表上的插入、删除、查找、修改操作。三、操作指导1、定义单链表的结点结构单链表的结点结构可为一个结构体类型(slnodetype),其成员是数据域和指针域,数据域可以是整数。2、模块划分和程序控制流程根据实验要完成的各功能,设置初始化、建立单链表、输出单链表、插入、删除、查找、修改和主函数8个模块,对于要完成的各功能,采用适当的人机界面,用循环和分支结构构成菜单进行选择。3、初始化模块intinitiate(slnodetype**h)该模块中产生一个只有头结点的空单链表,用指针h作为函数的参数返回,因为h是指针变参,所以在函数的参数位置要以二级指针出现。在函数里,申请一个头结点空间。4、建立单链表模块intcreatelink(slnodetype*h)该模块中建立有若干个结点的单链表,用循环控制输入若干个整数,申请相应的结点空间,以输入的整数作为结点中的数据,依次链接到初始只有头结点的单链表h中,可以把输入0作为建立链表的结束。5、输出单链表模块voiddisplay(slnodetype*h)对于传入的单链表h,依次输出单链表中的结点(数据)。6、插入结点模块intinserti(slnodetype*h)设在第i个结点前插入数据为data的结点。在该函数模块中输入i和数据data,对于传入的单链表h,先查找是否存在插入的位置(单链表h中至少要有i-1个结点),若不存在插入位置,则不做任何操作;若存在插入位置,则申请一个结点,其数据为data,挂在第i-1个结点的后面。7、删除结点模块intdelete(slnodetype*h)在该函数模块中,首先可以调用输出模块输出传入的单链表h,以便选择要删除的结点,然后输入要删除结点的数据data,再查找是否存在要删除的结点,若不存在要删除的结点,则显示相应的信息;若存在要删除的结点,则删除该结点(包括删除该结点空间)。8、查找模块intsearch(slnodetype*h)在该函数模块中,首先可以调用输出模块输出传入的单链表h,以便选择要查找的结点,然后输入要查找结点的数据data,再查找该结点是否存在,若不存在要查找的结点,则显示相应的信息;若存在要查找的结点,也显示相应的信息。9、修改模块intmodify(slnodetype*h)在该函数模块中,首先可以调用输出模块输出传入的单链表h,以便选择要修改的结点,然后输入要修改结点的数据data,再查找该结点是否存在,若不存在要查找的结点,则显示相应的信息;若存在要查找的结点,则显示原结点的数据,再提示输入新的数据,输入新的数据后,可以再调用输出模块输出修改结点数据后的单链表h,以便查看修改后的单链表h中的数据。10、主函数main()主函数中定义指向单链表的指针等变量,首先调用初始化操作initiate(),考虑人机界面,进入如下操作菜单的循环控制结构:==========menu==========1---create2---display3---insert4---delete5---search6---modify0---exitchoosethenumberbetween0to6:对于要进行的操作,进入接受选择的循环控制(对于不合法的选择,重新提示选择),对与合法的选择,退出接受选择的循环控制,进入多分支结构,以执行相应的功能,执行完毕后回到操