數據結構與演算法基礎青島大學PPT解析

本文將從多個方面對數據結構與演算法基礎青島大學PPT進行詳細的闡述，包括數據類型、集合類型、排序演算法、字元串匹配和動態規劃等內容。通過對這些內容的解析，讀者可以更好地了解數據結構與演算法的基礎知識，掌握其基本應用，提高編程能力。

一、數據類型

數據類型是編程語言中最基本的概念之一，它決定了變數在內存中分配的大小和數據存儲的格式。在C語言中，主要包括以下幾種數據類型：

int：整型變數，通常佔用4個位元組的內存空間。例如：int a = 10;

float：單精度浮點型變數，通常佔用4個位元組的內存空間。例如：float b = 10.0;

double：雙精度浮點型變數，通常佔用8個位元組的內存空間。例如：double c = 10.0;

char：字元型變數，通常佔用1個位元組的內存空間。例如：char d = 'A';

在數據類型的選擇上，需要根據業務需求和系統平台來進行權衡和選擇。例如，C語言中的int類型在32位和64位平台上的存儲方式是不同的，在進行跨平台開發時需注意。

二、集合類型

集合類型是常用的數據結構之一，它包括數組和鏈表等。在C語言中，數組是一組相同類型的變數集合，它們在內存中連續存放，並且可以通過下標訪問。例如，下面的代碼是一個長度為5的整型數組：

int arr[]={1,2,3,4,5};

鏈表是一組通過指針連接的節點集合，它們在內存中不一定是連續存放的，每個節點包含數據和一個指向下一個節點的指針。鏈表的插入和刪除操作比數組更高效，但是訪問速度較慢。例如，下面的代碼是一個簡單的鏈表結構體：

struct ListNode {
    int val;
    struct ListNode *next;
};

三、排序演算法

排序演算法是數據處理中常用的演算法之一，它可以將一組無序的數據按照某種規則重新排列。常見的排序演算法包括冒泡排序、選擇排序、插入排序、歸併排序和快速排序等。

以快速排序為例，它的原理是通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字小於另一部分關鍵字。然後分別對這兩部分記錄繼續進行快速排序，以達到整個序列有序的目的。

// 快速排序遞歸函數
void quickSort(int arr[], int left, int right) {
    int i = left, j = right;
    int pivot = arr[(left + right) / 2];
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    if (left < j) quickSort(arr, left, j);
    if (right > i) quickSort(arr, i, right);
}

四、字元串匹配

字元串匹配是在一個長字元串（稱為主串）中查找一個短字元串（稱為模式串）的過程，它在計算機科學中有著廣泛的應用。常見的字元串匹配演算法包括樸素演算法、KMP演算法和Boyer-Moore演算法等。

以KMP演算法為例，它的原理是通過預處理模式串來快速匹配主串中的子串。具體來說，KMP演算法通過計算模式串的最長公共前綴和最長公共後綴數組，來確定每次匹配失敗後模式串應該向右移動的位數。

// KMP演算法
int kmp(char* s, char* p) {
    int lenS = strlen(s), lenP = strlen(p);
    int* next = (int*)malloc(sizeof(int) * lenP);
    getNext(p, next);
    int i = 0, j = 0;
    while (i < lenS && j < lenP) {
        if (j == -1 || s[i] == p[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j == lenP) {
        return i - j;
    } else {
        return -1;
    }
}

五、動態規劃

動態規劃是一種常用的優化演算法，它通過將問題拆分成多個子問題，最終得到全局最優解。常見的動態規劃問題包括最長遞增子序列、背包問題和最短路徑問題等。

以最長遞增子序列為例，它的原理是通過動態規劃求出以每個位置為結尾的最長遞增子序列長度，並將其與之前的結果比較，最終得到全局最優解。

// 最長遞增子序列
int lengthOfLIS(int* nums, int numsSize) {
    int* dp = (int*)malloc(sizeof(int) * numsSize);
    int res = 0;
    for (int i = 0; i < numsSize; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = fmax(dp[i], dp[j] + 1);
            }
        }
        res = fmax(res, dp[i]);
    }
    return res;
}