1. 线性关系、线性表的定义，线性表的基本操作；
1.1 线性关系的定义
- 当 $ 1 \le i \le n $ 时，$ a_i $ 的直接前驱为 $ a_{i-1} $ ， $ a_i $ 的直接后继为 $ a_{i+1} $。
- 除了第一个元素与最后一个元素，序列中任何一个元素 有且仅有 一个直接前驱元素，有且仅有 一个直接后继元素。
- 数据元素之间的先后顺序为 "一对一" 的关系。
1.2 线性表的定义
数据元素之间具有的逻辑关系为 线性关系 的数据元素集合称为 线性表，n 为线性表的长度，长度为 0 的线性表称为空表。
1.3 线性表的基本操作
- 创建一个新的线性表。
- 求线性表的长度。
- 检索线性表中第 i 个数据元素。
- 根据数据元素的某数据项（通常称为关键字）的值，求该数据元素在线性表中的位置。
- 在线性表的第 i 个位置上存入一个新的数据元素。
- 在线性表的第 i 个位置上插入一个新的数据元素。
- 删除线性表中第 i 个数据元素。（$ 1 \le i \le n $）
- 对线性表中的数据元素按照某一个数据项的值的大小做升序或者降序排序。
- 销毁一个线性表。
- 复制一个线性表。
- 按照一定的原则，将两个或两个以上的线性表合并成为一个线性表。
- 按照一定的原则，将一个线性表分解为两个或两个以上的线性表。
2. 线性表的顺序存储结构与链式存储结构（包括单（向）链表、循环链表和双向链表）的构造原理；
2.1 线性表的顺序存储结构
- 线性表的顺序存储结构构造原理：
用一组地址连续的存储单元依次存储线性表的数据元素，数据元素之间的逻辑关系通过数据元素的存储位置直接反映。 - 线性表的顺序存储结构特点：
- 相邻数据元素之间，物理存储位置也相邻。
- 第 i 个元素的地址计算公式为：$ LOC(a_i) = LOC(a_1) + (i-1)*k $，注：每个数据元素占 k 个存储单元。
- 只要确定了线性表的起始位置，可以随机存取数据元素。
- 插入、删除都需要移动大量元素。
- 线性表的顺序存储结构优点：
- 构造原理简单、直观，易理解。
- 元素的存储地址可以通过一个简单的解析式 $ LOC(a_i) = LOC(a_1) + (i-1)*k $ 计算出来。 是一种随机存储结构，存储速度快。
- 由于只需存放数据元素本身的信息，而无其他空间开销，相对链式存储结构而言，存储空间开销小（仅此而已！）
- 线性表的顺序存储结构缺点：
- 存储分配需要事先进行。
- 需要一片地址连续的存储空间。
- 基本操作（如插入、删除）的时间效率较低。
2.2 线性表的链式存储结构
- 线性表的链式存储结构构造原理：
用一组地址任意的存储单元（连续的或不连续的）依次存储表中各个数据元素，数据元素之间的逻辑关系通过 指针 间接地反映出来。 - 线性表的链式存储结构特点：
- 相邻数据元素之间，物理存储位置不要求相邻（一般不相邻）。
- 数据元素之间的逻辑关系是由指针域来确定。
- 不可以随机存取数据元素。
- 插入、删除不需要移动大量元素。
- 线性表的链式存储结构优点：
- 存储空间动态分配，可以根据实际需要使用。
- 不需要地址连续的存储空间。
- 插入 / 删除操作只须通过修改指针实现，不必移动数据元素，操作的时间效率较高。（无论位于链表何处，无论链表的长度如何，插入和删除操作的时间都是 $ Ο (1) $ ）
- 线性表的链式存储结构缺点：
- 每个链结点需要设置指针域（存储密度小）。
- 是一种非随机存储结构，查找、定位等操作要通过顺序扫描链表实现，时间效率较低。（时间为 $ O(n) $）
3. 在以上两种存储结构的基础上对线性表实施的基本操作，包括顺序表的插入与删除、链表的建立、插入与删除、查找等操作对应的算法设计（含递归算法的设计）。
3.1 线性顺序表
3.1.1 线性顺序表的结构定义
typedef int ElemType; // 元素类型
#define LIST_MAX_SIZE 100 // 预先分配给线性表的空间大小
ElemType A[MaxSize]; // 线性表 A
int n; // 线性表长度3.1.2 确定元素 item 在长度为 n 的线性表 A 中的位置
算法设计
从左到右依次遍历，如果找到 item 值相等的元素，则返回元素在表中的位置。如果查找失败，则返回信息 -1
时间复杂度：$ O(n) $
/**
* 确定元素 item 在长度为 n 的线性表 A 中的位置
*/
int LOCATION_LIST(ElemType A[], int &n, ElemType item) {
for (int i = 0; i <= n-1; i++) {
if (item == A[i]) {
return i+1; /* 查找成功，返回在表中位置 */
}
}
return -1; /* 查找失败，返回信息-1 */
}3.1.3 在长度为 n 的线性表 A 的第 i 个位置上插入一个新的数据元素 item
算法设计
该运算是在线性表的第 i−1个数据元素与第 i 个数据元素之间插入一个由符号 item 表示的数据元素 ，使长度为 n 的线性表
转换成长度为 n+1 的线性表：
正常情况下需要的操作：
- 将第 i 个元素至第 n 个元素依次后移一个位置；
- 将被插入元素插入表的第 i 个位置；
- 修改表的长度（表长增 1）；
- 返回成功状态 1。
考虑异常情况（插入失败）：
- 是否表满？ n == MaxSize
- 插入位置是否合适？（正常位置:$ 1 \le i \le n+1 $）
- 返回失败状态 -1。
时间复杂度：$ O(n) $
通常采用元素移动次数的平均值作为衡量插入和删除算法时间效率的主要指标。
插入一个元素需要移动其他的元素的平均次数为：
$ \sum_{i=1}^{n+1} p_i (n-i+1) = \sum_{i=1}^{n+1} (n-i+1)/(n+1) = n/2 $
/**
* 在长度为 n 的线性表 A 的第 i 个位置插入一个新数据元素 item
*/
int INSERT_LIST(ElemType A[], int &n, int i, ElemType item) {
if(n == MAX_SIZE || i < 1 || i > n+1) { // 表满 或者 插入位置不合适
printf("线性表已满 或 插入位置不对。\n");
return -1; // 插入失败
}
// 将第 i 个元素至第 n 个元素依次后移一个位置；
for (int j = n-1; j >= i-1; j--) {
A[j+1] = A[j];
}
A[i-1] = item; // 将被插入元素插入表的第 i 个位置；
n++; // 修改表的长度（表长增1）
return 1; // 插入成功
}3.1.4 已知长度为 n 的线性表 A 采用顺序存储结构，并且数据元素按值大小非递减排列，写一算法， 在该线性表中插入一个数据元素 item，使得线性表仍然保持按值非递减排列。
算法设计
需要进行的操作：
- 特殊位置：item 与最后一个元素进行比较，若有关系 $ item \ge a_i $，直接将 item 插⼊表的末尾。
- 寻找插入位置：
- 从表的第一个元素开始进行比较，若有关系 $ item < a_i $，则找到插入位置为表的第 i 个位置。
- 将第 i 个元素至第 n 个元素依次后移一个位置；
- 将 item 插入表的第 i 个位置；
- 修改表的长度（表长增 1）。
时间复杂度：$ O(n) $
/**
* 向长度为 n 的线性表 A (非递减)中插入数据信息为 item 的元素
* 要求插入后的线性表仍为非递减序列
*/
void INSERT_ITEM_LIST(ElemType A[], int &n, ElemType item) {
if (item >= A[n-1]) { // 插入表的末尾
A[n] = item;
} else {
int i = 0;
while (item >= A[i]) { // 寻找 item 合适的位置
i++;
}
// 将第 i 个元素至第 n 个元素依次后移一个位置
for (int j = n-1; j >= i; j--) {
A[j+1] = A[j];
}
A[i] = item; // 将 item 插入到表中
}
n++; // 修改表的长度（表长增1）
}3.1.5 删除长度为 n 的线性表 A 的第 i 个数据元素
算法设计
该运算是把线性表的第 i 个数据元素从线性表中去掉，使得长度为 n 的线性表
转换成长度为 n-1的线性表：
正常情况下需要的操作：
- 将第 i+1 个元素至第 n 个元素依次前移一个位置。
- 修改表的长度（表长减 1）。
- 返回成功状态 1。
考虑异常情况（插入失败）：
- 是否表空？ n == 0
- 删除位置是否合适？（正常位置：$ 1 \le i \le n $）
- 返回失败状态 -1。
时间复杂度：$ O(n) $
/**
* 删除长度为 n 的线性表 A 的第 i 个数据元素
*/
int DELETE_LIST(ElemType A[], int &n, int i) {
if (i < 1 || i > n) { // 表空 或者 插入位置不合适
printf("线性表为空 或 删除位置不对\n");
return -1; // 删除失败
}
// 将第 i+1 个元素至第 n 个元素依次前移一个位置
for (int j = i; j <= n-1; j++) {
A[j-1] = A[j];
}
n--; // 修改表的长度（表长减 1）
return 1; // 删除成功
}3.1.6 删除长度为 n 的线性表 A 的数据信息为 item 的元素
算法设计（一）：
需要进行的操作：
- 寻找删除位置：
- 从表的第一个元素开始进行比较，若有关系 $ item = a_i $，则找到删除位置 i。
- 将第 i+1 个元素至第 n 个元素依次前移一个位置；
- 修改表的长度（表长减 1）；
- 继续寻找下一个删除位置。
时间复杂度：$ O(n^2) $
/**
* 删除长度为 n 的线性表 A 中数据信息为 item 的元素
*/
void DELETE_ITEM_LIST(ElemType A[], int &n, ElemType item) {
for (int i = 0; i <= n-1; i++) {
if (item == A[i]) { // 找到删除位置
// 将第 i+1 个元素至第 n 个元素依次前移一个位置
for (int j = i+1; j <= n-1; j++) {
A[j-1] = A[j];
}
n--; // 修改表的长度（表长减1）
}
}
}算法设计（二）：
需要进行的操作：
- 设定一个整形变量 k，初值赋为 0，表示相同元素个数。
- 遍历所有元素，比较 $ item $ 和 $ a_i $：
- 若满足关系 $ item = a_i $， k 值增 1。
- 若不满足关系 $ item = a_i $，将第 i 个元素移到第 i-k 的位置；
时间复杂度：$ O(n) $。
/**
* 删除长度为 n 的线性表 A 中数据信息为 item 的元素
*/
void DELETE_ITEM_LIST2(ElemType A[], int &n, ElemType item) {
int k = 0;
for (int i = 0; i <= n-1; i++) {
if (item == A[i]) {
k++; // 满足关系，k 值增 1
} else {
A[i-k] = A[i]; // 不满足关系，将第 i 个元素移到第 i-k 处。
}
}
n -= k; // 修改表的长度（表长减 k）
}3.1.7 删除长度为 n 的线性表 A 中重复出现的元素
算法设计
需要进行的操作：
- 从线性表的第 1 个元素，到最后 1 个元素。对于第 i 个元素，从第 i+1 个元素开始逐个进行比较。
- 如果存在 $ a_j = a_i $，则删除 $ a_j $。
- 若不存在 $ a_j = a_i $，则继续向后进行比较。
时间复杂度：$ O(n^2) $
/**
* 删除长度为 n 的线性表 A 中重复出现的元素
*/
void PURGE_LIST(ElemType A[], int &n) {
for (int i = 0; i <= n-1; i++) {
for (int j = i+1; j <= n-1;) { // 从第 i+1 个元素开始逐个与第 i 个元素进行比较
if (A[i] == A[j]) { // 若 A[j] 与 A[i] 相同
DELETE_LIST(A, n, j+1); // 删除元素 A[j]
} else {
j++;
}
}
}
}3.2 线性链表
3.2.1 线性链表的结构定义
typedef int ElemType;
typedef struct Node {
ElemType data;
struct Node *link;
}LNode, *LinkList;
LinkList list; // 线性链表 list
LNode *p; // 指向链结点的指针 p3.2.2 建立一个线性链表
算法设计：
需要进行的操作：
对于每个元素：
- 申请一个新的链结点
- 获取一个新的数据元素赋值给新的链结点数据域
- 将新的链结点指针域置空
- 将新的链结点连接到链表尾部
- 移动指针到尾部，继续重复 1、2、3、4、5的操作。
时间复杂度：$ O(n) $
/**
* 建立一个线性链表
*/
LinkList CREAT_LINKLIST(int n) {
LNode *p = NULL, *q = NULL;
LinkList list = NULL;
for (int i = 1; i <= n; i++) {
p = (LinkList)malloc(sizeof(LNode)); // 申请一个新的链结点
scanf("%d", &p->data); // 获取一个数据元素
p->link = NULL; // 新的链结点指针域置空
if (list == NULL) {
list = p;
} else {
q->link = p; // 将新的链结点链接在链表尾部
}
q = p; // 指针变量 q 总是指向链表尾部
}
return list;
}3.2.3 求线性链表的长度
非递归算法
时间复杂度：$ O(n) $
/**
* 求线性链表的长度(非递归算法)
*/
int LENGTH_LINKLIST(LinkList list) {
LNode *p = list;
int n = 0; // 链表长度初值置 0
while (p != NULL) {
n++;
p = p->link;
}
return n; // 返回链表长度
}递归算法
时间复杂度：$ O(n) $
/**
* 求线性链表的长度(递归算法)
*/
int LENGTH_LINKLIST_2(LinkList list) {
if(list != NULL) {
return 1 + LENGTH_LINKLIST_2(list->link);
} else {
return 0;
}
}3.2.4 在非空线性链表的第一个结点前插入一个数据信息为 item 的新结点
时间复杂度：$ O(1) $
/**
* 在非空线性链表的第一个结点前插入一个数据信息为 item 的新结点
*/
void INSERT_ITEM_BEFORE_FIRST_LINKNODE_LINKLIST(LinkList &list, ElemType item) {
/* list 指向第一个链结点指针 */
LNode *p = (LinkList)malloc(sizeof(LNode)); // 申请一个新的链结点
p->data = item; // 将 item 送新结点数据域
p->link = list; // 将 list 送新结点指针域
list = p; // 修改指针 list 的指向
}3.2.5 在线性链表中由指针 q 指的链结点之后插入一个数据信息为 item 的链结点
时间复杂度：$ O(1) $
/**
* 在线性链表中由指针 q 指的链结点之后插入一个数据信息为 item 的链结点
*/
void INSERT_ITEM_AFTER_LINKNODE_LINKLIST(LinkList &list, LNode *q, ElemType item) {
LNode *p;
p = (LinkList)malloc(sizeof(LNode));
p->data = item; // 将item送新结点数据域
if (list == NULL) { // 若原链表为空
list = p;
p->link = NULL;
} else { // 若原链表为非空
p->link = q->link;
q->link = p;
}
}3.2.6 从非空线性链表中删除 q 指的链结点，设 q 的直接前驱结点由 r 指出
时间复杂度：$ O(1) $
/**
* 从非空线性链表中删除 q 指的链结点，设 q 的直接前驱结点由 r 指出
*/
void DELETE_QLINKNODE_LINKLIST(LinkList &list, LNode *r, LNode *q)
{
if (q == list) {
list = q->link; // 删除链表的第一个链结点
} else {
r->link = q->link; // 删除 q 指的链结点
}
free(q); // 释放被删除的结点空间
}3.2.7 从非空线性链表中删除 q 指的链结点
时间复杂度：$ O(n) $
/**
* 从非空线性链表中删除 q 指的链结点
*/
void DELETE_QLINKNODE_LINKLIST_2(LinkList &list, LNode *q) {
if (q == list) { // 当 q 指的链结点为第一个结点
list = q->link; // 删除 q 指的链结点
free(q); // 释放被删除结点的空间
} else {
LNode *r = list;
// 寻找 q 结点的直接前驱 r
while ((r->link != q) && (r->link != NULL)) {
r = r->link; // 移向下一个链结点
}
if (r->link != NULL) { // 找到 q 节点的直接前驱
r->link = q->link; // 删除 q 指的链结点
free(q); // 释放被删除结点的空间
}
}
}3.3 循环链表
3.3.1 循环链表定义
循环链表是指链表中最后那个链结点的指针域存放指向链表最前面那个结点的指针 ，整个链表形成一个环。
3.3.2 创建循环链表
/**
* 建立一个线性循环链表
*/
LinkList CREAT_CYCLE_LINKLIST(int n) {
LNode *p = NULL, *q = NULL;
LinkList list = NULL;
for (int i = 1; i <= n; i++) {
p = (LinkList)malloc(sizeof(LNode)); // 申请一个新的链结点
scanf("%d",&p->data); // 获取一个数据元素
p->link = NULL; // 新的链结点指针域置空
if (list == NULL) {
list = p;
} else {
q->link = p; // 将新的链结点链接在链表尾部
}
q = p; // 指针变量 q 总是指向链表尾部
}
p->link = list;
return list;
}3.3.3 求循环链表的长度
int LENGTH_CYCLE_LINKLIST(LinkList list) {
LinkList p = list;
int n = 0; /* 链表的长度置初值 0 */
do {
p = p->link;
n++;
} while ( p != list);
return n; /* 返回链表的长度 n */
}3.3.4 约瑟夫问题
void JOSEPH_CIRCLE(int n, int m, int k) {
LNode *p, *r = NULL;
LinkList list = NULL;
/* 建立一个循环列表 */
for (int i = 1; i <= n; i++) {
p = (LinkList)malloc(sizeof(LNode));
p->data = i;
if (list == NULL) {
list = p;
r = list;
}
r->link = p;
r = p;
}
r->link = list;
/* 完成循环列表建立 */
/* 寻找第一个节点 */
p = list;
for (int i = 1; i < k; i++) {
r = p; // 保存前驱节点
p = p->link;
} // 此时 p 指向第 1 个人
/* 依次删除节点 */
while (p->link != p) {
for (int i = 1; i < m; i++) {
r = p;
p = p->link;
} // p 指向第 m 个人，r 指向第 m-1 个人
r->link = p->link;
printf("%4d",p->data);
free(p);
p = r->link;
}
printf("\n最后删除的节点是：%4d\n",p->data);
}3.4 双向链表
3.4.1 双向链表的定义
双向链表是指链表的每一个结点中除了数据域以外设置两个指针域，其中之一指向结点的直接前驱结点，另外一个指向结点的直接后继结点。
typedef int ElemType;
typedef struct Node {
ElemType data;
struct Node *llink, *rlink;
}DNode, *DLinkList;3.4.2 在带有头结点的双向循环链表中第 1 个数据域内容为 x 的结点右边插入一个数据信息为 item 的新结点
算法设计
需要进行的操作：
- 找到满足条件的结点；
- 若找到，构造一个新的链结点；
- 将新结点插到满足条件的结点后面。
/**
* 在带有头结点的双向循环链表中第 1 个数据域内容为 x 的结点右边插入一个数据信息为 item 的新结点
*/
int INSERT_DOUBLY_LINKLIST(DLinkList &list, ElemType x, ElemType item) {
DNode *p,*q;
q = list->rlink; /* q 初始指向头结点的下一个结点 */
while (q != list && q->data != x) { /* 寻找满足条件的链结点 */
q = q->rlink;
}
if (q == list) { /* 没有找到满足条件的结点 */
ERRORMESSAGE("无满足条件的节点");
return -1;
}
p = (DLinkList)malloc(sizeof(DNode)); /* 申请一个新的结点 */
p->data = item;
p->llink = q;
p->rlink = q->rlink;
q->rlink->llink = p;
q->rlink = p;
return 1; /* 插入成功 */
}3.4.3 从带有头结点的双向链表中删除第 1 个数据域内容为 x 的结点
算法设计
需要进行的操作：
- 找到满足条件的结点；
- 若找到，删除（并释放）满足条件的结点。
/** * 从带有头结点的双向链表中删除第 1 个数据域内容为 x 的结点 */ int DELETE_DOUBLY_LINKLIST(DLinkList &list, ElemType x) { DNode *q; q = list->rlink; /* q 初始指向头结点的下一个结点 */ while (q != list && q->data != x) { /* 寻找满足条件的链结点 */ q = q->rlink; } if (q == list) { /* 没有找到满足条件的结点 */ ERRORMESSAGE("无满足条件的节点"); return -1; } q->llink->rlink = q->rlink; q->rlink->llink = q->llink; free(q); /* 释放被删除的结点的存储空间 */ return 1; /* 删除成功 */ }
评论（没有评论）