搜索
计算机程序设计基础教师：文迪Email:wendi@tsinghua.edu.cn清华大学电子工程系智能图文信息处理实验室回顾上节课内容1.结构体类型的定义2.结构体类型的变量3.结构体与函数4.结构体数组5.联合体和枚举类型第十章结构体和联合体（二）1.结构体与指针2.动态内存分配3.结构体与链表如何使用指针访问结构体成员？如何使用动态内存分配？链表是一种什么样的数据结构，它和数组有什么区别？链表有哪些基本操作？指向结构体的指针•和指向整型、浮点型等基本数据类型的指针一样，指向结构体变量的指针内容是该结构体变量的首地址：typedefstructstudent{unsignedshortusYear;charbyMonth;charbyDay;unsignedintnID;boolbMale;floatfMarks;}STUDENT;STUDENTstu;STUDENT*pstu=&stu;usYearbyMonthbyDaynIDbMalefMarks低内存地址高内存地址变量stu指针变量pstu指向结构体的指针•可以使用结构体的指针结合“-”运算符访问结构体变量的各成员：STUDENTstu;STUDENT*pstu=&stu;pstu-usYear=1990;//相当于stu.usYear=1990;pstu-byMonth=1;//相当于stu.byMonth=1;•也可以通过取内容运算符“*”结合“.”运算符访问结构体变量的各成员：(*pstu).usYear=1990;(*pstu).byMonth=1;请注意：(*pstu).usYear和*pstu.usYear的区别“.”运算符优先级高于“*”指针变量作为结构体成员•结构体成员中可以包含指针变量，指针作为结构体成员的作用可能有以下三种情况：1.作为指向大量数据的索引；structstudent{constchar*strNation;//国名字符串常量};1.typedefstructstudent{2.constchar*strNation;//国名字符串常量3....4.}STUDENT;5.voidmain()6.{7.STUDENTstu;8.stu.strNation=“China”;9.}示例：结构体中使用字符串常量显然，在结构体中使用常量字符串指针是有局限的：字符串内容必须来自于程序代码里预先写好的字符串常量，不能在程序运行时根据用户输入来动态决定字符串的内容。所以这种写法用处不大。1.typedefstructstudent{2.charstrNation[32];//国名字符串空间3.charstrName[32];//姓名字符串空间4....5.}STUDENT;6.voidmain()7.{8.STUDENTstu;9.strcpy(stu.strNation,“China”);10.strcpy(stu.strName,“张三”);11.//注意:此时不能写成stu.strNation=“China”!12.}示例：结构体中使用字符串更常用的方式指针变量作为结构体成员•结构体成员中可以包含指针变量，指针作为结构体成员的作用可能有以下三种情况：2.作为有待分配内存空间的指针；structdynArray{intnNum;int*pData;};动态内存分配简介•到目前为止，我们所写的程序中的内存分配有以下特点：1.是由编译器为我们自动完成的；变量的声明（基本数据类型、数组、结构…）意味着内存的分配intx;structstudentstu;floatarrData[100];2.要分配的内存大小必须在编写程序时就确定，其后不能改变，由于不能到程序运行时再动态分配，因此只能提前分配足够大的内存空间，造成浪费。structstudent[100];//要录入若干个学生信息动态内存分配简介•C/C++语言支持动态内存分配机制，允许程序员在程序运行时根据实际需要动态地申请内存。C++通过运算符new/delete，支持动态内存分配int*pi=newint;float*pf=newfloat(3.14159);char*str=newchar[100];int**pArr2D=newint[4][5];new类型(初值)new类型[数组长度]new和delete运算符delete指针变量名delete[]指针变量名1.typedefstructdynArray{2.intnNum;3.int*pData;4.}DYNARRAY;5.voidmain()6.{7.DYNARRAYarr1={0,NULL};8.intnLen=0;9.cout“Inputthelengthofthearray:”;10.cinnLen;11.if(nLen0){12.arr1.pData=newint[nLen];13.arr1.nNum=nLen;14.}15....16.delete[]arr1.pData;17.}示例有关动态内存分配的详细内容后面再讲。指针变量作为结构体成员•结构体成员中可以包含指针变量，指针作为结构体成员的作用可能有以下三种情况：3.作为指向另一个结构体的指针，用于构建链表。structnode{charstrName[10];boolbMale;structnode*pNext;//指向下一个结构体的指针};数据域指针数据域指针在讲链表之前，先来看一个例子。结构体与链表•问题——稀疏数组通常我们使用数组来存放向量数据。但是如果向量中的元素大多数都是0，只有少数为非0（称为稀疏向量）时，开辟数组会显得浪费。我们希望设计一种针对稀疏向量的新的存储方式——稀疏数组，能够让我们只存储那些非0的向量元素。510-1350...0100...0-10...030123456789101112131415结构体与链表•针对以上问题，稀疏数组应该具有以下特性：1.根据数组中实际非0元素的个数，动态分配内存空间；2.可以按照顺序访问各个非0元素；3.可以方便地向一个稀疏数组添加、删除非0元素，并保持各元素的排列顺序。510-1350...0100...0-10...030123456789101112131415结构体与链表•为此，我们设计一个链表，其中每一个节点的类型定义如下：typedefstructtagNode{intindex;//非0元素的下标,应为非负整数intvalue;//非0元素的值tagNode*next;//下一个非0元素节点的指针}NODE,*PNODE;//PNODE是NODE地址50104-110315NULLindexvaluenext在这个链表结构中，第一个节点的地址并没有被记录，需要另外用一个指针变量专门记录。head链表的建立•设立链表头指针head，并初始化为NULL；•向链表的尾部添加节点；1.若head为NULL，分配新节点，并使head指向该新节点；2.若head非空，则向后找到链表的尾节点的指针tail，分配新节点，并使tail-next指向该新节点。50104-110315NULLindexvaluenexthead1.typedefstructtagNode{2.intindex;//非0元素的下标,应为非负整数3.intvalue;//非0元素的值4.tagNode*next;//（指向下一个NODE的位置）5.}NODE,*PNODE;//（PNODE为这个NODE的地址）6.voidmain()7.{8.PNODEhead=NULL,tail=NULL;//头和尾地址9.cout“请依次输入元素下标和值，输入-1停止.”10.endl;11.while(true)//true无用，只是break来搞定12.{13.inti,v;14.ciniv;15.if(i==-1)break;//输入-1停止16.PNODE*pNewNode=newNODE;//开辟新的，前市地址17.pNewNode-index=i;pNewNode-value=v;18.pNewNode-next=NULL;示例：建立稀疏数组链表1.if(head==NULL)2.{3.tail=head=pNewNode;4.}5.else6.{7.tail-next=pNewNode;8.tail=pNewNode;9.}10....11.}示例：建立稀疏数组链表50104-110315NULLindexvaluenextheadtail链表的基本操作•遍历链表中的所有元素；•在链表中查找指定元素；•在链表中指定元素之后插入元素；•在链表中指定位置删除元素；1.for(PNODEp=head;p!=NULL;p=p-next)2.{3.//使用p访问当前节点内容4....5.}6.注意：如果写成下面这样,会有什么结果？7.for(PNODEp=head;p-next!=NULL;p=p-next)8.{9.}示例：遍历链表中的所有元素50104-110315NULLindexvaluenextheadp1.PNODElookfor(PNODEhead,intindex)//PNODEp=head（代表首地址）2.{3.//在链表中查找下标为index的节点，并返回其指针4.for(PNODEp=head;p!=NULL;p=p-next)5.{6.if(p-index==index)//p为代表结构体的指针（也就是结构体的头地址）7.returnp;8.}9.returnNULL;10.}示例：在链表中查找指定元素50104-110315NULLindexvaluenextheadp1.PNODElookfor_before(PNODEhead,intindex)2.{3.//在链表中查找下标为index的节点，返回其前一个节点的指针4.PNODEp=NULL;5.for(p=head;p-next!=NULL;p=p-next)6.{//p首地址变7.if(p-next-index==index)8.break;9.}10.return(p-next!=NULL)?p:NULL;11.}示例：在链表中查找指定元素50104-110315NULLindexvaluenextheadp注意，该函数没有考虑链表头的下标等于index的情况！若找不到指定元素，函数会返回NULL1.PNODEinsert_after(PNODEp,PNODEpNewNode)2.{3.//在指针为p的节点后面插入元素,返回新元素的指针4.pNewNode-next=p-next;//pNewNode是新加入的结构体头指针5.p-next=pNewNode;6.returnpNewNode;7.}示例：在指定元素之后插入元素50104-110315NULLindexvaluenextheadp207NULLpNewNode如果这里的语句顺序颠倒，会产生什么结果？1.PNODEdelete_after(PNODEp)2.{3.//删除指针为p的节点的后面一个元素4.PNODEpDelNode=p-next;5.p-next=pDelNode-next;6.deletepDelNode;//pDelNode就是需要删除的结构体7.returnp-next;8.}示例：删除指定位置后面的一个元素50104-110315NULLindexvaluenextheadp如果只知道p，能否直接删除指针为p的节点？为什么？如果要做到这一点，需要怎么做？1.PNODElookfor_near_index(PNODEhead,intindex)2.{3.//寻找下标=index的最大元素的指针,若找不到则返回空4.if(head==NULL)returnNULL;5.if(head-indexindex)returnNULL;6.PNODEp=NULL;7.for(p=h