聊聊数据结构基础

发布 2021-05-30 20:22:28 阅读 4968

1. 数据结构概念。

2. 线性表。

3. 栈和队列。

4. 串及模式匹配。

5. 数组和广义表。

6. 数与二叉树。

7. 图。8. 查找。

9. 内部排序。

一、 数据结构。

数据结构是一门研究非数值计算的程序设计问题中数据对象之间的相互关系及其处理方法的课程。科学计算或数据处理、过程控制、对文件的存储和检索及数据库技术等计算机应用,都是对数据进行加工处理的过程。

数据的逻辑结构和存储结构。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

集合是具有松散结构关系的数据对象。

线性结构是结构中的数据元素之间存在一对一的关系。

树形结构是结构中的数据元素之间存在一对多的关系。

图形结构是结构中的数据元素之间存在多对多的关系。

逻辑结构。数据结构定义中的“关系”是通过抽象被操作数据对象的数学特性而得出的,它描述的是数据元素之间的逻辑关系,因此又称为数据的逻辑结构。

存储结构。数据结构在计算机中的表示(映像)称为数据的物理结构,即数据的存储结构。

顺序存储结构:采用一块地址连续的存储单元依次存储各数据元素。

链式存储结构:可以采用地址不连续的存储单元分别存储各数据元素,在链式存储结构中,数据元素以节点方式存储,节点由两部分组成,一部分是存储节点数据元素本身的值,另一部分存储后继结点元素的地址,成为指针域。

小结。逻辑结构有集合、线性、树形和图形4种基本结构。

物理结构有顺序和链式两种存储结构。

算法的效率度量分为时间度量和空间度量。

二、 线性表。

线性表是由 n 个具有相同数据类型的数据元素构成的有限序列。

线性表的存储结构:顺序存储结构和链式存储结构。

顺序表是指用一组地址连续(存储空间紧邻)的存储单元依次存储线性表的数据元素。

链式存储结构是将数据元素的存储空间映射为由数据域和指针域组成的节点。

顺序存储结构的优点是可以实现随机存取,存取速度快,存储空间利用率高,缺点是需要占用一片连续的存储空间,查如何删除操作时需要移动大量的数据元素,操作效率较低。

链式存储结构优点是不需要连续的存储空间,空间动态分配,在插入和删除元素时不需要移动元素,操作方便。缺点是不能实现随机存取,而且需要额外的空间存放指针,存储空间利用率较低。

线性存储结构比较适合线性表长度不经常发生变化,不经常执行插入和删除操作,而经常执行访问和查询操作的应用。

链式存储结构比较适合线性表长度不可预知,需要频繁进行插入和删除操作的应用。

三、 栈和队列。

栈和队列是两种特殊的线性表,他们是限定只能在表的一段或两端进行插入、删除元素的线性表,因此,统称为限定性数据结构。

栈又称堆栈,是限定仅在表的一段进行插入和删除操作的线性表,栈的特点是先进后出(first in last out,filo)

栈与递归。在计算机科学中将一个直接或间接调用自己的函数称作递归函数,按照最后调用最先返回的原则,系统运行期间所需要的数据空间被安排在一个栈中。

void r_write(int w)

int i;

if(w!=0)

r_write(w-1);

for(i=1;i<=w;i++)

if(flag==0)

快速排序。快速排序的基本思想是,以待排序列中某个记录为枢纽,分别从序列两端向中间逼近,通过该枢纽与其他记录的比较和交换,将待排序序列化分为两个子序列。其中一个子序列中记录的关键字均小于枢纽的关键字,另一个子序列中记录的关键字均大于该枢纽的关键字,枢纽是两个子序列的分割中间点,这个过程,成为一趟快速排序,然后分别对两个子序列重复上述分割过程,只到每个子序列中只有1个记录为止,至此,带排序序列有序。

选择排序。选择排序的基本思想是:不断从待排序序列中选取一个关键字最小(或最大)的记录,存放在合适的位置上,直到整个序列的记录都被选取完。

这样,根据选取记录的顺序,就得到按关键字有序的序列。

数据结构基础

内容简介。本书是最经典数据结构教材的最新版本,国内外大多数的同类教材都是以本书为蓝本编写而来的。本书用c作为描述语言,全面而生动地介绍了数据结构的有关知识,如数组 栈 队列 链表 树和图,以及构成所有软件基础的排序散列技术。此外,本书还介绍了各种高级或特殊数据结构,如优先级队列 高效二叉查找树 多路...

数据结构基础

文件输入输出。include include using namespace std int main file fin,fout fin fopen rscanf d x fscanf stdin,d x fout fopen w fprintf d x frpintf stdout,d x in...

数据结构基础

读万卷书,行万里路 刘彝 所属课程名称 数据结构基础。英文名称 fundamentals of data structure 所属课程编号 0901202 面向专业 计算机及电类专业。课程总学时 64 实验学时 32 课程学分 4.5 一。实验目的。通过上机实验,使学生深刻理解基础数据结构和算法的概...