C语言程序设计(Part Ⅸ)的整理笔记，若有错误，欢迎指正。

用指针处理链表

如果有一批数据要存储和引用，有两种方法：

一种方法是采取分配固定存储单元的方法，例如数组。但是在程序执行期间，数组的大小是固定的，不能改变的，在内存中是连续存放的。如果有的班级有100人，而有的班级只有30人，若用同一个数组先后存放不同班级的学生数据，则必须定义长度为100的数组。如果事先难以确定一个班的最多人数，则必须把数组定得足够大，以便能存放任何班级的学生数据，显然这将会浪费内存。这种数据结构称为静态的数据结构。另一种方法是动态的数据结构，它没有固定的大小，根据需要随时开辟存储单元，在用完后可以随时释放存储单元。线性链表就是动态地进行存储分配的一种数据结构。

下图表示最简单的一种链表(单向链表)的结构。

链表有一个"头指针"变量，以head表示，它存放一个地址，该地址指向链表中的一个元素。链表中的元素称为"结点"，每个结点都应包括两个部分：用户需要用的实际数据和下一个结点的地址。可以看出，head指向第一个结点；第一个结点中有一个指针变量指向第二个结点，……，直到最后一个结点，该结点不再指向其他结点，它称为"表尾"，它的地址部分放一个"NULL"(表示"空地址")，链表到此结束。可以看到链表中各结点在内存中的地址可以是不连续的。要找某一结点，必须先找到上一个结点，根据它提供的下一结点地址オ能找到下一个结点。如果不提供"头指针"(head)，则整个链表都无法访问。链表如同一条铁链一样，一环扣一环，中间是不能断开的。显然，链表这种数据结构，必须利用结构体变量和指针变量才能实现。在一个结点中包含两个部分：数据部分和一个指针变量(该指针变量存放下一结点的起始地址)。

---

建立简单的静态链表

例1：建立一个简单的链表，它由3个学生数据的节点组成。输出各结点中的数据。

#include<stdio.h>#define NULL 0struct student //声明结构体类型struct student{int num;float score;struct student * next;};int main(){struct student a, b, c, * p, * head; //定义3个结构体变量作为链表的结点a.num = 10101; a.score = 89.5; //对结点a的num的score成员赋值b.num = 10103; b.score = 90; //对结点b的num的score成员赋值c.num = 10107; c.score = 85; //对结点c的num的score成员赋值head = &a; //将结点a的起始地址赋给头指针heada.next = &b; //将结点b的起始地址赋给a结点的next成员b.next = &c; //将结点c的起始地址赋给b结点的next成员c.next = NULL; //c结点的next成员不存放其他结点地址p = head; //使p也指向a结点do {printf("%d %5.1f\n",p->num,p->score); //输出p指向的结点的数据p = p->next; //使p指向下一个结点} while (p != NULL); //输出完c结点后p的值为NULL，循环截至return 0;}

程序分析：

struct student共有三个成员，其中成员num和score用来存放结点中的有用数据(用户需要用到的数据)。为了构造链表，应当把next定义为指向struct student类型数据的指针变量，这时，next既是struct student类型中的一个成员，又指向struct student类型的数据。每一个结点(链表中的元素)都属于struct student类型，它的成员next存放下一结点的地址，程序设计人员可以不必知道各结点的具体地址，只要保证将下一个结点的地址放到前一结点的成员next中即可。开始时使head指向a结点，a.next指向b结点，b.next指向c结点，这就构成链表关系。"c.next=NULL"的作用是使c.next不指向任何有用的存储单元，这就形成了一个简单的链表。在输出链表时要借助p，先使p指向a结点，然后输出a结点中的数据。“p=p->next”是为输出下一个结点作准备。pー>next的值是b结点的地址，因此执行“p=p-next"后p就指向b结点，所以在下一次循环时输出的是b结点中的数据。

所有结点都是在程序中定义的，不是临时开辟的，也不能用完后释放，这种链表称为“静态链表”。

---

建立动态链表

所谓建立动态链表是指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点数据，并建立起前后相连的关系。

例2：建立一个有两名学生学号和成绩数据的单向动态链表。

#include<stdio.h>#include<malloc.h> //用malloc函数开辟新单元时需用此头文件#define LEN sizeof(struct student) //LEN代表struct student类型数据的字节数#define NULL 0struct student //声明struct student类型{int num; //学号成员float score; //成绩成员struct student * next; //指针变量成员};int main(){struct student * head, * p; //定义指针变量head和p//建立链表head = p = (struct student*)malloc(LEN); //开辟一个新单元，并让p和head指向它scanf("%d %f", &p->num, &p->score); //输入一个节点的数据p= (struct student * )malloc(LEN); //开辟第2个新单元，并让p指向它scanf("%d %f", &p->num, &p->score); //输入第2个节点的数据head->next = p; //使第1个结点中的next成员指向第2个结点p->next = NULL; //使第2个结点中的next成员不指向任何对象//输出两个结点中的数据p = head; //使p指向第1个节点printf("\n结点1：%d,%6.2f\n", p->num, p->score); //输出第1个结点中的数据p = p->next; //使p指向第2个结点printf("\n结点2：%d,%6.2f\n", p->num, p->score); //输出第2个结点中的数据return 0;}

