期末-aaaa数据结构第2章

第一章数据结构实现基础引子数据存储基础流程控制基础第2章实现基础§2.1引子还是为每个具体应用都编一个程序?

从不同的应用中抽象出共性的数据组织与操作方法？[例2.1]在日常数据处理中经常碰到的问题是需要对一组数据进行基本的统计分析。比如，分析一个课程班学生的平均成绩、最高成绩、最低成绩、中位数、标准差等。同样的统计要求也可能发生在其他领域。如统计家庭每月的开支情况、生产线上各位员工计件任务的完成情况……如何利用程序设计语言实现上述抽象类型？第2章实现基础§2.1引子1.数据存储C语言（包括其他高级语言）提供了数组、结构、链表等。数据结构的存储实现跟所需要实现的操作密切相关。在数据结构里，是利用数组和链表方式来实现的，包括很复杂的数据结构，如图、树等。2.操作实现流程控制语句，即分支控制语句（如if-else、switch语句）、循环控制语句（如for、while、do-while语句）。

此外，还有模块化的程序设计方法——函数ElementTypeAverage(ElementTypeS[],intN){/*求集合元素的平均值。集合元素存放在数组S中，数组大小为N*/

inti;ElementTypeSum=0;

for(i=0;i<N;i++)Sum+=S[i];/*将数组元素累加到Sum中*/

returnSum/N;}第2章实现基础§2数据存储基础

变量是数据存储的基本单位。变量的类型决定了存储和操作。几种基本的数据类型：整型、实型（浮点型）、字符型等。提供了构造数据类型：数组、结构、指针等。数组数组是最基本的构造类型，它是一组相同类型数据的有序集合。数组中的元素在内存中连续存放，用数组名和下标可以唯一地确定数组元素。（1）一维数组定义：类型数组名[数组长度]如：inta[10];数组定义时数组长度必须确定，即常量表达式中不能包含变量。数组元素引用：数组名[下标]如：a[5]附初值：类型名数组名[数组长度]={初值表}；如intb[4]={1,2,3,4};第2章实现基础§2数据存储基础

变量是数据存储的基本单位。变量的类型决定了存储和操作。几种基本的数据类型：整型、实型（浮点型）、字符型等。提供了构造数据类型：数组、结构、指针等。数组数组是最基本的构造类型，它是一组相同类型数据的有序集合。数组中的元素在内存中连续存放，用数组名和下标可以唯一地确定数组元素。（1）一维数组定义：类型数组名[数组长度]如：inta[10];数组定义时数组长度必须确定，即常量表达式中不能包含变量。数组元素引用：数组名[下标]如：a[5]2022/12/186注意：（1）数组元素是存储在连续的一段内存空间内，每个元素所在单元的地址可通过如下公式计算：

&a[i]=&a[0]+i*length

其中length为每个单元的长度（字节数）。（2）若数组长度为N，则数组元素下标范围为：

0~N1

a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]…………2022/12/187一维数组的初始化(1)inta[10]={0,1,2,3,4,5,6,7,8,9};(2)可以只给一部分元素赋值：

inta[10]={0,1,2,3,4}；(4)在对全部数组元素赋初值时，可以不定义数组长度。例如：inta[5]={1,2,3,4,5};

等价于：

inta[]={1,2,3,4,5};2022/12/188定义二维数组类型说明符数组名[常量表达式][常量表达式];

例如：floatpay[3][6],a[3][4],b[5][10];可将二维数组看成是一维数组的一维数组！二维数组在内存中按行存储a[0][0]a[0][1]a[0][2]a[0][3]a[1][0]a[1][1]a[1][2]a[1][3]a[2][0]a[2][1]a[2][2]a[2][3]aa[0]---------a[1]---------a[2]---------a[0][0]a[0][1]a[0][2]a[0][3]a[1][0]a[1][1]a[1][2]a[1][3]a[2][0]a[2][1]a[2][2]a[2][3]

