一、实验目的

1、复习线性表的逻辑结构、存储结构及基本操作；

2、掌握顺序表和（带头结点）单链表；

3、了解有序表。

二、实验内容

1、请采用顺序表或(带头结点)单链表实现：

（1）假设有序表中数据元素是正整数，请通过实现下列函数进而实现有序表的构造及归并：

(a) OrderInput(&L, int (*compare)(a, b))

//根据有序判定函数compare，并利用(b)中的有序插入函数OrderInsert，构造有序表L

(b) OrderInsert(&L, e, int (*compare)(a, b))

//根据有序判定函数compare，在有序表L的适当位置插入元素e

(c) OrderMerge(&La, &Lb, &Lc, int (*compare)())

//根据有序判定函数compare，将两个有序表La和Lb归并为一个有序表Lc

（2）请实现升幂多项式的构造及相加。升幂多项式是指多项式的各项按指数升序有序，约定系数不能等于0，指数不能小于0。

例如2-10x^2+3x^5或者 2-100x^14+3x^100-16x^1000

2、请实现:求一个顺序表序列的最长连续递增子序列，例如，{1,9,2,5,7,3,4,6,8,0}中的最长连续递增子序列为{3,4,6,8}

3、请实现:求两个单链表升序集合的交集，例如，{1,2,5}∩{2,4,5,8,10}={2,5}

三、数据结构及算法分析与设计

1.（1）数据结构:

链表节点结构体（ListNode）

data：存储节点的数据元素。

next：指向链表中下一个节点的指针。

链表结构体（LinkList）

head：指向链表的头结点，头结点不存储数据，用于简化插入和删除操作。

length：记录链表的长度，即节点的数量。

算法分析与设计：

1.初始化链表（InitList）

输入：链表指针。

输出：无。

2.创建新节点（CreateNode）

输入：数据元素e。

输出：新创建的节点指针。

3.打印链表（PrintList）

输入：链表指针。

输出：打印链表的所有数据元素。

4.有序输入（OrderInput）

输入：链表指针、比较函数指针。

输出：无。

5.有序插入（OrderInsert）

输入：链表指针、数据元素e、比较函数指针。

输出：无。

6.有序归并（OrderMerge）

输入：两个有序链表指针、结果链表指针、比较函数指针。

输出：无。

1.（2）数据结构: 多项式的项结构体（PolyNode）

coefficient：表示项的系数。

exponent：表示项的指数。

next：指向链表中下一个节点的指针。

算法分析与设计：

1.添加项（addTerm）

输入：多项式指针、系数、指数。

输出：无。

2.打印多项式（printPolynomial）

输入：多项式指针。

输出：打印多项式的每一项。

3.多项式相加（addPolynomials）

输入：两个多项式指针。

输出：返回相加后的多项式。

2.数据结构: 数组：

int arr[]：用于存储输入的顺序表序列。

int subsequence[]：用于存储最长连续递增子序列。

int subsequenceSize：用于存储子序列的大小。

算法分析与设计：

1.初始化：

设置 maxLength 为 1，因为单个元素本身就是一个递增子序列。

设置 currentLength 为 1，表示当前递增子序列的长度。

endIndex 用于记录最长递增子序列的结束索引。

2.遍历数组：

从第二个元素开始遍历数组。

若当前元素大于前一个元素，则递增 currentLength 并更新 subsequence。

若当前元素不大于前一个元素，则比较 currentLength 和 maxLength。

若 currentLength 大于 maxLength，则更新 maxLength 和 endIndex。

重置 currentLength 为 1，并更新 subsequence。

3.处理最后一个递增子序列：

遍历结束后，再次比较 currentLength 和 maxLength，以确保最后一个递增子序列被考虑。

4.复制最长递增子序列：

根据 endIndex 和 maxLength 计算最长递增子序列的起始索引。

将最长递增子序列复制到 subsequence 数组中。

3.数据结构:链表节点结构体（ListNode）：

int val：存储节点的值。

ListNode* next：指向链表中下一个节点的指针。

算法分析与设计：

1.初始化：

创建两个链表的头节点 head1 和 head2。

创建一个哑节点 dummyHead 作为结果链表的头节点，以及一个指针 tail 指向结果链表的尾部。

2.遍历链表：

使用两个指针 p 和 q 分别遍历 head1 和 head2。

3.处理结束条件：

当p或q任一指针到达链表末尾时，结束遍历。

4.返回结果：

返回结果链表的头节点。

四、核心程序代码（给出必要注释）

1.（1）

int main() {

    LinkList La, Lb, Lc;//定义三个有序表

    //对有序表进行初始化

    InitList(&La);

    InitList(&Lb);

    InitList(&Lc);

    printf("请输入有序表La中的元素(输入-1结束):\n");

    OrderInput(&La, ascendingCompare);

    printf("请输入有序表Lb中的元素(输入-1结束):\n");

    OrderInput(&Lb, ascendingCompare);

    printf("有序表La: ");

    PrintList(&La);

    printf("有序表Lb: ");

    PrintList(&Lb);

    OrderMerge(&La, &Lb, &Lc, ascendingCompare);//调用函数进行归并

    printf("有序表La和Lb归并为一个有序表Lc: ");

    PrintList(&Lc);

    return 0;

}

1.（2）

int main() {

    Polynomial poly1, poly2, result; //定义多项式1、多项式2、相加的的结果

    //初始化头指针

    poly1.head = NULL;

    poly2.head = NULL;

    //多项式1添加系数和指数

    addTerm(&poly1, 2, 0);

    addTerm(&poly1, -10, 2);

    addTerm(&poly1, 3, 5);

    //多项式2添加系数和指数

    addTerm(&poly2, 2, 0);

    addTerm(&poly2, -100, 14);

    addTerm(&poly2, 3, 100);

    addTerm(&poly2, -16, 1000);

    printPolynomial(&poly1);

    printPolynomial(&poly2);

    result = addPolynomials(&poly1, &poly2);

    printf("两个多项式相加的结果是: ");

    printPolynomial(&result);

    return 0;

}

2.

int main() {

    int arr[] = {1, 9, 2, 5, 7, 3, 4, 6, 8, 0};

    int n = sizeof(arr) / sizeof(arr[0]);//记录数组元素个数

    int subsequence[20]; // 假设最长递增子序列不会超过20个元素

    int subsequenceSize = 0;

    findLongestIncreasingSubsequence(arr, n, subsequence, &subsequenceSize);

    printf("最长连续递增子序列是: ");

    for (int i = 0; i < subsequenceSize; i++) {

        printf("%d ", subsequence[i]);

    }

    return 0;

}

3.

int main() {

    // 创建两个单链表

    ListNode *list1 = createNode(1);

    list1->next = createNode(2);

    list1->next->next = createNode(5);

    ListNode *list2 = createNode(2);

    list2->next = createNode(4);

    list2->next->next = createNode(5);

    list2->next->next->next = createNode(8);

    list2->next->next->next->next = createNode(10);

    // 求交集

    ListNode *intersectionList = intersection(list1, list2);

    // 打印交集

    printf("两个单链表升序集合的交集是：");

    printList(intersectionList);

    // 释放链表内存

    while (intersectionList != NULL) {

        ListNode *temp = intersectionList;

        intersectionList = intersectionList->next;

        free(temp);

    }

    return 0;

}

五、测试及结果（给出测试用例及测试结果）

1.（1）

1.（2）

2.

3.