《2.1节线性数据结构-基本概念》由会员分享，可在线阅读，更多相关《2.1节线性数据结构-基本概念（30页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性数据结构2.1.12.1.1 数据和数据结构数据和数据结构2.1.2 2.1.2 数据结构研究的内容和方法数据结构研究的内容和方法2.1.3 2.1.3 算法和算法和算法分析算法分析2.12.1 基本基本概念概念数据数据描述客观事物的数字、字符以及一切能 够输入到计算机中，并且能够被计算机 程序处理的符号的集合。数据元素数据元素表示一个事物的一组数据，是数据的基 本单位，又称结点。在计算机程序中通 常作为一个整体进行处理。一个数据元 素由若干数据项构成。数据结构数据结构数据元素之间具有的关系，即数据的组 织形式。2.1.1 数据和数据结构数据项数据项具有独立含义的最小标识单位,是
2、数据的最小单位数据元素数据元素数据项数据项学号姓名性别籍贯出生年月住址06048001赵玲女上海1987.10上海06048002杨扬男北京1987.3北京 数据数据描述客观事物的数字、字符以及一切能 够输入到计算机中，并且能够被计算机 程序处理的符号的集合。数据元素数据元素表示一个事物的一组数据，是数据的基 本单位，又称结点。在计算机程序中通 常作为一个整体进行处理。一个数据元 素由若干数据项构成。数据结构数据结构数据元素之间具有的关系，即数据的组 织形式。2.1.1 数据和数据结构表结构学号姓名 性别籍贯出生年月住址06048001 赵玲女上海1987.10上海06048002 杨扬男北京
3、1987.3北京 学籍登记表交通图乌鲁 木齐兰州西安呼和 浩特 北京郑州成都1892 1145668676695511842图结构1. 研究数据元素之间的客观联系。2. 研究具有某种逻辑关系的数据在计算机存储器内的存储方式。3. 研究如何在数据的各种结构(逻辑的和物理的)的基础上对数据实施一系列有效的基本操作。 逻辑结构存储结构1.2 数据结构研究的内容算法逻辑结构：计算机处理的数据元素的组织形式及其相互间的关系。由数据元素的有限集合及所有数据元素之间的关系组成。记为：Data_Structure = (D, R)其中，D是数据元素的有限集，R是所有数据元素之间的关系的有限集合。 根据数据元素
4、间关系的基本特性，有四种基本数据结构根据数据元素间关系的基本特性，有四种基本数据结构 集合结构集合结构 数据元素间除数据元素间除“ “同属于一个集合同属于一个集合” ”外，无其它关系外，无其它关系 线性结构线性结构 一个对一个，如线性表、栈、队列一个对一个，如线性表、栈、队列 树形结构树形结构 一个对多个，如树一个对多个，如树 图状结构图状结构 多个对多个，如图多个对多个，如图集合结构集合结构数据结构: SET =（D,R） D = 01,02,03,04,05,06,07,08,09,10 R = 08010305020704060910集合结构示意图线性结构线性结构数据结构 LINEARI
5、TY =（D,R）D = 01,02,03,04,05,06,07,08,09,10 R = , , 05010308020704060910线性结构示意图数据元素之间的联系：1:1树结构树结构数据结构 TREE =TREE =（D,RD,R） D D = 01,02,03,04,05,06,07,08,09,10 = 01,02,03,04,05,06,07,08,09,10 R = , R = , , , 01020304070809050610树结构示意图数据之间的联系：1：NGraph = ( D, R )D = 1,2,3,4,5,6,7,8,9 R = ,图结构图结构数据之间的联系
6、： M：Ns=0;+x;s=0;2 2O(1)O(1)for(i=1;i=n;+i)for(i=1;i=n;+i)+x;s+=x;+x;s+=x;n+2nn+2nO(n)O(n)for(j=1;j=n;+j)for(j=1;j=n;+j)for(k=1;k=n;+k)for(k=1;k=n;+k)+x;s+=x;+x;s+=x;n+3nn+3n2 2O(nO(n2 2) )例例2 2：例例3 3：频度频度时间复杂度时间复杂度程序程序百钱买百鸡问题百钱买百鸡问题: : 100100元钱买元钱买100100只鸡，母鸡每只只鸡，母鸡每只5 5 元，公鸡每只元，公鸡每只3 3元，小鸡元，小鸡3 3只只
7、1 1元，问共可以买多少元，问共可以买多少 只母鸡、多少只公鸡、多少只小鸡？只母鸡、多少只公鸡、多少只小鸡？for (i=0; i=100; i+) for (i=0; i=100; i+)for (j=0; j=100; j+) for (j=0; j=100; j+) for (k=0; k=100;k+) for (k=0; k=100;k+) if ( if (k%3=0 printf(“%d,%d,%dn”, i,j,k); 求解：求解：设母鸡、公鸡、小鸡各为设母鸡、公鸡、小鸡各为i,j,ki,j,k只，则有：只，则有： i+j+ki+j+k=100=100 5i+3j+k/3=10
8、05i+3j+k/3=100 只需要解出本方程就可以得到答案。只需要解出本方程就可以得到答案。 方法方法1 1：用三重循环用三重循环方法方法2 2、3 3：用两重循环用两重循环 因总共买因总共买100100只鸡，所以小鸡的数目可以由母鸡数和公鸡数只鸡，所以小鸡的数目可以由母鸡数和公鸡数 得到。得到。for ( i=0;i100;i+)for ( i=0;i100;i+)for (j=0;j100;j+) for (j=0;j100;j+) k=100-i-j ;k=100-i-j ;if ( if (k%3=0 printf(“%d,%d,%dn”,i,j,k); for (for (i i=
9、0;i=0;i2020;i ;i+)+)for ( for (j=0;jj=0;j3333;j ;j+) +) k=100-i-j ;k=100-i-j ;if ( if (k%3=0 ); 方法方法4 4：用一重循环用一重循环 由由i+j+k=100i+j+k=100和和5*i+3*j+k/3=1005*i+3*j+k/3=100合并为一个方程：合并为一个方程： 14*i+8*j=200, 14*i+8*j=200, 简化简化: : 7*i+4*j=1007*i+4*j=100得得: : i i不超过不超过1414，i i必为必为4 4的倍数？的倍数？! ! for ( for ( i i=
10、0; =0; i i=14; =14; i i+=4+=4 ) ) j = (100-7*j = (100-7*i i)/4;)/4;k=100-i-j k=100-i-j; ;if (if (k%3=0k%3=0) )printfprintf(“%(“%d,%d,%dd,%d,%dn”, n”, i,j,ki,j,k); ); 上面四个方法中，上面四个方法中，第一个方法的循环次数为：第一个方法的循环次数为：100*100*100,100*100*100,一一 百万次百万次；第二个方法的循环次数为：第二个方法的循环次数为：100*100100*100，1 1万次万次 ；第三个方法为：第三个方法为：20*3320*33，660660次次; ;第四个方法为：第四个方法为：4 4次次. . 由此可见，由此可见，算法的设计至关重要算法的设计至关重要。BACKBACK2. 2. 数据所占用的存储空间。数据所占用的存储空间。3 3. . 算法执行时需要的辅助空算法执行时需要的辅助空 间间。1. 1. 指令、常量、变量所占用的存储空间。指令、常量、变量所占用的存储空间。一一个个算法的实现算法的实现在在计算机计算机中所占用的存储空间中所占用的存储空间 大致包括三个方面：大致包括三个方面：3.空间复杂度时间复杂度和空间复杂度的关系相互矛盾相互矛盾
