數據結構------C語言經典題目（7）

1.系統棧和數據結構中的棧有什么區別？

????????1.本質：

? ? ? ? ? ? ? ? 系統棧：由程序運行時由操作系統自動分配的一塊連續內存區域，用于存儲函數調用過程中的臨時數據（參數、局部變量、返回地址），是程序運行的底層機制，遵循先進后出原則。

? ? ? ? ? ? ? ? 數據結構中的棧：是一種線性數據結構，定義了一組操作（壓棧、彈棧、查看棧頂），也遵循 先進后出 原則。

? ? ? ? 2.功能與用途：

? ? ? ? ? ? ? ? 系統棧：

? ? ? ? ? ? ? ? ? ?存儲函數調用時的 局部變量，保存函數的返回地址。傳遞函數調用的參數。支持遞歸調用。

示例：當函數A調用函數B時，系統會將A的當前狀態（局部變量值、返回地址）壓入棧，然后為B分配棧幀；B執行完畢后，棧會彈出A的狀態，恢復執行A。

? ? ? ? ? ? ? ? 數據結構中的棧：

????????? ? ? ? ? ? ?表達式求值、括號匹配、回溯算法等。

? ? ? ? 3.操作方式：

? ? ? ? ? ? ? ? 系統棧：

? ? ? ? ? ? ? ? ? ? ? ? 操作是隱式的，函數調用、返回、局部變量創建/銷毀等操作會自動觸發棧的壓入/彈出。

? ? ? ? ? ? ? ? 數據結構中的棧：操作是顯式的。需編寫實現代碼。

// 定義棧的最大容量
#define MAX_STACK_SIZE 100// 用數組實現棧（底層存儲結構）
// stack數組存儲棧元素，下標0為棧底，下標top為棧頂
int stack[MAX_STACK_SIZE];// top變量表示棧頂元素的索引：
// - 初始值-1表示棧為空（無有效元素）
// - 當壓入元素時，top先自增再賦值
// - 當彈出元素時，先返回top位置元素，再自減
int top = -1;// 壓棧操作：將元素value添加到棧頂
// 參數：value - 待壓入棧的整數值
// 說明：若棧已滿（top == MAX_STACK_SIZE - 1），則不執行壓棧操作
void push(int value) 
{// 檢查棧是否未滿（棧最大索引為MAX_STACK_SIZE-1）if (top < MAX_STACK_SIZE - 1) {// 先將棧頂指針上移一位，再存儲新元素（棧頂索引始終指向最后一個元素）stack[++top] = value;}
}// 彈棧操作：從棧頂取出并返回元素
// 返回值：棧頂元素（int類型），若棧空則返回-1（需根據業務調整錯誤處理）
// 說明：執行彈棧前需確保棧非空（調用前檢查top >= 0）
int pop() 
{// 檢查棧是否為空（棧空時top == -1）if (top >= 0) {// 先返回棧頂元素，再將棧頂指針下移一位return stack[top--];}// 棧空時返回-1（可根據實際需求定義錯誤碼）return -1; 
}

2.如何實現二叉樹的深度優先遍歷算法和廣度優先遍歷算法？

數據結構：

? ? ? ? 使用結構體TreeNode定義二叉樹節點，包含數據域和左右子節點指針。

深度優先遍歷：

? ? ? ? 前序遍歷：先訪問根節點，再遞歸遍歷左子樹，最后遞歸遍歷右子樹。

? ? ? ? 中序遍歷：左? ? ? ? ? ? 根? ? ? ? ? ? ? ? 右

? ? ? ? 后續遍歷：左? ? ? ? ? ? 右? ? ? ? ? ? ? ? 根

廣度優先遍歷：

? ? ? ? 使用數組模擬隊列實現層序遍歷。

? ? ? ? 根節點入隊----》循環取出隊首節點并訪問----》將其左右子節點依次入隊

? ? ? ? 測試構建的二叉樹結構：

    1/ \2   3/ \
4   5

示例代碼：

