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( )的功能是:在带头结点的单链表中查找数据域中值最小的结点.请填空#includestructnode intdata; structnode*next;intmin(struct node*first)/*指针first为链表头指针*/strct node*p;intm; p=first-next;m=p-data; p=p-next; for(; p!=NULL; p=_20_) if(p-data data;returnm;,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 nodeint data; struct node *next;typedef struct node NODETYPE;main() NODETYPE a,b,c,*h,*p;a.data=10;b.data=20;c.data=30;h=,p=p-next,