链式存储的表堆栈和队列

一、链表—表的链式存储顺序表的特点：

逻辑上关系上相邻的两个元素在物理位置上也相邻。

优点：

可以随即存取元素缺点：在插入删除操作时，需要移动大量元素。

链式存储结构链式存储结构是计算机中另外一种最基本的数据存储结构。链式存储结构初始时为空链，当有新的数据元素需要存储时用户向系统动态申请所需要的存储空间，然后插入链中。也样，存储空间不一定连续，为了表示每个元素ai和其后继元素ai＋1的逻辑关系，对ai来说，不但要存储ai本身的数据信息，还必须存储一个直接指示其后继的信息（后继的存储地址），这两部分组成ai的存储映象，叫做结点。其中存储数据元素信息的域叫做数据域，存储直接后继存储位置的域叫做指针域。线性表如下：(ZHAO，QIAN，SUN,LI,ZHOU,WU,ZHENG,WANG)

存储地址数据域指针域1 LI 437 QIAN 1313SUN1头指针19WANG NULL3125WU 3731ZHAO 737 ZHENG 1943ZHOU 25头指针指示链表中第一个结点的存储位置。一般把链表画成箭头相链的结点的序列，如：WUZHOUZHENGWANGLISUNQIANZHAOHead数据域，存储数据信息指针域，存储下一个元素的地址template<classT>单链表的删除（带头结点的情况）default:cin.有n个人围成一个圆圈，任意给出一总结：带头结点的链表可以方便（统一）结点的插入操作使用的数据结构有哪些？elsepower=power*d;node<T>*next;递归定义a)逆位序输入n个元素的值，建立带头节点的单链表L；s->next=p->next;阅读下面算法，用适当的语句完成各下划线的处理，使其能实现删除链表中voiddelete(L,x)的逻辑关系，对ai来说，不但要存储ai本身的数据信息，还必1）单链表

A)定义以及相关概念

链表中每个结点中只包含一个指针域，这样的链表叫做单链表。链表为空的标志：head==NULL（1）单链表headhead（2）带头节点的单链表有时，为了操作方便，我们在单链表的第一个节点之前附设一个节点，称为头节点。头节点的数据域可以不存储任何信息，也可以存放如线性表的长度等附加信息。a1a2...LL链表为空：L->next=NULL分析问题：数据成员：数据信息，指针信息函数成员：构造函数，析构函数数据元素不确定，所以应该使用类模板datanextA)链表（表的链式存储）的实现1）节点类的定义和实现实现template<calssT>classnode;{private:node<T>*next;递归定义Public:Tdata;node(Ta，node<T>*next=Null);~node(){};voidprint();};datanext

template<classT>node<T>::node(Ta，node<T>*ptrnext){next=ptrnext;data＝a;}2）节点类的具体实现voidmain(){node<int>*p; p=newnode<int>(20,NULL); p->print();}template<classT>voidnode<T>::print(){cout<<data<<endl; cout<<next<<endl;}3）单链表类的定义分析数据成员：头指针，单链表元素个数，当前指针函数成员：…见P68a)逆位序输入n个元素的值，建立带头节点的单链表L；

3）建立链表template<classT>list<T>::list(intx){inti;head=newnode<T>(x,NULL);for(i=x;i>0;--i){p=newnode<T>;p->next=head->next;head->next=p;}}

