首页 南京大学软件工程专业课程 大一上 CPL

# 指针与数组

# 【一维数组】

  • int *arr <=> int arr[]

  • arr[i] <=> *(arr + i)

  • &arr[i] <=> &(*(arr + i)) <=> arr + i

  • 若 p 为指向 a[i] 的指针变量，则 p + 3 为指向 a[i + 3] 的指针变量，不是地址 + 3!

  • malloc 手搓数组（有 <stdlib.h> 库）： int *numbers = (int *)malloc(len * sizeof(*numbers));

  • 手搓数组后最后记得 free(numbers);

  • 数组不是指针，但是数组名确实代表了第一个元素的地址！

  • 举个例子，手搓数组可以 arr++ 使指针移动，但是直接 * arr[] * 出来的数组不可以 arr++

# 【交换函数（指针的常见用法）】

c
void Swap(int *left, int *right)
{
    int temp = *left;
    *left = *right;// 将 right 指针指向的值赋值给 left 指针指向的值
    *right = temp;
}

# 【数组与字符串】

# 手搓字符串的两种不同方式

c
char *ptr_msg = "Hello World!"; // 定义指针指向该字符串。就是手搓数组，不过改不了元素
// 指向静态变量，只读，不能修改
ptr_msg[0] = 'N'; // 错误操作
char msg[] = "Hello World!";
msg[0] = 'N';
printf("%s\n", msg);
// 这种可以修改
# 【常见 string 库函数用法】
# strlen 读取字符串长短函数
手搓一个 strlen 函数：
c
int Strlen(const char *str)
{
    int len = 0;
    while (str[len ] != '\0')
    {
        len++;
    }
    return len;
}
# strcpy 字符串复制函数
手搓一个
c
void StrCpy2(char *dest, const char *src)
{
    int i = 0;
    while ((*(dest + i) = *(src + i)) != '\0') // 先赋值，再比较 dest [i] 是否为 '\0'
    {
        i++;
    }
}
* 对于标准库里的 strcpy 函数，返回值类型为 char ，即将复制后的字符串返回了，所以可以直接用
# strcmp 比较两个字符串第一个不同元素 ascii 值大小函数
一般用于比较两个字符串相不相等了，相等返回 0，前面大于后面返回正数，反之负数。 在作业里出现了一种它的用法，即从一堆字符串里面找有没有我要的那个字符串
# strtok 字符串分割函数
直接看具体应用（函数原理看 cpp 网站）
c
//arr,cut 都是字符串。arr 是原字符串，cut 是目标剪掉的字符串。该程序将 arr 字符串切成若干部分放在 tokens 数组里，count 为切后字符串数目
char *tokens[103];
char *token = strtok(arr, cut);
int i = 0;
while (token != NULL && i < 1000)
{
    tokens[i] = token;
    i++;
    token = strtok(NULL, cut);
}
int count = i;
token = strtok(NULL, cut); 是什么意思？
若 str 为空指针，则将调用当做对 strtok 的后继调用，函数从先前调用中它剩下的位置开始。 行为如同将先前存储的指针作为 str 传递
# strstr 查找首个目标字符串出现位置函数
void find_str(char const *str, char const *substr)
{
char *pos = strstr(str, substr);
pos ? printf("found the string '%s' in '%s' at position %td\n",
    substr, str, pos - str)
    : printf("the string '%s' was not found in '%s'\n",
    substr, str);
}
# strcat 字符串拼接函数
char *strcat( char *dest, const char *src );
返回值是 dest 。会改变 dest 指向的内容
# 【指针数组】
如：
const char *musicians[] = {
            "Luo Dayou",
            "Cui Jian",
            "Dou Wei",
            "Zhang Chu",
            "Wan Qing",
            "Li Zhi",
            "Yao",
            "ZuoXiao",
            "ErShou Rose",
            "Hu Mage",
    };
