天津大学本科课程考研数据结构课件全

数据结构

什么是数据结构基本概念和术语抽象数据类型算法分析性能分析与度量第一章绪论学生成绩表格选课单学号课程号时间成绩20001DS2000SX20002001,22000,9788720002ART2000DS20002002,22001,2689020003SX2000DS20002000,92001,2877820004SX2000ART20002000,92002,28976UNIX文件系统结构图/rootbinlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp例如:在迷宫问题中,计算机之所以能够找到迷宫的出口,是因为人们已将搜索出口的策略事先存入计算机中.在迷宫中,每走到一处,接下来可走的通路有三条,如图:计算机处理的这类对象之间通常不存在线性关系,若将从迷宫入口处到出口的过程中所有可能的通路都画出来,则可以得到一棵倒长的”树”.”树根”是迷宫入口,”树叶”是出口或死路.”树”可以是某些非数值计算问题的数学模型.入口死路死路死路死路死路死路死路死路死路死路出口死路死路死路死路在应用程序中涉及到各种各样的数据，如何在计算机中组织、存储、传递数据，需要讨论它们的归类及它们之间的关系，从而建立相应的数据结构，依此实现软件功能。综上，描述这类非数值计算问题的数学模型不是数学方程,而是树、表和图之类的数据结构。因此从广义上讲，数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现。基本概念和术语数据(Data)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。

数值性数据（整数、定点数、浮点数）非数值性数据（文字数据）数据元素（DataElement）数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。有时一个数据元素可以由若干数据项(DataItem)组成。数据项是具有独立含义的最小标识单位。数据元素又称为元素、结点、记录数据项(DataItem)

姓名俱乐部名称出生日期年月日入队日期职位业绩数据元素DataElement数据项DataItem数据字段DataField数据对象(dataobject)具有相同性质的数据元素的集合。整数数据对象N={0,1,2,…}字母字符数据对象

C={‘A’,‘B’,‘C’,…‘F’}数据结构（DataStructure）形式定义：

某一数据对象的所有数据成员之间的关系。记为：

Data_Structure={D,S}

其中，D是某一数据对象，S是该对象中所有数据成员之间的关系的有限集合。四个基本结构集合线性结构树形结构网状结构数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关；从具体问题抽象出来的数据模型；与数据元素本身的形式、内容无关；与数据元素的相对位置无关。数据的逻辑结构分类线性结构

线性表非线性结构

树图（或网络）bindevetclibuser2114131211234678910315871011998745662313155线性结构树形结构

树二叉树二叉排序树堆结构123548711102916125643125436113318146651921图结构网络结构数据的存储结构（物理结构）数据结构在计算机中的表示。数据的存储结构依赖于计算机语言。

顺序存储表示链接存储表示索引存储表示散列存储表示数据处理将数据通过人力或机器，将收集到的数据加以系统的处理，归纳出有价值的信息。编辑（edit）：将存在某种媒体上的数据经过计算机复制到另一媒体时，对输入的数据逐一检查，其目的在于改变数据的存储形式和效率，以便后面的处理。排序（sort）：将数据根据某一键值，以某种顺序排序后输出，其目的在于方便其他方面的数据处理。归并（merge）：将两种以上相同性质的文件数据归并在一起。分配（distribute）：将一个文件的数据按照某一基准分配在两个以上的存储体，其目的在于方便各个分配的文件能独自处理。建档（generate）：根据某些条件规格，配合某些已存在的文件，再产生一个新的且有利用价值的文件。更新（update）：根据数据的变动来更新主档案，以保持主档案的正确与完整性。计算（compute）：将读取的文件数据，依据规定方法计算处理。链表（list）：是一种数据的集合，也就是一系列的数据存储于内存，以某种关系来连接这些相关联的数据。查找（search）：输入一个键值到数据表中进行对照，找出具有相同键值的数据。查询（inquiry）：根据数据项的键值或条件，到主档案中找出符合该条件或键值相同的数据，依照用户指定的方法输出。其它处理：分类（classifying）、摘要（summarizing）、变换(transmission)。抽象数据类型（AbstractDataType）数据类型

定义：一个值的集合和定义在这个值集上的一组操作的总称。C语言中的基本数据类型

intcharfloatdoublevoid

