内容发布更新时间 : 2024/7/1 13:29:54星期一 下面是文章的全部内容请认真阅读。

西电机电院软件技术基础大作业

上机报告

班级：04103201 姓名：赵伟 学号：04103123

一、上机目的:

明确线性表和树的相关用法，写出相应的程序，实现相应所需的功能。

二、上机内容

1．设有一个由正整数组成的无序单链表，编写完成下列功能的算法：

① 找出最小值结点，且打印该数值；

② 若该数值是奇数，则将其与直接后继结点的数值交换； ③ 若该数值是偶数，则将其直接后继结点删除。

2．编一程序：①建立一个数据域为1至10的带头结点的链表； ②将此链表就地逆转。

3．设有一个含有数字、英文字母和其它字符的单链表，试编写一个算法将该单链表拆分为三个单链表，使每个单链表中只包含同一类的字符，要求利用原表中的结点空间作为这三个表的结点空间，头结点可以另辟空间。

4．某百货公司仓库中有一批电视机，试按价格从高到低的次序建立一个循环链表，每个结点有价格、数量和指针三个域。现新到10台价格为4000元的电视机，修改原链表并输出修改后链表的所有内容。

5．假设称正读反读都相同的字符序列为回文。例如，‘abba’，‘abcba’都是回文， ‘ababab’不是回文，试编写程序判别从标准输入读入的以’@’为结束符的字符序列是否是回文。

6．试设计一个程序，求二叉树的结点数目和叶子结点数目。

三、设计说明

1.用一个单链表实现，单链表中的每一个节点储存一个整数，从前到后遍历一遍链表找出最小值，若该值是奇数，则将最小值节点与其后节点交换，若该值

是偶数，则将其后节点删除。

2.建立一个单链表，从头结点开始，数据域依次是1到10。再按照头插法的思想，从第二个节点还是，依次把其后的节点，插到头节点的后面。即可将链表逆转。

3.建立三个单链表。其中一个链表用来存输入的数据，其余三个链表置空，从前到后遍历一遍原始链表，若数据域是数字，则继续遍历该链表。若数据域是英文字母或是其它字符，则将其从原来的链表中删除，并把它分别插入到其它两个链表中。

4.建立一个循环链表，链表的数据域为商品的价格和数量，最后插入（4000,10）节点。从前到后遍历这个链表，若链表中存在一个节点，其数据域的价格为4000，则数量再加上10即可，若不存在，按照链表的顺序将该节点插入。

5.建立一个顺序表，从键盘上输入字符串，从第一个节点和最后一个节点依次向中间比较。若发现不同。则比较结束，该字符串不是回文，否则，是回文。 6.叶子节点的左右孩子节点的数据域均为0.用先序遍历的方法遍历该链表，每遍历到一个节点，就将节点数加1，若节点的左右孩子节点的数据域为0，则叶子节点数加1.

四、调试分析

1.在调试过程中，要充分考虑到各种可能出现的情况。比如说，当有多个最小值时，需要依次与其后的节点进行操作；再如，到最小值在最后一个节点时，就不能进行任何处理了。 时间复杂度：O(n)。

2.好像没有遇到什么问题。 时间复杂度：O(n)。

3.此处要注意结束条件，否则可能没法正常退出。 时间复杂度：O(n)。 4.本题需要注意，链表中是否有数据域为4000的节点，有的话就不用再新建了。 时间复杂度：O(n)。

5.本题好像也没有遇到什么问题。 时间复杂度：O(n)。

6.本题要注意，叶子节点的定义。否则，程序无法判断节点是否为叶子节点。 时间复杂度：O(n)。

五、测试结果

1.