07《c语言与程序设计》第十二讲-清华李宛洲.

C语言程序设计基础2005.9第十二讲结构指针与链表入门教学内容指针与数据结构动态存储结构—链表•指针与链•动态存储的基本概念指针应用综合训练—链表设计初步•用节点内部指针关联两个节点•单链表基本概念与操作•例题:复制单链表引用的概念指针与数据结构指针代表数据的物理地址，它指向一个节点的内存位置。数据节点之间的关系有多种，数组可以存储具有线性关系的表格。但是数组无法存储如下一种关系：C语言04教程中考单词排序杨辉三角debug源程序期末总分期中成绩试卷节点之间的连接关系是非线性的，类似一棵树的结构怎样在计算机中存储文件夹所表达的逻辑关系？文件目录会随时增删，因此节点之间的连接关系是非线性的且动态变化的如果有一个指针指向后续节点位置，程序可以根据指针找到其后续节点，我们就能在计算机中存储文件夹所表达的逻辑关系修改指针的指向，可以动态的跟随后续节点的逻辑关系变化指针与抽象的数据节点连接指针在数据结构起到关联节点的作用；让指针从一个节点元素内指向另一个节点元素，通过指针连接节点元素之间的存储位置，从而让它们之间关联在一起，进而表达了它们之间的逻辑关系。指针能从一个节点指向另一（或者是多个）节点，它必须是在节点内部，因此，在结构定义中加入指针变量，指针在节点内，它指向下一个节点；假定程序找到了当前节点位置，就能根据指针找到后续节点所在，这就是节点关联。a1a2指针在节点内部a3节点之间用指针串成一条链，表明节点之间是线性逻辑关系具有指针的节点结构structstudent{charnum[20];charname[40];charclass[40];intsex;charbirthday[20];inttel;structstudent*next;};数据区域指针区域在student结构分成两部份,数据域描述学生属性的基本信息;该节点的指针域有指针变量next，若用next指向学生集合中的其它节点，可以表达集合中节点之间的关系，使它们关联在一起。指向同类型的节点用节点内部指针关联两个节点structstudent*head,*p;设指针head已指向内存里的一个节点a1;现在，再申请一个节点a2;对a1的next赋值使其指向a2，从而让a1与a2关联起来；a2=(structstudent_node*)malloc(sizeof(student_node))；a2-number=2006231;a2-name=刘东;a2-next=Null;head-next=a2;a1nextheadhead指向a1a2next^next指向a2物理上a1的指针next链接了节点a1和a2对a2的数据域赋值在逻辑上，指针表达了a1和a2是线性有序关系：a1,a2链表的概念与数组相比，链表是动态数据存储结构。设用结构数组存储学生选课人数，因不能预先确定人数，数组太大占用内存，太小不能满足使用要求。并且，当学生留级、退学之后也不能把其占用的空间从数组中释放出来。用动态存储的方法可以很好地解决这些问题。一个学生数据称之为一个结点。动态存储方法是每新增一个节点申请一个内存区域，有多少个学生就应该申请分配多少块内存空间，也就是说要建立多少个结点。存储空间随纪录增加而改变。无须预先确定学生人数，某学生退学，可删去该结点，从而释放该结点占用的存储空间。数组要占用一块连续的内存区域。动态分配的内存其每个结点之间可以是不连续的。结点之间的逻辑联系用指针实现。在结点结构中定义一个结构指针，用来存放下一结点的首地址，我们称之为指针域。用指针链接的线性表格，称之为“链表”。(a)数组存储结构(L是结构元素长度)a3a1a2ai-1aian起始地址SS+i*LS+LS+2LS+(i-1)*LS+(n-1)*L(b)链式存储结构a4a1ai-1aiS+La2数据域指针域起始地址SS+LS+2LS+(i-1)*LS+i*LS+(n-1)*LS+(i-1)*La3S+i*LS+2LS+(n-1)*L指向ai+1a1,a2,a3,…,anSa1,a2,a3,a4,ai-1S线性表—顺序存储与链式存储,ai指针的指向，描述了ai，ai+1的逻辑关系a1nextheadhead指向a1a2next^next指向a2具有两个节点的链表在链表的第一个结点的指针域内存入第二个结点的首地址；在第二个结点的指针域内又存放第三个结点的首地址；如此串连下去，直到最后一个结点。最后一个结点因无后续结点连接，其指针域可赋为0；只要初始化链表头指针head，让它指向头节点a1，通过把每次输入纪录ai的地址赋值给其前驱节点ai-1所含的指针next，就可以让ai-1指向ai：ai-1-next=ai;它描述了ai,ai+1的逻辑关系。线性表的链式存储结构特点是用一组任意的存储单元来存储线性表的数据元素；关系ai,ai+1是用节点指针域所含的后继节点地址信息来表达的。即节点有数据域与指针域两部分，所有节点指针的指向形成了一条数据链。head=a1a1a2ai-1aiai+1指针next串成了链构造单链表a1nexta2nexta1=(structnode*)malloc(sizeof(node));a1-next=NULL;head-next=a2;a2-next=NULL;a2=(structnode*)malloc(sizeof(node));head=a1;Structnode*head;head^链表尾节点标志是指针为空^指示链表头节点的指针通过head找到链表申请节点空间structnode{intkey;….structnode*next;};节点结构每个节点有一个关键码作唯一的标记，比如学号是学生的关键码循环单链表结构a1nexta2nexta1=(structnode*)malloc(sizeof(node));head-next=head;head-next=a2;a2-next=head;a2=(structnode*)malloc(sizeof(node));head=a1;Structnode*head;//指示链表头节点的指针head如何判别链表结束？链表操作—搜索指定节点a1nexta2nextif(p-key!=key){q=p;p=p-next;}p=head;Structnode*head,*q,*p;heada3nextan^否则，while(p){继续搜索}PPqqPPqq指向anp=NULL;while(p){if(p-key!=key){q=p;p=p-next;}}到达节点an之后，继续更新p则p=NULL;Pqp为空则搜索失败搜索成功返回位置指针elsereturn(p);递推搜索intsearches(structstu*head,intkey){if(!head)return(-1);while(head){if(head-num!=key)head=head-next;elsereturn(head-score);}return(-1);}int类型函数指向头结点的指针学号检索码表空，返回检索失败信息当前节点非空，循环搜索如学号如果不符修改头指针指向下一个节点学号相符，返回该节点成绩分量走出循环体则该表非空，且无检索的学号链表操作—搜索指定学号节点信息链表操作—指定节点前插入新节点，递增有序a1nexta2next若走出while(p){}循环,则p=NULL;p=head;Structnode*head,*q,*p;heada3nextan^if(p-keys-key){在a3前插入}PPif(p-keys-key){q=p;p=p-next;}PPqq指向anSnextS-next=p;q-next=S;Snext^插入尾部q-next=Sqif(p-keyS-key){q=p;p=p-next;}qstructnode*dls_store(structstu*s,structstu*head){structnode*p,*q;if(!head){head=s;s-next=NULL;return(s);}p=head;q=p;while(p){if(p-nums-num){q=p;p=p-next;}else{if(p==head){s-next=head;head=s;return(s);}s-next=p;q-next=s;return(head);}}q-next=s;s-next=NULL;return(head);}node类型指针函数待插入节点头指针表空，返回S为头部节点从头开始搜索插入位置当前节点关键字值小于S节点关键字值,递推搜索下一节点找到插入位置插入位置是头部？修改头指针指向插入位置在链表中间ai-1nextainextqPSnextS-next=p;q-next=S;走出循环体则该表非空且无关键字值大于S节点,S插入链尾an^Pqq指向anSnext^q-next=S循环链表操作—搜索指定节点a1nexta2nextp=head;if(p-key!=key){q=p;p=p-next;}p=head;Structnode*head,*q,*p;heada3nextannextwhile(p!=head){继续搜索}PPPqq指向anif(p-key!=key){q=p;p=p-next;}elsereturn(p);//返回位置指针搜索失败;qqP例编写一个函数copy，将单链表A复制到单链表B，并用函数list输出B到屏幕a1nexta2nextp=head;Structnode*head,*head2,*q,*p;heada3nextan^snexthead2空指针Pq=head2;申请节点sqs-data=p-data;q-next=s;a1使用了空指针while(p){s=(structnode*)malloc(sizeof(node))；s-data=p-data;q-next=s;q=s;p=p-next;}例单链表复制（二）p=head;Structnode*head,*head2,*q,*p;headan^h2nexthead2Pq-next=s;snexta1q申请节点sqanqPq=s;q=head2;a3nexta2nextq申请节点h2a1nexthead返回头指针q=head2-nextfree(head2);s-data=p-data;若走出while(p){}则复制过程结束q-next=NULL;q=head2-next;free(head2);return(q);^return(q);voidmain(){charch_a='a';charch_b='b';}ch_ach_b200220041000xy40044010voidget(char*x,char*y){}3000'a''c'20042002voidget(char*,char*)；定义指针函数调用时,变量的地址传递给被调函数内的指针用指针传递变量的地址给调用函数的实参赋值get(&ch_a,&ch_b);charch_a='a',ch_b='c’;内存ch_a20022004'a''c'实参是主调函数内部变量的地址40044010ch_b……xy20022004*x='x';给指针指向的数据变量赋值*y='y';'x''y'多级指针的情况下非常容易出错rcbrcavoidmain(){charca='a';charcb='b';char&rca=ca;char&rcb=cb;}cacb200220041000xy40044010voidget(char&x,char&y){}3000'a''c'voidget(char&,char&)；引用说明函数调用时,变量的引用传递给被调函数通过引用传递变量的地址给调用函数get(r