C语言程序设计课件：第9章-2链表.ppt

1、n数组的缺点数组的缺点?删除数组中的一个元素删除数组中的一个元素在数组中插入一个元素在数组中插入一个元素在数组末尾添加一个元素在数组末尾添加一个元素链表概述链表概述int a10; /定义数组定义数组a0 a1a2 a3 a4a5 a6 a7 a8 a9a2022-1-223ABCDE01234元素元素序号序号ABC01234元素元素下标下标5优点：便于快速、随机存取线性表中任一元素优点：便于快速、随机存取线性表中任一元素缺点：插入和删除操作需要移动大量元素缺点：插入和删除操作需要移动大量元素DEXAB01234元素元素下标下标CDE2022-1-224ABCDE01234元素元素序号序号缺点

2、：缺点：属于静态内存分配，程序一旦运行长度不能改变。属于静态内存分配，程序一旦运行长度不能改变。若想改变，只能修改程序。若想改变，只能修改程序。一旦确定，会带来两个问题：一旦确定，会带来两个问题： 1 1）不能超过数组元素最大长度的限制，否则溢出。）不能超过数组元素最大长度的限制，否则溢出。 2 2）数组元素低于所设定的）数组元素低于所设定的最大长度最大长度，将造成系统资，将造成系统资源的浪费。源的浪费。2022-1-225n要存储一组任意的数据元素可用多种方式，如：要存储一组任意的数据元素可用多种方式，如：数组数组 ：内存分配空间连续，长度事先固定。：内存分配空间连续，长度事先固定。链表链表

3、 ：内存分配空间可以不连续，在程序运行中可：内存分配空间可以不连续，在程序运行中可 根据需要动态分配或释放内存。根据需要动态分配或释放内存。结点结点头指针头指针1200032300510487NULL1750head1750200023001048链表概述链表概述n链表链表是指将一组同类型数据（通常为结构体类型）按其特有是指将一组同类型数据（通常为结构体类型）按其特有的方式连接在一起的一种数据结构的方式连接在一起的一种数据结构n链表中的元素称为链表中的元素称为结点结点。每一个结点都包含两类数据：一类。每一个结点都包含两类数据：一类数据称为结点的数据称为结点的值域值域；另一类数据称为；另一类数据

4、称为链域链域，它通常是与结，它通常是与结点同类型的指针，用来指向链表中的下一个结点点同类型的指针，用来指向链表中的下一个结点。n任何一个链表都有一个起始结点，称为该链表的任何一个链表都有一个起始结点，称为该链表的头结点头结点（head）。链表的最后一个结点称为）。链表的最后一个结点称为尾结点尾结点，它的链域指针不，它的链域指针不指向任何结点，通常将它设置为空指针。指向任何结点，通常将它设置为空指针。链表概述链表概述结点结点头指针头指针1200032300510487NULL1750head1750200023001048 头指针定义头指针定义: :node node * *head;head;

5、 结点的定义：结点的定义：struct node struct node int data; int data; node node * *next;next;linkedlist.swf处理动态链表所需的函数处理动态链表所需的函数 库函数提供动态地开辟和释放存储单元的库函数提供动态地开辟和释放存储单元的有关函数：有关函数：(1)malloc函数函数其函数原型为其函数原型为void *malloc(unsigned int size);其作用是在内存的动态存储区中分配一个长度为其作用是在内存的动态存储区中分配一个长度为size的连续空间。此函数的值（即的连续空间。此函数的值（即“返回值返回值”

6、）是一个指向分配域起始地址的指针（类型为是一个指向分配域起始地址的指针（类型为void）。如果此函数未能成功地执行（例如内）。如果此函数未能成功地执行（例如内存空间不足），则返回空指针存空间不足），则返回空指针(NULL)。(2) calloc函数函数 其函数原型为其函数原型为 void *calloc（unsigned ，unsigned size）;其作用是在内存的动态存储区中分配个长度其作用是在内存的动态存储区中分配个长度为为size的连续空间。函数返回一个指向分配域的连续空间。函数返回一个指向分配域起始地址的指针；如果分配不成功，返回起始地址的指针；如果分配不成功，返回NULL。 用用

