2017-04-06 19:44:03 yuanlaijike 阅读数 895
  • 初级学软件之ASP.NET 第六季 水晶报表

    主讲内容: 第一讲 水晶报表简介 第二讲 水晶报表结构组成 第三讲 水晶报表数据库访问模式-提取模式 第四讲 水晶报表数据库访问模式-提取模式 2 第五讲 水晶报表数据库访问模式-推入模式 第六讲 分组和排序 第七讲 数据筛选方式 第八讲 “抑制显示”功能的使用 第九讲 “选择讲师”-使用参数字段 第十讲 图表的使用

    2963 人正在学习 去看看 胡延亮

数据结构笔记链接:

第一章 绪论

第二章 线性表

第三章 栈和队列

第四章 串

第五章 数组和广义表

第六章 树和二叉树

第七章 图

第八章 排序

第九章 查找



1.1 数据结构的定义和分类

1.1.1 数据结构的定义

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。

数据结构是带有结构的数据元素的集合,数据元素之间的相互关系,即数据的组织形式。数据的组织方法与效率密切相关,采用不同数据的组织方法其处理效率也不同,对问题找出合适的数据组织方法十分重要。

1.1.2 数据结构包括的内容

(1)逻辑结构:数据元素之间的逻辑关系。
(2)存储结构:数据元素及其关系在计算机存储器内的表示。
(3)操作:数据的运算(检索、排序、插入、删除、修改)。

1.2 为什么学习数据结构

1.2.1 学习数据结构的作用

(1)计算机内的数值运算依靠方程式,而非数值运算(如表、树、图等)则要依靠数据结构。
(2)同样的数据对象,用不同的数据结构来表示,运算效率可能有明显的差异。
(3)程序设计的实质是对实际问题选择一个好的数据结构,加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。

1.2.2 电话号码查询问题

(1)要写出好的查找算法,取决于这张表的结构及存储方式。
(2)电话号码表的结构和存储方式决定了查找(算法)的效率。

求解方法:
(1)顺序表法:数组存储,一次查找结构简单,但效率偏低。
(2)索引结构法:按姓氏索引定位,支持快速查找。

1.3 数据结构的基本概念

数据结构分为逻辑结构和存储结构:

  • 逻辑结构定义了数据元素之间的逻辑关系。

  • 存储结构是逻辑结构在计算机中的实现。

一种逻辑结构可以采用不同存储方式存放在计算机中,但都必须反映出要求的逻辑关系。

1.3.1 基本逻辑结构

(1)集合结构:结构中的数据元素之间除了同属于一个集合的关系外无任何其他关系。
(2)线性结构:结构中的数据元素之间存在着一对一的线性关系。
(3)层次结构:结构中的数据元素存在着一对多的层次关系。
(4)网状结构:结构中的数据元素存在着多对多的任意关系。

1.3.2 基本存储结构

存储结构(又称物理结构),数据元素之间关系在计算机中的表示方法:
(1)顺序结构:一组连续单元(顺序存储结构,如数组)
(2)非顺序结构:一组任意存储单元(非顺序存储结构,如链表)

1.4 算法

1.4.1 算法的概念和特点

算法是由若干条指令组成的有穷序列,是为解决特定问题而规定的有限集合。

算法具有以下的特点:

  • 输入:具有0个或多个输入的外界量。

  • 输出:至少产生1个输出。

  • 有穷性:每一条指令的执行次数必须是有限的。

  • 确定性:每条指令的含义都必须明确,无二义性。

  • 可行性:每条指令的执行时间都是有限的。

1.4.2 算法的定义

1.4.2.1 正确性

算法的正确性具有以下三个层次:

  • 所设计的程序对于几组输入数据能够得出满足要求的结果。

  • 所涉及的程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得到满足要求的结果。

  • 程序对于一切合法的输入数据都能产生满足要求的结果。

1.4.2.2 可读性

一个好的算法首先应该便于人们理解和相互交流,其次才是机器可执行。可读性好的算法有助于人们对算法的理解,难懂的算法易于隐藏错误且难于调试和修改。

1.4.2.3 健壮性

即对非法输入的抵抗能力。它强调即使输入非法数据,算法应能加以识别并作出处理,而不是产生误动作或陷入瘫痪。

1.4.2.4 高效率和低存储量

