当前位置： 首页 > news >正文

数据结构与算法基础（王卓）（8）：线性表的应用（并集和有序表合并）

news 来源：原创 2024/11/17 13:21:21

PPT：第二章P173；

并集集合：线性表的合并（无需有序，不能重复）

线性表：

Status Union(Sqlist& A, Sqlist& B)//并集
{
    int len_A = A.length;
    int len_B = B.length;
    for (int i = 1; i <= len_B; i++)
    {
        Poly e=*A.elem;
        //这里只是给我们设定的元素e赋一个任意初值
        //只要保证e在初始化时由初值不为空即可
        //至于该e元素的内容是什么其实并没有什么所谓
        //因为后面我们总归是会改的
        GetElem(B, i, e);
        if (LocateElem(A, e))
            return ERROR;
        else
            ListInsert(A, ++len_A, e);
        //注意插入函数中输入的是位序，不是数组下标
    }
    return true;
}

该算法的时间复杂度：O(ListLenth(La) * ListLengrh(Lb))

最后A表为合并以后的新表

链表：

Status Union(Lnode& A, Lnode& B)
{
    for (int i = 1; i <= 求表长(&B); i++)
    {
        int len_A = 求表长(&A);
        Elemtype e;
        取第i个元素(&A, i, e);
        if (!LocateELem(&B, e))
            Listlnsert(&A, ++len_A, e);
    }
    return true;
}

结果：（默认在（7）：小结：关于链表和线性表的定义及操作当中预设的前置语句之下运行） 

而产生该结果的原因，和前置语句中，定义插入函数的语句有关：

Status Listlnsert(LinkList& L, int i, Elemtype e)

更准确的来说：问题源于我们给出的 “&A”和定义中的“LinkList& L”类型匹配不上

想要程序能够正常运行，改动的方法有两种：

1：

修改<插入>函数的函数体：（此时<合并>函数无需修改）

把合并函数的“声明”（函数体之外）部分改为：

Status Listlnsert(LinkList L, int i, Elemtype e)

此时，该合并函数所需要的前置条件（最简单版本）为：

//链表的定义及其基础操作
#include<iostream>
using namespace std;
#include<stdlib.h>//存放exit

#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE  -1
#define OVERFLOW   -2   

#define MAXlength 100  //初始大小为100，可按需修改

typedef int Status;         //函数调用状态

struct K
{
    float a;
    int b;
    string c;
    bool operator==(K& t)
    {
        return t.a == a && t.b == b;
        //&& t.c = c;
    }
    bool operator!=(K& t)
    {
        return t.a != a || t.b != b;
        //|| t.c = c;
    }
};
typedef K Elemtype;         //函数调用状态

struct Lnode
    //node:结; 结点;
{
    Elemtype data;
    Lnode* next;
};
typedef Lnode* LinkList;

Status 链表是否为空(LinkList L)
{
    if (L->next)
        return true;
    else
        return false;
}
Status 求表长(LinkList L)
{
    if (链表是否为空(L))
        cerr << "链表为空" << endl;
    LinkList p = L->next;
    //特别注意：因为这里从首元结点开始算起（计算）
    //所以：L->next;
    int i = 0;
    while (p)//不要写成if
    {
        p = p->next;
        i++;
    }
    //cout << "表长为：  " << i << endl;
    return i;
}

Status 取第i个元素(LinkList L, int i, Elemtype e)
{// GetElem“i”
    LinkList p;
    p = L->next;
    int j = 1;
    while (p && i > j)
    {
        p = p->next;
        j++;
    }
    if (i < 0 || i < j || !p)
        return false;
    e = p->data;
    return true;
}

Status LocateELem(LinkList L, Elemtype e)
{
    //在线性表L中查找值为e的数据元素
    //找到，则返回L中值为e的数据元素的地址，查找失败返回NULL
    auto p = L->next; int i = 1;
    while (p && p->data != e)
    {
        i++;
        if (e == p->data)
        {
            cout << "地址为：  " << p << ";" << endl;
            cout << "位置序号为：  " << i << ";" << endl;
        }
        p = p->next;
    }
    if (p == NULL)
        return NULL;
    return true;
}

Status Listlnsert(LinkList L, int i, Elemtype e)
{//插入（把元素e插到第i个位置结点上）
    auto p = L; int j = 0;
    while (p && j < i - 1)
    {
        p = p->next; ++j;
    }
    if (!p || j > i - 1)
        return false;
    auto s = new Lnode;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}//Listlnsert_L

2：
修改<合并>函数的函数体：（在前置语句保持不变，不必改动的情况下）

