高效合并有序单链表并去重的实现方法 |
您所在的位置：网站首页 › 合并两个单链表c语言不用辅助空位 › 高效合并有序单链表并去重的实现方法 |
高效合并有序单链表并去重的实现方法
|
摘要：本文介绍了一种高效合并有序单链表并去重的实现方法。通过定义链表节点的结构体，使用尾插法建立单链表，然后通过比较节点的值，将两个有序链表合并为一个新的链表，并去除重复的元素。这种方法不仅时间复杂度低，而且不需要额外的空间。
正文：
引言：合并有序单链表并去重是一种常见的链表操作，本文介绍了一种高效的实现方法，通过比较节点的值，将两个有序链表合并为一个新的链表，并去除重复的元素。
1. 定义链表节点的结构体
首先，我们定义了一个名为Lnode的结构体，包含一个数据域和一个指向下一个节点的指针。然后，使用typedef将Linklist定义为指向Lnode的指针，用来表示链表。 typedef struct Lnode { int data; struct Lnode* next; }Lnode,*Linklist; 2. 初始化链表和创建链表我们使用initlist函数来初始化链表，将链表的头结点指针指向NULL。然后，使用Creatlist函数来创建链表，通过尾插法将元素插入到链表中。 void initlist(Linklist &L) { L = new Lnode; L->next = NULL; } void Creatlist(Linklist& L, int n)//尾插法建立单链表 { Linklist r;//生成尾节点 Linklist p;//生成要插入的结点p L = new Lnode; L->next = NULL; r = L; printf("请输入元素（元素间用空格隔开）: \n"); for (int i = 0; n > i; i++) { p = new Lnode; scanf_s("%d", &p->data); p->next = r->next; r->next = p;//将新的结点p插入到尾节点r之后 r = p;//r指向新的结点p; } } 3. 打印链表为了验证链表的创建结果，我们实现了printlist函数，用来打印链表的所有元素。 void printlist(Linklist& L) { Linklist p; p = L->next; while (p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n"); } 4. 合并链表并去重为了合并两个有序链表并去重，我们实现了Mergelist函数。首先，我们将一个链表的头结点指针赋值给新的链表指针，作为合并后的链表。然后，使用三个指针分别指向两个有序链表和新链表的尾部。通过比较节点的值，将较小的节点插入到新链表的尾部，并移动相应的指针。最后，将非空链表的剩余部分插入到新链表的尾部。 void Mergelist(Linklist& la, Linklist& lb,Linklist& lc) { lc = la; Linklist pa, pb,pc; pa = la->next; pb = lb->next; pc = lc;//尾指针pc负责将其他结点插入pc之后 while ((pa != NULL) && (pb != NULL)) { if (pa->data data) { pc->next = pa;//将较小的值对应的结点插入到pc之后 pc = pa;//尾指针的移动，保证pc一直在链表尾部 pa = pa->next;//pa->next负责遍历la中的结点 } else { pc->next = pb; pc = pb; pb = pb->next; } } pc->next = pa != NULL ? pa : pb;//将非空表的剩余段插入到尾指针pc的后面 delete lb;//释放lb的头结点； } 5. 去除重复元素为了去除合并后链表中的重复元素，我们实现了delete_the_same_of_elem函数。通过遍历链表，比较相邻节点的值，如果相同则删除后一个节点。 void delete_the_same_of_elem(Linklist &lc) { Linklist p; p = lc; while (p->next != NULL) { if (p->data == p->next->data) { p->next = p->next->next; } else { p = p->next; } } } 6. 测试结果在主函数中，我们先初始化链表la和lb，然后分别创建这两个有序链表，打印它们的内容。接着，调用Mergelist函数将两个链表合并为一个新的链表，并调用delete_the_same_of_elem函数去除重复元素。最后，打印合并去重后的链表。 int main() { Linklist la; Linklist lb; Linklist lc; initlist(la); initlist(lb); lc = la; int n1,n2; printf("请输入要创建的单链表la长度n1：\n"); scanf_s("%d", &n1); Creatlist(la,n1); printf("创建的单链表la为:\n"); printlist(la); printf("请输入要创建的单链表lb长度n2：\n"); scanf_s("%d", &n2); Creatlist(lb, n2); printf("创建的单链表lb为:\n"); printlist(lb); Mergelist(la, lb, lc); delete_the_same_of_elem(lc); printf("合并后的单链表为：\n"); printlist(lc); return 0; } 7.完整代码展示： #include typedef struct Lnode { int data; struct Lnode* next; }Lnode,*Linklist; void initlist(Linklist &L) { L = new Lnode; L->next = NULL; } void Creatlist(Linklist& L, int n)//尾插法建立单链表 { Linklist r;//生成尾节点 Linklist p;//生成要插入的结点p L = new Lnode; L->next = NULL; r = L; printf("请输入元素（元素间用空格隔开）: \n"); for (int i = 0; n > i; i++) { p = new Lnode; scanf_s("%d", &p->data); p->next = r->next; r->next = p;//将新的结点p插入到尾节点r之后 r = p;//r指向新的结点p; } } void printlist(Linklist& L) { Linklist p; p = L->next; while (p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n"); } void Mergelist(Linklist& la, Linklist& lb,Linklist& lc) { lc = la; Linklist pa, pb,pc; pa = la->next; pb = lb->next; pc = lc;//尾指针pc负责将其他结点插入pc之后 while ((pa != NULL) && (pb != NULL)) { if (pa->data data) { pc->next = pa;//将较小的值对应的结点插入到pc之后 pc = pa;//尾指针的移动，保证pc一直在链表尾部 pa = pa->next;//pa->next负责遍历la中的结点 } else { pc->next = pb; pc = pb; pb = pb->next; } } pc->next = pa != NULL ? pa : pb;//将非空表的剩余段插入到尾指针pc的后面 delete lb;//释放lb的头结点； } void delete_the_same_of_elem(Linklist &lc) { Linklist p; p = lc; while (p->next != NULL) { if (p->data == p->next->data) { p->next = p->next->next; } else { p = p->next; } } } int main() { Linklist la; Linklist lb; Linklist lc; initlist(la); initlist(lb); lc = la; int n1,n2; printf("请输入要创建的单链表la长度n1：\n"); scanf_s("%d", &n1); Creatlist(la,n1); printf("创建的单链表la为:\n"); printlist(la); printf("请输入要创建的单链表lb长度n2：\n"); scanf_s("%d", &n2); Creatlist(lb, n2); printf("创建的单链表lb为:\n"); printlist(lb); Mergelist(la, lb, lc); delete_the_same_of_elem(lc); printf("合并后的单链表为：\n"); printlist(lc); return 0; }8、运行结果展示：
参考文献：数据结构（C语言第二版双色版）严蔚敏 李冬梅 吴伟民 编著 |
【本文地址】
今日新闻 |
推荐新闻 |