数据结构与算法基础青岛大学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;
}

原创文章，作者：TNETJ，如若转载，请注明出处：https://www.506064.com/n/375399.html