当前位置：首页 > news >正文

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

news 2025/6/27 8:44:03

第二章线性表

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--;  // 和太大elsei++;  // 和太小}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;
}