数据结构.docx

数据结构.docx

《数据结构.docx》由会员分享，可在线阅读，更多相关《数据结构.docx（37页珍藏版）》请在冰点文库上搜索。

数据结构

malloc函数为动态分配空间；

原型为:

void*malloc（intsize）;

使用方法一般为：

假设你要定义一个名为a的Node类型的指针变量，使用以下语句：

Node*a=（Node*）malloc（sizeof（Node））；

其中（Node*）为强制转换，把返回类型void*转换为Node*，sizeof（Node）为获取Node类型占据空间的大小，如在我机子上int类型占4字节，sizeof（int）就返回4；

使用malloc需要包含＃include

学习数据结构有什么用？

计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。

同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。

程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。

而好的算法在很大程度上取决于描述实际问题的数据结构。

程序=数据结构+算法（尼克劳斯.沃尔斯）

目标：

“数据结构”课程的教学目标是要求学生学会分析数据对象特征，掌握数据组织方法和计算机的表示方法，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及相应算法，初步掌握算法时间空间分析的技巧，培养良好的程序设计技能。

意义

1.算法和数据结构是计算机科学的两大支柱

2.数据结构是程序设计的基础

程序=数据结构+算法

--图灵奖获得者：

NicklausWirth（瑞士）

数据结构是设计OS、DBMS、编译等系统程序和各种应用程序的重要基础

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。

术语：

数据（Data）:

是对信息的一种符号表示。

在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素（DataElement）:

是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

一个数据元素可由若干个数据项组成。

数据项是数据的不可分割的最小单位。

数据对象（DataObject）：

是性质相同的数据元素的集合。

是数据的一个子集。

例如，整数数据对象的集合可表示为N＝{0，±1，±2…….}，字母字符数据对象的集合可表示为C={‘A’,’B’,…’Z’}。

&数据结构定义1----

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

形式化定义：

数据结构是一个二元组

Data_Structure=（D,R）

其中，D是数据元素的有限集合，R是D上关系的集合

&数据结构定义2----

按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。

具体来说，数据结构包含三个方面的内容，即数据的逻辑结构，数据的存贮结构和对数据所施加的运算（操作）。

这三个方面的关系为：

（1）数据的逻辑结构独立于计算机，是数据本身所固有的。

（2）存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。

（3）运算是指所施加的一组操作总称。

运算的定义直接依赖于逻辑结构，但运算的实现必须依赖于存贮结构。

数据的存储结构（物理结构）：

数据的逻辑结构在计算机中的存储形式

顺序存储：

把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系一致。

链式存储：

是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的

抽象数据类型概念（ADT）

数据类型：

在一种程序设计语言中，变量所具有的数据种类。

数据类型：

是一个值的集合和定义在该值上的一组操作的总称。

抽象数据类型：

由用户定义，是一个数学模型以及定义在该模型上的一组操作。

体现了程序设计中问题的分解、抽象和信息隐藏的特性。

Ø其定义仅取决于它的一组逻辑特性。

Ø它由基本的数据类型构成，并包括一组相关的服务（或称操作）

Ø它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。

抽象数据类型可以用以下的三元组来表示：

ADT=（D，S，P）

数据对象D上的关系集D上的操作集

ADT常用定义格式

ADT抽象数据类型名{

数据对象：

<数据对象的定义>

数据关系：

<数据关系的定义>

基本操作：

<基本操作的定义>

}ADT抽象数据类型名

注意：

ADT的定义一般为多形数据类型。

即其值的成分是不确定的数据类型。

抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。

它有些类似C语言中的结构体（struct）类型，但增加了相关的服务。

算法的概念和描述：

是对特定问题求解步骤的一种描述，算法是指令的有限序列，其中每一条指令表示一个或多个操作。

算法描述

算法具有以下五个特性：

（1）有穷性

（2）确定性

（3）可行性

4）输入

5）输出

算法设计的要求

评价一个好的算法有以下几个标准:

（1）正确性（Correctness）算法应满足具体问题的需求。

（2）可读性（Readability）算法应该好读。

以有利于阅读者对程序的理解，便于调试和修改。

（3）健壮性（Robustness）算法应具有容错处理。

当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。

（4）效率与存储量需求效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。

一般，这两者与问题的规模有关。

注意：

算法和程序的关系

算法的含义与程序十分相似，但二者是有区别的。

一个程序不一定满足有穷性（死循环），另外，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。

