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