数据结构 与 算法番外篇：恶补C语言内容提要v预定义变量和类型：#define 和#typedefv动态存储分配：malloc函数v函数的参数传递v指针和指针操作v结构体和结构体成员引用9/29/20222预定义常量和类型？干嘛用的？9/29/20223用#define命令预定义常量1.#include 2.#define PI 3.14159/定义符号常量定义符号常量PI3.void main()4.5.float s,v,r=10.0;6.s=4*PI*r*r;7.v=4*PI*r*r*r/3;8.printf(s=%f v=%fn,s,v);9.#define定义格式为：#define 使用符号常量的好处：含义清楚，增强程序可读性在需要改变一个常量时能做到“一改全改”例:编写程序，计算并输出半径为10的球表面积和球体的体积s=1256.637085 v=4188.790039【运行结果】9/29/20224类C语言中的预定义常量9/29/20225/函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE-1#define OVERFLOW -2/Status 是函数的类型，其/值是函数结果状态代码typedef int Status;例1-7：抽象数据类型Triplet的表示和实现1.Status Get(Triplet T,int i,ElemType&e)2./0 i 4,用用e返回返回T的第的第 i 元的值元的值3.if(i3)4.return ERROR;5.e=Ti-1;6.return OK;7.等价于在C程序开头定义如下内容目的：给常量取一个别名，通常是用户容易理解的单词。
1.int Get(Triplet T,int i,ElemType&e)2./0 i 4,用用e返回返回T的第的第 i 元的值元的值3.if(i3)4.return 0;5.e=Ti-1;6.return 1;7.typedef?ElemType？9/29/20226用typedef命令建立类型别名9/29/20227vtypedef是type define的缩写其实，typedef语句并不是用于定义新的数据类型，而是为已定义的数据类型定义别名vtypedef语句的一般格式是：typedef ;例如：typedef int INTEGER;定义类型名INTEGER是int的别名在该语句之后的程序中，标识符INTEGER和保留字int的作用相同例如：INTEGER i,j;编译时系统将把它当做int i,j;来处理，也就是把i,j定义为整型变量类C语言中的预定义类型9/29/20228typedef int Elemtype;typedef ElemType*Triplet;例：获取顺序结构线性表中第i个元素的内容1.Status Get(Triplet T,int i,ElemType&e)2.3.if(i3)4.return ERROR;5.e=Ti-1;6.return OK;7.若在C程序开头定义如下内容，则若在C程序开头定义如下内容，则Elemtype 是数据元素类型，可以是整型、字符型、自定义结构体等等，由用户自行定义。
typedef char Elemtype;typedef ElemType*Triplet;1.int Get(int*T,int i,int&e)2.3.if(i3)4.return 0;5.e=Ti-1;6.return 1;7.1.int Get(char*T,int i,char&e)2.3.if(i3)4.return 0;5.e=Ti-1;6.return 1;7.动态分配？为什么使用ElemType*9/29/20229这里主要涉及两个C语言的重要概念：1）变量的内存分配；2）指针；【注意】由于采用顺序存储结构，我们可以把三元组 Triplet定义成：类型为ElemType的数组，数组的长度为3.变量的内存分配？9/29/202210变量的内存分配与地址v计算机主存储器由一个个存储单元组成，微型计算机以字节作为存储单元单位v每个存储单元具有唯一的地址，存储单元的地址是一个无符号整数，主存储器的所有存储单元的地址是连续的v程序中处理的数据需要在内存中占用存储单元，编译系统根据变量的数据类型，为变量分配若干个存储单元（字节）例如VC+系统为每个字符变量分配一个字节，为每个整型变量分配4个字节，为每个单精度实数分配4个字节。
v一个变量所占用存储区域的所有字节都有各自的地址，C系统把存储区域中第一个字节的地址作为变量的地址执行int a;执行a=3;a地址:100地址:103不定值四个字节a地址:100地址:10339/29/202211获取变量的内存单元地址v变量地址可由取地址运算符”&”和变量名运算获得q例如输入函数scanf(“%d”,&a),其中，表达式”&a”的值就是变量a的地址，执行该函数从键盘读取一个整数，存入变量a的存储区域中9/29/202212数组的静态内存分配与单元地址执行int a3;a0地址:100地址:103不定值四个字节a1地址:104地址:107不定值a2地址:108地址:111不定值执行a0=3;a0地址:100地址:1033a1地址:104地址:107不定值a2地址:108地址:111不定值定义一维数组的语句格式：数组名常量表达式数组名本身就是地址，它代表该数组首元素的地址设a为一维数组，则有a=&a0，即 a 代表 a0 的地址9/29/202213变量地址输出的例子9/29/202214v变量地址输出示例，程序清单如下：1.#include 2.void main()3.4.int a,b3;5.printf(a的地址（十进制）：%dn,&a);6.printf(“b的地址（十进制）：%dn,b);7.printf(“b1的地址（十进制）：%dn,&b1);8.printf(“b1的地址（十进制）：%dn,&b2);9.【运行结果】a的地址（十进制）：1245052b的地址（十进制）：1245036b1的地址（十进制）：1245040b2的地址（十进制）：1245044指针？动态存储分配？9/29/202215指针存储整数的变量称为整型变量，存储字符的变量称为字符变量，存储浮点数的变量称为浮点型变量，存储地址的变量就是指针（变量）！9/29/202216指针变量9/29/202217定义指针变量的一般形式为：*;其中，为某已定义的数据类型，可以是系统预定义的类型，也可以是用户自己定义的类型，可以是简单类型，也可以是构造类型。
符号“*”表示定义的是一个指向“基类型”的指针变量例如：int var=10;int*pointer=&var;值:1310588变量名:pointer地址:1310584值:10变量名:var地址:1310588图10.1.1 指针变量示意图【注意】不能把一个变量的地址赋给一个不同基类型的指针例如下面的初始化是错误的：float f;int*p=&f;指针的赋值v可以把指针常量或另一个同类型的指针变量赋给指针变量例如：int a,*p1,*p2=0;/对p2初始化p1=p2;/把p2的值赋给p1p2=&a;/把变量a的地址赋给p2v【注意】基类型相同的指针才能进行赋值运算v指针变量的值虽然是一个整数，但不能把整数（0除外）直接赋给指针变量，也不能把指针赋给整型变量例如下面的运算时错误的：p1=100;/错误a=p1;/错误9/29/202218使用指针访问变量v要访问变量中的数据，有两种不同的方式q直接访问：C语言屏蔽了底层的实现细节，在程序中定义的变量，编译时系统就给这个变量分配适当的内存单元，并把变量名和变量存储地址对应起来，我们就可以直接在程序中 通过变量名访问存储单元中的数据。
o例如：int x;x=5;q间接访问：变量 x 的地址也是数据，如果定义一种特殊的变量 p（即指针变量），用指针变量 p 存放某变量 x 的地址，就可以由变量 p 的值得到变量 x 的地址，然后通过该地址取得变量 x 的值o例如：int x;int*p=&x;*p=5;o【注意】这里指向运算符*的运算对象只能是指针变量，*的运算结果得到运算对象（指针变量）所指的变量p 就表示变量 x，是对变量 x 的间接引用p 是整型变量，不是指针，*p 可以像一般整型变量一样使用9/29/202219使用malloc函数进行动态存储分配vC语言通过头文件提供malloc函数用于分配存储空间vmalloc函数的原型为：void*malloc(unsigned size);q说明(1)形参size用于确定分配存储空间的字节数，(2)函数返回的指针是无类型的，必须强制转换成相应的类型3)如果动态分配分配失败，返回的指针值为0.9/29/202220动态存储空间分配示例，程序清单如下：1.#include 2.#include 3.void main()4.5.int*p,*q;6.p=(int*)malloc(sizeof(int);/返回指针强制转换为整型7.*p=10;/如果没有前一行，赋值出错！8.q=(int*)malloc(5*sizeof(int);/返回指针强制转换为整型9.q4=5;/如果没有前一行，赋值出错！10.printf(“*p=%d,q4=%dn,*p,q4);11.能看懂这段代码了吗？9/29/202221假定我们在C程序开头定义如下内容typedef int Elemtype;typedef ElemType*Triplet;1.int InitTriplet(int*&T,int v1,int v2,int v3)2.3.T=(int*)malloc(3*sizeof(int);4.if(!T)exit(-2);5.T0=v1;T1=v2;T2=v3;6.return 1;7.函数参数传递的格式为什么不同？9/29/202222C语言函数的两种参数传递方式v值传递，传递的是实际参数的值，形式参数变量复制了实际参数的值，在函数内部操作形式参数对实际参数没有影响。
q形式如：void swap(int x,int y);v引用传递，形式参数成为实际参数的引用，在函数操作形式参数就是操作实际参数q形式如：void swap(int&x,int&y);v所以，如果要在函数内部修改实际参数，应该使用引用传递的方式9/29/202223值传递方式传递函数参数v值传递的例子：调用函数，交换两个变量的值/程序1，使用整型参数：1.#include 2.void swap(int x,int y)3./交换形参x，y的值4.int temp;5.temp=x;6.x=y;7.y=temp;8.9.void main()10.11.int a,b;12.printf(“请输入两个整数a和b:”);13.scanf(%d%d,&a,&b);14.printf(调用函数前：a=%dtb=%dn,a,b);15.swap(a,b);16.printf(调用函数后：a=%dtb=%dn,a,b);17.【运行结果】请输入两个整数a和b:3 5调用函数前：a=3 b=5调用函数后：a=3 b=59/29/202224引用传递方式传递函数参数v引用传递的例子:调用函数，交换两个变量的值。
/程序1，使用整型参数：1.#include 2.void swap(int&x,int&y)3./交换形参x，y的值4.int temp;5.temp=x;6.x=y;7.y=temp;8.9.void main()10.11.int a,b;12.printf(“请输入两个整数a和b:”);13.scanf(%d%d,&a,&b);14.printf(调用函数前：a=%dtb=%dn,a,b);15.swap(a,b);16.printf(调用函数后：a=%dtb=%dn,a,b);17.【运行结果】请输入两个整数a和b:3 5调用函数前：a=3 b=5调用函数后：a=5 b=39/29/202225能看懂这段代码了吗？9/29/202226结构体struct？9/29/202227结构体概述v数组类型用于表示一组相关联的、同类型的数据集合v一个数组不仅存储一批同类型数据，而且能表达各数据元素之间的线性关系v在实际应用中，有时要将不同类型的数据元素组合成为一个有机整体例如：一种商品包括商品编号、商品名称、商品价格、商品库存量等信息，这些数据项是相互关联的v在C语言中，为了将这些相互联系而类型不同的数据作为一个整体处理，引入了结构体类型。
v结构体类型由一组相互关联的数据元素（元素类型可以相同或不相同）构造而成9/29/202228结构体类型的定义v结构体类型比较复杂，系统无法事先为用户定义一种统一的结构体类型在定义结构体变量之前，用户要先定义结构体类型，即用自己定义的结构体类型定义结构体变量v定义结构体类型，应该指出该结构体类型叫什么名字，包含哪些数据元素，各数据元素叫什么名字，属于什么数据类型等v定义结构体类型的一般格式如下：struct 结构体名数据类型 成员项1;数据类型 成员项2;数据类型 成员项n;【注意】结构体类型定义是一个语句，要以分号结束实例：struct Commoditychar Name20;int Price,Count;char Provenance30;9/29/202229结构体变量的定义结构体类型反映的是所处理对象的抽象特征，而要描述具体对象时，就需要定义结构体类型的变量，简称结构体变量或结构体结构体变量的定义必须在结构体类型定义之后，它的一般形式是：struct 结构体类型名 结构体变量名;例如，前面已经定义了结构体类型 struct Commodity，可以用它来定义变量：struct Commodity TV;NamePriceCountProvenanceTelevision210020FujianCommodity TV=“Television”,2100,30,”Fujian”;NamePriceCountProvenance随机值随机值随机值随机值9/29/202230typedef与结构体struct LNode ElemType data;struct Lnode*next;typedef struct LNode LNode;typedef struct LNode*LinkList;struct LNode L;LNode L;struct LNode*P;LinkList P;结构体名结构体名类型别名类型别名结构体名可省略结构体名可省略类型别名类型别名9/29/202231对结构体变量成员项的引用v在程序设计中，如果定义结构体变量，对结构体变量成员的引用形式为：结构变量名.成员名例如上面定义的结构体变量TV，它的成员引用形式是：TV.Name,TV.Provenance例如：TV.Count=30;TV.Provenance=“Fujian”;v结构体的成员项也称为成员变量，其作用和简单变量一样，可以作为表达式的运算对象，进行各种操作运算。
例如：scanf(“%s”,TV.Name);scanf(“%d”,&TV.Price);TV.Price-=100;v在程序设计中，如果定义结构体指针，对结构体变量成员的引用形式为：结构指针名-成员名例如上面定义的结构体指针pTV，它的成员引用形式是：pTV-Name,pTV-Provenance例如：TV-Count=30;TV-Provenance=“Fujian”;v结构体的成员项也称为成员变量，其作用和简单变量一样，可以作为表达式的运算对象，进行各种操作运算例如：scanf(“%s”,TV-Name);scanf(“%d”,&TV-Price);TV-Price-=100;9/29/202232指针的运算？1.Status ListDelete_Sq(SqList&L,int i,ElemType&e)/算法2.52./在顺序线性表L中删除第i个元素，并用e返回其值3./i的合法值为1iListLength_Sq(L)4.ElemType*p,*q;5.if(iL.length)return ERROR;/i值不合法6.p=&(L.elemi-1);/p为被删除元素的位置7.e=*p;/被删除元素的值赋给e8.q=L.elem+L.length-1;/表尾元素的位置9.for(+p;p=q;+p)*(p-1)=*p;/被删除元素之后的元素左移10.-L.length;/表长减111.return OK;12./ListDelete_Sq9/29/202233指针的算术运算指针和整数进行加减运算v只有当指针指向数组时，这种运算才有意义。
例如当指针p指向数组时，下面运算时合法的：p+;/p指向下一个数组元素p=p+2;/p指向当前元素后的第二个元素1.#include 2.void main()3.4.int*p1,b4=1,2,3,4;5.p1=b;/把数组变量b的首地址赋给指针变量p16.printf(value=%dn,*p1);7.p1+;8.printf(value=%dn,*p1);9.p1=p1+2;10.printf(value=%dn,*p1);11.【运行结果】value=1value=2value=49/29/202234能看懂这段代码了吗？9/29/2022351.Status ListDelete_Sq(SqList&L,int i,ElemType&e)/算法2.52./在顺序线性表L中删除第i个元素，并用e返回其值3./i的合法值为1iListLength_Sq(L)4.ElemType*p,*q;5.if(iL.length)return ERROR;/i值不合法6.p=&(L.elemi-1);/p为被删除元素的位置7.e=*p;/被删除元素的值赋给e8.q=L.elem+L.length-1;/表尾元素的位置9.for(+p;p=q;+p)*(p-1)=*p;/被删除元素之后的元素左移10.-L.length;/表长减111.return OK;12./ListDelete_Sq。