// ====================== 數據結構定義 ======================
/*** 二叉樹節點結構體定義* 包含：* - data: 節點存儲的整數值* - left: 指向左子節點的指針（NULL表示無左子節點）* - right: 指向右子節點的指針（NULL表示無右子節點）*/
typedef struct TreeNode {int data;               // 節點數據域struct TreeNode *left;  // 左子節點指針struct TreeNode *right; // 右子節點指針
} TreeNode;// ====================== 節點操作函數 ======================
/*** 創建二叉樹節點* @param data 節點存儲的整數值* @return 新創建的節點指針（動態分配內存）*/
TreeNode* createNode(int data) 
{// 分配節點內存空間TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));if (newNode == NULL)  // 內存分配失敗處理（實際項目中需增強錯誤處理）{ exit(EXIT_FAILURE);}newNode->data = data;       // 初始化數據域newNode->left = NULL;       // 初始化左子節點指針為NULLnewNode->right = NULL;      // 初始化右子節點指針為NULLreturn newNode;             // 返回新節點指針
}// ====================== 內存釋放函數 ======================
/*** 遞歸釋放二叉樹所有節點內存* 遵循后序遍歷順序：先釋放左子樹 → 釋放右子樹 → 釋放當前節點* @param root 待釋放的二叉樹樹根節點（NULL時直接返回）*/
void freeTree(TreeNode* root) 
{if (root == NULL) return; // 終止條件：空節點freeTree(root->left);  // 遞歸釋放左子樹freeTree(root->right); // 遞歸釋放右子樹free(root);            // 釋放當前節點內存root = NULL;           // 防止野指針（雖然此處即將離開作用域）
}// ====================== 深度優先遍歷（遞歸實現） ======================
/*** 前序遍歷（根左右）* 訪問順序：根節點 → 左子樹 → 右子樹* @param root 當前遍歷的子樹樹根節點（NULL表示空樹）*/
void preOrderTraversal(TreeNode* root) 
{if (root == NULL)         // 遞歸終止條件：遇到空節點{return;}printf("%d ", root->data); // 先訪問根節點preOrderTraversal(root->left); // 遞歸遍歷左子樹preOrderTraversal(root->right); // 遞歸遍歷右子樹
}/*** 中序遍歷（左根右）* 訪問順序：左子樹 → 根節點 → 右子樹* @param root 當前遍歷的子樹樹根節點（NULL表示空樹）*/
void inOrderTraversal(TreeNode* root) 
{if (root == NULL)         // 遞歸終止條件{    return;}inOrderTraversal(root->left); // 先遞歸遍歷左子樹printf("%d ", root->data); // 再訪問根節點inOrderTraversal(root->right); // 最后遞歸遍歷右子樹
}/*** 后序遍歷（左右根）* 訪問順序：左子樹 → 右子樹 → 根節點* @param root 當前遍歷的子樹樹根節點（NULL表示空樹）*/
void postOrderTraversal(TreeNode* root) 
{if (root == NULL)         // 遞歸終止條件{return;}postOrderTraversal(root->left); // 先遞歸遍歷左子樹postOrderTraversal(root->right); // 再遞歸遍歷右子樹printf("%d ", root->data); // 最后訪問根節點
}// ====================== 廣度優先遍歷（隊列實現） ======================
/*** 層序遍歷（廣度優先遍歷）* 訪問順序：按層次從左到右依次訪問節點（第1層→第2層→...）* @param root 二叉樹的根節點（NULL表示空樹）*/
void levelOrderTraversal(TreeNode* root) 
{if (root == NULL)         // 空樹處理{return;}// 使用數組模擬隊列（固定大小，適用于小規模樹，大規模建議用鏈表實現）TreeNode* queue[100];       // 隊列存儲節點指針int front = 0;              // 隊頭指針（指向當前出隊節點位置）int rear = 0;               // 隊尾指針（指向當前入隊位置的下一個位置）queue[rear++] = root;       // 根節點入隊（初始隊列包含根節點）while (front < rear)       // 隊列不為空時循環{    TreeNode* current = queue[front++]; // 取出隊首節點（先取值，再front自增）printf("%d ", current->data); // 訪問當前節點// 左子節點非空則入隊（保證層次順序）if (current->left != NULL) {    queue[rear++] = current->left;}// 右子節點非空則入隊（保證同層節點左到右順序）if (current->right != NULL) {queue[rear++] = current->right;}}
}// ====================== 測試用例 ======================
int main() 
{TreeNode* root = createNode(1);          // 根節點（值1）root->left = createNode(2);              // 根節點左子節點（值2）root->right = createNode(3);             // 根節點右子節點（值3）root->left->left = createNode(4);        // 左子節點的左子節點（值4）root->left->right = createNode(5);       // 左子節點的右子節點（值5）printf("前序遍歷（根左右）結果：");preOrderTraversal(root);                 // 輸出：1 2 4 5 3printf("\n");printf("中序遍歷（左根右）結果：");inOrderTraversal(root);                  // 輸出：4 2 5 1 3printf("\n");printf("后序遍歷（左右根）結果：");postOrderTraversal(root);                // 輸出：4 5 2 3 1printf("\n");printf("層序遍歷（廣度優先）結果：");levelOrderTraversal(root);               // 輸出：1 2 3 4 5printf("\n");printf("正在釋放二叉樹內存...\n");freeTree(root); // 調用釋放函數，遞歸釋放所有節點root = NULL;    // 清空根指針，確保不再訪問已釋放內存return 0;
}

