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

DataStructureandAlgorithmdesign|analyze|experiment|implement数据结构与算法第二章线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4双链表2.5循环链表2.6线性表实现方法的比较*2.7算法拓展[408真题]*2.8STL应用*2.9

你怎么看？目录CONTENTS线性表的概念线性结构的特点是数据元素之间的逻辑关系是线性关系。线性结构是数据元素间约束力最强的一种数据结构：在非空线性结构的有限集合中，存在唯一一个被称为“第一个”的数据元素；存在唯一一个被称为“最后一个”的数据元素；除“第一个”元素无前驱外，集合中的每个元素均有且只有一个“直接”前驱；除“最后一个”元素无后继外，集合中每个数据元素均有且只有一个“直接”后继。

线性表的概念

线性表的概念线性表的概念抽象数据类型定义template<classT>classList{public:virtualvoidclear()=0; //清空线性表

virtualboolempty()const=0; //判空virtualintsize()const=0; //求线性表的长度

virtualvoidinsert(inti,constT&value)=0; //插入元素valuevirtualvoidremove(inti)=0; //删除位序为i[0..n-1]的元素

virtualintsearch(constT&value)const=0; //查找值为value的元素virtualTvisit(inti)const=0; //查找位序为i的元素并返回其值

virtualvoidtraverse()const=0; //遍历线性表

virtualvoidinverse()=0; //逆置线性表

virtual~List(){};};2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4双链表2.5循环链表2.6线性表实现方法的比较*2.7算法拓展[408真题]*2.8STL应用*2.9

你怎么看？目录CONTENTS………………

……线性表的存储结构顺序表单链表双链表循环链表在程序设计语言中，一块连续的存储空间可以用一个数组实现。由于线性表中的元素个数是动态的，因此采用了动态数组。保存一个动态数组，需要三个变量：指向线性表元素类型的指针，数组规模（容量），数组中的元素个数（表长）。线性表的顺序存储线性表的顺序存储线性表的顺序表示:线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称为顺序表。设a0的存储地址为Loc(a0)，每个数据元素占L个存储单元，则编号为i个的数据元素的地址为：

Loc(ai)=Loc(a0)+i*L（1≤i≤n）01i-2i-1in-1MAXSIZE-1a0a1…ai-1…an…

dataai-2ai+1顺序表的类型定义template<classelemType> //elemType为顺序表存储的元素类型classseqList:publicList<elemType>{private:elemType*data; //利用动态数组存储数据元素

intcurLength; //当前顺序表中存储的元素个数

intmaxSize; //顺序表的最大长度

voidresize(); //表满时扩大表空间public:seqList(intinitSize=10); //构造函数

seqList(seqList&sl); //拷贝构造函数

~seqList(){delete[]data;} //析构函数voidclear(){curLength=0;} //清空表，只需置curLength为0boolempty()const{returncurLength==0;}//判空

intsize()const{returncurLength;}//返回顺序表中当前存储元素的个数

voidtraverse()const; //遍历顺序表

voidinverse(); //逆置顺序表

voidinsert(inti,constelemType&value); //在位序i上插入值为value的元素voidremove(inti); //删除位序i上的元素intsearch(constelemType&value)const;//查找值为value的元素第一次出现的位序

elemTypevisit(inti)const;

//访问位序为i的元素的值，“位序0”表示第一个元素};顺序表的类型定义说明1.在插入insert(inti,constelemType&value)、remove(inti)、查找search(constelemType&value)等运算中涉及到的参数i指的是元素在线性表中的位序（即下标）。假定线性表有n个元素，那么数组下标从0到n-1。2.在顺序表中“求线性表长度”、“判空”、“清空”“取位序为i(0≤i≤curLen-1)的元素”等操作是非常简单的，算法的时间复杂度都是O(1)。顺序表上基本运算的实现1．构造函数[代码2.1]构建一个空顺序表template<classelemType>seqList<elemType>::seqList(intinitSize=100){if(initSize<=0)throwbadSize();maxSize=initSize; data=newelemType[maxSize]; curLength=0; }时间复杂度为O(1)2．拷贝构造函数[代码2.2]在构造函数里动态分配了内存资源，这时需要用户自定义拷贝构造函数进行深拷贝。template<classelemType>seqList<elemType>::seqList(seqList&sl){maxSize=sl.maxSize; curLength=sl.curLength; data=newelemType[maxSize]; for(inti=0;i<curLength;++i)data[i]=sl.data[i]; }时间复杂度为O(n)顺序表上基本运算的实现3．遍历顺序表[代码2.3]template<classelemType>voidseqList<elemType>::traverse()const{if(empty())cout<<"isempty"<<endl; //空表

