概念：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
三要素：
-
逻辑结构
概念：指数据元素之间的逻辑关系。
分类：
- 线性结构：线性表（栈、队列、串、数组…）。
- 非线性结构：集合、树形结构、图状结构。
-
存储结构（物理结构）
概念：指数据结构在计算机中的表示。
分类：顺序存储、链式存储、索引存储、散列存储。
-
数据运算
概念：包括运算的定义和实现。
概念：对特定问题求解步骤的一种描述。
重要特性：有穷性、确定性、可行性、输入、输出。
优秀标准：正确性、可读性、健壮性、效率、低存储量需求。
复杂度：
-
时间复杂度
概念：算法中所有语句的执行次数之和。
分类：最好时间复杂度、平均时间复杂度、最坏时间复杂度。
常见时间复杂度： O ( 1 ) < O ( l o g 2 n ) < O ( n ) < O ( n l o g 2 n ) < O ( n 2 ) < O ( n 3 ) < O ( 2 n ) < O ( n ! ) < O ( n n ) {color{Purple}Oleft ( 1right )}<{color{Green}Oleft ( log_{2}nright )}<{color{Orange}Oleft ( nright )}<{color{Magenta}Oleft ( nlog_{2}nright )}<{color{DarkOrange}Oleft ( n^{2}right )}<{color{DarkBlue}Oleft ( n^{3}right )}<{color{blue}Oleft ( 2^{n}right )}<{{color{Cyan}Oleft ( n!right )}}<{color{black}Oleft ( n^{n}right )} O(1)
-
空间复杂度
概念：算法所耗费的存储空间
注：当算法所需的辅助空间为常量时，空间复杂度为 O ( 1 ) {color{Purple}Oleft ( 1right )} O(1)
-
计算规则
- 加法规则： O ( f ( n ) ) + O ( g ( n ) ) = O ( m a x ( f ( n ) , g ( n ) ) ) Oleft ( {color{Green}fleft ( nright )}right )+Oleft ( {color{Blue}gleft ( nright )}right )=Oleft ( maxleft ( {color{Green}fleft ( nright )},{color{Blue}gleft ( nright )}right )right ) O(f(n))+O(g(n))=O(max(f(n),g(n)))
- 乘法规则： O ( f ( n ) ) ∗ O ( g ( n ) ) = O ( f ( n ) ∗ g ( n ) ) Oleft ( {color{Green}fleft ( nright )}right )*Oleft ( {color{Blue}gleft ( nright )}right )=Oleft ( {color{Green}fleft ( nright )}*{color{Blue}gleft ( nright )}right ) O(f(n))∗O(g(n))=O(f(n)∗g(n))
概念：线性表是具有相同数据类型的n个数据元素的有限序列。
特点：
- 表中元素个数有限
- 表中元素具有逻辑上的顺序性，有先后次序
- 每个元素数据类型相同，占用相同大小的存储空间
基本操作注：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是存储结构
| 函数 | 描述 |
|---|---|
| InitList(&L) | 初始化表，构造一个空的线性表 |
| Length(L) | 求表长，返回线性表L中数据元素的个数 |
| LocateElem(L,e) | 按值查找 |
| GetElem(L,i) | 按位查找，获取表L中第i个位置的元素 |
| ListInsert(&L,i,e) | 在表L的第i个位置插入元素e |
| ListDelete(&L,i,&e) | 删除表中第i个位置的元素，并用e返回删除元素的值 |
| PrintList(L) | 遍历输出线性表L |
| Empty(L) | 若L为空表返回true，否则返回false |
| DestroyList(&L) | 销毁线性表并释放占用的内存空间 |
注：考试尽量使用这些函数名称，方便老师阅卷
