扣着的是头节点(头子)
车是首节点(首子)
马是次节点(次子)
牙签细的是指针指向,香头发黑的是指向,铁头细的是指向。
根据步骤写程序的伪算法(3步4循环,7张图片搞定),如下:
以下是while循环(条件:香头指向不为空)
第一个循环把马弄到车前面,
第二个循环把相弄到马前面
第三个循环把士弄到相前面
........
直到香指向为空后停止循环。
代码如下:只需要一个首结点pHead,就能把链表找到,并倒置。具体代码如下
p香=pHead->pNext
p铁=p香->pNext
p香->pNext=NULL
P香=p铁
while(p香 !=NULL)
{
p铁=p香->pNext
p香->pNext=pHead->pNext
pHead->pNext=p香;
p香=p铁;
}
对照伪算法(三步四循环),和上面的代码是一一对应的:
第一步:香头指向首子,铁头指向次子
第二步:删掉首子指向次子(铁头所指向的那个子)的牙签
第三步:香头跟着铁头
以下循环条件:(条件:香头指向不为空)
{
循环1:铁头移动到香头的下一个指向
循环2:香头的下一个指向首子
循环3:头子的下一个跟着香头
循环4:香头跟着铁头
}
自己用道具操作几遍,然后把流程背会,以后自己根据流程写代码即可。
#include "stdio.h" \x0d\x0a#include"malloc.h" typedef struct node \x0d\x0a{ \x0d\x0a int data\x0d\x0a struct node *next\x0d\x0a}linklink *creat(int n) //创建链表 \x0d\x0a{ \x0d\x0a link *head,*p,*s\x0d\x0a int i\x0d\x0a p=head=(link *)malloc(sizeof(link))\x0d\x0a for(i=1idata)\x0d\x0a p->next=s\x0d\x0a p=s\x0d\x0a } \x0d\x0a p->next=NULL\x0d\x0a return head\x0d\x0a} void reverse(link *head)//原地置换 \x0d\x0a{ \x0d\x0a link *p,*s,*t\x0d\x0a p=head\x0d\x0a s=p->next\x0d\x0a while(s->next!=NULL)//主要置换过程 \x0d\x0a { \x0d\x0a t=s->next\x0d\x0a s->next=p\x0d\x0a p=s\x0d\x0a s=t\x0d\x0a } \x0d\x0a s->next=p\x0d\x0a head->next->next=NULL//收尾 \x0d\x0a head->next=s//赋头 \x0d\x0a} void display(link *head)//显示链表内容 \x0d\x0a{ \x0d\x0a link *p\x0d\x0a p=head->next\x0d\x0a while(p!=NULL) \x0d\x0a { \x0d\x0a printf("%d ",p->data)\x0d\x0a p=p->next\x0d\x0a } \x0d\x0a printf("\n")\x0d\x0a} void main() \x0d\x0a{ \x0d\x0a link *head\x0d\x0a head=creat(5)//创建一个5个节点的链表 \x0d\x0a printf("原链表:\n")\x0d\x0a display(head)\x0d\x0a reverse(head)\x0d\x0a printf("置换后链表:\n")\x0d\x0a display(head)\x0d\x0a}List_ptr InvertList(List_ptr head) //原地逆转单链表head{
List_ptr p=head,q=NULL,listend=head
while(listend->next!=NULL) listend=listend->next
while(p!=listend)
{
head=p->next
listend->next=p
if(q==NULL) p->next=NULL
else p->next=q
q=p
p=head
}
return head
}