绪论和线性表

顺序表：14

绪论

数据结构基本概念

数据有关名称
数据	字节流
数据项	int（基本数据类型）
数据元素	struct（复合数据类型）
数据对象	class（包含函数）

数据类型
原子数据类型	int，对应数据项
结构类型	struct，对应数据元素
抽象数据类型	class，对应数据对象

数据结构三要素：注意区分逻辑和物理结构

• 逻辑结构：线性和非线性
• 物理结构：顺序、链式、索引、哈希
• 数据运算：针对逻辑结构而言

一个完整的数据结构必须包括以上三要素，否则不能称作一个严格的数据结构

算法和算法评价

算法特性（五个）：有穷性；输入输出；确定性；可行性

评价算法质量

• 时间复杂度：基本运算的频度（语句的频度指其被执行的次数，基本运算指算法中嵌套最深的语句）
• 空间复杂度：额外辅助空间大小，如int[n]大小为O(n)，常量为O(1)，int[n][n]为O(n^2)

一个算法的时间复杂度一般是指算法平均执行情况的时间复杂度，但有时也指最差的时间复杂度，不同情况注意区分

在求算法的时间复杂度时，对于一般非递归算法，采用求和或积分的方法可以得到基本运算的频度，取其最高次幂作为时间复杂度，如

$$\sum_{i=1}^{n}\sum_{j=1}^{i}1 = \sum_{i=1}^{n}i = \int_1^n i\,di = \frac{1}{2}n^2-\frac{1}{2} \Rightarrow O(n^2)$$

对于递归算法，需要将每次递归的附加运算f(n)加上

$$T(n) = f(n)+T(n-1)=f(n)+f(n-1)+T(n-2)=...$$

通常这个f(n)是一个常数

线性表

线性表：逻辑结构，指线性排列的数据集合，是一种随机存取的存储结构（存取方式指读取方式，线性表可以自由读取）

线性表的两种物理实现：顺序表，链表

• 为什么说是物理实现，因为顺序表的顺序，指的是物理内存的连续，注意和线性这一概念的区别

顺序表相关算法

第八题，第十四题

插入位置，若 i 指的是下标，则范围为(0,n)，若指的是第几个位置，则为(1,n+1)

关于顺序表的算法：无非CRUD，即create, read, update, delete，多写多做

第六题

• 对于有序顺序表，采用双指针的形式，慢指针指向排好的元素末尾，快指针向后遍历将独一无二的元素添加到慢指针后
• 对于无序表，采用 Map 存储单独元素，构建新的顺序表

第七题：经典的对顺序表剩余的元素进行while(i < n){ res.push_back(L1[i++]); }操作

有点问题，重复看

二分搜索，在数组中插入元素

Hash 表存放每个位置的元素，遍历两次数组，第一次记录map[n+i-p] = L[i]，第二次构建数组arr[i] = map[i]，空间时间均为O(n)

和那个升序排列构建新数组的题有点像，这里要注意推出时机，使得下一个遍历到的元素为两个表公共中位数，时间O(n)空间O(1)

Hash 表处理，时空均为O(n)

好难

链表定义及算法

关于单链表的基本算法：

• 头插、尾插：头节点尾节点方便运算
• 前插、后插
• 删除：先删链（注意顺序不要断链），再 free 结点

双链表：方便前后邻接数据处理，可以很简单地找到前驱节点

循环链表 - 双向循环链表：判空看头指针H->next是否为头指针H（一般循环链表设尾指针不设头指针）

静态链表：数组实现的链表，每个数组元素链向数组的下一个下标，这样在删除添加数据时只用移动一个位置元素

应选 C，因为要遍历到 m 链表的尾节点

这种选择合适数据结构的题，其实就是看操作方不方便，方便指时间复杂度低，尽量往 O(1) 上靠，这里只有带头节点的双循环链表能够实现 O(1)，带尾指针的单循环链表要 O(n) 才能实现删除末尾节点

