资源描述
单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第十二讲 链表插入结点,1,链表插入结点,原则：,1,、插入操作不应破坏原链接关系,2,、插入的结点应该在它该在的位置。应该有一个插入位置的查找子过程。,2,5,head,6,10,15,null,12,8,先看下面一个简单的例子：,已有一个如图所示的链表。它是按结点中的整数域从小到大排序的。现在要插入一个结点，该节点中的数为,10,。,待插入结点,此结点已插入链表,3,/,结构,7.c,#include/,预编译命令,#include/,内存空间分配,#define null 0/,定义空指针常量,#define LEN,sizeof(struct,numST,)/,定义常量，表示结构长度,struct,numST,/,结构声明,int,num;/,整型数,struct,numST,*next;/,numST结构指针,;,参考程序,4,/,被调用函数,insert(),，两个形参分别表示链表和待插入的结点,void insert(,struct,numST,*,phead,struct,numST,*p),/,函数体开始,struct,numST,*q,*r;/,定义结构指针,q,r,if(*,phead,)=null)/,第一种情况,，链表为空,*,phead,=p;/,链表头指向,p,return;/,完成插入操作，返回,else/,链表不为空,/,第二种,情况,，,p结点num值小于链表头结点的num值,if(,(*,p,head,)-num,p-num),/,将p结点插到链表头部,p-next=*,p,head,;/,将p的next指针指向链表头,(*,p,head,),*,p,head,=p;,/,将链表头赋值为p,return;,/,返回,5,/,第三种,情况,，循环查找正确位置,r=*,p,head,;/,r赋值为链表头,q=(*,p,head,)-next;/,q赋值为链表的下一个结点,while(q!=null),/,利用循环查找正确位置,/,判断当前结点num是否小于p结点的num,if(q-num num),r=q;/,r赋值为q，即指向q所指的结点,q=q-next;/,q指向链表中相邻的下一个结点,else/,找到了正确的位置,break;/,退出循环,/,将p结点插入正确的位置,r-next=p;,p-next=q;,6,/被调用函数，形参为ST结构指针,，,用于输出链表内容,void,print(struct,numST,*head),int,k=0;/,整型变量，用于计数,struct,numST,*r;/,声明r为ST结构指针,r=head;/,r赋值为head，即指向,链表头,while(r,!=null)/,当型循环，链表指针不为空,则,继续,/,循环体开始,k=k+1;/计数加1,printf(%d,%,dn,k,r,-num);,r=r-next;,/,取链表中相邻的下一个结点,/,循环体结束,7,void main()/,主函数开始,/,函数体开始,struct,numST,*head,*p;/ST型结构指针,head=null;,/,初始化,head,为,null,/分配,3,个ST结构的内存空间，用于构造链表,head=(,struct,numST,*),malloc(LEN,);,head-next=(,struct,numST,*),malloc(LEN,);,head-next,-next,=(,struct,numST,*),malloc(LEN,);,/为链表中的,3,个结点中的num赋值为,5,、,10,和,15,head-num=5;,head-next-num=10;,head-next-next-num=15;,head-next-next,-next,=null;/,链表尾赋值为空,/,构造一个结点p，用于插入链表,p=(,struct,numST,*),malloc(LEN,);,p-num=,12,;,p-next=null;,insert(&head,p);,/,调用,insert,函数将结点,p,插入链表,print(head,);/,调用print函数，输出链表内容,/,主函数结束,8,1,、定义两个,ST,型结构指针*,head,，*,p,，并让,head=null,；,2,、分配,3,个,ST,结构的内存空间，用于构造链表,（,1,）,head=(,struct,numST,*),malloc(LEN,);,（,2,）,head-next=(,struct,numST,*),malloc(LEN,);,（,3,）,head-next-next=(,struct,numST,*),malloc(LEN,);,先看主函数,head,这,3,个,ST,结构的内存空间如上图所示。,head-next,head-next-next,9,下面用赋值语句往这,3,个空间中放,num,数据。最后的一个结点为队尾，在其指针域存放,null,。,（,4,）,head-num=5;,（,5,）,head-next-num=10;,（,6,）,head-next-next-num=15;,（,7,）,head-next-next-next=null;,做了这,4,条之后形成了一条链表如下：,5,head,10,15,null,该链表的头结点由,head,所指向。,10,3,、构造一个结点,p,，在,p,结点的数据域放,12,，再插入链表,（,1,）,p=(,struct,numST,*),malloc(LEN,);,（,2,）,p-num=12;,（,3,）,p-next=null;,4,、调用,insert,函数来插入,p,结点。,语句为,insert(&head,p,);,意思是以将,p,插入到以,head,为队头的链表中。但这里在调用时，不是用,head,作为实参，而是用,&head,作为实参，属于,传址调用,，而非,传值调用,。,11,这里要讲传址调用和传值调用的区别,（,1,）如果是传值调用主程序中的调用语句为,insert(head,p,);,被调用函数为,void,insert(struct,munST,*,phead,struct,numST,*p);,head,p,实际参数,形式参数,p,phead,12,当着实际参数,head,赋给了形式参数,phead,之后，,phead,就指向了已经存在了的链表，见下图。,5,10,15,null,phead,这时原来的主程序中的头指针就不再起作用了。而是,phead,起作用。假如现在,p,中的结点数据为,4,小于,5,，应该将,p,插入到,phead,所指向的结点前，如下图,head,13,5,head,10,15,null,phead,被调用函数无法改变,head,，这时,head,不再是头结点的指针了。如果被调用函数返回,head,，主函数只能表示,head,为头指针的三个结点，新插入的结点并没有包含进去。要想将新的插入到最前面的结点包含进去，就必须用传址调用。,4,phead,14,（,2,）如果是传址调用主程序中的调用语句为,insert(&head,p,);,被调用函数为,void,insert(struct,munST,*,phead,struct,numST,*p);,先看,struct,numST,*,phead,是说定义（*,phead,）为指向,numST,结构的指针。*,phead,是指向,numST,结构的指针,phead,又是指向*,phead,这个指针的指针。,phead,=&head,15,主程序中的实参为链表头指针,head,所在的地址值，传给被调用函数的,phead,的指针变量中，起到了让,phead,也指向,head,的目的。,&head,phead,head,16,在主函数中,head,为头指针，在被调用的子函数中,phead,为头指针的地址，,head,和*,phead,是同一个单元，只不过分别叫不同的名罢了。当然在子函数中无论插入什么结点都会让*,phead,指向链表的头。自然返回到主函数后，,head,也会是指向同一链表的头。,从这个例子中读者可以领回到传值调用与传址调用的区别。,5,、这样在子函数做插入结点的过程中，头指针的改变也能反映到主函数中来。调用,print,函数，从,head,开始输出整个链表的内容。,17,下面我们来研究,insert,函数,前提是主程序已将两个实参传给了,insert,函数的两个形参，这时*,phead,=head,，,p,所指向的就是待插入的一个结点。事先定义两个结构指针,q,和,r,。,第一种情况：,*,phead,=null,，说明主程序传过来的头指针为空，即链表为空，一个结点都不存在。这时待插入的,p,结点就是链表中的第一个结点。只要执行如下两条语句即可,*,phead,=p;/,将表头指针指向,p,结点,return;/,返回主程序,在主程序中必然头指针,head,指向,p,结点。,18,第二种情况：,p,结点的,num,值小于链表头结点的,num,值，即,(*,phead,)-nump-num,。这时要将,p,结点插入到头结点的前面，要执行如下三条语句,p-next=*,phead,;/,在,p,结点的指针域赋以头结点的地址值,*,phead,=p;/,将头结点指针,phead,指向,p,结点,return;/,返回主程序,这种情况如下图,5,*,phead,10,4,15,null,*,phead,p,null,19,第三种情况：,前两种情况，无论遇到哪一种，都会返回主程序。只要不返回就是这第三种情况，即,p,结点的,num,大于头指针所指向的结点的,num,值。这时肯定地说,p,结点要插入到头结点之后，究竟要插到哪里需要找到应该插入的位置。我们设指针,r,和指针,q,，分别指向相邻的两个结点，,r,在前,q,在后，当着满足,r-num num num,时，,p,就插在,r,与,q,之间。我们看图,5,head,10,12,p,15,null,q,r,null,q,r,20,一开始让,r=*,phead,，让,q=*,phead,-next,(1),当指针,q,为空指针时，说明原链表中只有一个结点，即,r,指向的结点，这时只要将,p,结点接在,r,之后即可。执行,r-next=p;,p-next=q;,(2),如果,q!=null,，说明起码有两个结点在链表中，接着要判,p,结点的,num,值是否大于,q,结点的,num,值。如果是大，则说明,p,应插在,q,之后而不是之前，这时让,r,和,q,指针同时后移一步，即,r=q;,q=q-next;,21,执行,(2),在,q!=null,的情况下，如果,p-numnum,了，说明这时找到了正确的插入位置，退出,while,循环，将,p,结点插入到,r,后，,q,前即可。使用的语句为,在下面我们画出该算法的结构框图,r-next=p;,p-next=q;,22,23,作业,1,、按下表顺序输入某班的一个学习小组的成员表,希望你将学习小组形成一个链表，每人一个结点。结点中有四个成员：姓名、出生年、出生月、指针。在链表中生日大者在前，小者在后。,建成链表后输出该链表。,姓名,赵达,钱亮,孙参,李思,周芜,武陆,郑琪,出 年,生 月,1983,1983,1983,1982,1983,1983,1982,1,3,2,9,5,4,6,24,2,、一年后钱亮同学调至其它学习小组，希望你编程从原链表中删除钱亮所在结点，之后输出该链表。,提示：原链表如下：,李思,1982,9,head,武陆,1983,4,赵达,1983,1,孙参,1983,2,钱亮,1983,3,郑琪,1982,6,周芜,1983,5,null,查找待删除的结点的位置，要从链头找起。,(1),如果是链头结点，即有,he
展开阅读全文