C语言教学课件：第十七部分 动态存储空间管理与链表.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,第十七部分,动态存储空间管理与链表,一,、程序与存储空间,程序运行时需要的存储空间,1.,需要空间用来保存待执行的,程序代码,2.,需要空间用来保存程序运行中用到的,数据,3,1.,程序获取存储空间的途径,途径,1,在程序代码中定义某种类型的变量,基本数据类型变量,指针变量,数组变量,结构体变量,途径,2,显式的内存空间申请,在标准,C,中用,malloc,等函数申请一块存储空间,在,C+,、,JAVA,或,PASACAL,中用,new,等命令申请存储空间或新建对象,谁帮程序申请的存储空间？,4,2025/5/16 周五,2.C,通过定义变量获取存储空间,外部变量，静态内部变量,编译器会生成申请内存空间的代码，程序一启动就分配固定的存储空间给这些变量使用，在程序执行期间，不再给这些变量换存储空间。,自动型内部变量,执行到定义处才将空间分配给自动型内部变量使用，函数结束后这些变量将不再存在（即原分配给变量的空间不再归这些自动型变量使用）。,谁在分配和回收存储空间的使用权？,编译后隐含在可执行程序中的申请和释放代码,变量存在期开始时，隐含了将变量对应的存储空间分配给变量使用的动作,变量存在期结束时，隐含了将变量对应的存储空间收回的动作,5,2025/5/16 周五,3.,显式申请存储空间,明确地向系统发出申请空间的指令,malloc,new,明确地向系统发出释放指令,free,delete,问题回顾,新申请的空间应该如何管理？,解决方案,把新申请得到的存储空间保存在可以保存地址的存储空间中,6,二,、数据缓冲区,Buffer,Buffering&Buffer,Array vs Buffer,Pointer vs Buffer,7,2025/5/16 周五,1.,数据缓冲与缓冲区,Data Buffering and Buffer,什么叫缓冲？,使用存储空间临时保存需要被处理的数据，这样的存储空间即称为缓冲区。,为什么要缓冲？,数据源,数据流,数据处理器,数据的到达速度与数据加工速度不对等,需要一次处理一批数据而不是单个数据,前面收到数据要用来检验后来的数据,不同数据包的到达速度不一致,数据作为一个整体,8,2025/5/16 周五,2.,缓冲区,每一段存储空间一般都是用于保存待处理的数据，因此只要是存储空间，常常被称为,Buffer,，即缓冲区。,例如,char szBuffer1000;/,定义一段长度为,1000,的字符缓冲区,char*psz;/,定义一个字符缓冲区指针变量,int nBuffer100;/,定义一段长度为,100,（,400,个字节）的整型缓冲区,int*pInt;/,定义一个整型缓冲区指针,9,2025/5/16 周五,3.,缓冲区与数组,每个数组就是一个缓冲区，其缓冲区大小为,数组长度*元素占用空间大小,如果需要,，每个缓冲区也可以看成是一个数组，可以设置一个指针变量保存缓冲区的首地址，而后通过指针变量按数组操作方式操作缓冲区。,但,并不是每个缓冲区都会被看成数组,，有些缓冲区需要存放多种不同类型的数据。,有些缓冲区在不同时候能起不同的作用，用于存放不同类别的数据，如,Windows,系统的剪粘板,QQ,的数据发送与接收缓冲区,10,2025/5/16 周五,4.,缓冲区与动态存储管理,许多缓冲区都是临时动态地从存储堆里分配得到，因此需要用到动态存储分配与释放程序,例如，临时需要一块长度为,n,的,double,型缓冲区，用来存放,n,个双精度浮点数，则可以采用如下步骤完成,显式地提交一个内存分配申请，分配成功后会得到申请得到的内存空间的首地址,addr,将,addr,存放在一个,double,型指针变量,p,中,而后就可以用,p,来访问这个缓冲区,常用分配和释放函数,void*malloc(size_t n);/,申请一块长度不小于,n,的缓冲型，返回缓冲区首地址,void free(void*p);/,释放,p,所指向缓冲区,需要包含,stdlib.h,11,2025/5/16 周五,示例,int n;,double*pDouble;,.scanf(%d,pDouble,=(double*),malloc(n*sizeof(double);,if(pDouble=NULL),./*,分配未完成时的处理*,/,.pDoublei.*(pDouble+j)./*,正常处理*,/,free(pDouble);/,用完后释放,申请存储空间,12,2025/5/16 周五,5.,程序的模块间数据传递方法回顾,方法,1,针对批量顺序数据,将缓冲区首地址传函数,设置指针参数,将缓冲区长度告诉函数,方法,2,针对批量非顺序存储的数据,指针数组，链表，,将数据的源头的地址传给函数,2025/5/16 周五,三,、函数数据接口机制,函数如何通过参数来接收及处理来自外部的批量数据？,14,2025/5/16 周五,1.,函数数据接口与处理机制,函数处理的数据的规模分成两种情况,数目不多的,零散数据,批量数量,零散数据用前述普通的函数参数即可实现向函数的数据传递,批量数据分成两大类,一批在内存中,连续存放,的数据,一批在内存中,非连续存放,的数据,15,2025/5/16 周五,2.,函数批量数据处理方法,函数要进行批量数据处理，必须要解决的问题,能通过一定途径,找个每一个数据元素,，并对数据元素进行逐个处理,找到每一个元素并处理的过程一般称为,遍历,。,问题,在处理一批,连续存放,的数据时，函数需要知道的关于数据的信息有哪些？,在处理一批,非连续存放,的数据时，函数需要知道的关于数据的信息有哪些？,16,2025/5/16 周五,3.,批量,连续,存放数据接口机制,通过简单分析可以知道，对于批量顺序存放的数据，函数若需要访问找到每一个元素，至少应知道如下信息,需要处理的数据在哪儿放着？,缓冲区首地址,数据是什么类型的？,数据类型,需要处理的数据有多少个？,缓冲区中的数据项个数,首地址,数据类型,数据项个数,可用指针做参数,17,2025/5/16 周五,批量连续存放数据的参数传递机制,一般机制,设置参数，让函数能接收到批量数据的,首地址,让函数能知道数据的,类型,让函数能接收到批量数据的,长度,C,函数的解决办法,设置一个,相应类型的指针参数,，用于,接收,批量数据缓冲区的,首地址,。,设置一个,整型变量,用于,接收缓冲区的长度,。,此类函数的常见样式,return_type FuncName(basetype*pBuffer,int nLen,);,表示其它参数，,return_type,表示返回值类型,basetype,是缓冲区中每一个元素的类型。,18,2025/5/16 周五,第,4,部分中的实例结构体,struct,UserAccount,char szUserNO15;,char szName20;,char szID19;,char cGender;,double dBalance;,User,Users100,*pUser;,struct,UserAccount,char szUserNO15,;,/,用户,ID,char szName20,;,/,姓名,char szID19,;,/,身份证号,char cGender,;,/,性别,double dBalance,;,/,卡余额,;,struct UserAccount User,Users100,*pUser;,User,为一个普通的结构体变量；,Users,是一个长度为,100,的结构体数组；,pUser,是一个指针变量，用于存放该类型结构体变量的所占存储空间的地址；,19,2025/5/16 周五,结构体数组操作举例,给用户充值，并返回充值后的余额。,double Charge(struct UserAccount*pUserAccount,double dAmount),return,pUserAccount-d,Balance,+=dAmount;/,充值返回,给全班学生发一定额度补助,void GroupCharge(struct UserAccount Accounts,int nCount,double dAmount),if(NULL=Accounts)/,判断所给用户指针是否合法,return;,for(int i=0;i nCount;i+),Accountsi.dBalance,+=dAmount;/Charge(,指针的数组用法,结构体的分量操作符,结构体指针的分量操作符,实质是指针参数,20,2025/5/16 周五,4.,批量,非连续,存放数据接口机制,批量非连续存放的数据是指一批彼此具有一定的关系的数据，但是出于各种原因，各个数据的存放位置并,不一定是紧挨着的,。,位置不连续导致程序,无法根据首地址和单元大小来自动推断出下一个元素的地址,。,因此，对于函数而言，要处理这些数据，必须具有途径能把各个数据的,存储位置找出来,。,能把存储位置找出来的前提,各个数据的,存储位置被记录在某个地方,而且数据的存储位置可以,通过一些办法找到,的。,关键的问题,数据存储位置在什么地方存着？,与一些藏宝游戏类似,21,2025/5/16 周五,数据存储地址的保管方案,方法,1,在生成数据的时候，把各个数据的地址,放在一个连续缓冲区中记下来,，然后把记地址用的连续缓冲区的传给函数。,方法,2,利用一些,特殊的数据表示机制,，通过一个数据能知道另外,一个或多个,跟它有关系的数据的存储地址。,这样就,需要知道第一个（或头几个）数据的存储位置，然后再顺藤摸瓜找到别的数据。,22,2025/5/16 周五,批量,非连续,存放数据参数机制,针对前述方案,1,把记地址用的连续缓冲区和缓冲区长度的传给函数,针对前述方案,2,把数据集的源头（第一个或头几个）的地址传给函数。,具体接口方式取决于数据关系的表示方法。,2025/5/16 周五,23,四,、,动态存储空间管理与链表,隐式和显式,24,2025/5/16 周五,1.,引例,要处理学生成绩，需要用数组存放。但编程时并不知道运行时需要处理多少学生成绩，每次处理的成绩项数也可能不同。,int n;,.,scanf(%d,double scoresn;/*,不行！*,/,./*,读入数据，然后处理*,/,不能用变量说明,scores,大小（必须静态确定）。,25,2025/5/16 周五,2.,问题的本质及解决方案,问题的本质,程序运行中需要使用存储，有时程序对存储的需求量在写程序时不能确定。,可能解决方案,1,）分析问题，定义适当大小的数组。若分析正确，一般都能处理。但数据很多时程序就不能用。,2,）定义尽可能大的数组以满足任何需要。浪费大量存储资源。如有多个这种数组就更难办。系统可能无法容纳几个大数组，但实际上它们并不同时需要很大空间。,解决的办法是,“,动态存储分配,”,。在程序运行中做存储分配工作。,26,2025/5/16 周五,3.,动态存储分配,动态存储分配,根据运行中的需要分配存储，取得存储块使用，称为动态存储分配。在运行中根据需要动态进行。,动态存储块具有起始地址，地址可以存储在指针里，因此可以借助于指针保存存储空间地址。,用指针指向存储块，间接使用被指存储。访问动态分配存储是指针的最重要用途。,27,2025/5/16 周五,4.,动态存储释放及存储堆,动态释放,不用的动态存储块应交还系统，动态申请的内存空间必须由程序代码以显式的方式主动释放。,动态分配、释放由动态存储管理系统完成，这是程序运行系统的子系统，管理着称作堆（英文,heap,）的存储区。,大部分常规语言都有这种机制。,28,2025/5/16 周五,5.C,语言的动态存储管理机制,用标准库函数实现,stdlib.h,malloc.h,存储分配函数,malloc(),，原型：,void*malloc(size_t n);/*,size_t,是某整型,*,/,功能,分配一块不小于,n,的存储，返回其地址。无法满足时返回空指针值。,29,2025/5/16 周五,例,int n;double*data;,.scanf(%d,data=(double*)malloc(n*sizeof(double);,if(data=NULL),./*,分配未完成时的处理*,/,.datai.*(data+j)./*,正常处理*,/,30,2025/5/16 周五,malloc,说明,malloc,使用注意事项：,的返回值（,void*,）应通过类型强制转为特定指针类型后赋给指针变量。,分配存储块大小应该用,sizeof,计算,动态分配必须检查成功与否,动态分配的块大小也是确定的。越界使用（尤其是越界赋值）是严重错误，可能导致程序或系统垮台,31,2025/5/16 周五,6.calloc,带计数和清,0,的存储分配函数,calloc,，原型：,void*calloc(size_t n,size_t size);,size,是元素大小，,n,是个数。,分配一块存储，足够存,n,个大小为,size,的元素，并把元素,全部清,0,；,无法分配时返回空指针值。前面的存储分配问题也可用下面语句实现,data=(double*)calloc(n,sizeof(double);,主要差别,malloc,对所分配的区域不做任何事情，,calloc,对整个区域自动清,0,。,32,2025/5/16 周五,7.,空间释放函数：,free,为保证动态存储的有效使用，动态分配块不再用时应释放。动态存储块的释放只能通过调用,free,完成。,Memory leak,函数原型,void free(void*p);,功能,free,释放,p,指的存储块。,注意,该块必须是通过动态存储分配得到的，不要对并非指向动态分配块的指针用本操作,p,值为空时什么也不做,执行,free(p),后,p,值未变，被指块可能已变。不允许再间接访问已释放存储块,33,2025/5/16 周五,8.,分配调整函数,realloc,函数原型,void*realloc(void*p,size_t n);,功能,更改已有分配。,p,指原分配块，,n,是新大小要求。,返回大小至少为,n,的存储块指针，新块与原块一致：,新块小时保存原块,n,范围内数据；,新块大时原数据存在，新增部分不初始化。分配成功后原块可能改变。,无法满足时返回空指针，原块不变。,常用写法,(,防止分配失败导致原存储块丢失,),：,q=(double*)realloc(p,m*sizeof(double);,if(q=NULL)/*,未成功，,p,仍指原块，特殊处理*,/,else p=q;/*,令,p,指向新块，正常处理*,/.,2025/5/16 周五,34,五,、动态存储空间管理,如果动态申请了许多同类型缓冲区，该如何管理？,35,2025/5/16 周五,方法,1,：指针数组（地址数组）,设置一段内存空间，例如数组，用来保存存储空间的起始地址。,数组中每个元素用来保存某种类型的存储空间的地址，等于每个元素都是一个指针变量。,int*pnarr10;/,定义一个长度为,10,的整型指针数组（整型地址数组）,char*psz5;/,定义一个长度为,5,的字符指针数组。,0 x0012ff7d,0 x0012ff80,0 x0012fe12,其中每个元素都用来保存某种类型的存储空间的地址,36,2025/5/16 周五,例如,设一个班最多有,50,人，但每个班的人数不定，为了表示这,50,用户，可以定义如下指针数组,struct UserAccount*Accounts 50;,完成如下功能,初始化指针数组,将新生成的某个班用户加入班级用户集，并存放在空位置上。,将某个班指定用户号的用户删除,给某个班所有女生发,m,元补助,将新生成的某个班用户插入到指定位置,i,上，,i,后面的用户顺序往后退。,37,2025/5/16 周五,指针数组结构示例,0 x0012ff6d,NULL,0 x0012ff80,0 x0012ce00,0 x0012fe12,08120001,张帅帅,110108,M,0.10,08120099,李美美,350108,F,500.00,08120002,赵小飞,360108,M,20.00,08120007,罗小花,410108,F,88.20,0 x0012ff6d,0 x0012ff80,0 x0012ce00,0 x0012fe12,长度为,50,空指针，可能曾被删除,后续元素或空或不空,Accounts,38,2025/5/16 周五,功能实现,初始化指针数组,void InitAccounts(struct UserAccount*Accounts,int nLen),for(int i=0;i nLen;i+),Accountsi=NULL,;,寻找一个空位置返回，,-1,表示无空位置,int FindEmptyPlace(struct UserAccount*Accounts,int nLen),/,可以有不同的搜索策略,NULL,NULL,39,2025/5/16 周五,功能实现（续）,将新用户放在空位置上，不成功返回,-1,，成功返回位置号,int AddNewAccountAtAnyEmptyPlace(struct UserAccount*Accounts,int nLen,struct UserAccount*pUser),int nPlace;,if(,nPlace=FindEmptyPlace(Accounts,nLen),)=-1),return-1;,AccountsnPlace=pUser;/,完成放置操作,return nPlace;/,返回位置,用户结构体指针数组,数组长度,新用户结构指针,40,2025/5/16 周五,功能示例,0 x0012ff6d,NULL,0 x0012ff80,0 x0012ce00,0 x0012fe12,08120001,张帅帅,110108,M,0.10,08120099,李美美,350108,F,500.00,08120002,赵小飞,360108,M,20.00,08120007,罗小花,410108,F,88.20,0 x0012ff6d,0 x0012ff80,0 x0012ce00,0 x0012fe12,长度为,50,Accounts,08120100,孙悟空,110105,M,600.10,0 x0012ff30,0 x0012ff30,新找到的空位,新结点,孙悟空报到,41,2025/5/16 周五,功能实现（续）,将指定用户号的用户删除，返回该用户原来所在位置,int DeleteAccountByNumber(struct UserAccount*Accounts,int nLen,char*pszUserNO),int i;,for(i=0;i szUserNO,)=0),free(Accountsi);/,释放空间,Accountsi=NULL;/,将当前位置置空,return i;,return-1;,用户结构体指针数组,数组长度,用户号,字符串比较函数,42,2025/5/16 周五,删除功能示例,0 x0012ff6d,0 x0012ff30,0 x0012ff80,0 x0012ce00,0 x0012fe12,08120001,张帅帅,110108,M,0.10,08120099,李美美,350108,F,500.00,08120002,赵小飞,360108,M,20.00,08120007,罗小花,410108,F,88.20,0 x0012ff6d,0 x0012ff80,0 x0012ce00,0 x0012fe12,Accounts,08120100,孙悟空,110105,M,600.10,0 x0012ff30,NULL,把孙悟空位置找到,把孙悟空开除,:,DeleteAccountByNumber(,Accounts,50,“,08120100,”,),释放存储空间,43,2025/5/16 周五,功能实现（续）,给指定性别的群体充值，返回充值人数,int ChargeByGender(struct UserAccount*Accounts,int nLen,char cGender,double dAmount,),int nCounter=0;/,计数器,for(int i=0;i cGender=cGender),Accountsi-dBalance+=dAmount;,nCounter+;,return nCounter;,ChargeByGender(Accounts,50,F,10.0);/,妇女节发补助,44,2025/5/16 周五,方法,2,：链接结构,采用链式数据结构,一环扣一环，通过一个元素保存的其它元素的地址找到其它元素。,通过链接结构实现动态数据,增加元素：在铁链的某个位置加一铁环,删除元素：去掉铁链的某一铁环,问题,铁链中的每一铁环是一样的吗？,普通的铁链是单向的还是双向的？,有没有一些特殊的铁链，比如有多个分叉的？,铁链可以跟铜链拴一起吗？,铁链的头部可以拴在柱子上吗？,45,2025/5/16 周五,链接结构实现原理,链接结构中的元素需要保存的信息,与结点本身有关的信息,找到其它元素所需要的信息,这些信息可以组织成结构,问题：如何找到其它元素？,保存其它元素在内存中的地址,在结构中设置指针分量，用来保存其它元素的地址的分量指针分量,问题：指针的类型？,需要指向结构类型的指针类型,如果需要指向的元素与本元素的类型相同的话，则需要定义自引用的结构类型。,46,2025/5/16 周五,链接结构,一个结构元素可以通过指针引用同类或不同类的结构元素，多个结构元素通过指针建立联系。,指向结构的指针称为链接，形成的复杂数据结构称为链接结构,最简单的链接结构,线性链接形成的表，,链接表,。,每个自引用结构有一个链接指针分量。,47,2025/5/16 周五,最简单的链接结构：单向链表,单向链接表就像链条，自引用结构是链表中的一个链节，称为链表结点，结点间由指针连接形成整个结构。,所有结点（结构）由动态分配创建。,从指向表首结点的指针出发，沿链接可顺序访问表中各结点。该指针代表整个表。通常把最后结点的指针置空表示结束。,48,2025/5/16 周五,更复杂的引用链接结构,49,2025/5/16 周五,单向链表结构示例,struct UserAccount,char UserNO15;,char Name20;,char ID19;,char Gender;,double Balance;,struct UserAccount,*pNextUser;,;,用来保存下一个结点的地址,此处改成如下形式是否可行，为什么？,struct,UserAccount,NextUser;,50,2025/5/16 周五,普通单向链表示意图,08120001,张帅帅,110108,M,0.10,08120002,赵小飞,360108,M,20.00,08120007,罗小花,410108,F,88.20,08120099,李美美,350108,F,500.00,NULL,Head,Tail,51,2025/5/16 周五,例，需求,设有某系统的用户信息结构体，其中,用户,ID,长度为,10,用户姓名长度不超过,10,需要处理的用户数据不定，,假设某程序需要以链表方式处理用户的数据,52,2025/5/16 周五,普通单向链表示意,Data,Data,Data,Data,NULL,Head,Tail,53,2025/5/16 周五,链表结点结构声明,方法,1:,struct UserInfoNode,char szID11;/ID,char szName11;/,姓名,struct UserInfoNode*pNextUser;/,下个用户指针,;,方法,2,：,typedef struct UserInfoNode,USERNODE,*USERPOINTER;,struct UserInfoNode,char szID11;/ID,char szName11;/,姓名,USERPOINTER pNextUser;/,下个用户指针,;,54,2025/5/16 周五,更好的方法：基本信息单独说明,/,用户基本信息结构声明,struct UserInfo,char szID11;/ID,，,11,个字符,char szName11;/,姓名，,11,个字符,;,或,typedef struct,char szID11;/ID,，,11,个字符,char szName11;/,姓名，,11,个字符,USERINFO;,55,2025/5/16 周五,更常见合理的声明方法,方法,3,：,struct UserLinkNode,struct UserInfo Data;/,数据,struct UserLinkNode*pNextUser;/,;,struct UserInfo UserInfoArr100;,或,typedef struct,USERINFO Data;/,数据结点,struct UserLinkNode*pNextUser;/,USERLINKNODE;,struct UserInfo,char szID11;,char szName11;,;,typedef struct,char szID11;,char szName11;,USERINFO;,56,2025/5/16 周五,增加一个链表描述信息结点,Number,Head,Tail,Data,Data,Data,Data,NULL,LinkInfoNode,关于链表整体描述信息结点,57,2025/5/16 周五,描述结点结构说明示例,struct UserLink,struct UserLinkNode*pHead;/,头指针,struct UserLinkNode*pTail;/,尾指针,int nNumber;/,链表中的结点计数,;,或,typedef struct,USERLINKNODE*pHead;/,头指针,USERLINKNODE*pTail;/,尾指针,int nNumber;/,链表中的结点计数,USERLINK;,58,2025/5/16 周五,可以增加一个不用的头结点,Number,Head,Tail,Data,Data,Data,NULL,LinkInfoNode,目的在于写程序方便，简化一些链表操作，数据结构课程中会有进一步的阐述,不用的头结点,59,2025/5/16 周五,关于后面的操作的假定,链表为单向链表,没有设置空的头结点,设置有信息描述结点，记录如下信息,头结点,尾结点,链表中结点个数,60,2025/5/16 周五,在链表中增加一个节点,有几种增加方式,将新结点作为最后一个元素增加到链表的尾部，,将新结点作为第一个元素增加到链表的头部,将新结点按照某种次序要求插入到指定位置,61,2025/5/16 周五,加到尾部,如果链表为空，则需要做一些初始化工作，将新的结点当成头结点和尾结点,如果链表不为空，则将该结点作为尾结点的下一个结点，修改尾结点指针。,如果没有记录尾结点指针，则需要从头结点开始找到最后一个结点。,pHead,pTail,Data,Data,NULL,pNewNode,NULL,62,2025/5/16 周五,示例代码，加到尾部,int AddUserToTail(struct UserLink*pUsers,/,链表描述信息指针,struct UserLinkNode*pNewUser/,新结点指针,),if(pUsers=NULL|pNewUser=NULL)return-1;,if(pUsers-nNumber pHead=pNewUser;,pUsers-pTail=pUsers-pHead;,/,头尾指针指向同一个结点,else/,把结点信息附到链表尾部,pUsers-pTail-pNext=pNewUser;/,加到尾,部,pUsers-pTail=pNewUser;/,修改尾结点指针,pUsers-pTail-pNext=NULL;/,最后一个结点的后继置空,pUsers-nNumber+;/,计数加,1,return 0;,63,2025/5/16 周五,加到头部,如果链表为空，则需要做一些初始化工作，将新的结点当成头结点和尾结点,如果链表不为空，需要将新结点的下一个结点置为原来的头结点，并把新结点作为头结点,pHead,pTail,Data,Data,NULL,NULL,pNewNode,64,2025/5/16 周五,示例代码，加到头部,int AddUserToHead(struct UserLink*pUsers,/,链表描述信息指针,struct UserLinkNode*pNewUser/,新结点指针,),if(pUsers=NULL|pNewUser=NULL)return-1;,if(pUsers-nNumber pHead=pNewUser;,pUsers-pTail=pUsers-pHead;,/,头尾指针指向同一个结点,pNewUser-pNext=NULL;,else/,把结点信息附到链表头部,pUsers-pNewUser-pNext=pUsers-pHead;/,加到头部,pUsers-pHead=pNewUser;/,修改头结点指针,pUsers-nNumber+;/,计数加,1,return 0;,65,2025/5/16 周五,在链表中插入一个新结点,基本操作,q-pNext=p-pNext;,p-pNext=q;,其它用于保持链表指针完整性的操作。,功能示意,p,p,q,q,r,r,插入前,插入后,66,2025/5/16 周五,去除链表中的某个结点,基本操作,p-pNext=q-pNext;,外围附加操作，用于保证链表的各种指针的完整性，如头指针，尾指针等。,如：如果删除的是最后一个结点的话，需要修改尾指针,功能示意,p,q,r,p,r,q,67,2025/5/16 周五,遍历链表,常见功能,遍历链表逐个访问所有结点，进行相应的处理，如将所有用户的某项指标求和，输出所有用户的信息,查找某个或某些符合给定条件的结点，进行相应处理,68,2025/5/16 周五,示例代码,:,输出所有元素,int ShowData(struct UserLink*pUsers),struct UserLinkNode*pNode;,if(pUsers-nNumber pHead;,/,从第一个元素开始,pNode!=NULL;,/,判断当前结点是否为空,pNode=pNode-pNext,/,准备处理下一个结点,),/,对每个结点出输出信息,printf(%11st%11stn,pNode-Data.szID,pNode-Data.szName,return 0;,69,2025/5/16 周五,参数改成头结点,int ShowData(struct UserLinkNode*pHead)/,给出头结点,struct UserLinkNode*pNode;,if(pHead=NULL),return-1;,for(,pNode=pHead;,/,从第一个元素开始,pNode!=NULL;,/,判断当前结点是否为空,pNode=pNode-pNext,/,准备处理下一个结点,),/,对每个结点出输出信息,printf(%11st%11stn,pNode-Data.szID,pNode-Data.szName,return 0;,70,词频统计示例,词频统计,统计正文文件里各个字或单词出现的次数。,统计前不知道有多少不同的词，无法在编程时准备好统计中使用的完整数据结构。,可能方案,动态分配计数器数组，必要时调整大小（用,realloc,）。,问题,新词逐个遇到，反复调整分配效率比较低，而且需要使用很大的块，不够灵活。,如果词很多，能否找到足够大的存储块也是问题。,71,词频统计实现,#include,#include,#include,#include,enum MAXLEN=20;,typedef struct node NODE,*LINK;,struct node/,定义链接结构,char wordMAXLEN;,int count;,LINK next;,;,int getword(int limit,char w);,LINK addwordL(LINK list,char w);,LINK addwordR(LINK l,char w);,void printwords(LINK l);,LINK list=NULL;,char wordMAXLEN;,int main(),while(getword(MAXLEN,word)!=0),list=addwordL(list,word);,printwords(list);,return 0;,72,LINK mknode(char w)/,创建一个新结点,LINK p=(LINK)malloc(sizeof(NODE);,if(p!=NULL),strncpy(p-word,w,MAXLEN);,p-count=1;,p-next=NULL;,return p;,int getword(int limit,char w),int c,i=0;,while(inext),if(strcmp(p-word,w)=0),p-count+;,break;,if(p-next=NULL),p-next=mknode(w);,break;,return list;,74,LINK addwordR(LINK p,char w)/,递归解法,if(p!=NULL),if(strcmp(p-word,w)=0),p-count+;,else,p-next=addwordR(p-next,w);,return p;,else,return mknode(w);,void printwords(LINK p)/,遍历打印链表结点,for(;p!=NULL;p=p-next),printf(%d%sn,p-count,p-word);,75,练习,实现一个学生成绩管理系统，可包括以下功能,学生成绩录入,学生成绩查询,按条件查询（及格的学生）,按姓名查询（如果该学生存在则输入相应信息）,按学号或总分排序,学生成绩统计（平均分，优、良、中、差的学生人数）,学生记录删除,可用结构数组,(,结构指针,),或链表实现,用链表实现猴子选大王的程序（选做）,76,设有学生成绩处理系统，用链表表示一个班级中所有学生的成绩，每个链表点中包括学生姓名、程序设计和数学课的成绩，设链表结构如下：,struct LinkNode,char Name20;,double Programming;,double Mathematics;,struct LinkNode*pNext;,;,请设计一个函数，该函数能输出,Programming,的值处于,Min,Max,之中的学生的姓名和二门课的成绩，函数原型要求如下：,void RangeQuery(struct LinkNode*pHead,，,double Min,double Max);,其中,pHead,为链表的第一个结点指针,Min,为成绩下界，,Max,为成绩上界。,07,年考题,77,2025/5/16 周五,本部分内容,动态存储分配及其函数,动态存储空间管理方法,链表概念,链表的定义和基本操作,202