数据结构

重庆邮电大学数据结构课程笔记，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间关系和运算的学科。

数据结构

• 图
  • 图的定义和术语
    • 基本定义
      • 顶点
    • 连通图
  • 图的存储结构
    • 数组表示法 邻接矩阵法
      • 子主题
      • 构造一个具有n个顶点和e条边的无向图的时间复杂度 O（n2 + e*n）
    • 邻接表
      • 建表的时间复杂度： 1.顶点信息为顶点的编号时 O（n+e） 2.否则 O（n*e）
    • 十字链表
      • • tailed:弧头所在的位置 headvex:弧尾所在的位置 hlink:弧头相同的下一条弧 think:弧尾相同的下一条弧
    • 邻接多重表
  • 图的遍历
    • 深度优先遍历DFS
      • 基本思想
        • 类似于树的先根遍历
        • 从一个未被访问过的点开始，一直访到底，再递归回来
      • 时间复杂度
        • 二维数组（邻接矩阵）：O（n2）
        • 邻接表：O（n+e）
    • 广度优先遍历BFS
      • 基本思想
        • 类似于数的层次遍历
        • 从一个未访问过的点开始，先把跟这个点邻接的点访问完，再访问邻接的点的邻接点（用了栈）
      • 时间复杂度
        • 二维数组：O（n2）
        • 邻接表：O（n+e）
  • 图的连通性问题
    • 无向图的连通分量和生成树
    • 有向图的强连通分量
    • 最小生成树
      • MST性质
      • Prim算法
        • 时间复杂度：O（n2） 适用于边多的图
      • Kruskal算法
        • 时间复杂度：O（eloge) e为边数 故适用于边少的图
  • 有向无环图及其应用
    • 定义
    • 拓扑排序
      • 拓扑序列
      • 基本思想
      • 涉及到的代码结构：邻接表
      • 代码
    • 关键路径
      • 一些基本概念
        • AOE网：在一个表示工程的带权有向图中，用顶点表示事件，用边表示活动（例如<v1，v2>表示该边的开始和结束），用边上的权值表示活动的持续时间。 只有当某个顶点代表的事件发生后，从该顶点出发的各活动才能开始。
        • 始点，源点 终点，汇点
        • 路径长度：路径上各个活动所持续的时间之和。 关键路径：从源点到汇点具有最大长度的路径。 关键活动：在关键路径上的活动。
        • 最早发生时间：从v1到vi的最长路径长度 最迟开始时间：在不推迟整个工程完成的前提下，活动ai最迟必须开始进行的时间
      • 关键路径算法的原理：求出所有活动的最早开始时间和最晚开始时间，并且比较他们，如果相等就意味着是关键活动。
      • 算法
      • 算法代码
  • 最短路径
    • 单个源点到其余各顶点的最短路径
      • Dijkstra算法（迪杰斯特拉）
        • 算法思想
        • 时间复杂度：O（n2）
        • 例题
          • 求解过程
    • 每一对顶点之间的最短路径
      • Floyd算法（佛罗伊德）
        • 算法思想
        • 时间复杂度：O（n3）