整型字符型浮点型双精度型无值抽象数据类型是指一个数学模型以及定义在此数学模型上的一组操作数据结构+定义在此数据结构上的一组操作=抽象数据类型例如：矩阵+（求转置、加、乘、 求逆、求特征值） 构成一个矩阵的抽象数据类型抽象数据类型的描述抽象数据类型可用（D，S，P）三元组表示 其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。

ADT抽象数据类型名{

数据对象：〈数据对象的定义〉

数据关系：〈数据关系的定义〉

基本操作：〈基本操作的定义〉 }ADT抽象数据类型名其中,数据对象、数据关系用伪码描述；基本操作定义格式为 基本操作名（参数表） 初始条件：〈初始条件描述〉

操作结果：〈操作结果描述〉基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。“初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。“操作结果”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。抽象数据类型的表示和实现

抽象数据类型可以通过固有数据类型(高级编程语言中已实现的数据类型)来实现抽象数据类型类class数据对象数据成员基本操作成员函数(方法)在C++中，类的成分(数据成员和成员函数)可以有三种访问级别Private私有成分（只允许类的成员函数进行访问）

protected保护成分（只允许类的成员函数及其子孙类进行访问）public公有成分（允许类的成员函数、类的实例及其子孙类、子孙类的实例进行访问）自然数的抽象数据类型定义ADT

NaturalNumberisobjects:一个整数的有序子集合,它开始于0,

结束于机器能表示的最大整数(MaxInt)。Function:

对于所有的x,

y

NaturalNumber;

False,TrueBoolean,+、-、<、==、=等都是可用的服务。

Zero():NaturalNumber

返回自然数0IsZero(x):if(x==0)返回True

Booleanelse返回FalseAdd(x,y):if(x+y<=MaxInt)返回x+y

NaturalNumber

else返回MaxIntSubtract(x,y):if(x<y)返回0

NaturalNumberelse返回x-yEqual(x,y):if(x==y)返回True

Booleanelse返回FalseSuccessor(x):if(x==MaxInt)返回xNaturalNumberelse返回x+1end

NaturalNumber程序的产生五个阶段：需求（输入、输出）设计（编写算法）分析（选择最佳算法）细化与编码（编写程序）验证（程序验证、测试、调试）算法分析算法定义：为了解决某类问题而规定的一个有限长的操作序列。特性：有穷性算法在执行有穷步后能结束确定性每步定义都是确切、无歧义可行性每一条运算应足够基本输入有0个或多个输入输出有一个或多个输出算法设计例子：

选则排序问题：递增排序解决方案：逐个选择最小数据算法框架：

for(inti=0;i<n-1;i++){

//n-1趟 从a[i]检查到a[n-1];

若最小整数在a[k],交换a[i]与a[k];}细化：SelectSortvoidselectSort(inta[],intn){

//对n个整数a[0],a[1],…,a[n-1]按递增顺序排序

for(inti=0;i<n-1;i++){

intk=i;

//从a[i]查到a[n-1],找最小整数,在a[k]

for(intj=i+1;j<n;j++)

if(a[j]<a[k])k=j;

inttemp=a[i];a[i]=a[k];a[k]=temp;}}

模板

(template)定义

适合多种数据类型的类定义或算法，在特定环境下通过简单地代换，变成针对具体某种数据类型的类定义或算法例：求最大值max(a,b)宏定义：#definemax(a,b)((a)>(b)?(a):(b))缺点不能检查数据类型，损害类型安全性例：求最大值max(a,b)函数重载：intmax(inta,intb){returna>b?a:b;}floatmax(floata,floatb){returna>b?a:b;}voidmain(){ cout<<“Max(3,5)is”<<max(3,5)<<endl; cout<<“Max(‘3’,’5’)is”<<max(‘3’,’5’)<<endl;}对于输入max(3,5)和max(‘3’,’5’)的结果？例：求最大值max(a,b)函数模板：#include<iostream.h>template<classT>Tmax(Ta,Tb){returna>b?a:b;}voidmain(){ cout<<“Max(3,5)is”<<max(3,5)<<endl; cout<<“Max(‘3’,’5’)is”<<max(‘3’,’5’)<<endl;}性能分析与度量算法的性能标准正确性：包括不含语法错误对几组数据运行正确对典型、苛刻的数据运行正确；对所有数据运行正确可读性效率：高效、低存储需要。（算法执行时间短，同时所占用的存储空间小。健壮性：当输入非法数据时，算法也能作出适当反应，而不会出现莫名其妙的输出结果。算法的后期测试在算法中的某些部位插装时间函数time