a[0][0]a[0][1]a[0][2]a[0][3]a[1][0]a[1][1]a[1][2]a[1][3]a[2][0]a[2][1]a[2][2]a[2][3]a[0]a[1]a[2]2022/12/189怎样引用二维数组也同样注意数组元素下标不要越界。对于定义的数组：inta[M][N];引用数组元素——a[i][j]则应0<=i<=M1,0<=j<=N1二维数组的初始化inta[3][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12}};inta[3][4]={1,2,3,4,5,6,7,8,9,10,11,12};可以对部分元素赋初值inta[3][4]={{1},{5},{9}};inta[3][4]={{1},{0,6},{0,0,11}};inta[3][4]={{1},{5,6}};inta[3][4]={{1},{},{9}};2022/12/1810二维数组的初始化如果对全部元素都赋初值，则初始化时可省略第一维的长度（即行数），但第二维的长度不能省略。inta[][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12}};实际上二维数组元素是存储在连续的一段内存空间内，每个元素所在单元的地址可通过如下公式计算：

&a[i][j]=&a[0][0]+(i*N+j)*length

其中N为二维数组的列数（第二维的长度），length为每个单元的长度（字节数）。第2章实现基础§2数据存储基础指针第2章实现基础§2数据存储基础

指针是C语言中一个非常重要的概念。使用指针可以对复杂数据进行处理，能对计算机的内存进行分配控制，在函数调用中使用指针还可以返回多个值。⑴指针的基本运算

取地址运算符&

间接访问运算符*指针的加、减操作。第2章实现基础§2数据存储基础（2）指针与数组

数组名是数组中第1个元素（下标为0）的地址，可以看作是常量指针，不能改变指针常量（数组名）的值。（3）用指针实现内存动态分配分配函数void*malloc(unsigned

size)。该函数分配了size个字节，并返回了指向这块内存的指针。如果分配失败，则返回一个空指针（NULL）。分配失败的原因有多种，如空间不足。释放函数voidfree(void*ptr)。该函数是将之前用malloc分配的空间还给程序或者是操作系统，也就是释放了这块内存，让它重新得到自由。注意事项：A、申请了内存空间后，必须检查是否分配成功。B、当不需要再使用申请的内存时，记得释放；释放后应该把原本指向这块内存的指针变量指向NULL，防止程序后面不小心使用了该指针。（释放的是内存，不是指针变量）C、这两个函数应该是配对使用。如果申请后不释放就是内存泄露；如果无故释放（还未使用就释放）那就是什么也没有做。释放只能一次，如果释放两次及两次以上会出现错误（释放空指针例外，释放空指针其实也等于啥也没做，所以释放空指针释放多少次都没有问题）。D、虽然malloc()函数的类型是(void*),任何类型的指针都可以转换成(void*),但是最好还是在前面进行强制类型转换，因为这样可以躲过一些编译器的检查。第2章实现基础§2数据存储基础（4）用指针实现动态顺序存储结构

int*p;p=(int*)malloc(10*sizeof(int));if(p==NULL)return;

第2章实现基础§2数据存储基础结构结构类型定义的一般形式为：struct

结构名{

类型名结构成员名1;

类型名结构成员名2;

……

类型名结构成员名n;};第2章实现基础§2数据存储基础【定义】结构类型把一些可以是不同类型的数据分量聚合成一个整体。同时，结构又是一个变量的集合，可以单独使用其变量成员。7/25structstudent//学生信息结构体{intnum;//学号

charname[20];//姓名

chargender;//性别

intage;//年龄}stu={97001,"LinLin",'F',19};structstudent//学生信息结构体{intnum;//学号

……

intage;//年龄}；structstudentsu1,stu2;第2章实现基础§2数据存储基础结构数组：结构与数组的结合结构指针：指向结构的指针（1）用*方式访问，形式：（*结构指针变量名）.结构成员名（2）用指向运算符“->”访问指针指向的结构成员，形式：结构指针变量名->结构成员名对结构数组元素成员的引用是通过使用数组下标与结构成员操作符“.”相结合的方式来完成的，其一般格式为：结构数组名[下标].结构成员名7/25结构变量的使用使用结构变量就是对其成员进行操作。格式为：结构变量名.结构成员名。此外，结构变量不仅可以作为函数参数，也可以作为函数的返回值。共用体【定义】共用体类型是指将不同的数据项组织成一个整体，它们在内存中占用同一段存储单元。第2章实现基础§2数据存储基础共用体类型定义的一般形式为：union共用体名{

类型名成员名1;

类型名成员名2;

……

