《C语言程序设计(第7章结构体与共用体)4.docx》由会员分享，可在线阅读，更多相关《C语言程序设计(第7章结构体与共用体)4.docx（5页珍藏版）》请在金锄头文库上搜索。
1、 C语言程序设计(第7章结构体与共用体)4数组作为存放同类数据的集合，给我们在程序设计时带来许多的便利，增加了敏捷性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定，不能在程序中进展调整，这样一来，在程序设计中针对不同问题有时需要3 0个大小的数组，有时需要5 0个数组的大小，难于统一。我们只能够依据可能的需求来定义数组，经常会造成肯定存储空间的铺张。 我们盼望构造动态的数组，随时可以调整数组的大小，以满意不同问题的需要。链表就是我们需要的动态数组。它是在程序的执行过程中依据需要有数据存储就向系统要求申请存储空间，决不构成对存储区的铺张。 链表是一种简单的数据构造，其数据之间的相互关
2、系使链表分成三种：单链表、循环链表、双向链表，下面将逐一介绍。 7.4.1 单链表 单链表有一个头节点head，指向链表在内存的首地址。链表中的每一个节点的数据类型为构造体类型，节点有两个成员：整型成员（实际需要保存的数据）和指向下一个构造体类型节点的指针即下一个节点的地址（事实上，此单链表是用于存放整型数据的动态数组）。链表按此构造对各节点的访问需从链表的头找起，后续节点的地址由当前节点给出。无论在表中访问那一个节点，都需要从链表的头开头，挨次向后查找。链表的尾节点由于无后续节点，其指针域为空，写作为NULL。 图7 - 3还给出这样一层含义，链表中的各节点在内存的存储地址不是连续的，其各节
3、点的地址是在需要时向系统申请安排的，系统依据内存的当前状况，既可以连续安排地址，也可以跳动式安排地址。 看一下链表节点的数据构造定义： struct node int num; struct node *p; ; 在链表节点的定义中，除一个整型的成员外，成员p是指向与节点类型完全一样的指针。在链表节点的数据构造中，特别特别的一点就是构造体内的指针域的数据类型使用了未定义胜利的数据类型。这是在C中规定可以先使用后定义的数据构造。 单链表的创立过程有以下几步： 1 ) 定义链表的数据构造。2 ) 创立一个空表。3 ) 利用malloc( )函数向系统申请安排一个节点。 4) 将新节点的指针成员赋值
4、为空。若是空表，将新节点连接到表头；若是非空表，将新节点接到表尾。5) 推断一下是否有后续节点要接入链表，若有转到3 )，否则完毕。 单链表的输出过程有以下几步 1) 找到表头。2) 若是非空表，输出节点的值成员，是空表则退出。3) 跟踪链表的增长，即找到下一个节点的地址。4) 转到2 )。 例7-5 创立一个存放正整数（输入- 9 9 9做完毕标志）的单链表，并打印输出。 #include /* 包含malloc( ) 的头文件*/#includestruct node /*链表节点的构造* / int num; struct node *next; ;main( ) struct node
5、 *creat(); / *函数声明* / void print(); struct node *head; / * 定义头指针* / head=NULL; /* 建一个空表*/ head=creat(head); /* 创立单链表*/ print(head);/*打印单链表*/ /*/struct node *creat(struct node *head) /* 函数返回的是与节点一样类型的指针*/ struct node *p1,*p2; p1=p2=(struct node*) malloc(sizeof(struct node); /* 申请新节点*/ scanf(“%d“, /*
6、输入节点的值*/ p1- next = NULL; /* 将新节点的指针置为空*/ while(p1-num0) /* 输入节点的数值大于0 */ if (head=NULL) head=p1; /* 空表，接入表头*/ else p2-next=p1; /* 非空表，接到表尾*/ p2 = p1; p1=(struct node *)malloc(sizeof(struct node); /* 申请下一个新节点*/ scanf(“%d“, /*输入节点的值*/ return head; /*返回链表的头指针*/ /*/void print(struct node *head) /* 输出以head 为头的链表各节点的值*/ struct node *temp; temp=head; /*取得链表的头指针*/ while (temp!=NULL) / *只要是非空表* / printf(“%6d“, temp-num); /*输出链表节点的值*/