• 查找
  • 概念
  • 查找算法的分析与应用
  • 静态查找表
    • 概念：只作查找操作的查找表
    • 注意：顺序查找、折半查找都是从数组下标为1开始查找（试具体情况而定）
    • 顺序表的查找
      • 顺序查找
        • 代码
          • /* 无哨兵顺序查找，a为数组，n为要查找的数组个数，key为要查找的关键字 */ int Sequential_Search(int *a,int n,int key) { int i; for(i=1;i<=n;i++) { if (a[i]==key) return i; } return 0; }
          • /* 有哨兵顺序查找 */ int Sequential_Search2(int *a,int n,int key) { int i; a[0]=key; i=n; while(a[i]!=key) { i--; } return i; }
        • 效率
          • 最好：1次 最坏：n次 查找失败时：n+1次
          • 平均查找次数：(n+1)/2
          • 时间复杂度：O(n)
    • 有序表的查找
      • 折半查找
        • 判定树
          • 可以转化成二叉树进行研究
        • 效率
          • 查找成功时的平均查找长度
          • 最大比较次数：log2(n)+1的向下取整
          • 最小比较次数：1
          • 时间复杂度：O(logn)
        • 代码
          • /* 折半查找 */ int Binary_Search(int *a,int n,int key) { int low,high,mid; low=1; /* 定义最低下标为记录首位 */ high=n; /* 定义最高下标为记录末位 */ while(low<=high) { mid=(low+high)/2; /* 折半 */ if (key<a[mid]) /* 若查找值比中值小 */ high=mid-1; /* 最高下标调整到中位下标小一位 */ else if (key>a[mid])/* 若查找值比中值大 */ low=mid+1; /* 最低下标调整到中位下标大一位 */ else { return mid; /* 若相等则说明mid即为查找到的位置 */ } } return 0; }
      • 插值查找
      • 斐波那契查找
    • 静态树表的查找
    • 索引顺序表的查找
  • 动态查找表
    • 概念：在查找的过程种同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。
    • 二叉排序树 二叉查找树
      • 定义：
      • 二叉排序树的结构
        • /* 二叉树的二叉链表结点结构定义 */ typedef struct BiTNode /* 结点结构 */ { int data; /* 结点数据 */ struct BiTNode *lchild, *rchild; /* 左右孩子指针 */ } BiTNode, *BiTree;
      • 二叉查找树的查找
        • /* 递归查找二叉排序树T中是否存在key, */ /* 指针f指向T的双亲，其初始调用值为NULL */ /* 若查找成功，则指针p指向该数据元素结点，并返回TRUE */ /* 否则指针p指向查找路径上访问的最后一个结点并返回FALSE */ Status SearchBST(BiTree T, int key, BiTree f, BiTree *p) { if (!T) /*T为空，查找不成功 */ { *p = f; return FALSE; } else if (key==T->data) /* 查找成功 */ { *p = T; return TRUE; } else if (key<T->data) return SearchBST(T->lchild, key, T, p); /* 在左子树中继续查找 */ else return SearchBST(T->rchild, key, T, p); /* 在右子树中继续查找 */ }
        • 时间复杂度：O(logn)
      • 二叉排序树的插入
        • 算法流程： （1）判断要插入的元素是否已存在在排序树里； （2）为新插入的节点分配内存； （3）判断原树是否为空树，如果是空树，就将新插入的节点当作根节点（*T=s）； （4）不是空树的时候，判断要插入的数据和父节点数据的大小，并插入
          • /* 当二叉排序树T中不存在关键字等于key的数据元素时， */ /* 插入key并返回TRUE，否则返回FALSE */ Status InsertBST(BiTree *T, int key) { BiTree p,s; if (!SearchBST(*T, key, NULL, &p)) /* 查找不成功 */ { s = (BiTree)malloc(sizeof(BiTNode)); s->data = key; s->lchild = s->rchild = NULL; if (!p) *T = s; /* 插入s为新的根结点 */ else if (key<p->data) p->lchild = s; /* 插入s为左孩子 */ else p->rchild = s; /* 插入s为右孩子 */ return TRUE; } else return FALSE; /* 树中已有关键字相同的结点，不再插入 */ }
      • 二叉排序树的构建
        • 代码实现
      • 二叉排序树的删除
        • 算法流程： （1）判断*T是否为空； （2）右子树空只需接左子树 （3）左子树空只需接右子树 （4）左右都不空
          • /* 从二叉排序树中删除结点p，并重接它的左或右子树。 */ Status Delete(BiTree *p) { BiTree q,s; if((*p)->rchild==NULL) /* 右子树空则只需重接它的左子树（待删结点是叶子也走此分支) */ { q=*p; *p=(*p)->lchild; free(q); } else if((*p)->lchild==NULL) /* 只需重接它的右子树 */ { q=*p; *p=(*p)->rchild; free(q); } else /* 左右子树均不空 */ { q=*p; s=(*p)->lchild; while(s->rchild) /* 转左，然后向右到尽头（找待删结点的前驱） */ { q=s; s=s->rchild; } (*p)->data=s->data; /* s指向被删结点的直接前驱（将被删结点前驱的值取代被删结点的值） */ if(q!=*p) q->rchild=s->lchild; /* 重接q的右子树 */ else q->lchild=s->lchild; /* 重接q的左子树 */ free(s); } return TRUE; }
          • /* 若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点, */ /* 并返回TRUE；否则返回FALSE。 */ Status DeleteBST(BiTree *T,int key) { if(!*T) /* 不存在关键字等于key的数据元素 */ return FALSE; else { if (key==(*T)->data) /* 找到关键字等于key的数据元素 */ return Delete(T); else if (key<(*T)->data) return DeleteBST(&(*T)->lchild,key); else return DeleteBST(&(*T)->rchild,key); } }
    • 平衡二叉树
      • 子主题
    • B-树
    • B+树
    • 键树
  • 哈希表（散列表）
    • 定义
    • 存储结构
    • 构造方法（利用关键字的值）
      • 直接定址法：取关键字或关键字的某个线性函数值为哈希地址
      • 数字分析法：哈希表中可能出现的关键字事先知道，可取关键字的若干位组成哈希地址
      • 平方取中法：取关键字平方后的中间几位为哈希地址
      • 折叠法：将关键字分割成位数相同的几部分，取这几部分的叠加和（舍去进位）为哈希地址
      • 除留取余法：取关键字被某个不大于哈希表长m的数p除后所得余数为哈希地址
      • 随机数法：选择一个随机函数，取关键字作为其种子时的随机函数值为它的哈希地址H（k）= random(k)
    • 处理冲突的方法
      • 开放地址法
        • 线性探测再散列
          • 优势
            • 只要哈希表未满，总能找到一个不发生冲突的地址Hk
          • 不足
            • 二次聚集
          • 增量序列：di = 1，2，3，4，m-1 增量序列加在第一次的哈希地址上
        • 二次探测再散列
          • 增量序列：
        • 伪随机探测再散列
          • di = 伪随机数列
      • 再哈希法：在同义词产生地址冲突时计算另一个哈希函数的地址
      • 链地址法
      • 建立一个公共溢出区
    • 哈希表的查找
      • 平均查找长度的计算
        • 开放地址法
          • 线性探测再散列
            • 查找成功时
            • 查找不成功时
          • 二次探测再散列
            • 查找成功时
            • 查找不成功时
          • 伪随机探测再散列
            • 查找成功时
            • 查找不成功时
        • 例题
    • 哈希表的删除：老师讲不可直接删除，应做特殊处理
