数据结构期末复习

第一章.绪论

基本概念

1.数据，是描述客观事物的符号

2.数据元素，数据的基本单位

3.数据对象，是同一种数据元素的集合

4.数据结构，是数据元素与数据元素之间关系的集合

数据结构的分类

顺序结构，链式结构

线性表（一对一），树（一对多），图（多对多）

算法的描述

自然语言描述，解决某一特定问题的具体步骤的描述，是指令的有限序列

解决问题的方法和步骤的统称，方法和步骤用自然语言描述，用流程图描述，转化成高级语言描述，伪代码买描述

五个特性：有穷性、确定性、可行性、输入、输出

评价算法的方法：正确性，可读性，健壮性，效率与低存储量。

数据结构的三种分类方法：

按照逻辑结构，分为线性结构和非线性结构；

数据的存储结构分为顺序存储和链式存储。

数据的运算包括：检索、排序、插入、删除、修改

其他概念

程序=数据结构+算法

第二章.线性表

基本定义

除了最后一个元素，每一个都有且只有一个唯一的直接后继都有，

除了第一个，每一个元素都有唯一的前驱元素

中间的每个都有前驱和后继

基本算法

线性存储的插入（要把n个到第i个每个元素都后移，n-i+1次）

查找（有没有顺序，没顺序分块找O(logn)或者顺序查找O(n)，有顺序折半）

删除（把i+1到n向前移动 n-i次）

链式存储的插入(正序建表，从尾巴上插入新的节点，假设尾巴为p，要插入s，p->next=s;s->next=null

倒序建表，在表头后面插入元素，假设表头为h，插入s：s->next=h->link;h->link=s;)

查找（去迭代查找）

