單鏈表逆置(共5頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 單鏈表逆置 題目：創(chuàng)建一個單鏈表并且逆置單鏈表 完成日期：2014-09-17一、需求分析 1、有一個單鏈表的第一個結(jié)點指針為head,編寫一個函數(shù)將該單鏈表逆置,即最后一個結(jié)點變成第一個結(jié)點,原來倒數(shù)第二個結(jié)點變成第二個結(jié)點。在逆置中不能建立新的單鏈表.2、 程序執(zhí)行的命令包括：（1）創(chuàng)建第一個單鏈表；（2）逆位序輸入n個元素的值，建立帶表頭節(jié)點的單鏈線性表L； （3）逆置鏈表設(shè)置頭結(jié)點由指向第一個結(jié)點改成指向最后一個結(jié)點；（4）輸出銷毀。 3、測試數(shù)據(jù) 輸入： 10 9 8 7 6 5 4 3 2 1二、概要設(shè)計1、 鏈表的抽象數(shù)據(jù)類型定義為： typedef

2、struct LNode int data; struct LNode* next; LNode, *LinkList;/* 創(chuàng)建一個鏈表*/void CreateList_1(LinkList *L, int n) /*逆位序輸入n個元素的值，建立帶表頭節(jié)點的單鏈線性表L*/int i;LNode* p = NULL;*L = (LinkList)malloc(sizeof(LNode);(*L)-next = NULL; /*先建立一個帶頭結(jié)點的單鏈表*/for (i = n; i 0; -i)p = (LinkList)malloc(sizeof(LNode); /*生成新結(jié)點*/sca

3、nf(%d, &(p-data);p-next = (*L)-next;(*L)-next = p; 2、本程序包含五個模塊：（1）主程序模塊：void main()定義頭結(jié)點；創(chuàng)建一個鏈表；輸出；逆置；輸出；銷毀；（2）逆位序輸入n個元素的值，建立帶表頭節(jié)點的單鏈線性表L（3）先建立一個帶頭結(jié)點的單鏈表在生成新結(jié)點；（4）輸出鏈表數(shù)據(jù)，逆置鏈表，設(shè)置頭結(jié)點由指向第一個結(jié)點改成指向最后一個結(jié)點；（5）把結(jié)點1的指針域設(shè)置為NULL，最后返回L。 三、詳細(xì)設(shè)計1、定義頭文件 #include #include 2、 類型定義，類型聲明typedef struct LNodeint data;st

4、ruct LNode* next;LNode, *LinkList;3、創(chuàng)建鏈表 void CreateList_1(LinkList *L, int n)/*逆位序輸入n個元素的值，建立帶表頭節(jié)點的單鏈線性表L*/int i;LNode* p = NULL;*L = (LinkList)malloc(sizeof(LNode);(*L)-next = NULL; /*先建立一個帶頭結(jié)點的單鏈表*/for (i = n; i 0; -i)p = (LinkList)malloc(sizeof(LNode); /*生成新結(jié)點*/scanf(%d, &(p-data);p-next = (*L)-

5、next;(*L)-next = p;/* 創(chuàng)建一個鏈表 2*/LinkList CreateList( int n)/*逆位序輸入n個元素的值，建立帶表頭節(jié)點的單鏈線性表L*/int i;LNode* p = NULL, *L=NULL;L = (LinkList)malloc(sizeof(LNode);L-next = NULL; /*先建立一個帶頭結(jié)點的單鏈表*/for (i = n; i 0; -i)p = (LinkList)malloc(sizeof(LNode); /*生成新結(jié)點*/scanf(%d, &(p-data);p-next = L-next;L-next = p;r

6、eturn L;/* 輸出鏈表數(shù)據(jù) */void out_list(LinkList L)LinkList p = NULL;p = L-next;/*這里L(fēng)是帶頭結(jié)點的鏈表，所以p指向第一個數(shù)據(jù)結(jié)點*/while (p != NULL)printf(%d , p-data);p = p-next;printf(n);4、 逆置鏈表 LinkList reverse_List(LinkList L)LinkList p, q, r;/* 如果鏈表為空或者只有一個元素，直接返回該鏈表*/if (L-next = NULL | L-next-next=NULL)return L;/*如何不為空，把

7、所有結(jié)點的指針域由后指變成前指，如鏈表1-2-3-4的指針，變成1-2-3頭結(jié)點-1-2-3-4-5-*/p = L -next; /*p指向1*/q = L-next-next;/*q指向2*/while(q != NULL)r = q-next;/*r指向3，作為一個臨時變量，防止指針斷鏈*/q-next = p;/*開始反向指向前繼元素： 14,別忘了這里r指向3，防止3后面的結(jié)點丟失*/p = q;/*處理下一個*/q = r;/*設(shè)置頭結(jié)點由指向第一個結(jié)點改成指向最后一個結(jié)點*/L-next-next = NULL;/*把結(jié)點1的指針域設(shè)置為NULL*/L-next = p;/*最后

8、返回L*/return L;/*主函數(shù)*/void main()LinkList head = NULL;int n =10;/*創(chuàng)建一個鏈表*/head=CreateList( n);/*輸出*/out_list(head);/*逆置*/head=reverse_List(head);/*輸出*/out_list(head);system(pause);四、調(diào)試分析1、在創(chuàng)建一個單鏈表并且建立帶表頭節(jié)點的單鏈線性表L，這樣采用指針就能迅速存入數(shù)據(jù)，再逆位輸出數(shù)值。 2、在逆置中不能建立新的單鏈表，這里就要求生成一個新結(jié)點。3、逆置鏈表時，如果鏈表為空或者只有一個元素，直接返回該鏈表。何不為空，把所有結(jié)點的指針域由后指變成前指，如鏈表1-2-3-4的指針，變成1-2-3頭結(jié)點-1-2-3-4-5- ，r = q-next; 指向作為一個臨時變量，防止指針斷鏈 q-next = p; 開始反向指向前繼元素： 14,別忘了這里r指向，防止后面的結(jié)點丟失 p = q;處理下一個 。4、逆置完成：設(shè)置頭結(jié)點由指向第一個結(jié)點改成指向最后一個結(jié)點，L-next-next = NULL;把結(jié)點1的指針域設(shè)置為NULL，L-next = p;最