• 排序
  • 定义：将一个数据元素的任意序列，排列成一个关键字有序的序列
  • 排序方法是否稳定：
    • 不稳定：快 希 堆
  • 各种排序算法的比较
  • 分类
    • 内部排序：将排序记录放在随机存储器中进行的排序，不使用外存
      • 数据类型
        • 复杂
        • 简单： int MAXSIZE 100 typedef struct { int data[MAXSIZE+1]； r0用作哨兵或临时变量 int length; }
      • 插入
        • 直接插入排序
          • 基本操作：将一个记录插入到已排序好的有序表中，从而得到一个新的、记录数增1的有序表 即先将序列中的第1个记录看成是一个有序的子序列，然后从第2个记录起逐个进行插入，直至整个序列变成按关键字非递减有序的序列为止。
          • 时间复杂度
            • 最好情况O（n）
              • 比较次数n-1 移动次数0
            • 最坏情况O（n2）
              • 比较次数（n-1）（n+2）/2 移动次数（n-1）（n+4）/2
            • 一般情况O（n2）
              • 比较次数，移动次数n2/4
          • 适用于元素数量少，或元素的初始序列较为有序
        • 希尔排序
          • 缩小增量排序
          • 基本思想：先将整个待排记录序列分割成若干个子序列分别进行直接插入排序，待整个序列的记录“基本有序”时，再对全体记录进行一次直接插入排序
      • 交换
        • 冒泡排序
          • 基本操作
            • 第一趟冒泡排序：将第一个记录的关键字和第二个记录的关键字进行比较，大的放后面，然后比较第二个和第三个，然后比较第三个和第四个，一直到第n-1和第n个，这样就把最大的放在了最后面
            • 第二趟冒泡排序：和第一次冒泡排序差不多，只是这次比较到第n-2和第n-1个，因为最大的已经放在了最后。这次排序的结果是第二大的记录放在了倒数第二个
            • 第n-1次排序，将第1个和第2个记录进行排序，排序之后就得到了有序的序列
          • 结束条件：最后一趟没有进行交换（设置flag）
          • 情况
            • 最好情况：比较n-1次，移动0次
            • 最坏情况：比较n（n-1）/2次，移动3n（n-1）/2次
            • 时间复杂度
              • 总的时间复杂度为O（n2）
        • 快速排序Quick Sort
          • 基本思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序
          • 做法
            • 大致做法：首先从记录中选取一个记录作为枢轴pivot，然后按照以下原则重新排列其余记录：
          • 情况
            • T（n）= n+T（k-1）+T（n-k）
            • 最好情况：O（nlogn）
            • 最坏情况：O（n2）
          • 适用情况
      • 选择
        • 简单选择排序
          • 基本思想：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换
          • 比较次数：n（n-1）/2 交换次数：最好0次，最多n-1次
          • 特点：排序时间基本不受代排序列初始状态
          • 时间复杂度：O（n2）
        • 堆排序
          • 小顶堆
            • 子主题
            • 子主题
      • 归并
        • 归并排序
          • 基本思想
          • 结构代码
          • 代码实现
          • 时间复杂度
      • 其他
    • 外部排序：待排数量很大，需使用外存
