线性表之单链表求集合并集

学习目标：

掌握以下内容 1、单链表的创建 2、将数据插入单链表 3、单链表合并 4、单链表去重

学习时间：

2020/10/20

学习产出：

技术博客 1 篇 哔哩哔哩专栏1篇

文章目录

线性表之单链表求集合并集学习目标：学习时间：学习产出：一、自定义结构体二、初始化单链表三、单链表长度测量四、 在第i个位置插入结点五、单链表排序（递增）六、单链表去除重复元素五、两个链表并集六、输出单链表七、主函数八、调用函数库九、运行结果

一、自定义结构体

typedef char elem; typedef struct LNode { elem data; struct LNode *next; }Lnode;//将结构体命名为Lnode

二、初始化单链表

int InitList(Lnode *&L) { L=(Lnode*)malloc(sizeof(Lnode));//申请分配空间 if(L == NULL) { printf("申请分配内存空间失败\n"); return 0; } L -> next = NULL; return 1; }

三、单链表长度测量

//求单链表的长度 int LinkList_Length(Lnode *L) { Lnode *p; p = L; int j = 0; while(p -> next != NULL) //没到NULL继续移至下一个结点 { p = p -> next; j++; } return j; }

四、 在第i个位置插入结点

//在第i个位置插入结点 bool InsertAfter_Linklist(Lnode *&L, elem x, int i) { Lnode *p, *s; int n; n = LinkList_Length(L); if (i <= 0) //判断插入位置是否合法 { printf("插入位置错误\n"); return false; } if(i > n+1)//判断插入位置是否合法 { printf("插入位置错误\n"); return false; } p = L; int j; for(j = 0; p && j < i - 1; j++) p = p -> next; //查找到第i结点前一结点 s = (Lnode*)malloc(sizeof(Lnode)); if(s == NULL)//判断申请空间是否成功 return false; s -> data = x; s -> next = p -> next; p -> next = s; return true; } }

五、单链表排序（递增）

void list_sort(Lnode *&L) { Lnode *p = L->next; int temp, i, j, num;//num用来存放单链表长度 num = LinkList_Length(L); for(i=0;i<num-1;i++) { p = L->next;//每次去第一个结点 for( j=0;j<num-i-1;j++) { if(p->data > p->next->data) //与下一个数据比较，如果大于下一个数据，则交换位置 { temp = p->data; p->data = p->next->data; p->next->data = temp; } p = p->next;//将p移至下一个位置 } } }

六、单链表去除重复元素

void Del_Sam(Lnode *L)//去重 { Lnode *p1, *p2; p1 = L -> next; p2 = p1 -> next; while(p2) { if(p1 -> data != p2 -> data) //如果与下一个结点元素不相等将其连接到链表尾端 { p1 -> next = p2; p1 = p2; p2 = p2 -> next; } else //如果相等就移至下一个结点 { p2 = p2 -> next; } } p1 -> next = NULL;//在最后加上NULL，使其成为完整链表 }

五、两个链表并集

Lnode* Mesh_LinkLists(Lnode *L1, Lnode *L2) //L1和L2为递增序列，都有头结点 { Lnode *p1, *p2， *L3; InitList(L3);//新建一个单链表，该链表将会表示L1,L2的并集 if(!L1)//L1为空链表 { L1 = L2; return L3;//返回空表 } int i = 1; p1 = L1 -> next; p2 = L2 -> next; while(p1 && p2) //如果L1 -> next与L2 -> next均不为空，执行循环 { if(p1 -> data <= p2 -> data) { InsertAfter_Linklist(L3, p1 -> data, i++); //较小的数据插入链表L3 p1 = p1 -> next; } else { InsertAfter_Linklist(L3, p2 -> data, i++); //较小的数据插入链表L3 p2 = p2 -> next; } } //长链表较短链表多出的部分接在L3链表的后面 while(p1)//L1较长时 { InsertAfter_Linklist(L3, p1 -> data, i++); p1 = p1 -> next; } while(p2)//L2较长时 { InsertAfter_Linklist(L3, p2 -> data, i++); p2 = p2 -> next; } Del_Sam(L3);//去除重复数据 return L3; }

六、输出单链表

//输出线性表 void Print_LinkList(Lnode *L) { LNode *p=L->next; //p指向首结点 while (p!=NULL) //p不为NULL,输出p结点的data域 { printf("%c ",p->data); p=p->next; //p移向下一个结点 } printf("\n"); }

七、主函数

#include "Linklist.cpp" int main() { elem A[10] = {'c','a','e','h'}; elem B[10] = {'f','h','b','g','d','a'}; int i; Lnode *L1, *L2, *L3; InitList(L1); InitList(L2); for(i = 0; A[i]; i++) //将 { InsertAfter_Linklist(L1,A[i], i+1); } for(i = 0; B[i]; i++) { InsertAfter_Linklist(L2, B[i], i+1); } printf("原 集 合A："); Print_LinkList(L1); printf("原 集 合B："); Print_LinkList(L2); list_sort(L1); list_sort(L2); printf("有序集合A："); Print_LinkList(L1); printf("有序集合B："); Print_LinkList(L2); L3 = Mesh_LinkLists(L1, L2); printf("集合的并C："); Print_LinkList(L3); return 0; }

八、调用函数库

#include <stdio.h> #include <malloc.h> #include<stdlib.h> typedef char elem; typedef struct LNode { elem data; struct LNode *next; }Lnode;//将结构体命名为Lnode //单链表初始化 int InitList(Lnode *&L) { L=(Lnode*)malloc(sizeof(Lnode));//申请分配空间 if(L == NULL) { printf("申请分配内存空间失败\n"); return 0; } L -> next = NULL; return 1; } //求单链表的长度 int LinkList_Length(Lnode *L) { Lnode *p; p = L; int j = 0; while(p -> next != NULL) { p = p -> next; j++; } return j; } //在第i个位置插入结点 bool InsertAfter_Linklist(Lnode *&L, elem x, int i) { Lnode *p, *s; int n; n = LinkList_Length(L); if (i <= 0) { printf("插入位置错误\n"); return false; } if(i > n+1) { printf("插入位置错误\n"); return false; } p = L; int j; for(j = 0; p && j < i - 1; j++) p = p -> next; s = (Lnode*)malloc(sizeof(Lnode)); if(s == NULL)//判断申请空间是否成功 return false; s -> data = x; s -> next = p -> next; p -> next = s; return true; } void Del_Sam(Lnode *L)//去重 { Lnode *p1, *p2; p1 = L -> next; p2 = p1 -> next; while(p2) { if(p1 -> data != p2 -> data) { p1 -> next = p2; p1 = p2; p2 = p2 -> next; } else { p2 = p2 -> next; } } p1 -> next = NULL; } void list_sort(Lnode *&L) { Lnode *p = L->next; int temp, i, j, num;//num用来存放单链表长度 num = LinkList_Length(L); for(i=0;i<num-1;i++) { p = L->next; for( j=0;j<num-i-1;j++) { if(p->data > p->next->data) //与下一个数据比较，如果大于下一个数据，则交换位置 { temp = p->data; p->data = p->next->data; p->next->data = temp; } p = p->next;//将p移至下一个位置 } } } //集合并集 Lnode* Mesh_LinkLists(Lnode *L1, Lnode *L2) //L1和L2为递增序列，都有头结点,将L2中的值按序插入L1中 { Lnode *p1, *p2, *L3; InitList(L3); if(!L1)//L1为空链表 { L1 = L2; return L3; } int i = 1; p1 = L1 -> next; p2 = L2 -> next; while(p1 && p2) //如果L1 -> next与L2 -> next均不为空，执行循环 { if(p1 -> data <= p2 -> data) { InsertAfter_Linklist(L3, p1 -> data, i++); p1 = p1 -> next; } else { InsertAfter_Linklist(L3, p2 -> data, i++); p2 = p2 -> next; } } //长链表较短链表多出的部分接在L3链表的后面 while(p1)//L1较长时 { InsertAfter_Linklist(L3, p1 -> data, i++); p1 = p1 -> next; } while(p2)//L2较长时 { InsertAfter_Linklist(L3, p2 -> data, i++); p2 = p2 -> next; } Del_Sam(L3);//去除重复数据 return L3; } //输出线性表 void Print_LinkList(Lnode *L) { LNode *p=L->next; //p指向首结点 while (p!=NULL) //p不为NULL,输出p结点的data域 { printf("%c ",p->data); p=p->next; //p移向下一个结点 } printf("\n"); }

九、运行结果

如有错误，敬请斧正