数据结构实验--带环、相交链表问题_输入数据元素构造单链表后,将元素值为 m 和 n(从键盘输入,如有多个相同元素值, 仅

一、问题描述：

基于课程上机关于单链表的作业，要求进一步实现以下需求:

• 1.构造链表后，将元素值为 m 和 n（从键盘输入，如有多个相同元素值，仅考虑首个出现的元素）的节点建立连接，注意判断节点出现的先后关系，将后面出现的节点（假设为 n）的链域连到先出现的节点（假设为 m），将原 n 节点的后续节点搬迁到原单链表的头部，形成以下双头相交链表（如果使用带头结点的链表，搬迁过程中请自行额外增加一个头节点）；
  

• 2.利用课程 ppt 中关于判断链表是否有环的方法，判断链表是否有环路，并求出环路出现的
  位置，即 m，n 节点的指针，请使用环路判断函数（输入为链表头指针），不可直接查找 m,n，
  支持使用 2 个不同的链表头部指针进行查询；

• 3.将环路链接取消，恢复成单链表，并根据表头指针（输入）求解链表的中间节点（输出中
  间节点的值并返回指针），注意：不要将链表转换成数组来求解；

• 4.编写函数，判断两个链表是否相交，函数输入为双头相交链表的两个头指针并输出相交的
  指针，如没有相交则返回 NULL。
  注意：判断相交是基于指针的比较（判断是否有相同的节点指针出现在两个链表中）而不是节点的值的比较。

二、需求分析：

首先要设计生成一个直链，然后考虑如何将其连接成符合题意的双头相交链表，设计判断环路的方法能够判断所给的链表是否有环并且返回环的入口，封装成函数供其他函数调用，最后就是判断链表相交，不应局限于题目所给条件而要充分考虑两链表相交的各种情况。

三、概要设计：

首先构建一个单链表，然后根据用户输入的m，n值依照题目要求的方式，构造符合要求的双头相交链表，并能够还原成原来的单链表。设计函数判断一个链表是否有环。编写函数判断给定的两个链表是否相交。

1、数据结构定义：

程序涉及到一个链表的储存，且涉及到的操作不多，故采用结构体的方式定义：

typedef struct LinkList
{   int Data=-999;
    LinkList* next=NULL;
}LinkList;//定义“链表”结构体，用于表示链表及相关节点
LinkList* CCListHead = new LinkList;//开始构建的单链表的头节点
LinkList* CCListHead2 = NULL;//对单链表处理过后的第二个头节点
1
2
3
4
5
6

2、模块设计：

1）main：显示菜单，并根据用户的选择做出判断，在其中调用其他函数完成功能
2）MakeLinklist()：以上述已定义的头节点为头构建一个长为100的数值为随机数的单链表。
3）连接成环function1():将上述已经建立好的单链表依据要求连接成双头相交链表。
4）判断环路function2():利用快慢指针法，以判断上述节点为头的链表是否有环，并返回环的入口
5）取消环，并输出中间节点function3():用连接环时的相反的操作把环路取消，并根据输入的头节点输出对应的中间节点。
6）判断相交function4():判断已有的两个头节点所指示的链表是否相交。

3、各模块间的调用关系：

四、详细设计

主要算法设计：

1）直链的构建：

先构建一个没有重复数字的随机数数组

for (int i = 0; i <150 ; i++) {
        int Same = 1;
        A[i] = rand() / (double)RAND_MAX * (200);
        while (Same) {//直到没有重复数字才结束循环
            Same = 0;
            for (int j = 0; j < i; j++) {
                if (A[i] == A[j]) {
                    Same = 1;//表示有重复数字，需要重新生成随机数
                    A[i] = rand() / (double)RAND_MAX * (200);
                    break;
                }
            }
        }       
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

然后利用此数组中的各元素的值来构建链表

while(1)
    {
        Current->Data = A[i++];
        //Current->Data = i++;
        if (i == 100)break;
        Current->next = new LinkList;
        Current = Current->next;
    }
1
2
3
4
5
6
7
8

2）判断环路：利用快慢指针法判断环路

原理：设置一个快指针fast每次走两步即Fast = Fast->next->next;//快指针走两步，设置一个慢指针slow每次走一步即 Slow = Slow->next;//慢指针走一步；初始状态 两个指针都从头开始走，如果有环的话则由于两指针有速度差，则必定会在环中某点相遇，反之在Fast走到尾部之前，两指针都不会相遇，以此来判断给定的头指针所指示的链表是否有环。

LinkList* function2(LinkList* Head) {
    LinkList* Slow = Head;
    LinkList* Fast = Head;
    int isLoop = 0;
    while (Slow->next != NULL && Fast->next->next != NULL) 
    {
        Slow = Slow->next;//慢指针走一步
        Fast = Fast->next->next;//快指针走两步
        if (Slow == Fast) {//快慢相遇
            isLoop = 1;///则有环
            break;
        }
        if(Fast->next==NULL)//快指针到尾 则结束
            return NULL;
    }
    if (isLoop) {//有环的话 就判断环的入口
        Slow = Head;
        while (Slow != Fast) {
            Slow = Slow->next;
            Fast = Fast->next;
        }
        return Slow;
    }
    return NULL;
}
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

如果有环路，判断环入口的方法：第一次相遇点到入口的距离=头指针到连接点入口的距离，因此，分别从第一次相遇点、头指针head开始走，再次相遇的那个点就是连接点。

3）连接成环：将单链表按要求转化为双交头链表。

首先判断是否已经是双头相交链表，若是则返回错误提示信息，若不是则可以在给出的链表的100个数值里面挑选两个作为m n，自动判断先出现的为m，并按照题目所给的方法连接m、n得到要求的双头相交链表，并将新得到的链表头记为Head2.

步骤：

• 先找到用户输入的m，n值对应的链表节点，小编号节点的指针记为MM大编号记为NN。
• 然后对链表进行再次连接：NN后面的节点用Head2 指示，链表尾部节点由空改为指向MM，NN后继指向MM。即完成了对链表的再次连接

 CCListHead2 = NN->next;
    Tail->next = MM;
    NN->next = MM;
1
2
3

4）取消环并输出中间节点:

先判断头指针是否为空，有一个为空则无法恢复。
要恢复成单链表只需要找到四个位置：m的位置，n的位置，原链表尾的位置，原n后继的位置。
方法：m的位置只需要调用2即可返回入口即m的位置，n用Current指针遍历链表，并设置PreCurrent保存Current的前驱节点，当Current第二次经过m时的PreCurrent即为n的位置（因为第一次不在环中），原链表尾类似的方法遍历Head2（连接链表后制造出的头节点）第一次到m时对应的PreCurrent即为原链表尾记为tail，易判断Head2即为原n的后继。
判断完上述位置后，只需将n的后继改为Head2 指示的节点并让tail指向空即可。

if (CCListHead == NULL || CCListHead2 == NULL) {
        cout << "*****当前无法恢复成单链*****"<<endl;
        return ;
    }

    LinkList* Tail = NULL;
    LinkList* NN = NULL;

    LinkList* MM = function2(CCListHead);
    LinkList* Current = CCListHead2;
    LinkList* PreCurrent = new  LinkList;
    PreCurrent->next = Current;

    for (Current = CCListHead2; Current != MM; ) {
          PreCurrent = PreCurrent->next;
        Current = Current->next;
    }
    Tail = PreCurrent;

    Current = CCListHead;
    PreCurrent = new  LinkList;
    PreCurrent->next = CCListHead;

    int time = 0;//第几次到达MM
    while(time != 4)
    {
        PreCurrent = PreCurrent->next;
        Current = Current->next;
        if(Current == MM) time++;
    }
    NN = PreCurrent;
    NN->next = CCListHead2;
      
  
    CCListHead2 = NULL;
      Tail->next = NULL;
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
31
32
33
34
35
36

根据表头指针（输入）求解链表的中间节点：
读入用户输入的起点和终点后，遍历链表，遇到数据等于其中之一就开始输出节点的值，直到遇到用户输入的另外一个为止。

	int m, n;
    cout << "\n*****请输入要输出中间节点的范围 m，n*****" << endl;
    cin >> m >> n;

    int i = 0, MLoc = -1, NLoc = -1;
    for (Current = CCListHead; Current != NULL; Current = Current->next)
    {
        if (Current->Data == m) 
            MLoc = i;
        if (Current->Data == n) 
            NLoc = i;
        
        i++;
    }
    if (MLoc == -1 || NLoc == -1) {
        cout << "*****没有对应的两个节点******";
        return;
    }

    int start = 0;
    for (i = 0, Current = CCListHead; Current != NULL; Current = Current->next,i++) {
        if (i == min(MLoc, NLoc))start = 1;
        if (start) cout << Current->Data << "--";
        if (i == max(MLoc, NLoc))start = 0;
    }
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

5）判断相交:此问题分三种情况讨论，即：两直链、两环、环+直链。

情况如图所示：

首先，判断链表是否有环的方法已经在2给出，直接调用即可。

• 两直链：判断两直链是否相交只需判断两直链尾指针是否一样即可，一样则说明两直链在尾部之前有相交。
• 两环：两环相交在公共环的部分可能有一个或者两个入口，不管有几个，首先利用2给出的方法判断A链表环的入口，然后在B中遍历，判断A的入口是否在其中（注意带环链表的遍历，结束条件应该为第二次经过环入口），在的话则相交，进一步可以判断有一个还是两个入口。
• 环+直链：此情况直接可判断为无相交。

 LinkList* Ahead=CCListHead;
    LinkList* Bhead=CCListHead2;
    LinkList* xx = function2(Ahead);
    LinkList* yy = function2(Bhead);

    LinkList* Current，PreCurrent;
    LinkList* AA，BB;

    if (xx==NULL&&yy==NULL) {
        //两个直链
        PreCurrent = new  LinkList;
        PreCurrent->next = Ahead;
        for (Current = Ahead; Current != NULL; ) {
            PreCurrent = PreCurrent->next;
            Current = Current->next;
        }
        AA = PreCurrent;
        PreCurrent = new  LinkList;
        PreCurrent->next = Bhead;
        for (Current = Bhead; Current != NULL; ) {
            PreCurrent = PreCurrent->next;
            Current = Current->next;
        }
        BB = PreCurrent;

        if(AA==BB){
            cout << "*****直链+直链，相交！！！*****";
        }
        else {
            cout << "*****直链+直链，不相交！！！*****";
            return NULL;
        }
    }
    else if (xx != NULL && yy != NULL) {
        //两个环
        LinkList* EntranceA;
        EntranceA= function2(Ahead);
        LinkList* EntranceB;
        EntranceB = function2(Ahead);

        int time = 0;//第几次到达MM
        int Jiao = 0;
        Current = Ahead;
        while (time != 4)
        {
            Current = Current->next;
            if (Current == EntranceA) time++;
            if (Current == EntranceB) {
                cout << "*****环+环，相交！！！*****";
                Jiao = 1;
                break;
            }
        }
        if(!Jiao)cout << "*****环+环，不相交！！！*****";
        return NULL;

    }
    else {
        cout << "*****直链+环，不相交！！！*****";
        return NULL;
    }
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

以上就是本程序的核心代码部分

五、用户手册：

打开程序后，程序出现菜单，选择你需要的功能，输入对应的序号按下回车即可，当选择功能一即连接成环时，程序会展示出预先生成的链表中的所有一百个值，选择两个值输入，系统自动判断先出现的为M反之为N，并连接成题目要求的链表，随后展示出连接的情况。当选择功能三时，如果已经存在相交链表则将其恢复成初始状态，随后展示出预先生成的链表中的所有一百个值，选择两个值输入后，程序会输出由用户输入的两个值对应节点的中间所有节点的值。其他功能类似，可反复使用。

六、调试报告：

测试过程中出现了以下几个问题：
恢复成直链失败：
尝试使用恢复成直链后，再次输出的链表与原链表不同，表明未正确恢复，于是将链表中的数据全部换成连续的一到一百，然后再次尝试就很容易发现出错的位置，分析后发现是N的位置找的不对，考虑到采用遍历的方法判断当前指针到达M则其后继即为N，但这是在环中的情况，在此之前还要经历在前半段直链的情况，所以用这种方法每次找到的都是在直链部分M的前驱而不是N。修改方法：用一个统计遍历次数的变量time初始化为零，每次当前指针遍历到M 时time就加一，这样只要time不是零，在当前指针遍历到M的时候其前驱就是N，修改过后程序即可输出预期的结果。
又尝试了以下改进：
对链表的相交情况进行可视化，即输出连接后的双头相交链表，具体采取的方法：
依次输出Head1到M，M到N，Head2到M即可表示出相交后的链表的具体情况，分析后发现与预期完全吻合。

八、测试结果：

测试结果如下：

图 1连接成环

图 2判断环路

图 3判断相交

图 4转化成直链并输出中间节点

图 5未连接状态下判断环

图 6 改进后的界面（输出链表的相交情况）