西电机电院自动化专业软件技术基础上机报告.doc

上机报告
上机目的
掌握链表的基本运算:建立,查找,删除,排序等。
掌握树的基本运算。
上机内容
,编写完成下列功能的算法:
①找出最小值结点,且打印该数值;
②若该数值是奇数,则将其与直接后继结点的数值交换;
③若该数值是偶数,则将其直接后继结点删除。
:①建立一个数据域为1至10的带头结点的链表;
②将此链表就地逆转。
、英文字母和其它字符的单链表,试编写一个算法将该单链表拆分为三个单链表,使每个单链表中只包含同一类的字符,要求利用原表中的结点空间作为这三个表的结点空间,头结点可以另辟空间。
,试按价格从高到低的次序建立一个循环链表,每个结点有价格、数量和指针三个域。现新到10台价格为4000元的电视机,修改原链表并输出修改后链表的所有内容。
。例如,‘abba’,‘abcba’都是回文, ‘ababab’不是回文,试编写程序判别从标准输入读入的以’@’为结束符的字符序列是否是回文。
,求二叉树的结点数目和叶子结点数目。
设计说明:写出数据结构的定义和算法流程
第一题:
(1)使用尾插法建立带有头结点的单链表:因为题目要求为正整数,故以数字0最为结束符。
(2)查找过程中,首先定义两个结点类型的变量p、s,p指向头结点,s指向第一个结点,然后将p依次后移,并且每移动一次就将p的值与s的值进行比较,若p->data<s->data,则将p赋给s;否则p继续后移,直至链尾。
(3)删除结点过程:删除结点就需要找到此结点的前驱结点,然后将此结点的前驱的后继指向此结点的后继结点即可。
(4)结点交换过程:定义一个中间结点,先将要交换的结点中的一个A赋给中间结点保存,然后将结点B的值赋给结点A,再将中间结点的值赋给结点B即可完成结点的交换。
(5)打印结点过程:首先定义局部结点变量p,并且使其指向要打印的链表的头结点,然后将p结点后移,每移动一次就打印当前p的值,直至p的后续结点为NULL。
第二题:
(1)使用尾插法建立带有头结点的单链表:因为题目要求数字为1到10,故当数字小于1或者大于10时就停止输入。
(2)打印结点过程:首先定义局部结点变量p,并且使其指向要打印的链表的头结点,然后将p结点后移,每移动一次就打印当前p的值,直至p的后续结点为NULL。
(3)逆置过程:首先定义两个结点p、q,p结点指向第一个结点,q结点始终指向p的后续结点然后将p的后续指向q的后续,并且将q的后续指向p,再将头结点指向q,因为p的位置不变,q依次后移,每次移动都将q插在head之后,故可以实现链表的逆置。
第三题:
(1) 使用尾插法建立带有头结点的单链表:当遇到回车符时结束字符的输入。
(2) 打印结点过程:首先定义局部结点变量p,并且使其指向要打印的链表的头结点,然后将p结点后移,每移动一次就打印当前p的值,直至p的后续结点为NULL。
(3)对链表的分类整理:考虑到分类之后要返回给不同的三个链表,故使用全局变量,在函数调用时直接对全局变量进行操作。在查找过程中根据ASCII码的不同依次将他们连接在相应的链表之后。通过将头结点的地址传给PRINT函数就可以将相应的链表打印出来。
第四题:
(1)使用尾插法建立带有头结点的单链表:当遇到price和number均为0时结束输入。
(2)排序过程:首先定义两个中间结点p、q,p结点指向链表的第一个结点,q结点指向p的后续结点,将q结点的price与p结点的price进行比较,如果p->price<q->price,则将两者进行交换,直至q指向链表的最后一个元素。然后将p后移,重复以上步骤执行。
(3)插入过程:在执行插入过程中,要先进行查找操作,即将要插入的元素s的s->price与原来链表中的元素逐个进行比较,插入到第一个比s->price大的数据前。
第五题:
方法一:
基本思想:将字符存入数组,然后对数组进行首尾两端的元素进行比较,若相等,则将前标号后移一位,同时后标号前移一位。
方法二:
基本思想:采用堆栈的思想:先将数据存入链表,然后计算链表长度,将链表的前一半压入堆栈,若长度为则需
先将链表当前指向后移一个,在将堆栈数据弹出,与链表后半部分数据进行比较;若长度为偶数,则直接将链堆、
栈中数据弹出与链表中的后半部分进行比较。
第六题:
(1)树的建立:树的建立是借用队列先入先出的原则,队尾指向当前输入的结点,对头指向当前在这个结点的双亲结点,当尾结点是偶数时,当前结点作为左孩子与双亲结点链接,当尾结点为奇数时,当前结点作为右孩子与双亲结点进