搜索
《数据结构（C语言版）》实验指导书（非计算机专业适用）广州大学2013.1目录实验一线性表的顺序存储及其操作...........................1实验二线性表的链式存储及其操作...........................3实验三栈和队列的应用..............................................7实验四串及其操作......................................................9实验五树及其操作....................................................11实验六图及其操作....................................................16实验七查找和排序....................................................22-1-实验一线性表的顺序存储及其操作预习题：1、线性表是如何定义的？有什么特点？2、线性表有哪些实现方法？3、线性表的顺序存储和链式存储各有什么优缺点？4、在线性表的顺序存储中，插入和删除都需要进行数据元素的迁移，问：两者迁移的方法有何异同？（从迁移的内容、迁移的顺序来分析）5、顺序存储的线性表进行内容的翻转时，和数据元素的奇偶性有关吗？实验项目：线性表的顺序实现：查找、插入、删除、翻转实验类型:基础性指导思想：用数组存储线性表，实现线性表的基本操作。实验目的及要求：1、复习C语言的数组的定义；2、理解线性表的属性；3、实践线性表的顺序实现方法以及相关的操作；4、要求：提交实验报告，附源程序、打印运行结果。涉及的知识点：线性表的逻辑属性、运算单数组的操作：定义、输入、输出、数组内容的翻转元素/数组的操作：元素的检索、插入、删除实验内容：实现数组的输入、输出、查找、插入、删除、翻转等功能，每个功能用一个函数实现，在主程序中按以下要求把这些函数组织起来。实验步骤：编写具有以下功能的程序：1、从键盘读入10个整数（或字符）；2、显示当前数组内容；3、输入一个数组元素，显示该元素在线性表中的位置；重复本过程，元素在表头、表中、表尾的各一次；4、输入一个不在数组中的数据，程序要检测出该元素不在线性表内；-2-5、输入一个新的数组元素和要插入的位置，把该元素插入后显示数组内容；重复本过程，插入的位置在表头、表中、表尾的各一次；6、输入一个合理的元素位置，删除该位置上的元素，显示数组内容；重复本过程，插入的位置在表头、表中、表尾的各一次；7、把数组的内容翻转后输出；8、删除一个数组元素，使得数组元素个数的奇偶性改变，再翻转一次、输出，以确认翻转过程适合于奇数和偶数长度的数组。-3-实验二线性表的链式存储及其操作预习题：1、线性表的链式存储在哪些方面比顺序存储要好？2、在线性表的链式存储中，插入和删除都需要进行数据元素的迁移吗？3、为什么链表的插入和删除操作都需要记住被操作的结点的前一个结点？4、链式存储的线性表进行内容的翻转时，和数据元素的奇偶性有关吗？实验项目：线性表的链表实现：遍历、插入、删除、翻转实验类型:基础性指导思想：用链表存储线性表，实现线性表的基本操作。实验目的及要求：1、复习C语言的指针的定义、链表的使用；2、理解线性表的属性；3、实践线性表的链式实现方法以及相关的操作。4、要求：提交实验报告，附源程序中填空的内容（10处）、打印运行结果涉及的知识点：线性表的逻辑属性、运算带表头的单链表的操作：定义、输入、输出、链表内容的翻转元素/链表的操作：元素的插入、删除实验内容：实现链表的输入、输出、插入、删除、翻转等功能，教师提供主要源代码，其中有10处标出需要学生填空，使得整个程序能正确运行。问题描述：用带表头的链表存放输入的数据，每读入一个数，按升序顺序插入到链表中，链表中允许两个结点有相同值。链表的头结点存放链表后面的结点个数，初始化时就生成头结点（初值为0）。链表翻转是把数据逆序（变成降序），注意，头结点不动。翻转后要再翻转一次，恢复升序后才能插入新元素，否则会出错。实验步骤：读懂后面附带的源代码，在标注“填空”的位置填写适当的表达式或语句，使得程序完成指定功能。-4-测试要求：1、连续插入5个实数；要求：插入的元素要分别位于表头、表中、表尾，以确保该插入函数适合于各种情况；2、翻转链表，确认成功后再翻转一次，恢复元素的升序序列；3、删除3个数组元素，删除的元素要分别要位于表头、表中、表尾，以确保该删除函数适合于各种情况；4、删除一个不存在的元素，确认链表的内容没被改变。以下是待填空的源代码，请同学们粘贴到系统中填空、运行、测试：/*链表操作：插入、删除、输出、翻转用带表头的链表存放输入的数据，每读入一个数，按升序顺序插入到链表中，链表中允许两个结点有相同值。链表的头结点存放链表后面的结点个数，初始化时就生成头结点（初值为0）。链表翻转是把数据逆序（变成降序），注意，头结点不动。翻转后要再翻转一次，恢复升序后才能插入新元素，否则会出错。*/#includestdio.h#includemalloc.h#definenull0structnode{floatdata;structnode*next;};voidinsert(floataa,structnode*vq){structnode*newnode,*p;newnode=(structnode*)malloc(sizeof(structnode));newnode-data=aa;p=vq;while((p-next!=null)&&(p-next-dataaa))/*填空1*/;newnode-next=p-next;/*填空2*/;vq-data=vq-data+1;}voiddele(floataa,structnode*vq){structnode*p,*q;-5-p=vq;while((p-next!=null)&&(p-next-dataaa))/*填空3*/;if((p-next==null)||(p-next-data!=aa))printf(\n%5.1fisnotinthelink!,aa);elseif(p-next-data==aa){q=p-next;p-next=/*填空4*/;free(/*填空5*/);vq-data=vq-data-1;}}voidprint(structnode*vq){structnode*p;printf(\nthelengthoflinkis%4.0f,vq-data);p=vq-next;printf(\nthelinkis:);while(/*填空6*/){printf(%5.1f,p-data);/*填空7*/;}}voidreverse(structnode**vq){structnode*q,*p;p=(*vq)-next;(*vq)-next=/*填空8*/;while(p!=null){q=p;p=/*填空9*/;q-next=/*填空10*/;(*vq)-next=q;}}main(){intmark=1,op;-6-floataa;structnode*vq;vq=(structnode*)malloc(sizeof(structnode));vq-data=0;vq-next=null;while(mark==1){printf(\nWhichkindofoperationwillyouselect?);printf(\ninsert---1,delete---2,print---3,reverse---4,exit---0:);scanf(%d,&op);switch(op){case0:mark=0;break;case1:printf(\nPleaseinputthenewelement:);scanf(%f,&aa);insert(aa,vq);print(vq);break;case2:if(vq-data==0)printf(\nthelinkisnull!,aa);else{printf(\nPleaseinputthedeletedelement:);scanf(%f,&aa);dele(aa,vq);print(vq);}break;case3:print(vq);break;case4:reverse(&vq);print(vq);break;default:printf(inputerror!\n);}}}/*程序结束*/-7-实验三栈和队列的应用预习题：1、栈和队列是如何定义的？各有什么特点？2、栈和队列有哪些实现方法？3、栈和队列的顺序存储和链式存储各有什么优缺点？实验项目：栈和队列及其操作的实现；栈和队列的应用实验类型：设计性指导思想：栈和队列是两种常用的和重要的数据结构。利用顺序存储或链式存储实现栈和队列及其基本操作，在此基础上，应用栈和队列解决实际问题。培养学生解决问题的能力。实验目的及要求：1、熟悉栈和队列的定义和特点；2、实践栈和队列的顺序和链式实现方法以及相关的操作；3、根据实际问题的要求，合理使用栈和队列，设计相关程序；4、要求：提交实验报告，附源程序、打印运行结果。涉及的知识点：栈和队列的存储方法栈的常用操作（构造、销毁、入栈、出栈、读栈、判断栈空或满）队列的常用操作（构造、销毁、入队列、出队列、判断队列空或满）实验内容：根据以下两个问题的要求，合理使用栈和队列，设计相关程序：项目一：字符串回文的判断“回文”英语叫做Palindrome，是指一个单字或名词或句子，顺读倒读都可成立的，英语单字中顺读倒读仍是同一字的有：civic，deed，did，gag，level，madam，noon，peep，refer，rotator。亚当同学刚刚碰到夏娃小姐时说的是什么？“Madam,I'mAdam.”Napoleon被关的时候因为过度无聊也写过这玩意儿:AbleWasIEreISawElba还有一些palindrome：-8-Nolemons，nomelon.DogssassGod~Sillyramatewetamaryllis!Now,evil,I'vewon!WasitacatIsaw?这个的高级版本是WasitacaroracatIsaw？通过程序自动判断用户输入的字符串是否回文。提示：首先构造一个栈和队列，将用户输入的字符串同时入栈和入队列。然后当栈或队列不为空时，将出栈和出队列的元素进行比较，若全部一致，则为回文。显示效果如下图所示：项目二：判别表达式中的括号（“{}、[]、()”）是否匹配表达式运算是计算机重要应用之一，而判断表达式是表达式运算的基础。通过程序自动判断用户输入的表达式中的括号是否匹配。显示效果如下图所示：-9-实验四串及其操作预习题：1、C语言是如何存储字符串的？与普通的字符型数组有何区别？2、C语言的标准库函数提供了哪些串的函数？你自己能编写实现其相同功能的函数吗？3、多个字符串合并时，如何处理结束符？4、串的模式匹配算法是怎样的？5、若主串中有多个地方匹配子串，要返回首次匹配的位置、返回最后匹配的位置、返回所有匹配的位置，各如何处理？实验项目：串的操作：单个字符串的长度统计、翻转、多个字符串的合并、子串判别实验类型：基础性指导思想：熟练掌握C语言的字符串操作方法，理解字符串与字符型数组的差异。实验目的及要求：1、复习C语言的字符串的使用；2、理解串的操作；3、实现串的模式匹配算法；4、要求：提交实验报告，附源程序、打印运行结果。涉及的知识点：串的存储方法常见的串的函数（求长度、两个字符串的连接）串的模式匹配BF算法（又称古典的、经典的、朴素的、穷举的）实验内容：读入两个字符串，输出其长度、连接之后的结果，再判断第一个字符串是否第二个串的子串。实验步骤：编写具有以下功能的程序：1.读入两个字符串S1、