admin 管理员组文章数量: 1086019
2024年4月21日发(作者：应用程序中的服务器错误)
第1章 绪论
内容提要：
◆ 数据结构研究的内容。
针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。
数据结构涵盖的内容：
◆ 基本概念：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型。
数据——所有能被计算机识别、存储和处理的符号的集合。
数据元素——是数据的基本单位，具有完整确定的实际意义。
数据对象——具有相同性质的数据元素的集合，是数据的一个子集。
数据结构——是相互之间存在一种或多种特定关系的数据元素的集合，表示为：
Data_Structure=（D, R）
数据类型——是一个值的集合和定义在该值上的一组操作的总称。
抽象数据类型——由用户定义的一个数学模型与定义在该模型上的一组操作，
它由基本的数据类型构成。
◆ 算法的定义及五个特征。
算法——是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输
出的计算步骤。
算法的基本特性：输入、输出、有穷性、确定性、可行性
◆ 算法设计要求。
①正确性、②可读性、③健壮性、④效率与低存储量需求
◆ 算法分析。
时间复杂度、空间复杂度、稳定性
学习重点：
◆ 数据结构的“三要素”：逻辑结构、物理（存储）结构及在这种结构上所定义的操作（运
算） 。
◆ 用计算语句频度来估算算法的时间复杂度。
第二章 线性表
内容提要：
◆ 线性表的逻辑结构定义，对线性表定义的操作。
线性表的定义：用数据元素的有限序列表示
◆ 线性表的存储结构：顺序存储结构和链式存储结构。
顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
链式存储结构: 其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一
定相邻。通过指针来实现！
◆ 线性表的操作在两种存储结构中的实现。
数据结构的基本运算：修改、插入、删除、查找、排序
1) 修改——通过数组的下标便可访问某个特定元素并修改之。
核心语句: V[i]=x;
顺序表修改操作的时间效率是 O(1)
2) 插入——在线性表的第i个位置前插入一个元素
实现步骤：
①将第n至第i 位的元素向后移动一个位置；
②将要插入的元素写到第i个位置；
③表长加1。
注意：事先应判断: 插入位置i 是否合法?表是否已满?
应当符合条件： 1≤i≤n+1 或 i=[1, n+1]
核心语句：
for (j=n; j>=i; j--)
a[j+1]=a[ j ];
a[ i ]=x;
n++;
插入时的平均移动次数为：n(n+1)/2÷（n+1）＝n/2≈O(n)
3) 删除——删除线性表的第i个位置上的元素
实现步骤：
①将第i+1 至第n 位的元素向前移动一个位置；
②表长减1。
注意：事先需要判断，删除位置i 是否合法?
应当符合条件：1≤i≤n 或 i=[1, n]
核心语句：
for ( j=i+1; j<=n; j++ )
a[j-1]=a[j];
n--;
版权声明：本文标题：理工类专业课复习资料-数据结构知识点全面总结—精华版 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1713678115a646582.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论