(),

测定算法完成某一功能所花费时间

doublestart,stop;

time(&start);

intk=seqsearch(a,n,x);

time(&stop);

doublerunTime=stop-start;printf("%d%d\n",n,runTime);intseqsearch(inta[],intn,intx){//在a[0],…,a[n-1]中搜索x

inti=0;

while(i<n&&a[i]!=x)

i++;

if(i==n)return

-1;

returni;}

算法的事前估计空间复杂度度量存储空间的固定部分

程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占空间可变部分

尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用空间、通过new和delete命令动态使用空间时间复杂度度量运行时间=算法中每条语句执行时间之和。每条语句执行时间=该语句的执行次数（频度）*语句执行一次所需时间。语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量，很难确定。设每条语句执行一次所需时间为单位时间，则一个算法的运行时间就是该算法中所有语句的频度之和。时间复杂度一、时间复杂度即算法中语句重复执行次数的数量级就是时间复杂度。二、表示方法：

T(n)=O(f(n))f(n)表示基本操作重复执行的次数，是n的某个函数，随问题规模n的增大，算法执行时间的增长率和f(n)的增长率属于同一数量级；O表示f(n)和T(n)只相差一个常数倍。T（n)称做渐进时间复杂度，简称时间复杂度。几种时间复杂度O(1):常数时间O(log2n)：对数时间O(n)：线性时间O(nlog2n)：线性对数时间O(n2):平方时间O(n3):立方时间O(2n):指数时间上述的时间复杂度的优劣次序如下（n>=16):O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)第二章线性表线性表顺序表链表顺序表与链表的比较线性表定义：

n（0）个数据元素的有限序列，记作（a1,…ai-1,ai,ai+1,…,an）

其中,ai

是表中数据元素，n是表长度。特点:同一线性表中元素具有相同特性。相邻数据元素之间存在序偶关系。除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。 a1a2a3a4a5a6顺序表定义：将线性表中的元素相继存放在一个连续的存储空间中。

存储结构：数组。特点：线性表的顺序存储方式。存取方式：顺序存取、随机存取顺序存储结构示意图458990674078

012345顺序表的存储方式：LOC(ai+1)=LOC(ai)+lLOC(ai)=LOC(a1)+(i-1)*l

a1

a2

…ai………an12…i………n

aa+l…a+(i-1)*l………a+(n-1)*l

idle顺序表（SeqList）的类型定义

#defineListSize100//最大允许长度

typedefintListData;

typedefstruct

{

ListData*data;//存储空间基址

intlength; //当前元素个数

}

SeqList;顺序表基本运算初始化

voidInitList(SeqList&L){L.data=(ListData*)malloc(ListSize*sizeof(ListData));if(L.data==NULL){printf(“存储分配失败!\n”);exit(1);}L.length=0;}按值查找：找x在表中的位置，若查找成功，返回表项的位置，否则返回-1

intFind(SeqList&L,ListDatax){inti=0;while(i<L.length&&L.data[i]!=x)i++;if(i<L.length)returni;elsereturn-1;}顺序搜索图示253457164809

012345data搜索

16i253457164809

i253457164809

i253457164809

i搜索成功2534571648

01234data搜索50i2534571648

i2534571648

i2534571648

i2534571648

i搜索失败搜索成功的平均比较次数

若搜索概率相等，则

搜索不成功数据比较n

次按值查找：判断x是否在表中

intIsIn(SeqList&L,ListDatax){ inti=0, found=0; while(i<L.length&&!found) if(L.data[i]!=x)i++; elsefound=1;returnfound;}求表的长度

intLength(SeqList&L){returnL.length;}提取函数：在表中提取第i个元素的值

ListDataGetData(SeqList&L,inti){if(i>=0&&i<L.length)returnL.data[i];elseprintf(“参数

i不合理！\n”); }

按值查找：寻找x的后继

intNext(SeqList&L,ListDatax){inti=Find(x);if(i>0&&i<L.length)returni+1; elsereturn-1;}寻找x的前驱

intPrevious(SeqList&L,ListDatax){inti=Find(x);if(i>0&&i<L.length)returni-1; elsereturn-1;}插入25345716480963