算法的效率通常是指算法的执行时间。对于一个具体的问题的解决通常可以有多给算法,对于执行时间短的算法其效率就高。

所谓的存储量要求,是指算法在执行过程中所需要的最大存储空间,这两者都与问题的规模有关。

1.4.3 算法与程序的区别

(1)一个程序不一定满足有穷性,但算法一定。
(2)程序中的指令必须是机器可执行的,而算法无此限制。
(3)一个算法若用机器可执行的语言来描述,则它就是一个程序。

1.5 算法描述

算法描述采用类语言,类语言接近于高级语言而又不失严格的高级语言。它具有高级语言一般的语句格式,撇掉语言中的细节,把注意力主要集中在算法处理步骤本身的描述上。

算法描述的要点如下:

  • 加上必要的注释(注明功能和参数)

  • 避免函数返回值隐含说明(全程量隐接口)

  • 预定义常量和类型

  • 使用有意义的函数名与变量名

  • 避免可能出现的二义性表达

  • 规范多分支转向

  • 简化输入、输出描述

  • 注意不同的退出语句区别

1.6 算法分析

算法评价的标准主要是其执行占用机器资源在执行时间存储空间上的表现。

1.6.1 时间复杂度

算法的执行时间 = 其所有语句执行时间的总和。

语句的执行时间 = 该条语句的执行次数 * 执行一次所需时间。

语句频度:指该语句在一个算法中重复执行的次数。

时间复杂度是以语句频度刻画随问题规模n增加的函数f(n)执行时间度量,记作T(n)=O(f(n))

常见函数的时间复杂度按数量递增排列及增长率:

常数阶O(1)
对数阶O(log2n)
线性阶O(n)
线性对数阶O(n log2n)
平方阶O(n2)
立方阶O(n3)
……
k次方阶O(nk)
指数阶O(2n)

例如分析以下x=x+1语句的时间复杂度:

(1)时间复杂度为O(1),称为常数阶

x=x+1; 

(2)时间复杂度为O(n),称为线性阶

for(i=1; i<=n; i++){
    x=x+1; 
}

(2)时间复杂度为O(n2),称为平方阶

for(i=1; i<=n; i++){
    for(j=1; j<=n; j++){
        x=x+1; 
    }
}

1.6.2 空间复杂度

空间复杂度是指算法在计算机内执行时所需存储空间的度量,以存储单元个数刻画随问题规模增加的函数f(n)存储空间量度,记作:S(n) = O(f(n))

1.6.3 算法分析的目的

目的在于选择合适算法和改进算法

1.7 例题

1.7.1 例1

for ( i=1; i < n; i++ ) {   
    y = y+1;        //语句1
    for ( j=0; j<=(2*n); j++ )
    x++;            //语句2 
}

解:

语句1频度为(n-1);语句2频度为(n-1)x(2n+1)=2n2-n-1,因此时间复杂度T(n)=2n2-2=O(n2)。

1.7.2 例2

i=1;            //语句1
while (i<=n){
    i=i*2;      //语句2
}   

解:

语句1频度为1;设语句2频度为f(n),则有2f(n)<=n,即f(n)<=log2n,去极大值,f(n)=log2n,因此时间复杂度T(n)=1+log2n=O(log2n)。

2019-03-20 00:04:07 qq_39706357 阅读数 104
  • 初级学软件之ASP.NET 第六季 水晶报表

    主讲内容: 第一讲 水晶报表简介 第二讲 水晶报表结构组成 第三讲 水晶报表数据库访问模式-提取模式 第四讲 水晶报表数据库访问模式-提取模式 2 第五讲 水晶报表数据库访问模式-推入模式 第六讲 分组和排序 第七讲 数据筛选方式 第八讲 “抑制显示”功能的使用 第九讲 “选择讲师”-使用参数字段 第十讲 图表的使用

    2963 人正在学习 去看看 胡延亮

数据结构整理

一、数据结构概述

1.数据结构概述

数据的储存结构:顺序储存结构、链式储存结构
数据的逻辑结构:集合结构、线性结构、树形结构、图像结构

2.算法概述

算法的定义:解决问题的思路
算法的特性:输入、输出、有穷性、确定性、可行性
算法基本要求:确定性、可行性、健壮性、时间复杂度、空间复杂度

二、线性结构

1.数组