一个算法若用计算机语言来书写，则它就可以是一个程序。

设计实现算法过程的步骤

·找出与求解有关的数据元素之间的关系（建立结构关系）。

·确定在某一数据对象上所施加的运算。

·考虑数据元素的存储表示。

·选择描述算法的语言。

·设计实现求解的算法，并用程序语言加以描述。

算法的描述和实现

描述---可采用自然语言、数学语言或约定的符号语言。

实现---必须借助程序设计语言提供的数据类型及其运算。

算法分析

算法效率的衡量方法和准则

衡量算法效率的方法:

事后统计法、

和算法执行时间相关的因素：

1．算法选用的策略

2．问题的规模

3．编写程序的语言

4．编译程序产生的机器代码的质量

5．计算机执行指令的速度

线性表（LinearList）是由n（n≥0）个类型相同的数据元素组成的有限序列，记作（a1,a2,…,ai-1,ai,ai+1,…,an）。

线性表的特点可概括如下：

同一性：

线性表由同类数据元素组成，每一个ai必须属于同一数据对象。

有穷性：

线性表由有限个数据元素组成，表长度就是表中数据元素的个数。

有序性：

线性表中表中相邻数据元素之间存在着序偶关系。

由此可看出，线性表是一种最简单的数据结构，因为数据元素之间是由一前驱一后继的直观有序的关系确定；线性表又是一种最常见的数据结构，因为矩阵、数组、字符串、堆栈、队列等都符合线性条件。

线性表的抽象数据类型定义

ADTList{

数据元素：

D={ai|ai∈ElemSet,i=1,2,…，n,n≥0，ElemSet为某一数据对象}

关系：

Ｓ＝｛|ai,ai+1∈D，i=1,2,…,n-1｝

基本操作：

（1）InitList（&L）

初始条件：

L为未初始化线性表。

操作结果：

将L初始化为空表。

（2）DestroyList（&L）

初始条件：

线性表L已存在。

操作结果：

将L销毁。

（3）ClearList（&L）

初始条件：

线性表L已存在。

操作结果：

将表L置为空表。

（4）ListEmpty（L）

初始条件：

线性表L已存在。

操作结果：

如果L为空表则返回真，否则返回假。

（5）ListLength（L）

初始条件：

线性表L已存在。

操作结果：

如果L为空表则返回0，否则返回表中的元素个数。

（6）LocateElem（L,e,compare（））

初始条件：

表L已存在，compare（）是数据元素判定函数。

操作结果：

返回L中第1个与e满足关系compare（）的数据元素的位序，如果不存在，返回值为0。

（7）GetElem（L,i,&e）

初始条件：

表L存在，且1≤i≤ListLength（L）。

操作结果：

用e返回线性表L中第i个元素的值。

（8）ListInsert（&L,i,e）

初始条件：

表L已存在，1≤i≤ListLength（L）+1。

操作结果：

在L中第i个位置之前插入新的数据元素e，L的长度加1。

（9）ListDelete（&L,i,&e）

初始条件：

表L已存在且非空，1≤i≤ListLength（L）。

操作结果：

删除L的第i个数据元素，并用e返回其值，L的长度减1。

}ADTList

线性表的顺序表示和实现

顺序存储定义：

把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构

简言之，逻辑上相邻，物理上也相邻

顺序存储方法：

用一组地址连续的存储单元依次存储线性表的元素，可通过数组来实现。

线性表顺序存储特点：

1.逻辑上相邻的数据元素，其物理上也相邻；

2.若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标）。

计算方法是：

设首元素a1的存放地址为LOC（a1）（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：

LOC（ai）=LOC（a1）+L*（i-1）

它是一种随机存取的数据结构。

顺序存储结构可以借助于高级程序设计语言中的一维数组来表示，一维数组的下标与元素在线性表中的序号相对应。

线性表的顺序存储结构可用C语言定义如下：

#defineLIST_INIT_SIZE100//线性存储空间的初始分配量

#defineLISTINCREMENT10//线性存储空间的分配增量

typedefstruct

{

ElemType*elem;//存储空间基地址

intlength；//当前长度（即当前存放数据元素的个数）

intlistsize;//当前分配的存储容量（即最多可存放的数据元素的个数）

}SqList；

初始化操作

StatusIniList_Sq（SqList&L）{

L.elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType））;

if（!

L.elem）exit（OVERFLOW）;

L.length=0;

L.listsize=LIST_INIT_SIZE;

returnOK;

}

