[数据结构] 特殊线性表：广义表 广义表广义表又称列表(List)，是 n≥0 个元素 (a1,a2,a3,...,an) 的优先序列，其中ai是原子数据类型或者是一个广义表，记LS=(a1,a2,a3,...,an)LS : 表示表名ai : 表示元素，通常小写字母表示元素是原子数据类型，大写字母表示元素是广义表广义表表头广义表的第一个元素(a1),可以是一个原子类型也可以是一个广义表广义表表尾广义表中除了第一个元素之外的其他元素组成的广义表 --> 表尾是一个表广义表可以使用 "()" 表示，其中()的最深层数表示表的深度，表的次序 ：一个直接前驱，一个直接后继例如LS = (a1) : LS中有一个元素 表头为 a1，表尾为 ()LS = (a1, a2) ：LS中有两个元素 表头为 a1，表尾为 (a2)LS = (a1, ()) ：LS中有两个元素 表头为 a1，表尾为 (())LS = (a1, a2,()) ：LS中有三个元素 表头为 a1，表尾为 (a2,())表的共享两个广义表 A，B, 其中A和 B 的关系 B = (A)表的递归有一个广义表 A，其中 A = (A)

[数据结构] 线性表之链式存储：单链表 定义线性表的链式存储又称单链表，它是只通过一组任意的存储单元来存储线性表的数据元素。为建立数据元素之间的线性关系，每个链表节点除了存放元素自身的信息外，还需要存放指向其后继的指针。typedef struct Node{ ElementType data; // 数据域，存放数据 struct Node *next; // 指针域，存放其后继节点的地址 }LNode;头指针和头结点的区别不管带不带头节点，头指针始终指向链表的第一个节点，而头结点是带头结点的链表中的第一个节点，节点数据域通常不存储信息。头结点的有点：由于第一个数据节点的位置被存放在头结点的指针域中，云次在链表的第一个位置上的操作和在表的其他位置操作一致，无需进行特殊处理。无论链表是否为空，其头指针都指向头结点的非空指针(空表中头结点的指针域为空)，因此空表和非空表的处理也得到了统一。链表基本操作InitLinkList(&L); // 初始化链表 BeforeHeader(&L, data); // 头插法 AfterHeader(&L, data); // 尾插法 BeforeInsert(p, data); // p 节点之前插入 AfterInsert(p, data); // p 节点之后插入 BeforeDelete(p, &data); // 删除 p 节点之前节点 AfterDelete(p, &data); // 删除 p 节点之后节点 ...特殊链表双链表循环链表循环双链表静态链表

[数据结构] 王道数据结构2023 P18_03 问题描述对长度为n的顺序表L，编写一个时间复杂度为O(n)，空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素实现代码bool DeleteSelectX(SeqList &L,ElementType x){ if(L.lenght == 0){ printf("线性表为空\n"); return false; } int i,j; for(i = 0,j = 0;i < L.lenght;i++){ if(L.data[i] != x){ L.data[j] = L.data[i]; j++; } } L.lenght = j; return true; }全部代码#include <stdio.h> #include <stdbool.h> #include <stdlib.h> #define ElementType int #define InitSize 100 int arr[] = {1,2,3,4,1,6,1,8,9,0}; typedef struct { ElementType *data; int MaxLen,lenght; }SeqList; void InitSeqList(SeqList &L){ L.data = (ElementType *)malloc(sizeof(ElementType) * InitSize); L.MaxLen = InitSize; L.lenght = 0; } bool InsertELem(SeqList &L,int i,ElementType data){ if(i < 1 || i > L.lenght + 1){ printf("位置不合法\n"); return false; } if(L.lenght + 1 > L.MaxLen){ printf("线性表已满\n"); return false; } for(int j = L.lenght;j >= i;j--){ L.data[j] = L.data[j - 1]; } L.data[i - 1] = data; L.lenght += 1; return true; } void ShowList(SeqList L){ for(int i = 0;i < L.lenght;i++){ printf("%d ", L.data[i]); } printf("\n"); } bool DeleteSelectX(SeqList &L,ElementType x){ if(L.lenght == 0){ printf("线性表为空\n"); return false; } int i,j; for(i = 0,j = 0;i < L.lenght;i++){ if(L.data[i] != x){ L.data[j] = L.data[i]; j++; } } L.lenght = j; return true; } int main() { SeqList L; InitSeqList(L); for(int i = 0;i < 10;i++){ InsertELem(L,i + 1, arr[i]); } DeleteSelectX(L,1); ShowList(L); return 0; }

[数据结构] 线性表之顺序存储：顺序表 顺序表定义线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。{message type="warning" content="线性表中元素的位序是从1开始的，但数组的下标是从0开始的"/}静态数组和动态数组的区别一维数组可以是静态分配的，也可以是动态分配的。静态分配由于数组大小和空间已经固定，所以一旦空间占满，在加入新的数据就会产生 数据溢出，进而导致程序运行崩溃。动态分配存储数组的空间是由程序执行过程通过动态存储分配语句分配的，一旦数据空间沾满，就可以另辟新的一块更大的存储空间，用以代替原来的存储空间，达到扩充空间的目的。顺序表空间分配#define ElementType int #define MaxSize 100 // 静态空间分配 typedef struct { ElementType data[MaxSize]; // 定义顺序表元素 int lenght; // 当前元素长度 }SeqList; // 动态空间分配 typedef struct { ElementType *data; // 定义顺序表元素 int MaxLen; // 顺序表最大长度 int lenght; // 当前元素长度 }SeqList;顺序表优点随机访问，通过首地址和元素位序可快速找到指定元素存储密度高，每个节点只存储数据元素逻辑上相邻的元素物理上也相邻顺序表缺点插入和删除需要移动大量元素需要连续内存空间

[数据结构] 王道数据结构2023 P18_02 问题描述设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)问题分析无代码实现bool ReverseList(SeqList &L){ if(L.lenght == 0){ printf("内容为空\n"); return false; } ElementType temp; for(int i = 0,j = L.lenght - 1;i < j;i++,j--){ temp = L.data[i]; L.data[i] = L.data[j]; L.data[j] = temp; } return true; }算法分析无时间复杂度 O(n)空间复杂度 O(1)完整代码#include <stdio.h> #include <stdbool.h> #include <stdlib.h> #define ElementType int #define InitSize 100 int arr[] = {1,2,3,4,5,6,7,8,9,0}; typedef struct { ElementType *data; int MaxLen,lenght; }SeqList; void InitSeqList(SeqList &L){ L.data = (ElementType *)malloc(sizeof(ElementType) * InitSize); L.MaxLen = InitSize; L.lenght = 0; } bool InsertELem(SeqList &L,int i,ElementType data){ if(i < 1 || i > L.lenght + 1){ printf("位置不合法\n"); return false; } if(L.lenght + 1 > L.MaxLen){ printf("线性表已满\n"); return false; } for(int j = L.lenght;j >= i;j--){ L.data[j] = L.data[j - 1]; } L.data[i - 1] = data; L.lenght += 1; return true; } bool ReverseList(SeqList &L){ if(L.lenght == 0){ printf("内容为空\n"); return false; } ElementType temp; for(int i = 0,j = L.lenght - 1;i < j;i++,j--){ temp = L.data[i]; L.data[i] = L.data[j]; L.data[j] = temp; } return true; } void ShowList(SeqList L){ for(int i = 0;i < L.lenght;i++){ printf("%d ", L.data[i]); } printf("\n"); } int main() { SeqList L; InitSeqList(L); for(int i = 0;i < 10;i++){ InsertELem(L,i + 1, arr[i]); } if(!ReverseList(L)){ printf("线性表反转失败\n"); }else{ printf("线性表反转成功:"); ShowList(L); } return 0; }

