基础数据结构_C语言实现

发表于2021-09-02更新于2025-09-28阅读次数

内容

  1. 数据结构的基础概念和时间空间复杂度
  2. 线性表：顺序表、链表
    1. 顺序表（定长的、扩容的）
    2. 单链表（带头结点的、不带头结点的）
      1. 需要动手实践，大量的面试题
  3. 栈（顺序栈、链栈）
    1. 用两个栈实现一个队列
  4. 队列（顺序队、链队）
    1. 用两个队实现一个栈
  5. 串（字符数组）
    1. API实现（strcpy strcat srtcmp strlen）
    2. 字符串的查找（BF、KMP算法）
  6. 双向链表、循环链表、双向循环链表
  7. 八大排序算法
    1. 冒泡排序
    2. 二路归并排序
    3. 插入排序
    4. 希尔排序
    5. 堆排序
    6. 基数排序（桶排序）
    7. 快速排序
    8. 选择排序

概念

数据结构

  1. 集合
  2. 线性（现实生活中的排队）
  3. 树型（部门架构、族谱）
  4. 图型（交通网络、六度分割理论、网络拓扑）

时间复杂度

执行语句与问题规模之间的函数

  1. O(1): 没有循环，或者有循环但是循环的退出条件和问题规模之间没有关系；
  2. O(n): 有循环，循环的退出条件与问题规模之间存在关系，并且控制循环的变量以++或者–的方式执行
  3. O(n^2): 有循环，嵌套一层。
  4. O(logn): 有循环，循环的退出条件与问题规模之间存在关系，并且控制循环的变量每次*2或/2的方式执行。

空间复杂度

算法所需的额外存储空间（除了函数本身计算申请的内存外）与问题规模之间的关系。

1
2
3
4
5
6
7
void Show(int arr[], int len)
{
    for(int i = 0;i<len;++i)
    {
        printf("%d ",arr[i]);
    }
}

此处，函数参数中的int arr[]和int len不是额外存储空间。而是for循环。

线性表

  • 唯一的头（此处的头指的是第一个有效节点），唯一的尾。
  • 除了头，剩余的节点都有前驱。除了尾，剩余的节点都有后继。

定长顺序表

相当于一个特殊使用的数组。

