大学c++计算机课件.pptVIP

第六章 结构和链表 6.1 结构类型 6.2 结构的应用--链表 6.3 应用举例 6.2 结构的应用——链表 6.2.2 链表的建立 6.2.3 单链表的基本操作 2、 统计结点个数 4、在链表中插入结点 5、删除链表中的某个结点 if(head==NULL) ; //newnode成为空表的第一个结点 else ;//将newnode连接到原来的表尾 ; // newnode成为新的表尾 } tail-next=NULL; return(head); } void main( ) { struct node *head; int n; cout请输入初始链表结点数:; cinn; head = create(n); } head=newnode tail-next=newnode tail = newnode 1、链表的遍历 由于链表的指针域中包含了后继结点的存储地址，所以只要知道该链表的头指针，即可依次对每个结点进行访问。 【例6.4】输出上例中建立的单链表的各结点的值。 假设定义p是指向链表中结点的工作指针，该指针从表头head开始逐一指向后续的各个结点，每指向一个结点，便通过该指针访问结点的数据域，直到p的值为NULL。 遍历的函数实现如下： void print(struct node *head) { struct node *p=head; while(p!=NULL) { coutp-data\t; ; //注意不能通过p++实现 指针后移 } } p = p-next 【例6.5】统计例6.3中创建的链表中结点的个数。 设置一个工作指针从表头结点开始，每经过一个结点，计数器的值增加1。实现统计的函数形式如下： int count(struct node *head) { struct node *p = head; int n = 0; while (p != NULL) { n++; p = p-next; } return(n); } 3、查找结点 【例6.6】在链表中按序号查找第i个结点。 设置一个序号计数器j和一个工作指针p，从表头结点开始，顺着链表的链进行查找。仅当j==i并且p!= NULL时查找成功，否则查找不成功。 void search(struct node *head, int i) { int j=1; struct node *p=head; if(i0) coutillegal index\n; else { while(j !=i p!= NULL) { j++; ; } if( ) coutindexi:p-data; else coutillegal index \n; } } p=p-next j==ip!=NULL 假定有一个指针behind 指向链表中的某个结点，newnode指向待插入结点。 newnode 12 10 15 19 behind front 如果有一个指针front指向behind的前驱，则仅需编写下面的两个语句，即可实现插入。 ; ; 如果没有behind指针，插入操作仍然可以完成。 newnode-next=front-next; front-next=newnode; 思考题：上述两个语句的次序能否交换？为什么？ newnode-next=behind front-next=newnode behind 7 两种特殊情况： 1. 在表头结点之前插入：