广义表 & 最大子列和改编 & 带头节点链表实现

今天整个心不在焉😢，可能是惦记着今晚羽生的自由滑😭，可能昨天刷了太多张宇视频魔怔了。。。电脑内胆包神奇的不见了，早上电脑包每层拉链搭扣都没合上就背着出门了。。。想撸会儿码定定神出错巨多，昨天才写了4种实现的最大子列和，本来想轻车熟路就一点改编怎么着半小时够了（而且pat可能刷到过了= = ），疯狂出错四五遍。。。甚至赋值左右写反= = WTF。。。状态实在不好放弃了网页上文本编辑器投向clion爸爸的怀抱。。。然后链表合并这么朴素的题目也一直出错= = 虽然不知道这是不是考点，anyway，学了就学了吧= =

---

广义表

• 王道在邻接表存储有向图/无向图的弊端和改进提到了其中重要的两种：十字链表（有向图），多重邻接表（无向图），然而讲的不清楚，没想到zju的数据结构mooc在线性表这儿就提了。

参考： zju mooc 2.1 线性表及其实现

广义表：十字链表、多重邻接表等

• ⚠️多重链表：多重体现在可能有多条链共用某些节点，而非节点中含有多个指针域。

多重链表

参考：b站上王卓老师讲解 十字链表 & 邻接多重表

邻接表弊端 -> 改进的存储结构

---

最大子列和 —— 输出子列首尾元素

• 需要注意的点：含0的情况，全负时题目要求输出整个序列的首尾元素， 有并列最大和取前者

  
  通过率不高是有原因的？？？

#include <cstdio>

const int INF = 0x3f3f3f3f;

int main() {
    int nn, curr, sum = 0, max_sum = -1, fst;
    scanf("%d", &nn);
    int st = -INF, best_st = -INF, best_ed = -INF, curr_len = 0, len = 0;
    for (int i = 0; i < nn; i++) {
        scanf("%d", &curr);
        if (i == 0) fst = curr;
        if (curr_len == 0 && curr >= 0)
            st = curr;
        sum += curr;
        if (sum < 0) {
            sum = 0, curr_len = 0, st = -INF;
        } else {
            curr_len++;
            if (sum > max_sum) {
                max_sum = sum, len = curr_len;
                best_st = st, best_ed = curr;
            }
        }
    }
    if (len > 0) {
        printf("%d %d %d\n", max_sum, best_st, best_ed);
    } else printf("0 %d %d\n", fst, curr);
    return 0;
}

---

带头节点的链表实现

• 题目：将两个有头节点的链表表示的递增整数序列合并为一个非递减的整数序列（zju ds mooc week2作业）
  

  List S = (List) malloc(sizeof(struct Node)); S->Next = NULL;

• ⚠️段错误：未给指针分配空间而p->data / 数组越界 / 未检查!empty()就出栈或者出队

• 指向某类型变量的指针 ptr = (指向某类型变量的指针) malloc(sizeof(某类型变量));

• 头节点的处理

• 注意看样例输出： L1->Next 、L2->Next 置为 NULL

#include <cstdio>
#include <cstdlib>

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode Next;
};
typedef PtrToNode List;


List Read() {
    ElementType len, data;
    scanf("%d", &len);
    List list = (List) malloc(sizeof(struct Node));
    list->Next = NULL;
    PtrToNode curr = list;
    for (int i = 0; i < len; ++i) {
        scanf("%d", &data);
        curr->Next = (PtrToNode) malloc(sizeof(struct Node));
        curr = curr->Next;
        curr->Data = data, curr->Next = NULL;
    }
    return list;
}

void Print(List L) {
    PtrToNode curr = L->Next;
    if (curr) {
        while (curr->Next) { // to avoid extra space
            printf("%d ", curr->Data);
            curr = curr->Next;
        }
        printf("%d\n", curr->Data);
    } else puts("NULL");
}

// 将两个链表表示的递增整数序列合并为一个非递减的整数序列
List Merge(List L1, List L2) {
    List final = (List) malloc(sizeof(struct Node)); //caution: with a head node
    PtrToNode curr1 = L1->Next, curr2 = L2->Next, curr = final;
    while (curr1 && curr2) {
        if (curr1->Data <= curr2->Data) {
            curr->Next = curr1;
            curr1 = curr1->Next;
        } else {
            curr->Next = curr2;
            curr2 = curr2->Next;
        }
        if (!final->Next) {
            final->Next = curr->Next;
        }
        curr = curr->Next;
    }
    if (curr1) {
        curr->Next = curr1;
    }
    if (curr2) {
        curr->Next = curr2;
    }
    L1->Next = L2->Next = NULL; //坑到我的地方qaq
    return final;
}


int main() {
    List L1, L2, L;
    L1 = Read();
    L2 = Read();
    L = Merge(L1, L2);
    Print(L);
    Print(L1);
    Print(L2);

    return 0;
}

/* Input:
 * 3
 * 1 3 5
 * 5
 * 2 4 6 8 10
 *
 * Output:
 * 1 2 3 4 5 6 8 10
 * NULL
 * NULL
 */

吃吃饭准备看羽生结弦比赛了！
借用小天使一句话“明けない夜はない。”
冲鸭！！！今天自由滑成绩如何，羽生さまも、わたしも、一生懸命に頑張っていく！！！❤️❤️❤️