文档介绍：数据结构与算法
主讲人:张雷
运城学院公共计算机教学部
2012年2月
一、算法
(1)算法的基本概念
算法是指解决问题方案的准确而完整的描述
(2)算法的基本特征:①有穷性;②确定性;③可行性;④0个或多个输入;⑤1个或多个输出。
(3)算法复杂度主要包括时间复杂度和空间复杂度。
所谓时间复杂度一般是用算法在执行过程中所需基本运算的执行次数来度量的。常见的时间复杂度有:线性级O(n),平方级O(n2),对数级O(log2 n)和指数级O(2n)等。
所谓空间复杂度是指执行算法所需要的存储空间的大小。
二、数据结构
(1)利用计算机进行数据处理是计算机应用的一个重要领域。在进行数据处理时,实际需要处理的数据元素一般较多,而这些大量的数据元素都需要存放在计算机中,因此,大量的数据元素在计算机中如何组织,以便提高数据处理的效率,并且节省计算机的存储空间,这是进行数据处理的关键问题。
(2)数据结构作为计算机的一门学科,主要研究和讨论以下三个方面的问题:
①数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构;
②在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;
③对各种数据结构进行的运算,包括插入、删除、查找、排序等。
数据的物理结构是指数据在计算机内的实际存储形式
三、线性表
(1)线性表的基本概念
线性表是由n(n>=0)个数据元素组成的一个有限序列,表中的每一个数据元素,除了第一个外,有且只有一个前件,除了最后一个外,有且仅有一个后件。即线性表或是一个空表,或可表示为:(a1,a2,……,ai,……,an)其中ai是性质相同的数据元素,也称为线性表中的一个结点。
线性表的长度,即表中的元素个数n,当n=0时称为空表。
(2)线性表的顺序存储结构
线性表的顺序存储结构的基本特点:
①线性表中所有元素所占的存储空间是连续的;
②线性表中每个元素在存储空间中是按逻辑顺序存放的。
线性表的随机存取地址计算公式为:
ADD(ai)=ADD(a1)+(i-1)*k
这里ADD(ai)是第i元素的地址,k是每个元素占用空间字节数。
(3)线性表的插入运算
在长度为n的线性表(a1,a2,…,ai,…,an)的第i 元素ai之前插入一个新元素x后得到的长度为n+1的线性表为(a1,a2,…,x,ai,…,an)。
实现方法:要在第i元素之前插入一个新元素x,首先要从最后一个(即第n 个)元素开始,直到第i 元素之间的n-i+1个元素依次向后移动一个位置,移动结束后,在第i 位置写入新元素x。插入结束后,表长度就增加了1。
(4)线性表的删除运算
在长度为n的线性表(a1,a2,…,ai,…,an)中删除第i 元素ai后,变为长度为n-1的线性表(a1,a2,…, ai-1, ai+1…,an)。
实现方法:要删除第i (1<=i<.n)元素,首先要从第i+1元素开始,直到最后一个(即第n个)元素之间的n-i个元素依次向前移动一个位置。删除结束后,表长度减1。
四、栈
(1)栈的概念
栈是限定只能在表的一端进行插入和删除的线性表。它按照“后进先出”(LIFO)的原则组织数据。表中允许插入和删除的一端叫做栈顶,表中的固定端叫做栈底。通常用指针top指示栈顶的位置,用指针buttom指向栈底。
(2)栈的基本运算
①入栈:先判断,若栈满不能入栈,发生“上溢”错误;不满时将新元素插入到栈顶位置后,修改栈顶指针top++。
②出栈:先判空,若栈空不能出栈,发生“下溢”错误;非空时修改栈顶指针top--,将栈顶元素赋给一个指定的变量。