链表完整版本

将新结点插入p的后面①②newp思考题：1、分别写出①②对应的语句2、①②是否可以颠倒？为什么？3、如果①②可以颠倒需要增加什么条件？4、如果链表为空怎么办？5、如果新结点为链表头怎么办？6、如果新结点为链表尾怎么办？12/19/2024链表

12/19/2024内容提纲

单向链表

双向链表

实战出击循环链表注意的问题12/19/20241.单向链表8910189.58910390head89105808910775

structstudent{intnum;floatscore;

structstudent*next;}head;12/19/20241.1链表建立初始状态（p链表尾结点指针，newp为新结点指针）最终状态p……p12/19/20241.1链表建立（续）p①p②③直到=-1为止①尾的后继指向新结点②改变尾结点③产生新结点12/19/20241.2链表遍历初始状态（p为遍历指针）最终状态pp循环：当!=x做p=p.next

指出其中的错误12/19/20241.3链表插入初始状态（p为遍历指针，newp为新结点指针）最终状态p12/19/20241.3链表插入（续1）①②③①遍历指针定位②新结点后继指向遍历结点的后继③遍历指针的后继指向新结点12/19/20241.4链表删除q①②③①遍历指针p定位②遍历结点的后继指向删除结点的后继③释放删除结点q12/19/20241.4删除链表（续）思考题：1、如果链表为空怎么办？2、如果新结点为链表头怎么办？3、如果新结点为链表尾怎么办？12/19/20242.双向链表priordatenext结点结构head

……

双向链表12/19/20242.1双向链表插入head

……

pnewp新结点插入到p结点的后面①②③④注意：先连后断12/19/20242.1双向链表删除删除p结点head

p①②③③释放删除结点p①p结点前驱指向p结点的后继②p结点后继指向p结点的前驱12/19/20243.循环链表P->next=headp12/19/20243.1循环链表中间插入p①②①新结点后继指向遍历结点的后继②遍历指针的后继指向新结点12/19/20243.2循环链表尾部插入p①②①新结点后继指向头结点

newp->next=head;②遍历指针的后继指向新结点

p->next=newp;12/19/20243.3循环链表头部插入①②③①新结点后继指向头结点：newp->next=head;②头指针指向新结点:head->=newp;③尾指针指向头结点:p->next=head;p12/19/20243.4删除循环链表中间结点p②p->next=p->next->next;或p->next=q->next;③释放q结点:free(q);删除p的后继结点①q=p->next;q②①12/19/20243.5删除循环链表尾结点pq①②①q=p->next;②p->next=head;③释放q结点:free(q);注意：引入q结点必要性12/19/20243.6删除循环链表头结点pq①q=p->next;或q=head;①②②p->next=head->next;③④释放q结点:free(q);③head=q->next;12/19/20244.注意的问题(1)必须画图(2)产生新结点：p=(structnode*)malloc(sizeof(structnode));(3)指针域不一定是next，一般取名为link,point(4)指向后继：p=p->next;(5)尾结点：if(p->next==NULL);或if(!p->next)(非循环链表)

if(p->next==head)(循环链表)(6)头结点：if(p==head)(7)#defineNULL012/19/20244.注意的问题（续）(8)初始化：p=head;(9)非空链表：while(p){……}(10)头指针不要轻易移动(11)指向后继：p=p->next;(12)唯一结点：if(h->next==NULL);(非循环链表)

if(head->next==head)(循环链表)(13)释放结点之前，要处理前驱结点的指向。(14)移动指针之前，要处理前驱结点的指向。12/19/20244.实战出击例1：函数fmax()的功能是:求出链表所有结点中,数据域值最大的结点的位置,并由参数s返回给主函数.该函数的第一参数是链表的首指针。（98春）structnode{intdata;

structnode*next;}；12/19/2024voidfmax(structnode*head,structnode28){structnode*p;p=head;*s=p;if(p==NULL)return;while(p){if(p->data>29)*s=p;p=30;}}**s）*s->data)*s=p;p->data);12/19/2024思考：

1、求最小元素位置并与表头结点交换

2、统计最大元素个数12/19/2024

1、求最小元素位置并与表头结点交换voidfmax(structnode*head,structnode**s){structnode*p,*q;p=head;*s=p;if(p==NULL)return;while(p){if(p->data<*s->data)*s=p;p=p->next;}q->data=p->date;p->date=*s->data;*s->date=q->data;}12/19/20242、统计最大元素个数（1）在升序排序的同时记录最大数；（2）遍历链表统计与最大数相等的次数；12/19/2024例2：函数fun的参数是链表的头指针，它完成的功能是：将链表中各结点分量data的数值为偶数的结点依次调到链表的前面。方法是：根据data的值，分为奇数偶书两个链表，然后将两个链表拼接在一起（98秋）。structnode{intdata;

structnode*next;};

12/19/2024

