理学第四章线性表

Chapter4线性表、堆栈和队列

4.1线性表的定义和基本操作

4.2线性表的存储结构

4.3堆栈和队列4.1线性表的定义和操作4.1.1线性表的定义

[例1]英文字母表（A,B,C,……,Z)

整数序列（1,78,9,12,10)[例2]某班学生健康情况登记表。学号姓名性别年龄健康情况

01张军男18一般02陈红女17良好

03陈军男19良好

…

…

…

…

…线性表定义：一个线性表是由零个或多个具有相同类型的结点组成的有序集合。用（a0，a1，…，an-1）来表示一个线性表。当n>0时，a0称为表的始结点，an-1称为表的终结点，当n=0时，线性表中有零个结点，称为空表。

线性表的逻辑结构：线性结构线性表记为(a0,a1,…,an-1)n≠0()n=0线性表的操作（1）随机存取：存取下标为k的结点（2）插入：在下标为k的结点前（或后）

插入一个新结点x（3）删除：删除下标为k的结点。（4）查找：寻觅具有特定域值的结点。（5）归并、分拆、复制、计数、排序。Chapter4

线性表、堆栈和队列

4.1线性表的定义和基本操作

4.2线性表的存储结构

4.2.1顺序存储结构

4.2.2链接存储结构－－单链表

4.2.3循环链表

4.2.4双向循环链表

4.3堆栈和队列

4.2线性表的存储结构线性表存储结构顺序存储非顺序存储——链表4.2.1顺序存储结构

●顺序存储：用一组连续的存储空间依次存储线性表的元素。

●特点：其逻辑顺序与物理顺序相同。 实现顺序存储的最有效方法是使用一维数组。[例]：线性表（a0，a1

，a2,a3)。可以使用一个数组a[n]来存放此线性表。

图4.1是包含4个结点的线性表A[4]在内存中的表示，其中每个结点占2个连续的字节，第一个结点A[0]的首地址为302

图4.1线性表的顺序存储线性表A[2]308306304302A[0]A[1]A[3]

Loc(a[k])=Loc(a[0])+k*ca0a1an-1akb+cb+k*cbb+(n-1)*c……01n-1k空闲区

特点：其逻辑顺序与物理顺序相同。顺序存储，随机存取

线性表上实现的基本运算

1、插入

[例]在线性表（12,13,21,24,28,30,42,77） 中下标为3的结点后，插入元素

25。问题：此时，线性表的逻辑结构发生什么变化？位置关系发生变化长度增1

序号元素230416751213212428304277插入25序号元素230416751213252124283042778在下标为k的结点后插入一个新结点//ADL描述算法Insert(A,k,x)Insert1[k是否合法]IF(k<0ORk>n)THENPRINT(“overflow”)ELSE(FORi=nTOk+1STEP-1DO

A[i+1]

A[i].A[i]

x.n

n+1.).▌时间复杂性分析插入操作的基本运算是：

元素移动Dn中有多少种可能的输入呢？

n+1种（n+1个位置可以发生插入）设每种输入发生的频率相等：1/（n+1）则期望复杂性为：E(n)=(n+(n-1)+……+1+0)/(n+1)=n/22、删除

[例]在线性表（12,13,21,24,28,30,42,77） 中删除下标为3的元素。问题：此时，线性表的逻辑结构发生什么变化？

位置关系发生变化长度减1序号元素230416751213212428304277删除24序号元素230416512132128304277删除下标为k的结点//ADL描述算法Delete(A,k)Delete1[检查k是否合法]IF(k<1ORk>n)THENPRINT(“error”)ELSE(FORi=k+1TOnDO

A[i-1]

A[i].

nn-1.)▌

时间复杂性分析删除操作的基本运算是：元素移动

Dn中有多少种可能的输入呢？

n种（n个位置可以发生删除）设每种输入发生的频率相等：1/n

则期望复杂性为：

E(n)=(n-1)/n+……+1/n+0/n=（n-1）/2

●结论：

优点：线性表的顺序存储结构简单、易于实现，数据的存取操作采用随机存取，可以随机访问表中任一元素。

缺点：线性表的容量不容易扩充，不利于数据的合并与分离；插入、删除操作需要移动大量元素。问题：由于线性表中元素的数目可以改变，定义数组时要做如何的考虑呢？

定义足够大的数组

4.2.2链接存储结构

————单链表

1、单链表的定义

●链式存储：用一组任意存储单元存储线性 表的数据元素。

单链表的结点结构：

链表的第一个结点被称为头结点，指向头结点

的指针被称为头指针。链表的最后一个结点被

称为尾结点。

●单链表的定义：每个结点只含有一个指针域的 链表叫单链表。datanext单链表的存储映像●特点：逻辑顺序与物理顺序可以相同也可 以不同。

