数据结构概述

2019-11-25  本文已影响0人  张_何

数据结构概述(参考资料,严蔚敏的数据结构.高一凡把书中的伪算法全部用代码写了出来)

数据结构定义:

算法:

什么是栈,什么是堆:

所谓的栈内存和堆内存并不是内存里面有一块区域叫栈,有一块区域叫堆.所谓的栈内存和对内存实际上指的是分配内存的算法不一样,如果是以压栈出栈的方式分配的内存,就叫栈内存.如果是以堆排序的方式分配的内存就叫堆内存

预备知识:

struct Student{
    int sid;
    char name[200];
    int age;
};
两种方式: struct Student st = {1000,”zhangsan”,20};
struct Student *pst = &st;
1.st .sid
2.pst—>sid (pst 所指向的结构体变量中的 sid 这个成员)

注意事项:
1.结构体变量不能加减乘除,但是可以相互赋值
2.普通结构体变量和结构体指针变量作为函数传参的问题(结构体形参时,一般要传地址,因为传结构体变量内存开销会大)

CPU 是如何与内存打交道的?

模块一:线性结构(把所有的结点用一根直线穿起来)

结点
struct Node{
     int data;//数据域
     struct Node *pNode; 指针域
}

每一个链表的结点都会有数据域和指针域
如果希望通过一个函数来对链表进行处理,我们至少需要接受链表的哪些参数? 只需要一个参数:头指针.因为我们通过头指针可以推算出链表的其他所有参数

  1. 排序:
  2. 删除结点:
    8.插入结点:

循环队列的讲解:
1.静态队列为什么必须是循环队列
2.循环队列需要几个参数来确定
需要两个参数来确定,front 和 rear
3.循环队列各个参数的含义
两个参数场合不同的含义.建议初学者先记住,然后慢慢体会:
1).队列初始化
front 和 rear 的值都是零
2).队列非空
front 代表的是队列的第一个元素
rear 代表的是队列的最后一个有效元素的下一个元素
3).队列空
front 和 rear 的值相等,但不一定是零
4.静态队列入队伪算法讲解
两步完成:
1.将值存入r 所代表的位置
2.错误写法 r = r+1
正确的写法是: r = (r+1)%数组的长度

image.png
5.循环队列出队伪算法讲解
f = (f+1)%数组的长度
6.如何判断循环队列是否为空
如果 front 和 rear 的值相等,则该队列就一定为空
7.如何判断循环队列是否已满
两种方式:1.多增加一个标志参数(一般不用)
2.少用一个元素(通常使用这种方式) ,如果r和f紧挨着,则队列已满
if ( (r+1)%数组的长度 == f ) 已满;
else 不满;
队列算法:
入队
出队
队列的具体应用: 所有和时间有关的操作都有队列的影子
专题:递归
定义:一个函数自己直接或间接调用自己
image.png

模块二:非线性结构

树

森林转化成二叉树总量的来说就是:如果一个节点有子节点,就把该子节点当做该节点的左子树,如果有兄弟节点,就把兄弟节点,当做该节点的右子树.
下图是有A, B, C 为根节点的数组成的森林,


image.png
树的操作

已知两种遍历序列求原始二叉树:

已知先序和中序 或者 已知后序和中序 才可以唯一的推出一个二叉树,但是已知先序和后序是不能推出一个二叉树的
例子:
示例1:
先序: ABCDEFGH
中序: BDCEAFHG
求后序: DECBHGFA
示例2:
先序: ABDGHCEFI
中序: GDHBAECIF
求后序: GHDBEIFCA
示例3:
中序: BDCEAFHG
后序: DECBHGFA
求先序: ABCDEFGH

模块三: 查找和排序

上一篇下一篇

猜你喜欢

热点阅读