0123456750插入x2534575016480963

0123456750i顺序表插入时，平均数据移动次数AMN在各表项插入概率相等时顺序表的插入

intInsert(SeqList&L,ListDatax,inti){

//在表中第i个位置插入新元素x

if(i<0||i>L.length||L.length==ListSize)return0;//插入不成功

else{ for(intj=L.length;j>i;j--) L.data[j]=L.data[j-1]; L.data[i]=x;L.length++; return1;//插入成功

}}删除253457501648096316删除

x2534575048096301234567顺序表删除平均数据移动次数AMN在各表项删除概率相等时顺序表的删除

intDelete(SeqList&L,ListDatax){

//在表中删除已有元素x

inti=Find(L,x); //在表中查找xif(i>=0){ L.length--; for(intj=i;j<L.length;j++) L.data[j]=L.data[j+1];return1; //成功删除

} return0;//表中没有x}顺序表的应用:集合的“并”运算voidUnion(SeqList&A,SeqList&B){intn=Length(A);intm=Length(B);for(inti=0;i<m;i++){ intx=GetData(B,i);//在B中取一元素

intk=Find(A,x);//在A中查找它

if(k==-1)//若未找到插入它

{Insert(A,x,n);n++;}}}集合的“交”运算

voidIntersection(SeqList&A,SeqList&B){intn=Length(A);intm=Length(B);inti=0;while(i<n){intx=GetData(A,i);//在A中取一元素

intk=Find(B,x);//在B中查找它

if(k==-1){Delete(A,i);n--;} elsei++;//未找到在A中删除它

}}顺序表(SeqList)类的定义template<classType> classSeqList{Type*data;//顺序表存储数组

intMaxSize; //最大允许长度

intlast; //当前最后元素下标public: SeqList(intMaxSize=defaultSize); ~SeqList(){delete[]data;}

intLength()const

{returnlast+1;

}C++描述

intFind(Type&x)const;//查找

intLocate(inti)const; //定位

intInsert(Type&x,inti);//插入

intRemove(Type

&x); //删除

intNext(Type

&x); //后继

intPrior(Type

&x);//前驱

intIsEmpty(){returnlast==-1;

} intIsFull(){returnlast==MaxSize-1;

}TypeGet(inti){//提取

returni<0||i>last？NULL:data[i];}}

C++描述顺序表部分公共操作的实现

template<classType>

//构造函数

SeqList<Type>::SeqList(intsz){if(sz>0){ MaxSize=sz;last=-1; data=newType[MaxSize];

if(data==NULL){MaxSize=0;last=-1;return;}

}}C++描述template<classType> intSeqList<Type>::Find(Type

&x)const{//搜索函数：在顺序表中从头查找结点值等于//给定值x的结点

inti=0;

while(i<=last&&data[i]!=x)i++;

if(i>last)return-1;

elsereturni; }C++描述template<classType>intSeqList<Type>::Insert(Type&x,inti){//在表中第

i个位置插入新元素

x

if(i<0

||

i>last+1

||

last==MaxSize-1)

return0;//插入不成功

else{last++;

for(intj=last;j>i;j--)data[j]=data[j-1]; data[i]=x;return1;//插入成功

}}C++描述

template<classType>intSeqList<Type>::Remove(Type&x){

//在表中删除已有元素

x

inti=Find(x); //在表中搜索

x

if(i>=0){ last--;

for(intj=i;j<=last;j++)data[j]=data[j+1];

return1; //成功删除

} return0;//表中没有

x}C++描述顺序表的应用：集合的“并”运算

voidUnion(SeqList<int>

&A,SeqList<int>

&B){

intn=A.Length();

intm=B.Length();

for(inti=0;i<m;i++){ intx=B.Get(i);//在B中取一元素

intk=A.Find(x);//在A中搜索它

if(k==-1)//若未找到插入它

{A.Insert(n,x);n++;}}}C++描述顺序表的应用：集合的“交”运算

