栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

数据结构整理

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

数据结构整理

数据结构复习 文章目录
  • 数据结构复习
    • @[toc]
    • 第0章绪论
    • 第1章线性表
      • 分类:顺序表和链表
        • 1.顺序表(数组存储)
          • 1)(数据类型)
        • 2.链表(链式存储)
          • 1)(数据类型)
          • 2)head和头结点
          • 3)主要操作
          • 4)分类
            • 循环链表 (将表尾的指针指向'头结点'
            • 双向链表 (方便查询前一个结点
    • 第2章栈和队列
      • 栈 **(有后进先出的特性**
        • **1)'栈的定义:**
        • 2)数据类型
            • 顺序栈 (以数组为格式存储
            • 链式栈 (以链表形式存储
        • 3)主要操作
      • 队列 (有先进先出的特性
        • 1)队列的定义:
        • 2)数据类型
            • 顺序队列(以数组为格式存储
            • 链式队列 (以链表形式存储
        • 3)主要操作
    • 第2章栈和队列
      • 串 (主要为BF、KMP算法
        • 1)定义
        • 2)**'串的模式匹配算法'**
        • 2)实际代码
      • 数组
            • 二维数组
            • 广义表(LS) 线性表内存储的数据不一定为相同类型
    • 第3章树和二叉树
      • 树
        • 1)定义
      • 二叉树
        • 1)定义
        • 2)数据类型
            • **'顺序存储':**按照满二叉树的编号放入数组,没有的空出填0即可
            • '链式存储':data,lchild,rchild
        • 3)算法
            • 二叉树的遍历
      • 线索二叉树(方便查询前驱和后继结点
      • 哈夫曼树 (带权路径长度最短的二叉树
        • 1)定义
        • 2)构造哈夫曼树
        • 3)哈夫曼编码
    • 第4章图
        • 1)定义
        • 2)数据类型
            • **'数组表示法(邻接矩阵)':**用二维数组表示元素之间的关系
            • '链式存储结构(邻接表)':
        • 3)图的遍历
            • 深度优先搜索(DFS) 递归思想
            • 广度优先搜索(BFS) 使用队列
        • 4)图的应用
            • 图的生成树:
            • 最小生成树 (各边权值和最小)
            • 最短路径
            • 有向无环图':通常用来描述一个工程或系统的进度
    • 第5章查找与排序
      • 查找
        • 1)概念
        • 2)线性表的查找
        • 3)树表的查找
          • '二叉排序树':
          • '平衡二叉树'(AVL):
        • 4)散列表的查找(哈希表)
            • '开放地址法':
            • '链地址法'(java中HashSet的存储方式):
      • 排序
        • 1)插入排序
          • 直接插入排序(按照顺序法定位插入位置,运用数组从后往前进行比较)
          • 二分插入排序(按照二分法定位位置)
          • 希尔排序(缩小增量、多遍插入排序)
        • 2)交换排序
          • **冒泡排序 O(n²)**
          • **快排 O(n*log2 n) 递归**
        • 3)选择排序
          • **简单选择排序:**
          • **堆排序:**
        • 4)归并排序
        • 5)基数排序
      • 排序时间汇总:
第0章绪论

1.抽象数据类型

ADT 抽象数据类型名 {
    'Data'
        数据对象:〈数据对象的定义〉
        数据关系:〈数据关系的定义>
    'Operation'
        操作1:
            初始化操作
            结果描述
        操作2:
            ...
        操作3:
            ...
} ADT 抽象数据类型名

2.计算时间复杂度(离散数学)

O(n)的相关计算

第1章线性表 分类:顺序表和链表 1.顺序表(数组存储)

线性表里面存储内容的类型必须相同

因为线性表里内容为:数组(存放数据),长度(记录大小)

1)(数据类型)
     struct{
         elem[100];//不一定是一维数组,可以根据需求改变 如自定义结构类型
         int length
     }L
2.链表(链式存储)

结构:数据 和指针(指向下一个数据)

注:最后一个结点指针域为NULL

1)(数据类型)
typedef struct  LNode{
            ElemType   data;
            struct  LNode   *next;//作为接收下一个链表地址的指针(next=&a1) next类型和当前类型一致
        }LNode,*Linklist//Linklist是结构体的指针类型名
2)head和头结点

head:指向链表中第一个结点的指针

头结点:不储存任何信息的结点,其指针指向第一个真正结点

3)主要操作

‘初始化操作’:

​ 在带头结点的情况下,则需建立一个其指针域的指针为NULL的头结点,并令头指针指向该结点

void InitList(Linklist &L){//传入一个指针变量 L
L = new LNode; //给指针L分配空间 大小为下一个LNode
if (!L) exit(1);// 存储空间分配失败
 L->next = NULL; //头结点的指针next指向空 
}

删除:

q=p->next;//引入一个q结点便于free掉
p->next=q->next;//相当于将p的next 跳过
delete q;

‘建立链表’:

