[项目006] 链表的综合应用与案例分析 隐藏答案 | 返回首页

作者：欧新宇（Xinyu OU）
当前版本：Release v1.0
开发平台：gcc 13.1.0, g++ 13.1.0, gdb 13.2
运行环境：Intel Core i7-13700KF CPU 3.4GHz, 32GB RAM
本教案所涉及的数据及代码仅用于教学和交流使用，请勿用作商用。

最后更新：2023年9月15日

---

作业要求：将【课后作业】的题目及程序代码整理成实验报告，并以PDF格式，或直接拍照上传到【雨课堂】（不要使用word文档进行上传）。

【课后作业】

‍1. 在带头结点的单链表L中，删除所有值为x的结点，并释放其空间，假设值为x的结点不唯一，试编写算法以实现上述操作。

算法提示：
1.定义两个指针p和pre，分别指向工作结点和该节点直接前驱；
2.逐元素扫描链表，当p所指结点的值等于x时，删除该节点，并让p向后移至下一结点；
3.若未找到值为x的结点，则将p和pre同时向后移动一个结点。

void DeleteX(LinkList &L, ElemType x){
    // 在此处填入代码
}

【参考代码】

void DeleteX(LinkList &L, ElemType x){
    LNode *p = L->next, *pre = L, *q;    // 1. 定于三个指针，分别是工作指针p，直接前驱指针pre和待删除结点指针q
    while(p != Null){                    // 2. 遍历整个链表，并让每个结点都和待删除结点进行比较
        if(p->data == x){                // 3. 若p指向的结点的值等于x，则删除该结点
            q = p;                       // 3.1 令q指向待删除结点
            p = p->next;                 // 3.2 令p指向pre的直接后继
            pre->next = p;               // 3.3 令pre指向p的直接后继
            free(q);                     // 3.4 释放q指向的结点
        }
        else{                            // 4. 若p指向的结点的值不等于x，则pre和p同时向后移动一个结点
            pre = p;                     // 4.1 令pre指向p
            p = p->next;                 // 4.2 令p指向p的直接后继
        }
    }
}

2.有两个循环单链表，链表头指针分别为 h1 和 h2，编写一个函数将链表 h2 连接到链表 h1 之后，要求链接后的链表仍保持循环链表形式。

算法提示：

1. 找到这两个循环链表的尾指针r1和r2；
2. 将第一个链表的尾指针与第二个链表的首元结点相连；同时，将第二个链表的尾指针也与第一个链表的头结点相连。

LinkList Link_TwoLinkList(LinkList &h1, LinkList &h2){
    // 在此处填入代码
}

【参考代码】

LinkList Link_TwoLinkList(LinkList &h1, LinkList &h2){
    LNode *r1, *r2;            // 1. 定义两个尾指针r1和r2，分别用于标识h1和h2的尾结点
    r1 = h1->next;             // 2. 通过遍历链表h1，寻找h1的尾结点
    while(r1->next != h1){     
        r1 = r1->next;         
    r2 = h2->next;             // 3. 通过遍历链表h2，寻找h2的尾结点
    while(r2->next != h2){     
        r2 = r2->next;         
    r1->next = h2;             // 4. 将链表h1的尾结点与链表h2的头结点相连
    r2->next = h1;             // 4. 将链表h2的尾结点与链表h1的头结点相连
    return h1;                 // 5. 返回h1
}

3. 【2009年统考真题】已知一个带有表头结点的单链表，结点结构为[data|link]。假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成果，算法输出该节点的data域的值，并返回1；否则，只返回0。要求：
1). 描述算法的基本设计思想
2). 描述算法的详细实现步骤
3). 根据设计思想和实现步骤，采用程序设计语言C/C++描述算法，关键之处请给出简要注释。

算法提示：
1.本题的关键是设计一个尽可能高效的算法，因此需要尽量保证算法的复杂度为O(n)，也即只需要进行依次链表扫描；若扫描次数为两次O(2n)，甚至更多 $O(n^2)$，则会被扣分。
2.考虑定义两个指针p和q，p指针先向前走k-1步；之后p和q同时向前走，当p走到链表尾时，q指向的结点即为倒数第k个结点。（注意该算法仅需要扫描一次链表）

int FindLastK(LinkList list, int k){
    // 在此处填入代码
}