1）单链表的插入，删除a在第一个位置上的操作abaxppsbheadheads->next=p;head=s;B)链表的几个重要操作分析s->next=p;p->next=s;b）在普通位置上的插入操作ababpscheadheadcxs->next=p->next;p->next=s;abheadcpc）在链表尾端的插入操作xsp->next=s;s->next=p;p->next=s;链表如果带头结点呢？sxapbheads->next=p->next;p->next=s;总结：带头结点的链表可以方便（统一）结点的插入操作bacp（A）删除操作（一般情况）s->next=p->nextdelete(p);2）单链表删除（不带头结点的单链表）heads（B）特殊情况head=p->nextp->next=NULLdelete(p)bacphead单链表的删除（带头结点的情况）abheadpss->next=p->nextdeletepps3）单链表类的定义分析数据成员：头指针，单链表元素个数，当前指针函数成员：…见P68template<classT>classlist{private:node<T>*head; intsize; node<T>*p,*q; public:list(void); list(intx); ~list(){} intlistsize(void)const; intisempty(void)const;

node<T>*index(intpos); voidinsert(constT&item,Tx); Tdelet(intpos); voidclear(void); voidprint();};单链表的操作都是从头指针开始的。单链表的删除（带头结点的情况）a在第一个位置上的操作（A）删除操作（一般情况）l1->next=s;用基数排序的思想对穿孔卡片进行排序的。p->next=head->next;inti,j,k,power=1;双向链表的节点有两个指针域，一个指向直接后继，一个指insert(a[j]);~node(){};p=newnode<int>(20,NULL);1)将两个链表合并成一个链表。result=Getdata(operand1,operand2);{private:node<T>*head;head=newnode();voidClear(void);p=newnode<int>(20,NULL);template<classT>list<T>::list(intx){inti; head=newnode<T>(x,NULL);for(i=x;i>0;--i) {p=newnode<T>;p->next=head->next;head->next=p;}}

template<classT>voidlist<T>::print()//输出链表中节点的数据域{cout<<"链表中得数据如下："<<endl; p=head->next; while(p!=NULL) {cout<<p->data<<""<<endl; p=p->next;}}template<classT>voidlist<T>::insert(constT&item,Tx)//在单链表中数据域为x的节点之后插入一个新节点{ p=head->next; while(p->data!=x&&p->next!=NULL) p=p->next; node<T>*q; q=newnode<T>(item,NULL); q->next=p->next; p->next=q;}template<classT>Tlist<T>::delet(intpos)//删除指定的节点{ inti(1); p=head->next; q=head; while(p!=NULL&&i!=pos) {p=p->next;q=q->next;i++;}q->next=p->next; returnp->data; deletep;}作业：1）编写一个在线性链表中数据域为a的节点之后，插入一个新节点的算法。若原链表中无数据域为a的节点，则把新节点插入表尾。新节点的数据域为x。2）编写一个将线性链表逆置的算法。以上算法均以链表类的成员函数的形式给出。（2）循环链表特点：将表中最后一个结点的指针域指向头结点，整个链表形成一个环。循环条件：p是否为头指针.headhead->next==headp->next==head单循环链表举例1)将两个链表合并成一个链表。p=L1->next;while(p->next!=L1)p=p->next;p->next=L2->next;while(p->next!=L2)p=p->next;p->next=L1;时间复杂度：L1L2ABBA仅设尾指针的循环链表，合并情况如下：p=A;p->next=B->next->next;B->next=A->next;A=b;2）Josephus(约瑟夫）问题。有n个人围成一个圆圈，任意给出一个整整数m，从第一个人开始计数，数到第m个人时第m个人被从圆圈中除去。问最后剩下是哪个人。分析问题，写出算法。三、双向链表（双向循环链表）cbheadhead->prior==head;head->next==head;为了克服单链表的不足——找后继容易，找前驱难。双向链表的节点有两个指针域，一个指向直接后继，一个指向直接前驱。空表循环条件：p->next是否为head1)双向链表上的插入与删除操作acbpA）删除

e=p->data;p->prior-->next=p-->next;p->next-->prior=p-->prior;delete(p);axbss-->prior=p-->prior;p-->prior-->next=s;s-->next=p;p-->prior=s;

B）插入p2）双向链表举例（2002年电子科大专业试题）

设双向链表结构如下：头节点有两个域，其中，firstlink指向第一个数据节点，lastlink指向最后一个数据节点，链表空时，firstlink＝lastlink＝NULL。阅读下面算法，用适当的语句完成各下划线的处理，使其能实现删除链表中data域为x的所有节点…datalinkfirstlinklastlinkvoiddelete(L,x){p=L->firstlink;q=L;{置初值：p，q为同步指针，q为p的直接前驱}while(p!=NULL){if(p->data==x)case{分三种情况}L=q;{第一个节点为x和只有一个节点为x的处理}

LL->lastlink=p:{最后一个节点为x的处理}

others:{其他节点为x的处理}else{不为x的处理}}}1）链表的基本操作的实现举例。2）课后作业（1）上机实现循环单链表的基本操作；（2）实现双向链表的基本操作。单链表的应用举例一元多项式的表示和相加pn(x)=p0+p1(x)+p2(x2)+…+pn(xn)p=(p0,p1,p2,…pn)qm(x)=q0+q1(x)+q2(x2)+…+qm(xm)q=(q0,q1,q2,…qm)r=((p0+q0),(p1+q1),(p2+q2),…(pm+qm),pm+1,…pn)(m<n)S(x)=1+3x1000+2x2000一般情况下，一元n次多项式可写成如下形式：Pn(x)=p1xe1+p2xe2+p3xe3+...+pmxem则可以用一个长度为m,每个元素有两个数据项的线性表（（p1,e1),(p2,e2),(p3,e3),...,(pm,em))来唯一确定多项式Pn(x).-1071893175A-118722B8-9-1071

