数据与数据结构

1、数据与数据结构游光芒1/69一、数据二、数据结构三、数据结构应用2/69一、数据digitalvaluedatabig data数字数值数据大数据 在计算机科学中，数据是指全部能输入到计算机并被计算机程序处理符号总称。1.概念3/69（1）数字 ：砍一刀飘多少血，升一级需要多少经验（2） 数值 ： 砍死一个怪要多少刀 升一级需要多少时间（3） 数据 ： 装备、道具等与哪类场景匹配等，形式有文字、图像、视频、音频等（4） 大数据 ：大数据5V特点：Volume（大量）、Velocity（高速）、Variety（多样）、Value（低价值密度）、Veracity（真实性）。4/692. 数据作用单

2、车信息，采集数据，影响公交线路制订等。热地图，热源，微信中热点区域。依据时间段人数多区域，选择性开什么店；移动带宽适时调整：依据每个时段热源多少，来确定带宽适时往哪边多放一些等。5/69二、数据结构（一）数组与链表（二）字符串、队列与栈（三）树6/69（一）数组与链表同类型数据组成序列。1. 数组数组元素：a0a1a2a3a432124562数组名a：下标：012347/69例1：神奇矩阵 以下列图所表示，由19个数字组成3*3矩阵，其行列、对角线上三数和均相同。编程输出全部神奇矩阵排列方式。8/691.结构出全部三个数字之和15三位数，且三个位置上数字不相同。用数组存放。2.枚举所得数组，每

3、三个三位数结构一个神奇矩阵。每三个数fi,fj,fk 结构 矩阵情况有以下所表示，需依次判断这些情况下对角下之和是否为15。FiFjFkFiFkFjFjFiFkFjFkFiFkFiFjFkFjFi9/69f=number=0for i in range(123,1001): a=i / 100 b=i /10 % 10 c=i % 10 if (a+b+c=15) and (a!=b) and (a!=c) and (c!=b): number+=1 f.append(i)结构三位数字之和为15三位数：10/69枚举全部刚才得到三位数字：for i in range(number): for

4、j in range(i+1,number): for k in range(j+1,number): x1=fi / 100 y1=fi /10 % 10 z1=fi % 10 x2=fj / 100 y2=fj / 10 % 10 z2=fj % 10 x3=fk / 100 y3=fk / 10 % 10 z3=fk % 10 if (x1+x2+x3=15) and (y1+y2+y3=15) and (z1+z2+z3=15) and (x1*x2*x3*y1*y2*y3*z1*z2*z3=362880): if (x1+y2+z3=15) and (z1+y2+x3=15): pr

5、int(fi) print(fj) print(fk) print() #以下5种情况略11/69任务一：数组练习1.输入一串值不一样整数数列，输出递增和递减子序列数目。如数列7，2，6，9，8，3，5，2，1可分为（7，2），（2，6，9），（9，8，3），（3，5），（5，2，1）5个子序列，其中递增数列2个，递减数列3个。2.数组元素插入。输入n个整数及插入位置x和数字y。再输出该数组。比如：输入：57 2 3 4 529输出：7 9 2 3 4 53.求n*n数阵中马鞍数，输出它位置。所谓马鞍数，是指在行上最小 而在列上最大数。以下：（n=5） 5 6 7 8 9 4 5 6 7 8