【参考代码】

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *link;
}LNode, *LinkList;
int FindLastK(LinkList list, int k){
    LNode *p = list->link, *q = list->link; // 1. 定义两个指针p和q，用于查找倒数第k个元素，确保两个结点最终的距离为k
    int count = 0;                          // 2. 定义计数器count，用于记录p和q之间的距离
    while(p != NULL){                       // 3. 遍历链表
        if (count < k)                      // 3.1 若距离小于k，则只有p向前走，并且count加1
            count++;
        else                                // 3.2 若距离大于k，则p, q同时向前走
            q = q->link;
        p = p->link;
    }
    if (count < k)                           // 4. 链表遍历完时，count还小于k，则说明链表长度比k小，返回0
        return 0;
    else{                                    // 5. 顺利遍历完成，并且找到了倒数第k个元素，则输出该元素q，并返回1
        printf("%d", q->data);
        return 1;
    }
} // FindLastK

算法步骤（可根据代码注释和逻辑结构进行撰写）：

1. 定义两个指针p和q，用于查找倒数第k个元素，确保两个结点最终的距离为k
2. 定义计数器count，用于记录p和q之间的距离
3. 遍历链表，若p为空，则跳转到第5步
4. 若距离count小于k，则只有p向前走，并且count加1；若距离大于k，则p, q同时向前走
5. 链表遍历完时或p为空，判断count是否小于k，若小于k，则说明链表长度比k小，返回0，查找失败
6. 若count大于等于k，则输出q所指结点的数据域，并返回1，查找成功

4. (选做)[奖励分:0~1] 已知两个非递减序列S1与S2，要求设计一个基于链表的合并算法输出一个新的递减序列S3，该序列不能有重复数据。要求：
1). 描述算法的基本设计思想
2). 描述算法的详细实现步骤
3). 根据设计思想和实现步骤，使用C/C++语言完成该算法的编写，关键之处给出注释。

【参考答案】
一、设计思想
设存在两个非递减序列S1和S2，非递减意味着可能存在重复的数据，因此在进行合并时需要考虑跳过重复的数据。在进行这两个序列的合并时，可以同时从S1和S2的列首开始比较，不断将较小的值赋值给一个新的结点p3，并将p3采用前插法插入到S3的头部。当某个序列遍历完后，继续将另一个序列的剩余元素逐个赋值给新结点p3，然后再以前插法插入到新序列S3的头部。考虑使用新结点p3来复制p1或p2的值的原因是，S1和S2可能会存在重复的值，此时需要利用它们自身的指针p1和p2来完成重复值的跳过。如果直接将p1或p2的值链接给p3，则会导致无法在S1和S2中跳过重复值。

二、实现步骤

1. 分别为序列S1和S2初始化两个指针，并指向其首元结点；
2. 创建并初始化一个新链表S3，并为其分配空间；
3. 当两个序列均未遍历完时，比较两个序列的当前结点值，将较小值结点插入到新序列S3的头部；
4. 在进行比较插入的时候，若p1所指向的数据比p2所指向的数据更小，则将p1所指向的结点的数据赋值给新结点p3，并将p3使用前插法插入到S3的头部，作为S3新的首元结点。同时，遍历S1，跳过与p1具有相同值的结点；
5. 若p1所指向的数据与p2所指向的数据相同，则将p1所指向的结点的数据赋值给新结点p3，并将p3使用前插法插入到S3的头部，作为S3新的首元结点。同时，分别遍历S1和S2，并分别跳过与p1和p2具有相同值的结点；
6. 若p1所指向的数据比p2所指向的数据更大，则将p2所指向的结点的数据赋值给新结点p3，并将p3使用前插法插入到S3的头部，作为S3新的首元结点。同时，遍历S2，跳过与p2具有相同值的结点；
7. 将S1或S2中未遍历完的剩余元素依次使用前插法插入到S3的头部，作为S3新的首元结点，同时，应注意跳过具有相同值的结点。

三、参考代码