这里的 const 保护的是指针所指向的字符串，并不是保护字符指针数组内的值不可修改
保护字符指针数组内的值： const char * const arr[]
musicians [0] 为指针数组内第 0 个字符串的首地址。但是 printf ("% s", arr [i]); 就可以直接打印出第 i 个字符串了。 这是为什么？
我的理解：这个地址已经直接指向字符串了，他不是一个存粹的地址，只有十六进制表示，而是一个有指向的指针。因此可以不用解地址符？
[] 的转换关系：
# char arr[] : char *arr
# char *arr[]: char **arr
# 【二维数组的指针形式】
**int table[][col]** : int (*table)[col] , table 是指针，指向一个 ** 长度为 col 类型为 int ** 的数组
另一种形式： int table[][col] <=> int[col] *table 。
即：table 是一个指针，它的具体类型是 ** int[col] * ，指向一个长度为 col 类型为 int ** 的数组
// 一个推导
             table[i][j] : *(*(table + i) + j)
             table : int (*)[]
             table + i : int (*)[]    // 指向数组的指针
             *(table + i) : int *     // 数组的首地址。与上一个指向同一个位置，但含义不一样。
             *(table + i) + j : int *
             *(*(table + i) + j) : int
# 【函数指针】
int (*comp)(const void *, const void *) = CompareInts;
声明一个 camp 函数指针，它所对应的函数的类型是 接收接受两个 const int * 类型指针，返回 int。
typedef int (*CompareFunction)(const void *, const void *);
将函数指针（接受两个 const int * 类型指针，返回 int 的类型）命名为 CompareFunction
更多的例子：
double Integrate(double low, double high, double (*func)(double));
    //func 是一个函数指针，指针指向函数，函数接受一个 double，返回一个 double
double (*funsarr[])(double) = {sin, cos};
    // 一个数组，存储类型为函数指针，该指针对应函数接受一个 double 类型，返回一个 double 类型
    //sin 不一定要取地址，sin 在这里被隐式地转成函数指针
函数指针的使用
double Integrate(double low, double high, double (*func)(double))
{
    double x = func(5); // 在这里不需要对 fun 解引用，因为被隐式地转成函数
    // 后面省略
}
integration = Integrate(low, high, sin); //sin 不一定要取地址，sin 在这里被隐式地转成函数指针
判断指针 or 函数 or 数组：
最关键的是看最里面的内容，结合运算符优先级
# 运算符优先级：() 函数调用 / [] 数组下标 > * 解引用
char **argv; // 指向指针的指针
int *names[10]; // 指针数组
int (*musician_score_table)[10]; // 指针，指向长度为 10 的数组
int *StrCpyStd(char *dest, const char *src); // 函数，接收一个 char * 与 const char *，返回 int *
int (*comp)(const void *left, const void *right); // 指针，指向一个接收两个 const void *，返回 int 的函数
int atexit(void (*func)(void)); // 函数，接受一个函数指针，返回 int
void (*signal(int sig, void (*handler)(int)))(int); 
// 函数，接收一个 int、一个函数指针（接收 int 返回 void 类型），返回一个函数指针（接收 int 返回 void 类型）
# 【qsort 用法与 bsearch 用法】
头文件： #include <stdlib.h>
qsort：
定义
void qsort( void *ptr, size_t count, size_t size,
            int (*comp)(const void *, const void *) );
// 参数分别是：要排序的数组，数组内元素个数，数组内单个元素大小，具体的排序准则（一个函数，要自己写）
//comp 函数参考：
int comp(const void *left, const void *right)
{
    int left_int = *(const int *)left; // 强制类型转换后解引用
    int right_int = *(const int *)right; // 强制类型转换后解引用
    return (left_int > right_int) - (left_int < right_int);
    // 如果左大于右，则返回 1 - 0 = 1. 其他类推
}
// 那么，在 qsort 中将会按照升序排序、
// 改成降序排序：将返回值取相反值
如果想要以结构数组中某一个元素的值为参考排序：
int CompareMusician(const void *m1, const void *m2)
{
    const Musician *left_m = m1;
    const Musician *right_m = m2;
    return strcmp(left_m->name, right_m->name);
//  改变比较对象即可。注意，这里 left_m 和 right_m 都是指针，所以不能用 "." 运算符，要用 "->"
// *(left_m).name <=> left_m->name
}
bsearch：
定义
void *bsearch(const void *key, const void *ptr, size_t count, size_t size,
            int (*comp)(const void*, const void*) );