同理 C 能够使两个操作均为 O(1)，所以选 C

画图，循环链表判空条件h->next = h

void deleteX(LNode *n, int x){
    if(n == NULL){
        return;
    } else if(n->val == x){
        LNode *p = h;
        h = h->next;
        free(p);
        deleteX(h, x);
    } else {
        deleteX(h->next, x);
    }
}

为什么不会断链？

我想用递归算法求解，时间复杂度 O(n)，未经验证，可能是对的

int flag = 0;
int deep(LNode* n, int k){
    if(n->next == NULL){
        return 1;
    }
    int cur = 1+deep(n->next, k);
    if(cur == deep){
        cout << n->val;
        flag = 1;
    }
    return deep
}

int getK(LNode* h, int k){
    deep(h, k);
    return flag;
}

实在不行用最笨的方法遍历两次，第一次读到长度 n，则所求元素正序为 n-k，再遍历一次取值

最笨的办法，用set存储LNode*，先遍历 L1，再遍历 L2，返回遍历 L2 时第一个重复的节点

用 set 判重，快慢指针删除单链表元素

很久以前写过，因为要求空间复杂度为 O(1)，不能用额外数据结构，解题步骤如下

1. 截取后半段链表
2. 反转后半段链表
3. 合并前后两段链表

// 截取链表后半段，带头节点
LNode* split(LNode* h){
    int n = 0;
    LNode* p = h;
    while(p != NULL) { p = p->next; n++; }
    p = h;
    for(int i = 0; i < n/2; i++){
        p = p->next;
    }
    // 得到后半段的第一个节点，新增头节点l，返回
    LNode* l;
    l->next = p->next;
    p->next = NULL;
    return l;
}

// 递归反转链表，不带头节点
LNode* reverseNode(LNode* n){
    if(n->next == NULL){
        return n;
    }
    reverseNode(n->next)->next = n;
    return n;
}
// 封装翻转函数，处理尾节点和头节点
LNode* reverseList(LNode* h){
    LNode* tail = h;
    while(tail->next != NULL){ tail = tail->next; }
    reverseNode(h)->next = NULL; // 将原先的头节点，现在尾节点的 next 置空
    return tail; // 返回原先的尾节点，现在的头节点
}

// 合并两个链表l1，l2，其中l1带头节点，l2不带头节点
LNode* merge(LNode* l1, LNode* l2){
    LNode* h = l1, *p = h; // 保存头节点和创建移动节点
    l1 = l1->next; l2 = l2->next;
    int count = 0;
    while(l1 != NULL && l2 != NULL){ // 遍历两个链表
        if(count % 2 == 0){
            p->next = l1;
            l1 = l1->next;
            p = p->next;
        }else {
            p->next = l2;
            l2 = l2->next;
            p = p->next;
        }
        count++;
    }
    // 因为分割链表时取得 n/2，所以只有可能后半段链表比前半段链表多一个元素
    while(l2 != NULL){
        p->next = l2;
        l2 = l2->next;
        p = p->next;
    }
    return h; // 返回合并的链表的头节点
}

void solve(LNode* h){ // 整理出解决算法
    LNode* l = split(h);
    LNode* r = reverseList(l);
    merge(h, r); // 头节点没变，h 仍为头节点
}

不要用递归翻转链表，用头插法翻转（带头节点）

void reverse(LNode* h){
    LNode *pre = h->next, *cur = NULL;
    if(pre != NULL){ cur = h->next; }
    else{ return; } // 空表直接返回
    // 取第一个元素为尾节点，后继置空
    pre->next = NULL;
    while(cur != NULL){
        LNode* next = cur->next; // 保存下一节点
        cur->next = pre; // 令当前节点指向前一节点
        pre = cur; // 保存当前节点，下一轮要指
        cur = next; // 更新当前节点
    }
    // 头节点指向新的第一元素
    h->next = cur;
}