什么是链表

使用指针组织和处理表中的数据，称为链表。一般在程序设计中针对不同问题有时需要30个大小的数组，有时需要50个数组的大小，难于统一。我们只能够根据可能的最大需求来定义数组，常常会造成一定存储空间的浪费。

        因此我们希望构造动态的数组，随时可以调整数组的大小，以满足不同问题的需要。链表就是我们需要的动态数组。它是在程序的执行过程中根据需要有数据存储就向系统要求申请存储空间，决不构成对存储区的浪费。

单向链表

        链表是一组节点的集合，每个节点由两部分组成：数据和下一个节点的地址。每个节点由结构体数据类型表示。如图：

定义节点结构

struct nodeType

{

        int data; //节点数据区

        nodeType*link; //link存储下一节点的地址

} 

创建链表

    创建链表时需要三个指针来建立链表，分别指向链表的第一个节点，最后一个节点，新节点。对链表进行操作时必须从头（即第一个节点开始）遍历链表，所以创建链表后需要返回第一个节点。

#include <stdlib.h>

#include <stdio.h>

//定义链表数据结构

struct nodeType

{       

        int data; //节点数据区       

        nodeType*link; //link存储下一节点的地址

} 

main( )

{

    struct node *creat();

    void print();

    struct nodeType *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));/*新节点*/

    printf("p1= %d\n",p1);

    scanf("%d",&p1->num);/*输入节点的值*/

    p1->next=NULL;/*将新节点的指针置为空*/

    while(p1->num>0)/*输入节点的数值大于0*/

    {

        //将新节点的指针成员赋值为空。若是空表，将新节点连接到表头；若是非空表，将新节点接到表尾;

        if(head==NULL)

            head=p1;/*空表，接入表头*/

        else

            p2->next=p1;/*非空表，接到表尾*/

        p2=p1;

        p1=(struct node*)malloc(sizeof(struct node));/*下一个新节点*/

        printf("p2= %d\n",p2);

        scanf("%d",&p1->num);/*输入节点的值*/

        //判断一下是否有后续节点要接入链表，若有转到3 )，否则结束;

    }

    printf("p2->next=%d\n",p2->next);

    return head;/*返回链表的头指针*/

}

/*******************************************/

void print(struct node*head)/*打印以head为头的链表各节点的值*/

{

    struct nodeType *temp;

    temp=head;/*取得链表的头指针*/

    while(temp!=NULL)/*只要是非空表*/

    {

        printf("%6d",temp->num);/*输出链表节点的值*/

        temp=temp->next;/*跟踪链表增长*/

    }

}