• 树
  • 定义
    • 结点的度：拥有的子树的数量
    • 树的度：树内各结点度的最大值
  • 二叉树
    • 每个节点至多只有两颗子树，子树有左右之分，次序不能任意颠倒：定义 基本形态有5种
    • 性质
      • 在二叉树的第i层至多有2^(i-1)个结点
        • 每一层上元素个数最多是上一层元素个数的二倍：计算来源
        • 多叉树时：k^(i-1)
      • 深度为k的二叉树至多有2^k -1个结点
        • 上条性质，等比数列求和：推导
      • 对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1
    • 存储结构
      • 顺序存储结构
      • 链式存储结构
    • 二叉树的遍历
      • 先序遍历
        • 前缀表示
      • 中序遍历
        • 中缀表示
      • 后序遍历
        • 后缀/逆波兰式表示
      • 层次遍历
        • 从上到下，从左到右
    • 二叉树的应用一：哈夫曼树 最优二叉树
      • 基本概念
        • 路径长度：路径上的分支数目
        • 树的路径长度：从根结点到每个结点的路径长度之和
        • WPL树的带权路径长度：所有叶子结点的带权路径长度之和
        • 最优二叉树：WPL最小的二叉树
      • 哈夫曼算法（建树）
      • 哈夫曼编码
        • 例
        • 编码期望值：每个叶子结点的概率×路径长度之和
        • 压缩率：（原编码所占位数-编码期望值）/原编码所占位数
  • 树与森林
    • 树的存储结构
      • 双亲表示法
      • 孩子表示法
      • 孩子兄弟表示法
    • 森林与二叉树的转换
      • 例
    • 树的遍历
      • 先根遍历
        • 先访问树的根结点，然后依次先根遍历根的每颗子树
      • 后根遍历
        • 先依次后根遍历每颗子树，然后访问根结点
      • 例
    • 森林的遍历
      • 先序遍历森林
      • 中序遍历森林
      • 例