插入操作

在这种结构中容易实现随机存取第i个数据元素，C语言中数组的下标从0开始，所以ai应在L.elem[i-1]中存取。

线性表的插入运算是指在表的第i（1≤i≤n+1）个位置，插入一个新元素e，使长度为n的线性表（e1，…，ei-1，ei，…，en）变成长度为n+1的线性表（e1，…,ei-1，e，ei，…，en）。

当i=n+1时，是指在线性表的末尾插入结点，所以无需移动结点，直接将e插入表的末尾即可。

实现步骤：

•将第n至第i位的元素向后移动一个位置；

•将要插入的元素写到第i个位置；

•表长加1。

StatusListInsert_sq（SqList&L,inti,ElemTypee）

{

if（i<1||i>L.length+1）returnERROR;

if（L.length>=L.listsize）{//当前存储空间已满，增加分配

newbase=（ElemType*）realloc（L.elem,

（L.listsize+LISTINCREMENT）*sizeof（ElemType））;

if（!

newbase）exit（OVERFLOW）;//存储分配失败

L.elem=newbase;//重新分配的存储空间的首地址

L.listsize+=LISTINCREMENT;//增加的存储容量

}

q=&（L.elem[i-1]）;//q指向要元素插入的位置

for（p=&（L.elem[L.length-1]））;p>=q;--p）*（p+1）=*p;//插入位置及之后的原始后移

*q=e;//插入元素e

++L.length;//表长增1

returnOK；

}

插入元素时，时间主要耗费在移动元素上。

移动个数取决于插入位置。

删除操作

线性表的删除运算是指将表的第i（1≤i≤n）个元素删去，使长度为n的线性表（e1，…,ei-1，ei，ei+1，…，en）变成长度为n-1的线性表（e1，…,ei-1，ei+1，…，en）。

实现步骤：

•将第i+1至第n位的元素向前移动一个位置；

•表长减1。

StatusListDelete_Sq（SqList&L,inti,ElemType&e）{

//在顺序表L中删除第i个元素，并用e返回

if（（i<1）||（i>L.length））returnERROR;

p=&（L.elem[i-1]）;//p指向要删除元素

e=*p;

q=L.elem+L.length-1;//q指向表尾元素

for（++p;p<=q;++p）*（p-1）=*p;//被删除元素之后的元素依次前移

--L.length;//表长减1

returnOK;

}

在顺序表中查找元素的算法：

//在顺序表L中查找第1个值与e满足compare（）的元素的位序

intLocatElem_Sq（SqListL,ElemTypee,Status（*compare）（ElemType,ElemType））{

i=1;//i的初值为第1个元素的位序

p=L.elem;//p的初值为第1个元素的存储位置

while（i<=L.length&&!

（*compare）（*p++,e））

++i;

if（i<=L.length）

returni;

elsereturn0;

}

有两个顺序表LA和LB，其元素均为非递减有序排列，编写一个算法，将它们合并成一个顺序表LC，要求LC也是非递减有序排列。

例如LA=（2,2,3），LB=（1,3,3,4），则LC=（1,2,2,3,3,3,4）。

算法思想：

设表LC是一个空表，为使LC也是非递减有序排列，可设两个指针i、j分别指向表LA和LB中的元素，若LA.elem[i]>LB.elem[j]，则当前先将LB.elem[j]插入到表LC中;若LA.elem[i]≤LB.elem[j]，则当前先将LA.elem[i]插入到表LC中，如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中。

voidMergeList_Sq（SqListLa,SqListLb,SqList&Lc）{

pa=La.elem;pb=Lb.elem;

Lc.listsize=Lc.length=La.length+Lb.length;

pc=Lc.elem=（ElemType*）malloc（Lc.listsize*sizeof（ElemTpe））;

if（!

Lc.elem）exit（OVERFLOW）;

pa_last=La.elem+La.length-1;

pb_last=Lb.elem+Lb.length-1;

while（pa<=pa_last&&pb<=pb_last）{

if（*pa<=*pb）*pc++=*pa++;

else*pc++=*pb++;

}

while（pa<=pa_last）*pc++=*pa++;

while（pb<=pb_last）*pc++=*pb++;

}

由上面的讨论可知，线性表顺序表示的优点是：

（1）无需为表示结点间的逻辑关系而增加额外的存储空间（因为逻辑上相邻的元素其存储的物理位置也是相邻的）；

（2）可方便地随机存取表中的任一元素。