11175C722

#include"iostream.h"classnode{ friendclasslist;private: floatcoef; intexpn; node*next;public: node(){next=NULL;} ~node(){}};classlist{ friendclassnode;private: node*head,*p;public: list(){} node*creat(intn); node*add(node*p1,node*p2); voidprint(node*s);};node*list::creat(intn){ head=newnode(); node*q;

q=head; for(inti=0;i<n;i++) { p=newnode(); cin>>p->coef; cin>>p->expn; q->next=p; q=p; } returnhead;}node*list::add(node*p1,node*p2){ node*l1,*s,*q; p=p1->next;

l1=p1; q=p2->next;while(p!=NULL&&q!=NULL) { if(p->expn<q->expn) { p=p->next; l1=l1->next; cout<<"A表的指针后移即可！"<<endl; } if(p->expn>q->expn) { s=q; q=q->next; s->next=p;

l1->next=s; l1=s; cout<<"将B的节点插入到A！"<<endl; } if(p->expn==q->expn) { p->coef=p->coef+q->coef; if(p->coef==0) { node*m; m=p; l1->next=p->next; p=l1->next; m->next=NULL; deletem;

q=q->next; cout<<"两个节点相加，和为0"<<endl; } else { p=p->next; l1=l1->next; q=q->next; cout<<"两个节点相加，和不为0"<<endl; } } } if(p==NULL)l1->next=q;returnp1;}voidlist::print(node*s){ p=s->next; while(p->next!=NULL) { cout<<p->coef<<"X"<<p->expn<<"+"; p=p->next; } cout<<p->coef<<"X"<<p->expn; cout<<endl;}voidmain(){ listA,B,C; node*p1,*p2;p1=A.creat(4); p2=B.creat(3); node*mylist; mylist=C.add(p1,p2); C.print(mylist);}二、链栈——栈的链式存储...topdatanext栈底栈顶节点类的定义数据信息：头指针数据域，指针域函数：1）入栈操作的实现...topdatanext栈底栈顶ss->next=top->nexttop->next=s