类型名成员名n;};各个成员变量在内存中都使用同一段存储空间，因此共用体变量的长度等于最长的成员的长度。共用体的访问方式同结构体类似。intmain(){

unionkey{

intk;

charch[2];}u;u.k=258；printf(“%d%d\n”,u.ch[0],u.ch[1]);return0;}0000001000000001u.k=258的二进制表示：u.ch[0]=2u.ch[1]=18/25枚举类型的声明形式如下：enum枚举类型名{变量值列表};⑤枚举类型【定义】将需要的变量值一一列举出来，便构成了一个枚举类型例如：enumweekday{sun,mon,tue,wed,thu,fri,sat};枚举类型应用说明：

对枚举元素按常量处理，不能对它们赋值。如，不能写：sun=0;

枚举元素具有缺省值，它们依次为：0,1,2,......。也可以在声明时另行指定枚举元素的值，如：enumweekday{sun=7,mon=1,tue,wed,thu,fri,sat};枚举值可以进行关系运算。如：weekdaytoday；

if(today==tue);整数值不能直接赋给枚举变量，如需要将整数赋值给枚举变量，应进行强制类型转换。如：today=(weekday)3;链表

链表是一种重要的基础数据结构，也是实现复杂数据结构的重要手段。它不是顺序存储数据，而是由若干个同一结构类型的“结点”依次串接而成的，即每一个结点里保存着下一个结点的地址（指针）。

链表又分单向链表，双向链表以及循环链表等。单向链表的结构使用结构的嵌套来定义单向链表结点的数据类型。如：structNode{ElementTypeData;

structNode*Next;};第2章实现基础§2数据存储基础structNode*p;p=(structNode*)malloc(sizeof(structNode));9/25head……（1） 插入结点(p之后插入新结点t)单向链表的常见操作（2） 删除结点第2章实现基础§2数据存储基础ptt->Next=p->Next;//先p->Next=t;

head……pt=p->Next;//先p->Next=t->next;

10/25（3）单向链表的遍历p=head;while(p!=NULL){……处理p所指的结点信息；

……p=p->Next;}（4） 链表的建立

有两种常见的插入结点方式：（4.1）在链表的头上不断插入新结点；（4.2）在链表的尾部不断插入新结点。如果是后者，一般需要有一个临时的结点指针一直指向当前链表的最后一个结点，以方便新结点的插入。第2章实现基础§2数据存储基础11/25(4.1)头插入法建表

从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头之后，直到读入结束标志为止。即每次插入的结点都作为链表的第一个结点。第2章实现基础§2数据存储基础算法描述structNode*create_LinkList(void)

/*头插入法创建单链表,链表的头结点head作为返回值*/

{intdata;structNode*head,*p;head=(structNode*)malloc(sizeof(structNode));head->Next=NULL;/*创建链表的表头结点head*/while(1)//一直执行{scanf(“%d”,&data);if(data==32767)break;p=(structNode*)malloc(sizeof(structNode));p->Data=data;/*数据域赋值*/p->Next=head->Next;head->Next=p;

/*钩链，新创建的结点总是作为第一个结点*/}return(head);}返回值是表头结点head，实际就是所创建的链表。此时主函数中只要建一个structNode*类型的变量，即可调用该函数。如structNode*head;head=create_LinkList();算法描述intcreate_LinkList(structNode*head)

/*头插入法创建单链表,成功返回1，失败返回0*/

{intdata;structNode*p;while(1)//一直执行{scanf(“%d”,&data);if(data==32767)break;p=(structNode*)malloc(sizeof(structNode));if(p==NULL)return0;p->Data=data;/*数据域赋值*/p->Next=head->Next;head->Next=p;

/*钩链，新创建的结点总是作为第一个结点*/}return1;}此时表头结点head是作为函数的参数，即需要在主函数中定义一个头结点，然后在调用时将参数传过来！即structNode*head;

head=(structNode*)malloc(sizeof(structNode

));head->Data=0;head->Next=NULL;success=create_LinkList(head);

(2)尾插入法建表

头插入法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾，使其成为当前链表的尾结点。structNode*create_LinkList(void)

/*尾插入法创建单链表,链表的头结点head作为返回值*/

