数据结构经典课件

数据结构与算法2009年秋季授课教师：张剑波方芳授课班级：111081-4班115081-2班Chapter3线性表本章教学内容3.2线性表ADT3.3线性表的公式化描述（数组表示）3.4线性表的链表描述3.5线性表的应用-不带表头节点的单链表删除算法（续）（程序3-14）else{

//useqtogettok-1'stChainNode<T>*q=first;for(intindex=1;index<k-1&&q;index++)

q=q->link;

if(!q||!q->link)throwOutOfBounds(

);

//nok'thp=q->link;

//k'thq->link=p->link;

//removefromchain}

//savek'thelementandfreenodep

x=p->data;

deletep;

return*this;}时间复杂度：Θ(k)-不带表头节点的单链表插入算法（程序3-15）template<classT>Chain<T>&Chain<T>::Insert(intk,constT&x){//Insertxafterthek'thelement.//ThrowOutOfBoundsexceptionifnok'thelement.//PassNoMemexceptionifinadequatespace.

if(k<0)throwOutOfBounds();

//pwilleventuallypointtok'thnodeChainNode<T>*p=first;for(intindex=1;index<k&&p;index++)//moveptok'thp=p->link;

if(k>0&&!p)throwOutOfBounds();

//nok'th

-不带表头节点的单链表插入算法（续）（程序3-15）//insert

ChainNode<T>*y=newChainNode<T>;y->data=x;

if(k){//insertafterpy->link=p->link;p->link=y;}

else{//insertasfirstelementy->link=first;first=y;

}return*this;}时间复杂度：Θ(k)template<classT>voidChain<T>::fun(){ if(first==NULL)return;ChainNode<T>*p=first->link,*pr=NULL; while(p!=NULL){

first->link=pr;

pr=first;

first=p;

p=p->link;

}first->link=pr;}阅读算法，说明该算法的功能单链表的原地逆置操作-链表遍历器类（程序3-18）template<classT>classChainIterator{public:T*Initialize(constChain<T>&c){

location=c.first;if(location)

return&location->data;return0;

}T*Next(

){

if(!location)return0;

location=location->link;if(location)

return&location->data;return0;

}private:ChainNode<T>*location;};使用：输出链表int*x;ChainIterator<int>c;x=c.Initialize(X);while(x){cout<<*x<<‘’；x=c.Next();}cout<<endl;Chain的友元类带头节点的空链表firstNULLfirst->link=NULL;带头节点的循环链表abcdefirstfirstfirst->link=first;带表头节点的空循环链表带表头节点的非空循环链表循环链表上的运算与单链表上运算基本一致，区别只在于最后一个节点的判断（即循环的条件不同）；单链表

p!=NULL或p->link!=NULL循环单链表

p!=first或p->link!=first循环单链表的操作(!p||!p->link)-在带头节点的循环单链表中查找（程序3-20）template<classT>intCircularList<T>::Search(constT&x)const{//Locatexinacircularlistwithheadnode.ChainNode<T>*current=first->link;intindex=1;//indexofcurrent

first->data=x;

//putxinheadnode

//searchforxwhile(current->data!=x){current=current->link);index++;}

//areweathead?return((current==first)?0:index);}循环链表的应用实例——求解约瑟夫环问题【约瑟夫环问题】

n

个人围成一个圆圈，首先第1个人从1开始一个人一个人的顺时针报数,报到第m个人，令其出列；然后再从顺时针方向上的下一个人开始重新报数，报到第m个人，再令其出列，

…，如此下去,直到圆圈中只剩一个人为止，此人即为优胜者。例123456设m=3，n=83出列76出列×1出列…3，6，1，5，2，8，4××8××××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{public:

CircList(Typevalue);

~CircList(); Type*getData

()const;//返回当前节点的地址

voidFirster

();//将当前指针置于第一个节点

boolNext();//将当前节点指针指到当前节点的后继节点

voidInsert(constType&value);//插入新节点

voidRemove

(); //删除当前节点

private:

CircListNode<Type>*first,*current,*last;};-带表头节点循环链表类的定义-析构函数template<classType>CircList<Type>::~CircList(){ CircListNode<Type>*p;

while(first->link!=first)

{ p=first->link; first->link=p->link; deletep; } deletefirst;}//析构函数，释放循环链表的存储空间template<classType>voidCircList<Type>::Insert(constType&value){ CircListNode<Type>*newnode=newCircListNode<Type>(value); last->link=newnode; newnode->link=first; last=newnode;}

-向循环链表中插入新节点，直接插在表尾template<classType>Type*CircList<Type>::getData()const{ if(first!=last) return&(current->data); else returnNULL;}-返回当前节点的地址template<classType>boolCircList<Type>::Next(){

if(first==last) {//空表情况，无法指到其后继

current=NULL; returnfalse; } if(current->link!=first) {//不是表尾指针，直接指向其后继节点

current=current->link; returntrue; }

else {//当前节点为表头节点时

current=first; returnNext(); }}-将当前节点指针指到当前节点的后继节点template<classType>voidCircList<Type>::Remove(){ CircListNode<Type>*p=first,*q; if(first==last)return; if(current==NULL) return; while(p->link!=current) //找当前节点的前驱; p=p->link;

//删除当前节点

q=current; p->link=q->link; current=q->link; deleteq; if(current==first) Next();//当前节点为表头节点时，删除其后继节点}

-删除当前节点intmain(){ CircList<int>clist(10); intn,m; cout<<"Enternandm:"; cin>>n>>m; for(inti=1;i<=n;i++) clist.Insert(i); Josphus(clist,n,m);return0；}Enternandm:83Deleteperson:3Deleteperson:6Deleteperson:1Deleteperson:5Deleteperson:2Deleteperson:8Deleteperson:4theresultis:7运行结果如果每次m的值都不一样（假设每个人都有一个密码，每次m的值取这一密码），怎么解决？为节点增加一个数据域，即在节点类中增加一个成员key；用一个结构体表示一个节点的数据域。datakeylink【思考】4、双向链表如果希望能快速找到一个结点的直接前驱，可以在单链表中的结点中增加一个指针域指向它的直接前驱，这样的链表，就称为双向链表(一个结点中含有两个指针)。在单链表中，从某个结点出发可以直接找到它的直接后继，时间复杂度为O(1)，但无法直接找到它的直接前驱；在循环单链表中，从某个结点出发可以直接找到它的直接后继，时间复杂仍为O(1)，直接找到它的直接前驱，时间复杂为O(n)；left（左链指针）data（数据）right（右链指针）

双向链表是指在前驱和后继方向都能遍历的线性链表。双向链表中每个结点的结构前驱方向后继方向双向链表通常采用带表头结点的循环链表形式。a0…an-1first带表头结点的双向循环链表abcdeNULLfirstNodeNULLlastNode在双向链表中可以方便地访问节点的前驱。两个指针域：left，right双向循环链表abcdefirstNode带头节点的双向循环链表abceheaderNodedfirst带头节点的双向循环空链表firstfirst->left=first;first->right=first;ABCp->left：Ap->right：Cpp->left->right：Bp->right->left：Bp==p->left->right==p->right->left

p既被它的前驱结点的右指针所指，又被它的后继结点的左指针所指。双向链表的重要特征思考：双向链表的插入、删除操作ABC××××AvaluesC××①③②

④pp②

④①s->left=p->left;②s->left->right=s;③s->right=p;④p->left=s;在p之前插入一个节点删除p所指示的节点①p->left->right=p->right;②p->right->left=p->left;①②

5、提示1：注意指针变量的有效性记得使用new使用新指针变量，或要生成一个新节点前先执行new操作不要引用NULL指针使用指针前，先用if语句（或while循环条件中的语句）判断它非空不能引用Delete了的指针提示2：注意链表的边界处理几个特殊点的处理头指针处理非循环链表尾节点的指针域保持为NULL循环链表尾节点的指针回指头节点链表处理空链表的特殊处理插入或删除节点时指针勾链的顺序指针移动的正确性插入查找或遍历6、链表vs.数组描述方法操作查找第k个元素删除第k个元素在第k个元素后插入公式化描述（顺序表）(1)(n-k)s(n-k)s链表描述（链表）(k)k(k+s)链表vs.数组：线性表实现方法比较顺序表的主要优点没有使用指针，不用花费附加开销链表需要额外空间来存放指针；线性表元素的访问非常简洁便利采用公式化描述，可在常数时间内访问第k个元素；而在链表中，需要的时间为O(k)。链表的主要优点无需事先了解线性表的长度允许线性表的长度有很大变化能够适应经常插入删除内部元素的情况链表中的插入和删除操作不需要移动数据，所以更快链表vs.数组：应用场合的选择不要使用顺序表的场合经常插入删除时，不宜使用顺序表；线性表的最大长度也是一个重要因素。不要使用链表的场合当存取操作比插入删除操作频率大时，不应选择链表；当指针的存储开销和整个节点内容所占空间相比其比例较大时，应该慎重选择。1、2000年华中科技大学考研题：【填空题】设单链表的节点结构为（data,next)，next为指针域。已知指针px指向单链表中data为x的节点，指针py指向data为y的节点，若将y插入节点x之后，则需执行以下语句：

px->next=py;课堂练习

2、2000武汉大学考研题：【选择题】非空循环链表head的尾节点p满足：

A、p->link=headB、p->link=NULLC、p=NULLD、p=head3、1999上海交大考研题：

【算法设计】假设有两个按元素递减有序排列的线性表A和B，均以单链表作存储结构。请编写算法，将表A和表B归并成一个按元素值非递增有序（允许值相同）排列的线性表C，并要求利用原表（即表A和表B）的节点空间存放表C。A课堂练习4、设双向循环链表中结点的结构为（data，lLink，rLink），且不带表头结点。若想在指针p所指结点之后插入指针s所指结点，则应执行下列哪一个操作

。A、p->rLink=s;s->lLink=p;p->lLink->lLink=s;s->rLink=p->rLink;B、p->rLink=s;p->rLink->lLink=s;s->lLink=p;s->rLink=p->rLink;C、s->lLink=p;s->rLink=p->rLink;p->rLink=s;p->rLink->lLink=s;D、s->lLink=p;s->rLink=p->rLink;p->rLink->lLink=s;p->rLink=s;D课堂练习5、算法填空：判断一个带表头结点的双向循环链表DL是否对称相等的算法如下所示，请在算法的

处填入正确的语句。intsymmertry(DbList&DL){

intsym=1;DblNode*p=DL->rLink;*q=DL->lLink;while((p!=q)||p->lLink==q)&&(1)){ if(p->data==q->data) {

(2);

(3); } elsesym=0;}return0;}sym==1p=p->rLinkq=q->lLink;课堂练习4种描述方法的比较【课后作业三】编码实现：Page97【练习32】【练习34】单链表的合并、拆分可使用教材上的Chain类，也可以自定义单链表类写测试程序测试算法的正确性10月11日前发至：fangfangcug@126.com

邮件名称：11108X-XX-单链表合并、拆分知识拓展-STL中的vector和listSTL简介StandardTemplateLibrary(STL)：标准模板库，更准确的说是C++程序设计语言标准模板库。STL是所有C++编译器和所有操作系统平台都支持的一种库，说它是一种库是因为，虽然STL是一种标准，也就是说对所有的编译器来说，提供给C++程序设计者的接口都是一样的。——同一段STL代码在不同编译器和操作系统平台上运行的结果都是相同的，但是底层实现可以是不同的。STL的使用者并不需要了解它的底层实现。STL的目的是标准化组件，不用重新开发，可以仅仅使用这些现成的组件。STL现在是C++的一部分，因此不用额外安装什么，它被内建在编译器之内。STL的组成STL的三大核心部分：容器（Container）算法（Algorithms）迭代器（Iterator）容器适配器（containeradaptor）函数对象（functor）STL其他标准组件。容器-算法-迭代器容器：装东西的东西，装水的杯子，装咸水的大海，装人的教室……STL里的容器是可容纳一些数据的模板类。算法：往杯子里倒水，往大海里排污，从教室里撵人……STL里的算法，就是处理容器里面数据的方法、操作。迭代器：往杯子里倒水的水壶，排污的管道，撵人的那个物业管理人员……STL里的迭代器：遍历容器中数据的对象。对存储于容器中的数据进行处理时，迭代器能从一个成员移向另一个成员。它能按预先定义的顺序在某些容器中的成员间移动。对普通的一维数组、向量、双端队列和列表来说，迭代器是一种指针。容器STL中的容器有队列容器（Sequencecontainers）每个元素都有固定位置－－取决于插入时机和地点，和元素值无关。vector、deque、list关联容器（Associatedcontainers）元素位置取决于特定的排序准则，和插入顺序无关set、multiset、map、multimap容器适配器（containeradapters：stack，queue，priorityqueue）位集（bit_set）串包(string_package)