程序分析：

在C语言中，开辟内存单元需要用malloc函数。如果有malloc(10)，表示要向系统申请分配一个占10个字节的内存空间，此函数的返回值是该段内存单元的起始地址。程序第3行已定义LEN代表struct student类型数据的字节数，因此malloc(LEN)的作用是开辟一个长度为struct student类型数据长度的内存空间。由于malloc函数返回的地址(指针)是(void*)类型的，即不指向一个特定的类型的对象，因此，对其返回值进行强制类型转换，即(struct student * )malloc(LEN)，使它能指向struct student类型的数据。第16行的作用是把新开辟的内存单元(即结点)的起始地址赋给p和head，也就是说使p和head指向新开辟的结点。由于p指向新结点，因此用scanf函数输入数据时，p→num就是此结点(是结体变量)中的num成员，p→score是此结点中的score成员。第18行再开辟一个新结点(即第2个结点)，并把此结点的起始地址赋给p，即p此时指向了第2个结点，第19行用scanf函数输入第2个结点中的数据。第20行的作用是把p的值(即第2个结点的起始地址)赋给第1个结点中的next指针，这样就使第1个结点的next指针指向第2个结点。第21行的作用是使第2个结点中的next指针的值为NULL，在stdio.h头文件中已定义NULL为0，这就使next指向地址为0的单元，系统不将0地址分配给任何对象。因此，第2个结点中的next指针不指向任何对象，故第2个结点就是链表中最后的结点。程序最后4行的作用是输出链表，"p=head"使p指向第1个结点，输出第1个结点中成员的值，然后“p=p→next”把p当前所指向的结点中的next指针的值赋给p，而此时第1个结点中的next指针是指向第2个结点的，因此也就是使p指向第2个结点。因此最后的printf语句中的p→num就是第2个结点的num成员。

---

共用体类型与枚举类型

用户除了可以自己建立结构体类型之外，还可以建立共用体类型和枚举类型

共用体类型

有时需要使几种不同类型的变量存放到同一段内存单元中。

例如，可把一个整型变量、一个字符型变量、一个实型变量放在同一个地址开始的内存单元中。以上3个变量在内存中占的字节数不同，但都从同一地址开始(假设地址为1000)存放。也就是使用覆盖技术，几个变量互相覆盖。

这种使字符几个不同的变量共占同一段内存的结构，称为"共用体"类型的结构。

与结构体对象相似，定义共用体对象也有三个形式：

①先声明共用体类型再定义共用体对象union 共用体类型名 共用体对象名列表;

②同时声明共用体类型和定义共用体对象union 共用体类型名 { 成员列表 } 共用体对象名列表;

③直接定义共用体对象union { 成员对象 } 共用体对象名列表;

例：

union data{short int i;char ch;float f}a,b,c;

可以看到，“共用体”与“结构体”的定义形式相似。但它们的含义是不同的。结构体变量所占内存长度是各成员占的内存长度之和。每个成员分别占有其自己的内存单元；而共用体变量所占的内存长度等于最长的成员的长度。例如，上面定义的“共用体”变量a、b、c各占4个字节(因为一个实型变量占4个字节)，而不是各占2+1+4=9个字节。

访问共用体成员

为了访问共用体的成员，我们使用成员访问运算符（.）。

例：

#include <stdio.h>#include <string.h>union Data //声明一个共用体类型union Data{int i;float f;char str[20]; //数组类型};int main( ){union Data data; data.i = 10; //赋值data.f = 220.5;strcpy( data.str, "C Programming"); printf( "data.i : %d\n", data.i); //输出printf( "data.f : %f\n", data.f);printf( "data.str : %s\n", data.str);return 0;}//输出结果为：data.i : 1917853763data.f : 4122360580327794860452759994368.000000data.str : C Programming

程序分析：

C语言只有在定义字符数组时才能用’=‘来初始化赋值，其他情况(如：给结构体/共用体内数组赋值)不能用’='直接赋值。但可用strcpy函数，此时需要在程序开头写上"#include<string.h>"。

！注意：程序2、7、15行。代码被编译和执行后，从输出结果可以看到共用体的i和f成员的值有损坏，因为最后赋给变量的值占用了内存位置，这也是str成员能够完好输出的原因。

由于成员是共享存储空间的，使用共用体对象成员时有如下特点：

①修改一个成员会使其他成员发生改变，所有成员存储的总是最后一次修改的结果

②所有成员的值是相同的，区别是不同的类型决定了使用这个值的全部或是部分