structnode*fun(structnode*head){structnode*p=head,*even=0,*old=0,*p1=0,*p2=0;

if(head==NULL){returnhead;}

while(p){if(p->data%2)

if(old==0{old=p;p1=p;}else{28;p1=p;}else

if(even==0{even=p;p2=p;}else{29;p2=p;}p=p->next;}

if(old)p1->next=0;

if(even){head=even;30;}elsehead=old;returnhear;}p1->next=p;p1=p;}p2->next=p;p2=p;}p2->next=old;}移动指针之前，要处理前驱结点的指向。12/19/2024思考：

1、所有素数调整到链表的前面

2、把满足某一性质的元素调整到链表的后面

3、链表反序12/19/2024例3：将链表上相临的两个结点合并成一个结点，即将第一结点与第二结点合并，将第三结点与第四结点合并，….，若链表上的结点个数为奇数，则最后的一个结点不合并，直接作为合并后链表上的最后一个结点（99春）。链表上结点数据结构为：structnode{intdata;

structnode*next;};12/19/2024初始状态：24

9head6815head104

最终状态：p1p212/19/2024合并过程：24

9head8p16p215①①p1->data+=p2->next;②p1②p1->next=p2->next;④③释放p2结点:free(p2);④p1=p1->next;p2⑤⑤p2=p1->next;②③可以颠倒吗？为什么？不可以，释放结点之前，要处理前驱结点的指向。12/19/2024voidmerge(structnode*h){structnode*p1,*p2;if(27)return;p1=h;p2=h->next;while(p2){p1->data+=p2->data;p1->next=28;free(p2);if(29)p2=30;elsep2=NULL;}}

h==NULL||h->next==NULL)return;

p2->next

;

p1->next!=NULL

p1->next;12/19/2024思考：

1、两端合并

2、相同元素合并

12/19/2024例4：有n个人围成一圈，他们的编号为1-n。第一个人从1开始顺序报数，凡报到m时，该人退出圈子。其后的人再从1开始顺序报数，直到最后一个退出圈子为止。输出依次退出圈子的人的编号。n和m的值从键盘上输入，且均小于200。（2000年）链表上结点数据结构为：structnode{intdata;

structnode*next;};12/19/2024p为遍历指针；指针q指向p的前驱；count为计数器当指针p指向的结点不是要删除的结点时：pqq①①q=p;p②②p=p->next;③count++;12/19/2024当指针p指向的结点是要删除的结点时：pq①①q->next=p->next;p④②free(p);③count=0;④p=q->next;注意：使用两个指针对循环链表的操作无需考虑头和尾。12/19/2024voidcircle(structnode*head,intm){structnode*p,*q;intcount=0;p=head;q=p;while(18){if(count!=m){count++;19p=p->next;}else{printf(“%d->”,p->data);

q->next=p->next;

free(p);

20;count=0;}}}

移动指针之前，要处理前驱结点的指向。q=p;p!=p->next)p=q->next12/19/2024main(){structnode*p,*head=0,*q;inti;head=(structnode*)malloc(sizeof(structnode));q=head;q->data=1;

for(i=2;i<8;i++){p=(structnode*)malloc(sizeof(structnode));p->data=i;q->next=p;q=p;}q->next=head;

circle(head,3);}

12/19/2024算法提示：a[0]……a[n-1]分别存放n个人的序号1、2……n-1、n。报数时，若a[i]的值不为0，则参与报数；否则不参与报数。当a[j]对应的人退出圈子时（下标取值n的余数为0），则将a[j]置为0。方法2：用数组实现

12/19/2024voidcircle(intn,inta[],intm){intcount=0,i=0,k=0;while(count19){if(20){i++;if(21){printf(“%d\t”,a[k]);i=0;a[k]=0;count++;}}if(++k22)k=0;}

printf(“\n”);}

<na[k]i%m==0%n==012/19/2024main(){intn,a[200],m,i;

printf(“输入围成一圈的人数：“)；scanf(“5d”,&n);

printf(“输入出圈的号数：“)；scanf(“%d”,&m);

for(i=0;i<n;i++)a[i]=i+1;

circle(n,a,m);}12/19/2024例5：设已建立了一条链表，链表上结点的数据结构为：

structnode{floatenglish,math;

structnode*next;};

求出该链表上的结点个数、英语的总成绩和数学总成绩，并在链首增加一个新的结点，其分量english,math分别存放这两门课程的平均成绩。若链为空链时，链首不增加结点。以下函数ave的第一个参数h指向链首，第二个参数count存放求出的结点个数。

12/19/2024structnode*ave(structnode*h,int*count){structnode*p1,*p2;floatsume=0,sum=0;*count=0;

if(h==NULL)27;p1=h;while(28){sume+=p1->English;sum+=p1->math;*count=*count+1;

29;}p1=(structnode*)malloc(sizeof(structnode));p1->English=sume/*count;p2->math=summ/*count;

30;h=p1;returnh;}

return0p1p1=p1->next

p1->n