数据结构第二章.docx

数据结构第二章.docx

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

数据结构第二章

第二章线性表（LinearList）

|逻辑结构及其基本操作

|线性表的顺序存储结构

|线性表的链式存储结构

|静态链表

|应用实例

逻辑结构及其基本操作

|定义：

由n个相同类型数据元素a0a1…ai…an-1构成的有限序列。

z说明：

ai是抽去现实意义的抽象表示符号。

typedefintDataType;

typedefcharDataType;

typedefstructstudentDataType;

|基本操作

初始化：

Initiate（L）

求长度：

ListLength（L）

前插：

ListInsert（L,i,x）

删除：

ListDelete（L,i,x）

取元素：

ListGet（L,i,x）

注：

L为线性表

|顺序存储结构：

用一组地址连续的存储单元依次存储线性表的各个元素。

线性表的定义：

#defineMaxSize1024//假定线性表的最大长度为1024

typedefintDataType;/*定义数据类型*/

typedefstruct

{

DataTypeList[MaxSize];

intsize;

}SeqList;

注意：

这样定义不能对size进行初始化，因此一定要在使用前进行初始化赋值。

|线性表元素的插入

|线性表元素的删除

小结：

很显然，顺序表的插入和删除一个元素时，其时间主要花费在移动数据元素上。

算法的代价分析：

插入删除

平均移动结点的次数：

同理可得：

E=E=

假设结点插入的概率相同，即　

Pi=

把Pi代入E的计算公式中，则有：

E=

所以，在顺序表上插入和删除一个元素的时间复杂度是：

Ｏ（n）。

对于取元素和定位操作可以直接实现。

|例：

利用线性表的基本运算实现清除L中多余的重复节点。

|顺序表的优点：

简单、常用。

无须为表示节点间的逻辑关系而增加额外的存储空间

可以方便的随机存取表中的任一节点

|顺序表的缺点

插入和删除运算时，需移动大量数据，运行速度受到影响。

需预先确定数据元素最大个数。

|线性表的链式存储

|链表（LinkedList）：

一种物理存储上非连续、非顺序的线性存储结构，数据元素间的逻辑顺序是通过链表中的指针链接次序实现的。

|节点构成：

数据域＋指针域

|单链表结点的定义

typedefstructNode

{DataTypedata;

structNode*next;

}SLNode;

|单链表的结点结构的定义

（１）一般形式的单链表存储结构的结点定义方法

typedefstructNode

{

DataTypeData;

structNode*Next

}SLNode;

|

typedefintdatatype;

typedefstruct{

charname[10];

intage;

}DataType;

节点存储空间的申请

p＝（SLNode*）malloc（sizeof（SLNode））;

节点存储空间的释放

free（p）;

|单链表中的基本操作——初始化

intListInitiate（SLNode**head）

{

if（（*head=（SLNode*）malloc（sizeof（SLNode）））

==NULL）

return0;

用头指针建立了一个空表。

（*head）->Next=NULL;

return1;

}

|单链表中的基本操作——前插

在单链表h中的第i个元素之前插入一个数据元素x。

intListInsert（SLNode*head,inti,DataTypex）

{

SLNode*p,*q;

intj;

p=h;

j=0;

while（p!

=NULL&&j

{

p=p->Next;

j++;

}

if（j!

=i-1）

{

printf（“\n插入位置不合理！

”）;

return0;

}

/*申请一空结点*/

if（（q=（SLNode*）malloc（sizeof（SLNode）））==NULL）return0;

q->Data=x;/*给数据赋值*/

q->Next=p->Next;

p->Next=s;

return1;

}

|单链表中的基本操作——删除

在单链表h中删除第i个结点。

|单链表中的基本操作——取元素

在单链表h中寻找第i个结点，并返回该结点的数据元素。

|单链表中的操作举例

假设已有单链表la，复制一个具有同样结构的单链表lb。

|循环单链表

循环单链表的定义：

循环单链表是单链表的另一种形式,其特点是链表中最后一个结点的指针不再是空的,而是指向头结点或第一个结点,整个链表形成一个环。

从表中任一个结点出发，都可找到表中其它结点。

|双向链表

双向链表的定义：

具有两个方向的指针域的链表叫双向链表，这两个指针域分别指向当前结点的前驱和后继。

单链表只能从表头开始沿一个方向查找；而双向链表可以从任一个结点出发，向前或向后查找。

|双向链表结点的结构定义

typedefstructNode

{

DataTypeData；

structNode*Prior，*Next；

}DLNode；

双向链表前插操作的C语言算法P-49

|双链表中的基本操作——删除

双向链表删除操作的C语言算法p-50

|链式存储结构的特点

链式存储结构的优点

（1）结点空间的动态申请和动态释放;

（2）数据元素的逻辑次序用结点的指针域指示，插入、删除等操作中不需要大量移动数据。

链式存储结构的缺点

（1）每个结点中的指针域需额外占用存储空间；

（2）链式存储结构是一种非随机存储结构。

|应用实例

|以单链表存储结构实现线性表的就地逆转

|一元多项式的相加（合并同类项）