数据结构教程第一章知识总结

第一章、绪论

1.1 什么是数据结构

1.1.1 数据结构的定义

数据(data)

：是描述客观事物的数和字符的集合。

数据元素(dataelement)

：数据的基本单位(例如,200902班中的每个学生记录都是一个数据元素)。一个数据元素可以由若干个数据项组成。

数据项(data item)

：是数据最小单位，也称为字段或域。例如，200902班中的每个数据元素(即学生记录)是由学号、姓名、性别和班号等数据项组成的。

数据对象(data object)

：是指性质相同的数据元素的集合,它是数据的一个子集。

数据结构(data strueture)

：是指所有数据元素以及数据元素之间的关系，可以看作是相互之间存在着某种特定关系的数据元素的集合。因此,我们可以把数据结构看成是带结构的数据元素的集合。包含三个方面：逻辑结构、存储结构和对数据的运算。

1.1.2逻辑结构

逻辑结构的表示

：图表表示，二元组表示。

逻辑结构的类型

：

集合。
线性结构：线性结构(linear structure)是指该结构中的数据元素之间存在一对一的关系。其特点是开始元素和终端元素都是唯一的，除了开始元素和终端元素以外,其余元素都有且仅有一个前驱元素，有且仅有一个后继元素。代表线性表。
树形结构：树形结构是指该结构中的数据元素之间存在一对多的关系。其特点是除了开始元素以外，每个元素有且仅有一个前驱元素,除了终端元素以外，每个元素有一个或多个后继元素。二叉树就是一种典型的树形结构。
图形结构：图形结构是指该结构中的数据元素之间存在多对多的关系。其特点是每个元素的前驱元素和后继元素的个数可以是任意的。树形结构和图形结构统称为非线性结构。

1.1.3存储结构

数据逻辑结构在计算存储器中的存储表示称为数据的存储结构(也称为

映像

)，也就是逻辑结构在计算机中的存储实现。包括

数据元素的表示和关系的表示

。关系的表示有两种表示方法:顺序映像和非顺序映像，对应两种不同的存储结构，

顺序存储结构和链式存储结构

。

4种常用的存储方法

:

顺序存储结构：将数据元素存放在地址连续的存储单元里，逻辑上相邻的元素其存储的物理位置也相邻。可实现对元素的随机存储，对元素的插入和删除操作要移动一系列元素，比如数组。
链式存储方法：数据放在任意的存储单元里，逻辑上相邻的元素存储的物理位置不一定相邻。便于元素的插入和删除，不用移动一系列元素；但是不能随机存储(按照下标)；存储空间利用率低，有一部分空间要来存放下一个节点的地址。
索引存储结构：索引存储结构(indexedstoragestructure)是指在存储数据元素信息的同时还建立附加的索引表。存储所有数据元素信息的表称为主数据表,其中每个数据元素有一个关键字和对应的存储地址。索引存储结构的优点是查找效率高。其缺点是需要建立索引表，从而增加了空间开销。
哈希(或散列)存储方法：哈希(或散列)存储结构(hashedstoragestructure)的基本思想是根据元素的关键字通过哈希(或散列)函数直接计算出一个值,并将这个值作为该元素的存储地址。

【例1】以下属于逻辑结构的时___。

A. 顺序表 B. 哈希表

C. 有序表

D. 单链表

【例2】以下不属于存储结构是___。

A. 栈

B. 线索树 C. 哈希表 D. 单链表

栈是一种逻辑结构，通常有顺序栈和链栈两种存储结构。

【例3】在决定选取何种类型的存储结构时，一般不多考虑___。

A. 各节点的值如何

B. 节点的个数多少

C. 对数据有哪些运算 D. 所用编程语言实现这种结构是否方便

【例4】数据采用链式存储结构时，要求___。

A.每个节点占用一片连续的存储区域

B.所有节点占用一片连续的存储区域

C.节点的最后一个

数据域

是指针类型

D.每个节点有多少个后继就设多少个指针域

【例5】数据的存储结构包括___的表示和___的表示。

答:①数据元素②数据元素之间关系。

【例6】任何数据结构都具备3个基本运算:插入、删除和查找。

错误。如队列和栈等数据结构并不具备查找基本运算。

1.1.4数据运算

数据运算就是指对数据实施的操作。有检索、插入、删除、更新和排序等。

