《结构体数组学习》PPT课件.ppt

,一、结构体数组,形式一:间接定义 struct student int num; char name20; ; student stu2;,形式二:直接定义 struct student int num; char name20; stu2;,形式三:无名定义 struct int num; char name20; stu2;,结构数组的初始化,顺序初始化: struct student int num; char name20; int age; ; student stu =200401,“Wang Yong”, 19, 200402,“Li Gang”, 20;,如果对所有数组元素赋初值,则数组元素个数可省略。,分行初始化: struct student int num; char name20; int age; ; student stu = 200401,“Wang Yong”, 19, 200402,“Li Gang”, 20 ;,结构数组的引用,引用形式：结构数组名下标.成员名 (结构数组元素.成员名) 例如：stu0.num,struct student int num; char name20; char sex; int age; stu3;,stu1.age+;,; strcpy(, “ZhaoDa”);,cinstu1.num;, EXAMPLE 2. . . Sort by student aver,#include #include #include using namespace std; struct Grade int s1; int s2; int s3; float aver; ; struct StudentRec int num; string name; Grade s; ;,typedef struct StudentRec STUDENT; STUDENT inputstu( int ); void sort( STUDENT stu , int ); void main() STUDENT stu 6 ; for( int i=0; i=0; i- ) cout6-i“: “stu i .num“ “setw(6)left stu i .name“ “stu i .s.averendl; ,声明结构体数组,用结构体数组名作实参,void sort( STUDENT stu , int n) int i, j, min; STUDENT t; for ( i=0; in; i+ ) min=i; for( j=i+1; jn; j+) if ( stu j .s.averstu min .s.aver ) min = j; t = stu i ; stu i =stu min ; stu min = t; ,用结构体数组名作形参,选择法排序,指针不仅可以指向普通变量、数组、 数组元素、函数，同样的，指针也可以指向结构变量，我们把指向结构变量的指针称为结构指针。结构指针指向了结构变量所在存储空间的起始地址。,二、 结构体指针,定义形式：结构类型名 *结构指针名; 使用结构指针引用结构成员： 方法一：(*结构指针).成员名 方法二：结构指针-成员名 结构指针的运算：,1.指向结构变量的指针,指针不仅可以指向普通变量、数组、 数组元素、函数，同样的，指针也可以指向结构变量，我们把指向结构变量的指针称为结构指针。结构指针指向了结构变量所在存储空间的起始地址。,二、 结构体指针,定义形式：结构类型名 *结构指针名; 使用结构指针引用结构成员： 方法一：(*结构指针).成员名 方法二：结构指针-成员名 结构指针的运算：,1.指向结构变量的指针,(*s).num,struct student int num; char name20; char sex; int age; ; student stu; student *s=,指针不仅可以指向普通变量、数组、 数组元素、函数，同样的，指针也可以指向结构变量，我们把指向结构变量的指针称为结构指针。结构指针指向了结构变量所在存储空间的起始地址。,定义形式：结构类型名 *结构指针名; 使用结构指针引用结构成员： 方法一：(*结构指针).成员名 方法二：结构指针-成员名 结构指针的运算：,1.指向结构变量的指针,(*s).num,s是结构指针，(*s)表示s指向的结构变量stu，(*s).num表示s所指的结构变量中的成员num，所以(*s).num的意义是先访问结构指针所指向的结构变量，再访问该结构变量中的成员。由于结构成员运算符“ . ”优先于指针运算符“*”，故(*s).num中的括号( )不能省略。,s-num,指向结构成员运算符 优先级和“ . ”同级别 结合性是左结合,指针不仅可以指向普通变量、数组、 数组元素、函数，同样的，指针也可以指向结构变量，我们把指向结构变量的指针称为结构指针。结构指针指向了结构变量所在存储空间的起始地址。,定义形式：结构类型名 *结构指针名; 使用结构指针引用结构成员： 方法一：(*结构指针).成员名 方法二：结构指针-成员名 结构指针的运算：,1.指向结构变量的指针,(*s).num,s-num,常用运算符的优先级顺序: 一级运算符( - .) 单目运算符( ! + - - * & sizeof (类型) ) 算术运算符关系运算符逻辑运算符 条件条件符赋值运算符逗号运算符,访问结构变量中的结构成员共有三种方式： 结构变量.成员名 stu.num (*结构指针).成员名 (*s).num 结构指针-成员名 s-num,指针不仅可以指向普通变量、数组、 数组元素、函数，同样的，指针也可以指向结构变量，我们把指向结构变量的指针称为结构指针。结构指针指向了结构变量所在存储空间的起始地址。,定义形式：结构类型名 *结构指针名; 使用结构指针引用结构成员： 方法一：(*结构指针).成员名 方法二：结构指针-成员名 结构指针的运算：,1.指向结构变量的指针,(*s).num,s-num,结构指针指向的是结构变量所在存储空间的首地址。将结构指针加1，则指针指向内存中下一个结构变量，其地址的增加量取决于指针所指向的结构的长度。 coutnum; /输出结构成员num的值。 coutnum+; /*先输出结构成员num的值，然后将该值 加1。*/ coutnum; /*先取结构成员num的值，然后将 该值加1, 之后再输出。*/ coutnum; /*先输出num的值，然后指针加1，指向 下一个结构变量。*/,在C+语言中，把指向结构数组或数组元素的指针称为结构数组指针。,#include struct student int num; char name20; float score; ;,2.指向结构体数组的指针, 例 使用结构数组指针输出数据,void main( ) student stu3=1001,“Liu Jin“,75, 1002,“Li Lan“,82, 1003,“Ma Kai“,80 ; student *s=stu; coutnumnamescoreendl; ,程序的运行结果为： Num Name Score 1001 Liu Jin 75 1002 Li Lan 82 1003 Ma Kai 80,注意： (1)如果s的初值为stu，即指向第一个元素stu0 则s+1后指向下一个元素stu1的起始地址。 (2)程序中已定义了指针s是指向struct student 类型数据的变量,它只能指向一个struct student型的数据,而不能指向stu数组元素中的某一个成员。,三、动态分配内存,通常定义变量（或对象），编译器在编译时都可以根据该变量（或对象）的类型知道所需内存空间的大小，从而系统在适当的时候为他们分配确定的存储空间。这种内存分配称为静态存储分配 有些操作对象只有在程序运行时才能确定，这样编译器在编译时就无法为他们预定存储空间，只能在程序运行时，系统根据运行时的要求进行内存分配，这种方法称为动态存储分配。所有动态存储分配都在堆区中进行。,当程序运行到需要一个动态分配的变量或对象时，必须向系统申请取得堆中的一块所需大小的存贮空间，用于存贮该变量或对象。当不再使用该变量或对象时，也就是它的生命结束时，要显式释放它所占用的存贮空间，这样系统就能对该堆空间进行再次分配，做到重复使用有限的资源。,new运算符用于申请所需的内存空间，返回指定类型的一个指针(常量，即内存空间首地址)。它的语法格式为： 指针变量 = new 数据类型; 其中，指针变量应预先声明，指针变量指向的数据类型与new后面的数据类型相同。若申请成功，则返回分配空间的首地址赋给指针变量；否则（如没有足够的内存空间）返回0（NULL一个空指针）。,例如： int *p; p=new int ;,(20);,系统为指针p开辟了一个用来保存int类型数据的内存空间(在申请时，也可以进行初始化 )。,new 运算符,在C+中，申请和释放堆中分配的存贮空间，分别使用new和delete的两个运算符来完成，其使用的格式如下：,例如： int *p; p=new int20 ;,系统为指针p开辟了一个用来保存int类型数组的内存空间，数组中有20个元素 。,也可以用new运算符申请一块保存数组的内存空间，即动态创建一个数组。 格式为：指针变量new 数据类型数组大小; 其中，数组大小给出数组元素的个数，指针指向分配的内存空间首地址，指针的类型与new后的数据类型相同。,new 运算符,当程序中不再使用由运算符new申请的某个内存空间时，可以用delete运算符释放它。 它的语法格式为：delete 指针变量; delete 常量指针变量; 它的功能是释放由new申请到的内存空间。其中指针变量是指向需要释放内存空间的指针变量名字，并且delete只是删除动态内存空间，并不是将指针变量本身删除。,常量可以省略，且不用考虑数组的维数。,int *p1= new int; int *p2= new int 20; delete p1; delete p2;,delete 运算符,1.new 运算符返回的是一个指向所分配类型变量（对象）的指针。对所创建的变量或对象，都是通过该指针来间接操作的，而动态创建的对象本身没有名字。,2.一般定义变量和对象时要用标识符命名，称命名对象，而动态所创建的变量或对象称无名对象。堆区是不会自动在分配时做初始化的（包括清零），所以必须用初始化式（ )来显式初始化。但不可对动态数组初始化,3. 指针变量new 数据类型数组大小; 请注意“数组大小”不是常量表达式，即它的值不必在编译时确定，可以在运行时确定。变量 n 在编译时没有确定的值，而是在运行中输入，按运行时所需分配堆空间，这一点是动态分配的优点，可克服数组“大开小用”的弊端，在表、排序与查找中的算法，若用动态数组，通用性更好。,说明：,4. 动态分配失败。返回一个空指针（NULL），表示发生了异常，堆资源不足，分配失败。因此，一定要检查分配的内存指针是否为空，如果是空指针，则不能引用这个指针，否则将造成系统崩溃。,说明：,int *p= new int 20; if (p!=NULL) else ,5. 指针删除与堆空间释放。删除一个指针p; 实际意思是删除了p所指的目标（变量或对象等），释放了它所占的堆空间，而不是删除本身，释放堆空间后，成了空悬指针。,6. 动态分配的变量或对象的生命期。无名对象的生命期并不依赖于建立它的作用域，比如在函数中建立的动态对象在函数返回后仍可使用。我们也称堆空间为自由空间（free store）就是这个原因。但必须记住释放该对象所占堆空间，并只能释放一次，在函数内建立，而在函数外释放是一件很容易失控的事，往往会出错。,说明：,7内存泄漏（memory leak）和重复释放。new与 delete 是配对使用的， delete只能释放堆空间。如果new返回的指针值丢失，则所分配的堆空间无法回收，称内存泄漏，同一空间重复释放也是危险的，因为该空间可能已另分配，所以必须妥善保存new返回的指针，以保证不发生内存泄漏，也必须保证不会重复释放堆内存空间。,链表是一种最常见的数据结构，分为动态链表和静态链表。程序员经常使用的是动态链表，它能进行动态内存分配，可以适应数据动态增减的情况，并且可以方便地进行数据元素的插入、删除等操作。 链表有单向链表、双向链表、循环链表等形式。下图是一个单向链表的结构示意图。,四、 用指针处理链表,链表是一种最常见的数据结构，分为动态链表和静态链表。程序员经常使用的是动态链表，它能进行动态内存分配，可以适应数据动态增减的情况，并且可以方便地进行数据元素的插入、删除等操作。 链表有单向链表、双向链表、循环链表等形式。下图是一个单向链表的结构示意图。,8.6 用指针处理链表,头指针:每个链表都有一个“头指针”变量，图中以head表示，它存放一个地址，指向链表的第一个元素。 结点:链表中每一个元素被称为一个“结点”(node)。每个结点都应包含两部分，第一部分是链表中存放的用户需要用的实际数据，在图中以、表示；第二部分是一个地址，指向下一个结点。 表尾:链表中最后一个结点称为“表尾”，表尾结点存放一个NULL(表示空地址)，因此该结点不再指向其它结点 。,链表是一种最常见的数据结构，分为动态链表和静态链表。程序员经常使用的是动态链表，它能进行动态内存分配，可以适应数据动态增减的情况，并且可以方便地进行数据元素的插入、删除等操作。 链表有单向链表、双向链表、循环链表等形式。下图是一个单向链表的结构示意图。,链表中各结点在内存中可以不是连续存放的，要找到某一结点,必须先找到上一个结点,根据它提供的下一个结点的地址才能找到下一个结点。结点中的地址用指针变量来实现。即一个结点中应包含一个指针变量,用它存放下一个结点的地址。 用结构变量作链表中的结点是最合适的，一个结构体变量包含若干成员，它们可以是数值类型、字符类型、数组类型，也可以是指针类型。我们用这个指针类型成员来存放下一个结点的地址。,链表是一种最常见的数据结构，分为动态链表和静态链表。程序员经常使用的是动态链表，它能进行动态内存分配，可以适应数据动态增减的情况，并且可以方便地进行数据元素的插入、删除等操作。 链表有单向链表、双向链表、循环链表等形式。下图是一个单向链表的结构示意图。,struct student int num; float score; student *next; ；,每个结点数据都属于student结构类型，因而next也应为一个student类型的结构指针，它指向下一结点的地址。用这种方法可以建立链表。,链表是一种最常见的数据结构，分为动态链表和静态链表。程序员经常使用的是动态链表，它能进行动态内存分配，可以适应数据动态增减的情况，并且可以方便地进行数据元素的插入、删除等操作。 链表有单向链表、双向链表、循环链表等形式。下图是一个单向链表的结构示意图。,struct student int num; float score; student *next; ；,每个结点数据都属于student结构类型，因而next也应为一个student类型的结构指针，它指向下一结点的地址。用这种方法可以建立链表。,链表的特点在于动态地进行内存分配，即在需要时才会开辟一个结点的存储空间，当某个存储空间不再需要时可以释放。在+语言中，可使用new和delete两个运算符进行动态内存的分配和释放。,算法分析: 假设输入的学号为0时，表示建立链表的过程结束，该结点不应链接到链表中。根据题目要求，链表中结点数据应采用结构体类型来描述。 同时定义三个指针变量head，p1，p2，它们都是结构类型的指针变量。结构指针变量head的初值为NULL(即等于0),此时是空链表(head不指向任何结点,链表中无结点)，当链表建成后，应使head指向第一个结点。, 例 写一个函数，建立一个有5名学生数据(包含学号和成绩)的单向动态链表。,struct student long num; float score; student *next; ; student *head, *p1, *p2; int n=0; /n为结点个数，初值为0,p1,数据域,指针域,建立链表的过程: 首先利用new运算符，在内存中开辟一个存储空间,用来存放新结点。使p1,p2都指向该存储空间,然后从键盘上输入一个学生的数据进行判断,如果输入的p1-num不等于0，而且是第一个结点数据（n1）,则把p1的值赋给head(head=p1),这样，结构指针head就指向了链表中的第一个结点。,p2,p1,head,(n=1),建立表头结点,0001,89.5,p2,p1,head,0001,89.5,然后利用new再开辟一个新的存储空间，用来存放另一个结点，并使p1指向新开辟的存储空间，然后输入该结点的数据。如果输入的p1-num不等于0，而且不是第一个结点（n1）时，则应将新建结点与前一个结点连接在一起,即:执行p2 - next=p1，使第一个结点的next 成员指向第二个结点。 接着使p2p1，即:使p2指向刚刚建立的结点(即建立链表进程中的最后一个结点) 。,建立中间结点,(n=2),p2,p1,head,0001,89.5,然后利用new再开辟一个新的存储空间，用来存放另一个结点，并使p1指向新开辟的存储空间，然后输入该结点的数据。如果输入的p1-num不等于0，而且不是第一个结点（n1）时，则应将新建结点与前一个结点连接在一起,即:执行p2 - next=p1，使第一个结点的next 成员指向第二个结点。 接着使p2p1，即:使p2指向刚刚建立的结点(即建立链表进程中的最后一个结点) 。,建立中间结点,(n=2),0002,76,p2,p1,head,0001,89.5,然后利用new再开辟一个新的存储空间，用来存放另一个结点，并使p1指向新开辟的存储空间，然后输入该结点的数据。如果输入的p1-num不等于0，而且不是第一个结点（n1）时，则应将新建结点与前一个结点连接在一起,即:执行p2 - next=p1，使第一个结点的next 成员指向第二个结点。 接着使p2p1，即:使p2指向刚刚建立的结点(即建立链表进程中的最后一个结点) 。,建立中间结点,(n=2),0002,76,p2,p1,head,0001,89.5,然后利用new再开辟一个新的存储空间，用来存放另一个结点，并使p1指向新开辟的存储空间，然后输入该结点的数据。如果输入的p1-num不等于0，而且不是第一个结点（n1）时，则应将新建结点与前一个结点连接在一起,即:执行p2 - next=p1，使第一个结点的next 成员指向第二个结点。 接着使p2p1，即:使p2指向刚刚建立的结点(即建立链表进程中的最后一个结点) 。,(n=2),0002,76,p2,head,0001,89.5,0002,76,重复步骤 ,依次建立若干个新结点。每次都让p1指向新建立的结点，p2指向链表中最后一个结点,然后用“p2-next=p1”，把p1所指的结点连接到p2所指结点的后面。 当输入某个结点数据后,如果p1-num等于0,则不再执行上述循环,此新结点不应该被连接到链表中,用语句“p2-next=NULL”,将NULL值赋给前一个结点的next成员。 至此，建立链表的过程结束。,p1,(n=2),p2,head,0001,89.5,0002,76,重复步骤 ,依次建立若干个新结点。每次都让p1指向新建立的结点，p2指向链表中最后一个结点,然后用“p2-next=p1”，把p1所指的结点连接到p2所指结点的后面。 当输入某个结点数据后,如果p1-num等于0,则不再执行上述循环,此新结点不应该被连接到链表中,用语句“p2-next=NULL”,将NULL值赋给前一个结点的next成员。 至此，建立链表的过程结束。,p1,0003,88,p2,head,0001,89.5,0002,76,重复步骤 ,依次建立若干个新结点。每次都让p1指向新建立的结点，p2指向链表中最后一个结点,然后用“p2-next=p1”，把p1所指的结点连接到p2所指结点的后面。 当输入某个结点数据后,如果p1-num等于0,则不再执行上述循环,此新结点不应该被连接到链表中,用语句“p2-next=NULL”,将NULL值赋给前一个结点的next成员。 至此，建立链表的过程结束。,0003,88,p2,head,0001,89.5,0002,76,重复步骤 ,依次建立若干个新结点。每次都让p1指向新建立的结点，p2指向链表中最后一个结点,然后用“p2-next=p1”，把p1所指的结点连接到p2所指结点的后面。 当输入某个结点数据后,如果p1-num等于0,则不再执行上述循环,此新结点不应该被连接到链表中,用语句“p2-next=NULL”,将NULL值赋给前一个结点的next成员。 至此，建立链表的过程结束。,0003,88,0,0,p1,NULL,建立表尾结点,struct student * creat( ) student *head,*p1,*p2; head = NULL; /在没有创建任何结点时，表头指向空 p1 = new student; /创建一个新结点 -（1） p2 = p1; cinp1-nump1-score; /*输入第一个结点的 学生数据*/,p2,p1,head,0001,89.5,(n=1),建立表头结点,while(p1-num != 0) / -（2） n +; if (n = 1) head = p1; / 将链表中第一个新建结点作为表头 else p2-next = p1; p2 = p1; p1 = new(student); / 新建一个结点 cinp1-nump1-score; delete p1; p2-next =NULL; return head; /返回表头指针 /end creat,while(p1-num != 0) / -（2） n +; if (n = 1) head = p1; / 将链表中第一个新建结点作为表头 else p2-next = p1; p2 = p1; p1 = new(student); / 新建一个结点 cinp1-nump1-score; delete p1; p2-next =NULL; return head; /返回表头指针 /end creat,建立中间结点,(n=2),0002,76,p1,p2,while(p1-num != 0) / -（2） n +; if (n = 1) head = p1; / 将链表中第一个新建结点作为表头 else p2-next = p1; p2 = p1; p1 = new(student); / 新建一个结点 cinp1-nump1-score; delete p1; p2-next =NULL; return head; /返回表头指针 /end creat,while(p1-num != 0) / -（2） n +; if (n = 1) head = p1; / 将链表中第一个新建结点作为表头 else p2-next = p1; p2 = p1; p1 = new(student); / 新建一个结点 cinp1-nump1-score; delete p1; p2-next =NULL; return head; /返回表头指针 /end creat,0,0,p1,while(p1-num != 0) / -（2） n +; if (n = 1) head = p1; / 将链表中第一个新建结点作为表头 else p2-next = p1; p2 = p1; p1 = new(student); / 新建一个结点 cinp1-nump1-score; delete p1; p2-next =NULL; return head; /返回表头指针 /end creat,p1,NULL,建立表尾结点,while(p1-num != 0) / -（2） n +; if (n = 1) head = p1; / 将链表中第一个新建结点作为表头 else p2-next = p1; p2 = p1; p1 = new(student); / 新建一个结点 cinp1-nump1-score; delete p1; p2-next =NULL; return head; /返回表头指针 /end creat,输出链表就是将链表中各结点的数据依次输出。首先要知道链表第一个结点的地址，也就是要知道表头结点head的值,然后依次通过各结点next的值找到下一个结点，就可以依次输出所有结点的数据，直到链表的尾结点为止。,void main( ) struct student *head1; cout“input records:”endl; head1=creat( ); /*建立链表， 并返回表头*/ print(head1); /输出链表 , 例 main函数调用两个函数creat( )和print( ),实现链表的创建和链表数据的输出。,void print(struct student *p) coutnumscorenext; /使p指向下一个结点 while(p!=NULL); ,void print(struct student *p) coutnumscorenext; /使p指向下一个结点 while(p!=NULL); ,对链表的删除操作是把某个结点从链表中摘除,并不是真正从内存中将这个结点删除掉，使它脱离原来的链表，解除原来的链接关系。,算法分析：以指定的学号为删除标志。从指针变量p指向的第一个结点开始，检查该结点中的num是否为要删除的学号,如果是则将其删除;如果不是，则将p移到下一个结点，再继续判断，直到删除或到表尾为止。,对链表的删除操作,执行过程：设两个指针p1和p2,先使p1指向第一个结点。如果p1所指的结点不是要删除的结点,就将p2指向p1所指的结点(p2=p1),然