但存放数据是按顺序来存的，不能随意位置存放。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//sqlist.h
#pragma once	//防止头文件重复
typedef int ElemType;
typedef struct Sqlist
{
    ElemType arr[10];//节点
    int length;//当前有效数据节点的个数
}Sqlist,*PSqlist;
//初始化
void Init_sqlist(PSqlist plist);
//增删改查
//按位置插入（头插、尾插）
bool Insert_Pos(PSqlist plist, int pos, int val);
//删除：按值删、按位置删（删除这个值第一次出现的位置）
bool Del_val(PSqlist plist, int val);
bool Del_pos(PSqlist plist, int pos);
//查找值为val的节点
Sqlist* FindNode(PSqlist plist, int val);
//判空 判满
bool IsEmpty(PSqlist plist);
bool IsFull(PSqlist plist);
//清空
void Clear(PSqlist plist);
//销毁
void Destory(PSplist plist);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include"sqlist.h"
#include<string.h>
//初始化
void Init_sqlist(PSqlist plist)
{
    assert(plist!=NULL);
    memset(plist->arr,0,sizeof(arr));
    plist->length = 0;
}
//增删改查
//按位置插入（头插、尾插）
bool Insert_Pos(PSqlist plist, int pos, int val)
{
    assert(plist!=NULL);
    if( pos<0 || pos > plist->length || IsFull(plist) )return false;
    
    //移动数据
    for(int i = plist->length-1; i>=pos ;i--)
    {
        //不会越界，因为如果length为10时，不能进入此循环
        plist->arr[i+1] = plist->arr[i];
    }
    //插空
    plist->arr[pos] = val;
    //长度加1
    plist->length++;
    return true;
}
//头插
bool Push_Front(PSqlist plist, int val)
{
    assert(plist!=NULL);
    return Insert_Pos(plist, 0, val);
}
//尾插
bool Push_Back(PSqlist plist, int val)
{
    assert(plist!=NULL);
    return Insert_Pos(plist, plist->length, val);
}
//删除：（删除这个值第一次出现的位置）
//按值删
bool Del_val(PSqlist plist, int val)
{
    assert(plist!=NULL);
    return Del_pos(plist, FindPos_withVal(plist, val) );
}
//按位置删
bool Del_pos(PSqlist plist, int pos)
{
    assert(plist!=NULL);
    if( pos<0 || pos > plist->length || IsEmpty(plist) )return false;
    //长度减1
    plist->length--;
    //移动数据（相当于清除了arr[pos]）
    for(int i = pos; i < plist->length-1 ;++i)//i < plist->length-1  容易出错
    {
        plist->arr[i] = plist->arr[i+1];
    }
    return true;
}
//头删
bool Pop_Front(PSqlist plist)
{
    assert(plist!=NULL);
    Del_pos(plist, 0);
}
//尾删
bool Pop_Back(PSqlist plist)
{
    assert(plist!=NULL);
    Del_pos(plist, plist->length);
}
//查找值为val的节点
int FindPos_withVal(PSqlist plist, int val)
{
    assert(plist!=NULL);
    int pos = -1;
    int i = 0;
    while(i< plist->length && val!=plist->arr[i])
    {
        ++i;
    }
    if(i!=length)//则while是因为val==plist->arr[i]跳出的。
    {
        pos = i;
    }
    return pos;
}
//判空 判满
bool IsEmpty(PSqlist plist)
{
    return plist->length == 0;
}
bool IsFull(PSqlist plist)
{
    return plist->length == sizeof(plist->arr)/sizeof(plist->arr[0]);
}
//清空
void Clear(PSqlist plist)
{
    assert(plist!=NULL);
    plist->length = 0;
}
//销毁
void Destory(PSplist plist)
{
    assert(plist!=NULL);
    Clear(plist);
}

不定长顺序表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//sqlist.h
#pragma once	//防止头文件重复
typedef int ElemType;
#define INIT_SIZE 10
typedef struct DSqlist
{
    ElemType* ar;//基地址
    int cursize;//当前有效数据节点的个数
    int capacity;//当前最长容量
}DSqlist,*PDSqlist;
//初始化
void Init_sqlist(PDSqlist plist);
//增删改查
//按位置插入（头插、尾插）
bool Insert_Pos(PDSqlist plist, int pos, int val);
//头插
bool Push_Front(PDSqlist plist, int val);
//尾插
bool Push_Back(PDSqlist plist, int val);
//删除：按值删、按位置删（删除这个值第一次出现的位置）
bool Del_val(PDSqlist plist, int val);
bool Del_pos(PDSqlist plist, int pos);
//头删
bool Pop_Front(PDSqlist plist);
//尾删
bool Pop_Back(PDSqlist plist);
//查找值为val的节点
int FindPos_withVal(PDSqlist plist, int val);
//判空 判满
bool IsEmpty(PDSqlist plist);
bool IsFull(PDSqlist plist);
//清空
void Clear(PDSqlist plist);
//销毁
void Destory(PDSplist plist);
void Inc(PDsqlist plist);
1
2
3
4
void Inc(PDsqlist plist)
{
    
}

单链表

image-20210902180653639

image-20210902181055988

  1. 第一种大厂笔试/面试中常用，主要考察对边界条件检测的掌握力；
    • 不带头结点的逆置和带头结点的逆置难度不一样。
  2. 第二种实际编程中常用，方便好用；
  3. 第三种的循环无意义，因为功能和头指针差不多。
  4. 第四种是加了一个尾指针，使尾插也变O(1)，但代价是需要对尾指针进行密切维护。

面试

image-20210904191948363

C语言_编译和预处理

发表于2021-08-23更新于2025-09-28阅读次数

