数据结构与算法（C++版）课件第2章 线性表

第2章线性表数据结构与算法

(C++版)(第2版)2.1线性表的逻辑结构一、线性表的定义和特点1.线性表的定义

n（

0）个数据元素的有限序列，记作:

（a1,a2,…,an）

ai

是线性表中数据元素，n是线性表长度，其中ai称为ai+1的直接前驱，简称为前驱，ai+1称为ai的直接后继，简称为后继。

2.线性表的特点除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。a1a2a3a4a5a6一、线性表基本操作（1）intLength()const

初始条件：线性表已存在。

操作结果：返回线性表元素个数。

（2）boolEmpty()const

初始条件：线性表已存在。

操作结果：如线性表为空，则返回true，否则返回false。（3）voidClear()

初始条件：线性表已存在。

操作结果：清空线性表。

（4）voidTraverse(void(*visit)(constElemType&)) const

初始条件：线性表已存在。

操作结果：依次对线性表的每个元素调用函数(*visit)。（5）boolGetElem(intposition,ElemType&e)const

初始条件：线性表已存在，1≤position≤Length()。

操作结果：用e返回第position个元素的值。

（6）boolSetElem(intposition,constElemType&e)

初始条件：线性表已存在，1≤position≤Length()。

操作结果：将线性表的第position个位置的元素赋值为e。（7）boolDelete(intposition,ElemType&e)

初始条件：线性表已存在，1≤position≤Length()。

操作结果：删除线性表的第position个位置的元素,并用e返回其值，长度减1。（8）boolDelete(intposition)初始条件：线性表已存在，1≤position≤Length()。操作结果：删除线性表的第position个元素,，长度减1。（9）boolInsert(intposition,constElemType&e)

初始条件：线性表已存在，1≤position≤Length()+1。

操作结果：在线性表的第position个位置前插入元素e，长度加1。2.2线性表的顺序存储结构1.顺序表的定义和特点定义：将线性表中的元素相继存放在一个连续的存储空间中。特点：可利用一维数组描述存储结构，采用线性表的顺序存储方式253457164809

012345elemsa1

a2

a3

a4

a5

a6

2.顺序表(SeqList)类模板的

定义//顺序表类模板template<classElemType>classSqList{protected://顺序表实现的数据成员: intcount; //元素个数

intmaxSize; //顺序表最大元素个数

ElemType*elems; //元素存储空间public://抽象数据类型方法声明及重载编译系统默认方法声明: SqList(intsize=DEFAULT_SIZE);

//构造函数模板

virtual~SqList(); //析构函数模板

intLength()const; //求线性表长度

boolEmpty()const; //判断线性表是否为空

voidClear(); //将线性表清空 voidTraverse(void(*visit)(constElemType&)) const; //遍历线性表

boolGetElem(intposition,ElemType&e)const; //求指定位置的元素

boolSetElem(intposition,constElemType&e);

//设置指定位置的元素值

boolDelete(intposition,ElemType&e);//删除元素

boolDelete(intposition); //删除元素

boolInsert(intposition,constElemType&e);

//插入元素

SqList(constSqList<elemType>&source);

//复制构造函数模板

SqList<elemType>&operator=(const SqList<elemType>&source);

//重载赋值运算符};template<classElemType>SqList<ElemType>::SqList(intsize)//操作结果：构造一个最大元素个数为size的空顺序表{ maxSize=size; //最大元素个数 elems=newElemType[maxSize];//分配存储空间 count=0; //空线性表元素个数为0}template<classElemType>SqList<ElemType>::~SqList()//操作结果：销毁线性表{ delete[]elems; //释放存储空间}3.顺序表部分操作的实现（1）表项的插入25345716480963

a1

a2

a3

a4

a5

a6

a7

a8elems50插入e2534575016480963

a1

a2

a3

e

a4

a5

a6

a7elems50itemplate<classElemType>boolSqList<ElemType>::Insert(intposition,constElemType&e)//操作结果：在线性表的第position个元素前插入元素e，// position的的取值范围为// 1≤position≤Length()+1，如线性表已满,则返回// false，如position合法,则返回true,否则返回false{ if(count==maxSize) { //线性表已满返回false returnfalse; } elseif(position<1||position>Length()+1) { //position范围错 returnfalse; //范围错 }