其缺点是：

（1）插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量的结点，其效率较低;

（2）预分配空间（浪费）；

（3）表的扩充不方便。

线性表的链式表示和实现

单链表：

用一组地址任意的存储单元存放线性表中的数据元素

以元素（数据元素的映象）+指针（指示后继元素存储位置）=结点（表示数据元素或数据元素的映象）

以“结点的序列”表示线性表称作链表

以线性表中第一个数据元素的存储地址作为线性表的地址，称作线性表的头指针

有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针

线性表的操作

GetElem（L,i,&e）

在单链表中插入操作的实现：

单链表是一种顺序存取的结构，为找第i个数据元素，必须先找到第i-1个数据元素。

线性表的操作ListInsert（&L,i,e）

StatusGetElem_L（LinkListL,inti,ElemType&e）{

//L是带头结点的链表的头指针，以e返回第i个元素

p=L->next;j=1;//p指向第一个结点，j为计数器

while（p&&j

{p=p->next;++j;}

//顺指针向后查找，直到p指向第i个元素或p为空

if（!

p||j>i）

returnERROR;//第i个元素不存在

e=p->data;//取得第i个元素

returnOK;

}//GetElem_L

线性表的操作ListInsert（&L,i,e）

在单链表中的实现：

有序对改变为和

可见，在链表中插入结点只需要修改指针。

但同时，若要在第i个结点之前插入元素，修改的是第i-1个结点的指针。

因此，在单链表中第i个结点之前进行插入的基本操作为:

找到线性表中第i-1个结点，然后修改其指向后继的指针。

StatusListInsert_L（LinkList&L,inti,ElemTypee）{

//L为带头结点的单链表的头指针，本算法

//在链表中第i个结点之前插入新的元素e

p=L;j=0;

while（p&&j

{p=p->next;++j;}//寻找第i-1个结点

if（!

p||j>i-1）

returnERROR;//i大于表长+1或者小于1

}//LinstInsert_L

s=（LinkList）malloc（sizeof（LNode））;//生成新结点

if（s==NULL）returnERROR;

s->data=e;

s->next=p->next;p->next=s;//插入

returnOK;

在单链表中的实现：

有序对和改变为

在单链表中删除第i个结点的基本操作为:

找到线性表中第i-1个结点，修改其指向后继的指针。

StatusListDelete_L（LinkList&L,inti,ElemType&e）{

//删除以L为头指针（带头结点）的单链表中第i个结点

p=L;j=0;

while（p->next&&jnext;++j;}

//寻找第i个结点，并令p指向其前趋

if（!

（p->next）||j>i-1）

returnERROR;//删除位置不合理

q=p->next;p->next=q->next;//删除并释放结点

e=q->data;free（q）;

returnOK;}//ListDelete_L

链表是一个动态的结构，它不需要给予分配空间，因此生成链表的过程是一个结点“逐个插入”的过程。

链表的运算效率分析

时间效率分析

1.查找因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为O（n）

2.插入和删除因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为O

（1）。

但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为O（n）。

静态链表（线性链表可以借助一维数组来描述）

静态链表上操作的实现

intLocateElem_SL（SlinklistS,ElemTypee）{

//设头结点为S[0],在静态链表S上找第一个值为e的结

//点，找着返回它在S中的下标，否则返回0。

i=s[0].cur;//j指向线性表的第一个元素；

while（i&&S[i].data!

=e）j=s[i].cur;//顺链查找

returni;

}

在进行插入、删除运算时，用户应能模拟动态链表中动态申请存储malloc和释放结点free的操作。

为了解决这个问题，辨明数组中哪些分量未被使用，解决的办法是，将所有未使用的以及被删除的结点用游标链成一个备用链。

每当进行插入时便可从备用链表上取得一个结点作为待插入的新结点；反之，在删除时将从链表中删除下来的结点链接到备用链表上

下面从计算（A-B）（B-A）例子出发，讨论静态链表的算法。

为使算法清晰起见，我们先给出3个基本操作：

（1）将整个数组空间初始化成一个链表;//Initapace_SL

（2）从备用链空间取得一个结点；//Malloc_SL

（3）将空闲结点链结到备用链表上;//Free

#include

#include

#defineMAXSIZE20

typedefcharElemType;

typedefintStatus;

//定义静态链表

typedefstruct{

ElemTypedata;

intcur;

}

component,SLinkList[MAXSIZE];

//将一维数组space中各分量链成一个备用链表