内容

本章主要讲解了预处理的三种方式：宏定义、文件包含、条件编译

学习目标

  1. 掌握无参数宏定义和带参数宏定义的使用方法
  2. 学会使用文件包含
  3. 熟悉条件编译指令的使用方法

预处理命令的作用不是实现程序的功能，而是给C语言编译系统提供信息，通知C编译器在对源程序进行编译之前应该做哪些预处理工作。预处理是指在进行编译之前所作的处理，由预处理程序负责完成。接下来还要经过编译、链接，才能变成可执行程序。本章节将结合案例对编译和预处理的相关知识进行详细讲解。

最简单的预处理-不带参宏定义

案例描述

为了引入“预处理”这个概念，本案例要求将矩形的长和宽设置为宏，然后再求出矩形的面积。这事最简单的预处理。

案例分析

宏定义是预处理最常用的功能之一，它用于将一个标识符定义为一个字符串。这样，在源程序被编译器处理之前，预处理器会将标识符替换成定义的字符串。根据是否带参数，可以将宏定义分为无参数宏定义和带参数宏定义。本案例要学习的是不带参数的宏定义。

必备知识

不带参数的宏定义

在程序中，经常会定义一些常量，例如，3.14、“ABC”。如果这些常量在程序中被频繁使用，难免会出现书写错误的情况。为了避免程序书写错误，可以使用不带参数的宏定义来定义这些常量，其语法格式如下：

1
#define 标识符 字符串

在上述语法格式中，"#define"用于标识一个宏定义，"标识符"指的是所定义的宏名，"字符串"指的是宏体，它可以是常量、表达式等。一般情况下，宏定义需要放在源程序的开头，函数定义之外。它的有效范围是从宏定义语句开始到源文件结束。一般宏名都是大写字母，以便于与其他的操作符区别。

1
#define PI 3.141592

#undef指令取消宏定义

与#define相对，还有#undef指令用于取消宏定义，当使用#define定义了一个宏之后，如果预处理器在接下来的源代码中看到了#undef指令，那么#undef后面的代码中这个宏将会失效，如下代码所示。

1
2
3
4
5
6
7
8
9
#include<stdio.h>
#define PI 3.14
int main()
{
    printf("%f\n",PI);
#undef PI
    printf("%f\n",PI);
    return 0;
}

运行这段程序，会报错

1
2
IntelliSense: 未定义标识符 "PI"		//7行17列
error C2065: "PI": 未声明的标识符	   //7行1列

第二简单的预处理-带参宏定义

案例描述

在之前的章节中，我们已经学过简单的数据交换。本案例要求使用宏定义，依次交换两个一维数组中的元素。

案例分析

本案例要实现两个一维数组中元素的依次交换，整个交换过程包含多次数组元素的交换。结合之前学习的知识，可以使用函数实现简单的数据交换功能，在使用循环遍历数组的同时，调用交换函数，实现数组元素的交换。本案例要求使用宏定义实现此功能。

因为数组遍历的过程中，数据在不断改变，而不带参宏定义中只能定义固定的内容。这里我们需要使用第二简单的预处理方法——带参宏定义来完成本案例。

必备知识

带参数的宏定义

语法格式如下所示：

1
#define 标识符(形参表) 字符串

上述语法格式和不带参数的宏定义有些类似，不同的是多了一个括号，括号中的“形参表”由一个或多个形参组成，当多于一个形参时，形参之间要用逗号进行分隔。

对于带参数的宏定义来说，同样需要使用字符串替换宏名，使用实参替换形参。

与带参函数的区别

带参宏定义和带参函数有时可以实现同样的功能，但两者有本质的不同，具体如表所示。

基本操作 带参数的宏定义 带参数的函数
处理时间节点 预处理时 程序运行时
参数类型 无 需定义参数类型
参数传递 不分配内存，无值传递的问题 分配内存，将实参值代入形参
运行速度 快 相对较慢，因为函数的调用会涉及到参数的传递、压栈、出栈等操作

