《程序设计(结构体)》-课件.pptVIP

七 、结构体与链表（三） 7.5 结构体指针 1、概述 一个指针变量用来指向一个结构变量时，称为结构指针变量。结构指针变量中的值是所指向的结构变量的首地址。通过结构指针即可访问该结构变量。 2、指向结构变量的指针的定义 struct 结构体名 *结构指针变量名 struct Stud { int sno; char sname[20]; float score; } stu; struct Stud *p= stu; 3、访问结构成员变量的三种方法 （1） stu.sno、stu.sname、stu.score （2） (*p).sno、(*p).sname、(*p).score （3） p-sno、p-sname、p-score 4、说明 （1） “ - ”为指向运算符，是优先级最高的运算符； （2） 采用“ (*p). 成员名 ” 形式时，括号不能省略； （3）经常这样使用： p-num、p-num++、++ p-num 5、指向结构数组的指针 struct st { int sno; char sname[20]; float score; } stu[29], *p; 合法的操作： p=stu; p=stu[3]; p+1、 (++p)-num、 ++p-num、 (p++)-num、 p-num++等 6、用结构体变量和指向结构体的指针作函数参数 （1）用结构体变量的成员作实参（传值） void fun(int); // 函数声明 fun(stu.sno); // 函数调用 （2）用结构体变量作实参（传值） 要求形参也必须是同类型的结构体变量。 （3）用指向结构体变量(或数组)的指针作实参 将结构体变量(或数组)的首地址传给形参 7.6 链表概述 一种常用的、能够实现动态存储分配的数据结构。 链表：若干数据按一定原则连接起来的表。链表的前一结点指向后一结点，只能通过前一结点才能找到后一结点。第一个结点没有前趋，最后一个结点没有后继。链表必须有链表结束标志，最后一个结点的指针域的值为NULL。单链表必须从头开始（通常有一个头指针）顺序访问；而不可随机访问。 结构体可以嵌套声明，而结构成员不能是自身的结构变量，但可以用结构体指针作为成员。 结点：链表的每个结构体变量是一个结点。 链表是动态存储分配的数据结构。 链表有单向链表、双向链表、循环链表等形式（此处只讨论单向链表）。 7.7 创建和操作链表 7.7.1 链表结构 7.7.2 创建单链表 7.7.3 遍历单链表（从头开始，顺序输出） 7.7.4 查找 7.7.5 插入操作 7.7.6 删除操作 7.7.1 链表结构 链表是一种常见且重要的数据结构。它是动态地进行存储分配的一种结构。 因数组存放数据时，必须事先定义固定的长度。若事先难以确定数组的大小，则必须把数组定得足够大，显然这将会浪费内存。而链表则没有这种缺点，它根据需要开辟内存单元。（也可使用指针的堆内存分配来解决这个问题） 若对数组元素进行插入和删除操作，执行效率非常低下，对于经常对元素进行插入和删除操作的情况，采用链表无疑将是你的首选。 链表有一个“头指针”变量，前图中以head表示，它存放一个地址，该地址指向第一个元素。链表中的元素常称为结点，每个结点都应包括两个部分：一为用户需要用的实际数据，二为下一个结点的地址。head指向第一个元素；第一个元素又指向第二个元素……直到最后一个元素，该元素不再指向其他元素，它称为“表尾”，它的地址部分为空值（NULL），链表到此结束。 链表中各元素在内存中一般不是连续存放的。要找某一元素，必须先找到上一个元素，根据它提供的下一元素地址才能找到下一个元素。如果不提供“链表头”(head)，则整个链表都无法访问。链表如同一条铁链一样，一环扣一环，中间是不能断开的。链表的这种数据结构，必须利用指针变量才能实现。即：一个结点中应包含一个指针变量，用它存放下一结点的地址。 7.7.2 创建单链表 设链表的结点结构为： struct Node { int data; 　 struct Node *next; }; 建立链表的两种的思想： （1）新结点链到表尾 （2）新结点链到表头 7.7.3遍历单链表 // 从头开始，顺序输出 void Traverse (struct Node *head) { struct Node *p = head-next; while(p != NULL) { cout p-data endl; // 访问当前节点 p = p-next; } } 7.7.4查找 // 从头顺序查找，若找到，返回指向该节