LinkList MergeList(LinkList &S1, LinkList &S2){
    p1 = S1->next; p2 = S2->next;          // 1. 初始化两个序列的指针
    LinkList S3;                           // 2. 初始化一个新链表S3
    S3 = (LinkList)malloc(sizeof(LNode));  // 2.1 为S3分配空间
    S3->next = NULL;                       // 2.2 初始新链表
    
    while(p1->next && p2->next){                  // 3. 两个序列均未遍历完时
        if(p1->data < p2->data){                  // 3.1 比较两个序列工作指针所指向的元素，若p1较小，则将p1移动到S3中，并调整指针p1
            p3 = new LNode;                       // 3.1.1 创建一个新结点p3
            p3->data = p1->data;                  // 3.1.2 将p1的值赋值给新节点p3
            p3->next = S1->next;                  // 3.1.3 将p3采用前插法插入到S3表中
            S1->next = p3;                        
            while(p1->data == p1->next->data)     // 3.1.3 判断p1的后继是否与p1相等，若相等则持续向后移动，跳过相等部分
                p1 = p1->next;                        
            p1 = p1->next;                        // 3.1.4 将p1指向下一个和当前结点值不相同的结点
        }
        else if(p1->data == p2->data){            // 3.2 若p1和p2的所指向的元素相等，则将p1移动到S3中，并同时调整指针p1和p2
            p3 = new LNode;                       // 3.2.1 创建一个新结点p3
            p3->data = p1->data;                  // 3.2.2 将p1的值赋值给新节点p3            
            p3->next = S1->next;                  // 3.2.3 将p3采用前插法插入到S3表中
            S1->next = p3;                           
            while(p1->data == p1->next->data)     // 3.2.3 判断p1的后继是否与p1相等，若相等则持续向后移动，跳过相等部分
                p1 = p1->next;
            p1 = p1->next;                        // 3.2.4 将p1指向下一个和当前结点值不相同的结点
            while(p2->data == p2->next->data)     // 3.2.5 判断p2的后继是否与p2相等，若相等则持续向后移动，跳过相等部分
                p2 = p2->next;
            p2 = p2->next;                        // 3.2.6 将p2指向下一个和当前结点值不相同的结点
        }
        else{                                     // 3.3 若p1大于p2，则将p2移动到s3中，并调整指针p2
            p3 = new LNode;                       // 3.2.1 创建一个新结点p3
            p3->data = p1->data;                  // 3.2.2 将p1的值赋值给新节点p3   
            p3->next = S3->next;                     // 3.3.1 将p2采用前插法插入到S3表中 
            S3->next = p3;                           // 3.3.2 更新p3 
            while(p2->data == p2->next->data)     // 3.3.3 判断p2的后继是否与p2相等，若相等则持续向后移动，跳过相等部分
                p2 = p2->next;
            p2 = p2->next;                        // 3.3.4 将p2指向下一个和当前结点值不相同的结点
        }
    }
    if(p1->next){                                 // 4. 将S1中剩余的元素依次采用前插法插入到S3中
        p3 = new LNode;                       
        p3->data = p1->data;     
        p3->next = S1->next;                  
        S1->next = p3;                          
        while(p1->data == p1->next->data)     
            p1 = p1->next;
        p1 = p1->next;
    }
    if(p2->next){                                 // 5. 将S2中剩余的元素依次采用前插法插入到S3中
        p3 = new LNode;
        p3 ->data = p2->data;
        p3->next = S3->next;                      
        S3->next = p2;   
        while(p2->data == p2->next->data)   
            p2 = p2->next;
        p2 = p2->next;
    }
    
}

【扩展练习】

1. 设计一个算法用于判断带头结点的循环双链表是否对称。

算法提示：
1.定义两个方向指针l和r，并让l从左向右扫描，让r从右向左扫描；
2.若l和r所指结点值相等，则继续扫描，否则返回0；若l和r均扫描到表尾，则返回1；
3.若双链表中结点个数为奇数，则l和r均最终将指向中间结点；若为偶数，则l和r最终将相遇但不重合。

int Symmetry(DLinkList L){
    // 在此处填入代码
}

【参考代码】

int Symmetry(DLinkList L){
    DNode *l = L->next; *r = L->prior;    // 1. 定义两个方向指针l和r，并让l从左向右扫描，让r从右向左扫描；
    while(l != r && l->next != r){        // 2. 若l和r未重合或未相邻，则继续扫描；
        if(l->data = r->data) {           // 3. 若l和r所指结点值相等，则继续扫描；
            l = l->next;
            r = r->prior;
        }
        else return 0;                    // 4. 若l和r不相等，则返回0；
    }
    return 1;                             // 5. 若l和r相遇或重合，扫描结束，则返回1；
}

2. 设头指针为L的带有表头结点的非循环双向链表，其每个结点中除有前驱指针pre、数据data和后继指针next外，还有一个访问频度域freq。在链表被启用前，其值均初始化为零。每当在链表中进行一次Locate(L, x)运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点前面，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。

算法提示：
1.本题涉及三个过程，分别是查找、删除和插入；
2.查找：在双向链表中查找值为x的结点；
3.删除：将查找到的值从链表上摘下；
4.插入：从摘除点开始往前进行查找，查找第一个freq比其大的结点，并插入到该结点之后。注意双链表的插入需要执行四件套，被插入结点的前驱和后继都有两个指针需要修改。

DLinkList Locate(DLinkList &L, ElemType &x){
    // 在此处填入代码
}

【参考代码】