优点：①插入、删除操作方便。 ②数据的合并与分离容易。结点可以不连续存储线性表可扩充[例]将线性表（a3，a4，a5),以链表的形式存储 在内存中。a5500a3100002a4002500∧●单链表的特性：

①在链表中，利用指针域表示线性表的逻辑结

构。②链表有头节点、尾节点、头指针。a5a3a4∧2.单链表插入、删除操作举例●插入：

…FATHAT…pGATssnext=pnext;pnext=s;×插入操作演示2.单链表插入、删除操作举例●删除：

删除操作演示

q=pnext;×…FATHAT…pGATqpnext=qnext;链表结点类Node的ADT描述：ADTNodeisDatadata用来保存结点信息的域

next用来存放后继结点地址信息的域，即存放指

向后继结点的指针

OperationsConstructorInitialvalue: 给出当前结点的data域值和next域值

Process: 对data域和next域进行初始化

NextNode:

Input: 无

Precondition: 无

Process: 取next域值

Output: 返回next域值

Postcondition: 无

InsertAfterInput: 指向被插入结点的指针

Precondition: 无

Process:在当前结点之后插入结点。

1．将当前结点的next域值赋给新插入结点的next域

2．将当前结点的next域值更新为新插入结点的地址

Output: 无

Postcondition:当前结点的next域存放新插入结点的地址

DeleteAfterInput: 无

Precondition:无

Process: 删除当前结点的后继结点。

将当前结点的后继结点的next域值赋给当前结点的next域

Output: 指向被删除结点的指针

Postcondition: 当前结点的next域值被更新

EndADTNode3.单链表基本操作算法

(1)Node类声明：

template<classT>classNode{private:Node<T>*next;public:Tdata;

//

构造函数Node(constT&item,Node<T>*ptrnext=NULL);//

在当前结点之后插入指针p所指结点voidInsertAfter(Node<T>*p);//

删除当前结点的后继结点Node<T>*DeleteAfter(void);//

返回指向当前结点的后继结点的指针Node<T>*NextNode(void)const;};

(2)Node类的实现①构造函数

template<classT>Node<T>::Node(constT&item,Node<T>*ptrnext）：

data(item),next(ptrnext){}

②返回当前结点的next域的值

C++：

template<classT>

Node<T>*Node<T>::

nextNode(void)const{returnnext;} ADL:算法NextNode(this.p) NextNode1[取当前结点的下一个结点] pnext(this).▌

③在当前结点之后插入结点p

//ADL描述算法InsertAfter（this，p）

IA1[将当前结点的next域值赋给P的next域]

next（p）

next（this）.IA2[将P赋给当前结点的next域]

next（this）

p.▌

…FATHAT…thisGATp×

④删除当前结点的后继结点

//ADL描述算法DeleteAfter（this.tempptr）

DA1[this的next域值=NULL？]IFnext（this）=NULL THENtempptr

NULLELSE（tempptr

next（this）. next（this）

next（tempptr））.▌

×…FATHAT…thisGATtempptr

(3)构造链表

//ADL描述①创建一个data域值为item,next域值为 nextptr的结点。算法GetNode（item，nextptr.newNode）

GN1[为新结点申请空间]

newNode

AVAIL.GN2[为结点诸域赋值]

data（newNode）

item.next（newNode）

nextptr.▌itemNewNodenextptr

②在头指针为head的链表中，插入一个data域为item的新结点作为该链表的表头结点。

算法InsertFront（head，item）

IF1[调用函数GetNode]

GetNode（item，head.newNode）.

IF2[head指向新结点]

head

newNode.▌

表头插入结点演示HATheadGAT∧itemnewNodehead

head

(4)遍历链表

遍历链表演示算法

PrintList（head）//输出头指针为head的链表,每输出5个元素换行PL1[取表头，计数器初始化]currptr

head.count

0.acbheadcurrptr∧PL2[遍历并输出链表结点的data值]

WHILE（currptr≠NULL）DO（PRINT（data（currptr））.count

count+1.IF（MOD（count，5）=0）THENPRINT.

currptr

next（currptr）.

）▌acbheadcurrptrcurrptrcurrptrcurrptr∧(5)表尾插入结点

表尾插入结点演示算法InsertRear（head，item）//在头指针为head的链表尾部插入data域值//为item的结点；IR1[取头指针]currptr

head.acbheadcurrptr∧

IR2[currptr=NULL？]IFcurrptr=NULLTHEN

InsertFront（head，item）

head=NULLcurrptr=NULLheaditemheadNULL

IR2[currptr=NULL？]IFcurrptr=NULLTHEN

InsertFront（head，item）

ELSE

（WHILE（next（currptr）≠NULL）DOcurrptr

next（currptr）.

GetNote（item，NULL.newNode）.InsertAfter（currptr，newNode）.）▌acbheadcurrptrcurrptrnewNodeitemNULL∧

定义一种链表类，将链表的基本操作视为链表类的成员函数，即将其封装在类中。

6.链表类LinkedList

在链表类的定义中，有一个当前指针，称当前指针所指结点为当前结点，用Node（currptr）记。类LinkedList的数据成员：头指针：front

尾指针：rear

当前指针：currptr

当前结点的前驱结点指针：prevptr

链表中结点个数：size

当前结点在链表中的位置：position//令当前指针指向表头voidReset（intpos=0）;

//令当前指针指向原当前结点的后继结点voidNext（void）;

//判断当前指针是否指向表尾结点intEndOfList（void）const;

//插入一个data域值为item的结点voidInsertFront（constT&item）; //表头插入voidInsertRear（constT&item）; //表尾插入//返回当前结点的data域值T&Data（void）; 例4.1按表L1在前，表L2在后的次序，实现两者的连接。template<classT>链表连接演示voidJointLists（LinkedList<T>&L1，LinkedList<T>&L2）{//为操作无误，先令两个表当前指针指向

//各自表头结点

L1.Reset（）; L2.Reset（）; while（!L2.EndOfList（））

{ L1.InsertRear（L2.Data（））;L2.Next（）; }}缺点：（1）单链表虽然克服了顺序存储的缺点，但却不能进行随机访问，数据存取只能采用顺序存取方式。（2）内存空间占用较多。问题：从单链表中某一个结点出发，能访问到它前面的结点吗？不能，只能访问到它后面的结点。对单链表来说，只有从头结点开始才能扫描表中全部结点.作业68页4-14.2.3循环链表

