表的自然连接(数据结构链表链接)
我们先引入表的自然连接
知乎回答:
自然连接是在广义笛卡尔积R×S中选出同名属性上符合相等条件元组，再进行投影，去掉重复的同名属性，组成新的关系。自然连接是一种特殊的等值链接，它要求两个关系中进行比较的分量必须是相同的属性组，并且在结果中把重复的属性列去掉，所以根据T关系中的有序组可知R和S进行的是自然连接。我是这么通俗地想的这道题：你看R和S，两者第一行，都有个B，那么第一行可以很自然地接上，根据定义，把重复的B留一个就行；再第二行，两者共有一个1，也同理衔接；再看第三行，R与S二者无相同项，无法自然连接。最后连接在一起就是前两行的了。
作者：不错
链接：https://www.zhihu.com/question/317633206/answer/1707523986
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
按照我的理解:
自然连接：是一种特殊的等值连接，它要求两个关系进行比较的分量必须是相同的属性组，并且在结果集中将重复属性列去掉。
我们看一个问题:
●有表A , m1 行 , n1 列
●有表B , m2行 , n2 列
●求自然连接的结果
连接的条件 :表A 的第 i 列与 表 第 j 列相等
C = A ▷◁ B
i=j
例如 :
表A 的第1 列的元素,如果有元素和 表 B第 1 列的元素有重合的话,就把两个表 那一列的那一行 连起来,
例如: 2 1 2 2 1
2 1 2 2 4
1 1 2 1 2
5 2 1 5 3
这样就找到了两个表有共同属性的数据
我们现在举一个现实中的例子,
假如 A 是餐厅的顾客数据 , B是隔壁按摩店的顾客数据, 这两家时常会有顾客,一条龙服务, 吃完饭后,去按摩,
所以现在饭店老板就想收购这家按摩店 , 想来搞一个数据分析,调查同时去 A 和 B 的顾客的信息,然后再根据信息调查,
所以, 现在我们就要找的就是 同时去 A 餐厅和 去 B 按摩店的人
人们一次只吃一顿饭 , 所以 A 列表里没有重复的人名 ,而吃完饭去按摩店的人可以选择不同类型的服务 , 所以同一个人可以记录很多条不同的服务
现在我们找到A 和 B 的账本,如上图 ,所以我们要做得事情就是把两家共同的顾客的信息列出来
现在开始我们的人脑模拟 :
先去A的第一行的第一个节点 ,取得 3, 然后拿着3 ,去B账单每一行的第一个数据进行对比
遍历完发现 3 没有去过按摩店 , 那这个顾客就不记录了
然后再去A 的第二行的第一个节点, 取得顾客2 , 然后去遍历B账单的每一行第一个数据
发现顾客 2 有过两次服务 就记录两次
2 1 2 2 1
2 1 2 2 4
以此类推, 取到顾客 4 的名字, 然后去便利 B,发现没有就不记录
顾客1 ,然后去B遍历所有记录
1 1 2 1 2
顾客 5 ,再去遍历B记录
5 2 1 5 3
这样,我们记录的数据就是
2 1 2 2 1
2 1 2 2 4
1 1 2 1 2
5 2 1 5 3
用人脑模拟 , 这的确很快, 但是如果有很多按摩店的数据呢? 我们就需要利用计算机了, 我们的思路就是先取到 列表A 的第一行的第一个节点 ,然后拿着这一个节点去循环遍历 B 每行的第一个元素 ,
如果和B名字有重合的话, 就把顾客的 饭店数据和 按摩店数据 连起来 ,
那结束的条件是什么呢? 我们拿到 A中一个顾客的姓名, 然后去遍历 B的所有行的顾客姓名,
然后拿到A 的第二个顾客的名字, 再去遍历B的所有顾客姓名 ,
直到 A 遍历完为止 ,
有名字重合的话,就把饭店信息和按摩店信息连接起来 ,当成列表的一行
把信息全再传到列表里就可以了.
构造承载数据类型的列表:
我们首先想到的就是数组了,但是我们一行的几个数组成一个数组的话, 我们有很多行,如何链接起来呢?
那当然是用链表了 ,这样也方便插入每个顾客的信息了,
表 A 数据我们用 链表 h1 存储 ,表 B 数据我们用 h2存储 , 头结点是代表这个线性表有几行几列 , 每行的数据用数据存储, 然后再指引下一行就可以了
操作流程就是:
先构建链表节点的数据结构 ,然后构建头结点 ,构建两个链表 ,
然后遍历 h1 的第二个节点的第一个数,取到后,去遍历h2的每个节点的第一个数 , 如果和h1节点中的那个数,相等的话, 我们就把这两个节点的数据连接起来,存在数组里面,然后构建一个新节点,
形成 h 链表 ,这个 h 链表里面就是我们所需要的数据.
h里面存放的是我们所遍历B和 A ,以A为主,遍历 B中和 A有相同性质的数据 ,然后把数据联系起来.
我们这个找的是,名字相同的人,在两家,进行的服务的信息整理.
构造存储信息的节点的数据结构:
定义节点数据类型
typedef int ElemType;
定义数据节点的数据结构
typedef struct Node1 //定义存储数据的节点
{
ElemType data[MaxCol]; //定义存储数据的节点数组
struct Node1 *next; //定义节点的前驱指针
}DList;typedef struct Node2 //定义头结点结构类型
{
int Row,Col; //头结点数据存储列表行数和列数
DList *next; //头结点的后继指针
}HList;
创建数据链表
我们已经定义了,节点的数据结构类型,头结点定义列表的行列数, 后面的数据节点数组存储每行的数据,每个节点存储一行数据
下面,我们开始构建 创建如图链表的成员方法:
我们利用尾插法 , 插入节点,所以需要定义尾指针
传入要构建的链表地址指针
void CreateTable(HList *&h){
然后,需要创建头结点,先为头结点分配空间
h=(HList *)malloc(sizeof(HList)); //创建头结点这是我们刚才创建的头结点的类型 HList
接着,头结点置空
h->next=NULL;我们利用尾插法 , 插入节点,所以需要定义尾指针
DList *r;我们插入的新数据节点,也需要定义指针
DList *s;
下面开始构建数据链表
注意:头节点数据表示列表的行数和列数 ,后面节点的数据区里存放的是数组,每个数组里面存放按照列的排序的数据, 每行通过指针来链接
所以,我们对应的去修改头结点的数据就行了
printf("请输入要创建表的行数和列数");
scanf("%d%d",&h->Row,&h->Col);
接着遍历每一行的每一列的每一个元素,进行对应赋值就行了
for(int i=0; i<h->Row;i++) { printf("第%d行:",i+1); //物理地址加1,就是逻辑地址 s=(DLink *)malloc(sizeof(DList)); //每一行算一个节点,每一行的数据存放在数组里面 for(int j=0; j<h->Col; j++) { scanf("%d",&s->data[j]); //对节点数组进行按顺序赋值,一行的数据,按列正序输入 } //因为我们第一次插入,头结点h的后继指针是空,所以我们让头结点的后继指针指向新节点s if(h->next == NULL) { h->next=s; } else { r->next =s; } r=s; //这里分析一下,为什么不让指向尾结点的指针r,直接指向头结点呢?因为头结点和数据节 //点的数据结构不一样,我们定义的*r 是DList *r; //最后的时候,将尾结点置空就可以了 r->next =NULL; }
这样,我们构建两个数据链表的操作就完成了
接下来,就是遍历 h1 链表的每一个节点的数组的特定位置和 h2 的每一行的特定位置作对比了,
如果相等,那么就把这两个列表的那一行链接成一串,构成一个新节点
这样就把两个表 , 具有相同属性的数据链接存储起来了,
下面开始我们的代码实操:
我们首先传入创建好的链表 h1 ,链表 h2 ,和 需要创建的链表 h
void LinkTable(HList *h1,HList *h2,HList *&h){
注:我们现在是在成员方法里面, h1 和 h2 都是指针链表 ,已经创建好了,但是 h 链表还需要我们重新从头结点开始创建, 然后把符合我们上述属性的节点连接起来,当成数据节点就可以了.
我们需要首先指定需要把哪些相同属性的数据 , 通过遍历连接起来
表 A :我们需要遍历列表每行的第一个元素(姓名)
表B: 我们需要遍历列表每行的第一个元素(姓名)
映射到链表里面,就是每个节点的数组坐标
当然,我们也不局限于只链接这几列 , 可以指定 属性列,进行遍历链接,这是后话
通过输入属性的列表列序 ,来指定自然连接的位置
printf("连接字段是 : 第 1 个表位序 ,第二个表位序:");
int f1 , f2;
scanf("%d%d",&f1,&f2); //定义要链接的列
//创建头结点
h=(HList *)malloc(sizeof(HList));
//头结点的数据区,初始的时候还没有插入节点, 置为0
h->Row=0;
//头结点的列,如果存在的话,那就是两个链表的列相加
h->Col = h1->Col + h2->Col;
//头结点的后继节点置为空
h->next = NULL;
现在存储数据的链表有了,就可以进行遍历,链接节点,创建节点,插入链表了
先确定表 A 的第一个节点 ,然后遍历 B的每个节点的数组的第一个元素,
如果相等,就把A 和 B 这两行连接起来,组成链表 h 的新节点
我们先定义,遍历 A 和 B 的指针 *p 和 *q
DList *p;
DList *q;
p = h1->next; //p初始指向 h1 头结点的后继节点
while (p!=NULL)
{
q=h2->next; //初始的时候, q 指向 h2头结点的后继节点
while (q!=NULL) //当 h2的遍历节点不为空,就是没遍历到结尾的话
{
if (p->data[f1-1]==q->data[f2-1]) //如果找到相同属性的字段,就是对应字段值相等
{
s=(DList *)malloc(sizeof(DList)); //创建一个数据结点
for (i=0; i<h1->Col; i++) //复制表1的当前行
{s->data[i]=p->data[i]; //节点数据复制到新节点
}
for (i=0; i<h2->Col; i++)
{ s->data[h1->Col+i]=q->data[i]; //复制表2的当前行,数组的构建,按顺序构建
//h的节点数据已经赋值 ,下面把新节点用尾插法插入到头节点 h 后面就行了}
if (h->next==NULL) //插入第一个数据结点
{h->next=s;
}
else //插入其他数据结点
{r->next=s; //为什么不让 r直接指向头结点,然后就少一步呢,因为r和头结 } // 点的数据结构类型不一样
r=s; //r始终指向最后数据结点
h->Row++; //表行数增1
}
q=q->next; //表2下移一个记录
}
p=p->next; //表1下移一个记录,先内层循环,然后 外层循环
}
r->next=NULL; //表尾结点next域置空
}
这样,我们就可以构建一个 h 链表把我们所需要数据都存在里面了
下面怎么输出呢? 这不是很简单吗?
遍历输出一下就行了,先遍历节点,节点内部套一个 while循环遍历数组
void DispTable(HList *h) //传入要输出的链表
{
int j;
DList *p=h->next; //遍历输出的节点,初始的情况下,就是头结点的后继节点,头结点不用输出
while (p!=NULL) //循环遍历节点
{
for (j=0; j<h->Col; j++) //我们传入了 h ,就知道了 h的属性 Col
printf("%4d",p->data[j]); //输出节点数组的元素
printf("\n"); //为了美观换行
p=p->next; //指向下一个节点,直到为空节点
}
}
接下来,当然是主函数调用了:
int main()
{
HList *h1,*h2,*h;
printf("表1:\n");
CreateTable(h1); //创建表1
printf("表2:\n");
CreateTable(h2); //创建表2
LinkTable(h1,h2,h); //连接两个表
printf("连接结果表:\n");
DispTable(h); //输出连接结果
return 0;
}
完整代码如下:
#include <stdio.h>
#include <malloc.h>
#define MaxCol 10 //最大列数
typedef int ElemType;
typedef struct Node1 //定义数据结点类型
{
ElemType data[MaxCol];
struct Node1 *next; //指向后继数据结点
} DList;
typedef struct Node2 //定义头结点类型
{
int Row,Col; //行数和列数
DList *next; //指向第一个数据结点
} HList;
void CreateTable(HList *&h)
{
int i,j;
DList *r,*s;
h=(HList *)malloc(sizeof(HList)); //创建头结点
h->next=NULL;
printf("表的行数,列数:");
scanf("%d%d",&h->Row,&h->Col);
for (i=0; i<h->Row; i++)
{
printf(" 第%d行:",i+1);
s=(DList *)malloc(sizeof(DList)); //创建数据结点
for (j=0; j<h->Col; j++) //输入一行的数据初步统计
scanf("%d",&s->data[j]);
if (h->next==NULL) //插入第一个数据结点
h->next=s;
else //插入其他数据结点
r->next=s; //将*s插入到*r结点之后
r=s; //r始终指向最后一个数据结点
}
r->next=NULL; //表尾结点next域置空
}
void DispTable(HList *h)
{
int j;
DList *p=h->next;
while (p!=NULL)
{
for (j=0; j<h->Col; j++)
printf("%4d",p->data[j]);
printf("\n");
p=p->next;
}
}
void LinkTable(HList *h1,HList *h2,HList *&h)
{
int f1,f2,i;
DList *p=h1->next,*q,*s,*r;
printf("连接字段是:第1个表位序,第2个表位序:");
scanf("%d%d",&f1,&f2);
h=(HList *)malloc(sizeof(HList));
h->Row=0;
h->Col=h1->Col+h2->Col;
h->next=NULL;
while (p!=NULL)
{
q=h2->next;
while (q!=NULL)
{
if (p->data[f1-1]==q->data[f2-1]) //对应字段值相等
{
s=(DList *)malloc(sizeof(DList)); //创建一个数据结点
for (i=0; i<h1->Col; i++) //复制表1的当前行
s->data[i]=p->data[i];
for (i=0; i<h2->Col; i++)
s->data[h1->Col+i]=q->data[i]; //复制表2的当前行
if (h->next==NULL) //插入第一个数据结点
h->next=s;
else //插入其他数据结点
r->next=s;
r=s; //r始终指向最后数据结点
h->Row++; //表行数增1
}
q=q->next; //表2下移一个记录
}
p=p->next; //表1下移一个记录
}
r->next=NULL; //表尾结点next域置空
}
int main()
{
HList *h1,*h2,*h;
printf("表1:\n");
CreateTable(h1); //创建表1
printf("表2:\n");
CreateTable(h2); //创建表2
LinkTable(h1,h2,h); //连接两个表
printf("连接结果表:\n");
DispTable(h); //输出连接结果
return 0;
}