基本使用(数组元素的添加、删除都是赋值)
面向对象的数组
数组的有序性
查找算法:线性查找(按顺序查找)、二分查找法

2.栈

压入元素、取栈顶元素、查看栈顶元素、查看栈是否为空
栈是一种“先进后出”的一种数据结构,有压栈出栈两种操作方式。
在这里插入图片描述
栈主要分为两类:

  • 静态栈 :静态栈的核心是数组,类似于一个连续内存的数组,我们只能操作其栈顶元素。
  • 动态栈:链表作为数据的存储方式。

3.队列

像栈一样,队列也是一种线性表。它允许在表的一端插入数据,在另一端删除元素。插入元素的这一端称之为队尾。删除元素的这一端我们称之为队首。队列的结构如下图所示。
队列的特性:

  • 在队尾插入元素,在队首删除元素
  • FIFO(先进先出),就向排队取票一样
  • 在这里插入图片描述

4.单链表

链表是最基本的数据结构,其储存的原理如图所示
在这里插入图片描述
上面展示的是一个单链表的存储原理图,简单易懂,head为头节点,他不存放任何的数据,只是充当一个指向链表中真正存放数据的第一个节点的作用,而每个节点中都有一个next引用,指向下一个节点,就这样一节一节往下面记录,直到最后一个节点,其中的next指向null。

链表有很多种,比如单链表,双链表等等。我们就对单链表进行学习,其他的懂了原理其实是一样的。

5.循环链表

1、循环链表的定义

循环链表的任意元素都有一个前驱和一个后继,所有数据元素在关系上构成逻辑上的环。
循环链表是一种特殊的单链表,尾结点的指针指向首结点的地址。
循环链表的逻辑关系图如下:
在这里插入图片描述

2、循环链表的设计实现

循环链表的设计实现要点:
A、通过模板定义CircleList,继承自LinkedList
B、定义连接链表首尾的内部函数
C、实现首元素的插入和删除操作
D、重写清空操作和遍历操作

3、循环链表的实现关键

A、插入位置为0时,头结点和尾结点均指向新结点,新结点作为首结点插入链表。
B、删除位置为0时,头结点和尾结点指向位置为1的结点,删除销毁首结点

6.双链表

双向链表(双链表)是链表的一种。和单链表一样,双链表也是由节点组成,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。

和单向链表相比有以下优势:

  • 插入删除不需要移动元素外,可以原地插入删除
  • 可以双向遍历

在这里插入图片描述
删除单个图示:
在这里插入图片描述

7.递归

斐非波那契、汉诺塔问题

三、排序结构

1.时间复杂度和空间复杂度

1.交换排序:冒泡排序、快速排序
2.插入排序:直接插入排序、希尔排序
3.选择排序:简单选择排序、堆排序
4.归并排序
5基数排序

2.八种常用的排序算法

3.八种排序算法的对比

四、树结构

1.树的结构概述

2.二叉树

  1. 链式储存的二叉树
    创建二叉树、添加节点、查找节点、树的遍历(前序遍历、中序遍历、后序遍历)、删除节点
  2. 顺序储存的二叉树

3.线索二叉树

4.赫夫曼树

5.二叉排序树(二叉查找树、二叉搜索树)BST

对于二叉树中任何一个非叶子节点,要求左字节点比当前节点值小,右字节点比当前节点值大

6.AVL树(平衡二叉树)

对任何一个子树而言,左子树和右子树的高度差的绝对值不超过1。

7.多路查找树

五、哈希表

散列函数:直接定值法、数据分析法、平方取中法、取余法、随机数法

六、图结构

1.基本概念
图结构、邻接、路径、有向图和无向图、带权图
2.图的遍历
深度优先搜索算法、广度优先搜索算法

2017-12-02 22:58:18 m0_38128121 阅读数 1465
  • 初级学软件之ASP.NET 第六季 水晶报表

    主讲内容: 第一讲 水晶报表简介 第二讲 水晶报表结构组成 第三讲 水晶报表数据库访问模式-提取模式 第四讲 水晶报表数据库访问模式-提取模式 2 第五讲 水晶报表数据库访问模式-推入模式 第六讲 分组和排序 第七讲 数据筛选方式 第八讲 “抑制显示”功能的使用 第九讲 “选择讲师”-使用参数字段 第十讲 图表的使用

    2963 人正在学习 去看看 胡延亮

