資源描述：
《逆轉(zhuǎn)線性表 - 副本》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、作業(yè)題目：逆轉(zhuǎn)線性表數(shù)據(jù)結(jié)構(gòu)描述：采用數(shù)據(jù)的鏈?zhǔn)酱鎯?chǔ)算法描述：,創(chuàng)建head指針對(duì)線性表進(jìn)行鏈?zhǔn)酱鎯?chǔ)。先判斷是否為空鏈表或是單節(jié)點(diǎn)鏈表，若是則不需做任何操作，算法結(jié)束；若為兩節(jié)點(diǎn)鏈表，直接將兩節(jié)點(diǎn)前后件關(guān)系逆轉(zhuǎn)，并將head指針指向新的前件，算法結(jié)束；若節(jié)點(diǎn)數(shù)大于或等于3，初始狀態(tài)：新建兩個(gè)指針p,q,并將p指向原鏈表第二個(gè)節(jié)點(diǎn)，q指向第三個(gè)節(jié)點(diǎn)，這樣head,p,q三個(gè)指針?biāo)赶虻娜齻€(gè)節(jié)點(diǎn)依次相鄰，將頭兩個(gè)節(jié)點(diǎn)之間前后件關(guān)系逆轉(zhuǎn)，即將第二個(gè)指針指向第一個(gè)指針?biāo)傅刂?，而后將第一個(gè)指針指向第三個(gè)指針指向的節(jié)點(diǎn)的后件的地址。如此循環(huán)操
2、作直至head,p,q中的某一個(gè)指針指向末尾節(jié)點(diǎn)為止。此時(shí)三個(gè)指針依次指向最后三個(gè)節(jié)點(diǎn)。將此時(shí)最后兩個(gè)前后件關(guān)系逆轉(zhuǎn)，即將最后第二位的指針指向最后第三個(gè)指針指向的地址，又將最后一個(gè)指針指向最后第二個(gè)指針指向的地址。最后把head指針指向最后一個(gè)指針指向的地址。算法結(jié)束；最后把head指針保存的線性表順序輸出。對(duì)鏈表的一次逆轉(zhuǎn)操作（以head,p,q指針順序?yàn)槔?ààààà…h(huán)eadpq?ààà…Pqhead對(duì)線性鏈表最后三個(gè)節(jié)點(diǎn)前后件關(guān)系的逆轉(zhuǎn)(以最后三個(gè)節(jié)點(diǎn)為head,p,q指針順序?yàn)槔?：…àààheadpq…à??head
3、程序：#include#includestructnode{intd;structnode*next;};structnode*head;//創(chuàng)建全局變量指針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;//空鏈表或者單節(jié)點(diǎn)鏈表時(shí)逆轉(zhuǎn)不用操作if(head->next->next==NULL){p=head->next;head->next=NULL;p->next=head;head=p;return;}//兩節(jié)點(diǎn)列表時(shí)逆轉(zhuǎn)操作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;}}//逆轉(zhuǎn)線性表的函數(shù)voidprt_List(){structnode*p;p=head;while(p!=NULL){printf(“%d”,p->d)p=p->next;}}//順序輸出線性鏈表intmain(void){inti,n;List();//建立空鏈表scanf(“%d”,&n);//確定鏈表長(zhǎng)度f(wàn)or(i=1;i<=n;i++)ins_List();//將線性表已鏈表形式存
9、儲(chǔ)ch_List();//逆轉(zhuǎn)線性表操作prt_List();//將逆轉(zhuǎn)后的線性表順序輸出return0;}驗(yàn)證算法的實(shí)例及其運(yùn)算結(jié)果：5//n=554321//實(shí)際鏈表為1,2,3,4,5理論輸出：54321實(shí)際輸出：死循環(huán)，無(wú)輸出值，自己未能找到程序中的錯(cuò)誤。
