软件开发技术基础 第4版 课件 1.基本概念及线性数据结构

数据结构

——基本概念及线性数据结构基本概念1．数据（data）

数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合。

2．数据元素（dataelement）

数据元素是组成数据的基本单位。数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项（字段），故不是组成数据的最小单位西安交通大学计算机教学实验中心赵英良2基本概念3．数据结构

是指相互之间存在一种或多种特定关系的数据元素所组成的集合。数据结构包含三个方面的内容，即数据的逻辑结构数据的存贮结构对数据所施加的运算。西安交通大学计算机教学实验中心赵英良3基本概念3．数据的逻辑结构西安交通大学计算机教学实验中心赵英良4线性结构——通迅录、成绩单、花名册树形结构——电子字典、家谱、目录图状结构——交通线路、通信网络基本概念3．数据的存储结构西安交通大学计算机教学实验中心赵英良5(1)顺序存贮所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。(2)链式存贮所有元素存放在可以不连续的存贮单元中，元素之间的关系通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。(3)索引存贮（略） (4)散列存贮（略）基本概念3．算法分析西安交通大学计算机教学实验中心赵英良61）时间复杂度一个算法中的时间复杂度一般用语句执行次数的数量级来衡量。数据结构中数据元素个数n称为问题的规模，当n不断变化时，语句的执行次数也会变化2）空间复杂度

与时间复杂度类似，空间复杂度是指算法在计算机内执行时所占用的内存开销规模。线性数据结构

线性表是由有限个同类型的数据元素组成的有序序列，一般记作（a1,a2,…,an）。除了a1和an之外，任意元素ai都有一个直接前趋ai-1和一个直接后继ai+1。a1无前趋，an无后继。线性表的存储结构主要有顺序存储结构和链式存储结构两种。西安交通大学计算机教学实验中心赵英良7线性数据结构：顺序表采用顺序存储结构的线性表称为顺序表，它的数据元素按照逻辑顺序依次存放在一组连续的存储单元中。逻辑上相邻的数据元素，其存储位置也彼此相邻。假定元素a1的物理地址是Loc(a1)，每个元素占d个存储单元，则第i个元素的存储位置为：Loc(ai)=Loc(a1)+(i-1)*d

西安交通大学计算机教学实验中心赵英良8顺序表主要算法判定线性表是否为空求线性表的长度在表中第i个位置插入新元素x

在表中删除第i个元素在表中查找某个元素西安交通大学计算机教学实验中心赵英良9线性数据结构：栈栈是限制在表的一端进行插入和删除操作的线性表。允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。西安交通大学计算机教学实验中心赵英良10a1a3a2进栈出栈top线性数据结构：栈的主要操作创建空栈。进栈(push)操作:在栈顶插入元素。出栈(pop)操作:在栈顶删除元素。读栈顶元素:只是读出栈顶元素，并不改变栈内元素。

西安交通大学计算机教学实验中心赵英良11线性数据结构：循环队列队列是只能在表的一端进行插入、在另一端进行删除操作的线性表。允许删除元素的一端称为队头，允许插入元素的一端称为队尾。解决队列假溢出的办法是将存放队列元素的数组首尾相接，形成循环队列。循环队列的基本操作方式为：入队列时先执行rear=(rear+1)%M，再将新元素在rear指示位置加入；出队列时先执行front=(front+1)%M，再将下标为front的元素取出。

西安交通大学计算机教学实验中心赵英良12线性数据结构：循环队列西安交通大学计算机教学实验中心赵英良13将队空和对满的条件加以区分:

队空条件:

front=rear

队满条件:(rear+1)%M=front30124567frontrearABCD30124567frontrear30124567frontrearABCDFGE

(a)循环队列空(b)非空循环队列(c)循环队列满线性数据结构：单链表西安交通大学计算机教学实验中心赵英良14单链表用一组地址任意的存储单元存放线性表中的数据元素。由于逻辑上相邻的元素其物理位置不一定相邻，为了建立元素间的逻辑关系，需要在线性表的每个元素中附加其后继元素的地址信息。这种地址信息称为指针。附加了其他元素指针的数据元素称为结点。带头结点单链表的逻辑结构西安交通大学计算机教学实验中心赵英良15为了能顺次访问每个结点，需要保存单链表第一个结点的存储地址。这个地址称为线性表的头指针，本节用head表示。为了操作上的方便，可以在单链表的头部增加一个特殊的头结点。头结点的类型与其他结点一样，只是头结点的数据域为空。head

a1a2an∧带头结点的单链表带头结点单链表的逻辑结构西安交通大学计算机教学实验中心赵英良16head38数据域指针域38229486

a2

86…

…

94…

…

a3

NULL

a1

22

存储地址单链表存储结构示意图单链表中指针移动西安交通大学计算机教学实验中心赵英良17图2单链表指针后移一步ai2167ai+17650ai-192579257p=p.next2167pp

图1带头结点的空链表head∧∧单链表插入结点西安交通大学计算机教学实验中心赵英良18(a)第1步,生成结点s(b)第2步，s结点指向结点ai

(c)第3步，结点ai-1指向s结点图3

在单链表中插入结点x

pai-1

xai

sp.next=s③ai-1

ai

px

s②s.next=p.nextai-1

ai

px

s①单链表删除结点西安交通大学计算机教学实验中心赵英良19删除第i个结点，需进行如下操作：

①若第i个结点存在则找到第i和第i-1个结点的指针p和q②通过语句q.n