11.7用指针处理链表动态数据结构概念数组和结构体是定长数据结构，而链表、堆栈、队列、树、图等是执行时大小可变的动态数据结构。链表是连成一行的数据项集合，每一个数据项(元素)称为节点，可以在链表中的任意位置进行节点插入或删除操作，使链表数据项的个数随之增加或减少。链表的构成单向链表图示：2头节点表内节点尾节点210189.ad其中：各节点是相同的结构体类型，该类型有三个成员；head是指针变量c语言 链表，存放链表的头节点指针1048；各节点应包含一个指针成员存放下一节点的地址；各节点存储有可能不连续，但各节点逻辑上连续。节点的构成上图每个节点具有如下结构体类型：;;next;/链节成员*/其中：成员num、score用于存放一个节点的具体数据；成员next是指针类型，用于存放下一节点指针，最后一个节点的next成员存放空指针NULL；成员next是指向与自身同一类型的结构，这种结构称为自引用结构。(只有指针成员可自引用)节点是在运行时动态生成的。

  动态内存分配和释放建立和维护动态数据结构需要实现动态内存分配；如在链表中插入节点需要先申请一段存储区域，而删除一个节点需要释放该节点原先占用的存储区域，这可由标准函数实现。内存分配函数原形：voidmalloc();功能：申请长度为size个字节的内存空间；若申请成功，返回存储块起始指针，该指针类型为void；否则返回空指针(NULL)。内存释放函数原形：(void功能：释放p所指向的内存块。包含文件：malloc.h、stdlib.h中均有其原型声明。采用链表的意义与定长数据结构数组相比，链表能更好地利用内存，按需分配和释放存储空间。在链表中插入或删除一个节点，只需改变某节点“链节”成员的指向，而不需要移动其它节点，相对数组元素的插入和删除效率高。即：链表特别适合于对大线性表频繁插入和删除元素、或成员数目不定的数据结构。链表的类型单链表：每个节点只有一个指向后继节点的指针双向链表：每个节点有两个用于指向其它节点的指针；一个指向前趋节点，一个指向后继节点循环链表：使最后一个节点的指针指向第一个节点单链表的建立和输出建立链表的准备工作:定义与节点同类型的链表头指针变量head并赋值0，表示链表在建立之前是空的；开辟第一个节点的存储区域，使head、p1、p2指向第一个节点，并输入第一个节点数据；210189.操作：len=sizeof();p1=()malloc(len);scanf("%ld,%f",&p1->num,&p1->score);head=p2=p1;开辟下一节点的存储区域，使p1指向新节点、输入新节点数据，并将上一个节点的next成员指向新节点；210189.操作：p1=()malloc(len);scanf("%ld,%f",&p1->num,&p1->score);p2->next=p1;p2=p1;/使p2也指向新节点/重复第2步，建立并链接多个节点直至所需长度c语言 链表，将末尾节点的next成员赋值0。

  210189.操作：p1=()malloc(len);scanf("%ld,%f",&p1->num,&p1->score);p2->next=p1;p2=p1;/使p2也指向新节点/p2->next=NULL;/末尾节点next赋值0/10【例】建立并输出有3名学生数据的单链表。#/包含NULL的定义/##/结构体类型定义/;;next;/自引用结构体指针/((head,p1,p2;intlen;sqrt(5.5);/TC激活浮点运算/head=NULL;/head不指向任何位置/len=sizeof();/求类型长/p1=()malloc(len);/申请/printf(",score:");/输入数据/scanf("%ld,%f",&p1->num,&p1->score);head=p2=p1;/指向首节点/elsep2->next=p1;p2=p1;p2->next=NULL;/标记末尾节点/(p1=head;/p1指向首节点/elsep1=p1->next;/p1指向下一节点/printf("%d:num=%ld,score=%5.2f\n",p1->num,p1->score);/main/13【例】将上题利用函数实现，并求平均成绩。

  定义如下函数：建立链表函数:create(void);输出链表函数:(head);求平均值函数:(head);函数间信息传递：头指针头指针无返回值平均值头指针14###/全局结构类型/;;next;((head,create(void);(head);(head);intlen;;sqrt(5.5);clrscr(/TC中使用head=NULL;head=create(/返回链表头指针/plink(head);aver=averf(head);/返回平均值/printf("=%5.2f\n",aver); create( head, p1, p2; int len;len=sizeof(struct ); p1=( )malloc(len); printf("Enter num,score:"); scanf("%ld,%f", &p1->num, &p1->score); head=p2=p1;//头节点 else p2->next=p1;p2=p1; p2->next=NULL;//尾节点 return(head);//返回链表头指针 17void plink(struct head) /输出各节点/ p=head;else p=p->next; printf("%d:num=%ld,score=%5.2f\n", p->num,p->score); 210189.5 1370 1048 2101 89.5 1370 averf(struct head) =0; int p=head;/使p指向首节点/ while(p!=NULL) /c统计节点数/sum=sum+p->score; p=p->next; return(sum/c);/返回平均值/ 191370 节点的删除步骤： 找到，则将要删除节点的“链节”成员赋给前一节点的“链节”成员，使删除的节点脱离链表。

   若：要删除节点为首节点，则将首节点“链节”成 员赋给链头指针变量。 释放已被删除节点占用的空间。1 89.5 1370 head 2304 90 1012 2918 85 1012 20 【例】按上例删除指定学号的节点 struct del(struct head, long p1, p2; /n：要删除学号/ p1=head; if(p1->num==n) head=p1->next; /删除首节点/ else p2=p1;p1=p1->next; /继续找/ p1->num!=n);if(p1->num==n) p2->next=p1->next; /找到/ else printf("Not found!\n");/未找到/ free(p1);/释放被删除节点的存储区/ return(head); /返回头指针/ 21void plink(struct head) /更具通用性*/ p=head;while(p!=NULL) printf("num=%ld,score=%5.2f\n", p->num, p->score); p=p->next; 注：本形式的链表输出函数具有通用性，可适应由于删除或插入节点引起的链表长度的变化。

   22 节点的插入插入可分为随意插入和按顺序插入，随意插 入包括插入到头部、尾部或中间指定位置；按顺 序插入是指按某关键字的顺序插入，而在插入前 链表必须已按该关键字进行了排序。 按顺序插入的步骤： 查找插入位置：从链表首节点开始按关键字成员与待插入节点相同成员进行比较，直到确定 了插入位置； 23 点的“链节”成员；若：插入点在链头，则将头指针赋给待插入节点的 “链节”成员； 若：插入点在链头，先将头指针赋给插入节点的指针域，再将待插入节点的指针赋给头指针变量。 2101 89.5 1370 head 1048 2304 90 1012 2414 78 1 1 2918 85 NULL 24 【例】按上例在链表中按学号顺序插入节点 插入函数： struct insert(struct head) p0, p1, p2; long intlen; len=sizeof(struct ); p0=(struct )malloc(len); /申请新节点/ printf("Enter num,score insert:");scanf("%ld,%f", &p0->num, &p0->score); n=p0->num; /产生学号副本n/ p1=head; /从首节点开始查找/ p1=head;/插入在头部/ if(n

  num) p0->next=head;head=p0; do/查找插入位置/ p2=p1;p1=p1->next; n>p1->num);p0->next=p2->next; /插入在其余位置/ p2->next=p0; /insert/26 【例】编写一个通用的函数，可根据需要建立任意 节点数的链表。 struct creat( head=NULL, p1, p2; int len; long len=sizeof(); while(1) /循环次数不确定/ printf(",score:"); scanf("%ld,%f", break;/输入0表示数据结束/ p1=(struct )malloc(len); printf(",score:"); scanf("%ld,%f", break;/以0表示数据结束/ p1=(struct )malloc(len); p1->num=n; p1->score=s; /转存入节点/ if(head==NULL) head=p2=p1; else p2->next=p1;p2=p1; p2->next=NULL;/末尾链节成员赋空/ return(head); /返回链表头指针/ /creat/28