C语言链表及链表上机题.ppt

第13讲 链表,链表概述（1）,所谓链表是指若干个数据项（每个数据项称为一个“结点”）按一定的原则连接起来。每个数据项都包含有若干个数据和一个指向下一个数据项的指针，依靠这些指针将所有的数据项连接成一个链表。,链表概述（2）,struct student long num; float score; sturct student *next ; struct student *head;,一个简单链表示例：,内存动态管理函数,动态分配存储 根据需要开辟或释放存储单元 相关函数 malloc函数 calloc函数 free函数 说明 应包含stdlib.h,malloc函数,函数原型 typedef unsigned size_t; void *malloc(size_t size); 参数 size:分配存储空间的字节数 返回值 若成功，返回指向分配区域起始地址的指针 若失败，返回NULL,calloc函数,函数原型 void *calloc(size_t n, size_t size); 参数 n :分配内存的项目数 size:分配内存的每个项目的字节数 返回值 若成功，返回指向分配区域起始地址的指针 若失败，返回NULL,free函数,函数原型 void free(void *ptr); 参数 ptr:要释放的内存区地址 说明 释放prt指向的内存区 释放后的内存区能够分配给其他变量使用,链表的基本操作,链表的建立 从链尾到链头：新结点插入到链头 从链头到链尾：新结点插入到链尾 链表的插入操作 根据一定的条件，把新结点插入到指定位置 链表的删除操作 根据一定的条件，删除一个或多个结点 链表的输出操作 链表的查找操作,建立链表操作(从链尾到链头),head,., head = p;, p = malloc(sizeof (struct node); p-data = ai;, for(i=0; in; i+), p-next = head;,建立链表操作 (从链头到链尾),., p-next = q;, q = malloc(sizeof (struct node); q-data = ai;, for(i=0; in; i+), q-next = NULL;, p = q;,链表的插入操作,.,., p-next = q;, q = malloc(sizeof (struct node); q-data = x;, if(p满足插入条件), q-next = p-next;,链表的删除操作,.,., p-next = q-next;, free(q);, q = p-next;, if(p-next满足删除条件),链表的输出操作,.,., p = p-next;, while(p), printf(“%d“, p-data);,链表的查找操作,.,., p2=p1;p1=p1-nxet ;, while(x!=p1-num & p1!=NULL ), printf (find: %ld %5.2fn，x，p1-num);,2007-9,1、函数main( )的功能是:在带头结点的单链表中查找数据域中值最小的结点.请填空 #include struct node int data; struct node *next; ; int min(struct node *first)/*指针first为链表头指针*/ strct node *p; int m; p=first-next; m=p-data; p=p-next; for(; p!=NULL; p=_20_) if(p-data data; return m; ,p-next,2008-9,1、假定已建立以下链表结构，且指针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,1、以下程序把三个NODETYPE型的变量链接成一个简单的链表,并在while循环中输出链表结点数据域中的数据，请填空。 #include struct node int data; struct node *next; typede