数据结构进阶 - 第二章线性表-EW帮帮网

第二章线性表

408考研大纲

线性表的基本概念
线性表的实现
1. 顺序存储
2. 链式存储
线性表的应用

概念区分

基本概念

线性结构：一种元素间的逻辑关系，一对一
线性表：一种抽象数据类型，其元素的逻辑结构为线性结构
顺序表：线性表的顺序存储
链表：线性表的链式存储

重点提醒

顺序表是有序表。该说法是错误的。

顺序表指的是存储方式，与元素是否有序无关。

2.1 线性表的定义

线性表为n(n≥0)个相同数据元素的有限序列，其特点为：

存在唯一首元素、尾元素
除首元素和尾元素外，其余每个元素只有一个前驱和后继（线性结构，1:1关系）

表示方法：L=(a₁, a₂, a₃, …, aₙ)

每个元素都有：

唯一直接前驱
唯一直接后继

2.2 顺序表——线性表的顺序存储

定义

用一段连续的内存空间存储线性表中的元素。逻辑上相邻的元素，物理存储位置也相邻。

数据结构定义

静态分配

#define MAXSIZE 100
typedef struct {
    ElemType elem[MAXSIZE];
    int last;  // 最后元素下标
} SeqList;

动态分配

typedef struct {
    ElemType *pElem;
    int last;
    int maxSize;
} SqList;

顺序表的基本运算

查找：GetData(L,i); Locate(L,e)
插入：插入位置 1≤i≤n+1；等概率时，平均移动 n/2个元素
删除：删除位置 1≤i≤n；等概率时，平均移动(n-1)/2个元素

顺序表的优缺点

优点：

存储密度大（为1）
可随机访问元素

缺点：

插入、删除需要移动大量元素
需要连续的内存空间
静态内存分配

顺序表算法实例

1. 删除所有值为e的元素

算法一：双指针法（保持相对顺序）

void DeleteItems(SeqList *L, ElemType e) {
    int i = -1, j = 0;
    while (j <= L->last) {
        if (L->elem[j] == e)
            j++;
        else {
            L->elem[i+1] = L->elem[j];
            j++; i++;
        }
    }
    L->last = i;
}

时间复杂度：O(n)
空间复杂度：O(1)
特点：保持原有元素相对顺序

算法二：两头夹击法（不保持相对顺序）

void DeleteItems(SeqList *L, ElemType e) {
    int i = 0, j = L->last;
    while (i <= j) {
        while (i <= j && L->elem[i] != e) i++;
        while (i <= j && L->elem[j] == e) j--;
        if (i < j) {
            L->elem[i] = L->elem[j];
            i++; j--;
        }
    }
    L->last = i - 1;
}

时间复杂度：O(n)
空间复杂度：O(1)
特点：会改变原有元素相对顺序

2. 删除有序表中重复元素

void DeleteRepeatItem(SeqList *L) {
    int i = 0, j = 1;
    while (j <= L->last) {
        if (L->elem[i] == L->elem[j])
            j++;
        else {
            L->elem[i+1] = L->elem[j];
            i++; j++;
        }
    }
    L->last = i;
}

3. 删除无序表中重复元素（元素值≤1000）

void DelrepeatElem(SeqList *L) {
    int *tmp = (int*)malloc(sizeof(int) * 1001);
    int i = 0, j = 0, x;
    memset(tmp, 0, 1001 * sizeof(int));
    
    while (j <= L->last) {
        x = L->elem[j];
        if (tmp[x] == 1) 
            j++;  // 重复出现，舍弃
        else {    // 第一次出现，保留
            tmp[x] = 1;
            L->elem[i] = L->elem[j];
            i++; j++;
        }
    }
    L->last = i - 1;
    free(tmp);
}

算法思想：用空间换时间

4. 求主元素

int Majority(int A[], int n) {
    int i, count = 1;
    int majorNum = A[1];
    
    // 第一阶段：找候选主元素
    for (i = 2; i <= n; i++) {
        if (A[i] == majorNum) 
            count++;
        else {
            if (count > 0) 
                count--;
            else {
                majorNum = A[i]; 
                count = 1;
            }
        }
    }
    
    // 第二阶段：验证是否为真正的主元素
    count = 0;
    for (i = 1; i <= n; i++)
        if (A[i] == majorNum) count++;
    
    if (count > n / 2) 
        return majorNum;
    else 
        return 0;
}

5. 查找和为X的整数对

void pairNum(int a[], int n, int x) {
    // 先排序（假设已排序）
    int i = 0, j = n - 1;
    bool found = false;
    
    while (i < j) {
        if (a[i] + a[j] == x) {
            found = true;
            cout << a[i] << " " << a[j] << endl;
            i++; j--;
        }
        else if (a[i] + a[j] > x)
            j--;  // 和太大
        else
            i++;  // 和太小
    }
    
    if (!found)
        cout << "不存在！" << endl;
}

6. 三个有序序列的公共元素