1.1.5数据类型和抽象数据类型

数据类型：int、float、struct student。一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型：抽象数据类型(Abstract Data Type,ADT)指的是用户进行软件系统设计时从问题的数学模型中

抽象出来的逻辑数据结构和逻辑数据结构上的运算，而不考虑计算机的具体存储结构和运算的具体实现算法

。抽象数据类型中的数据对象和数据运算的声明与数据对象的表示和数据运算的实现相互分离。

1.2算法及其描述

1.2.1什么是算法

算法(algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列。算法有5个特性：

有穷性

：一个算法必须总是在执行有穷步之后结束，且每一步都可在有穷时间内完成。
确定性

：对于相同的输人只能得出相同的输出，不能有二义性。
可行性

：算法中的所有操作都必须足够基本,算法可以通过有限次基本操作来完成其功能。
有输人

：一个算法有零个或者多个输人。
有输出

：一个算法有一个或者多个输出。

算法和程序不同，程序可以不满足有穷性。

1.2.2算法设计的目标

正确性
可使用性
可读性
健壮性：要求算法具有很好的容错，即提供异常处理，能够对不合理的数据进行检查。
高效率与低存储量需求

1.3算法分析

1.3.1算法时间复杂度

算法时间复杂度是以算法中

基本操作

重复执行的次数作为算法的时间度量。一般不必要精确计算出算法的时间复杂度，只要大致计算出相应的数量级即可，如O(1)、O(
$log_{2}n$
)、O(n)或O(
$n^{2}$
)等。

算法的时间复杂度T(n)=O(f(n))，f(n)是正整数n(

n表示问题的规模

)的一个函数。

当算法的时间复杂度T(n)与n无关时，T(n)=O(1)；当算法的时间复杂度T(n)与n为线性关系时，T(n)=O(n)；当算法的时间复杂度T(n)与n为平方关系时，T(n)=O(
$n^{2}$
)等。常用的时间复杂度有如下关系：

$O(1)<O\left(\log _{2} n\right)<O(n)<O\left(n \log _{2} n\right<O\left(n^{2}\right)<O\left(n^{3}\right)<O\left(2^{n}\right)<O(n !)$

【例7】某算法的时间复杂度为O(
$n^{2}$
)，表明该算法的___。

A.问题规模是
$n^{2}$
B.执行时间等于
$n^{2}$

C.执行时间与
$n^{2}$
成正比

D.问题规模与
$n^{2}$
成正比

【例8】以下说法中错误的是___。

(1)原地工作算法的含义是指不需要任何额外的辅助空间

(2)在相同的问题规模n下，时间复杂度为O(nlog2n)的算法在执行时间上总是优于时间复杂度为 O(n2)的算法

(3)时间复杂度通常是指最坏情况下，估计算法执行时间的一个上限

(4)一个算法的时间复杂度与实现算法的语言无关

A. (1)

B. (1)、(2)

C. (1)、(4) D. (3)

答:原地工作算法(亦称就地工作算法)的含义是指算法所需要的临时空间不依赖问题的规模n,即算法的空间复杂度为0(1)，并非不需要任何额处的临时空间。执行时间与时间复杂度成正比，但是不等于时间复杂度。

1.3.2算法空间复杂度

算法空间复杂度(space complexity)是对一个算法在运行过程中临时占用的存储空间大小的量度。一般也作为问题规模n的函数,以数量级形式给出,记作S(n)=O(f(n)),f(n)是正整数n(

n表示问题的规模

)的一个函数。

【例9】分析以下算法的时间复杂度。

void fun (int n)
{
    int s=0，i,j, k;
    for (i=0;i<=n; i++)
        for(j=0;j<=i;j++)
            for (k=0;k<j;k++)
                s++;
}

答:该算法的基本运算是语句s++，其频度:

$\begin{aligned} T(n) &=\sum_{i=0}^{n} \sum_{j=0}^{i} \sum_{k=0}^{j-1} 1=\sum_{i=0}^{n} \sum_{j=0}^{i}(j-1-0+1)=\sum_{i=0}^{n} \sum_{j=0}^{i} j \\ &=\sum_{i=0}^{n} \frac{i(i+1)}{2}=\frac{1}{2}\left(\sum_{i=0}^{n} i^{2}+\sum_{i=0}^{n} i\right)=\frac{2 n^{3}+6 n^{2}+4 n}{12}=O\left(n^{3}\right) \end{aligned}$

则该程序段的时间复杂度为O(n)。

【例10】求以下算法时间复杂度。

int fact (int a[], int n, int x)
{
    int i=0;
    while(i<n)
    {
        if(a[i]==x)
            return i;
        i++;
    }
    return -1;
}

若查找每个元素的概率相等，则在成功找到x时，T(n)=(1+2+… +n)/n=(n+1)/2=O(n)。

若在数组a[0..n- l]中找不到x，while执行n次，此时T(n)=n=O(n)。因此本算法的平均时间复

杂度为O(n)。

【例11】求以下递归算法时间复杂度。

void mergesort(int i,int j)
{
    int m;
    if(i!=j)
    {
        m = (i+j)/2;
        mergesort(i,m);
        mergesort(m+1,j);
        merge(i,j,m)
    }
}

解:设调用mergesort(0,n-1)的执行时间为T(n), 由其执行过程得到以下求执行时间的递归关系:

$T(n)=\left\{\begin{array}{ll} O(1) & n=1 \\ 2 T\left(\frac{n}{2}\right)+O(n) & n>1 \end{array}\right.$

其中，O(n)为merge(所需的时间，设为cn (c 为正常量)。因此:

$\begin{array}{l} \mathrm{T}(\mathrm{n})=2 \mathrm{~T}\left(\frac{\mathrm{n}}{2}\right)+\mathrm{cn}=2\left(2 \mathrm{~T}\left(\frac{\mathrm{n}}{4}\right)+\frac{\mathrm{cn}}{2}\right)+\mathrm{cn}=2^{2} \mathrm{~T}\left(\frac{\mathrm{n}}{4}\right)+2 \mathrm{cn}\\ =2^{3} \mathrm{~T}\left(\frac{\mathrm{n}}{2^{3}}\right)+3 \mathrm{cn}\\ =2^{\mathrm{k}} \mathrm{T}\left(\frac{\mathrm{n}}{2^{\mathrm{k}}}\right)+\mathrm{kcn}\\ =\mathrm{n}^{*} \mathrm{O}(1)+\mathrm{cn} \log _{2} \mathrm{n}=\mathrm{n}+\mathrm{cn} \log _{2} \mathrm{n} \quad \\ =\mathrm{O}\left(\mathrm{n} \log _{2} \mathrm{n}\right) \end{array}$

【例11】设计一个算法求解hanoi问题:有3根柱子a、b、C,有n个半径不同的中间有孔的圆盘，这n个圆盘在柱子a上，从上往下半径依次增大。要求把所有圆盘移至目标盘c上，可将柱子b作为辅助柱，移动圆盘时必须服从以下规则:

每次只可搬动一个圆盘。
任何柱子上都不允许大圆盘在小圆盘的上面。

并分析算法的时间复杂度。

解:求解hanoi问题的思路为:当n=1 时，搬动一次即可;当n>1 时，分3步进行。

将n-1个圆盘(除最大的圆盘外)从柱子a移到柱子b.
将最大的圆盘从柱子a移动到柱子c。
将柱子b上的n-1个圆盘从柱子b移动到柱子c。

由此得到以下求解算法:

void hanoi (int n,char a, char b, char c)
{ 
    if (n==1)
        printf ("move %d disk from %C to %c\n",n,a,c);
    else
    {
        hanoi(n-1,a,c,b);
        printf ("move %d disk from %C to %c\n",n,a,c);
        hanoi(n-1,b,a,c);
    }
}

由上述算法得到时间复杂度的递归关系如下:

$T(n)=\left\{\begin{array}{ll} 1 & n=1 \\ 2 T(n-1)+1 & n=t \end{array}\right.$

$\begin{array}{l} T(n)=2 T(n-1)+1 \\ =2(2 T(n-2)+1)+1=2^{2} T(n-2)+2^{2}+1 \\ =2^{2}(2 T(n-3)+1)+2^{2}+1=2^{3} T(n-3)+2^{3}+1 \\ =\cdots \\ =2^{n-1} T(1)+2^{n-1}+1=2^{n}+1=O\left(2^{n}\right) \end{array}$

原文链接：https://blog.csdn.net/qq_42148307/article/details/125024638