• 数组Array
  • 定义
    • n维数组
    • 数组一旦被定义，它的维数和维界就不再改变
  • 存储结构
    • 顺序存储 从a00开始
      • 以行序为主序
        • a0,0 a0,1 a0,2 .. a1,0 a1,1 ... am-1,n-1
        • 先第一行，再第二行
      • 以列序为主序
        • a0,0 a1,0 a2,0 .. a0,1 a1,1 ... am-1,n-1
        • 先第一列，第一列排完再排第二列
      • 存储地址的计算
        • 2维
        • n维
    • 矩阵的压缩存储 从a11开始
      • 压缩存储：为多个值相同的元只分配一个存储空间，对零元不分配空间
      • 分类
        • 特殊矩阵
          • 当非零元的分布有一定的规律时，将其压缩到一维数组中
          • 对称矩阵的压缩存储
        • 稀疏矩阵
          • 判别方式
            • 稀疏因子=t/(m*n) t个元素不为零 稀疏因子小于等于0.05时
          • 稀疏矩阵的压缩存储方法
            • 三元组顺序表
              • 结构代码 （data[]以 行序为主序）
              • 矩阵的转置
                • 一般矩阵的转置
                • 三元表的转置一
                • 三元表的快速转置算法
            • 行逻辑链接的顺序表
            • 十字链表
• 队列Queue
  • 定义
    • 先进先出
  • 存储结构
    • 循环队列
      • 基础知识
        • 目的：克服假溢出
        • 在具有n个单元的循环队列中， 队满时有n-1个元素
        • 判断满：Q.front=(Q.rear+1)%m
        • 计算长度：
          • rear指向尾结点的下一个结点时，(rear-front+n)%n
          • rear指向队位元素时，(rear-front+n+1)%n
      • 结构代码
      • 循环队列入队
      • 循环队列出队
    • 链式队列
      • 结构代码
      • 入队
      • 出队
• 栈Stack
  • 定义
    • 后进先出
    • 栈满时入栈：上溢
    • 栈空时出栈：下溢
  • 存储结构
    • 栈的顺序存储结构
      • 结构代码
      • 入栈push
      • 出栈pop
    • 两栈共享空间
      • 原理
      • 结构代码
      • 入栈push
      • 出栈pop
      • 好处
        • 节省存储空间
        • 降低上溢发生的概率
    • 栈的链式存储结构
      • 结构代码
      • 入栈push
      • 出栈pop
  • 栈的应用
    • 数制转换
    • 括号匹配检验
    • 行编辑程序
    • 迷宫求解
    • 表达式求值
      • 后缀表达式
        • 从左到右遍历表达式的每个数字和符号，遇到数字就入栈，遇到符号，就将 ：计算规则 处于栈顶的两个元素出栈，进行运算，运算结果进栈，一直到最终获得结果
        • 9 3 1 - 3 * + 10 2 / +
      • 中缀表达式
        • 9+(3-1)*3+10/2
        • 中缀表达式转后缀表达式的规则： 从左到右遍历中缀表达式，若是数字就输出，若是符号就判断其与栈顶元素的优先级，若此符号是右括号）或优先级低于、等于栈顶符号，就将栈顶元素依次出栈并输出（边输出边判断条件是否满足），并将当前符号进栈，直到遍历完成
    • 实现递归
      • 斐波那契数列
      • 汉诺塔问题