③所有成员的起始地址值是相同的，因此通常只按一个成员输入、初始化

枚举类型

如果一个变量只有几种可能的值，则可以定义为枚举类型。所谓“枚举”是指将变量的值一一列举出来，变量的值只限于列举出来的值的范围内。 声明枚举类型用enum开头。

枚举语法定义格式为：enum 枚举名 {枚举元素1,枚举元素2,……};

例：enumweekday{sun,mon,tue,wed,thu,fri,sat};

以上声明了一个枚举类型 enum weekday，然后可以用此类型来定义变量。

workday和week_end被定义为枚举变量，它们的值只能是sun到sat之一。

例:

workday=mon;week_end=sun;

也可以直接定义枚举变量，例：enumweekday{sun,mon,tue,wed,thu,fri,sat} workday,week_end;。

其中sun、mon、…、sat称为枚举元素或枚举常量，它们是用户定义的标识符。

！注意：第一个枚举成员的默认值为整型的 0，后续枚举成员的值在前一个成员上加1。如：sun=0,mon=1,tue=2,…。

枚举变量的定义：

可以通过以下三种方式来定义枚举变量

先定义枚举类型，再定义枚举变量

enum DAY {MON=1, TUE, WED, THU, FRI, SAT, SUN };enum DAY day;

定义枚举类型的同时定义枚举变量

enum DAY {MON=1, TUE, WED, THU, FRI, SAT, SUN } day;

省略枚举名称，直接定义枚举变量

enum {MON=1, TUE, WED, THU, FRI, SAT, SUN } day;

在C语言中，枚举类型是被当做int或者unsigned int类型来处理的，所以按照C语言规范是没有办法遍历枚举类型的。不过在一些特殊的情况下，枚举类型必须连续是可以实现有条件的遍历。

例：

#include <stdio.h> enum DAY {MON = 1, TUE, WED, THU, FRI, SAT, SUN } day;int main(){for (day = MON; day <= SUN; day++) // 遍历枚举元素printf("%d ", day);}//输出结果为：1 2 3 4 5 6 7

！枚举数据表的值都是整数，枚举常量不是字符串，不能用%s方式输出字符串。如需输出字符串，需要用switch语句。

例：

#include<stdio.h>enum color {red, yellow, blue, white, black };int main(){enum color num;for (num = red; num <= black; num++)switch (num){case red:printf("%s ", "red"); break;case yellow:printf("%s ", "yellow"); break;case blue:printf("%s ", "blue"); break;case white:printf("%s ", "white"); break;case black:printf("%s ", "black"); break;default:break;}return 0;}

---

例：口袋中有红、黄、蓝、白、黑5种颜色的球若干个，每次从口袋中先后取出3个球，问得到3种不同色的球的可能排列，输出每种排列的情况。

#include<stdio.h>enum color {red,yellow,blue,white,black };int main(){enum color i, j, k, pri;int loop, n = 0;for(i=red;i<=black;i++)for(j=red;j<=black;j++)if(i!=j){for(k=red;k<=black;k++)if ((k != i) && (k != j)){n = n + 1;printf("%-4d", n);for (loop = 0; loop < 3; loop++){switch (loop){case 0:pri = i; break;case 1:pri = j; break;case 2:pri = k; break;default: break;}switch (pri){case red:printf("%-10s", "red"); break;case yellow:printf("%-10s", "yellow");break;case blue:printf("%-10s", "blue");break;case white:printf("%-10s", "white");break;case black:printf("%-10s", "black");break;default:break;}}if(n%2==0) printf("\n");}}printf("\ntotal:%5d\n", n);return 0;}

程序分析：

球只能是5种色之一，而且要判断各球是否同色，应该用枚举类型变量处理。设取出的球为i、j、k，根据题意i、j、k分别是5种色球之一，井要求i≠j≠k。可以用穷举法，即把每一种排列都试一下，看哪一组符合条件。用n累计得到3种不同色球的次数。外循环使第1个球i从red变到black，内循环使第2个球j也从red变到black。如果i和j同色则不可取，只有i和j不同色(i≠j)时オ需要继续找第3个球，此时第3个球k也有5种可能(red到black)，但要求第3个球不能与第1个球或第2个球同色,即k≠i,k≠j，满足此条件就得到3种不同色的球。输出这种3色组合方案，然后使n加1。外循环全部执行完后，全部方案就已输出完了，最后输出总数n。

结构体、共用体、枚举类型总结：

共用体与结构体不同，其各成员不是分別占独立的存储单元，而是共享同一段存储空间，因此，各成员的值不会同时存在，在某一瞬时，只有最后一次被赋值的成员是有意义的。枚举类型是把可能的值全部一一列出，枚举变量的值只能是其中之一。实际生活中有些问题没有现成的数学公式来解决，只能把所有的可能性一一列出，测试其是否满足条件，这时用枚举变量比较方便。