用有序单链表实现集合的判等、交、并和差等基本运算。
（1）如果要求将交、并、差等运算的结果保存在一个新的有序单链表中，应如何修
改算法？
（2）如果表示集合的单链表是无序的，应如何实现集合的判等、交、并和差等基本
运算？时间性能如何？
(1) 如果要将交、并、差等运算的结果保存在一个新的有序单链表中，可以按照以下步骤修改算法：
创建一个新的空链表来保存结果。
遍历两个输入链表，比较节点的值，根据运算符的要求执行相应的操作。
如果要进行交集运算，当两个节点的值相等时，将该节点的值插入到新链表中。
如果要进行并集运算，将两个节点的值都插入到新链表中。
如果要进行差集运算，将只存在于第一个链表而不存在于第二个链表的节点值插入到新链表中。
最后，返回新的链表作为运算结果。
这样修改后的算法将根据需要的运算结果创建一个新的有序单链表，并将结果保存在其中。
(2) 如果表示集合的单链表是无序的，可以按照以下步骤实现集合的判等、交、并和差等基本运算：
对于判等运算，可以遍历第一个链表中的每个节点，并在第二个链表中查找是否存在相同的节点值。如果找到相同的节点值，说明两个链表相等。
对于交集运算，遍历第一个链表中的每个节点，检查该节点的值是否在第二个链表中存在。如果存在，则将该节点值插入到新的链表中。
对于并集运算，首先将第一个链表的所有节点复制到新链表中。然后遍历第二个链表的每个节点，检查该节点的值是否已经在新链表中存在，如果不存在，则将该节点值插入到新链表的末尾。
对于差集运算，遍历第一个链表的每个节点，检查该节点的值是否在第二个链表中存在。如果不存在，则将该节点值插入到新的链表中。
时间性能方面，无序链表的实现在查找和比较操作上可能会比有序链表更耗时，因为无序链表需要进行更多的遍历和比较操作。但是，具体的时间性能取决于链表的长度和具体实现方式。如果链表长度较小，无序链表的性能可能还是可以接受的。但是随着链表长度的增加，有序链表的性能通常会更好，因为可以利用有序性进行更高效的查找和比较操作。
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
typedef struct Node Node;
// 创建新节点
Node* createNode(int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
}
// 插入节点到链表尾部
void insertNode(Node** head, int value) {
Node* newNode = createNode(value);
if (*head == NULL) {
*head = newNode;
} else {
Node* current = *head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
}
}
// 打印链表
void printList(Node* head) {
Node* current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
// 判等运算
int isEqual(Node* list1, Node* list2) {
while (list1 != NULL && list2 != NULL) {
if (list1->data != list2->data) {
return 0;
}
list1 = list1->next;
list2 = list2->next;
}
// 如果两个链表同时到达末尾，说明长度相等
if (list1 == NULL && list2 == NULL) {
return 1;
}
return 0;
}
// 交集运算
Node* intersection(Node* list1, Node* list2) {
Node* result = NULL;
Node* current = list1;
while (current != NULL) {
Node* temp = list2;
while (temp != NULL) {
if (temp->data == current->data) {
insertNode(&result, temp->data);
break;
}
temp = temp->next;
}
current = current->next;
}
return result;
}
// 并集运算
Node* unionSet(Node* list1, Node* list2) {
Node* result = NULL;
Node* current = list1;
while (current != NULL) {
insertNode(&result, current->data);
current = current->next;
}
current = list2;
while (current != NULL) {
if (!isExist(result, current->data)) {
insertNode(&result, current->data);
}
current = current->next;
}
return result;
}
// 差集运算
Node* difference(Node* list1, Node* list2) {
Node* result = NULL;
Node* current = list1;
while (current != NULL) {
if (!isExist(list2, current->data)) {
insertNode(&result, current->data);
}
current = current->next;
}
return result;
}
// 判断某个值是否存在于链表中
int isExist(Node* head, int value) {
Node* current = head;
while (current != NULL) {
if (current->data == value) {
return 1;
}
current = current->next;
}
return 0;
}
int main() {
Node* list1 = NULL;
insertNode(&list1, 1);
insertNode(&list1, 2);
insertNode(&list1, 3);
insertNode(&list1, 4);
Node* list2 = NULL;
insertNode(&list2, 3);
insertNode(&list2, 4);
insertNode(&list2, 5);
insertNode(&list2, 6);
printf("List 1: ");
printList(list1);
printf("List 2: ");
printList(list2);
// 判等运算
if (isEqual(list1, list2)) {
printf("List 1 and List 2 are equal.\n");
} else {
printf("List 1 and List 2 are not equal.\n");
}
// 交集运算
Node* intersectionSet = intersection(list1, list2);
printf("Intersection: ");
printList(intersectionSet);
// 并集运算
Node* unionSet = unionSet(list1, list2);
printf("Union: ");
printList(unionSet);
// 差集运算
Node* differenceSet = difference(list1, list2);
printf("Difference: ");
printList(differenceSet);
return 0;
}
遍历两个链表，比较元素大小控制两个链表的遍历进度，使两个链表的进度保持相对同步。
无序链表应该先排序再进行集合运算。
1 #include "viewReader.h"
2 #include "oper.h"
3 #include<assert.h>
4
5
6 void readerAdmin(){//读者目录
7 printf("指针图书信息管理系统 -- 读者\n");
8 printf("1 查找图书(借阅.还书.预约)\n");//模糊查询 借阅 还书 预约图书
9 printf("2 充值余额\n");
10 printf("3 修改密码\n");
11 printf("4 返回\n");
12 printf("0 退出\n");
13 }
14
15 void fuzzy(const char *dady,const char *baby){
16 assert(dady!=NULL&& baby!=NULL );
17 int i=0;
18 size_t len = strlen(baby);
19 while(dady[i] != '\0'){
20 if(dady[i] == baby[0]){
21 if(strncmp(baby,dady+i,len)==0){
22 printf("%s ",dady);
23 }
24 }
25 i++;
26 }
27 } 29 Book *fuzzyBooks(Reader *pr){ //查找书籍
30 if(pbook == NULL){
31 printf("the list is empty!\n");
32 return pbook;
33 }
34 Book *pb = pbook;
35 char seekName[NAME_LEN];
36 printf("请输入您要查找的书籍名(模糊匹配):");
37 scanf("%*c");
38 scanf("%[^\n]",seekName);
39 int i=0;
40 int len = strlen(seekName);
41 printf("您可能想要查找的书籍如下:\n");
42 for(i=0;i<bcnt;i++){
43 fuzzy(pb[i].name,seekName);
44 }
45 printf("请您选择输入具体书名:");
46 scanf("%*c");
47 scanf("%[^\n]",seekName);
48 i=0;
49 while(strcmp(pb->name,seekName)!=0 && i<bcnt){
50 pb++;
51 i++;
52 }
53 if(strcmp(pb->name,seekName) == 0){
54 printf("编号为%d 的书籍的信息如下:\n",pb->id);
55 printf("书号:%d\t书名:%s\t作者:%s\t价格:%.2lf\t状态:%s\t借阅者%d\n",pb->id,pb->name,pb->author,pb->price,pb->state==0?"可借":(pb->state==1?"借
阅":(pb->state ==2?"预约":"借阅预约")),pb->lender);
56 printf("请操作:1-借阅书籍 2-预约书籍 3-归还书籍 4-返回");
57 int opt;
58 scanf("%d",&opt);
59 switch(opt){
60 case 1:
61 borrowBooks(pb,pr);
62 break;
63 case 2:
64 appBooks(pb,pr);
65 break;
66 case 3:
67 returnBooks(pb,pr);
68 case 4:
69 return pbook;
70 break;
71 default:
72 printf("illegal input!\n");
73 break;
74 }
75 }else{
76 printf("查无此书籍!\n");
77 }
78 return pbook;
79 }
80 void borrowBooks(Book *pb,Reader *pr){
81 if(pb->state == 1){//被借走
82 printf("这本书被借走了\n");
83 return;
84 }else if(pb->state == 2){//被预约
85 if(strcmp(pr->orderBook[0],pb->name) == 0 && pb->lender == 0){//1预约者与被预约的书一样才能借2这本书别人已经还了
86 printf("成功借走这本书\n");
87 pb->state = 1;//状态变为借走
88 pb->lender = pr->id;//把读者的id赋值给书的借阅者
89 strcpy(pr->borrowBook[0],pb->name);//把书名赋值给读者所借的书
90 pr->balance -= 10;//读者的金额减少10
91 strcpy(pr->orderBook[0],NULL);
92 }else{
93 printf("这本书被预约了，不能借走\n");
94 }
95 }else{
96 printf("成功借走\n");
97 pb->state = 1;//状态变成借走
98 pb->lender = pr->id;//把读者的id赋值给书的借阅者
99 strcpy(pr->borrowBook[0],pb->name);//把书名赋值给读者所借的书
100 pr->balance -= 10;//读者的金额减少10
101 return;
102 }
103 }
104
105 void returnBooks(Book *pb,Reader *pr){
106 printf("请输入要归还的书号\n");
107 int id = 0;
108 scanf("%d",&id);
109 int i = 0;
110 while(i < bcnt && pb->id != id){
111 i++;
112 pb++;
113 }
114 if(pb->id == id){
115 if(strcmp(pb->name,pr->borrowBook[0]) == 0){//借的书和书名一样
116 pb->state = 0;
117 pb->lender = 0;//书的使用者变为空
118 strcmp(pr->borrowBook[0],"NULL");//读者所借的书变为空
119 printf("还书成功\n");
120 }else{
121 printf("这本书你没有借，无法归还\n");
122 }
123 }else{
124 printf("没有这本书\n");
125 }
126 }
127 void appBooks(Book *pb,Reader *pr){//预约书籍
128 if(strcmp(pr->orderBook[0],"NULL") != 0){
129 printf("你已经有预约的书了,预约失败\n");
130 return;
131 }
132 if(pb->state == 0){//可借
133 pb->state = 2;
134 strcpy(pr->orderBook[0],pb->name);
135 pr->balance -= 2;
136 printf("你成功预约了这本书\n");
137 return;
138 }else if(pb->state == 1){//被借走
139 pb->state = 3;//被借走的书，被预约了
140 pr->balance -= 2;
141 printf("你成功预约了这本书，等别人还了你就能借啦\n");
142 return;
143 }else{//被预约了
144 printf("这本书别人预约了,预约失败\n");
145 return;
146 }
147 }
148
149 void balanceAdd(Reader *pr){
150 double money = 0;
151 printf("你当前的余额为%.2lf\n",pr->balance);
152 printf("请输入要充值的金额\n");
153 scanf("%lf",&money);
154 pr->balance += money;
155 printf("你充值后的余额为%.2lf\n",pr->balance);
156 }
157
158 void changePass(Reader *pr){
159 printf("请输入原来的密码\n");
160 char oldPass[NAME_LEN];
161 scanf("%s",oldPass);
162 if(strcmp(pr->pass,oldPass) == 0){
163 printf("请输入新密码");
164 scanf("%s",pr->pass);
165 }else{
166 printf("你输入的旧密码有错\n");
167 }
168 }