void findCommonElem(int A[], int B[], int C[], int n) {
    int i = 0, j = 0, k = 0;
    
    while (i < n && j < n && k < n) {
        if (A[i] == B[j] && B[j] == C[k]) {
            cout << A[i] << endl;
            i++; j++; k++;
        }
        else {
            int minVal = min(A[i], min(B[j], C[k]));
            if (A[i] == minVal) i++;
            if (B[j] == minVal) j++;
            if (C[k] == minVal) k++;
        }
    }
}

时间复杂度：O(n)
空间复杂度：O(1)

7. 三个序列的最小距离

int findMinDist(int s1[], int s2[], int s3[], int n1, int n2, int n3) {
    int min_dist = INT_MAX;
    int dist;
    int i = 0, j = 0, k = 0;
    
    while (i < n1 && j < n2 && k < n3) {
        dist = abs(s1[i] - s2[j]) + abs(s2[j] - s3[k]) + abs(s3[k] - s1[i]);
        if (dist < min_dist) 
            min_dist = dist;
        
        // 移动指向最小元素的指针
        if (s1[i] <= s2[j] && s1[i] <= s3[k]) i++;
        else if (s2[j] <= s1[i] && s2[j] <= s3[k]) j++;
        else k++;
    }
    
    return min_dist;
}

8. 顺序表调整（奇偶分离）

void AdjustSqlist(SeqList *L) {
    int i = 0, j = L->last;
    int temp;
    
    while (i < j) {
        while (i < j && L->elem[i] % 2 != 0) i++;  // 找偶数
        while (i < j && L->elem[j] % 2 == 0) j--;  // 找奇数
        if (i < j) {
            temp = L->elem[i];
            L->elem[i] = L->elem[j];
            L->elem[j] = temp;
        }
    }
}

2.3 链表——线性表的链式存储

定义

线性表中的元素在内存空间中的位置不一定连续。为了维系元素的逻辑关系，需要额外的指针域(next)记录下一个元素的位置。

数据结构定义

typedef struct Node {
    ElemType data;
    struct Node *next;
} Node, *LinkList;

重要概念区分

头指针：指向链表第一个结点的指针
头结点：链表第一个结点，通常不存储数据
首元素结点：存储第一个数据元素的结点

头结点的好处

处理第一个结点和处理其他结点操作相同
参数带头指针即可，无需指针的指针

链表的基本运算

建链表：头插法、尾插法
查找：GetData(L,i); Locate(L,e)
插入：不需要移动元素，T(n)=O(n)
删除：不需要移动元素，T(n)=O(n)

链表的优缺点

优点：

插入、删除不需要移动大量元素
动态分配内存

缺点：

存储密度小
不能随机访问

链表分类

单链表
循环单链表
双向链表
双向循环链表
静态链表

双向链表

插入操作：

s->prior = p->prior;
p->prior->next = s;
s->next = p;
p->prior = s;

删除操作：

p->prior->next = p->next;
p->next->prior = p->prior;
free(p);

链表算法实例

1. 快慢指针查找中间结点

Node *midNode(LinkList L) {
    Node *fast, *slow;
    fast = slow = L;
    
    if (L->next == NULL) return NULL;
    
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    return slow;
}

2. 链表就地逆置（头插法）

void ReverseList(LinkList L) {
    Node *p, *q;
    p = L->next;
    L->next = NULL;
    
    while (p != NULL) {
        q = p->next;
        p->next = L->next;
        L->next = p;
        p = q;
    }
}

3. 删除有序链表中范围内的元素

void DelData(LinkList L, ElemType mink, ElemType maxk) {
    Node *p = L->next, *pre = L, *temp;
    
    // 找到开始删除的位置
    while (p && p->data <= mink) {
        pre = p;
        p = p->next;
    }
    
    // 删除范围内的元素
    while (p && p->data < maxk) {
        temp = p->next;
        free(p);
        p = temp;
    }
    
    pre->next = p;
}

4. 递归从尾到头输出链表

void ReversePrint(LinkList L) {
    if (L == NULL) return;
    if (L->next != NULL)
        ReversePrint(L->next);
    printf("%d ", L->data);
}

5. 查找倒数第k个结点（快慢指针）

Node *FindKthToTail(LinkList L, int k) {
    Node *fast = L, *slow = L;
    
    // 快指针先走k步
    for (int i = 0; i < k && fast != NULL; i++) {
        fast = fast->next;
    }
    
    if (fast == NULL) return NULL;  // k超出链表长度
    
    // 快慢指针同时移动
    while (fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }
    
    return slow;
}

6. 删除绝对值重复的结点

void delSame(LinkList L) {
    int A[5001] = {0};
    Node *pre, *p;
    
    pre = L;
    p = L->next;
    
    while (p) {
        int k = abs(p->data);
        if (A[k] == 0) {  // 第一次出现
            A[k] = 1;
            pre = p;
            p = p->next;
        }
        else {  // 已经出现过，删除该结点
            pre->next = p->next;
            free(p);
            p = pre->next;
        }
    }
}

7. 特殊逆置（2019-408真题）

