[工学]链表综合学习.doc

链表链表属于动态数据结构，可以类比成一环接一环的链条，这里每一环视作一个结点，结点窜在一起形成链表。这种数据结构非常灵活，结点数目无须事先确定，可以临时生成。每个结点有自己的存储空间，结点间的存储空间也无须连接，结点之间的串连由指针来完成！一举例说明链表的概念程序可以将节目串在一起，形成一份有序的节目报告将节目列表有如下三项要求：（1）节目名称，包括新闻联播，祖国各地，体育之窗，学校见闻和电影展播。（2）节目主持人；（3）播放时间长度。建立链表的过程#include#define null 0struct ActList char ActName20; char director20; int Mtime; ActList *next;ActList *head; /链头指针ActList *Creat() /定义一个指向ActList结构的指针函数 ActList *p=null; /指针，指向一个待插入的结点 ActList *q=null; /指针，用于在其后插入结点 head=null; /一开始链表为空 int Time;/一下是给新结点输入节目信息 coutTime; while(Time!=0) /纳入链表 p=new ActList; /分配内存空间给p结点! p-Mtime=Time; /让Time赋给p结点的结构成员 coutp-ActName; coutp-director; if(head=null) /插入第一个 head=p; /结点，让头指针指向结点p else q-next=p; /否则不是头结点，应将p结点插入到q/结点的后面 q=p; /q指向当前最后一个结点 coutTime;if(head!=null) /头指针不空，链表至少有一个结点 /让q所指的最后一个结点的指针域为空 /说明这已经是链尾了 q-next=null; /q一定是最后一个结点return(head); void displayList(ActList *head)cout显示节目列表n;while(head!=null)coutMtimeendl;coutActNameendl;coutdirectorendlnext;int main()/调用子函数displayList()，调用时的实参为Creat()函数的返回值 displayList(Creat(); return 0;(1)程序开头为结构定义。在这里称这样的一个结构为一个结点。这个结点包含两个域，即数据域和指针域。(2)数据域装有节目的信息，而指针域装的是指向另一个结点的地址。(3)首先给p结点分配内存空间，p结点有了内存空间，就可以给它的各个成员赋值了。(4)q-next=p;将此时的p结点放到q所指向的结点后面。之后让q=p(q赋值为p)，即让指针指向刚进入链表的结点，腾出p去指向下一个待加入的结点。(5) return(head);执行完函数后得到head指针所指向的地址，这个地址就是链表中第一个结点的地址！(6)定义指向结构的两个指针p和q，定以后立即初始化为空，即不指向任何地址。再让链表头指针head为空，也是不指向任何地址，表示该链表尚未建立，一个结点也没有。(7)当Time不为0，p又被分配了内存空间，形成了第二个结点，装入信息后，判断head不再为空，说明前面已经有结点在链表中。这时要将第二个结点放到q所指向的结点的后面，即执行q-next=p;再将q指针移到第二个结点上，将p指针腾出来去做下一个结点的工作。链表结点的插入与删除/链表插入结点#include#include#define NULL 0struct numST int num; numST *next; /numST结构指针;void insert(numST *&pHead,numST *pNode) struct numST *q,*r; /定义结构指针q,r /第一种情况，链表为空 if(pHead=NULL) pHead=pNode; /链表头指向pNodereturn;/第二种情况，pNode结点num值小于等于链表头结点的num值/则将pNode结点插到链表头前面if(pNode-num)num)pNode-next=pHead; /将pNode的next指针指向链表头pHeadpHead=pNode; /将链表头赋值为pNodereturn;/第三种情况，循环查找正确位置r=pHead; /r赋值为链表头q=pHead-next; /q赋值为链表头的下一个结点(q永远为最末指针)while(q!=NULL)/判断pNode结点的num值是否大于当前结点的num值if(pNode-num)(q-num)r=q; /r指向q所指的结点q=q-next; /q指向链表中相邻的下一个结点else /找到正确位置，退出循环!break;/将pNode结点插入正确位置r-next=pNode;pNode-next=q;void print(numST *pHead) int k=0;numST *r=pHead; /声明numST结构指针r，并让它指向链表头 while(r!=NULL) /链表头指针不为空则循环继续 cout.width(2); /设置输出序号k所占的宽度k=k+1;coutk:numnext; /移动至下一个结点int main() numST *pMHead=NULL;numST *pMNode=NULL;/分配3个numST结构的内存空间，用于构造链表pMNode=new numST;pMHead=new numST;pMHead-next-next=new numST;/为链表中的三个结点中的num值赋值5,10,15pMHead-num=5;pMHead-next-num=10;pMHead-next-next-num=15;pMHead-next-next-next=NULL;/构造一个结点p，用于插入链表pMNode=new numST;pMNode-num=12;pMNode-next=NULL;insert(pMHead,pMNode);print(pMHead);return 0;/与new对应，用delete释放空间!传引用调用： numST *&pHead，声明pHead为numST结构指针的引用，即pHead是“指向numST结构的指针”的引用!主程序中的实参为链表头指针pMHead的引用，传给被调用函数的pHead，在子函数中对pHead的操作就等价于对pMHead的操作。void del(numST *&pHead,int num)numST *p=NULL,*q=NULL;if(pHead=NULL)return;p=pHead;if(p-num=num)pHead=p-next;delete p;return;q=p-next;while(q!=NULL)if(q-num=num)p-next=q-next;detele q;return;if(q-numnum)return;p=q;q=q-next;(1)链表头是要删除的结点。这时先用一个指针p暂存此结点，再让链表头指向相邻的下一个结点，最后将p结点删除。(2)找到了要删除的结点，为了不破坏原链表的链接关系，要将该结点的上一个结点链接到该结点的下一个结点，因此先要暂存上一个结点的指针p，然后让p-next指向q-next所指的结点，最后删除q指向的结点。(3)建立链表时，动态申请的内存空间应该在程序结束前释放，即在程序结束之前将链表中的结点全部删除。void release(numST *&pHead)numST *p=NULL,*q=NULL;p=pHead;while(p!=NULL)q=p-next; /用q指针暂存下一个结点delete p;p=q; /删除p指向的结点pHead=NULL; /重要!将链表置空。循环链表#include#include struct monkeyint num;monkey *next;monkey *head,*tail;void creat(int nn)int i;monkey *p,*q;p=new monkey;p-num=1;p-next=NULL;head=p;q=p;for(i=2;inum=i;q-next=p;q=p;p-next=NULL;tail=q;tail-next=head;void select(int mm)int x=0;monkey *p,*q;q=tail;dop=q-next;x+;if(x%mm=0)cout被删除的猴子号为:num号!next=p-next;delete p;p=NULL;else q=p;while(q!=q-next);head=p;int main()int n,m;head=NULL;coutn;coutm;creat(n);select(m);cout猴子王是:num号!next=p，接着让q指针指向刚插入的的p结点，使用q=p让q永远指向链表的最末一个结点，使用q-next=NULL，这样就能把p解放出来，又可去指向待插入的下一个结点。（二）学习链表的插入过程，需要用到4个指针：pHead，pNode，r，q。让pHead永远指向链表的第一个结点，pNode指向待插入的结点，让r和q为一前一后两个同步移动的指针，用来查找pNode结点的正确位置。一开始让r指向链表头，让q指向相邻的下一个结点，即r=pHead;q=pHead-next;之后就比较pNode结点和q结点的num值。如果pNode-numq-num;说明尚未找到正确的插入点!让r和q同步后移一个结点，即r=q;q=q-next;如果pNode-numnum；则将pNode结点插入到r结点后q结点之前，即r-next=pNode;pNode-next=q。带头结点单链表的C+完整描述#include#includetemplateclass NODE public:datatype data;NODE *next;templateclass LIST private:NODE *head;public:LIST() head=new NODE;head-next=NULL;int length();bool isempty() return head-next=NULL?true:false;bool get_data(int i,datatype &x);bool get_succ(int i,datatype &x);bool get_prior(int i,datatype &x);bool replace_data(int i,const datatype x);bool insert_data(datatype datd,int i);bool delete_data(int i);bool find_data(datatype x,datatype &result);void print_list();LIST() NODE *p;while(head) p=head;head=head-next;delete p;templateint LIST:length() int counter=0;NODE *current;current=head-next;while(current!=NULL) current=current-next;counter+;return counter;templatebool LIST:get_data(int i,datatype &x) NODE *current;int j=1;if(ilength() cout非法位置读取元素，不能读取!next;while(current!=NULL) j+;current=current-next;x=current-data;return true;templatebool LIST:get_succ(int i,datatype &x) NODE *current;int j=1;if(ilength() cout非法位置读取元素!不能读取!next;while(current!=NULL&jnext;if(current-next!=NULL) x=current-next-data;return true;else cout第i个元素无后继，不能读取!endl;return false;templatebool LIST:get_prior(int i,datatype &x) NODE *current,*previous;int j=1;if(ilength() cout非法位置读取元素，不能读取!next;while(current!=NULL&jnext;if(previous!=head) x=previous-data;return true;else cout第i个元素无前驱，不能读取!endl;return false;templatebool LIST:replace_data(int i,const datatype x) NODE *current=head;int j=1;if(ilength() cout非法位置修改元素，不能修改!next;while(current!=NULL&jnext;current-data=x;return true;templatebool LIST:insert_data(datatype data,int i) NODE *current,*previous,*newnode;int j=1;if(ilength()+1)|(i0) cout插入位置不正确!不能插入!endl;return false;newnode=new NODE;if(newnode=NULL) cout内存无空间!不能插入!data=data;newnode-next=NULL;previous=head;current=head-next;while(current!=NULL&jnext;j+;newnode-next=current;previous-next=newnode;return true;templatebool LIST:delete_data(int i) NODE *current,*previous;int j=1;if(isempty() cout表已空，不能删除!length()+1)|(i0) cout删除位置不正确!不能删除!next;while(current!=NULL&jnext;j+;previous-next=current-next;delete current;return true;templatebool LIST:find_data(datatype x,datatype &result) NODE *current;current=head-next;while(current!=NULL) if(current-data!=x)current=current;else result=current-data;return true;cout链表中没有x这个数据元素!endl;return false;templatevoid LIST:print_list() NODE *current;current=head-next;cout链表中全体元素为:endl;while(current) coutdatanext;coutendl;int main() int i;LIST list1;for(i=1;i=5;i+)list1.insert_data(i*100,i);list1.print_list();list1.insert_data(404,4);list1.print_list();list1.insert_data(809,-4);list1.print_list();list1.delete_data(8);list1.print_list();list1.delete_data(1);list1.print_list();int i_data=-1;list1.replace_data(0,i_data);list1.print_list();list1.replace_data(4,i_data);list1.print_list();LIST list2;for(i=1;i=5;i+)list2.insert_data(i*100+.141,1);list2.print_list();float f_data=-1.0;for(i=0;i=6;i+) if(list2.get_prior(i,f_data)coutf_data ;f_data=-1.0;for(i=0;i=6;i+) if(list2.get_succ(i,f_data)coutf_data ;return 0;ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo#include#include#define LEN sizeof(struct listnode)struct listnode int num;char name10;float score; struct listnode *next;struct listnode *creat(void)struct listnode *p1,*p2,*head;int n=0;p1=p2=(struct listnode *)malloc(LEN);cout输入学号、姓名、成绩(学号为零停止):p1-nump1-namep1-score;head=NULL;while(p1-num!=0)n+;if(n=1)head=p1;elsep2-next=p1;p2=p1;p1=(struct listnode *)malloc(LEN);cinp1-nump1-namep1-score;p2-next=NULL;return (head);/用于两个链表的合并struct listnode *insert(struct listnode *ah,struct listnode *bh)struct listnode *pa1,*pa2,*pb1,*pb2;pa2=pa1=ah;pb2=pb1=bh;dowhile(pb1-score)score)&(pa1-next!=NULL)pa2=pa1;pa1=pa1-next;if(pb1-score=pa1-score)if(ah=pa1)ah=pb1;else pa2-next=pb1;pb1=pb1-next;pb2-next=pa1;pa2=pb2;pb2=pb1;while(pa1-next!=NULL)|(pa1=NULL&pb1!=NULL);if(pb1!=NULL)&(pb1-scorescore)&(pa1-next=NULL)pa1-next=pb1;return (ah);/用于排序struct listnode *sort(struct listnode *head) struct listnode *p,*p1,*p2,*p3; struct listnode h, t; if(head = NULL)return NULL; h.next=head; p=&h; while(p-next!=NULL) p=p-next; p=p-next=&t; whi