3.滿二叉樹第K層有多少個節點？總共有多少個節點？

? ? ? ? 滿二叉樹的每一層節點數都達到最大值。第K層的節點數為 $_2{_{}^{k-1}}^{}$ 個。

? ? ? ? 將滿二叉樹的高度設為H（即共有H層），則總節點數為 $2_{}^{k} -1$ 個。

4.冒泡排序、插入排序、選擇排序、快速排序如何實現？

冒泡排序：??

/*** 冒泡排序函數* @param arr 待排序的整數數組* @param n 數組元素個數* 算法思想：重復走訪數組，比較相鄰元素，將較大的元素逐步后移* 時間復雜度：O(n2)，穩定排序算法*/void bubble_sort(int arr[], int n) 
{int i = 0；    //外層循環計數器（控制排序輪數），int j = 0;     //內層循環計數器（控制每輪比較次數）//int temp = 0;  //臨時變量用于交換元素// 外層循環：執行n-1輪排序（每輪確定一個最大元素到末尾）for (i = 0; i < n-1; i++) {// 內層循環：每輪比較相鄰元素，將最大元素逐步后移// 每輪結束后，第n-i-1個位置是當前未排序部分的最大元素for (j = 0; j < n-i-1; j++) {// 如果當前元素大于下一個元素，則交換位置if (arr[j] > arr[j+1]) {temp = arr[j];        // 保存當前元素值arr[j] = arr[j+1];    // 下一個元素移到當前位置arr[j+1] = temp;      // 當前元素移到下一個位置}}}
}

插入排序：

/*** 插入排序函數* @param arr 待排序的整數數組* @param n 數組元素個數* 算法思想：將未排序元素插入到已排序部分的合適位置，使已排序部分始終有序* 時間復雜度：O(n2)，穩定排序算法*/
void insertion_sort(int arr[], int n) 
{int i = 0;                    //未排序部分起始索引   int key = 0;                  //待插入的當前元素int j = 0;                    //已排序部分反向遍歷索引// 外層循環：從第二個元素開始（假設第一個元素已排序）for (i = 1; i < n; i++) {key = arr[i]; // 保存當前待插入的元素j = i - 1;    // 已排序部分的最后一個元素索引// 內層循環：將已排序部分中大于key的元素后移，為key騰出位置// 當j>=0且當前元素大于key時，繼續后移while (j >= 0 && arr[j] > key) {arr[j+1] = arr[j]; // 元素后移一位j--;               // 向前移動一位繼續比較}arr[j+1] = key; // 將key插入到正確位置（j+1是因為循環結束時arr[j] <= key）}
}

