MENU

链表数据集合的包含关系

• October 27, 2020 •

设带头结点的单链表seqlist1和seqlist2中分别存放着两个数据元素集合S1和S2,编写算法判断集合S1是否是集合S2的子集,即判断集合S1中的元素是否都是集合S2中的数据元素


题目分析:

要看是否含有某个元素,相当于查询。归根到底此题是要考察链表的查询,遍历seqlist1中的元素,若有元素不再seqlist2里面,则S1不是S2的子集,若都是S2的元素,则为S2的子集


考点:

**1.链表的遍历
2.链表的查询**

代码实现:

#include<stdio.h>
#include<stdlib.h>
typedef int dataType;    //数据类型为int
//结点结构体
typedef struct node
{
    dataType data;      //数据域
    struct node *next;  //指针域
}Node;
//初始化结点
void listInitiate(Node **head)            //双星指针,地址的地址,在初始化时,我们要使地址的值改变,所以使用双星作为参数传入
{
    *head = (Node*)malloc(sizeof(Node));  //为头结点分配位置空间(一个结点的大小)
    (*head)->next = NULL;                 //头结点指针域初始默认为空
}
/*尾插法建立单链表——得到的链表是顺序的
利用数组的前n个数建立一条单链表*/
void listBuildRear(Node *head, dataType arr[], int n)
{
    Node *p = head;                       //新增一个指针,用来代替head指针
    for (int i = 0; i < n; i++)              //循环n次,每次循环都在链表尾部追加一个结点
    {
        Node *q = (Node*)malloc(sizeof(Node));//新建立结点,并为之分配内存空间
        q->data = arr[i];                 //数据域赋值,将数组的第i+1个数字赋给新结点q
        q->next = NULL;                   //单链表最后一个结点的指针域都为空
        p->next = q;                      //将原始单链表最后一个结点指针域指向新结点q,从此q成为最后一个结点,原始最后一个结点变成倒数第二个结点
        p = q;                            //p又指向当前链表最后一个结点,为下一次尾部插入做准备
    }
}
//链表长度
int listLength(Node *head)
{
    int n = 0;
    while (head->next != NULL)
    {
        n++;
        head = head->next;
    }
    return n;
}
/*判断是否seqlist1、seqlist2具有包含关系
有则返回1,无则返回0 */
int listContainJudge(Node *head1,Node *head2)
{
    Node *h1 = head1, *h2 = head2;
    if(h1==NULL)                           //S1为空集,是S2的子集
        return 1;
    else if(listLength(h1)>listLength(h2)) //S1的元素个数比S2多,不是S2的子集
        return 0;
    else{
        int len = 0;                       //S1中包含在S2中的元素个数
        for (h1 = head1->next; h1 != NULL; h1 = h1->next)        //遍历seqlist1
            for (h2 = head2->next; h2 != NULL; h2 = h2->next)    //遍历seqlist2
                if (h1->data == h2->data)  //若seqlist1的当前结点在seqlist2中能匹配到相同结点
                {
                    len++;                 //S1中包含在S2中的元素个数
                    break;
                }
    h1 = head1;
    if (len == listLength(h1))                 //S1中包含在S2中的元素个数等于seqlist1的长度,说明数据全部包含在seqlist2中
        return 1;
    else
        return 0;
    }
}
//遍历输出函数
void listPrint(Node *head)
{
    printf("单链表:");
    Node *p = head;                       //新增一个指针,用来代替head指针
    while (p->next != NULL)
    {
        printf("%d   ", p->next->data);
        p = p->next;                      //这一句不要忘了,不然会死循环的,我总是忘掉这一句
    }
    printf("\n");
}
int main()
{
    Node link1,link2;
    Node *p1 = &link1,*p2 = &link2;
    //建立seqlist1
    int n,arr[50];
    listInitiate(&p1);
    listInitiate(&p2);
    printf("第一个链表的数据个数:");
    scanf("%d",&n);
    if(n!=0)
    {
        printf("请输入这些数:");
        for(int i = 0;i < n;i++)
        scanf("%d",&arr[i]);
    }
    listBuildRear(p1,arr,n);
    printf("第一条");
    listPrint(p1);
    //建立seqlist1
    printf("第二个链表的数据个数:");
    scanf("%d",&n);
    if(n!=0)
    {
        printf("请输入这些数:");
        for(int i = 0;i < n;i++)
        scanf("%d",&arr[i]);
    }
    listBuildRear(p2,arr,n);
    //判断是否有包含关系
    if(listContainJudge(p1,p2))
        printf("S1是S2的子集!\n");
    else
        printf("S1不是S2的子集!\n");
    return 0;
}

运行结果:


(1)S1是空


(2)S1是S2的子集


(3)S1的数据个数大于S2,S1不是S2的子集


(4)S1的数据个数小于S2,但S1不是S2的子集


</div>

代码编译器:Dev-C++
ok,结束

Archives QR Code Tip
QR Code for this page
Tipping QR Code