一、数据结构绪论

• 逻辑结构与物理结构
  • 逻辑结构：集合、线性（一对一）、树（一对多）、图（多对多）
  • 物理结构：顺序存储结构、链式储存结构
• 抽象数据类型 （Abstract Data Type,ADT）：是指一个数学模型及定义在该模型上的一组操作

  标准格式
  　　　ADT　抽象数据类型名
  　　　Date 数据元素之间的逻辑定义
  Operation
  操作1
  初始条件
  操作结果描述
  操作2
  ......
  操作3
  ......
  endADT

二、算法

• 算法特性：输入输出、确定性、又穷性、可行性
• 算法要求：正确性、健壮性、可读性、时间效率高和存储量低
• 算法时间复杂度
  • 推导大O阶方法
    1.用常数1取代运行时间中所有加法常数
    2.在修改后的运行函数中，只保留最高位
    3.如果最高阶项存在且不是1，则去除与这个项相乘的常数
    得到的结果是大O阶

三、线性表

• 定义：零个或多个数据元素的有限序列
• 抽象数据结构

  ADT 线性表
  Data ：
  线性表的数据对象集合为{a1，a2，......，an}，每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
  Operation：

InitList(&l)

操作结果：构造一个空的线性表L

DestroyList(&l)

初始条件：线性表已存在
操作结果：销毁线性表L

ClearList(&l)

初始条件：线性表已存在
操作结果：置线性表L为空表

ListEmpty(L)

初始条件：线性表已存在
操作结果：若线性表L为空表，则返回TRUE，否则返回FALSE

ListLenght(L)

初始条件：线性表已存在
操作结果：返回线性表L数据元素个数

GetElem(L,i,&e)

初始条件：线性表已存在（1≤i≤ListLenght(L)）
操作结果：用e返回线性表L中第i个数据元素的值

locatElem(L,e,comare())

初始条件：线性表已存在,comare()是数据元素判定函数
操作结果：返回线性表L中第1个与e满足关系comare()的数据元素的位序

PriorElem(L,cur_e,&pre_e)

初始条件：线性表已存在
操作结果：若cur_e是线性表L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义

NextElem(L,cur_e,&)

初始条件：线性表已存在
操作结果：若cur_e是线性表L的数据元素，且不是第最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义

ListInsert(&L,i,e)

初始条件：线性表已存在（1≤i≤ListLenght(L)+1）
操作结果：在线性表L中第i个数据元素之前插入新元素e，L长度加1

ListDelete(&L,i,&e)

初始条件：线性表已存在（1≤i≤ListLenght(L)）
操作结果：删除线性表L中第i个数据元素，用e返回其值，L长度减1

ListTraverse(L,visit())

初始条件：线性表已存在
操作结果：依次对线性表L的每个数据元素调用visit()函数，一旦visit()失败，则操作失败}ADT List

• 顺序储存结构代码
  #define MAXSIZE 20
  typedef int ElemType；
  typedef struct{
  ElemType data[MAXSIZE];
  int length;
  }SqList;

单链表、静态链表、循环链表、双向链表

• 单链表
• 单链表储存结构代码
  typedef struct node{
  ElemType data；
  struct Node *next；
  } Node；
  typedef struct Node *LinkList；

• 静态链表（早期没有指针，用数组代替指针）
• 静态链表的储存结构代码
  #define MAXSIZE 1000
  typedef struct{
  Elemtype data；
  int cur；/游标/
  }Component,StaticLinkList[MAXSIZE];
  十字链表

  容易求得顶点的出度和入度

  • 邻接多重表

    
    边表结点结构
  邻接多重表
  • 图的遍历
    • 深度优先遍历
      从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发，深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到（邻接表）
    • 广度优先遍历
      类似于树的前序遍历（队列）
  • 最小生成树
    • （普里姆）prim算法
    • （克鲁斯卡尔）kruskal算法
  • 最短路径
    • （地杰斯特拉）dijkstr算法
    • （弗洛伊德）floyd算法
  • 拓扑排序

  八、查找

  • 顺序表查找
  • 有序表查找
    • 有序查找
    • 斐波那契查找
    • 插值查找
  • 线性索引查找
    • 稠密查找
    • 到排查找
    • 分块索引
  • 二叉排序树
  • 平衡二叉树
  • 多路查找树（B树）
  • 散列表查找（哈希表）概述
  • 散列函数构造方法
  • 处理散列冲突方法
  • 散列表的查找实现

  九、排序

  • 冒泡排序
  • 简单选择排序
  • 直接插入排序
  • 希尔排序
  • 堆排序
  • 归并排序
  • 快速排序