voidIntersection(SeqList<int>

&A,SeqList<int>

&B){

intn=A.Length();

intm=B.Length();inti=0;

while(i<n){intx=A.Get(i);//在A中取一元素

intk=B.Find(x);//在B中搜索它

if(k==-1){A.Remove(i);n--;} elsei++;//未找到在A中删除它

}}C++描述链表（LinkedList）链表是线性表的链接存储表示单链表静态链表循环链表双向链表单链表(SinglyLinkedList)定义：用一组地址任意的存储单元存放线性表中的数据元素。例如：线性表ZHOU,ZHAO,SUN,WU,WANG,ZHANG,LI数据域指针域ZHANG13WANG1LInullZHAO37WU7ZHOU19SUN25存储地址17131925313731头指针表中节点位置6572413每个元素由结点(Node)构成, 它包括两个域:数据域Data和指针域Linkdatalink存储结构：链式存储结构特点：存储单元可以不连续。存取方式：顺序存取。Node单链表结构单链表的类型定义typedefcharListData;typedefstructnode{//链表结点

ListDatadata; //结点数据域

structnode*link;//结点链域}ListNode;typedefListNode*LinkList;//链表头指针LinkListfirst;//链表头指针单链表的类定义多个类表达一个概念(单链表)。链表结点(ListNode)类链表(List)类链表游标(Iterator)类定义方式复合方式嵌套方式

继承方式

classList;

//链表类定义（复合方式）

classListNode{

//链表结点类

friendclassList;

//链表类为其友元类

private:

intdata;

//结点数据,整型

ListNode*link;

//结点指针

};classList{

//链表类

private:ListNode*first,*last;

//表头指针};classList{

//链表类定义(嵌套方式)private:

classListNode{

//嵌套链表结点类

public:

intdata;

ListNode*link;

};ListNode*first,*last;

//表头指针public:

//链表操作………};链表类和链表结点类定义(继承方式)classListNode{

//链表结点类

protected:

intdata;

ListNode*link;

};classList:public

classListNode{

//链表类,继承链表结点类的数据和操作

private:ListNode*first,*last;

//表头指针};单链表的基本运算插入（三种情况）

第一种情况：在第一个结点前插入

newnode->link=first;first=newnode;（插入前）（插入后）

firstnewnodenewnodefirst第二种情况：在链表中间插入

newnode->link=p->link; p->link=newnode；(插入前)(插入后)newnodepnewnodep第三种情况：在链表末尾插入

newnode->link=p->link; p->link=newnode；p(插入前)(插入后)newnodenewnodep算法描述intList::Insert(intx,inti){//在链表第

i个结点处插入新元素

x

ListNode*p=first;for(

k=0;k<i-1;k++)

//找第i-1个结点

if(p==NULL)break;

elsep=p->link;

if(p==NULL&&first!=NULL){

cout<<“无效的插入位置!\n”;return0;}

ListNode*newnode=

//创建新结点

newListNode(x,NULL);

if(first==NULL||i==0){

//插在表前

newnode->link=first; if(first==NULL)last=newnode;

first=newnode;}else{

//插在表中或末尾

newnode->link=p->link;

if(p->link==NULL)last=newnode;

p->link=newnode;}

return1;

}删除 在单链表中删除ai结点

q=p->link; p->link=q->link;删除前删除后ai-1aiai+1pqpai-1ai+1aiintList::Remove(inti){//在链表中删除第i个结点

ListNode*p,*q;if(i==0)

//删除表中第

1个结点

{q=first;p=first=first->link;}else{

p=first; intk=0;

//找第i-1个结点

while(p!=NULL&&k<i-1)

{p=p->link;k++;}if(p==NULL||p->link==NULL){cout<<“无效的删除位置!\n”;return0;

}

else{

//删除表中或表尾元素

q=p->link;

//重新链接

p->link=q->link;} if(

q==last)last=p; //可能修改last

Typex=q->data;deleteq;

//删除q

returnx;

//返回第i个结点的值

}带表头结点的单链表表头结点位于表的最前端，本身不带数据，仅标志表头。设置表头结点的目的:简化链表操作的实现。非空表空表^ana1firstfirst^插入

q->link=p->link; p->link=q;firstqfirstqfirstq^firstq^pppp插入前插入后表头表尾qq插入pp表中intInsert(LinkListfirst,ListDatax,inti){//将新元素x插入在链表中第i号结点位置

ListNode*p=Locate(first,i-1);if(p==NULL)return0; //参数i值不合理返回0ListNode*newnode=//创建新结点

(ListNode*)malloc(sizeof(ListNode));newnode->data=x;newnode->link=p->link;//链入

p->link=newnode;return1; }删除

q=p->link;p->link=q->link;deleteq;删除前first(非空表）(空表）first^firstpq^pqfirst删除后intdelete(LinkListfirst,inti){ //将链表第i号元素删去

ListNode*p,*q p=Locate(first,i-1);//寻找第i-1个结点

if(p==NULL||p->link==NULL) return0;//i值不合理或空表

q=p->link; p->link=q->link;//删除结点

free(q); //释放

return1;}前插法建立单链表从一个空表开始，重复读入数据：生成新结点将读入数据存放到新结点的数据域中将该新结点插入到链表的前端直到读入结束符为止。firstqfirstq^^LinkListcreateListF(void){charch;ListNode*q;LinkListhead=//建立表头结点(LinkList)malloc(sizeof(ListNode));head->link=NULL;while((ch=getchar())!=‘\n’){q=(ListNode*)malloc(sizeof(ListNode));q->data=ch;//建立新结点

q->link=head->link;//插入到表前端

head->link=q;}returnhead;}后插法建立单链表每次将新结点加在链表的表尾；尾指针r,总是指向表中最后一个结点，新结点插在它的后面；^qfirst^r^first^rLinkListcreateListR(void){charch;LinkListhead=//建立表头结点(LinkList)malloc(sizeof(ListNode));ListNode*q,*r=head; while((ch=getchar())!=‘\n’){q=(ListNode*)malloc(sizeof(ListNode));q->data=ch;//建立新结点

r->link=q;r=q;

//插入到表末端}

r->link=NULL;

returnhead;}单链表清空voidmakeEmpty(LinkListfirst){//删去链表中除表头结点外的所有其它结点

ListNode*q;while(first->link!=NULL){//当链不空时，循环逐个删去所有结点

q=first->link;first->link=q->link; free(q);//释放

} last=first;}计算单链表长度intLength(LinkListfirst){ListNode*p=first->link;//指针p指示第一个结点

intcount=0;while(p!=NULL){//逐个结点检测

p=p->link;count++;} returncount;}

按值查找ListNode*Find(LinkListfirst,ListDatavalue){ //在链表中从头搜索其数据值为value的结点

ListNode*p=first->link;

//指针p指示第一个结点

while(p!=NULL&&p->data!=value)p=p->link;returnp;}按序号查找（定位）

ListNode*Locate(LinkListfirst,inti){//返回表中第i个元素的地址

if(i<0)returnNULL;ListNode*p=first;intk=0;while(p!=NULL&&k<i){p=p->link;k++;} //找第i个结点

if(k==i)returnp;//返回第i个结点地址

elsereturnNULL;}1ZHANG2WANG6LI5ZHAO5WU-1CHEN31ZHANG2WANG3LI4ZHAO5WU-101234560123456修改前（插入chen,删除zhao)修改后用一维数组描述线性链表静态链表定义constintMaxSize=100;//静态链表大小typedefintListData;typedefstructnode{//静态链表结点

ListDatadata;

intlink;}SNode;typedefstruct{//静态链表

SNodeNodes[MaxSize];intnewptr; //当前可分配空间首地址}SLinkList;链表空间初始化voidInitList(SLinkList*SL){SL->Nodes[0].link=1;SL->newptr=1;//当前可分配空间从1开始

//建立带表头结点的空链表

for(inti=1;i<MaxSize-1;i++)SL->Nodes[i].link=i+1;//构成空闲链接表

SL->Nodes[MaxSize-1].link=-1;

//链表收尾}在静态链表中查找具有给定值的结点intFind(SLinkListSL,ListDatax){intp=SL.Nodes[0].link;//指针p指向链表第一个结点

while(p!=-1)//逐个查找有给定值的结点

if(SL.Nodes[p].data!=x)p=SL.Nodes[p].link;elsebreak; returnp;}在静态链表中查找第i个结点intLocate(SLinkListSL,inti){if(i<0)return-1;//参数不合理

intj=0,p=SL.Nodes[0].link;while(p!=-1&&j<i){//循环查找第i号结点

p=SL.Nodes[p].link;j++;}if(i==0)return0;returnp;}在静态链表第i个结点处插入一个新结点intInsert(SLinkList*SL,inti,ListDatax){intp=Locate(SL,i-1);if(p==-1)return0;//找不到结点

intq=SL->newptr;//分配结点

SL->newptr=SL->Nodes[SL->newptr].link;SL->Nodes[q].data=x;

SL->Nodes[q].link=SL.Nodes[p].link;SL->Nodes[p].link=q;

//插入

return1;}在静态链表中释放第i个结点intRemove(SLinkList*SL,inti){intp=Locate(SL,i-1);if(p==-1)return0;//找不到结点

intq=SL->Nodes[p].link;//第i号结点

SL->Nodes[p].link=SL->Nodes[q].link;SL->Nodes[q].link=SL->newptr;//释放

SL->newptr=q;return1;}循环链表(CircularList)特点:最后一个结点的link指针不为NULL，而是指向头结点。只要已知表中某一结点的地址，就可搜寻所有结点的地址。存储结构:链式存储结构

带表头结点的循环链表an-1firsta1a0first(空表)(非空表)循环链表的插入template<classType>classCircList;template<classType>classCircListNode{friendclassCircList<Type>;public:CircListNode(Typed=0,CircListNode<Type>*next=NULL)

:data(d),link(next){}//构造函数private:

Typedata; //结点数据

CircListNode<Type>*link;//链接指针}

循环链表类的定义template<classType>classCircList{private:CircListNode<Type>*first,*current,*last;

//链表的表头指针、当前指针和表尾指针public:CircList(Typevalue); ~CircList();

intLength()const; BooleanIsEmpty()

{returnfirst->link==first;

}BooleanFind(constType&value);

TypegetData

()const;

voidFirster(){current=first;} BooleanFirst();

BooleanNext();BooleanPrior(); voidInsert(constType&value);

voidRemove();

};搜索成功搜索不成功循环链表的搜索算法firstfirst3131484815155757搜索15搜索25currentcurrentcurrentcurrentcurrentcurrentcurrentcurrent循环链表的搜索算法template<classType>CircListNode<Type>*CircList<Type>::

Find(Typevalue

){//在链表中从头搜索其数据值为value的结点

CircListNode<Type>*p=first->link;

//检测指针

p

指示第一个结点

while(p!=first&&p->data!=value)

p=p->link;

returnp;}if(first!=NULL){

CircListNode<Type>*second=first->link;first->link=av;av=second;

first=NULL;}利用可利用空间表回收循环链表firstavfirstav回收前回收后if(av==NULL)newnode=newCircListNode<Type>;else{newnode=av;av=av->link;

}从可利用空间表分配结点avnewnodeav分配前的可利用空间表分配后的可利用空间表和新结点约瑟夫问题用循环链表求解约瑟夫问题n个人围成一个圆圈，首先第1个人从1开始一个人一个人顺时针报数,报到第m个人，令其出列。然后再从下一个人开始，从1顺时针报数，报到第m个人，再令其出列，…，如此下去,直到圆圈中只剩一个人为止。此人即为优胜者。例如n=8m=3约瑟夫问题的解法#include<iostream.h>#include“CircList.h”voidJosephus(intn,intm){for(inti=0;i<n-1;i++){//执行n-1次

for(intj=0;j<m-1;j++)Next();

//数m-1个人

cout<<“Deleteperson”<<getData()<<endl;Remove();//删去

}}voidmain(){CircList<int>clist; intn,m; cout<<“EntertheNumberofContestants?”;cin>>n>>m;for(inti=1;i<=n;i++)clist.insert(i);//形成约瑟夫环

clist.Josephus(n,m);//解决约瑟夫问题}多项式(Polynomial)n阶多项式Pn(x)有n+1项。

系数a0,a1,a2,…,an

指数0,1,2,…,n。按升幂排列classPolynomial{public:Polynomial();//构造函数

intoperator!();//判是否零多项式

floatCoef(inte);

intLeadExp();//返回最大指数

Polynomial

Add(Polynomial

poly);PolynomialMult(Polynomialpoly);

floatEval(floatx); //求值}多项式(Polynomial)的抽象数据类型

#include<iostream.h>classpower{

doublex;

inte;

doublemul;

public:

power(doubleval,intexp);

//构造函数

doubleget_power(){returnmul;}

//取幂值

};创建power类，计算x的幂

power::power(doubleval,intexp){

//按val值计算乘幂

x=val;e=exp;mul=1.0;

if(exp==0)return;

for(;e