​ ‘头插法’:插入头结点的后一位即可(数据插入顺序为逆序

 void CreateList_H(Linklist &L,int n){//n个元素
​      L=new LNode;
​      L->next=NULL;//建立一个带头结点的单链表
​      for(i=n;i>0;--i){//逆序
 p=new LNode; //生成新的结点p
 scanf(&p->data); //手动输入插入的元素值
p->next=L->next; //插入到表头 
L->next=p;
}
}

​ ‘尾插法’:插入尾结点的后一位 要引入尾指针’r’(数据插入为顺序

  void CreateList_R(Linklist &L,int n){#n个元素
​      L=new LNode;
​      L->next=NULL;//建立一个带头结点的单链表
​      r=L; //将尾指针指向头结点
​      for(i=n;i>0;i++){
​        p=new LNode;//生成新的结点p
​        scanf(&p->data); //手动输入插入的元素值
​        p->next=NULL;
​        r->next=p; //插入到表尾部
​        r=p; //r指向新的尾结点
​      }
​    }
4)分类 循环链表 (将表尾的指针指向’头结点’

‘特点’:

​ 从任一结点出发,沿着链可访问全部结点;

​ 运算与单链表基本一致,仅是循环结束条件为P->next==L (L为头指针);

​ 判断是否是表尾结点:p->next==L ;

双向链表 (方便查询前一个结点

:结构中多了一个前趋指针,方便对前一个进行查询

第2章栈和队列

注意进栈出栈那种排序题,见作业2

栈 (有后进先出的特性

1)'栈的定义:

可以在表尾进行插入和删除的线性表

表尾称为栈顶:top, 表头称为栈底:base

stacksize:栈的最大存储上限

2)数据类型 顺序栈 (以数组为格式存储
        typedef struct{
            int stacksize;//栈的大小
            SElemType *top;//指向栈顶元素的上一个的位置
            SElemType *base;//指向栈底元素
        }SqStack;
链式栈 (以链表形式存储
        typedef struct{
            SElemType data;
            struct StackNode *next;
        }StackNode,*LinkStack;
3)主要操作

‘入栈’:给top指针所值的区域赋值,top指针上移一个

‘出栈’:top指针下移,返回top现在所指的元素


队列 (有先进先出的特性

1)队列的定义:

可以在表尾进行插入 在表头进行删除的线性表,队头(Front) 队尾(Rear)

解决上溢的办法:引入循环队列,求余数(%)即可

解决队满的办法:少用一个元素空间

(rear+1)%maxsize==front;
2)数据类型 顺序队列(以数组为格式存储
    typedef struct{
        Qelementtype *base;//指向数组的首元素
        int front;//指向队头的下标
        int rear; //指向队尾的下标
    }SqQuence;
链式队列 (以链表形式存储
   typedef struct QNode{
        Qelementtype data;
        struct Qnode *next;
    }QNode,*QuenePtr;/
        }
    }
快排 O(n*log2 n) 递归

1.找一个中心形成两个子表’左子表’小’右子表’大

2.对各子表重新选择中心(方法同上)

3.如果只有一个中心点结束

‘子表的形成’:

1.将第0号位置空下,存储中心点,'low’变为空

2.前后两指针’low’&‘high’,如果’high’小于中心点,'high’和’low’值交换从两头向中间交替逼近的思想

3.递归调用,直到表剩1个

int L[100];//定义顺序表
int length=0;
void Qsort(int *L,int low,int high){
    int center;
    if (low 
        center=Partition(L,low,high);//找到中心点
        Qsort(L,low,center-1);//对左子表排序
        Qsort(L,center+1,high);//对右子表排序
    }
}
int Partition(int *L,int low,int high){
    int key;
    L[0]=L[low];key=L[low];//将中心点调整到0处
    while (low
        while (low=key)
            --high;
        L[low]=L[high];
        while (low 
3)选择排序 
简单选择排序: 

1.从所有的数据元素中挑一个最小的与第一个进行交换

2.第二次从第二个开始找最小值

3.依次排序

堆排序:

堆定义:若n个元素的序列满足(实际为完全二叉树)

‘小根堆’:ai

‘大根堆’:ai>a2i&&ai>a(2i+1)

‘输出堆顶元素对其余元素进行调整’:

1.输出堆顶后,以堆中最后一个元素代替它

2.将其与左右子树的结点进行比较,小了交换

3.重复,直到叶子结点

‘堆的建立’:

1.所有非叶子结点(n/2–1)进行排序即可(顶点和自己的左右子树进行比较)

2.根节点需要从上往下对比完全

‘堆排序’:

1.进行堆排序

2.输出根

3在进行调整、输出

4)归并排序

‘思路’:

1.两两排序合并成一个有序的

2.四四合并

…

5)基数排序

方法:

分配+收集(数字根据实际情况而定)

​ '0-9’数字,第一次按照’个位’分配,分配后按照顺序取出

'0-9’数字,第二次按照’十位’分配后,按照顺序取出

排序时间汇总:

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/972704.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号