第13讲链表 C语言课件.pptVIP

第13讲 链表 链表概述（1） 所谓链表是指若干个数据项（每个数据项称为一个“结点”）按一定的原则连接起来。每个数据项都包含有若干个数据和一个指向下一个数据项的指针，依靠这些指针将所有的数据项连接成一个链表。 链表结构定义用结构体来实现。 链表概述（2） 内存动态管理函数 动态分配存储 根据需要开辟或释放存储单元 相关函数 malloc函数 free函数 说明 应包含stdlib.h malloc函数 函数原型 typedef unsigned size_t; void *malloc(size_t size); 参数 size:分配存储空间的字节数 返回值 若成功，返回指向分配区域起始地址的指针 若失败，返回NULL free函数 函数原型 void free(void *ptr); 参数 ptr:要释放的内存区地址 说明 释放prt指向的内存区 释放后的内存区能够分配给其他变量使用 链表的基本操作 链表的建立 从链尾到链头：新结点插入到链头 从链头到链尾：新结点插入到链尾 链表的插入操作 根据一定的条件，把新结点插入到指定位置 链表的删除操作 根据一定的条件，删除一个或多个结点 链表的输出操作 链表的查找操作 建立链表操作(从链尾到链头) 建立链表操作 (从链头到链尾) 链表的插入操作 链表的删除操作 链表的输出操作 链表的查找操作 两种链表的区别 带头结点的链表：p 第一个节点表示：p=head-next; 不带头结点的链表： 第一个节点表示：p=head; 2007年9月 1、以下程序的输出结果是_______________ # includestdio.h struct tt {int x; struct tt *y;} *p; struct tt a[4]={20,a+1,15,a+2,30,a+3,17,a}; main( ) {int i; p=a; for (i=1;i=2;i++) {printf(“%d,”,p-x); p=p-y;} } 2008年9月 1. 假定已建立以下链表结构，且指针p 和q 已指向如图所示的结点： head data next ↑p ↑q 则以下选项中可将 q 所指结点从链表中删除并释放该结点的语句组是（ ）。 A）(*p).next=(*q).next; free(p); B）p=q-next; free(q); C）p=q; free(q); D）p-next=q-next; free(q); 2009年3月 以下程序把三个NODETYPE型的变量链接成一个简单的链表，并在while循环中输出链表结点数据域中的数据。请填空： #include stdio.h struct node{int data;struct node *next;}; typedef f struct node NODETYPE; main( {NODETYPE a,b,c,*h,*p; a.data=10;b.data=20;c.data=30;h=a; a,.next=b;b.next=c;c.next=‘\0’; p=h; while (p) {printf(“%d,”,p-data); ;} printf(“\n”); } 题盘（16道） 14-1；36-1（排序）48-3(求平均值);57-2；65-1；67-1逆置链表；77-2；79-1；79-2；81-3；88-1；90-1求和；91-1逆置；92-1插入；94-1删除；103-1； C语言程序设计 C语言程序设计 C语言程序设计 C语言程序设计 上一页 下一页 a1 a2 a3 ... an ^ head struct student data next ai struct student { char name[20]; long num; float score; struct student *next; }; struct student *head; 1620 head 李为 2004101 85 0586 数据项A 数据项C 刘娜 2004102 93 3818 数据项B 张三 2004125 95 0 1620 0586 3818 一个简单链表示例： head ai-1 ... ④ head = p; ② p = malloc(sizeof