1.循环链表的定义和结构

循环链表的定义：在单链表中，使其表尾结点的指针指向表头结点，这样的链表叫循环链表。循环链表演示

xnx1…L单链表表头结点：第一个节点循环链表表头结点：哨位节点

●注意：判断表尾的条件：单链表：p

next==NULL循环链表：p

next==header

xnx1…pheader

判断空表的的条件:

单链表：head==NULL

循环链表：header

next＝＝header

header

2.循环链表结点类CNode的定义声明

template<classT>classCNode

{private：

CNode<T>*next;public:Tdata;

CNode(void);//生成哨位结点

CNode(constT&item):data(item),next(this){}voidInsertAfter(CNode<T>*p);CNode<T>*DeleteAfter(void);CNode<T>*NextNode(void)const;};s,s.InsertAfter(…),…实现

//删除当前结点的后继结点

ADL描述：算法DeleteAfter（this.tempptr）DA1[链表为空？]IFnext（this）=thisTHEN

tempptr

NULL

DeleteAfter函数的演示

ELSE(IFnext(this)＝headerTHEN (tempptrnext(header). next(header)next(tempptr).) ELSE (tempptr

next（this）.

next(this)

next(tempptr).))▌xnx1…headerthisx1headerthis4.2.4双向循环链表

1.问题的提出在循环链表中访问当前结点的前趋结点tempptrnext(p).WHILEnext(tempptr)≠pDOtempptrnext(tempptr).xnx1…headerp2双向循环链表的结构结点结构：

链表的结构：

。。。L★★leftdataright

headerleft==headerright==header

prightleft=pleftright=p

双向循环链表判空的条件：★双链表的对称性：★header

3循环双链表结点类DNode定义声明

template<classT>classDNode{private：

DNode<T>*left;

DNode<T>*right;

public:Tdata;

DNode(void);//生成哨位节点

DNode(constT&item);voidInsertRight(DNode<T>*p);voidInsertLeft(DNode<T>*p);DNode<T>*

DeleteNode(void);DNode<T>*NextNodeLeft(void)const;DNode<T>*NextNodeRight(void)const;};实现①

构造函数

tamplate<classT>Node<T>::DNode(constT&item）：

data(item),left(this),right(this){}

thisitem

在当前结点(this)之后插入结点p

left（right（this））

P.right（P）

right（this）.

left（P）

this.

right（this）

Pp4321this×②

在当前结点(this)之后插入结点p算法InsertRight（this，P）//在当前结点Node（this）的右边插入结点Node（P）IR1[令当前结点的右结点的左指针指向Node（P）]left（right（this））

P.IR2[令Node（P）的右指针指向当前结点的右结点]right（P）

right（this）.IR3[令Node（P）的左指针指向当前结点]left（P）

this.IR4[令当前结点的右指针指向Node（P）]right（this）

P▌右插入演示②p2134×在当前