// 参数分别是：要查找的对象的地址，查找的数组，数组内元素的个数，数组内单个元素的大小，comp 函数（这个函数这里必须要大于返回 1 了）
// 返回值是目标对象的地址。如果没找到，返回 NULL 空指针
// 要求：数组必须已经升序排序完成
//comp 函数参考：
int CompareStrs(const void *left, const void *right)
{
    char *const *pp1 = left;
    char *const *pp2 = right;
    return strcmp(*pp1, *pp2);
    // 必须要解引用！不然比较的是指针了
}
具体使用：
const char *names[] = {
        "Cui Jian",
        "Dou Wei",
        "ErShou Rose",
        "Hu Mage",
        "Li Zhi",
        "Luo Dayou",
        "Wan Qing",
        "Yao",
        "Zhang Chu",
        "ZuoXiao",
};
char *key_name = "Zhang Chu";
char **name_str = bsearch(&key_name, names,
                          sizeof names / sizeof names[0], sizeof names[0],
                          CompareStrs);
// 为什么要 & : 参数为 const void *key，目标元素的地址
// 为什么是 char **：返回的是找到的那个元素的地址。元素是 char * 类型，地址自然是 char **
# 结构与链表
# 【结构体】
typedef struct score{
    int c_score; // 4
    int java_score; // 4
    int python_score; // 4
} Score;
typedef struct musician {  // 类型为 struct musician
    char *name; // 8
    Gender gender; // 1
    char *album; // 8
    Score score;  // 结构体的嵌套
} Musician;  // 利用 typedef 定义为 Musician
为什么内存空间不是 29：（1）地址最后应该为 8 的倍数，所以要补字节使其合法。 （2）每个部分字节为多少，它的起始地址 % 多少 就应该为 0。如 8 字节 char * 起始地址 应该 %8 为 0。 定义顺序不同，大小也可能不一样
初始化：
Musician luo = {
            .name = "Luo Dayou",
            .gender = MALE,
            .album = "ZhiHuZheYe",
            .score.c_score = 0,
            .score.java_score = 10,
            .score.python_score = 20,  // 伪逗号可以加
    };
    // 没有初始化的默认为 0
    
    Musician cui = {
            .name = "Cui Jian",
            .gender = MALE,
            .album = "XinChangZhengLuShangDeYaoGun",
            .score = {
                    .c_score = 10,
                    .java_score = 20,
                    .python_score = 30,
                    }
    };
    // 上面这样也行
    Musician luo = cui; // 结构体可以直接赋值，与数组不同
    Musician musicians[] = {luo, cui, zhang};  // 结构数组
    int len = sizeof musicians / sizeof *musicians;   // 数组内元素个数
