线性表应用

2024-07-05 20:36| 来源: 网络整理| 查看: 265

完成单链表基本操作，并使用基本操作实现集合的并、交和差功能。

集合的实现方法有多种，其中一种方法是用单链表表示。

struct Node { DataType element; struct Node *next; }；

假设单链表的头结点不存放集合元素，但头结点的element存放链表中数据元素的个数。

测试输入：

5 91 51 2 32 7 4 21 51 2 16

预期输出：

并集： 16 21 4 5 91 51 2 32 7 交集：51 2 差集：5 91 32 7

测试输入：

2 1 100 4 16 101 1 6

预期输出：

并集： 6 101 16 4 2 1 100 交集：1 差集：2 100

#ifndef _LINKSET_H_ #define _LINKSET_H_ #include using namespace std; typedef int DataType; // 定义链表节点结构 struct node { DataType element; struct node *next; }; typedef struct node *SET; void insert(DataType datax, SET set); /* 函数名： InitSet 函数功能：根据参数num，初始化集合函数参数：集合元素的个数返回值：集合头指针 */ SET InitSet(int num) { SET p; p = new struct node; p->next = NULL; p->element = num; int temp; for (int i = 0; i < num; i++) { cin >> temp; insert(temp, p); //调用insert函数，将输入数据插入集合 } return p; } /* 函数名： find 函数功能：在集合中查找值为datax的成员函数参数：datax:待查找的值； set：集合的头结点返回值：找到值为datax的成员返回1，否则返回0 */ int find(DataType datax, SET set) { // 遍历集合中的每个节点，如果找到与datax相等的元素，返回1；否则返回0 SET a = set->next; while (a->next != NULL) { if (a->element == datax) return 1; a = a->next; } return 0; } /* 函数名： insert 函数功能：在集合set中插入值为datax的成员，插入位置在表头函数参数：datax:待插入的值； set：集合的头结点返回值：无 */ void insert(DataType datax, SET set) { // 创建新节点，并将datax插入集合set的表头 SET q = set; SET p = (SET)malloc(sizeof(struct node)); while (q->next != NULL) { q = q->next; } p->next = NULL; p->element = datax; q->next = p; } /* 函数名： copyList 函数功能：将集合setA复制生成集合setB 函数参数：setA 、setB的头结点返回值：无 */ void copySet(SET setA, SET setB) { // 未提供函数实现 } /* 函数名： printSet 函数功能：输出集合的元素，以空格作为元素之间分界符函数参数：set的头结点返回值：无 */ void printSet(SET set) { // 遍历集合中的每个节点，输出节点的元素值，以空格作为分隔符 SET p = (SET)malloc(sizeof(struct node)); p = set->next; while (p != NULL) { printf("%d ", p->element); p = p->next; } } /* 函数名： setUnion 函数功能：求两个集合setA 和 setB的并集函数参数：setA和setB的头结点返回值：并集集合的头结点 */ SET setUnion(SET setA, SET setB) { int flag; SET p1 = setA->next, p2 = setB->next, p; SET head = (SET)malloc(sizeof(struct node)); head->next = NULL; SET q = head; while (p2 != NULL) { flag = find(p2->element, setA); if (flag != 1) { p = (SET)malloc(sizeof(struct node)); p->element = p2->element; q->next = p; q = p; } p2 = p2->next; } while (p1 != NULL) { p = (SET)malloc(sizeof(struct node)); p->element = p1->element; q->next = p; q = p; q->next = NULL; p1 = p1->next; } return head; } /* 函数名： setIntersect 函数功能：求两个集合setA 和 setB的交集函数参数：setA和setB的头结点返回值：交集集合的头结点 */ SET setIntersect(SET setA, SET setB) { int flag; SET p1 = setA->next, p2 = setB->next, p; SET head = (SET)malloc(sizeof(struct node)); SET q = head; while (p1 != NULL) { flag = find(p1->element, setB); if (flag == 1) { p = (SET)malloc(sizeof(struct node)); p->element = p1->element; q->next = p; q = p; q->next = NULL; } p1 = p1->next; } return head; } /* 函数名： setExcept 函数功能：求两个集合setA 和 setB的差函数参数：setA和setB的头结点返回值：结果集合的头结点 */ SET setExcept(SET setA, SET setB) { int flag; SET p1 = setA->next, p2 = setB->next, q, p; SET head = (SET)malloc(sizeof(struct node)); q = head; while (p1 != NULL) { flag = find(p1->element, setB); if (flag != 1) { p = (SET)malloc(sizeof(struct node)); p->element = p1->element; q->next = p; q = p; q->next = NULL; } p1 = p1->next; } return head; } #endif #include "linkset.h" int main(void) { int count; cin >> count; SET setA = InitSet(count); // 初始化集合A cin >> count; SET setB = InitSet(count); // 初始化集合B cout

【本文地址】

公司简介

联系我们