C语言数据结构作业：复数与有理数抽象数据类型及算法复杂度

本资源是一份关于C语言的数据结构作业，主要包括两个部分：抽象数据类型的定义和算法分析。 首先，关于抽象数据类型(ADT)的定义，题目要求仿照三元组(ADTTriplet)来定义复数(ADTComplex)和有理数的数据类型。复数ADT定义了一个包含实部和虚部的结构D，以及初始化函数R，表示复数对象及其操作。具体定义如下： 1. **复数(ADTComplex)**: - 结构体D: 包含两个实数成员r和i，分别表示复数的实部和虚部。 - 函数R: 初始化函数`InitComplex`，接受实部(re)和虚部(im)作为参数，用于创建新的复数对象。 2. **有理数ADT**: - 结构体D: 定义为一个三元组，包括分子c1，分母c2，以及条件c3（c3不为零），表示有理数。 - 函数R: 只包含一个操作，`C3=c1/c2`，用于计算有理数的值，即分子除以分母。 接下来是算法分析部分，针对两个问题进行讨论： 1. **算法时间复杂度分析**: - 对于`intTime(int n)`函数，它采用线性搜索的方式，每次将`x`翻倍并递增计数器`count`，直到`x`达到`n/2`。当`n`是2的幂且`n > 2`时，循环次数为`log2(n)`。因此，时间复杂度为O(log n)，`count`的值将等于这个对数。 2. **排序算法**: - `bubble_sort`是一个冒泡排序算法，用于按降序输出三个整数X、Y、Z。它遍历数组并比较相邻元素，如果发现逆序则交换，直到整个序列有序。时间复杂度为O(n^2)，其中n为输入元素个数，这里n=3，所以`count`为3次交换。 最后，涉及到数据结构概念的区别： 1. **头指针、头结点和首元结点**: - 头指针：单链表中用于指向第一个节点的指针，不是单独的节点。 - 头结点：在单链表中，常在实际数据节点之前插入一个额外的节点，专门用于标记链表的起始位置。 - 首元结点：存储线性表第一个数据元素的节点，通常称为首节点。 关于顺序表和单链表的特性对比： - 顺序表： - 插入或删除操作可能涉及大量元素移动，因为它们是连续存储的，移动元素个数与元素位置相关。 - 逻辑相邻的元素物理上也相邻。 - 单链表： - 插入或删除操作只需要改变邻接节点的指针，效率高，但逻辑相邻的元素可能不相邻。 - 元素的物理位置由前驱节点的指针决定。 在单链表中设置头结点的主要作用： - 便于快速访问第一个元素，特别是插入和删除操作时，不需要移动其他元素，提高了操作效率。