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