{intdata;structNode*head,*p,*q;head=p=(structNode*)malloc(sizeof(structNode));p->Next=NULL;/*创建单链表的表头结点head*/while(1){scanf(“%d”,&data);if(data==32767)break;q=(struct

Node*)malloc(sizeof(struct

Node));q->Data=data;/*数据域赋值*/q->Next=p->Next;p->Next=q;p=q;

/*钩链，新创建的结点总是作为最后一个结点*/}return(head);}算法描述双向链表如果将双向链表最后一个单元的Next指针指向链表的第一个单元，而第一个单元的Previous指针指向链表的最后一个单元，这样构成的链表称为双向循环链表。第2章实现基础§2数据存储基础structNode{ElementTypeData;

structNode*Next;

structNode*

Previous;};12/25双向链表的插入、删除和遍历基本思路与单向链表相同，但需要同时考虑前后两个指针。A1A2A3AN…headpt第2章实现基础§2数据存储基础structDNode{ ElementTypeData;

structDNode*Next;

structDNode*Previous;}*p,*t;指针操作顺序：①t->Previous=p;②t->Next=p->Next;③p->Next->Previous=t;④p->Next=t;①②③④13/25[例2.4]给定一个单链表L，请设计函数Reverse将链表L就地逆转，即不需要申请新的结点，将链表的第一个元素转为最后一个元素，第二个元素转为倒数第二个元素，……。【分析】基本思路是：利用循环，从链表头开始逐个处理。如何把握住循环不变式。（循环不变式表示一种在循环过程进行时不变的性质，不依赖于前面所执行过程的重复次数的断言。）在每轮循环开始前我们都面临两个序列，其中p是一个待逆转的序列，而q是一个已经逆转好的序列，如下图。每轮循环的目的是把p中的第一个元素插入到q的头上，使这轮循环执行好后，p和q还是分别指向新的待逆转序列和已经逆转好的序列。第2章实现基础§2数据存储基础p->Next=q;q=p;t……qpt=p->Next;p->Next=q;q=p;p=t;

14/25structNode*Reverse(structNode*L){structNode*p,*q,*t;

p=L;q=NULL;

while(p!=NULL){t=p->Next;p->Next=q;q=p;p=t;}

returnq;}……qpt=p->Next;p->Next=q;q=p;p=t;

类型定义typedef第2章实现基础§2数据存储基础除了使用C语言提供的标准类型和自己定义的一些结构体、枚举等类型外，还可以用typedef语句来建立已经定义好的数据类型的别名。typedef

原有类型名

新类型名typedef

structNode*Linklist;这样，Reverse函数头就可以写成：LinklistReverse(LinklistL)LinklistReverse(LinklistL)/*structNode*Reverse(structNode*L)*/{structNode*p,*q,*t;

p=L，q=NULL;

while(p!=NULL){t=p->Next;p->Next=q;q=p;p=t;}returnq;}15/25第2章实现基础§3流程控制基础顺序结构是一种自然的控制结构，通过安排语句或模块的顺序就能实现。C语言为分支控制提供了if-else和switch两类语句，为循环控制提供了for、while和do-while三类语句。三种基本的控制结构是顺序、分支和循环。函数定义函数调用函数递归语句级控制单位级控制16/25If语句：switch语句：

执行过程当switch后面“表达式”的值，与某个case后面的“常量表达式”的值相同时，就执行该case后面的语句（组）；当执行到break语句时，跳出switch语句，转向执行switch语句的下一条。while语句：1.while语句特点是“先判断，后执行”，如果表达式的值非0时，执行while语句中的内嵌语句，执行完循环体语句后再返回循环的开始部位，判断表达式的值，决定是否执行循环，当循环的条件为0时，退出循环。2.循环体语句如果是多条语句，采用复合语句的形式，即采用符号{}把语句包含进来。

3.在循环体内应该包含改变循环条件表达式值的语句，否则会导致“死”循环。