h=header;
int flag=0;
while(h->next!=null){
    if(if(h->data==ch){
        flag=1;
        break;
    }else{
        h=h->link;
    }
}

删除{确认位置}建立

双向链表

多一个指针域，指向前一个

循环链表

首尾相连，从任意点进入可以查找

一元多项式的合并

未知数的指数从小到大，

按照指数的大小合并的相关算法过程。三种类型

typedef   struct node
{   int coef,exp;
     struct node  *next;
}JD;

void add_poly(JD *pa,JD *pb) {
    JD *p,*q,*u,*pre;
    int x;
    p=pa->next;
    q=pb->next;
    pre=pa;
    while((p!=NULL) && ((q!=NULL)) {
        if(p->exp<q->exp) {
            pre=p;
            p=p->next;
        } else if(p->exp==q->exp) {
            x=p->coef+q->coef;
            if(x!=0) {
                p->coef=x;
                pre=p;
            } else {
                pre->next=p->next;
                free(p);
            }
            p=pre->next;
            u=q;
            q=q->next;
            free(u);
        } else {
            u=q->next;
            q->next=p;
            pre->next=q;
            pre=q;
            q=u;
        }
    }
    if(q!=NULL)
            pre->next=q;
    free(pb);
}

序存储结构的优缺点

优点

逻辑相邻，物理相邻

可随机存取任一元素

存储空间使用紧凑

缺点

插入、删除操作需要移动大量的元素

预先分配空间需按最大空间分配，利用不充分

表容量难以扩充

结构格式：

单链表节点
typedef struct node {
     datatype data;
     struct node  *link;
}JD;

双向链表节点
typedef struct node {
     datatype element;
     struct node *prior,*next;
}JD;

第三章.栈和队列

基本定义

栈的定义，限定仅在表尾进行插入或删除操作的线性表

有一个数组s[m]，int top=0；

栈

入栈出栈都在线性表的同一端

队列

入队在一端进入，在另一端出队（类似于管道）

相当于在线性表的两端进行插入和删除操作。

有两个指示器，front 队首，rear队尾

栈的定义：

操作受限制的线性表，都在栈顶进行

顺序栈，链式栈

相关增删操作

顺序栈的插入，h为头节点，插入s

s->link=h->link;
h->link=s;

出栈的操作

x=h->link->data;
p=h->link;
h->link=p->link;
free(p);

入队的操作，头节点front，尾结点rear

rear->link=s;
s->link=null;
rear=s;

出队的操作

x=front->link->data;
p=front->link;
front->link=p-link;
free(p);

队列的定义：

队尾进行入队

链队列，顺序队列

循环队列

相关概念，取模运算

判断空和满的方法

真溢出，front=-1；rear=length-1；真溢出

假溢出为front！=-1.rear=length-1；

解决方案1，每次元素出队的时候，剩余元素下移，保证所有元素在最下面开始。

结局方案2，循环队列，出队的时候就出（rear+1）%m

​ 人对的时候入队（front+1）%m

此时如何判断队满问题，rear==front时候有两种情况，一个是队满了，一个是空队

这时候的处理方法有两种，1通过一个flag，在入队的时候+1，在出队的时候-1，如果flag==M了，则满了，否则是空队

第二种方法是=少用一个元素，(rear+1）%M==front时候是空的，则最后一个元素空间浪费

相关定义方法

链栈的节点

typedef   struct node
{   int data;
     struct  node  *link;
}JD;

链队的节点

typedef   struct node 
{   int data;
     struct node  *link;
}JD;

第四章.串

定义：

线性表的一种，数据类型是字符类型

串的存储方法：

定长顺序存储，堆分配存储方式链式存储（块儿）

定长和堆分配的区别：空间的分配方式不同。

基础算法：

串的截取（SubStr），串的连接（concat）

串的匹配算法：

next函数只和子串本身有关

next函数的算法

void getnext{int next[],Hstring s}{
    int j,k;
    netx[0]=1;
    for（j=1;j<HString.length;j++){
        if(j==0||s.ch[j]==s.ch[k]){
            j++;k++:
            next[j]=k;
        }else{
            k=next[k];
        }
    }
}

void getNext(Sstring S[],int next[]){
    int j,k;
    for(next[0]=1,j=1;j<s[0];j++){
        if(k==0||S[j]==s[k]){
            j++;
            k++;
            next[j]=k;
        }else{
            k=next[k];
        }
    }
}

截取算法

int substring(Sstirng &Sub,Sstring s,int start,int length){
    if(start>0&&start+length<s[0]){
        return error;
    }else{
        Sub[0]=len;
        for (int count=1;count<=len;count++){
            Sub[count]=s[count+start-1];
        }
    }
    return OK;
}

基于HString的连接方法

int Concat(HString s1,HSting s2,HString t){
    if(t.ch){
        free(t);
    }
    if(!(T.ch=(char *)malloc (sizeof(char)*(s1.length+s2.length)))){
        return OVERFlOW;
    }
    T.length=s1.length+s2.length;
    for(int i=0;i<s1.length;i++){
        T.ch[i]=s1.ch[i];
    }
    for(int i=s1.length;i<T.length;i++){
        T.ch[i]=s2.ch[i-s1.length];
    }
    return ok;
}

相关定义方法

静态顺序存储

#define    MAXSTRLEN   255  
typedef unsigned char Sstring[MAXSTRLEN+1]    

堆分配的存储方法

typedef struct {
    char *ch;
    int length;
} Hstring;

串的链式储存结构

#define CHUNKSIZE 80  
typedef struct Chunk  {
    char ch[CHUNKSIZE];
    struct Chunk *next;
}Chunk;               
typedef struct  {
    Chunk  *head,  *tail;
    int curlen;   
} LString;      

indexof算法

int indexof(Sstring S, Sstring T,int pos){
    int i=1,j=pos;
    while(i<s[0]&&j<T[0]){
        if(s[i]==s[j]){
            i++;j++;
        }else{
            i=i-j+2;
            j=1;
        }
    }
    if(j>T[0]){
        return i-T[0];
    }else{
        return -1;
    }
}

KMP算法

int KMP(Ssting S,Sstring T,int pos,int next[]){
    int i=1,j=pos;
    while(i<s[0]&&j<T[0]){
        if(s[i]==s[j]){
            i++;j++;
        }else{
            j=next[j];
        }
    }
    if(j>T[0]){
        return i-T[0];
    }else{
        return -1;
    }
}

第五章.数组

数组的定义：

线性表

寻址算法：

地址=首地址+偏移量

提前约定行列的主序

数组的顺序表示：

系数矩阵(用三元组矩阵，i，j，data数组存贮)

十字链表，两个链表。

特殊矩阵：

对称矩阵，三角矩阵，对角矩阵 存储多少

结构定义方法:

三元组表

# define MAXSIZE max    
typedef struct {
    int i，j;
    ElemType e;
}Triple;
typedef union {
    Triple data[MAXSIZE+1];
    int mu，nu，tu;
}TSMatrix;

简单可以如下描述:
#define    M    20
typedef   struct  node {
    int  i,j;
    int v;
}
JD;
JD   ma[M];
//此时ma[0]存行列，非零个数

十字链表

 typedef struct OLNode{
     int i, j;                       /*矩阵非零元素的行、列值*            
     ElemType e;                       /*非零元素的值*/
     struct OLNode *right, *down;      /*该非零元所在行、 列的后继链域*/
    } OLNode, *Olink;

  typedef struct{
      Olink *rhead, *chead;   /*行、列表指针向量基址*
      int mu,nu,tu;     /*矩阵的行、列数及非零元数个数*/
       }CrossList;

第六章.树和二叉树

树的定义和基本术语：

结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支

结点的度(degree)——结点拥有的子树数

叶子(leaf)——度为0的结点

孩子(child)——结点子树的根称为该结点的孩子

双亲(parents)——孩子结点的上层结点叫该结点的~

兄弟(sibling)——同一双亲的孩子

树的度——一棵树中最大的结点度数

结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层……

深度(depth)——树中结点的最大层次数

森林(forest)——m(m³0)棵互不相交的树的集合

堂兄弟 ：其双亲在同一层的结点间互称堂兄弟。

二叉树：

五个性质。对于所有二叉树，满二叉树，完全二叉树

性质1：对于任意二叉树，在第i层上，最多有2^(i-1)个节点

性质2：深度为k的二叉树至多有2^k-1个节点

性质3：下面的n0=n2+1

二叉树的n0为度为0的节点（叶子节点），n1为度为1的节点，n2为度为2的节点

这里面有性质n0=n2+1;

对于本题，已知条件可得n0=20，n1=20,则n2=n0-1=19，

所以n=n0+n1+n2=59

用分支的数量来证明相关内容

性质4：具有n个节点的完全二叉树的深度为int（logn）+1

性质5：对于任意节点i，按层排序 1<=i<=n;

(1) 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是int(i/2)

(2) 如果2i>n， 则结点i 无左孩子；如果2i<=n， 则其左孩子是2i

(3) 如果2i+1>n， 则结点i 无右孩子；如果2i+1<=n， 则其右孩子是2i+1

储存方法：

顺序存储

适于存满二叉树和完全二叉树，由性质5转换来，需要把树补满成完全二叉树，然后按照性质5来找双亲孩子

二叉链表

typedef    struct  node
{    datatype    data;
  struct  node  *lchild,  *rchildhild;
}JD;

左右节点分别指向左右孩子，总共有2n个指针，有n-1条边，所以有n+1个空指针

三叉链表

在二叉链表的基础上加上parent节点

双亲表示法

#define MAX_TREE_SIZE 100
typedef struct PTNode {
    TElemType data;
    int  parent;
    //双亲位置
}PTNode;
typedef struct {
    PTNode nodes[MAX_TREE_SIZE];
    int n;
    //结点数
}Ptree;

孩子表示法

typedef struct CTNode {
    int child;
    struct CTNode *next;
}
*ChildPtr;
typedef struct {
    TElemType data;
    ChildPtr firstchild;
}CTBox;
typedef struct {
    CTBox  nodes[MAX_TREE_SIZE];
    int n,r;
}
Ctree;

带双亲的孩子链表

typedef struct CTNode {
    int child;
    struct CTNode *next;
}
*ChildPtr;
typedef struct {
    TElemType data;
    ChildPtr firstchild;
 int parent;
}CTBox;
typedef struct {
    CTBox  nodes[MAX_TREE_SIZE];
    int n,r;
}
Ctree;

与孩子表示法的区别在于多了一个parent指示器

孩子兄弟表示法

typedef struct CSNode {
    ElemType data;
    struct CSNode *firstchild, *nextsibling;
}
CSNode, *CSTree;

一个结构体，分别记录了数据值，第一个孩子的指针，和第一个兄弟的指针。

遍历方法：

先序遍历 非递归方法借用栈

中序遍历（递归方法，借助栈还是队列？）

后序遍历（）

层序遍历

树和森林：

数的储存方法（双亲表示法顺序，孩子表示法顺序和链式存储的结合，孩子兄弟表示法加一个指针）

树和二叉树以及森林之间的相互转化

树转二叉树

（1）给兄弟之间加线

（2）给长子以外的孩子去线

（3）层次调整

由兄弟节点转换过来的都是右子树

由第一个孩子转换过来的是左节点

森林转二叉树

（1）将森林中每棵树转化为二叉树

（2）第一棵树不动

（3）第二棵树作为第一棵树的右孩子，第三棵树做第二棵树的右孩子

二叉树转换为树

将二叉树与其右孩子和的右孩子……套娃的节点，去除原来各种与右孩子的连线

二叉树转换为森林，

前提有右孩子

如果有右孩子，就去掉与右孩子的连线，套娃

树的遍历

先根、后根

森林遍历

按顺序遍历每棵树或者森林转二叉树遍历二叉树

哈弗曼树（最优二叉树）：

wpl最小的二叉树

构造方法，过程

哈弗曼编码的方法，左标0，右表1

第七章.图

图的定义和术语

图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为 G= ( V, {E} )

无向图——无向图G是由两个集合V(G)和E(G)组成的

有向图——有向图G是由两个集合V(G)和E(G)组成的

无向完全图——如果在无向图中，任何两个顶点都有一条边相连接， 则称此图为无向完全图。含有n个顶点，每一个顶点都与 其它n-1个顶点有边，因此，共有n*(n-1)/2条边。

有向完全图——在有向图G中，任何两个顶点都有方向相反的两条弧线连接，若图G中含有n个顶点，则共有n*(n-1)条弧

子图，一部分的拿出阿里

邻接点：有边的两个点称为一对儿邻接点

顶点的度

无向图中，顶点的度为与每个顶点相连的边数，记为TD(V)。

有向图中，顶点的度分成入度与出度

入度：以该顶点为头的弧的数目，记为ID(V)

出度：以该顶点为尾的弧的数目，记为OD(V)

路径——图中从顶点V到顶点V’的路径是顶点的序列

路径长度**—沿路径边的数目或沿路径各边权值之和

回路——第一个顶点和最后一个顶点相同的路径叫回路或环。

简单路径——序列中顶点不重复出现的路径叫

简单回路—除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫~

连通——从顶点V到顶点W有一条路径，则说V和W是连通的

连通图——图中任意两个顶点都是连通的叫~

连通分量——指无向连通图中极大连通子图或非连通图的每一个连通部分的极大连通子图。

强连通图——有向图中，如果对每一对Vi,VjV, ViVj,从Vi到Vj 和从Vj到 Vi都存在路径，则称G是强连通图。有向强连通图G的极大强连通子图或非强连通图的强连通子图中的极大强连通子图称为强连通分量。

网和图的区别

网是有权重的，图是无权的

存储方法：

数组表示法（邻接矩阵）

开n*n的数组，有权就放权重，无权有边放1，无放放0

#define INFINITY INT_MAX                   //最大值
#define MAX_VERTEX_NUM     20  //最大顶点个数
typedef enum {
    DG,DN,UDG,UDN
}GraphKind;
//有向图网、无向图网
typedef struct ArcCell {
    VRType  adj;
    Infotype *info
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
    VertexType vexs[MAX_VERTEX_NUM];
    AdjMatrix arcs;
    int vexnum,arcnum;
    GraphKind kind;
}
Mgraph;

邻接表

#define MAX_VERTEX_NUM 20
typedef struct ArcNode {
    int   adjvex;
    struct  ArcNode *nextarc;
    InfoType  *info;
}ArcNode;
typedef  struct VNode {
    VertexType data;
    ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
    AdjList vertices;
    int    vexum,arcnum;
    int Kind;
}ALGraph;

纵向AdjList，包括所有的顶点集合，

横向是从这一行的顶点出发的可以到达的所有边，节点数代表出度

有向图的十字链表表示法

typedef  struct  arcnode {
    int   tailvex,  headvex;
    struct   arcnode   *hlink；
    struct   arcnode   *tlink;
}AD;
typedef  struct  dnode {
    int   data;
    struct   arcnode   *firstin；
    struct   arcnode   *firstout;
}DD;
DD  g[M];

数组表示法——邻接矩阵（储存方法，储存规则，查找边数的方法）

邻接表，十字链表，邻接多重表

typedef   struct  node
{   int  mark;                           //标志域
  int  ivex, jvex;                   //该边依附的两个顶点在表头数组中位置
struct  node   *ilink,  *jlink; //分别指向依附于ivex和jvex的下一条边
}JD;
typedef   struct  dnode
{    int   data;                    //存与顶点有关的信息
   struct   node  *firstedge;  //指向第一条依附于该顶点的边
}DD;

DD  ga[M];   //ga[0]不用

遍历方法：

DFS类似先根遍历

BFS类似层序遍历

连通图（生成树）：

Prim算法

把点集分为两部分，V全集，S为已经访问的,T为未访问过的。

通过找未访问过的点集合中到S中的一个边，并保证权重最小，则同时加边加顶点

Kruskal

将边矩阵中最小的一条边拿出来，如果和现在已经形成的图不能形成回路，则加入，否则抛弃这条边

没有回路，由于不同遍历方法的遍历结果不同出现的不同的生成树

生成树不唯一，但最小生成树唯一

最短路径

Dij，Floyd不考

第八章.查找

基本概念：

静态查找方法：顺序查找，折半查找，

折半查找的跳出条件是low>high

分块查找

块内无序，块间有序。

动态查找：二叉排序树

删除叶子节点直接删除

删除有一个孩子的，直接把孩子拿上来替换

删除有左右孩子的，找左子树最大的（最右边的）替换，然后删除

B-树

除了根根节点，每个节点的最小节点数是向上取整(m/2)-1 ，最大是m-1、

插入就循环就行

删除向根或兄弟借，然后换位置

删除根节点，从左树最大值或右树最小值替换

哈希表

处理冲突的方法，

开放定址法：1.线性探测再散列 2.二次探测再散列 3.伪随机探测再散列

再哈希法，在原基础上加新的哈希函数。冲突了计算你下一个哈希函数

链地址法：将所有冲突用链表储存

#include <algorithm>
#include <map>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
typedef pair<string, int> PAIR;   
bool cmp_by_value(const PAIR& lhs, const PAIR& rhs) {  
  return lhs.second < rhs.second;  
}  
struct CmpByValue {  
  bool operator()(const PAIR& lhs, const PAIR& rhs) {  
    return lhs.second < rhs.second;  
  }  
};
int main(){  
  map<string, int> name_score_map;  
  name_score_map["LiMin"] = 90;  
  name_score_map["ZiLinMi"] = 79;  
  name_score_map["BoB"] = 92;  
  name_score_map.insert(make_pair("Bing",99));  
  name_score_map.insert(make_pair("Albert",86));
  vector<PAIR> name_score_vec(name_score_map.begin(), name_score_map.end());  
  sort(name_score_vec.begin(), name_score_vec.end(), CmpByValue());  
  for (int i = 0; i != name_score_vec.size(); ++i) {  
    cout<<name_score_vec[i].first<<" "<<name_score_vec[i].second<<endl;  
  }  
  return 0;  
}  

第九章.排序

插入排序：直接插入排序，希尔排序

直接插入排序是每次找一个

例如有一个组，把第一个插入到已排序，然后从下一个开始。循环n-1次。

每次取到对应的数，如果这个数比已排序的最后一个大（也就是i前面那个），就不用动，下一次循环

如果比最后一个小，要倒着往前找，直到找到位置，L[0].key>L[j].key，每次循环将j移动到j+1，然后循环跳出去找到位置，就替换

希尔排序就是改变插入排序的分组长度

交换排序：冒泡排序，快速排序

循环，每次有a[i]>a[i+1]，就swap，然后到本轮结束会出现最后一个元素是剩下的元素最大的。

冒泡排序的特点。每次循环，内外循环次数和等于元素个数

交换排序：简单选择排序，堆排序

归并排序：2-路归并排序

例题

对于关键字序列（475,137,481,219,382,674,350,326,815,506 ）

手写各趟排序的结构

（1）直接插入排序

137 475 481 219 382 674 350 326 815 506

137 475 481 219 382 674 350 326 815 506

137 219 475 481 382 674 350 326 815 506

137 219 382 475 481 674 350 326 815 506

137 219 382 475 481 674 350 326 815 506

137 219 350 382 475 481 674 326 815 506

137 219 326 350 382 475 481 674 815 506

137 219 326 350 382 475 481 674 815 506

137 219 326 350 382 475 481 506 674 815

（2）希尔排序率d=5.3.1

475 137 326 219 382 674 350 481 815 506

219 137 326 350 382 674 475 481 815 506

137 219 326 350 382 475 481 506 674 815

（3）冒泡排序

475,137,481,219,382,674,350,326,815,506

137 475 219 382 481 350 326 674 506 815

137 219 382 475 350 326 481 506 674 815

137 219 382 350 326 475 481 506 674 815

137 219 350 326 382 475 481 506 674 815

137 219 326 350 382 475 481 506 674 815

137 219 326 350 382 475 481 506 674 815

137 219 326 350 382 475 481 506 674 815

137 219 326 350 382 475 481 506 674 815

（4）选择排序

475,137,481,219,382,674,350,326,815,506

137 475 481 219 382 674 350 326 815 506

137 219 481 475 382 674 350 326 815 506

137 219 326 475 382 674 350 481 815 506

137 219 326 350 382 674 475 481 815 506

137 219 326 350 382 674 475 481 815 506

137 219 326 350 382 475 674 481 815 506

137 219 326 350 382 475 481 674 815 506

137 219 326 350 382 475 481 506 815 674

137 219 326 350 382 475 481 506 674 815

（5）快速排序

475,137,481,219,382,674,350,326,815,506

326,137,350,219,382,475,674,481,815,506

219.137 326 350 382 475 506 481 674 815

137 219 326 350 382 475 481 506 674 815

（6）归并排序

475,137,481,219,382,674,350,326,815,506

137 475 219 481 382 674 326 350 506 815

137 219 475 481 326 350 382 674 506 815

137 219 326 350 382 475 481 674 506 815

137 219 326 350 382 475 481 506 674 815

（7）堆排序

475,137,481,219,382,674,350,326,815,506

137 219 350 326 382 624 481 425 815 506

137 219 326 350 425 382 624 481 506 815

137 219 326 382 350 425 815 624 481 506

137 219 326 350 382 481 425 815 624 506

127 219 326 350 382 425 481 506 815 624

127 219 326 350 382 425 506 481 624 815

127 219 326 350 382 425 481 506 815 624

127 219 326 350 382 425 481 506 624 815

127 219 326 350 382 425 481 506 624 815

题型：

选择题

判断题4个

解答题：描述图的邻接表的存储方法，稀疏矩阵的十字链表表示方法，C语言的描述方法（结构体，数组的表示，第六章之前，第i趟某种排序的结果），森林转化成二叉树。哈弗曼编码，最小生成树。

编程题：四次实验任务（前三个）