• 线性表List
  • 定义
  • 存储结构
    • 顺序存储SqList
      • 基础知识
        • 用一组连续的存储单元依次存储线性表的数据元素：定义
        • ：特点
        • 优点
          • 无需增加额外的存储空间来表示元素间的逻辑关系
          • 可以快速存取表中任意位置的元素
        • 缺点
          • 插入和删除需要移动大量的元素
          • 长度不能控制
          • 造成存储空间的碎片化
        • 存储地址计算方法
          • LOC(ai+1)=LOC(ai)+c
          • LOC(ai)=LOC(1)+c*(i-1)
          • 存取性能为O（1） —>随机存取结构
      • 操作
        • 结构代码
          • #define MAXSIZE 20 /* 存储空间初始分配量 */ typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */ typedef struct { ElemType data[MAXSIZE]; /* 数组，存储数据元素 */ int length; /* 线性表当前长度 */ }SqList;
        • 获取元素
          • /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */ /* 操作结果：用e返回L中第i个数据元素的值，注意i是指位置，第1个位置的数组是从0开始 */ Status GetElem(SqList L,int i,ElemType *e) { if(L.length==0 || i<1 || i>L.length) return ERROR; *e=L.data[i-1]; return OK; }
        • 插入
          • /* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */ /* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */ Status ListInsert(SqList *L,int i,ElemType e) { int k; if (L->length==MAXSIZE) /* 顺序线性表已经满 */ return ERROR; if (i<1 || i>L->length+1) /* 当i比第一位置小或者比最后一位置后一位置还要大时 */ return ERROR; if (i<=L->length) /* 若插入数据位置不在表尾 */ { for(k=L->length-1;k>=i-1;k--) /* 将要插入位置后的元素向后移一位 */ L->data[k+1]=L->data[k]; } L->data[i-1]=e; /* 将新元素插入 */ L->length++; return OK; }
        • 删除
          • /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */ /* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */ Status ListDelete(SqList *L,int i,ElemType *e) { int k; if (L->length==0) /* 线性表为空 */ return ERROR; if (i<1 || i>L->length) /* 删除位置不正确 */ return ERROR; *e=L->data[i-1]; if (i<L->length) /* 如果删除不是最后位置 */ { for(k=i;k<L->length;k++) /* 将删除位置后继元素前移 */ L->data[k-1]=L->data[k]; } L->length--; return OK; }
    • 链式存储LinkList
      • 基础知识
        • 头结点和头指针
          • 若链表有头结点，则头指针是指向头结点的指针
        • 子主题
      • 单链表操作及代码
        • 结构代码
          • /* 线性表的单链表存储结构 */ typedef struct Node { ElemType data; struct Node *next; }Node; typedef struct Node *LinkList; /* 定义LinkList */
        • 初始化
          • Status InitList(LinkList *L) { *L=(LinkList)malloc(sizeof(Node)); /* 产生头结点,并使L指向此头结点 */ if(!(*L)) /* 存储分配失败 */ return ERROR; (*L)->next=NULL; /* 指针域为空 */ return OK; }
        • 读取
          • /* 初始条件：链式线性表L已存在，1≤i≤ListLength(L) */ /* 操作结果：用e返回L中第i个数据元素的值 */ Status GetElem(LinkList L,int i,ElemType *e) { int j; LinkList p; /* 声明一结点p */ p = L->next; /* 让p指向链表L的第一个结点 */ j = 1; /* j为计数器 */ while (p && j<i) /* p不为空或者计数器j还没有等于i时，循环继续 */ { p = p->next; /* 让p指向下一个结点 */ ++j; } if ( !p || j>i ) return ERROR; /* 第i个元素不存在 */ *e = p->data; /* 取第i个元素的数据 */ return OK; }
        • 插入
          • /* 初始条件：链式线性表L已存在,1≤i≤ListLength(L)， */ /* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */ Status ListInsert(LinkList *L,int i,ElemType e) { int j; LinkList p,s; p = *L; j = 1; while (p && j < i) /* 寻找第i个结点 */ { p = p->next; ++j; } if (!p || j > i) return ERROR; /* 第i个元素不存在 */ s = (LinkList)malloc(sizeof(Node)); /* 生成新结点(C语言标准函数) */ s->data = e; s->next = p->next; /* 将p的后继结点赋值给s的后继 */ p->next = s; /* 将s赋值给p的后继 */ return OK; }
        • 删除
          • /* 初始条件：链式线性表L已存在，1≤i≤ListLength(L) */ /* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */ Status ListDelete(LinkList *L,int i,ElemType *e) { int j; LinkList p,q; p = *L; j = 1; while (p->next && j < i) /* 遍历寻找第i个元素 */ { p = p->next; ++j; } if (!(p->next) || j > i) return ERROR; /* 第i个元素不存在 */ q = p->next; p->next = q->next; /* 将q的后继赋值给p的后继 */ *e = q->data; /* 将q结点中的数据给e */ free(q); /* 让系统回收此结点，释放内存 */ return OK; }
        • 整表创建
          • 头插法
            • /* 随机产生n个元素的值，建立带表头结点的单链线性表L（头插法） */ void CreateListHead(LinkList *L, int n) { LinkList p; int i; srand(time(0)); /* 初始化随机数种子 */ *L = (LinkList)malloc(sizeof(Node)); (*L)->next = NULL; /* 先建立一个带头结点的单链表 */ for (i=0; i<n; i++) { p = (LinkList)malloc(sizeof(Node)); /* 生成新结点 */ p->data = rand()%100+1; /* 随机生成100以内的数字 */ p->next = (*L)->next; (*L)->next = p; /* 插入到表头 */ } }
          • 尾插法
            • /* 随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法） */ void CreateListTail(LinkList *L, int n) { LinkList p,r; int i; srand(time(0)); /* 初始化随机数种子 */ *L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */ r=*L; /* r为指向尾部的结点 */ for (i=0; i<n; i++) { p = (Node *)malloc(sizeof(Node)); /* 生成新结点 */ p->data = rand()%100+1; /* 随机生成100以内的数字 */ r->next=p; /* 将表尾终端结点的指针指向新结点 */ r = p; /* 将当前的新结点定义为表尾终端结点 */ } r->next = NULL; /* 表示当前链表结束 */ }
        • 整表删除
          • /* 初始条件：链式线性表L已存在。操作结果：将L重置为空表 */ Status ClearList(LinkList *L) { LinkList p,q; p=(*L)->next; /* p指向第一个结点 */ while(p) /* 没到表尾 */ { q=p->next; free(p); p=q; } (*L)->next=NULL; /* 头结点指针域为空 */ return OK; }
      • 静态链表StaticLinkList
      • 循环链表
        • 填空题
          • 元素个数
        • 容易与循环队列搞混
      • 双向链表
