【GL07】C语言要点
1.C语言中的结构体
（1）使用struct关键字
struct Student {
int id; // 学生ID
char name[50]; // 学生姓名
float score; // 学生成绩
};
用法：
struct Student student1; // 创建一个Student类型的变量student1
（2）使用typedef关键字
typedef struct {
int id;
char name[50];
float score;
} Student; // 现在你可以直接使用Student作为类型名，而不需要每次都写struct
用法：
Student student3 = {3, "guilin", 95.0f}; // 使用typedef定义的结构体类型的变量 2.常用排序算法
（1）冒泡排序（Bubble Sort）
通过对待排序序列从前向后（或从后向前），依次比较相邻元素的值，若发现逆序则交换，使值较大（或较小）的元素逐渐从前移向后（或从后移向前），就像水底的气泡一样逐渐向上冒。它的时间复杂度：平均和最坏情况都是O(n^2)，最好情况是O(n)（但这种情况很少出现）。冒泡排序是一种交换排序，冒泡排序是从第一个元素开始，相邻的两个数俩俩比较，若后面一个数大于（小于）前一个数则交换，一直到把每趟的最大（小）元素都排在末尾。下面以最大为例：
#include <stdio.h>
void bubbleSort(int arr[], int n)
{
int i, j, temp;
for (i = 0; i < n-1; i++) { // 每次遍历都会将一个最大值移动到数组的末尾
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;
}
}
}
}
void printArray(int arr[], int size) // 数组打印
{
for (int 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("排序前的数组: \n");
printArray(arr, n);
bubbleSort(arr, n); //冒泡排序算法
printf("排序后的数组: \n");
printArray(arr, n);
return 0;
}
（2）快速排序（Quick Sort）
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。他打时间复杂度：平均O(n log n)，最坏O(n^2)（但可以通过随机化等方式优化）。下面是算法实现：
#include <stdio.h>
// 交换两个元素
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
// 分区函数（左边小右边大），选择最后一个元素作为中心点
int partition(int arr[], int low, int high)
{
int pivot = arr[high]; // 中心元素
int i = (low - 1); // 小于中心点的元素的索引
for (int j = low; j <= high - 1; j++) {
// 如果当前元素小于或等于中心点
if (arr[j] <= pivot) {
i++; // 将小于中心点的元素放在正确位置
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]); // 把中心点放到正确位置
return (i + 1); // 返回中心位置
}
// 快速排序主函数
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
// pi 是分区索引，arr[pi] 已经被放在了正确的位置
int pi = partition(arr, low, high);
// 分别对左右子数组进行快速排序
quickSort(arr, low, pi - 1); // 左子数组
quickSort(arr, pi + 1, high); // 右子数组
}
}
// 输出数组
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("排序前的数组: \n");
printArray(arr, n);
quickSort(arr, 0, n - 1);
printf("排序后的数组: \n");
printArray(arr, n);
return 0;
}
（3）希尔排序（Shell's Sort）
称为缩小增量排序（Diminishing Increment Sort），是插入排序的一种更高效的改进版本，由美国计算机科学家Donald Shell于1959年提出。希尔排序通过将原始记录序列分割成若干个子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序，从而提高了排序效率。
希尔排序的基本思想是将待排序的数组元素按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。这种方法实质上是一种分组插入方法。
排序过程：确定增量：首先确定一个初始的增量（这个增量的选择对排序效率有很大影响），通常可以选择数组长度的一半作为初始增量。分组排序：根据当前增量将数组分成若干个子序列，每个子序列由下标差值为增量的元素组成。对每个子序列进行直接插入排序。减小增量：完成一轮排序后，减小增量值，继续对新的子序列进行排序。重复步骤：重复上述分组排序和减小增量的过程，直到增量为1，此时整个数组恰被分成一组，进行最后一次直接插入排序。
算法代码：
#include <stdio.h>
// 希尔排序函数
void shellSort(int arr[], int n)
{
// 开始时将增量设置为数组长度的一半
for (int gap = n / 2; gap > 0; gap /= 2) {
// 对每个子数组进行插入排序
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
// 通过增量 gap 进行分组，并进行插入排序
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
// 输出数组
void printArray(int arr[], int size)
{
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int arr[] = {12, 34, 54, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
printf("排序前的数组: \n");
printArray(arr, n);
shellSort(arr, n);
printf("排序后的数组: \n");
printArray(arr, n);
return 0;
}
（4）插入排序（Insertion Sort）
将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
#include <stdio.h>
// 插入排序函数
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i]; // 选择未排序序列的第一个元素作为关键字
j = i - 1;
/* 将大于key的元素向后移动一位 */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key; // 插入key到正确的位置
}
}
// 打印数组
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// 主函数来测试上述代码
int main()
{
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}3.C语言 - - 指针
C语言中的指针是C语言编程中非常重要和强大的概念之一。指针是一个变量，它存储的不是数据本身，而是数据的内存地址。通过使用指针，你可以直接访问和操作内存中的数据。
（1）如何在C语言中正确初始化一个指针变量？
int *ptr = NULL; // 1.初始化为NULL
int value = 10;
int *ptr = &value; // 2.初始化为具体的内存地址
int *ptr = (int *)malloc(sizeof(int));
if (ptr != NULL) {
*ptr = 10;
} // 3.初始化为动态分配的内存
char str[] = "hello";
char *ptr = str; // 4.初始化为数组或字符串
int *ptr = function_that_returns_pointer(); // 5.初始化为函数返回的指针
// 函数指针案例
#include <stdio.h>
#include <time.h>
int * getRandom( )
{
static int r[10];
int i;
srand( (unsigned)time( NULL ) );
for ( i = 0; i < 10; ++i) {
r[i] = rand();
printf("%d\n", r[i] );
}
return r;
}
int main ()
{
int *p;
int i;
p = getRandom();
for ( i = 0; i < 10; i++ ) {
printf("*(p + [%d]) : %d\n", i, *(p + i) );
}
return 0;
}
（2）为什么要避免在C语言编程中使用野指针？
在C语言编程中，避免使用野指针（dangling pointer）是因为野指针可能导致程序崩溃、数据损坏或安全漏洞。野指针是指指向已经被释放或不再有效的内存地址的指针。当程序尝试通过野指针访问或修改内存时，可能会发生不可预测的行为，因为该内存区域可能已经被分配给其他数据或程序，或者已经被操作系统回收。
使用野指针的风险包括：
- 程序崩溃：尝试解引用野指针可能会导致程序立即终止，因为操作系统检测到非法内存访问。
- 数据损坏：野指针可能会覆盖其他变量的值，导致程序逻辑错误或数据不一致。
- 安全漏洞：攻击者可能会利用野指针来执行恶意代码，从而获得对系统的未授权访问。
4.C语言内存管理
C语言中的内存管理是一个关键且复杂的主题，它直接关系到程序的性能和稳定性。C语言本身提供了几种基本的方式来管理内存，主要是使用 malloc、calloc、realloc 和 free 函数。这些函数是在标准库 <stdlib.h> 中定义的。
| 函数 | 说明 |
|---|---|
| void *calloc(int num, int size); | 此函数分配一个num元素数组，每个元素的大小（以字节为单位）将为size。 |
| void free(void *address); | 此函数释放由地址指定的存储块。 |
| void *malloc(int num); | 此函数分配一个num个字节的数组，并使它们未初始化。 |
| void *realloc(void *address, int newsize); | 此函数重新分配内存，将其扩展到新大小。 |
示例：
#include <stdio.h>
#include <stdlib.h>
int main()
{
int *ptr = (int*)malloc(sizeof(int) * 5); // 分配内存
if (ptr == NULL) {
fprintf(stderr, "内存分配失败\n");
return 1;
}
for (int i = 0; i < 5; i++) {
ptr[i] = i * i; // 使用内存
}
for (int i = 0; i < 5; i++) {
printf("%d ", ptr[i]); // 输出内容
}
free(ptr); // 释放内存
ptr = NULL; // 避免野指针
return 0;
} 这个例子展示了如何使用 malloc 分配内存，如何使用这块内存，以及最后如何释放它。