两个递增的线性表合成一个递增的线性表
时间: 2023-05-21 13:05:13 浏览: 126
可以使用归并排序的思想,将两个递增的线性表按顺序合并成一个新的递增的线性表。具体的做法可以使用双指针来遍历两个线性表,比较当前指针指向的元素大小,选择较小的元素加入新的线性表中,直到其中一个线性表遍历结束,然后将另一个线性表中剩余的元素全部加入新的线性表中即可。
相关问题
用线性表将两个递增的线性表合并成一个非递减线性表,要求利用原表的结点空间结构构造新表
算法思路:
1.定义两个指针分别指向两个递增的线性表的头结点;
2.新建一个空的线性表作为合并后的结果;
3.比较两个指针指向结点的大小,将小的结点插入新表中;
4.将小的结点的指针向后移动一位;
5.重复执行3、4两步,直到其中一个表的指针指向空;
6.将另一个表剩余的结点插入新表中;
7.返回合并后的结果。
实现代码如下(C语言):
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
int data;
struct Node *next;
}Node, *LinkedList;
LinkedList createList(int n) { // 创建一个长度为n的有序线性表
LinkedList head = (LinkedList)malloc(sizeof(Node));
head->next = NULL;
LinkedList p = head;
int i;
for (i = 0; i < n; i++) {
LinkedList newNode = (LinkedList)malloc(sizeof(Node));
scanf("%d", &newNode->data);
newNode->next = NULL;
p->next = newNode;
p = p->next;
}
return head;
}
LinkedList mergeList(LinkedList l1, LinkedList l2) { // 合并两个有序线性表
LinkedList head = (LinkedList)malloc(sizeof(Node));
head->next = NULL;
LinkedList p = head;
LinkedList p1 = l1->next;
LinkedList p2 = l2->next;
while (p1 != NULL && p2 != NULL) {
if (p1->data <= p2->data) {
p->next = p1;
p1 = p1->next;
} else {
p->next = p2;
p2 = p2->next;
}
p = p->next;
}
if (p1 == NULL) {
p->next = p2;
} else {
p->next = p1;
}
return head;
}
void printList(LinkedList list) { // 输出链表中的元素
LinkedList p = list->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main() {
int n, m;
printf("请输入有序线性表1的长度:");
scanf("%d", &n);
printf("请输入有序线性表1的元素:");
LinkedList l1 = createList(n);
printf("请输入有序线性表2的长度:");
scanf("%d", &m);
printf("请输入有序线性表2的元素:");
LinkedList l2 = createList(m);
printf("合并后的非递减线性表为:");
LinkedList l3 = mergeList(l1, l2);
printList(l3);
return 0;
}
```
运行结果:
```
请输入有序线性表1的长度:3
请输入有序线性表1的元素:1 3 5
请输入有序线性表2的长度:4
请输入有序线性表2的元素:2 4 6 8
合并后的非递减线性表为:1 2 3 4 5 6 8
```
线性表的应用算法:构造两个按指数递增的有序链表,实现两个一元多项式相加
这个算法的实现步骤如下:
1. 定义一个结构体表示多项式的每一项,包括系数和指数。
2. 构造两个按指数递增的有序链表,分别表示两个多项式。
3. 从两个链表的头部开始遍历,比较当前节点的指数大小,将指数较小的节点加入结果链表,并将指针指向下一个节点。
4. 如果两个节点的指数相同,则将它们的系数相加,并将结果加入结果链表,同时将两个指针都指向下一个节点。
5. 当其中一个链表遍历完后,将另一个链表的剩余节点加入结果链表。
6. 最后得到的结果链表即为两个多项式相加的结果。
这个算法的时间复杂度为 O(m+n),其中 m 和 n 分别为两个多项式的项数。