逆转线性表 - 副本

《逆转线性表 - 副本》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、作业题目：逆转线性表数据结构描述：采用数据的链式存储算法描述：,创建head指针对线性表进行链式存储。先判断是否为空链表或是单节点链表，若是则不需做任何操作，算法结束；若为两节点链表，直接将两节点前后件关系逆转，并将head指针指向新的前件，算法结束；若节点数大于或等于3，初始状态：新建两个指针p,q,并将p指向原链表第二个节点，q指向第三个节点，这样head,p,q三个指针所指向的三个节点依次相邻，将头两个节点之间前后件关系逆转，即将第二个指针指向第一个指针所指地址，而后将第一个指针指向第三个指针指向的节点的后件的地址。如此循环操

2、作直至head,p,q中的某一个指针指向末尾节点为止。此时三个指针依次指向最后三个节点。将此时最后两个前后件关系逆转，即将最后第二位的指针指向最后第三个指针指向的地址，又将最后一个指针指向最后第二个指针指向的地址。最后把head指针指向最后一个指针指向的地址。算法结束；最后把head指针保存的线性表顺序输出。对链表的一次逆转操作（以head,p,q指针顺序为例）：-ààààà…headpqßààà…Pqhead对线性链表最后三个节点前后件关系的逆转(以最后三个节点为head,p,q指针顺序为例)：…àààheadpq…àßßhead

3、程序：#include#includestructnode{intd;structnode*next;};structnode*head;//创建全局变量指针headvoidList(){head=NULL;}//建立空链表voidins_List(){intx;structnode*q;scanf(“%d”,&x);q=malloc(sizeof(structnode*));q->next=head;q->d=x;head=q;}//在链头插入元素xvoidch_List(){structno

4、de*p,*q;if(head==NULL

5、

6、head->next==NULL)return;//空链表或者单节点链表时逆转不用操作if(head->next->next==NULL){p=head->next;head->next=NULL;p->next=head;head=p;return;}//两节点列表时逆转操作p=head->next;q=p->next;while(p->next!=NULL&&q->next!=NULL&&head->next!=NULL){if(head->next==p&&p->next==q){

7、p->next=head;head=q->next;}if(p->next==q&&q->next==head){q->next=p;p=head->next;}if(q->next==head&&head->next==p){head->next=q;q=p->next;}}if(head->next==p&&p->next==q){p->next=head;q->next=p;head=q;return;}if(p->next==q&&q->next==head){q->next=p;head->next=q;return;}i

8、f(q->next==head&&head->next==p){head->=q;p->next=head;head=p;return;}}//逆转线性表的函数voidprt_List(){structnode*p;p=head;while(p!=NULL){printf(“%d”,p->d)p=p->next;}}//顺序输出线性链表intmain(void){inti,n;List();//建立空链表scanf(“%d”,&n);//确定链表长度for(i=1;i<=n;i++)ins_List();//将线性表已链表形式存

9、储ch_List();//逆转线性表操作prt_List();//将逆转后的线性表顺序输出return0;}验证算法的实例及其运算结果：5//n=554321//实际链表为1,2,3,4,5理论输出：54321实际输出：死循环，无输出值，自己未能找到程序中的错误。