else { //成功 intlength=Length(); //暂存线性表长度

ElemTypetemElem; //临时元素

count++; //插入后元素个数将自增1 for(inttemPos=length;temPos>=position; temPos--) { //插入位置之后的元素右移

GetElem(temPos,temElem);

SetElem(temPos+1,temElem); } SetElem(position,e); //将e赋值到position处 returntrue; //插入成功 }}（2）表项的删除2534575016480963

a1

a2

a3

a4

a5

a6

a7

a8elems16删除

e25345750480963

a1

a2

a3

a4

a6

a7

a8

a9elemstemplate<classElemType>boolSqList<ElemType>::Delete(intposition,ElemType&e)//操作结果：删除线性表的第position个元素,并前用e返// 回其值，position的取值范围为1≤position≤Length()，// position合法时返回true，否则返回false{ if(position<1||position>Length()) { //position范围错 returnfalse; //范围错 } else { //position合法 GetElem(position,e); //用e返回被删除元素 ElemTypetemElem; //临时元素 for(inttemPos=position+1; temPos<=Length();temPos++) { //被删除元素之后的元素依次左移

GetElem(temPos,temElem);

SetElem(temPos-1,temElem);

} count--; //删除后元素个数将自减1 returntrue; //删除成功 }}4.顺序表的应用：集合的“差”运算//文件路径名:s2_1\alg.htemplate<classElemType>voidDifference(constSqList<ElemType>&la, constSqList<ElemType>&lb, SqList<ElemType>&lc)//操作结果:用lc返回la和lb表示的集合的差集//方法:在la中取出元素,在lb中进行查找,如果未在lb中// 出现了,将其插入到lc{ ElemTypeaElem,bElem; lc.Clear(); //清空lc for(intaPos=1;aPos<=la.Length();aPos++) { la.GetElem(aPos,aElem);

//取出la的一个元素aElem boolisExist=false;

//表示aElem是否在lb中出现

for(intbPos=1;bPos<=lb.Length();bPos++) { lb.GetElem(bPos,bElem);

//取出lb的一个元素bElem if(aElem==bElem) { isExist=true; //aElem同时在la和lb中

//出现,置isExist为true

break; //退出内层循环

} } if(!isExist) { //aElem在la中出现,而未在lb中未出现, // 将其插入到lc中

lc.Insert(lc.Length()+1,aElem); } }}2.3线性表的链式存储结构一、单链表

(SinglyLinkedList)

用一组地址任意的存储单元存放线性表中的数据元素。以data(元素的值)

+next(后继)=结点(表示数据元素)以“结点的序列”表示线性表称作单链表1.单链表的概念

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

a1a2…...an^头指针头指针

有时为了操作方便，在第一个结点之前虚加一个“头结点”，这时指向头结点的指针称为链表的头指针。空指针线性表为空表时，头结点的指针成份为空

//结点类模板template<classElemType>structNode{//数据成员: ElemTypedata; //数据成分

Node<ElemType>*next; //指针成分//构造函数模板: Node(); //无参数的构造函数模板

Node(ElemTypee,Node<ElemType>*link= NULL);//已知数据成份和指针成份建立结构};2.单链表的相关类模板//简单线性链表类模板template<classElemType>classSimpleLinkList{protected://链表实现的数据成员:

Node<ElemType>*head; //头结点指针//辅助函数模板: Node<ElemType>*GetElemPtr(intposition)const; //返回指向第position个结点的指针public://抽象数据类型方法声明及重载编译系统默认方法声明: SimpleLinkList(); //无参数构造函数模板

virtual~SimpleLinkList(); //析构函数模板

intLength()const; //求线性表长度

boolEmpty()const; //判断线性表是否为空

voidClear(); //将线性表清空

voidTraverse(void(*visit)(constElemType&)) const; //遍历线性表

boolGetElem(intposition,ElemType&e)const; //求指定位置的元素

boolSetElem(intposition,constElemType&e); //设置指定位置的元素值 boolDelete(intposition,ElemType&e);//删除元素 boolDelete(intposition);//删除元素

boolInsert(intposition,constElemType&e); //插入元素

SimpleLinkList(constSimpleLinkList<ElemType> &source); //复制构造函数模板

SimpleLinkList<ElemType>&operator=(const SimpleLinkList<ElemType>&source); //重载赋值运算符};3.单链表中的插入与删除插入newPtr=newNode<ElemType>(e,temPtr->next);temPtr->next=newPtr;

template<classElemType>boolSimpleLinkList<ElemType>::Insert( intposition,constElemType&e)//操作结果：在线性表的第position个位置前插入元素e// position的取值范围为1≤position≤Length()+1// position合法时返回true,否则返回false{ if(position<1||position>Length()+1) { //position范围错