void specialReverse(LinkList L) {
    Node *mid;
    if (L->next == NULL) return;
    
    mid = midNode(L);  // 获取中间结点
    
    // 逆置后半段
    Node *p = mid->next, *tmp;
    mid->next = NULL;
    while (p) {
        tmp = p->next;
        p->next = mid->next;
        mid->next = p;
        p = tmp;
    }
    
    // 交替插入
    p = L->next;  // 前半段指针
    Node *q = mid->next;  // 后半段指针
    mid->next = NULL;
    
    while (q != NULL) {
        tmp = q->next;
        q->next = p->next;
        p->next = q;
        q = tmp;
        p = p->next->next;
    }
}

8. K个一组翻转链表

LinkList reverseKGroup(LinkList head, int k) {
    if (head == NULL || head->next == NULL) return head;
    
    // 计算链表长度
    int len = 0;
    Node *p = head->next;
    while (p) {
        len++;
        p = p->next;
    }
    
    int groups = len / k;  // 需要翻转的组数
    Node *prev = head;
    Node *curr = head->next;
    
    for (int i = 0; i < groups; i++) {
        Node *groupStart = curr;
        
        // 翻转k个结点
        for (int j = 0; j < k; j++) {
            Node *next = curr->next;
            curr->next = prev->next;
            prev->next = curr;
            curr = next;
        }
        
        groupStart->next = curr;
        prev = groupStart;
    }
    
    return head;
}

2.4 顺序表和链表的综合比较

顺序表

优点：

无需存储元素间的关系，存储密度大
可随机查找

缺点：

若静态分配，则容易造成溢出或空间浪费
若动态分配，需要移动大量元素
插入删除需要移动大量元素

链表

优点：

动态分配
插入删除不需要移动元素

缺点：

需要额外空间存储元素间的关系
不能随机查找

选择依据

根据以下因素选择合适的存储结构：

线性表长度是否经常变化
各种操作的频率
操作的位置

补充练习题

1. 顺序表两段调整

题目：顺序表L=(a₁,a₂,a₃,…aₙ,b₁,b₂,b₃,…,bₘ)，n≠m。编写算法将其调整为L=(b₁,b₂,b₃,…,bₘ,a₁,a₂,a₃,…aₙ)

算法1：

将整个顺序表逆置
将前m个元素逆置，后n个元素逆置

算法2：

将前n个元素逆置，后m个元素逆置
将整个顺序表逆置

2. 链表旋转

题目：给定一个链表，旋转链表，将链表每个节点向右移动k个位置，其中k是非负数。

算法思想：

k = k % n（n为链表长度）
找到倒数第k个结点
重新连接链表

3. 循环链表中的环检测

题目：某循环单链表（尾元素的指针域可指向链表中的任意一结点），编写算法求循环结点。

算法思想：使用快慢指针

设环外部分长度为a，环内部分长度为b+c
当快慢指针相遇时：2*(a+b) = a+n*(b+c)+b
解得：a = (n-1)(b+c) + c

重要技巧总结

头插法：用于链表逆置、构建递减序列
尾插法：用于构建递增序列
预留指针、工作指针：用于删除操作
快慢指针：用于查找中间结点、倒数第k个结点、环检测
双指针技术：用于有序数组的查找、去重等操作
空间换时间：使用辅助数组处理元素值范围有限的问题

时空复杂度要求

在408考研中，算法设计要求：

重点考察算法思想
对时空复杂度有要求
通常要求时间复杂度为O(n)或O(nlogn)
空间复杂度通常要求为O(1)或允许使用辅助空间

数据结构进阶 - 第二章 线性表

第二章 线性表

408考研大纲

概念区分

基本概念

重点提醒

2.1 线性表的定义

2.2 顺序表——线性表的顺序存储

定义

数据结构定义

静态分配

动态分配

顺序表的基本运算

顺序表的优缺点

顺序表算法实例

1. 删除所有值为e的元素

2. 删除有序表中重复元素

3. 删除无序表中重复元素（元素值≤1000）

4. 求主元素

5. 查找和为X的整数对

6. 三个有序序列的公共元素

7. 三个序列的最小距离

8. 顺序表调整（奇偶分离）

2.3 链表——线性表的链式存储

定义

数据结构定义

重要概念区分

头结点的好处

链表的基本运算

链表的优缺点

链表分类

双向链表

链表算法实例

1. 快慢指针查找中间结点

2. 链表就地逆置（头插法）

3. 删除有序链表中范围内的元素

4. 递归从尾到头输出链表

5. 查找倒数第k个结点（快慢指针）

6. 删除绝对值重复的结点

7. 特殊逆置（2019-408真题）

8. K个一组翻转链表

2.4 顺序表和链表的综合比较

顺序表

链表

选择依据

补充练习题

1. 顺序表两段调整

2. 链表旋转

3. 循环链表中的环检测

重要技巧总结

时空复杂度要求

网站公告

今日签到

热门文章

最新发布

数据结构进阶 - 第二章线性表

第二章线性表