Status Union(Lnode& A, Lnode& B)
{
    for (int i = 1; i <= 求表长(&B); i++)
    {
        int len_A = 求表长(&A);
        Elemtype e;
        LinkList p = &A;
        取第i个元素(&A, i, e);
        if (!LocateELem(&B, e))
            Listlnsert(p, ++len_A, e);
    }
    return true;
}

那么此时，一个让我觉得很有意思（很奇怪）的现象（情况）就发生了

问题：

为什么在前面“&A”和定义中的“LinkList& L”类型匹配不上

但是只要我们把“&A”放到一个新的该类型的变量当中，让该信息以变量的形式在程序中执行

放进去的明明都是同一个东西（&A），凭什么（怎么）原来的时候程序就可以运行了呢？？？

合并为一个新的整体：有序表的合并（有序，可重复）

线性表：

对于该操作的具体实现的流程设计：（各模块）

  1. 创建一个空表C

  2. 依次从A或B(中）“摘取”元素值较小的结点插入到C表的最后，直至其

    中一表变空

  3. 继续将A或B其中一表的剩余结点插入C表的最后

模块一：

对于这里的模块一，我们需要进行的：

建一个新表来返回两表合并后的结果（最终合并后的表）的操作的整个学习过程与问题，详见：

数据结构与算法基础（王卓）（8）附：关于new的使用方法详解part 2；

而在本程序中，我们使用的语句，即：

    C.elem = new Elemtype[100];

模块二：

其中，模块二的流程实现，又具体细分为：

  1.  摘取两表中元素值较小的结点
  2. 将结点插入到C表的结尾
  3. 重复循环“1”、“2”步操作，直至其中一表变为空为止

project1：

    //不用指针，直接硬钢判断语句
    int i = 0,//对应A表
        j = 0,//对应B表
        k = 0;//对应C表
    while (i < A.length || j < B.length)
    {
        if (A.elem[i] > B.elem[j])
        {
            C.elem[k] = B.elem[i];
            i++;
            k++;
        }

        if (A.elem[i] == B.elem[j])
        {
            C.elem[k] = A.elem[i];
            C.elem[++k] = B.elem[j];
            i++;
            j++;
            k++;
        }

        else//        if (A.elem[i] < B.elem[j])

        {
            C.elem[k] = A.elem[i];
            i++;
            k++;
        }
//当然，也可以先大于小于再等于

说明：

（1）：

在模块二中，两表相比较的两结点元素值都相等的语句，也可以写为：

        if (A.elem[i] == B.elem[j])
        {
            C.elem[k] = A.elem[i];
            C.elem[++k] = B.elem[j];
            i++;
            j++;
            k++;
        }

（2）：

需要注意（记住），本来（一开始），对于循环执行（的）判断语句，我们本来想写为

    while(A.elem[i] != 0 || B.elem[j] != 0)

然而，结果显示：

首先，第一点确定无疑的事情（结论）就是：

在这里，我们的程序不能完成该语句中的“！=”判断

在这里，想要程序能够成功实现执行该判断，我们可以有如下两种解决办法：

  • 手撸一个关于<Poly类型> != <int类型>的判断定义表达式
  • 定义结点为空时，该空节点的内容；即：定义一个这样的空结点

当然，要真这么写，可以是也可以，但是太过麻烦，我们这里就不选择这种方法了

project 2：（利用线性表地址线性排列存储的性质）

    //利用指针
    Poly* pa, * pb, * pc;
    pa = A.elem;
    pb = B.elem;
    pc = C.elem;

    //*pa = A.elem[0];
    //*pb = B.elem[0];

    while (pa <= &A.elem[A.length - 1] || pb < &B.elem[B.length - 1])
    {
        if (*pa > *pb)
        {
            *pc = *pb;
            pa++;
            pc++;
        }

        if (*pa == *pb)
        {
            *pc = *pa;
            *(++pc) = *pb;
            pa++;
            pb++;
            pc++;
        }

        else
        {
            *pc = *pa;
            pa++;
            pc++;
        }

模块三：

    if (A.length > B.length)
    {
        //while (i < A.length)  同理,后面不再赘述
        while (pa <= &A.elem[A.length - 1])    
        {
            *pc = *pa;
            pc++;
            pa++;
        }
    }
    else
    {
        while (pb <= &B.elem[B.length - 1])
        {
            *pc = *pb;
            pc++;
            pb++;
        }
    }

最终修改打磨：

根据（参考）PPT（178）中的标准答案，我们发现以下地方仍有修改的空间：

模块一:

一方面：

我们没有给新建的C表的length元素赋值

另一方面：

C表的长度是A表和B表两表长度的总和

如果还是只是固定的，像开辟和A表B表一样的固定为100的大小的空间，未免有些不妥：

  C.length = A.length + B.length; 
  C.elem = new Elemtype[C.length];

另外，模块二这里我们写的限定条件：

    while (pa <= &A.elem[A.length - 1] || pb < &B.elem[B.length - 1])

写成：

    while (pa <= A.elem + A.length - 1 || pb < B.elem + B.length - 1)

也同理（一样）；（标准答案就是按后者这么写的，但我感觉这么写倒也没有什么特别过人之处）

但是另一个问题就严重了：

在C++中：

与：&&

或：||

非：！

所以应该改为：

    while (pa <= A.elem + A.length - 1 && pb < B.elem + B.length - 1)

 或者：

    while (pa <= &A.elem[A.length - 1] && pb < &B.elem[B.length - 1])

另外：

在模块二中关于这个循环的循环体，我写的倒是也没有什么大的错误

但是太过累赘，还是标准答案上写的更加简洁和方便

当然他其实没有我写的那么严谨：具体写出两节点元素值相等时的操作流程，可以让循环次数减少

但是从大的时间复杂度的角度来说，其实n次循环和（n-5）次循环本质上没有太大区别

所以这里我们还是选择标准答案上的写法：

    while (pa <= &A.elem[A.length - 1] && pb < &B.elem[B.length - 1])
    {
        if (*pa < *pb)
            *pc++ = *pa++;
        else
            *pc++ = *pb++;
    }

该写法，即：

先（给C表中最后的结点（*pc））赋值，再自增；一个语句实现

最后，关于模块三：

其实我们不用在去设置看A和B哪个表更长的判断语句

因为其实我们即使直接写两个循环语句，依然不影响程序的运行

因为一个表的指针已经到达该表的尾结点以后，自然就不符合该循环的循环判断条件：

        while (pa <= &A.elem[A.length - 1])    
和
        while (pb <= &B.elem[B.length - 1])

了，另外，这里的函数体，我们也可以写为像上面一样的“先（给C表中最后的结点（*pc））赋值，再自增；”的形式：

        while (pa <= &A.elem[A.length - 1])    
        {
            *pc++ = *pa++;
        }
        while (pb <= &B.elem[B.length - 1])
        {
            *pc++ = *pb++;
        }

综上：

关于线性表的：有序表的合并（有序，可重复）操作如下：

int Merge(Sqlist A, Sqlist B, Sqlist& C)
{//合并; 融入; (使)结合; 并入; 相融;

    typedef Poly Elemtype;

    C.length = A.length + B.length;
    C.elem = new Elemtype[C.length];

    //利用指针
    Poly* pa, * pb, * pc;
    pa = A.elem;
    pb = B.elem;
    pc = C.elem;
    //*pa = A.elem[0];
    //*pb = B.elem[0];

    while (pa <= &A.elem[A.length - 1] && pb < &B.elem[B.length - 1])
    {
        if (*pa < *pb)
            *pc++ = *pa++;
        else
            *pc++ = *pb++;
    }
    //
    while (pa <= &A.elem[A.length - 1])
    {
        *pc++ = *pa++;
    }
    while (pb <= &B.elem[B.length - 1])
    {
        *pc++ = *pb++;
    }
    //
    return true;
}

链表：

相关文章：

  • 汕尾做网站/日本域名注册网站
  • 北京网站开发软件/全网营销国际系统
  • 用户上传网站用什么做/百度免费
  • 高端的佛山网站建设/制作网站的工具
  • 官方网站的推广策划怎么做/nba最新交易动态
  • 做推广的网站/个人在线做网站免费
  • 【java】java多线程及线程池面试题
  • SAP MM 物料分类账的启用配置
  • 搭建wordpress
  • CSDN网站勋章获取介绍
  • SAP MM 新建移动类型（Movement Type）
  • 大数据技术架构(组件)——Hive：环境准备1
  • freemarker包含字符串操作
  • leetcode 1813. 句子相似性 III【python3双指针的实现思路及过程整理】
  • Android启动流程源码分析(基于Android S)
  • Spring Cloud Gateway（黑马springcloud笔记）
  • 【ROS】—— 机器人导航(仿真)—导航实现(十八)[重要][重要][重要]
  • JAVA会员营销系统源码+数据库，实体店铺会员管理和营销系统源码，采用SpringBoot + Mysql+Mybatis