目录
一、绪论Introduction
1、数据结构
2、逻辑结构（数据元素之间的相互关系）
3、物理结构（数据逻辑结构在计算机中的存储形式）
4、数据类型（一组性质相同的值的集合及定义在此集合上的一些操作的总称）
5、算法
二、线性表List
1、基本概念
一、绪论Introduction
1、数据结构
（1）数据结构是研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。
（2）数据元素：组成数据的有一定意义的基本单位，也被称为记录。
（3）数据项：数据不可分割的最小单位，一个数据元素可以由若干个数据项组成。
（4）数据对象：性质相同的数据元素的集合，数据的子集。
（5）结构：不同数据元素之间非独立而是存在特定的关系。
2、逻辑结构（数据元素之间的相互关系）
（1）集合结构：数据元素除了同属于一个集合范围内，它们之间就没有其他关系。
（2）线性结构：数据元素之间是一对一的关系。
（3）树形结构：数据元素之间存在一对多的层次关系。
（4）图形结构：数据元素之间是多对多的关系。从左到右依次为集合、线性表、树、图结构
3、物理结构（数据逻辑结构在计算机中的存储形式）
（1）顺序存储结构：把数据元素存放在地址连续的存储单元里。
（2）链式存储结构：把数据元素存放在任意存储单元里，通过地址找到相关联数据元素位置。
4、数据类型（一组性质相同的值的集合及定义在此集合上的一些操作的总称）
（1）原子类型：不可再分的，包括整型、实型、字符型等。
（2）结构类型：可再分解的，例如整型数组是由若干个整型数据组成的。
（3）抽象数据类型ADT（Abstract Data Type）：一个数学模型及定义在该模型上的一组操作，体现了程序设计中问题分解、抽象和信息隐藏的特性。
5、算法
（1）算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，每条指令执行一或多个操作。
（2）基本特性：输入、输出、有穷性、确定性和可行性。
（3）设计要求：正确性、可读性、健壮性、时间效率高和存储量低。
（4）效率度量方法：事后统计（写好程序比较编译运行时间）和事前分析估算（在编程前对算法估算）
（5）程序运行时间：依赖于算法好坏、问题输入规模（执行量的多少）。
（6）函数的渐近增长：给定函数f(n)和g(n)，若 ∃ N ∈ Z，使所有n > N，f(n)总是比g(n)大，那么就说f(n)增长渐近快于g(n)。
（7）算法的时间复杂度：大O记法。
(i) 用常数１取代运行时间中的所有加法常数，即O(1)。
(ii) 在修改后的运行次数函数中只保留最高阶项。
(iii) 最高阶项的系数为１，得到结果就是大O阶。
常见时间复杂度如下：
常见时间复杂度所耗费时间从小到大依次是：
（8）算法的空间复杂度：即对计算机的内存占用空间需求。
二、线性表List
1、基本概念
（1）线性表是零或多个数据元素的有限序列。
（2）数组长度指存储空间长度，线性表长度指数据元素个数。
（3）顺序存储结构的三个属性：数组data，数组长度MAXSIZE，线性表当前长度length；查找时间复杂度为O(1)，插入删除的时间复杂度为O(n)。
插入算法思路：
(i) 如果插入位置不合理，抛出异常；
(ii) 如果线性表长度 ≥ 数组长度，则抛出异常或动态增加容量；
(iii) 从最后一个元素开始向前遍历到第 i 个位置，分别将它们都向后移动一个位置；
(iv) 将要插入的元素填入位置i处，表长+1即可。
删除算法思路：
(i) 如果删除位置不合理，抛出异常；
(ii) 取出删除元素；
(iii) 从删除元素位置开始遍历到最后一个元素位置，将它们都向前移动一个位置，表长-1即可。
（4）链式存储结构，查找时间复杂度为O(n)，插入删除时间复杂度为O(1)。
(i) 结点（Node）包含数据域（存储数据元素信息）和指针域（存储直接后继位置）。
(ii) n个结点连接成一个链表，即线性表的链式存储结构。
(iii) 链表第一个结点的存储位置称为头指针（链表的必要元素），最后一个结点指针为空NULL。
(iv) 常在单链表的第一个结点前附设一个结点，称为头结点，其数据域可以不存储任何信息，指针域则存储指向第一个结点的指针。头结点非必需元素，若线性表为空表，则头结点指针域为空NULL。
假设p是指向线性表第 i 个元素的指针，则数据域表示为p -> data，值为数据元素；指针域表示为p -> next，值为一个指针，指向第 i+1个元素，关系如下图所示：
（5）静态链表：用数组描述的链表
(i) 数组元素都由data和cur组成，前者存放数据元素，后者相当于单链表中的指针，存放该元素的后继在数组的下标。如下将甲、乙、丙、丁、戊等数据存入静态链表：
(ii) 优点是在插入删除操作中只需要修改cur而不用移动元素，缺点是仍连续存储，表长难以确定。
（6）循环链表（Circular Linked List）：终端结点的指针由空NULL改为指向头结点即形成循环。
（7）双向链表（Double Linked List）：每个结点再额外设置一个指向其前驱结点的指针域即可。
双向链表的结点表示关系有p -> next -> prior相当于 p 也相当于p -> prior -> next。
(i)插入操作顺序思路：s -> prior = p; s -> next = p -> next; p ->next ->prior = s; p ->next = s;
(ii)删除操作顺序思路：p -> prior -> next = p ->next; p ->next ->prior = p -> prior; free (p);
