已知一顺序表A,其元素值非递减有序排列,编写一个函数删除顺序表中多余的值相同的元素。
时间: 2024-09-29 21:08:19 浏览: 43
已知有两个按元素值递增有序的顺序表A和B,设计一个算法将表A和表B的全部元素归并为一个按元素值递增有序的顺序表C。
5星 · 资源好评率100%
要删除顺序表A中的多余相同元素,我们可以采用双指针的方法,遍历列表的同时维护两个指针。第一个指针(i)用于遍历列表,第二个指针(j)则指向最后一个不重复的元素。当遇到与前一个元素相同的值时,我们跳过它们;如果找到不同的值,就将其移动到第二个指针的位置并更新第二个指针。
以下是一个简单的C语言函数实现示例:
```c
#include <stdio.h>
// 定义顺序表结构体
typedef struct {
int value;
struct Node* next; // 指向下个元素
} Node;
// 删除重复元素并返回新的头节点
Node* removeDuplicates(Node* head) {
if (head == NULL || head->next == NULL) {
return head;
}
Node* i = head;
Node* j = head;
while (i != NULL && i->next != NULL) {
if (i->value != i->next->value) { // 不同的值
i->next = i->next->next;
if (i->next == NULL) {
j = i + 1; // 结束条件:所有元素处理完后,最后一个元素就是不重复的
}
} else {
i = i->next; // 相同的值,继续寻找下一个
}
}
return j; // 返回新的头节点,可能与原头节点不同
}
// 打印顺序表
void printList(Node* head) {
Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->value);
temp = temp->next;
}
printf("\n");
}
int main() {
// 假设你已经有了一个初始化好的顺序表A
Node* list = ...;
// 删除重复元素
list = removeDuplicates(list);
// 打印结果
printList(list);
return 0;
}
```
在这个例子中,`removeDuplicates()` 函数接受一个顺序表的头节点作为参数,然后直接修改原头节点。如果你希望保留原始数组而不想改变它,你可以创建一个新的顺序表并复制非重复的元素。
阅读全文