returnfalse; //位置不合法

} else { //position合法

Node<ElemType>*temPtr; temPtr=GetElemPtr(position-1); //取出指向第position-1个结点的指针

Node<ElemType>*newPtr; newPtr=newNode<ElemType>(e, temPtr->next); //生成新结点

temPtr->next=newPtr; //将temPtr插入到链表中

returntrue; }}删除

nextPtr=temPtr->next; //nextPtr为temPtr的后继

temPtr->next=nextPtr->next;//删除结点

deletenextPtr; //释放被删结点在单链表中删除含b的结点template<classElemType>BoolSimpleLinkList<ElemType>::Delete(intposition, ElemType&e)//操作结果：删除线性表的第position个位置的元素,并用// e返回其值,position的取值范围为// 1≤position≤Length(),position合法时返回// true,否则返回false{ if(position<1||position>Length()) { //position范围错

returnfalse; } else { //position合法

Node<ElemType>*temPtr; temPtr=GetElemPtr(position-1); //取出指向第position-1个结点的指针

Node<ElemType>*nextPtr=temPtr->next; //nextPtr为temPtr的后继

temPtr->next=nextPtr->next;//删除结点

e=nextPtr->data;//用e返回被删结点元素值

deletenextPtr; //释放被删结点

returntrue; }}二、循环链表(CircularList)循环链表是单链表的变形。循环链表最后一个结点的next指针不为NULL，而是指向了表的前端。为简化操作，在循环链表中往往加入表头结点。循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。1.循环链表的概念2.循环链表示例//简单循环链表类模板template<classElemType>classSimpleCircLinkList{protected://循环链表实现的数据成员: Node<ElemType>*head; //头结点指针//辅助函数模板: Node<ElemType>*GetElemPtr(intposition)const; //返回指向第position个结点的指针3.循环链表的相关类模板public://抽象数据类型方法声明及重载编译系统默认方法声明: SimpleCircLinkList(); //无参数的构造函数模板

virtual~SimpleCircLinkList(); //析构函数模板

intLength()const; //求线性表长度

boolEmpty()const; //判断线性表是否为空

voidClear(); //将线性表清空

voidTraverse(void(*visit)(constElemType&)) const; //遍历线性表

boolGetElem(intposition,ElemType&e) const; //求指定位置的元素

boolSetElem(intposition,constElemType&e); //设置指定位置的元素值 boolDelete(intposition,ElemType&e);//删除元素 boolDelete(intposition); //删除元素

boolInsert(intposition,constElemType&e); //插入元素

SimpleCircLinkList(const SimpleCircLinkList<ElemType>&source); //复制构造函数模板

SimpleCircLinkList<ElemType>&operator=(const SimpleCircLinkList<ElemType>&source); //重载赋值运算符};4.循环链表的应用——用循环链表求解约瑟夫问题约瑟夫问题的提法

n个人围成一个圆圈，首先第1个人从1开始一个人一个人顺时针报数,报到第m个人，令其出列。然后再从下一个人开始，从1顺时针报数，报到第m个人，再令其出列，…，如此下去,直到圆圈中只剩一个人为止。此人即为优胜者。例如n=8m=3//文件路径名:s2_5\alg.hvoidJosephus(intn,intm)//操作结果:n个人围成一个圆圈，首先第1个人从1开始一// 个人一个人顺时针报数,报到第m个人，令其出列。// 然后再从下一个人开始，从1顺时针报数报到第m// 个人，再令其出列，…，如此下去,直到圆圈中只// 剩一个人为止。此人即为优胜者{ SimpleCircLinkList<int>la; //定义空循环链表

intpos=0; //报数到的人在链表中序号

intout,winer; for(intk=1;k<=n;k++)la.Insert(k,k); //建立数据成份为1,2,..,n的循环链表 cout<<"出列者:"; for(inti=1;i<n;i++) { //循环n-1次，让n-1个个出列

for(intj=1;j<=m;j++) { //从1报数到m pos++; if(pos>la.Length()) pos=1; } la.Delete(pos--,out);//报数到m的人出列

cout<<out<<""; } la.GetElem(1,winer); //剩下的一个人为优胜者

cout<<endl<<"优胜者:"<<winer<<endl;}三、双向链表

(DoublyLinkedList)1.双向链表的概念双向链表是指在前驱和后继方向都能游历(遍历)的线性链表。双向链表每个结点结构：前驱方向后继方向双向链表通常