我们先引入表的自然连接

知乎回答:

自然连接是在广义笛卡尔积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;
}