结构体数组学习.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+;,cinstu0.name;strcpy(stu0.name,“ZhaoDa”);,cinstu1.num;,EXAMPLE 2.Sort by student aver,#include#include#include using namespace std;struct Gradeint s1;int s2;int s3;float aver;struct StudentRecint 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 Score1001 Liu Jin 751002 Li Lan 821003 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),然后将p1指向下一个结点(p1=p1-next)。再继续判断p1所指的结点是不是要删除的结点,如此重复,直到找到要删除的结点并将其删除或是检查完全部链表为止。,要删除的结点分两种情况：要删除的是第一个结点（即p1=head），则执行head=p1-next。这时，head指向了原来的第二个结点。此时，第一个结点虽然还存在，但它已与链表脱离，因为链表中没有一个结点或头指针指向它，也就不能访问它了，即已被删除。,要删除的结点分两种情况：要删除的不是第一个结点,则应执行 p2-next=p1-next,即p2-next指向了p1-next所指向的结点，p1所指向的结点就被删除而不再是链表的成员了。,struct student*dele(student*head,long num)student*p1,*p2;if(head=NULL)coutnum!=num,对链表的插入是指将一个结点插入到一个已有的链表中。为简单起见，假设有一个学生链表，各结点已按其成员学号（num）的值由小到大顺序排列，现在要插入一个学生的结点，要求按学号的顺序插入。,过程分析：先将要插入的结点学号与第一个结点的学号相比，若小则插入到第一个结点前面，否则与第二个结点相比，如此重复，直到找到一个比它大的学号插入到它的前面或链表结束插入到链表的尾部。,对链表的插入操作,过程实现：,要插入结点指针,前移指针,紧随指针,过程实现：,过程实现：,0002,89.5,head,struct student*insert(student*head,student*stud)struct student*p0,*p1,*p2;p1=head;/p1指向第一个结点 p0=stud;/p0指向待插入的结点 if(head=NULL)/原来的链表是空表 head=p0;p0-next=NULL;/使p0指向的结点作为头结点 else while(p0-nump1-num)/p1后移一个结点,插入结点的函数如下：函数的参数是head和要插入的结点存储空间首地址指针(stud)，函数的返回值是链表头指针head，head的值可能在函数执行过程中被改变（当插入到第一个结点之前时）。,if(p0-numnum)if(head=p1)head=p0;/插入到第一个结点前面 else p2-next=p0;/插入到p2指向的结点后面 p0-next=p1;else p1-next=p0;p0-next=NULL;/插入到最后的结点后面 n=n+1;/链表结点个数加1 return(head);,综合实习：,数组、结构体与指针,链表操作:,创建链表,输出链表,Main(),删除结点,插入结点,EXAMPLE 2.,用结构体数组对10名学生的成绩进行排序（冒泡法和选择法）。,