[数据结构] 王道数据结构2023 P18_01 问题描述从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删除的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。问题分析无代码实现bool DeleteMin(SeqList &L,ElementType &min){ if(L.lenght == 0){ printf("顺序表为空"); return false; } int flag = 0; for(int i = 0;i < L.lenght;i++){ if(L.data[i] < L.data[flag]){ flag = i; } } min = L.data[flag]; if(flag != L.lenght - 1){ L.data[flag] = L.data[L.lenght - 1]; } L.lenght -= 1; return true; }算法分析无时间复杂度 O(n)空间复杂度 O(1)完整代码#include <stdio.h> #include <stdbool.h> #include <stdlib.h> #define ElementType int #define InitSize 100 int arr[] = {1,2,3,4,5,6,7,8,9,0}; typedef struct { ElementType *data; int MaxLen,lenght; }SeqList; void InitSeqList(SeqList &L){ L.data = (ElementType *)malloc(sizeof(ElementType) * InitSize); L.MaxLen = InitSize; L.lenght = 0; } bool InsertELem(SeqList &L,int i,ElementType data){ if(i < 1 || i > L.lenght + 1){ printf("位置不合法\n"); return false; } if(L.lenght + 1 > L.MaxLen){ printf("线性表已满\n"); return false; } for(int j = L.lenght;j >= i;j--){ L.data[j] = L.data[j - 1]; } L.data[i - 1] = data; L.lenght += 1; return true; } bool DeleteMin(SeqList &L,ElementType &min){ if(L.lenght == 0){ printf("顺序表为空"); return false; } int flag = 0; for(int i = 0;i < L.lenght;i++){ if(L.data[i] < L.data[flag]){ flag = i; } } min = L.data[flag]; if(flag != L.lenght - 1){ L.data[flag] = L.data[L.lenght - 1]; } L.lenght -= 1; return true; } int main() { SeqList L; InitSeqList(L); for(int i = 0;i < 10;i++){ InsertELem(L,i + 1, arr[i]); } int min; if(DeleteMin(L,min)){ printf("删除元素：%d\n", min); for(int i = 0;i < L.lenght;i++){ printf("%d ", L.data[i]); } }else{ printf("删除失败\n"); } return 0; }

[数据结构] 线性表 线性表的定义线性表是具有n个数据元素的有限序列，其中n为线性表的长度，当n=0时，线性表是空表，若用L表示线性表：L = {a1,a2,a3,...,an}其中a1为第一个数据元素，又称表头元素，an为最后一个数据元素，又称表尾元素；除第一个元素外，每个元素都有唯一的前驱；除最后一个元素，每个元素都有唯一的后继。线性表的特点表中元素个数有限表中元素具有逻辑上的顺序性，表中元素都有先后顺序表中元素都是数据元素，每个元素都是单个元素表中元素数据类型相同，即：每个元素占有空间大小相同表中元素具有抽象性，即：仅讨论元素之间的逻辑关系，而不考虑元素究竟表达什么内容线性表的基本操作InitList(&L) : 初始化表ListInsert(&L,i,data) : 插入操作，将元素插入到第i个位置ListDelete(&L,i,&data) : 删除操作，删除第i个元素ListModify(&L,i,data) : 修改操作ListFindByValue(&L,data) : 查找操作，按值查找ListFindByIndex(&L,i,&data) : 查找操作，按位置查找ListDestory(&L) : 销毁表getLength(L) : 获取表长度Empty(L) : 线性表判空