数据结构之链表（一）

数据结构中主要有三种数据形式，链表，树，图。其中链表是线性结构，其他的两种是非线性结构。

这里先从链表说起。

无论是哪种数据结构，都是由节点构成的。节点可以称之为，其基本单位。因而，一般写程序时。都先用结构体来定义一个节点。链表节点如下：

typedef struct NodeNODE,*PNODE;

但是，链表为方便程序员对其操作，创建了头节点。该节点只有地址没有数据，也就是说该节点只起到指向下个节点的作用。下个节点为首节点。该节点有数据，有地址（指针），与其他的有效节点一样。是链表数据链真正开始的标志。这里我用了数据链这个辞藻，在我的浅知拙见里是比较恰当的。尾节点是链表结束的标志因而尾节点只有数据，并没有地址（指针）。

因为头节点的存在，我们需要一个参数---头指针，就可以对链表操作了。

链表又分为了单链表，双链表，循环链表。。。这里只介绍最常见的单链表了。

关于链表，主要有以下几个难点以及重点：

链表的创建和遍历

链表长度的判断

链表是否为空，为满的判断

链表插入和删除

接下来，逐步进行介绍。

1）静态链表的创建：

静态链表的创建主要涉及到三个参数：len-用来设定有效节点个数；int--用于设定循环次数，来输入各个节点的数据，val-输入节点的值。动态链表的节点个数，无需事先指定。其链表创建直到达到某种条件时结束创建。

静态链表创建的示例程序如下：

PNODE creat_list(void){int len;int i;int val;//用于存放节点临时数据PNODE pHead = (PNODE)malloc(sizeof(NODE));//为头节点指针分配一个内存空间if (NULL == pHead){printf("分配失败,程序终止！\n");exit(-1);}PNODE pTail = pHead;//分配一个尾节点 ，指向头节点pTail 指向pHeadpTail->pNext = NULL;//将尾节点的指针域 清空printf("输入链表节点数：\n");scanf_s("%d", &len);

for (i = 0; i data = val;// pTail->pNext = pNew;//将新的节点挂到尾节点后面， pNew->pNext = NULL; //再将此时的新节点指针域清空 pTail = pNew; //然后再将pTail指向pNew}return pHead;}

程序有几个地方要注意的地方：

这里先为头节点动态分配一个内存。只允许程序员手动释放。这里有个问题，剩下的节点也是按照动态来分配的吗？

接下来判断头节点，判断是否为空。若空，则说明分配失败。后面还有涉及到，对某节点的指针来判断是否为空。这个问题后面再详述其区别。这里可以用：assert(pHead != NULL);来判断其是否为空。

然后再创建尾节点，将头节点指针也赋尾节点指针。同样动态创建？再将尾节点的指针（地址域）清空。确定尾节点。

接下来，循环创建。

先动态创建一个临时节点，备用。

最重要的四行来了！！

第一行，将节点值赋给新节点的数据域。

然后将尾节点指向临时节点，也就是说将临时节点挂到尾节点（也是头节点没有指针域那个节点）后面。

再将临时节点的指针域清空。此时，临时节点暂为 尾节点。

这里尾节点又指向临时节点。也就是说这里，临时节点彻底变成了尾节点。因为，这意味着现在的尾节点彻底有了含义！成为了有效数据。以下的节点构造同理。

2）链表的遍历

遍历的程序是比较容易理解的。示例程序如下：

void traverse_list(PNODE pHead){PNODE p = pHead->pNext;//将头指针指针域赋给pwhile (NULL != p) //当指针域不为空的时候，也就是不是尾节点的时候，继续{printf("%d\n", p->data);//打印该节点的数据p = p->pNext; //指针下移，指向下一个节点}printf("\n"); //换行return;}

这里借助指针p来不断下移打印数据，不可将p直接改为p->pHead。因为这样的话，只能打印第一个有效节点了。这里出过错。

————————————————————————————————

解释那四句话的时候，终于感受到了，想说说不出来的难受！！

补充一点：堆和栈都是动态存储。先写在这里，后面，写栈的时候再补上。