- 相關(guān)推薦
單鏈表逆置
單鏈表逆置
題目：創(chuàng)建一個(gè)單鏈表并且逆置單鏈表
完成日期：
一、需求分析
1、有一個(gè)單鏈表的第一個(gè)結(jié)點(diǎn)指針為head,編寫(xiě)一個(gè)函數(shù)將該單鏈表逆置,即最后一個(gè)結(jié)點(diǎn)變成第一個(gè)結(jié)點(diǎn),原來(lái)倒數(shù)第二個(gè)結(jié)點(diǎn)變成第二個(gè)結(jié)點(diǎn)。在逆置中不能建立新的單鏈表.
2、 程序執(zhí)行的命令包括：
（1）創(chuàng)建第一個(gè)單鏈表；（2）逆位序輸入n個(gè)元素的值，建立帶表頭節(jié)點(diǎn)的單鏈線性表L；
（3）逆置鏈表設(shè)置頭結(jié)點(diǎn)由指向第一個(gè)結(jié)點(diǎn)改成指向最后一個(gè)結(jié)點(diǎn)；（4）輸出銷毀。
3、測(cè)試數(shù)據(jù)
輸入： 10 9 8 7 6 5 4 3 2 1
二、概要設(shè)計(jì)
1、 鏈表的抽象數(shù)據(jù)類型定義為：
typedef struct LNode{
int data;
struct LNode* next;
}LNode, *LinkList;
/* 創(chuàng)建一個(gè)鏈表*/
void CreateList_1(LinkList *L, int n)
{
/*逆位序輸入n個(gè)元素的值，建立帶表頭節(jié)點(diǎn)的單鏈線性表L*/
int i;
LNode* p = NULL;
*L = (LinkList)malloc(sizeof(LNode));
(*L)->next = NULL; /*先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表*/
for (i = n; i > 0; --i)
{
p = (LinkList)malloc(sizeof(LNode)); /*生成新結(jié)點(diǎn)*/
scanf("%d", &(p->data));
p->next = (*L)->next;
(*L)->next = p;
}
}
2、本程序包含五個(gè)模塊：
（1）主程序模塊：
void main(){
定義頭結(jié)點(diǎn)；
創(chuàng)建一個(gè)鏈表；
輸出；
逆置；
輸出；
銷毀；
}
（2）逆位序輸入n個(gè)元素的值，建立帶表頭節(jié)點(diǎn)的單鏈線性表L
（3）先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表在生成新結(jié)點(diǎn)；
（4）輸出鏈表數(shù)據(jù)，逆置鏈表，設(shè)置頭結(jié)點(diǎn)由指向第一個(gè)結(jié)點(diǎn)改成指向最后一個(gè)結(jié)點(diǎn)；
（5）把結(jié)點(diǎn)1的指針域設(shè)置為NULL，最后返回L。
三、詳細(xì)設(shè)計(jì)
1、定義頭文件
#include
#include
2、 類型定義，類型聲明
typedef struct LNode{
int data;
struct LNode* next;
}LNode, *LinkList;
3、創(chuàng)建鏈表
void CreateList_1(LinkList *L, int n)
{
/*逆位序輸入n個(gè)元素的值，建立帶表頭節(jié)點(diǎn)的單鏈線性表L*/
int i;
LNode* p = NULL;
*L = (LinkList)malloc(sizeof(LNode));
(*L)->next = NULL; /*先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表*/
for (i = n; i > 0; --i)
{
p = (LinkList)malloc(sizeof(LNode)); /*生成新結(jié)點(diǎn)*/
scanf("%d", &(p->data));
p->next = (*L)->next;
(*L)->next = p;
}
}
/* 創(chuàng)建一個(gè)鏈表 2*/
LinkList CreateList( int n)
{
/*逆位序輸入n個(gè)元素的值，建立帶表頭節(jié)點(diǎn)的單鏈線性表L*/
int i;
LNode* p = NULL, *L=NULL;
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL; /*先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表*/
for (i = n; i > 0; --i)
{
p = (LinkList)malloc(sizeof(LNode)); /*生成新結(jié)點(diǎn)*/
scanf("%d", &(p->data));
p->next = L->next;
L->next = p;
}
return L;
}
/* 輸出鏈表數(shù)據(jù) */
void out_list(LinkList L)
{
LinkList p = NULL;
p = L->next;/*這里L(fēng)是帶頭結(jié)點(diǎn)的鏈表，所以p指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn)*/
while (p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
4、 逆置鏈表
LinkList reverse_List(LinkList L)
{
LinkList p, q, r;
/* 如果鏈表為空或者只有一個(gè)元素，直接返回該鏈表*/
if (L->next == NULL || L->next->next==NULL)
{
return L;
}
/*如何不為空，把所有結(jié)點(diǎn)的指針域由后指變成前指，如鏈表1->2->3->4的指針，變成1
/*例如，當(dāng)前鏈表為：head->頭結(jié)點(diǎn)->1->2->3->4->5->^*/
p = L ->next; /*p指向1*/
q = L->next->next;/*q指向2*/
while(q != NULL)
{
r = q->next;/*r指向3，作為一個(gè)臨時(shí)變量，防止指針斷鏈*/
q->next = p;/*開(kāi)始反向指向前繼元素： 14,別忘了這里r指向3，防止3后面的結(jié)點(diǎn)丟失*/
p = q;/*處理下一個(gè)*/
q = r;
}
/*設(shè)置頭結(jié)點(diǎn)由指向第一個(gè)結(jié)點(diǎn)改成指向最后一個(gè)結(jié)點(diǎn)*/
L->next->next = NULL;/*把結(jié)點(diǎn)1的指針域設(shè)置為NULL*/
L->next = p;
/*最后返回L*/
return L;
}
/*主函數(shù)*/
void main()
{
LinkList head = NULL;
int n =10;
/*創(chuàng)建一個(gè)鏈表*/
head=CreateList( n);
/*輸出*/
out_list(head);
/*逆置*/
head=reverse_List(head);
/*輸出*/
out_list(head);
system("pause");
}
四、調(diào)試分析
1、在創(chuàng)建一個(gè)單鏈表并且建立帶表頭節(jié)點(diǎn)的單鏈線性表L，這樣采用指針就能迅速存入數(shù)據(jù)，再逆位輸出數(shù)值。
2、在逆置中不能建立新的單鏈表，這里就要求生成一個(gè)新結(jié)點(diǎn)。
3、逆置鏈表時(shí)，如果鏈表為空或者只有一個(gè)元素，直接返回該鏈表。何不為空，把所有結(jié)點(diǎn)的指針域由后指變成前指，如鏈表1->2->3->4的指針，變成1頭結(jié)點(diǎn)單鏈表逆置->1->2->3->4->5->^ ，r = q->next; 指向作為一個(gè)臨時(shí)變量，防止指針斷鏈 q->next = p; 開(kāi)始反向指向前繼元素： 14,別忘了這里r指向，防止后面的結(jié)點(diǎn)丟失 p = q;處理下一個(gè) 。
4、逆置完成：設(shè)置頭結(jié)點(diǎn)由指向第一個(gè)結(jié)點(diǎn)改成指向最后一個(gè)結(jié)點(diǎn)，L->next->next = NULL;把結(jié)點(diǎn)1的指針域設(shè)置為NULL，L->next = p;最后返回L
五、運(yùn)行結(jié)果
六、實(shí)驗(yàn)環(huán)境
（1） 編程環(huán)境：VC6.0++
七、實(shí)驗(yàn)體會(huì)
通過(guò)本次實(shí)驗(yàn)我對(duì)于C語(yǔ)言,數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識(shí)有了更加深刻的理解，對(duì)于鏈表的使用也有了深刻的認(rèn)識(shí)。鍛煉了結(jié)合數(shù)據(jù)結(jié)構(gòu)思想來(lái)編寫(xiě)程序的能力，也增加了對(duì)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)相關(guān)知識(shí)的興趣。
【單鏈表逆置】相關(guān)文章：
唐代置觀制度述略04-27
如何置核能死地而后生04-29
手捧愛(ài)，置心尖作文04-17
逆襲的作文07-24
逆市調(diào)價(jià)?05-01
逆戰(zhàn)的作文09-05
順與逆作文07-21
水環(huán)境逆邊界逆動(dòng)態(tài)混合控制精確算法04-27
位置作文600位置作文12-16