数据结构易错整理1

目录

数据结构的基础概念

数据结构基础概念

数据结构的逻辑结构

数据结构的物理结构

算法分析

时间复杂度

例题

数据结构的基础概念

数据结构基础概念

设计存储结构时不仅要存储格数据元素的值，而且还要存储数据元素之间的关系

数据结构具有特定关系的数据元素的集合

在数据结构中按存储结构可把数据结构分为书序结构和链式结构

数据机构相同对应的存储结构也相同，相同的数据结构可以由不同存储结构实现

数据逻辑结构与数据元素本身的形式相对位置和个数无关

数据项是数据的最小元素 ，数据元素使数据的基本单位 

数据机构的定义为（D,S）,其中d是数据元素的集合，s是d上的有限集

数据结构的逻辑结构

树的存储结构是不是线性逻辑

逻辑结构与所使用的计算机无关

数据结构的物理结构

链式存储不能通过计算直接确定第i个结点

链式存储要求每个节点占用一片连续的存储区域

数据存储结构有  顺序存储，链式存储，索引存储，散列存储。其中散列表是散列存储

顺序表按照关键字查找插入删除速度慢，单数寻存取和随机存取第i个元素快

顺序有序表查找和存取速度快但插入删除速度慢

散列表查找插入和删除速度快但不能进行顺序存取

链接表插入删除和顺序存取速度快但查找速度慢

算法分析

同一个算法实现语言的级别越高执行效率越低

算法是对特定问题求解步骤的一种描述

时间复杂度

基础的排序算法 在最坏的情况下的计算时间复杂度的下界是

表明算法的执行时间与成正比

算法的时间复杂度与选择的程序设计语言无关

在一个元素为n的数组里找到升序排在n/5位置的元素的最优算法时间复杂度是

时间复杂度的含义是执行时间与问题规模无关

例题

该程序的时间复杂度是多少

int sum = 0;
for(int i = 1; i < n; i * 2){for(int j = 0; j < i; j++){sum++;    }
}

首先外层循环是x = log_{2}n 

sum++ 是等比数列求和 为a 1-q^{n}/1-q