数据结构导论-1.概述

￡神魔★判官ぃ 2022-05-14 04:28 218阅读 0赞

*  **数据结构导论-概论**
    
     *  定义：数据结构是相互之间存在一种或多重特定关系的**数据元素的集合**。包括数据的逻辑结构、数据的存储结构和数据的基本运算。
     *  数据：所有被计算机存储、处理的对象
     *  数据元素：数据的基本单位。（亦称结点、元素、顶点、记录等）
     *  数据项：数据不可分割的最小标识单位。
     *  关系：数据可由若干个数据元素组成，而数据元素又可由若干个数据项组成。
     *  逻辑结构
        
         *  指数据元素之间的逻辑关系。
         *  逻辑关系指数据元素之间的关联方式或“邻接关系”。
         *  四类基本结构
            
             *  集合 
             *  线性结构 
             *  树形结构 
             *  图结构
         *  逻辑结构数学模型二元组：B=(D,R)  
            B表示数据结构；D是某个数据对象，是数据元素的集合；R是D中各数据元素之间关系的有限集合。  
            例子：  
            B=(D,R)  
            D=｛春，夏，秋，冬｝  
            R=｛<春，夏>，<夏，秋>，<秋，冬>｝
     *  存储结构
        
         *  数据的逻辑结构在计算机中的实现称为数据的存储结构。
         *  包括两个部分：1、存储数据元素；2、数据元素之间的关联方式。
         *  关联方式
            
             *  顺序存储方式：指所有存储结点存放在一个连续的存储区里。
             *  链式存储方式：指每个存储结点除了含有一个数据元素外，还包含指针，每个指针指向一个与本结点有逻辑关系的结点，用指针表示数据元素之间的逻辑关系。
             *  还有索引存储方式和散列存储方式。
         *  运算
            
             *  是指在某种逻辑结构上施加的操作，即对逻辑结构的加工。
             *  建立、查找、读取、插入、删除等。
     *  算法及描述  
        运算的实现是指该运算的算法。
        
         *  函数描述形式  
            函数类型 函数名（函数参数表）  
            //算法说明  
            ｛  
            语句序列  
            ｝
         *  输入、输出语句  
            输入语句：scanf｛格式串，变量1，...，变量n｝；  
            输出语句：printf｛格式串，变量1，...，变量n｝；
         *  赋值语句  
            变量名=表达式；
         *  选择语句  
            1、条件语句  
            if（表达式） 语句；  
            或  
            if（表达式） 语句；  
            else 语句  
            2、分支语句  
            switch  
            ｛  
             case 条件1：语句序列；break；  
             case 条件2：语句序列；break；  
            ....  
             case 条件n：语句序列；break；  
             default； 语句序列；  
            ｝  
            其中“default； 语句序列；”可以省略
         *  循环语句  
            for（赋初值表达式序列；条件；修改表达式序列）语句；  
            while（条件）语句；  
            do｛  
            语句；  
            ｝while（条件）；
         *  结束语句  
            1、函数结束语句：return 表达式；  
            2、case结束语句：break；  
            3、异常结束语句：exit（异常代码）；
         *  出错语句 error（“错误描述”）
         *  注释  
            单行注释：//注释内容  
            多行注释：/\*注释内容\*/
     *  算法分析
        
         *  评价算法的好坏的因素：
            
             *  正确性
             *  易读性
             *  健壮性
             *  时空性
         *  时间复杂度
            
             *  T(n)=O(f(n))
         *  空间复杂度
            
             *  S(n)=O(g(n))