單鏈表逆置

時間：2023-05-01 08:06:27 資料我要投稿

相關推薦

單鏈表逆置

題目：創建一個單鏈表并且逆置單鏈表

完成日期：

一、需求分析

1、有一個單鏈表的第一個結點指針為head,編寫一個函數將該單鏈表逆置,即最后一個結點變成第一個結點,原來倒數第二個結點變成第二個結點。在逆置中不能建立新的單鏈表.

2、程序執行的命令包括：

（1）創建第一個單鏈表；（2）逆位序輸入n個元素的值，建立帶表頭節點的單鏈線性表L；

（3）逆置鏈表設置頭結點由指向第一個結點改成指向最后一個結點；（4）輸出銷毀。

3、測試數據

輸入： 10 9 8 7 6 5 4 3 2 1

二、概要設計

1、鏈表的抽象數據類型定義為：

typedef struct LNode{

int data;

struct LNode* next;

}LNode, *LinkList;

/* 創建一個鏈表*/

void CreateList_1(LinkList *L, int n)

{

/*逆位序輸入n個元素的值，建立帶表頭節點的單鏈線性表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(){

定義頭結點；

創建一個鏈表；

輸出；

逆置；

輸出；

銷毀；

}

（2）逆位序輸入n個元素的值，建立帶表頭節點的單鏈線性表L

（3）先建立一個帶頭結點的單鏈表在生成新結點；

（4）輸出鏈表數據，逆置鏈表，設置頭結點由指向第一個結點改成指向最后一個結點；

（5）把結點1的指針域設置為NULL，最后返回L。

三、詳細設計

1、定義頭文件

#include

2、類型定義，類型聲明

typedef struct LNode{

int data;

struct LNode* next;

}LNode, *LinkList;

3、創建鏈表

void CreateList_1(LinkList *L, int n)

{

/*逆位序輸入n個元素的值，建立帶表頭節點的單鏈線性表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*/

LinkList CreateList( int n)

{

/*逆位序輸入n個元素的值，建立帶表頭節點的單鏈線性表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;

}

/* 輸出鏈表數據 */

void out_list(LinkList L)

{

LinkList p = NULL;

p = L->next;/*這里L是帶頭結點的鏈表，所以p指向第一個數據結點*/

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;

}

/*主函數*/

void main()

{

LinkList head = NULL;

int n =10;

/*創建一個鏈表*/

head=CreateList( n);

/*輸出*/

out_list(head);

/*逆置*/

head=reverse_List(head);

/*輸出*/

out_list(head);

system("pause");

}

四、調試分析

1、在創建一個單鏈表并且建立帶表頭節點的單鏈線性表L，這樣采用指針就能迅速存入數據，再逆位輸出數值。

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

五、運行結果

六、實驗環境

（1）編程環境：VC6.0++

七、實驗體會

通過本次實驗我對于C語言,數據結構的相關知識有了更加深刻的理解，對于鏈表的使用也有了深刻的認識。鍛煉了結合數據結構思想來編寫程序的能力，也增加了對于學習數據結構相關知識的興趣。

【單鏈表逆置】相關文章：

唐代置觀制度述略04-27

如何置核能死地而后生04-29

手捧愛，置心尖作文04-17

逆襲的作文07-24

逆市調價?05-01