3.1 Data Structure
Mon & Wed Lecture
主要讲述了数据结构与 struct 数组定义
arrays
无论你用什么编程语言，双列表第一个做的事永远是把第一个维度视为行，第二个维度视为列
Initialization
我们一般倾向于在 C 文件开头使用 define 语句提前定义好列表的内存大小
#define N 20
int myarray[ N ];
int evensum;
evensum = 0;
for(int i=0 ; i < N ; ++i) {
myarray[ i ] = i * 2;
evensum = evensum + myarray[ i ];
}
一维列表的初始化方法如下，和 Python 不同的是 C 的一切都需要提前在内存中初始化好后再接入其元素，有运行时初始化并分配元素与编译时初始化两种方案
initialize the elements at run-time, by executing statements to assign values to the elements
initialize the values at compile-time, by telling the compiler what values to initially store in the memory
编译时让自动初始化分配内存大小
在不指定内存大小的时候，编译时会根据元素数量自动推倒，define 这行列表中都是同一类型的数据，每个 int 元素占据 4 bytes, sizeof(array) 会返回列表大小也就是 4 * 5 = 20, 第一个元素的大小为 4 相除就成了列表长度。
提前预留内存与指定部分元素
在 run-time 后 define 才能确定大小的数组被称之为 variable-length arrays, or variable-sized arrays 也就是可变长度数组和可变大小数组；但由于其在嵌入式设备中实现效率低下，现代 Linux 内核移除了可变长度数组，C11 中成为了可选定义。并且可变长度数组都可以在一个函数中定义并传递给另一个函数。但是，由于大小在运行时之前是未知的，因此也必须传递数组的大小。无法根据数组的名称确定数组的大小。
void function2(int array_size, char vla[ ])
{
for(int i=0 ; i < array_size ; ++i) {
// access vla[i] ...
....
}
}
void function1(void)
{
int size = read an integer from keyboard or a file;
char vla[ size ];
function2(size, vla);
}
strings
由于 C 中不具备字符串这种基础的数据类型，使用的是 char array 数组字符去实现，无论是 #include <string.h> 下可被调用的功能计算字符长度，是否相等，拷贝等和 printf 一样都本质是管理字符数组。
和 int 一样同样支持自动计算分配所需大小
Strings are terminated by a special character
在数组中 \0 被称为 null byte, 一般用于 char arrary 中的末尾序列，标明 string 到这里就处理结束了：
这个字符需要六个字节的内存才能被正常储存，但是 strlen 这样的函数返回会显示 5
先前的案例 char month[] = "August"; 中，实际上系统自动给 August 末尾分配了一个 \0 符，使用了 7 个位置储存,，但在 Monday 中由于指定了内存大小因此不会被自动分配 \0 符
如果执行 arrary[5] = '\0', 数组仍然会占据 12 个字节的储存空间，但是如果打印出来就只会得到 hello
copy one string into another
solution one： for loop
void my_strcpy(char destination[], char source[])
{
int length = strlen(source);
for(int i = 0 ; i < length ; ++i) {
destination[i] = source[i];
}
destination[length] = '\0';
}
解决方案一是首先计算长度然后插进新数组内容，最后插入 \0 结束
solution two: while loop unbounded loop:
void my_strcpy(char destination[], char source[])
{
int i = 0;
while(source[i] != '\0') {
destination[i] = source[i];
i = i+1;
}
destination[i] = '\0';
}
根据原 source 数组判断，只要不是 null byte 就继续复制，do while 同样可以实现
// USE AN UNBOUNDED LOOP, COPYING UNTIL THE NULL-BYTE
void my_strcpy(char destination[], char source[])
{
int i = 0;
do {
destination[i] = source[i];
i = i+1;
} while(source[i-1] != '\0');
}
sprintf - 格式化写入变量
在很多情况下，我们希望我们的“输出”被写入字符数组，而不是到屏幕上。
#include <stdio.h>
char chess_outcome[64];
if(winner == WHITE) {
sprintf(chess_outcome, "WHITE with %i", nwhite_pieces);
}
else {
sprintf(chess_outcome, "BLACK with %i", nblack_pieces);
}
printf("The winner: %s\n", chess_outcome);
默认可以这样用，但由于不要超过接收格式化打印的数组的最大长度，因此可以定义
char chess_outcome[64];
// FORMAT, AT MOST, A KNOWN NUMBER OF CHARACTERS
if(winner == WHITE) {
snprintf(chess_outcome, 64, "WHITE with %i", nwhite_pieces);
}
// OR, GREATLY PREFERRED:
if(winner == WHITE) {
snprintf(chess_outcome, sizeof(chess_outcome), "WHITE with %i", nwhite_pieces);
}
struct
anonymous struct
教授用了 RGB 调色盘首先举例匿名 struct 其机制：
C provides a mechanism to bring related data together, structures, using the struct keyword.
// DEFINE AND INITIALIZE ONE VARIABLE THAT IS A STRUCTURE
struct {
char *name; // a pointer to a sequence of characters
int red; // in the range 0..255
int green;
int blue;
} rgb_colour = {
"DodgerBlue",
30,
144,
255
};
printf("Color name: %s\n", rgb_colour.name);
printf("RGB: (%d, %d, %d)\n", rgb_colour.red, rgb_colour.green, rgb_colour.blue);
匿名结构体在 struct 后没有标明结构体类型 / 数据类型，{} 后定义了一个 variable, 因此在调用的时候不需要先对结构体进行数据类型声明直接用
variable 也可以是数组：
struct myStructure s1[3] = {
{13, 'B', "Some text"},
{25, 'C', "Another text"},
{42, 'D', "More text"}
};
printf("s1[0] - number: %d, letter: %c, text: %s\n", s1[0].number, s1[0].letter, s1[0].text);
printf("s1[1] - number: %d, letter: %c, text: %s\n", s1[1].number, s1[1].letter, s1[1].text);
Multiple football teams
这个案例就是 C11 中 struct 匿名函数的数组 variable 用法
多个 TEAM 的内容都可被自定义，然后循环打印每个 TEAM 的元素
#include <stdio.h>
#define MAX_TEAMS 3 // 定义队伍数量
#define MAX_TEAMNAME_LEN 30 // 最大队伍名称长度
// 定义球队的结构体数组
struct {
char teamname[MAX_TEAMNAME_LEN+1]; // 队伍名称
int played; // 比赛场次
int won; // 胜场数
int lost; // 败场数
int drawn; // 平局场次
int bfor; // 进球数
int bagainst; // 失球数
int points; // 积分
} team[MAX_TEAMS] = {
{"Team A", 10, 6, 2, 2, 20, 10, 20}, // 定义第一个队伍的数据
{"Team B", 12, 8, 3, 1, 25, 15, 25}, // 定义第二个队伍的数据
{"Team C", 11, 5, 5, 1, 18, 18, 16} // 定义第三个队伍的数据
};
// 打印所有队伍的信息
void printTeams() {
for (int i = 0; i < MAX_TEAMS; i++) {
printf("Team Name: %s\n", team[i].teamname);
printf("Played: %d, Won: %d, Lost: %d, Drawn: %d\n", team[i].played, team[i].won, team[i].lost, team[i].drawn);
printf("Goals For: %d, Goals Against: %d, Points: %d\n", team[i].bfor, team[i].bagainst, team[i].points);
printf("--------------------------\n");
}
}
int main() {
printTeams(); // 调用函数打印队伍信息
return 0;
}
这样管理定义极其方便，如果是非匿名函数：
#include <stdio.h>
#define MAX_TEAMS 3 // 定义队伍数量
#define MAX_TEAMNAME_LEN 30 // 最大队伍名称长度
// 定义一个结构体类型 Team
struct Team {
char teamname[MAX_TEAMNAME_LEN+1]; // 队伍名称
int played; // 比赛场次
int won; // 胜场数
int lost; // 败场数
int drawn; // 平局场次
int bfor; // 进球数
int bagainst; // 失球数
int points; // 积分
};
// 定义 Team 类型的数组
struct Team team[MAX_TEAMS] = {
{"Team A", 10, 6, 2, 2, 20, 10, 20}, // 第一个队伍
{"Team B", 12, 8, 3, 1, 25, 15, 25}, // 第二个队伍
{"Team C", 11, 5, 5, 1, 18, 18, 16} // 第三个队伍
};
// 打印所有队伍的信息
void printTeams() {
for (int i = 0; i < MAX_TEAMS; i++) {
printf("Team Name: %s\n", team[i].teamname);
printf("Played: %d, Won: %d, Lost: %d, Drawn: %d\n", team[i].played, team[i].won, team[i].lost, team[i].drawn);
printf("Goals For: %d, Goals Against: %d, Points: %d\n", team[i].bfor, team[i].bagainst, team[i].points);
printf("--------------------------\n");
}
}
int main() {
printTeams(); // 调用函数打印队伍信息
return 0;
}
可以看见需要另外再声明 variable 后进行 assignment
如果不使用 struct 结构，那就要手动重复去定义管理所有队伍：
// DEFINE THE LIMITS ON PROGRAM'S DATA-STRUCTURES
#define MAX_TEAMS 24
#define MAX_TEAMNAME_LEN 30
....
// DEFINE A 2-DIMENSIONAL ARRAY HOLDING OUR UNIQUE TEAMNAMES
char teamname[MAX_TEAMS][MAX_TEAMNAME_LEN+1]; // +1 for null-byte
// STATISTICS FOR EACH TEAM, INDEXED BY EACH TEAM'S 'TEAM NUMBER'
int played [MAX_TEAMS];
int won [MAX_TEAMS];
int lost [MAX_TEAMS];
int drawn [MAX_TEAMS];
int bfor [MAX_TEAMS];
int bagainst[MAX_TEAMS];
int points [MAX_TEAMS];
....
// PRINT EACH TEAM'S RESULTS, ONE-PER-LINE, IN NO SPECIFIC ORDER
for(int t=0 ; t<nteams ; ++t) {
printf("%s %i %i %i %i %i %i %.2f %i\n", // %age to 2 decimal-places
teamname[t],
played[t], won[t], lost[t], drawn[t],
bfor[t], bagainst[t],
(100.0 * bfor[t] / bagainst[t]), // calculate percentage
points[t]);
}
Accessing system information using structures
操作系统的信息被藏在 /usr/include 和其 /usr/include/sys 中
我们用非匿名函数作演示作最后收尾：
#include <stdio.h>
#include <sys/time.h>
struct timeval {
int tv_sec; // Seconds
int tv_usec; // Microseconds
};
struct timeval start_time;
struct timeval stop_time;
gettimeofday(&start_time, NULL);
printf("program started at %i.06%i\n",
(int)start_time.tv_sec, (int)start_time.tv_usec);
按地址传递结构，使用 & 运算符， 使得 gettimeofday（）函数，第二个时区信息由于不感兴趣所以设置为 NULL