前言

这段时间,在准备有关软考和英语考试的材料,并且做了一些关于数据结构的资料。本次将通过有序链表来实现集合的基本操作。


结构定义

首先复习一些集合,哈哈哈。集合具有三种特性
. 确定性:给定一个集合,任给一个元素,该元素属于或者不属于该集合,二者必居其一,不能模棱两可。
. 互异性:集合内任何两个元素都认为是不同的,每个元素只能出现一次。有时需要对同一元素出现多次的情形进行刻画,可以使用多重集,其中的元素允许多次。
. 无序性:每个元素的地位都是相同的,元素之间是无序的。

1
2
3
4
5
6
7
8
9
10
typedef int DataType;   //为int变量取别名DataType

typedef struct node{ //集合节点的定义
DataType data; //每个成员的数据
struct node *next; //链接指针
}setNode;

typedef struct linkSet{ //集合的定义
setNode *first, *last;//表头和表尾的定义
};

查找算法

判断一个元素是否在集合内
. 存在则返回当前节点的地址
. 因为是有有序链,当前数据的值大于序查找的数据时或链表到达末尾,则返回NULL指针,表示未查询到
. 时间复杂度为O(n)

1
2
3
4
5
6
7
8
setNode *contains(linkSet &s, DataType x){
setNode *p = s.first->next;
while(p != NULL && p->data < x){
p = p -> next;
}
if(p != NULL && p->data == x) return p;
else return NULL;
}

插入算法

· 因为链表为有序链表,可根据成员大小来判断插入的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool addMember(linkSet &s, DataType x){
setNode *p, *pre;
p = s.first->next//s.first为头结点,s.first->next为第一个元素的地址
pre = s.first; //pre为p的前驱节点

while(p!=NULL ||p.data < x){
pre = p;
p = p -> next;
}
if(p != NULL && p.data == x) return false;//集合中以包含改元素
setNode *q = new setNode;
if(q == NULL) cerr <<"内存分配失败!"<<endl;
q -> data = x;
q -> next = p;
pre -> next = q;
}


删除算法

· 搜索需要删除的节点,如果没有找到,返回False,若搜索到则将pre直接指向p的后继节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool delMember(linkSet &s, DataType x){
setNode *p, *pre;
p = s.first->next;
pre = s.first;
while(p!=NULL && p->data < x){
pre = p;
p = p -> next;
}
if(p != NULL && p->data == x){
pre -> next = p -> next;
delte p;
return true;
}else{
return false;
}
}


并运算

· 并集运算求两个集合中的所有元素(不重复)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void Merge(linkSet &LA, linkSet &LB, linkSet &LC){//求集合的并集
setNode *pa = LA.first->next, *pb = LB.first->next, *pc = LC.first;
setNode *p;
while(pa != NULL && pb != NULL){
if(pa->data == pb->data){ //若两个集合中包含相同元素则,两者同时向后移动
pc->next = new setNode;
pc -> next -> data = pa->data;
pa = pa -> next;
pb = pb -> next;
}else if(pa->data < pb->data){ //若两个集合中的元素比较大小,若pa的数据小于pb的数据则
pc->next = new setNode; //将pa的数据插入pc,pa向后移动
pc -> next -> data = pa->data;
pa = pa -> next;
}else if(pa->data > pb->data){ //否则将pb的数据插入pc,pb向后移动
pc -> next = new setNode;
pc -> next -> data = pb -> data;
pb = pb -> next;
}
pc = pc->next;
}
p = (pa!=NULL) ? pa : pb; //可能存在集合的数据未取光,取出剩余的数据,继续进行炒作。
while(p!=NULL){
pc -> next = new setNode;
pc -> next -> data = p -> data;
p = p -> next;
pc = pc -> next;
}
pc -> next = NULL;
LC.last = pc;
}


交集运算

· 双重循环,遍历找出两个集合的公共数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void interSection(linkSet &LA, linkSet &LB, linkSet &LC){
setNode *pa = LA.first->next, *pb = LB.first->next, *pc = LC.first;
while(pa != NULL){ //双重循环遍历,时间复杂度为O(n^2)
setNode *tempP = pb;//临时节点用于遍历pb集合
while(tempP != NULL){
if(pa->data == tempP -> data){
pc -> next = new setNode;
pc -> next -> data = pa -> data;
pc = pc -> next;
break;
}
tempP = tempP -> next;
}
pa = pa -> next;
}
pc -> next = NULL;
}


感谢从这些博客和书籍中获得的帮助
《数据结构C语言描述》

留言

⬆︎TOP