《C语言:逆转链表.doc》由会员分享,可在线阅读,更多相关《C语言:逆转链表.doc(5页珍藏版)》请在金锄头文库上搜索。
1、#include stdio.h#include malloc.h#define BOOL int#define FALSE 0#define TRUE 1typedef char T;typedef struct nodeT data;/数据域struct node *next;/指针域 Node,List;/结点构造Node* NewNode()Node *p = (Node*)malloc(sizeof(Node);p-next = NULL;return p;Node* NewNode1(T x)Node *p = (Node*)malloc(sizeof(Node);p-data =
2、 x;p-next = NULL;return p;/用表尾插入法建立带头结点的单链表(元素为字符):List* Create()Node *head=NewNode();Node *p,*r=head;char c;T x;head-next=NULL;printf(请输入链表:);while(c=getchar()!=n)x= c;p = NewNode1(x);r-next=p;r=p;return head;void Invert(List *h) List *p,*q; /NodePtr为指向结点的指针类型 p=h-next; /p指向第一个数据结点 h-next=NULL; /将原
3、链表置为空表h while(p) q=p; p=p-next; q-next=h-next; /将当前结点插入到头结点的后面 h-next=q; /输出函数void PrintElement(T Element)printf(%c ,Element);void PrintList(List *lst)Node *p = lst-next;while(p)PrintElement(p-data);p = p-next;printf(n);void main()List *lst = Create();printf(链表输出:);PrintList(lst);printf(逆转后输出:);Inve
4、rt(lst);PrintList(lst);/*算法思路:依次取原链表中的每个结点,将其作为第一个结点插入到新链表中,指针p用来指向当前结点,p为空时结束*/void reverse(NodePtr h) NodePtr p,q; /NodePtr为指向结点的指针类型 p=h-next; /p指向第一个数据结点 h-next=NULL; /将原链表置为空表h while(p) q=p; p=p-next; q-next=h-next; /将当前结点插入到头结点的后面 h-next=q; 请问下这个算法的while循环具体做的什么事情,要详细的解答(主要解释while循环)。假设有链表:h-1
5、-2-3-4p=h-next;,即p=1-2-3-4h-next=NULL;即断开h与p,即h 1-2-3-4然后while(p)第一步:q=p,即q=1-2-3-4第二步:p=p-next;,即p=2-3-4第三步:q-next=h-next,因为h-next=NULL所以q-next=NULL,即把q断开为1和2-3-4第四步:h-next=q;即h-next=1到此链表分成两部分:h-1和2-3-4第二次循环:第一步:q=p,即q=2-3-4第二步:p=p-next;,即p=3-4第三步:q-next=h-next,因为h-next=1,所以q-next=1,即把q分成:2-1和3-4第
6、四步:h-next=q;即h-next=2-1到此链表分成两部分:h-2-1和3-4第三次循环:第一步:q=p,即q=3-4第二步:p=p-next;,即p=4第三步:q-next=h-next,因为h-next=2-1,所以q-next=2-1,即把q分成:3-2-1和4第四步:h-next=q;即h-next=3-2-1到此链表分成两部分:h-3-2-1和4第四次循环:第一步:q=p,即q=4第二步:p=p-next;,即p=NULL第三步:q-next=h-next,因为h-next=3-2-1,所以q-next=3-2-1,即把q分成:4-3-2-1和NULL第四步:h-next=q;即h-next=4-3-2-1到此链表分成两部分:h-4-3-2-1和NULLp=NULL结束循环.