do-while语句：1．do-while语句特点是“先执行，后判断”，先执行一次指定的循环体，当表达式的值为非0时，即为真时，返回继续执行循环体，否则当表达式的值为0时，退出循环。因此，不论最初表达式的值是否为1都执行一次循环体。2．循环体语句如果是多条语句，采用复合语句的形式，即采用符号{}把语句包含进来。3．在循环体内应该包含改变循环条件表达式值的语句，否则会导致“死”循环。for语句：表达式1：循环体变量赋初值；表达式2：循环退出条件；表达式3：循环变量增值。三个表达式都可以省略，但是省略的表达式要在其他位置以语句形式出现，否则可能导致死循环。break语句、continue语句：Break强制循环结束；用于swich语句。Contunue跳过本次循环，执行下一次循环。循环嵌套：指大循环中嵌套小循环3种循环（for、while、do-while）可以相互嵌套[例2.5]求100到200之间的所有素数。[分析]可以设定两重循环：大循环（外层循环）控制整数i在100到200之间变化（用for语句），而小循环（内层循环）则用来判别i是否是素数（用while语句）。第2章实现基础§3流程控制基础intmain(){

inti,j;

for(i=100;i<=200;i++){/*外层循环*/j=2;

while(j<i&&i%j!=0)j++;

/*内层循环,判别i是否是素数*/

if(j==i)printf(“%d”,i);

/*j==i说明在上面的while循环中i都不能被j整除，因此i是素数*/}return0;}17/25函数与递归比如：C语言提供了实数和整数的加法运算符号“+”来完成运算；但是“+”不能对复数做加法运算；可以写一个函数来实现这个功能。第2章实现基础§3流程控制基础【定义】函数是一个完成特定工作的独立程序模块。只需定义一次，就可以多次调用。

函数包括库函数和自定义函数两种。例如，scanf、printf等库函数由C语言系统提供定义，编程时只要直接调用即可。

在程序设计中，往往根据模块化程序设计的需要，用户可以自己定义函数，属于自定义函数。先定义复数类型ImgType，以约定何为复数：structImage{doubler;doublei;};typedefstructImageImgType;再定义复数的加法函数：ImgTypeImgAdd(ImgTypea,ImgTypeb){ImgTypec;c.r=a.r+b.r;c.i=a.i+b.i;/*实部和虚部分别相加*/

returnc;}有了这个函数，以后可以在任何需要计算复数加法的地方调用它！18/25在设计函数时，注意掌握以下原则：第2章实现基础§3流程控制基础（1）函数功能的设计原则：结合模块的独立性原则，函数的功能要单一，不要设计多用途的函数，否则会降低模块的聚合度；（2）函数规模的设计原则：函数的规模要小，尽量控制在50行代码以内，这样可以使得函数更易于维护；（3）函数接口的设计原则：结合模块的独立性原则，函数的接口包括函数的参数（入口）和返回值（出口），不要设计过于复杂的接口，合理选择、设置并控制参数的数量，尽量不要使用全局变量，否则会增加模块的耦合度。19/25递归函数【定义】一个函数除了可以调用其他函数外，C语言还支持函数直接或间接调用自己。这种函数自己调用自己的形式称为函数的递归调用，带有递归调用的函数也称为递归函数。两个关键点：（1） 递归出口：即递归的结束条件，到何时不再递归调用下去;第2章实现基础§2.3流程控制基础（2） 递归式子：当前函数结果与准备调用的函数结果之间的关系，如求阶乘函数的递归式子：

Factorial(n)=n*Factorial(n-1)。longintFactorial(intn){if(n==0)return1;else

returnn*Factorial(n-1);}注意：程序代码不能写成上述式子！！递归调用20/256.1指针的引出一.地址与指针

1.地址与取地址运算

C程序中的变量在内存中占有一个可标识的存储区,

每一个存储区是由若干个字节组成,每一个字节都有自己的地址,而一个存储区的地址是指该存储区中第一个字节的地址C语言允许在程序中使用变量的地址(通过地址运算符&可得到)

如:floatx;

变量x的地址----&x

inta[10];

数组变量a的地址----数组名a

2.指针与指针变量(1)变量的访问方式①直接访问:通过变量名或地址访问变量的存储区

例:scanf(“%d”,&x);

x=sqrt(x);printf(“%d”,x);②间接访问:将一个变量的地址存放在另一个变量中.

如将变量x的地址存放在变量p中,访问x时先找到p,

再由p中存放的地址找到xpx201210101010(2)指针:一个变量的指针就是该变量的地址(指针就是地址)(3)指针变量:存放变量地址的变量,它用来指向另一个变量

二、指针变量的定义1.格式:数据类型

*指针变量名;

例int*p1;char*p2;2.说明:(1)在变量定义时,*号表示该变量是指针变量

(注意:指针变量是p1,p2,不是*p1,*p2)(2)定义指针变量后,系统为其分配存储空间,用以存放其他变量的地址,但在对指针变量赋值前,它并没有确定的值,也不指向一个确定的变量例:intx,*p;x=5;px2012101051234注:指针变量p的值是随机值,

此时p和x并无关联(3)使指针变量指向一个确定的变量必须进行赋值intx,*p;x=5;p=&x;px201210105