7、calloc函数可以为一维数组开辟动态存函数可以为一维数组开辟动态存储空间，储空间，n为数组元素个数，每个元素长度为为数组元素个数，每个元素长度为Size。(3) free函数函数 其函数原型为其函数原型为void free（void *p）;其作用其作用是释放由指向的内存区，使这部分内存区能是释放由指向的内存区，使这部分内存区能被其他变量使用。是最近一次调用被其他变量使用。是最近一次调用calloc或或malloc函数时返回的值。函数时返回的值。free函数无返回值。函数无返回值。 以前的版本提供的以前的版本提供的mallocmalloc和和calloccalloc函数函数得到的是指向字符型

8、数据的指针。得到的是指向字符型数据的指针。 ANSI ANSI 提提供的供的mallocmalloc和和calloccalloc函数规定为函数规定为voidvoid类型。类型。链表的基本操作链表的基本操作链表构建与操作（定义结点类型）链表构建与操作（定义结点类型）1200032300510487NULL1750head17502000230010481. 1. 建立一条无序链表建立一条无序链表单步单步EX11_31将结点设置为表头的过程如下图所示：将结点设置为表头的过程如下图所示：(a) 加入结点前加入结点前p1headp1head(b) 加入结点后加入结点后p2头结点头结点将结点加到链表末尾

9、的过程如下图所示：将结点加到链表末尾的过程如下图所示：nextnextdatadata头结点头结点结点结点nnextdata新结点新结点p1p2head(a) 加入前加入前nextnextdatadata头结点头结点结点结点nnextdata结点结点n+1p1p2head(b) 加入后加入后2. 输出链表上各个节点的值输出链表上各个节点的值单步单步EX11_313. 删除链表上具有指定值的一个结点删除链表上具有指定值的一个结点head=p2-next;head=p2-next;123headp1NULL4headp1,p2NULL3456p1-next=p2-next;p1-next=p2-n

10、ext;head4.4.删除删除p2p2所指结点所指结点 delete p2;delete p2;p2p2p1p23 node *Delete_one_node(node *head,int num) node *p1,*p2;if(head = 0)printf(链表为空，无结点可删除链表为空，无结点可删除!n);return 0; if(head-data = num)p2 = head; head = head-next; free( (void *)p1 );printf(删除了一个结点删除了一个结点!n); else p1 = head; p2 = head; while(p2-da

11、ta != num & p2-next != 0) p1 = p2; p2 = p2-next; if(p2-data = num)p1-next = p2-next;free( (void *)p2 );printf(删除了一个结点删除了一个结点!n); elseprintf(链表上没有找到要删除的结点链表上没有找到要删除的结点!n); return head; 单步单步EX11_314. 释放链表的结点空间释放链表的结点空间单步单步EX11_315. 把一个结点插入链表把一个结点插入链表指向新结点指向新结点指向当前结点指向当前结点指向当前结点的前一个结点指向当前结点的前一个结点1.1.链表

12、为空时链表为空时: : p=new node; p=new node;head=p; p-next=NULL;head=p; p-next=NULL;2.2.插在链表的第一个结点前，插在链表的第一个结点前，p1p1指向第一个结点指向第一个结点: :p-next=head; head=p; p-next=head; head=p; 1NULLheadp234NULLhead1pp2-next=p; p-next=NULL;p2-next=p; p-next=NULL;-102NULLhead1pp2p1NULLNULL-2-10head1pp2 node *Insert(node *head,n

13、ode *p) node *p1,*p2;if(head = 0 )head = p; p-next = 0;return head;if(head-data = p-data)p-next = head; head = p;return head;p2 = p1 = head;while(p2-next & p2-data data)p1 = p2; p2 = p2-next; if(p2-data data) p2-next = p; p-next = 0;elsep-next = p2; p1-next = p; return head; 单步单步EX11_31node *Create_sort(void) node *p1,*head = NULL; int a; printf(产生一条有序链表，输入数据，以产生一条有序链表，输入数据，以-1结束结束); scanf(%d,&a); while(a!=-1) p1=(node *)malloc(sizeof(node); p1-data=a;head = Insert(head,p1); scanf(%d,&a); return head;单步单步EX11_31