传统上数据结构分为逻辑结构和物理结构
逻辑结构:就是数据对象中数据元素之间的相互关系

四大逻辑结构

集合结构:集合结构中的数据元素除了在同属于一个集合外没有别的其他关系

线性结构:线性结构中的数据元素之间的关系是一对一的关系

树形结构:树形结构中的数据元素存在一种一对多的层次关系

图形结构:图形结构中的元素是多对多的关系
这里写图片描述

物理结构:数据的逻辑结构在计算机中的存储形式
数据元素的存储方式有两种 : 顺序存储 链式存储

顺序存储:把数据单元放在地址连续的存储单元里,数据的逻辑关系和物理关系是一致的
链式存储:把数据元素存放在任意的存储单元里,这组存储单元可以是连续的可以是不连续的
这里写图片描述
图片从小甲鱼数据结构视频上面截取下来的 如有侵权 请联系我

2018-02-02 17:23:44 cvper 阅读数 442
  • 初级学软件之ASP.NET 第六季 水晶报表

    主讲内容: 第一讲 水晶报表简介 第二讲 水晶报表结构组成 第三讲 水晶报表数据库访问模式-提取模式 第四讲 水晶报表数据库访问模式-提取模式 2 第五讲 水晶报表数据库访问模式-推入模式 第六讲 分组和排序 第七讲 数据筛选方式 第八讲 “抑制显示”功能的使用 第九讲 “选择讲师”-使用参数字段 第十讲 图表的使用

    2963 人正在学习 去看看 胡延亮

在 数据结构(一)中,我们了解了什么是数据结构的概念,现在我们再复习一下;


数据结构:是相互之间存在一种或多种特定关系的数据元素的集合;


数据结构三部分:逻辑结构,物理结构,运算



一、数据结构的 逻辑结构


      逻辑结构:数据元素之间的逻辑关系;


      简单理解:逻辑结构其实和计算机是没有关系的,现在假设你要建一个漂亮的别墅,

                       那么首先要做的是设计一下房子的图纸,然后再开始建房子;现在设计图纸

                       就相当于逻辑结构,怎么建房子相当于物理结构(不是很贴切,但是有助于理解)


       逻辑结构分类:可以分为 线性结构 非线性结构


        再具体一点分类:线性结构 )(  集合    树形     图状


        可以看出,后面三个都是非线性结构;


二、数据结构的 物理结构(存储结构)


      物理结构(存储结构):数据结构在计算机中的表示;


      简单理解:同上面的逻辑结构的例子,房子可以从下往上一点点建,也可以先来个整体的框架,

                       然后再不断补充,所以不同的建房方法相当于不同的物理结构(存储结构);


       物理结构分类:主要是四类


                               顺序存储     链接存储   索引存储   散列存储

2019-09-19 18:27:33 weixin_43908849 阅读数 37
  • 初级学软件之ASP.NET 第六季 水晶报表

    主讲内容: 第一讲 水晶报表简介 第二讲 水晶报表结构组成 第三讲 水晶报表数据库访问模式-提取模式 第四讲 水晶报表数据库访问模式-提取模式 2 第五讲 水晶报表数据库访问模式-推入模式 第六讲 分组和排序 第七讲 数据筛选方式 第八讲 “抑制显示”功能的使用 第九讲 “选择讲师”-使用参数字段 第十讲 图表的使用

    2963 人正在学习 去看看 胡延亮

先看看官方怎么说的:
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
个人认为:
和斗地主一个道理。数据就是你手里牌,数据结构就是怎么组合你的牌比如三带一,四带二这种。数据结构的选择和打牌一样,出个炸弹翻倍,春天翻倍,四带二偷渡。不同的选择赢的分不同。
总之,数据就是牌,结构就是怎么组合牌,选择数据结构就是怎么出牌

数据结构又分为逻辑结构(logical structure)、物理结构(physical structure)、存储结构(storage structure)

逻辑结构:

1.集合:数据结构中的元素之间除了“同属一个集合” 的相互关系外,别无其他关系;

2.线性结构:数据结构中的元素存在一对一的相互关系;

3.树形结构:数据结构中的元素存在一对多的相互关系;

4.图形结构:数据结构中的元素存在多对多的相互关系。

在这里插入图片描述

数据结构第三章

阅读数 123

博文 来自: zzqgf69
没有更多推荐了,返回首页