選擇排序：

/*** 選擇排序函數* @param arr 待排序的整數數組* @param n 數組元素個數* 算法思想：每輪找到未排序部分的最小元素，與當前位置元素交換* 時間復雜度：O(n2)，不穩定排序算法*/
void selection_sort(int arr[], int n) 
{int i = 0;                      //已排序部分末尾索引  int j = 0;                      //未排序部分遍歷索引int min_idx = 0;                //最小元素索引int temp = 0;                   //臨時變量用于交換// 外層循環：控制已排序部分的末尾位置（從0到n-2）for (i = 0; i < n-1; i++) {min_idx = i; // 初始化最小元素索引為當前位置// 內層循環：在未排序部分（i+1到n-1）尋找最小元素索引for (j = i+1; j < n; j++) {if (arr[j] < arr[min_idx])  // 如果找到更小的元素，更新最小索引{   min_idx = j;}}// 交換最小元素與當前位置元素（將最小元素放到已排序部分末尾）temp = arr[min_idx];arr[min_idx] = arr[i];arr[i] = temp;}
}

快速排序：

/*** 快速排序輔助函數：分區操作* @param arr 待分區的整數數組* @param low 分區起始索引* @param high 分區結束索引* @return 分區點索引（基準元素的最終位置）* 算法思想：選擇基準元素，將數組分為兩部分，左邊<=基準，右邊>=基準*/
int partition(int arr[], int low, int high) 
{int pivot = arr[high];  // 選擇最后一個元素作為基準值int i = (low - 1);     // 初始化最小元素索引為low-1（表示已處理部分的末尾）// 遍歷low到high-1的元素，將小于等于基準的元素移到左邊for (int j = low; j <= high - 1; j++) {// 如果當前元素小于等于基準值if (arr[j] <= pivot) {    i++;  // 最小元素索引遞增（指向當前處理的左邊區域的下一個位置）// 交換arr[i]和arr[j]，將較小元素移到左邊int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 將基準元素放到正確的位置（左邊區域的末尾+1），完成分區int temp = arr[i+1];arr[i+1] = arr[high];arr[high] = temp;return (i + 1); // 返回基準元素的最終位置
}/*** 快速排序主函數* @param arr 待排序的整數數組* @param low 排序起始索引* @param high 排序結束索引* 算法思想：分治策略，通過分區將數組分為兩部分，遞歸排序子數組* 平均時間復雜度：O(n log n)，最壞O(n2)，不穩定排序算法*/
void quick_sort(int arr[], int low, int high) 
{if (low < high)  // 終止條件：當子數組長度>=2時繼續處理{// 獲取分區點，將數組分為左右兩部分int pi = partition(arr, low, high);// 遞歸排序左子數組（low到pi-1）和右子數組（pi到high）quick_sort(arr, low, pi - 1);quick_sort(arr, pi, high);}
}

主函數：

/*** 打印數組函數* @param arr 待打印的整數數組* @param size 數組元素個數*/
void print_array(int arr[], int size) 
{int i = 0;for (i = 0; i < size; i++) {printf("%d ", arr[i]); // 逐個打印數組元素}printf("\n"); // 換行
}int main() 
{int arr[] = {64, 34, 25, 12, 22, 11, 90}; // 測試用數組int n = sizeof(arr) / sizeof(arr[0]);    // 計算數組元素個數printf("原始數組: ");print_array(arr, n); // 打印排序前的數組// 選擇要測試的排序算法（取消注釋對應函數調用）// bubble_sort(arr, n);        // 冒泡排序// selection_sort(arr, n);     // 選擇排序// insertion_sort(arr, n);     // 插入排序quick_sort(arr, 0, n-1);       // 快速排序（注意快速排序需要傳入low=0和high=n-1）printf("排序后的數組: ");print_array(arr, n); // 打印排序后的數組return 0;
}