务必要注意的问题

来看一个例子

1
#define ABS(x) ((x)>=0 ? (x): -(x))

这是一个求绝对值的带参宏定义，调用这个宏定义，代码如下所示：

1
2
double x = 12;
printf("%d \n",ABS(++x));

输出的结果是14，显然与我们的初意中的12不相符。这是因为在预处理时，表达式"ABS(++x)“会被替换为”( (++x)>=0 ? (++x): -(++x) ) "，因此结果是14。

那么，这就是带参宏定义时要注意的问题，宏定义中的参数替换是“整体”替换，不像是函数中只是参数之间的值传递。

案例实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<stdio.h>
#define SWAP(a,b) {int temp = a; a=b; b=temp;}
int main()
{
    int i,j;
    int a[5]={3,4,5,6,7};
    int b[5]={5,6,7,8,9};
    for(int i = 0;i<5;i++)
    {
        SWAP(a[i],b[i]);
    }
    printf("After swaping:\n");
    for(int i = 0;i<5;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
    for(int i = 0;i<5;i++)
    {
        printf("%d ",b[i]);
    }
    printf("\n");
    return 0;
}
//运行结果：
After swaping
5 6 7 8 9
3 4 5 6 7

关于宏定义中参数的替换-要注意的问题

表达式字符串中出现运算符

若宏定义中的字符串出现运算符，需要在合适的位置上加上括号，如果不添加括号可能会出现错误。例如

1
2
3
#define S 3+4
int c = 100;
int a = S*c		//3+4*c == 403 而非 7*c ==700

宏定义的末尾不要加分号

如果加了分号，将被视为被替换字符串的一部分。

宏定义不会进行严格的语法检查，因此宏替换的错误要等到系统编译时才能被发现，例如：

1
2
3
4
5
6
7
#define Max=20;
....
if(result == Max)	//if(result==20;)
{
    printf("equal");
}
//显然if语句会出错

宏定义允许嵌套

在宏定义的字符串中可以使用已经定义的宏名。

1
2
3
#define PI 3.141592
#define P PI*x
printf("%f",P);		//替换后的语句为printf("%f",3.141592*x);

但宏定义不支持递归，因此下面的宏定义是错误的：

1
#define Max Max+5

预处理的第二种方式-文件包含

案例描述

要求设计一个头文件，将经常使用的输出模式都写进头文件中，方便编写代码。

案例分析

除宏定义外，文件包含也是一种预处理语句，它的作用就是将一个源程序文件包含到另外一个源程序文件中。

必备知识

文件包含命令的形式

同引入头文件一样，文件包含也是使用#include指令实现的，它的语法格式有两种，具体如下

格式一

1
#include <文件名>

格式二

1
#include "文件名“

区别

上述两种格式都可以实现文件包含，不同的是，格式一是标准形式，当使用这种格式时，C编译系统在系统指定的路径下搜索尖括号(<>)中的文件；当使用第二种格式时，系统首先会在用户当前工作的目录中搜索双引号(“”)中的文件，如果找不到，再按系统指定的路径进行搜索。

案例实现

foo.h代码如下：

1
#define INT(x) printf("%d\n",x)

main.c代码如下：

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>
#include "foo.h"
int main()
{
    int a;
    printf("Please input an integer:\n");
    scanf("%d",&a);
    INT(a);		//替换为"printf("%d\n",a)" + ";"
    return 0;
}

32还是64-条件编译

案例描述

要求使用条件编译，根据条件输出对应的判定结果：如果系统是32位的，就输出“系统是32位的”；如果系统是64位的，就输出“系统是64位的”。

案例分析

上文提到的“条件编译”也是预处理的一种方式。

一般情况下，C语言程序中的所有代码都要参与编译，但有时出于程序代码优化的考虑，希望源代码中一部分内容只在指定条件下进行编译。这种根据指定条件，只对程序一部分内容编译的情况，称为条件编译。

在C语言中条件编译指令的形式有很多种，接下来将详细讲解一种最常见的条件编译指令：#if/#else/#endif，该指令根据常数表达式来决定某段代码是否执行。

必备知识

#if/#else/#endif指令

通常情况下，#if指令、#else指令和#endif指令是结合在一起使用的，其语法格式如下所示：

1
2
3
4
5
#if 判断表达式
	程序段
#else
    程序段2
#endif

在上述语法格式中，编译器只会编译程序段1和程序段2中的一段。当条件为真时，编译器会编译程序段1，否则编译程序段2。

案例实现

案例设计

  1. 定义两个宏，分别表示Windows32位和64位平台；
  2. 定义宏SYSTEM表示其中某个平台；
  3. 使用条件编译指令判断SYSTEM值，并输出结果到屏幕上。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
#define Win32 0
#define x64 1
#define SYSTEM Win32		//定义宏SYSTEM是32位的
int main()
{
#if SYSTEM == Win32			//此处条件成立
    printf("Win32\n");
#else
    printf("x64");
#endif
    return 0;
}
//执行printf("Win32\n");
运行结果为 Win32

#ifdef-神奇的#include<stdio.h>

案例描述

在同一文件中写两遍"#include<stdio.h>"，编译器进行编译时为什么没有报错呢？按常理而言，文件"stdio.h"中的函数和数据类型等必然被定义了两次，此时编译器应该报出"重定义"的错误，但实际上编译十分顺利。

案例分析

在上一个案例中我们提到C语言中条件编译指令的形式有很多种，如果现在的你百思不得其解，那是因为你没有学过另一种条件编译指令：#ifdef和#ifndef。下面来讲解。

必备知识

#ifdef指令

如果想判断某个宏是否被定义，可以使用#ifdef指令，通常情况下，该指令需要和#endif一起使用，#ifdef指令的语法格式如下所示：

1
2
3
4
5
#ifdef 宏名
	程序段1
#else
    程序段2
#endif

在上述语法格式中，#ifdef指令用于控制单独的一段源码是否需要编译，它的功能类似于一个单独的#if/#endif

#ifndef指令

和#ifdef相反，#ifdef用来确定某一个宏是否没有被定义，如果宏没有被定义，那么就编译#ifndef和#endif中间的内容，否则就跳过。其语法格式如下所示：

1
2
3
4
5
#ifndef 宏名
    程序段1
#else
    程序段2
#endif

案例实现

如果我们打开"stdio.h"这个文件，便会发现其开头是这样的两行代码。

1
2
#ifndef _STDIO_H_
#define _STDIO_H_

在其结尾有这样一行代码：

1
#endif /* _STDIO_H_ */

这三行代码是三条预处理指令，也就是为什么写两遍"#include<stdio.h>"也不会报错。当然，写更多遍也不会报错。

这三行代码的含义是：如果"_STDIO_H_“没有定义过，那么就定义”_STDIO_H_“。仔细观察后我们会发现**”#define _STDIO_H_“后面什么都没写，其实这也是宏定义的一种写法——并不关注”_STDIO_H_"被定义成了什么，只关注他是否被定义过。**

综上分析可知，初次遇到"_STDIO_H_“的时候，由于宏”_STDIO_H_“尚未定义，因此，#ifndef条件成立，定义”_STDIO_H_“。当再次遇到”_STDIO_H_“的时候，#ifndef的条件不成立，因此它与”#endif"之间的内容就不会被编译了。

利用预定义宏得知程序允许到了何处

下面是<stdio.h>头文件中的五个预定义宏，利用这些宏可以轻松得知程序运行到了何处，有助于编程人员进行程序调试，具体如下表。

预定义宏 说明
_DATE_ 定义源文件编译日期的宏
_FILE_ 定义源代码文件名的宏
_LINE_ 定义源代码中行号的宏
_TIME_ 定义源代码编译时间的宏
_FUNCTION_ 定义当前所在函数名的宏