else{cout<<"outputelement:\n";for(inti=0;i<curLength;i++) //依次访问顺序表中所有元素

cout<<data[i]<<"";cout<<endl; } }时间复杂度为O(n)顺序表上基本运算的实现4．查找值为value的元素算法思想：遍历线性表，将线性表中每一个元素依次与value进行比较。若value==data[i](0<=i<curLength)则查找成功，返回data[i]的位序i，否则查找失败返回-1[代码2.4]template<classelemType>intseqList<elemType>::search(constelemType&value)const{for(inti=0;i<curLength;i++)if(value==data[i])returni;return-1; //查找失败返回-1}时间复杂度为O(n)顺序表上基本运算的实现5．求前驱和后继算法思想：求顺序表中位序为i的元素的前驱和后继，若i==0，则为第一个元素无前驱，否则其前驱是data[i-1]；若i==curLength-1，则为最后一个元素无后继，否则其后继是data[i+1]。通过元素的下标可以直接定位其前驱和后继，算法的时间复杂度为O(1)。顺序表上基本运算的实现

顺序表上基本运算的实现cur

a0a1a2

a0a1a2

cura4a3a5Xa5Xa4a3顺序表上基本运算的实现[代码2.5]插入运算template<classelemType>voidseqList<elemType>::insert(inti,constelemType&value){if(i<0||i>curLength)throwoutOfRange(); //合法的插入位置为[0..curLength]if(curLength==maxSize)resize(); //表满，扩大//下标j-1在[curLength-1..i]范围的元素往后移动一步for(intj=curLength;j>i;j--)data[j]=data[j-1];

data[i]=value; //将value置入位序为i的位置++curLength; //表的实际长度增1}时间复杂度为O(n)顺序表上基本运算的实现注意：

(1)检验插入位置的有效性，这里i的有效范围是：0≤i≤curLength，注意：在表尾元素data[curLength-1]的后面插入元素成为新的表尾是合法的。(2)检查表空间是否满了，在表满的情况下不能再做插入，否则产生溢出错误。此时有两种解决方法：一种是不执行插入，报错后退出；另一种是扩大数组的容量。本书采用第二种方法。(3)注意数据的移动方向，最先移动的是表尾元素。顺序表上基本运算的实现插入算法的时间复杂度分析

顺序表上基本运算的实现cura0a1a2

a0a1a2

cura4a3a5a6a4a3a5a6顺序表上基本运算的实现[代码2.6]删除运算template<classelemType>voidseqList<elemType>::remove(inti){//合法的删除位置为[0..curLength-1]if(i<0||i>curLength-1) throwoutOfRange(); //[i+1..curLength-1]范围的元素往前移动一步for(intj=i;j<curLength-1;j++) data[j]=data[j+1]; --curLength; //表的实际长度减1}时间复杂度为O(n)顺序表上基本运算的实现

顺序表上基本运算的实现删除算法时间复杂度分析

顺序表上基本运算的实现[代码2.7]逆置template<classelemType>voidseqList<elemType>::inverse(){elemTypetmp;for(inti=0;i<curLength/2;i++){//控制交换的次数tmp=data[i];data[i]=data[curLength-i-1];data[curLength-i-1]=tmp;}}时间复杂度为O(n)顺序表上基本运算的实现9．扩大表空间由于数组空间在内存中必须是连续的，因此，扩大数组空间的操作须重新申请一个更大规模的新数组，将原有数组的内容拷贝到新数组中，释放原有数组空间，将新数组作为线性表的存储区。顺序表上基本运算的实现[代码2.8]扩大表空间template<classelemType>voidseqList<elemType>::resize(){elemType*p=data; //p指向原顺序表空间maxSize*=2; //表空间扩大2倍data=newelemType[maxSize]; //data指向新的表空间for(inti=0;i<curLength;++i) data[i]=p[i]; //复制元素delete[]p;}时间复杂度为O(n)顺序表上基本运算的实现*10．合并顺序表顺序表A与B的结点关键字为整数，A表与B表的元素均非递减有序，试给出一种高效的算法，将B表中元素合并到A表中，使新的A表的元素仍保持非递减有序，高效指最大限度的避免移动元素。顺序表上基本运算的实现[代码2.9]合并顺序表，本例用类的成员函数实现template<classelemType>boolseqList<elemType>::Union(seqList<elemType>&B){ intm,n,k,i,j;m=this->curLength; //当前对象为线性表An=B.curLength; //m，n分别为线性表A和B的长度k=m+n-1; //k为结果线性表的工作指针（下标）i=m-1,j=n-1; //i，j分别为线性表A和B的工作指针（下标）while(m+n>this->maxSize){ //判断A表空间是否足够大resize(); //空间不够，扩大表空间}while(i>=0&&j>=0) //合并顺序表，直到一个表为空if(data[i]>=B.data[j])data[k--]=data[i--];elsedata[k--]=B.data[j--]; //默认当前对象while(j>=0) //将B表的剩余元素复制到A表data[k--]=B.data[j--];curLength=m+n; //修改A表长度returntrue;}时间复杂度为O(m+n)顺序表上基本运算的实现顺序表的特点(1)顺序表需要预先分配存储空间，很难恰当预留空间，分配大了造成浪费，分配小了对有些运算会造成溢出。(2)由于逻辑次序和物理次序的一致性，顺序表能够按元素序号（下标）直接存取元素具有随机存取的优点；(3)由于要保持逻辑次序和物理次序的一致性，顺序表在插入删除时需要移动大量的数据，因此顺序表的插入和删除效率低；(4)改变顺序表的大小，需要重新创建一个新的顺序表，把原表里的数据复制到新表，然后释放原表空间。(5)顺序表比较适合静态的、经常做定位访问的线性表。2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4双链表2.5循环链表2.6线性表实现方法的比较*2.7算法拓展[408真题]*2.8STL应用*2.9

你怎么看？目录CONTENTS线性表的链接存储结构将每个结点放在一个独立的存储单元中，结点间的逻辑关系依靠存储单元中附加的指针来给出。结点的存储单元在物理位置上可以相邻，也可以不相邻。单链表双链表循环链表单链表存储结点由两部分组成：

数据字段+指针字段（后继地址）每个结点附加了一个指针字段，如next，该指针指向它的直接后继结点，最后一个结点的next字段为空。nullhead己知表头元素为c的单链表在内存中的存储状态如下表所示。现将f放于1014H处并插入到单链表中，若f在逻辑上位a和e之间，则a，e，f的链接地址”依次是()【2012全国硕士统考408】1010H,1014H,1004H1010H,1004H,1014H1014H,1010H,1004H1014H,1004H,1010HABCD提交地址元素链接地址1000Ha1010H1004Hb100CH1008Hc1000H100CHdNULL1010He1004H1014H

单选题10分首元结点是指链表中存储线性表第一个数据元素的结点,也称为第一元素结点。头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志,表长等信息或者是空的;也可做监视哨。头指针是指向链表中第一个结点（有头结点的指向头结点，无头结点则指向首元结点）的指针。单链表可由一个头指针唯一确定，能够标识一个单链表，也常做链表的名字。头指针头结点首元结点a1单链表的几个概念带头结点的单链表不带头结点的单链表单链表的几个概念若单链表为空不带头结点的空单链表带头结点的空单链表单链表的几个概念头结点的意义头结点的出现，使得在表头位置上进行插入和删除和在其它结点位置上是完全一致的，从而使得插入和删除算法得到简化。

单链表的几个概念如，在没有头结点的单链表中插入和删除

单链表的几个概念单链表结点类型定义单链表结点类型定义template<classelemType> structNode{public:elemTypedata; //数据域Node *next; //指针域

Node(constelemTypevalue,Node*p=NULL){ //两个参数的构造函数data=value;next=p;}Node(Node*p=NULL){ //一个参数的构造函数next=p;}};利用C++的new和delete操作符给对象分配和释放空间

例如：Node<elemType>*p=newNode<elemType>(value,NULL);说明：p的类型为Node<elemType>*型，所以该无名结点可以用指针p间接引用，数据域为(*p).data或p->data，指针域为(*p).next或p->next，如图所示单链表结点类型定义单链表结点类型定义单链表结点类型定义template<classelemType> structNode{public:elemTypedata; //数据域Node *next; //指针域

Node(constelemTypevalue,Node*p=NULL){ //两个参数的构造函数data=value;next=p;}Node(Node*p=NULL){ //一个参数的构造函数next=p;}};public:linkList(); //构造函数

~linkList(); //析构函数

voidclear(); //将单链表清空，使之成为空表

boolempty()const{returnhead->next==NULL;} //判空

intsize()const; //返回单链表的当前实际长度

voidinsert(inti,constelemType&value);//在位序i处插入值为value的结点1voidremove(inti); //删除位序i处的结点intsearch(constelemType&value)const;//查找值为value的结点第一次出现的位序

elemTypevisit(inti)const;//访问位序为i的结点的值，0定位到首元结点

voidtraverse()const; //遍历单链表

voidheadCreate(); //“头插法”创建单链表

voidtailCreate(); //“尾插法”创建单链表

voidinverse(); //逆置单链表

…….};单链表类型定义在上述单链表类型定义中，亦可以加入尾指针tail，指向表尾结点，如图所示。尾指针的加入使得频繁修改表尾结点的值或后继时，无需从头遍历链表。在上述单链表类型定义中，亦可以像顺序表seqList一样设置整型变量curLength用于存储表长，这样在求单链表的表长时，就无需从头到尾遍历单链表了。单链表类型定义1．单链表的初始化[代码2.10]template<classelemType>linkList<elemType>::linkList(){head=newNode(NULL); //创建带有头结点的空表}2．析构函数[代码2.11]template<classelemType>linkList<elemType>::~linkList(){clear(); //清空单链表deletehead; //释放头结点}单链表上基本运算的实现时间复杂度为O(n)时间复杂度为O(1)3．清空单链表：清空单链表的主要操作是将工作指针从头结点一直移动到链表尾，边移动指针边释放结点[代码2.12]template<classelemType>voidlinkList<elemType>::clear(){Node*p,*tmp; //p为工作指针，指向首元结点p=head->next; //引入工作指针是为了防止随意修改头指针while(p!=NULL){ //等效while(p)tmp=p;p=p->next; //指针后移deletetmp; }head->next=NULL; //头结点的指针域置空}时间复杂度为O(n)单链表上基本运算的实现4．求表长:从第一个结点开始，一个结点一个结点的计数，直至链表尾[代码2.13]template<classelemType>intlinkList<elemType>::size()const{//若没有curLengthNode*p=head->next; //需要从头到尾遍历链

intcount=0;while(p){count++;p=p->next;}returncount;}//若单链表中像顺序表一样设置了整型变量curLength用于存储表长，则直接返回template<classelemType>intlinkList<elemType>::size()const{returncurLength; //直接返回curLength}时间复杂度为O(1)时间复杂度为O(n)单链表上基本运算的实现5．遍历链表[代码2.14]template<classelemType> voidlinkList<elemType>::traverse()const{Node*p=head->next; //工作指针p指向首元结点cout<<"traverse:";while(p!=NULL){cout<<p->data<<"";p=p->next; //向后移动指}cout<<endl;}时间复杂度为O(n)单链表上基本运算的实现6．查找位序为i的元素

[代码2.15]template<classelemType> typenamelinkList<elemType>::Node*linkList<elemType>::getPosition(inti)const{if(i<-1)returnNULL; //位序i越界，返回NULLNode*p=head; //工作指针p指向头结点

intcount=0; //计数器初始化

while(count<=i&&p){ //若p为NULL，则查找失败

p=p->next;count++;}returnp; //无论查找成功或失败均返回指针p}时间复杂度为O(n)单链表上基本运算的实现7．查找值为value的元素的位序[代码2.16]template<classelemType> intlinkList<elemType>::search(constelemType&value)const{Node*p=head->next; //工作指针p指向首元结点intcount=0; //首元结点的位序为0while(p!=NULL&&p->data!=value){p=p->next;count++;}if(p==NULL)return-1; //查找失败返回-1，这里-1并非头结点elsereturncount; //查找成功，count为元素的位序}时间复杂度为O(n)单链表上基本运算的实现8．求某个结点的后继算法思想：求值为value的结点的后继，从单链表的第一个结点开始查找，若查找成功，则查看该结点的指针域，若其指针域为空，则说明该结点是尾结点，无后继；否则，结点的指针域指向其后继。若查找失败，则说明单链表中无值为value的结点，更谈不上后继。本算法主要是定位操作。需要指出，求前驱和后继还有另外一种叙述：即求第i个结点的前驱和后继。这等同于求第i-1个结点和第i+1个结点。上面已有算法，这里不再赘述。单链表上基本运算的实现p指向当前结点，pre表示前一个结点(的指针)。在*p前(*pre后)插入元素q的语句序列：

q->next=pre->next; pre->next=q;aknext插入元素示意图：ai-1nextainextpreqp单链表上基本运算的实现9．插入元素：在位序为i的位置插入值为value的新结点q。需要先找到位序为i-1的结点p，让q的指针域指向p原来的后继，然后修改p的后继为q[代码2.17]template<classelemType> voidlinkList<elemType>::insert(inti,constelemType&value){Node*p,*q;if(!(p=getPosition(i-1))) //p是位序为i的结点的前驱

throwoutOfRange(); //插入位置非法，抛出异常

q=newNode(value,p->next);//q指向新结点，隐含q->next=p->nextp->next=q; //q结点插入到p结点的后面}时间复杂度为O(n)单链表上基本运算的实现tail==p?no15202312headptail10yes15202312headptail10tailcurcur注意：若单链表带尾指针tail，p是插入位置cur的前驱则在表尾插入新结点，需修改尾指针tail单链表上基本运算的实现插入元素示意图：单链表上基本运算的实现删除元素10．删除元素：删除位序为i的结点[代码2.18]template<classelemType> voidlinkList<elemType>::remove(inti){Node*p,*pre=getPosition(i-1);;//pre是待删除结点的前驱

if(pre==NULL||pre->next==NULL)throwoutOfRange(); //删除位置非法，抛出异常

p=pre->next; //p是待删结点

pre->next=p->next; //修改指针

deletep; //释放结点}时间复杂度为O(n)单链表上基本运算的实现单链表带头结点，pre是删除位置p的前驱注意：若在表尾删除结点，需修改尾指针tailtail==p?no15202312headpretailyes15202312headpretail10tailpp单链表上基本运算的实现删除元素11．头插法创建单链表头插法是在链表的头部插入结点建立单链表，也就是每次将新增结点插入在头结点之后，首元结点之前。读入数据的顺序1,2,3,4,5与单链表中元素的顺序是相反的单链表上基本运算的实现头插法可用于逆置链表[代码2.19]头插法创建单链表template<classelemType> voidlinkList<elemType>::headCreate(){//头插法创建单链表Node*p;elemTypevalue,flag;cout<<"inputanendmark:";cin>>flag; //输入结束标志

cout<<"inputelements,endedwith:"<<flag;while(cin>>value&&value!=flag){p=newNode(value,head->next);//隐含p->next=head->next

//置结点p的后继为头结点原来的后继

head->next=p; //将结点p插入到头结点的后面

}}时间复杂度为O(n)单链表上基本运算的实现12．尾插法创建单链表尾插法是指在单链表的尾部依次插入新增结点来建立单链表，因此需要设置尾指针tail。读入数据的顺序1,2,3,4,5与单链表中元素顺序相同。单链表上基本运算的实现[代码2.20]尾插法创建单链表template<classelemType> voidlinkList<elemType>::tailCreate(){//尾插法创建链表Node*p,*tail=head;elemTypevalue,flag;cout<<"inputanendmark:";cin>>flag; //输入结束标志

cout<<"inputelements,endedwith:“<<flag;while(cin>>value&&value!=flag){p=newNode(value,NULL);tail->next=p; //将结点p插入到尾结点的后面

tail=p; //结点p成为新的表尾

}}时间复杂度为O(n)单链表上基本运算的实现13．逆置单链表：用工作指针p依次访问链表中的每个结点，每访问一个结点，将它插入到头结点的后面（头插法）。[代码2.21]template<classelemType>voidlinkList<elemType>::inverse(){//头插法逆置Node*p,*tmp;p=head->next; //p为工作指针指向首元结点head->next=NULL; //头结点的指针域置空，构成空链表while(p){tmp=p->next; //暂存p的后继p->next=head->next;

head->next=p; //结点p插入到头结点的后面

p=tmp; //继续处理下一个结点}}时间复杂度为O(n)单链表上基本运算的实现*15．合并链表将非递减有序的单链表la和lb合并成新的非递减有序单链表lc，要求利用原表空间。算法思想：因为新创建的单链表lc仍然是非递减有序的，所以用尾插法创建lc表。[代码2.24]本例用类的成员函数实现，la表为this指针所指向的当前链表template<classelemType>typenamelinkList<elemType>*linkList<elemType>::Union(linkList<elemType>*lb){Node*pa,*pb,*pc; //分别是链表la、lb、lc的工作指针linkList<elemType>*lc=this; //lc表利用la表空间pa=head->next;head->next=NULL; //la表构成空链表pb=(lb->head)->next;(lb->head)->next=NULL; //lb表构成空链表pc=lc->head; //lc表直接利用la表头结点单链表上基本运算的实现while(pa&&pb){ //la和lb均非空

if(pa->data<=pb->data){ //pa所指结点用尾插法插入lc中

pc->next=pa;pc=pa;pa=pa->next;}else{ //pb所指结点用尾插法插入lc中

pc->next=pb;pc=pb;pb=pb->next;}}if(pa)pc->next=pa; //若pa未到表尾，则将pc指向paelsepc->next=pb; //若pb未到表尾，则将pc指向pbdeletelb; returnlc;}单链表上基本运算的实现总结链表的特点：(1)不要求用地址连续的存储空间存储，每个结点在运行时动态生成。结点的存储空间在物理位置上可以相邻，也可以不相邻；(2)插入和删除操作不需要移动元素，只需修改指针，满足经常插入和删除结点的需求；(3)链表不具备顺序表随机存取的优点；(4)链表结点增加了指示元素间关系的指针域，空间开销比较大。单链表上运算的分析1.对一个结点操作，必先找到它，即用一个指针指向它2.找单链表中任一结点，都必须从第一个点开始：

p=head;或p=head->next;while(没有到达) p=p->next;单链表的时间复杂度查找：O(n)插入：O(n)+O(1)=O(n)删除：O(n)+O(1)=O(n)总结2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4双链表2.5循环链表2.6线性表实现方法的比较*2.7算法拓展[408真题]*2.8STL应用*2.9

你怎么看？目录CONTENTS双链表如果某链表经常进行查找结点前驱的操作，我们希望查找前驱的时间复杂度也达到O(1)，这时可以用空间换时间：即每个结点再增加一个指向前驱的指针域prior，使链表可以进行双向查找，这种链表称为双向链表。每个结点附加了两个指针字段，如prior和nextprior字段给出直接前驱结点的地址next给出直接后继结点的地址。为了消除在表头、表尾插入删除的特殊情况，通常双链表设一头结点，设一尾结点头结点中prior字段为空，它的next字段给出线性表中的首结点的地址尾结点中next字段为空，它的prior字段给出线性表中最后一个节点的地址双链表深刻理解双向链表

设：双链表p;则：

p->prior->next==?;P->next->prior==?;即：

p->prior->next==p->next->prior==p;Create运算创建一个双链表就是创建一个只有头尾结点的链表，把头结点的地址保存在head中，尾结点的地址保存在tail中head∧tail∧双链表插入运算s->prior=p->prior; //①p原先的前驱成为s的前驱p->prior->next=s; //②s成为p原先的前驱的后继

s->next=p;//③s的后继是pp->prior=s;//④修改p的前驱为ss双链表

ki-1

ki

ki+1

p

p

prior

pnextp

priornext=p

next;pnextprior=p

prior;priornextdeletep;删除运算双链表己知一个带有表头结点的双向循环链表L，结点结构为（prev，data，next），其中prev和next分别是指向其直接前驱和直接后继结点的指针。现要删除指针p所指的结点，正确的语句序列是()。p->next->prev=p->prev;p->prev->next=p->prev;free(p);p->next->prev=p->next;p->prev->next=p->next;free(p);p->next->prev=p->next;p->prev->next=p->prev;free(p);p->next->prev=p->prev;p->prev->next=p->next;free(p);ABCD提交【2016年全国硕士研究生入学统一考试计算机学科专业基础综合】单选题10分2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4双链表2.5循环链表2.6线性表实现方法的比较*2.7算法拓展[408真题]*2.8STL应用*2.9

你怎么看？目录CONTENTS单循环链表通常单循环链表不带头结点，且往往只设尾指针，如下图所示，用一个指向尾结点的尾指针来标识单循环链表，好处是既方便查找表尾结点又方便查找首元结点tail双循环链表头结点中prior字段给出尾结点的地址，尾结点中next字段给出头结点的地址一般也不设头尾结点例2.2将两个用尾指针标识的带头结点的单循环链表T1和T2连接成一个单循环链表。例题p=T1->next; //p指向T1的头结点T1->next=T2->next->next;//T1表尾结点的指针域指向T2的首元结点deleteT2->next; //释放T2表的头结点T2->next=p; //T2表尾结点的指针域指向T1的头结点例题已知头指针h指向一个带头结点的非空单循环链表，结点结构为（data,next），其中next是指向直接后继结点的指针，p是尾指针，q是临时指针。现要删除该链表的第一个元素，正确的语句序列是（

）。【2021年全国统考408】h->next=h->next->next;q=h->next;free(q);q=h->next;h->next=h->next->next;free(q);q=h->next;h->next=q->next;if(p!=q)p=h;free(q);q=h->next;h->next=q->next;if(p==q)p=h;free(q);ABCD提交单选题10分算法举例假设一个单循环链表，其结点含有三个域pre、data、next。其中data为数据域；pre为指针域，它的值为空指针（null）；next为指针域，它指向后继结点。请设计算法，将此表改成双向循环链表。voidSToDouble（LinkedListla）{ while（la->next->pre==null）

{ la->next->pre=la; la=la->next；//la指针后移

}}//算法结束2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4双链表2.5循环链表2.6线性表实现方法的比较*2.7算法拓展*2.8STL应用*2.9

你怎么看？目录CONTENTS总结1.顺序表的主要优点(1)顺序表的实现方法简单，各种高级语言中都有数组类型，容易实现；(2)按序号查找可通过下标直接定位，时间代价O(1)；(3)元素间的逻辑次序和物理存储次序一致，不需要借助指针，不产生结构性存储开销；(4)顺序表是存储静态数据的理想选择。2.顺序表的主要缺点(1)需要预先申请固定长度的数组；(2)插入删除运算需要移动大量的元素，时间代价O(n)总结3.链表的主要优点(1)插入删除运算不需要移动元素，只需修改指针的指向，时间代价O(n)；若不考虑查找，则插入删除运算时间代价O(1)，链表比较适合经常插入删除元素的情况；(2)动态地按照需要为表中新的元素分配存储空间，无需事先了解线性表的长度，对线性表的长度难以估计时，采用链表比较合适；(3)链表是存储动态变化数据的理想选择。4.链表的主要缺点(1)链表需要在每一个结点上附加指针，用以体现元素间的逻辑关系，增加了结构性的存储开销。(2)按序号查找元素需要遍历链表，时间代价O(n)2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4双链表2.5循环链表2.6线性表实现方法的比较*2.7算法拓展*2.8STL应用*2.9

你怎么看？目录CONTENTS算法举例1：删除所有值为item的元素已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为0(n)、空间复杂度为0(1)的算法，该算法删除线性表中所有值为item的数据元素。O(1)表示算法的辅助空间为常量。

【北京航空航天大学】算法思想算法拓展

template<classT>

//顺序表的元素类型为TvoidarrList<T>::DelAll(Titem)//A是顺序存储的线性表，本算法删除A中所有值为item的元素{

inti=0,j=curLen-1; //设置数组低、高端指针（下标）

while(i<=j)

{

while(i<=j&&aList[i]!=item)i++;//若值不为item，右移指针

while(i<=j&&aList[j]==item)j--;//若值为item，指针左移

if(i<j)aList[i++]=aList[j--];

}

curLen=i;}算法拓展

若题目要求元素间相对顺序不变，可用如下语句段：

i=0；j=0；

while（j<n）

if(aList[j]==item）j++；elseA[i++]=A[j++]；最后线性表中的元素个数是i。

算法拓展

算法思想算法拓展

算法举例2：循环左移42、（13分）设将n（n>1）个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法，将R中保存的序列循环左移P（0<P<n）个位置，即将R中的数据由（X0,X1,…,Xn-1）变换为（Xp,Xp+1,…,Xn-1,X0,X1,…,Xp-1）。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度和空间复杂度。

【2010年全国硕士研究生入学统一考试计算机学科专业基础综合】算法设计思想：按照下标0到p-1、p到n-1、0到n-1的顺序，将这三段分别逆置，最后的结果即为所求。算法拓展

(2)voidleftshift(intR[],intp,intn)//将有n个元素的一维数组R的序列循环左移p(0<p<n)个位置{elemtypet; //t和数组R中的元素具有相同类型

for(i=0;i<p/2;i++)//逆置0..p-1段

{t=R[i];R[i]=R[p-1-i];R[p-1-i]=t;}for(i=p;i<(n+p)/2;i++)

//逆置p..n-1段

{t=R[i];R[i]=R[n-1-i+p];R[n-1-i+p]=t;}for(i=0;i<n/2;i++) //逆置0..n-1段，即整个数组逆置

{t=R[i];R[i]=R[n-1-i];R[n-1-i]=t;}}//算法初始调用:leftshift(R,p,n)，各参数意义如上。算法拓展

算法拓展

(3)算法执行了两趟逆置，时间复杂度为O(n);用了一个辅助变量空间，空间复杂度为O(1)。讨论：若采用直接左移p位，空间复杂度仍为O(1)，但时间复杂度为O(np)。算法举例3：找未出现的最小正整数41.（13分）给定一个含n(n≥1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5,3,2,3}中未出现的最小正整数是1；数组{1,2,3}中未出现的最小正整数是4。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度和空间复杂度。【2018年全国硕士研究生入学统一考试计算机学科专业基础综合】算法拓展

算法思想：由于数组中有n个整数，则未出现的最小的正整数一定在1到n+1的范围，假如：数组a为[1,2,3,4]，则最小正整数为5，也就是n+1,如果数组中介于1到n之间的正整数个数不足n个，则未出现的最小的正整数的范围是1到n。设置一个辅助数组b,大小为n+2,初始值全部为0，然后对a[i]进行遍历，如果0<a[i]<=n+1，则将b[a[i]]赋值为1，接下来遍历b数组，遇到的第一个满足b[i]==0的就退出，i就是数组a中未出现过的最小正整数算法拓展

intfindMissMin(intA[],intn){int*B=newint[n]; //创建动态数组

memset(B,0,n*sizeof(int)); //赋初值

inti;for(i=0;i<n;++i){ if(A[i]>0&&A[i]<n){//仅处理A中范围在1~n的元素B[A[i]-1]++;}}for(i=0;i<n;++i){if(B[i]==0)break;}delete[]B;returni+1;}(3)算法的时间复杂度为O(n);

空间复杂度为O(n)。算法拓展

算法举例4：取单链表倒数第k个元素42（15分）已知一个带有表头结点的单链表，结点结构为(data,link)，假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数），若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0，要求：⑴描述算法的基本设计思想；⑵描述算法的详细实现步骤；⑶根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C++或JAVA语言实现），关键之处请给出简要注释【2009年全国硕士研究生入学计算机学科专业基础综合试题】算法拓展

算法拓展

intSearchInvK(constintk){//在单链表la上查找倒数第k个结点

p=list->link;//p指向当前待处理元素

q=list;//若成功,q指向倒数第k个元素

i=1;

while(p&&i<k){i++;p=p->link;} if(p==null){cout<<“不存在\n”;return0;} while(p){q=q->link;p=p->link;}

cout<<“倒数第k个元素的data域：”<<q->data<<endl; return1;}//SearchInvK算法举例5：共同后缀42.（13分）假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading”和“being”的存储映像如下图所示。设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为（data，netxt），请设计一个时间上尽可能高效的算法，找出由str1和str2所指的两个链表共同后缀的起始位置（如图中字符i所在结点的位置p）。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C++或JAVA语音描述算法，关键之处注释。（3）说明你所设计算法的时间复杂度。【2012年全国硕士研究生入学统一考试计算机学科专业基础综合】算法拓展

42.解析（1）找两个单词的共同后缀，应从两个单词的词尾向前找，找到最前边那个相同的字母，就找到了共同后缀。由于本题中单词以单链表存储，若想找到最后字母，需使用栈，这将增大空间复杂度。为不增大空间复杂度，可以先求出两个链表的长度m和n，让两个链表“尾对齐”，即长的链表将指针移到|m-n+1|,短链表的指针指向链表的第一个字母，两个链表进行模式匹配：对应字母比较，从最后遇到两个链表结点值相等，直至到表尾对应结点值都相等为止。要注意处理虽然首次遇到对应结点值相等，但有后续结点值不等的情况,即在匹配中，并非一遇到对应字母相等，就结论后边是共同后缀。算法拓展

（2）求用单链表表示的两个单词的共同后缀的算法typedefstructNode{ ElemTypedata; structNode*next;}LNode,*LinkedList；intListLength(LNode*la){ //求链表la的长度

inti=0;LNode*p=la->next; //p指向链表的第一个元素结点

while(p){i++; //元素个数加1p=p->next; //链表指针后移

}returni; //返回链表的长度}算法拓展

LNode*ComPostfix(LNode*str1,LNode*str2){//str1和str2分别是单词以单链表存储的头指针，本算法返回两个单词共同后缀的起始位置

p=null; //p指向两个链表共同后缀的起始位置

m=ListLength(str1);n=ListLength(str2); //求链表str1和str2的长度

if(m>n){ s=str1->next; //s指向长链表的第一个元素

q=str2->next; //q指向短链表的第一个元素

len=m-n+1; //两个链表开始比较时，长链表应移到的位置}else{ s=str2->next; //s指向长链表的第一个元素

q=srt1->next;//q指向短链表的第一个元素

len=n-m+1;//两个链表比较时，长链表应移到的位置}}算法拓展

i=1;while(i<len){i++;s=s->next;}//尾部对齐while(s){while(s&&s->data!=q->data) { s=s->next;q=q->next;} p=s; //p指向两个链表共同后缀的起始位置

while(s&&s->data==q->data)

{ s=s->next;q=q->next;}}returnp;//返回两个链表共同后缀的起始位置}算法拓展

（3）算法中求了两个链表的长度，接着将长链表的指针移到两链表的比较处，进行对应元素的比较，记住可能共同后缀的开始位置，直到链表尾。总的时间复杂度为O(m+n)。算法拓展

算法举例7:删除重复元素用单链表保存m个整数，节点的结构为(data,link)，且|data|<n(n为正整数)。现要求设计一个时间复杂度尽可能高效地算法，对于链表中绝对值相等的节点，仅保留第一次出现的节点而删除其余绝对值相等的节点。若给定的单链表head如图（a）所示，则删除结点后的head如图（b）所示。【2015年全国硕士研究生入学计算机学科专业基础综合试题】算法拓展

要求(1)给出算法的基本思想(2)使用c或c++语言，给出单链表节点的数据类型定义。(3)根据设计思想，采用c或c++语言描述算法，关键之处给出注释。(4)说明所涉及算法的时间复杂度和空间复杂度。算法拓展

(1)算法思想：定义一个大小为N的数组，初始化为0.在遍历链表的同时将数组中索引值为节点的值的绝对值的元素置1.如果此元素已经为1，说明此节点之前已经有与此节点的值的绝对值相等的节点，需将此节点删除。(2)节点的数据结构定义如下：typedefstructNode{Intdata;StructNode*next;}Node;算法拓展

(3)inta[n];//全局数组标志节点的绝对值的值是否出现过voidDeleteABSEqualNode(Node*head){ memset(a,0,n);//初始化为0

if(head==NULL)returnNULL; Node*p=head; Node*r=head; while(p!=NULL) { if(a[abs(p->data)]==1) //如果此绝对值已经在数组中出现过，则删除 {r->next=p->next;deletep;p=r->next;} else//否则，将数组中对应的元素置1 {a[abs(p->data)]=1;r=p;p=p->next;} } returnhead;}(4)只遍历一次链表，所以时间复杂度为O(m)因为申请大小为n的数组，所以空间复杂度为O(n)，（n为节点绝对值的最大值）。算法拓展

算法举例8:重新排列单链表41. (13分)设线性表L=(a1，a2，a…，an-2，an-1，an。)采用带头结点的单链表保存，链表中结点定义如下：typedefstructnode{intdata；structnode*next；}NODE；请设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表L'=(a1，an，a2，an-1，a3，an-2…)。要