• 基本概念
  • 数据结构的概念
    • 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间关系和运算的学科
    • （D，R）
      • D 数据元素的有限集合
      • R D上的关系有限集合
  • 数据
    • 分类
      • 数值类型
      • 非数值类型
    • 数据元素：组成数据的基本单位
    • 数据项：若干个数据项组成数据元素，数据的最小单位
    • 数据对象：数据的子集
    • 数据结构：数据元素之间的关系
  • 数据结构包括
    • 逻辑结构
      • 线性结构
        • 元素之间一对一
          • 线性表，栈，队列，数组
      • 非线性结构
        • 集合结构
        • 树形结构
          • 一对多
        • 图形结构
          • 多对多
    • 存储结构
      • 顺序存储结构
      • 链式存储结构
      • 其余
        • 索引
        • 散列
    • 运算
      • 插入
      • 删除
      • 修改
      • 查找
      • 排序
  • 数据类型
    • 分类
      • 原子类型
      • 结构类型
    • 定义：一组性质相同的值集合以及定义在这个值集合上的一组操作的总称
    • 抽象数据类型
  • 算法
    • 定义：解决特定问题求解步骤的描述， 在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作
    • 特点
      • 输入
      • 输出
      • 有穷性
      • 确定性
      • 可行性
    • 算法设计的要求
      • 正确性
      • 可读性
      • 健壮性
      • 时间效率高和存储量低
    • 算法效率的度量方法
      • 事后统计法
      • 事前分析估算法
    • 算法复杂度
      • 时间复杂度O
        • 常数阶O（1）
          • 12
        • 线性阶O（n）
          • 2n+3
        • 对数阶O（logn）
          • 5log2n+20
        • 平方阶O（n2）
          • n2
        • 立方阶O（n3）
        • nlogn阶
        • 指数阶O（2n）
      • 空间复杂度

中心主题