【数据结构】C语言必备知识学习
1. 结构体类型
结构体是一种用户自定义类型，一般由基本数据类型复合而成，如学生的定义可以包括：学号、性别、英语成绩和数学成绩。下例定义并输出小明同学的性别和数学成绩。
#include<stdio.h>
int main() {
struct student
{
int stdID;
char gender;
int English;
int Math;
};
struct student Xiaoming; // 声明结构体变量Xiaoming
Xiaoming.stdID=20190102; // 对结构体中的学号赋值
Xiaoming.gender='M'; // 对结构体中的性别赋值
Xiaoming.English=90; // 对结构体中的英语成绩赋值
Xiaoming.Math=85; // 对结构体中的数学成绩赋值
printf("Xiaoming\n");
printf("Gender:%c",Xiaoming.gender); // 输出结构体中的性别
printf("\nMath:%d",Xiaoming.Math); // 输出结构体中的数学成绩
return 0;
}
2. typedef定义新的类型
请看如下语句：
typedef int ElemType;
其中，标识符 ElemType 是一个用户自定义标识符，其实来自 Element Type，表示数据元素类型的含义。
typedef 则来自两个词 type definition，表示类型定义，是系统关键字。
int是系统关键字，表示整数类型。
typedef int ElemType；表示在程序中将用标识符ElemType替换int，可以用来声明变量。
如 ElemType a; 表示 a 就是一个整型变量。
类似的，typedef 可以将结构体类型替换。如下面语句将 sturct sqList 这个结构体替换为 SqList。注意 S 大小写是不同的。
typedef struct sqList {
ElemType* elem;
int length;
int listsize;
} SqList;
因此可以用 SqList 声明结构体变量，如：
SqList s2;
它与下面声明语句是等价的：
struct sqList s1;
也可以声明指针类型，如下例中的LinkList：
Typedef struct LNode {
ElemType data; // 数据域
struct LNode *next; // 指针域
} LNode, *LinkList;
LinkList是指向结构体struct LNode的指针类型，通过它可以声明指针变量：
LinkList p; //本语句声明一个变量 p，它是一个指针变量。
3. 有关函数参数传递的说明与举例
函数参数传递方式：传值、传址和引用。 C语言只有前两种，C++提出引用的概念，因此有3种参数传递方式。本课程算法实现主要采用了传值和引用传递。下面以计算平方值的函数为例，说明3种参数传递方式。
函数的参数传递（一）：传值
在主函数中，将变量a中存储的值赋值到函数fun的参数x中，a和x是不同变量，对应两个不同的存储空间。
#include<stdio.h>
float fun(float x) { return x*x; }
int main() {
float a=2.5;
float b=fun(a);
printf("result=%f",b);
return 0;
}
函数的地址传递（二）：传址
主函数中，将a的地址传到函数fun的参数p中，运行时函数对p的访问时就是对a的地址的访问，换言之p里面保存的就是a的地址。
#include<stdio.h>
float fun(float* p) { return *p**p; } // *p表示指针p所表示地址中存储的内容
int main() {
float a=2.5;
float b=fun(&a);
printf("result=%f",b);
return 0;
}
函数的引用传递（三）：引用
引用是C++中的概念。主函数中，将a以引用形式传给函数fun的参数x， x和a共享a表示的存储空间，对x的操作就是对a的操作。与传址相比，引用没有指针操作，更简单明了。
例1：将数据传递到函数内
#include<stdio.h>
float fun(float& x) { return x*x; } // &表示参数x是引用传递，不是对x取地址
int main() {
float a=2.5;
// x与a共享a的存储空间
//在fun函数中对x的使用就是对a的使用
float b=fun(a);
printf("b=%f",b);
return 0;
}
例2：将函数处理结果传递到函数外
#include<stdio.h>
void fun(float& result, float x) { result=x*x; } // &表示参数x是引用传递
int main() {
float a=2.5;
float b;
// result与b共享相同的存储空间
//在fun函数中对result的修改就是对b的修改
fun(b,a);
printf("result=%f",b);
return 0;
}
4. 动态内存分配malloc
malloc函数的全称是memory allocation，即动态内存分配，用于申请一块连续的指定大小的内存区域。 malloc函数的参数是需要分配的字节数，该函数以void*类型返回分配的内存区域地址，使用时根据需要进行类型转换。
原型为：void* malloc (size_t size);
【参数说明】
size 为需要分配的内存空间的大小，以字节（Byte）计。
【函数说明】
malloc() 在堆区分配一块指定大小的内存空间，用来存放数据。这块内存空间在函数执行完成后不会被初始化，它们的值是未知的。
【返回值】
分配成功返回指向该内存的地址，失败则返回 NULL。
操作：
由于申请内存空间时可能有也可能没有，所以需要自行判断是否申请成功，再进行后续操作。
注意：函数的返回值类型是 void *，void 并不是说没有返回值或者返回空指针，而是返回的指针类型未知。所以在使用 malloc() 时通常需要进行强制类型转换，将 void 指针转换成所希望的类型。
下面程序通过malloc申请10个整数类型数据的存储空间，对数据存储后输出。
#include<stdio.h>
#include<stdlib.h>
int main()
{
int *data; //存储空间首地址（基址，第一个数据所在内存空间的地址）
int i;
// sizeof用于计算一个int类型数据所占字节
// 下面语句分配10个整数所占的内存空间，并将第一个数据的地址保存在data变量中
data = ( int * ) malloc( 10 * sizeof ( int ) );
for (i=0;i<10;i++)
data[i]=2*i;
for (i=0;i<10;i++)
printf("%d\t",data[i]);
return 0;
}
输出10个整数：0 2 4 8，… …，16 18
5. 关于for循环的分析
算法的时间复杂度一般主要取决于最内层语句的执行频度。关于for循环，请看例子。
y=0; // 执行1次
for(i=1; i<=n; i++) // 执行n+1次
for(j=1; j<=n; j++) // 执行n(n+1) 次
y++; // 执行n^2次
外层循环正常执行n次后，i 继续自增后大于n，不再满足循环条件，因此外层for语句执行n+1次。内层for循环，在外层的 n 次循环中都会被执行，但是每次循环与外层for循环类似，也要执行n+1次，因此内层for循环执行n(n+1)次。而语句y++的执行次数是n的平方(n^2)。