...topdatanext栈底栈顶stops->next=top;top=s;voidLinStack<T>::push(constT&item){StackNode<T>*newNode=newStackNode<T>(item,top); top=newNode; size++;}个整整数m，从第一个人开始计数，数到第m个人时第m个人head=newnode();特点：将表中最后一个结点的指针域指向头结点，整个链表形成一个环。链式存储结构是计算机中另外一种最基本的数据存储结构。{p=L->firstlink;if(p->expn>q->expn)while(p!=NULL)Pn(x)=p1xe1+p2xe2+p3xe3+.for(j=0,k=0;j<d;j++)//顺序回收各队列中的对象（A）删除操作（一般情况）p->print();head=p->nexts-->prior=p-->prior;returndata;cin>>p->coef;node*next;2）出栈的操作实现...topdatanext栈底栈顶栈不空时：p=top->next;data=p->data;top->next=p->next;deletep;returndata;p...topdatanext栈底栈顶p=top;top=top->next;deletep;template<classT>TLinStack<T>::pop(void){ if(size==0) { cerr<<"堆栈空！"<<endl; exit(1); } StackNode<T>*p=top->next; Tdata=top->data; deletetop; size--; top=p; returndata;}表达式计算输入后缀表达式，计算表达式的值。#include<ctype.h>#include"LinStack.h"template<classT>classPost{ private: LinStack<T>s;//定义一个栈 voidEnter(Tnum);//将数据元素T入栈 intGetdata(T&op1,T&op2);//出栈顶元素分别到op1和op2中 voidcomputer(charop);//做相应的运算，将结果入栈 public: Post(void){}; voidrun(void); voidClear(void);};template<classT>voidPost<T>::Enter(Tnum){ s.Push(num);}template<classT>intGetdata(T&op1,T&op2){ if(s.StackEmpty()) { cerr<<"栈空!"<<endl; return0; }

op1=s.Pop();if(s.StackEmpty()) { cerr<<"缺少操作数!"<<endl; return0; }op2=s.Pop();return1;}template<classT>voidPost<T>::computer(charop){ intresult; Toperand1,operand2; result=Getdata(operand1,operand2); if(result==1) switch(op) { case'+':s.Push(operand2+operand1);break; case'-':s.Push(operand2-operand1);break; case'*':s.Push(operand2*operand1);break; case'/':s.Push(operand2/operand1);break; }else s.ClearStack();

}template<classT>voidPost<T>::run(void){ charc; Tnewoperand; cout<<"输入后缀表达式，以＃结束！"<<endl; while(cin>>c,c!='#') { switch(c) { case'+': case'-': case'*': case'/':Compute(c); break;

default:cin.putback(c);//是操作数，入栈 cin>>newoperand; Enter(newoperand); break; } } if(!s.StackEmpty()) cout<<"计算结果为："<<s.Peek()<<endl;}template<classT>voidPost<T>::Clear(void){ s.ClearStack();}#include"Post.h"voidmain(void){ Post<float>exp; exp.run();}三、链式队列链式队列式队列的链式存储结构。frontrearfrontrear空队列1）出队列frontrearpintlinqueue::del(void){ if(size==0) { cerr<<“队列为空"<<endl; exit(1); }node*p=front->next; intx=front->data; deletefront; front=p; if(front==NULL)rear=NULL; size--; returnx;}2）入队列frontrearsrearrear->next=s;rear=s;一般情况：特殊情况：voidlinqueue::insert(int&item){ node*p=newnode(item); if(size>0) { rear->next=p; rear=p; } else { front=p; rear=p; } size++;}3)链队列的应用举例——链式基数排序基数排序是一种依据组成关键字的各位值进行排序的方法。该方法是最早的排序方法之一，早在计算机出现之前的卡片排序机就是利用基数排序的思想对穿孔卡片进行排序的。278109063930083008269505184589voidradixsort(inta[],intn,intm,intd){ inti,j,k,power=1; linqueue*tub=newlinqueue[d]; for(i=0;i<m;i++)//进行m次排序 { if(i==0)power=1; elsepower=power*d;for(j=0;j<n;j++)//将对象按关键码第k为的大小放到相应的队列中 {

k=a[j]/power-(a[j]/(power*d))*d; tub[k].inser