DLinkList Locate(DLinkList &L, ElemType &x){
    DNode *p = L->next, *q;                // 1. 定义指向头结点的工作指针p和其前驱q
    while(p && p->data != x){              // 2. 遍历链表L，并查找值为x的结点
        p = p->next;                       
    if (!p) exit(0);                       // 3. 若未找到，则返回空指针
    else {                                 // 4. 若找到
        p->freq++;                         // 4.1 令被访问元素p的访问频度增1
        if (p->pre = L || p->pre->freq < p->freq)  // 4.2 若p是首元结点或p的freq小于前驱，则返回p
            return p;                      // 4.2 返回被访问元素p
        if (p->next != NULL)
            p->next->pre = p->pre;         // 4.3.1 （删除p）若p的后继存在，则将后继的前驱指向p的前驱
        p->pre->next = p->next;            // 4.3.2 （删除p）将p的前驱的后继指向p的后继
        q = p->pre;                         // 4.4 开始查找比p的freq大的结点
        while(q != L && q->freq <= p->freq) // 4.4.1 若前面结点q的freq不大于结点p，则q向前移动
            q = q->pre;                        // 不大于的目的是为了保证p能插入到同频率的第一个
        q->next->pre = p;                   // 4.4.2 执行插入操作，将q的next的pre指向待插入结点p
        p->next = q->next                   // 4.4.3 执行插入操作，将新结点p的next指向q原来的next
        p->pre = q;                         // 4.4.4 执行插入操作，将新结点p的pre指向q
        q->next = p;                        // 4.4.5 执行插入操作，将q的next指向p
    }
    return p;                               // 5. 返回找到的结点p的新位置       
}

3. 试编写在带头结点的单链表L中删除一个最小值结点的高效算法，假设最小值结点时唯一的。

算法提示：
1.定义一组指针p和pre用来扫描链表，其中pre为p的直接前驱；
2.定义另一组指针minp和minpre，用于保存值最小的结点和其直接前驱；
3.从左往右扫描链表，并比较当前扫描结点p和minp的值，若p<minp，则将minp指向p所在的位置，minpre指向p的直接前驱；
4.待整个链表扫描完成后，将minp指向的结点删除即可。

LinkList DeleteMin(LinkList &L){
    // 在此处填入代码
}

【参考代码】

LinkList DeleteMin(LinkList &L){
    LNode *pre = L, *p = pre->next;     // 1.定义一组指针p和pre用来扫描链表，其中pre为p的直接前驱；
    LNode *minp = pre, *minpre = pre;   // 2.定义另一组指针minp和minpre，用于保存值最小的结点和其直接前驱
    while (p !=NULL){
        if (p->data < minp->data){      // 3.从左往右扫描链表，并比较当前扫描结点p和minp的值，
            minp = p;                   // 3.1 若minp<p，则将minp指向p所在的位置，minpre指向p的直接前驱；
            minpre = pre;
        }
        pre = p;                        // 3.2 若minp>=p，则将pre和p同时向后移动一个结点
        p = p->next;
    }
    minpre->next = minp->next;          // 4. 待整个链表扫描完成后，将minp指向的结点删除即可
    free(minp);                         // 5. 释放已删除结点minp的空间
    return L;
}

4. 将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，而B表中含有原表中序号为偶数的元素，且保持其相对顺序不变。

算法提示：

1. 定义一个flag变量来计算被访问过的结点数
2. 当flag为奇数时，将结点插入A表，否则插入B表

LinkList SeparateList(LinkList &L){
    // 在此处填入代码
}

【参考代码】

LinkList SeparateList(LinkList &L){
    int flag = 0;                                     // 1. 定义一个flag变量来计算被访问过的结点数
    LinkList A = (LinkList)malloc(sizeof(LNode));     // 2.1 创建一个新表A
    LinkList B = (LinkList)malloc(sizeof(LNode));     // 2.2 创建一个新表B
    A->next = B->next = NULL;                         // 2.3 初始化新表A和B
    LNode *pa = A->next, *pb = B->next, *p = L->next; // 3. 定义指针pa,pb,p分别指向新表A,B和源表L的首元结点
    while (p != NULL){                                // 5. 遍历原表
        flag++;                                       // 5.1 计算被访问过的结点数量
        if (flag % 2 == 1){                           // 5.2 当flag为奇数时，将结点插入A表
            pa->next = p;                                // 先将pa的下一个结点指向p 
            pa = p;                                      // 再将pa移动到p所指结点
        }                        
        else{                                         // 5.3 当flag为偶数时，将结点插入B表
            pb->next = p;                                // 先将pa的下一个结点指向p
            pb = p;                                      // 再将pa移动到p所指结点
        }
        p = p->next;                                  // 5.4 遍历结点移动到原表的下一个结点
    }
    pa->next = pb->next = NULL;                       // 6. 插入完毕后，为A,B的尾结点赋null值
    return A, B;                                      // 7. 返回新表A,B
}