6、3 4 5 2 1 2 3 4 9 0 1 2 5 4 8 则1行1列上数就是马鞍数。输入n及二维矩阵（数字都不一样），输出马鞍数所在行列位置。12/694. 数学黑洞6174。已知：一个任意四位正整数。将数字重新组合成一个最大数和最小数相减，重复这个过程，最多七步，必得6174。即：764114676174。将永远出不来。输出全部四位数及掉进黑洞步数。5. 以下列图，第1次按1，第2次隔1个按钮按3，第3次隔2个按钮按6，依这类推，按1000次后，把没有按到数字从小到大升序输出。6.求分数准确值。使用数组准确计算M/N(0M s=abcdef s:abcdefstart: 从start 提取

7、到结尾 s=abcdef s0:abcdef:end 从开头提取到end - 1 s=abcdef s:6abcdefstart:end 从start 提取到end - 1 s=abcdef s0:6abcdefstart:end:step 从start 提取到end - 1，每step 个字符提取一个 s=abcdef s0:6:2aceleft:right左侧第一个字符位置/偏移量为0，右侧最终一个字符位置/偏移量为-1 s=abcdef s2:4cd19/69字符串基本操作 连接（+）和重复（*）字符串连接：把两个字符串连接成一个字符串str1=“Py”str2=“thon”s=str1

8、+str2print(s)输出：Python字符串重复：把某个串重复n次str1=“Py”s=str1*3print(s)输出：PyPyPy20/69字符串基本操作字符串比较in运算符 in运算符用于检验是否为子串。运算符需要两个参数：测试字符串和可能包含测试字符串字符串。因为是组员检验，所以它将返回布尔值，指示测试字符串是否包含在第二个字符串中。str1 = Hello if( H in str1):print(H 在变量 str1 中) else: print(H 不在变量 str1 中)运行后显示：H 在变量 str1 中21/69字符串基本操作字符串比较 依据英文字符ASCII码值大小

9、来比较。分三种情况：第一个：串str1长度等于串str2长度时，即m=n，此时采取挨个比较串中字符。比如：str1=“word”，str2=“work”，从左往右，挨个比较，参考ASCII值。str1 = wordstr2 = workif(str1str2):print(str1)else: print(str2) 运行后显示：work22/69字符串基本操作字符串比较 依据英文字符ASCII码值大小来比较。分三种情况：第二种：串str1长度小于串str2长度，且前面一部分相等，即mstr1。str1 = workstr2 = workingif(str1str2):print(str1)e

10、lse: print(str2)运行后显示：working23/69字符串基本操作字符串比较 依据英文字符ASCII码值大小来比较。分三种情况：第三种：存在某个位置xstr2x+1时，则字符串str1str2。str1 = moonstr2 = monkeyif(str1str2):print(str1)else: print(str2)运行后显示：moon24/69字符串基本操作字符串惯用函数函数和方法功效实例len(x)输出字符串x中字符个数x=”Hello!”print(len(x) 输出为：6x.upper()将字符串x中小写字母转大写x=”Hello!”print(x.upper()

11、输出为：HELLO!x.lower()将字符串x中大写字母转小写x=”Hello!”print(x.lower()输出为：hello!x.swapcase()将字符串x中字母大写转小写，小写转大写x=”Hello!”print(x.swapcase()输出为：hELLO!x.find(y)返回字符串x中子串y出现首字符下标，若找不到子串则输出-1x=”Hello!”y=”llo”print(x.find(y)输出为：2x.index(y)返回字符串x中子串y出现首字符下标，若找不到子串则输出异常x=”Hello!”y=”llo”print(x.index(y)输出为：2x.count(y)返回

12、字符串x中子串y重复出现次数x=”I like Python”y=” ”print(x.count(y)y=”like”print(x.count(y)第一个输出为：2第二个输出为：125/69字符串实例 输入一个数字串s(长度小于100)，删去其中k(k0: j=0 while jlen(s)-1 and sj1) and s0=0: temps=s1: s=tempsprint(s)请输入数字串s，长度不超出100位：1298034请输入k：3输出：103429/69任务三：字符串实践1.李雷收到了朋友发给他一封奇怪邮件，里面有段内容是由一些数字和符号组成， 信上面说了，这段内容是加密后内

13、容，并给出了详细加密方法（假定原文英文字母都是大 写），详细方法以下： （1）“ A”变为一个 1 到 100 内随机数*27+1，“ B”变为一个 1 到 100 内随机数*27+2， “Z”变为一个 1 到 100 内随机数*27+26； （2）每个字母变为数字后会加上一个“-”用来分割数字； （3）其它空格和标点字符都按原来表示密文1898-1462-1555-772-835-2084-49-2057-2205-1915-112-1108-2347-1原文任务：输入密文，输出原文。30/69任务三：字符串实践2.某字符串（字节数为3倍数）编码规则以下：（1）将该字符串内码分成3个字节一组

14、，顺次连接后得到24位二进制数；（2）将得到24位二进制数字分成4组，每组6位；（3）在每组数字前补上两个0，得到4个字节二进制数；（4）将（3）中得到四个二进制数分别转换为十进制数；（5）将每个十进制数转换为1个加密字符，对应“密码表”按数值由小到大依次为“ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyx0123456789+/” 小明按照上述方法，设计了一个字符串（仅包含ASCII字符）加密程序，依次将输入字符串中每3个字符ASCII值按编码规则转换为四个加密字符，连接这些加密字符，最终输出加密结果。原串This is an exam

15、ple密文VGhpcOBpcOBhbKBleGFtcGxl31/692.队列 队列是一个特殊线性表，它只允许在表前端（front）进行删除操作，而在表后端（rear）进行插入操作。进行插入操作端称为队尾，进行删除操作端称为队头。32/69队列存放 队列普通按次序结构进行存放，能够用数组来实现。因为队首和队尾位置均是改变，因而需要设置两个数组下标变量head和tail，head指向队首元素，tail指向队尾元素。33/69队列基本操作： 建立队列queue=“”*100head=-1tail=-1 入队tail=tail+1queuetail=“一”出队while headtail: head=

16、head+1 print(queuehead)34/69队列实列模拟实现移动营业厅取号与叫号功效，用程序实现。（1）取号，入队操作（2）叫号，出队操作35/69queue=-1*1000head=-1tail=-1print(请输入详细操作)print(请输入详细操作：)print(1.新到用户（取号）)print(2.下一个用户（叫号）)x=int(input(请输入操作，输入3结束：)while x!=3: if x=1: tail+=1 queuetail=tail print(你当前号码为：A%d%(tail) print(需等候人数为：%d%(tail-head-1) if x=2:

17、 if head=0:print(stacktop)栈基本操作出栈。while top=0:print(stacktop)top=top-140/69栈实例用栈实现一个十进制转二进制程序。41/69stack=-1*100top=-1number=int(input(请输入十进制整数：)while number0: x=number % 2 top=top+1 stacktop=x number=number / 2while top=0: print(stacktop,end=) top=top-142/69栈实践任务：1. 有六个元素FEDCBA 从左到右依次次序进栈，在进栈过程中会有元素

18、被弹出栈。问以下哪一个不可能是正当出栈序列？A) EDCFABB) DECABFC) CDFEBAD) BCDAEF2. 元素R1、R2、R3、R4、R5入栈次序为R1、R2、R3、R4、R5。假如第1个出栈是R3，则第5个出栈不可能是A. R1 B. R2 C. R4 D. R53. 设栈S初始状态为空，元素a, b, c, d, e, f, g依次入栈，以下出栈序列不可能出现是（ ）。A. a, b, c, e, d, f, g B. b, c, a, f, e, g, d C. a, e, d, c, b, f, g D. g, e, f, d, c, b, a43/69栈实践任务：1.

19、 编程求中缀表示式 值。如： (a+b)*c-d*e2. 编程将中缀表示式转后缀表示式。对于题1中缀转后缀为：ab+c*de*-44/69（三）树课标解读：经过列举实例，认识到抽象数据类型对数据处理主要性，了解抽象数据类型概念，了解二叉树概念及其基本操作。1. 抽象数据类型数据类型。它是指一组性质相同值集合及定义在此集合上一些操作总称。如整型、字符串类型等抽象数据类型。是指一个数学模型及定义在该模型上一组操作，ADT基本思想是抽象。比如字符串len函数等。使用时，不用关系len是怎样来，直接使用即能够。45/69（三）树1. 树与二叉树46/69（1）结点（Node）和边（Edge）（2）结点

20、度（Degree）和树度（3）根结点（Root）和叶子（Leaf）（4）孩子结点（Child）和双亲结点（Parents）（5）结点层数（Lever）和树高度（Height）普通树：47/69二叉树：二叉树是以结点为元素有限集，它或者为空，或者满足以下条件：有一个特定结点称为根；余下结点分为互不相交子集L和R，其中R是根左子树；L是根右子树；L和R又是二叉树；树每一个结点能够有任意多个后件，而二叉树中每个结点后件不能超出2；树子树能够不分次序（除有序树外）；而二叉树子树有左右之分。我们称二叉树中结点左后件为左儿子，右后件为右儿子。 二叉树与树不一样地方：48/69二叉树五种基本形态 49/69

21、二叉树两种特殊形态：满二叉树 假如一棵二叉树任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树。（比如图(a)）能够验证含有n个叶结点满二叉树共有2n-1个结点。50/69二叉树两种特殊形态：完全二叉树 假如一棵二叉树最多只有最下面两层结点度数能够小于2，而且最下面一层结点都集中在该层最左边若干位置上，则称此二叉树为完全二叉树（比如图(b)）51/69二叉树性质：（1）在二叉树第i（1）层上，最多有2i-1个结点（2）在深度为k(k1)二叉树中最多有2k-1个 结点。（3）在任何二叉树中，叶子结点数总比度为2结点多1。52/69证实： 设n0为二叉树叶结点数；n1为二叉树中度为

22、1结点数；n2为二叉树中度为2结点数，显然n=n0+n1+n2 （1） 因为二叉树中除了根结点外，其余每个结点都有且仅有一个前件。设 b为二叉树前件个数，n=b+1（2） 全部这些前件同时又为度为1和度为2结点后件。所以又有b=n1+2n2 (3)除v0没有前件外，v1、v2、v3、v4、v5都有一个前件，b=5。而v1和v2为v0后件，v3为v1后件，v4和v5为v2后件，所以b= b=n1+2n2=1+2*2=5。 我们将（3）代入（2）得出n=n1+2n2+1 (4) 比较（1）和（4），得出n0=n2+1,即叶子数比度为2结点数多1 53/69二叉树基本操作：（1）二叉树存放（线性存放

23、 完全二叉树）ABCDEF12345654/69（1）二叉树存放（线性存放 非完全二叉树）ABCDEFGH123457101455/69（1）二叉树存放（链式存放）56/69（2）二叉树遍历 就是按一定规则和次序走遍二叉树全部结点，使每一个结点都被访问一次，而且只被访问一次。因为二叉树是非线性结构，所以，树遍历实质上是将二叉树各个结点转换成为一个线性序列来表示。遍历时，要求先左子树后右子树次序时，能够分为三种遍历：先序遍历：先访问根结点，再访问左子树，最终访问右子树。先序序列：a b d e h i c f g 57/69（2）二叉树遍历中序遍历：先访问左子树，再访问根结点，最终访问右子树。中

24、序序列：d b h e i a f c g 58/69（2）二叉树遍历后序遍历：先访问左子树，再访问右子树，最终访问根结点。后序序列：d h i e b f g c a59/69树实践任务：（1）写出下面二叉树先序遍历、中序遍历、后序遍历60/69树实践任务：（2）假如根高度为 1，含有 61 个结点完全二叉树高度为（ ） A. 5 B. 6 C. 7 D. 8（3）已知一棵二叉树有 10 个节点，则其中至多有（ ）个节点有 2 个子节点 。A. 5 B. 6 C. 7 D. 4（4）二叉树T，已知其先序遍历是1 2 4 3 5 7 6（数字为节点编号，以下同），中序遍历是4 2 1 7 5 3 6 ，则该二叉树后序遍历可能为（ A ）A4 2 7 5 6 3 1 B2 4 1 7 5 3 6 C4 2 1 7 5 6 4 D2 4 1 5 7 3 661/69三、数据结构应用（一）算法与数据结构（二）迭代与递归（三）数据排序（四）数据查找62/69（一）算法与数据结构1.算法效率分析 时间复杂度又称计算复杂度，是指执行程序计算工作量。同一问题，采取不一样算法，程序计算工作量是不一样。【例题】输入100个整数，输出其中