---

一，問題描述

在數據處理中，常常會遇到需要對鏈接存儲的線性表進行操作的情況。本次任務聚焦于將鏈接存儲的線性表進行逆置。具體來說，就是要改變線性表中結點的順序，使得原來的最后一個結點變為新線性表的第 1 個結點，原來倒數第 2 個結點變為新線性表的第 2 個結點，依此類推，從而實現整個線性表的逆置。

二，基本要求

1. 算法分析與設計：對鏈表逆置問題進行深入分析，考慮到可能存在帶附加表頭結點和不帶附加表頭結點這兩種不同情況。對于帶附加表頭結點的鏈表，表頭結點不存儲實際數據，僅作為鏈表的起始標志，在逆置過程中需要特殊處理，以保證表頭結點的位置和指向關系正確；對于不帶附加表頭結點的鏈表，逆置時要特別注意第一個結點的處理，以及如何正確更新指針，確保鏈表的完整性和正確性。分別設計出針對這兩種情況的高效算法，明確算法的邏輯步驟和操作流程。
2. 編寫完整上機程序：使用 C++ 語言，根據設計好的算法，編寫完整的程序代碼。在程序中，要清晰地定義鏈表的節點結構，包括數據域和指針域。實現鏈表的創建、逆置以及輸出等功能函數，確保函數之間的調用關系正確，代碼結構清晰易讀。同時，要合理處理內存分配和釋放問題，避免內存泄漏。
3. 設計測試用例并上機驗證：精心設計多種測試用例，涵蓋不同長度的鏈表、包含不同數據的鏈表以及特殊情況（如空鏈表、只有一個結點的鏈表等）的鏈表。通過上機運行程序，輸入各種測試用例，觀察程序的運行結果，驗證程序是否能夠正確地對鏈表進行逆置操作。
4. 記錄測試結果，對測試結果進行分析：詳細記錄每個測試用例的輸入和輸出結果，包括鏈表的原始狀態和逆置后的狀態。對測試結果進行深入分析，檢查程序在不同情況下的運行是否符合預期，是否存在邏輯錯誤或異常情況。比較帶附加表頭結點和不帶附加表頭結點兩種情況下算法的執行效率、代碼復雜度等方面的差異，總結兩種方法的優缺點，為今后在實際應用中選擇合適的鏈表結構和算法提供參考。

三，算法分析

1. 不帶附加表頭結點的鏈表逆置算法：
   • 初始化三個指針：prev 指向 NULL，表示當前結點的前一個結點；curr 指向鏈表的頭結點，即第一個實際存儲數據的結點；next 用于臨時存儲 curr 的下一個結點。
   • 遍歷鏈表，在每次循環中，先將 next 指向 curr 的下一個結點，然后將 curr 的 next 指針指向 prev，更新 prev 為 curr，curr 為 next。
   • 當 curr 變為 NULL 時，說明已經遍歷到鏈表的末尾，此時 prev 指向的就是逆置后鏈表的頭結點，完成逆置操作。
2. 帶附加表頭結點的鏈表逆置算法：
   • 同樣初始化三個指針：prev 指向附加表頭結點；curr 指向附加表頭結點的下一個結點，即第一個實際存儲數據的結點；next 用于臨時存儲 curr 的下一個結點。
   • 遍歷鏈表，在每次循環中，先將 next 指向 curr 的下一個結點，然后將 curr 的 next 指針指向 prev，更新 prev 為 curr，curr 為 next。
   • 當 curr 變為 NULL 時，說明已經遍歷到鏈表的末尾，此時需要將附加表頭結點的 next 指針指向 prev，完成逆置操作。注意在整個過程中，附加表頭結點始終存在且位置不變，只是其 next 指針指向發生了變化。

四，示例代碼

#define STACK_INIT_SIZE  100    // 棧存儲空間初始分配量
#define STACKINCREMENT  10     // 棧存儲空間分配增量
#define OVERFLOW -1
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0#include "stdio.h"
#include "malloc.h"
#include <stdlib.h>  // 添加這一行，引入 exit 函數的定義typedef int status;
typedef char SelemType;typedef struct {                       // 順序棧的定義SelemType *base;SelemType *top;int stacksize;
} SqStack;status InitStack(SqStack &S) {        // 構造一個空棧 SS.base = (SelemType *)malloc(STACK_INIT_SIZE * sizeof(SelemType));if (!S.base)exit(OVERFLOW);       // 存儲分配失敗S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;
}status Push(SqStack &S, SelemType e) {// 插入元素 e 為新的棧頂元素if (S.top - S.base >= S.stacksize) {         // 棧滿，追加存儲空間S.base = (SelemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SelemType));if (!S.base)exit(OVERFLOW);       // 存儲分配失敗S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;}*(S.top) = e;S.top++;return OK;
}status Pop(SqStack &S, SelemType &e) {// 若棧不空，則刪除 S 的棧頂元素，用 e 返回其值，并返回 OK；否則返回 ERRORif (S.top == S.base)return ERROR;S.top--;e = *(S.top);return OK;
}status StackEmpty(SqStack S) {         // 判斷棧 S 是否為空if (S.top == S.base)return TRUE;elsereturn FALSE;
}void conversion() {                    // 進制轉換// 對于輸入的任意一個非負十進制整數，打印輸出與其等值的對應的進制數SqStack S;int N, d, ys;SelemType x, e;InitStack(S);                      // 構造空棧while (1) {printf("請輸入一個非負十進制數(0結束)：");scanf("%d", &N);if (N == 0)break;printf("請輸入要轉換的進制：");scanf("%d", &d);   // 2、8 或 16 進制while (N) {                    // 輸出相應的符號ys = N % d;     // 求余if (ys <= 9)x = ys + '0';elsex = ys - 10 + 'A';Push(S, x);N = N / d;      // 求商}printf("轉換所得%d進制數為：", d);while (!StackEmpty(S)) {              // 顯示結果Pop(S, e);printf("%c", e);}printf("\n");}
}void main() {conversion();
}    

五，實驗操作

1.雙擊程序圖標，啟動程序。

2.新建項目。

3.選擇”空項目“——輸入項目名稱——單擊”確認“按鈕。

4.右擊”源文件“——”添加“——選擇”新建項“。

5.選擇”C++文件“——輸入文件名——單擊”添加“按鈕。

6.編寫代碼。

7.編譯代碼。

8.查看編譯結果。

9.單擊綠色小三角，運行項目。

六，運行效果

1.要求效果。

2.編寫程序，運行效果。