结构体在函数中的使用：
// 尽量不要传递结构体，因为复制花费时间。可以传递指针
void PrintMusician(const Musician *m)
{
    printf("%s\t%c\t%s\t%d\t%d\t%d\n",
           (*m).name,      //. 的优先级高于 *
           m -> gender,    // 语法糖，等同于上面的写法
           m -> album,
           m -> score.c_score,
           m -> score.java_score,
           m -> score.python_score);
}
# 【链表】
// 定义数据类型 : linked list (circular)
typedef struct node {
    int index;
    struct node *next;  // 不能写成 Node *
} Node;
// 节点结构
typedef struct list {
    Node *head; // 头指针
    Node *tail; // 尾指针
} Linkedlist;
// 链表结构
常见链表函数 (很多)
void Init(Linkedlist *list); // 传指针。初始化链表
void Free(Linkedlist *list); // 释放链表
void Append(Linkedlist *list, int index); // 添加节点
void Insert(Linkedlist *list, Node *prev, int index); // 在指定节点 prev 后添加节点
bool Isempty(const Linkedlist *list);  // 链表是否为空
void Print(Linkedlist *list); // 输出链表
void Delete(Linkedlist *list, Node *prev); // 删除 prev 节点后的节点
void Nilist(Linkedlist *list);  // 使单向链表倒序
void Init(Linkedlist *list)
{
    list->head = NULL;
    list->tail = NULL;
}
void Free(Linkedlist *list)
{
    if (list->head == NULL)
    {
        return;
    }
    Node *point = list->head;
    Node *next = point->next;
    while (point != NULL)
    {
        next = point->next;
        free(point);
        point = next;
    }
}
bool Isempty(const Linkedlist *list)
{
    return list->head == NULL;
}
void Append(Linkedlist *list, int index)
{
    Node *node = malloc(sizeof *node); // 生成一个指针，指向 Node 结构类型，并分配了 Node 结构大小的空间
    if (node == NULL)
    {
        return;
    }
    if (Isempty(list)) // 链表为空
    {
        list->head = node;
    }
    else  // 通用情况
    {
        list->tail->next = node;
    }
    node->index = index;
    list->tail = node;
    list->tail->next = list->head; // 啊这里是环形链表吗？
}
void Insert(Linkedlist *list, Node *prev, int index)
{
    // 首先，创建一个新节点
    Node *new_node = (Node *)malloc(sizeof(Node));
    if (new_node == NULL)
    {
        // 处理内存分配失败的情况
        return;
    }
    new_node->index = index; // 设置新节点的值
    new_node->next = NULL; // 新节点的下一个节点先设置为 NULL
    if (prev == NULL)
    {
        // 如果 prev 是 NULL，那么将新节点插入到链表头部
        if (list->head == NULL)
        {
            // 如果链表为空，那么新节点同时也是链表的尾部
            list->tail = new_node;
        }
        else
        {
            // 将新节点链接到当前的头节点
            new_node->next = list->head;
        }
        // 更新链表的头部为新节点
        list->head = new_node;
    }
    else
    {
        // 插入到指定节点 prev 后面
        new_node->next = prev->next; // 新节点的下一个节点是 prev 原来指向的节点
        prev->next = new_node; // 将 prev 的下一个节点设置为新节点
        if (prev == list->tail)
        {
            // 如果 prev 是尾节点，那么更新尾部为新节点
            list->tail = new_node;
        }
    }
}
bool Isempty(const Linkedlist *list)
{
    return list->head == NULL;
void Print(Linkedlist *list)
{
    if (Isempty(list))
    {
        return;
    }
    Node *node = list->head;
    do {
        printf("%d ", node->index);
        node = node->next;
    } while (node != list->head);
}
void Delete(Linkedlist *list, Node *prev)
{
    if (Isempty(list))
    {
        return;
    }
    if (Issingleton(list))
    {
        Init(list);
        free(prev);
        return;
    }
    Node *cur = prev->next;  // 指向被删节点
    Node *next = cur->next;
    prev->next = next;
    if (cur == list->head)
    {
        list->head = next;
    }
    if (cur == list->tail)
    {
        list->tail = prev;
    }
    free(cur);
}
void Nilist(Linkedlist *list)
{
    // 检查链表是否为空或只包含一个节点
    if (list->head == NULL || list->head == list->tail)
    {
        return; // 空链表或只有一个节点的链表不需要倒序处理
    }
    Node *prev = NULL;
    Node *current = list->head;
    Node *next = NULL;
    // 更新 tail 指向原链表的头节点
    list->tail = list->head;
    // 遍历每个节点，并反转 next 指针
    while (current != NULL)
    {
        next = current->next; // 临时保存下一个节点
        current->next = prev; // 反转 next 指针
        prev = current;       // 移动 prev 到当前节点
        current = next;       // 继续下一个迭代
    }
    // 更新 head 指向原链表的最后一个节点
    list->head = prev;
}
# 输入输出
# 【关于 scanf】
  1. 输入的终止
while ((scanf("%s", s) != EOF))
{
    // 其它代码
}
  1. 正则表达式匹配读入
scanf("%[^;];%[^;];%d;%d;%d", s1, s2, &d1, &d2, &size);
getchar();  // 为什么有这个？因为回车也会被读进来
%[^;] 意为读入除 ';' 外的所有字符。（本题的要求是所有部分用分号隔开）
# 杂项
# 【UB—— 未定义行为】
数字除以 0、scanf printf 类型不匹配、访问未初始化局部变量、数组访问越界 等
千万不要数组越界！在循环时，记得加上限制条件。
# 数字翻转
int reverse(int n)
{
    int ans = 0;
    while (n)
    {
        ans = ans * 10 + n % 10;
        n /= 10;
    }
    return ans;
}
 更新于   阅读次数  次
请我喝[茶]~(￣▽￣)~*
北沐清 微信支付
微信支付
北沐清 支付宝
支付宝