不带空头节点的链表
在这种链表中每一个节点都用来存放数据。
我们可以在链表结构体中把指向节点结构体的头尾指针定义出来，并选取一个int型的变量length来控制链表的长度。
同样以简单的学生成绩管理系统为例。
#include <stdio.h> #include <stdlib.h> /*数据结构体*/ typedef struct Student { int number; char name[20]; float math; }STU; typedef STU* PtStu; /*节点结构体*/ typedef struct Node { /*数据域*/ STU data; /*指针域*/ struct Node* pnext; }NODE; typedef NODE* PtNode; /*链表*/ typedef struct List { /*头尾指针*/ PtNode pfront; PtNode prear; /*长度*/ int length; }LIST; typedef LIST* PtList;
首先，同样要初始化链表：
我们都知道在带有空头节点的链表中，可以直接把空头节点创建出来；
现在初始化链表要确定头指针、尾指针指向哪里，长度究竟是多少（即创建链表的“管理者”）
这里的plist指向的内存是链表里面的节点。
//创建一个头结点（是链表的一部分） PtList ListInit() { PtList ptlist = (PtList)malloc(sizeof(LIST)); ptlist->pfront = NULL; ptlist->prear = NULL; ptlist->length = 0; return ptlist; }
接着，判断链表是否为空
//为空返回1 不为空返回0 unsigned char IsEmpty(PtList ptlist)//此处想用八个位的char表示布尔型，在c++中可直接用bool函数 { if (NULL == ptlist->pfront&& NULL == ptlist->prear && 0 == ptlist->length) return 1; else return 0; }
之后，我们就可以操作链表来达到目的了。
在增加节点的时候，以增加第一个节点为例：头尾指针都指向第一个节点，同时length变为1，增加第二个节点时尾指针后移，length+1，如图
接下来依次类推，在后面增加只要尾指针后移，如果我们想要在前面增加可以把头指针向前移动，效果一样。
我们可以在外面（main函数中）开辟内存空间，
因此在main函数中我们就可以增加以下代码，仍然用for循环来控制增加个数。
int n = 0; printf("需要增加几条信息："); scanf("%d", &n); for (int i = 0; i <n; i++) { PtNode ptnode = (PtNode)malloc(sizeof(NODE)); memset(ptnode, 0, sizeof(NODE)); printf("input numeber: "); scanf("%d", &ptnode->data.number); printf("input name: "); scanf("%s", ptnode->data.name); printf("input score: "); scanf("%f", &ptnode->data.math); AddListNode(ptlist, ptnode); }
在函数中就可以只针对链表了，把链表的节点作为参数带进去，作为链表结构体的指针。
我们也就能分为原本为空和不为空两种。
为空时
不为空时
简化后代码如下：
//增加链表的节点 在ptlist这个链表中增加ptnode void AddListNode(PtList ptlist, PtNode ptnode) { if (IsEmpty(ptlist) != 1) //不为空的 ptlist->prear->pnext = ptnode; else //为空 ptlist->pfront = ptnode; ptlist->prear = ptnode; ptlist->length++; }
接下来遍历链表可以使用函数指针，只要不是空，就查看数据
//查看一个节点数据 void SeekData(PtNode ptnode) { if (ptnode != NULL) { printf("number:%d ", ptnode->data.number); printf("name:%s ", ptnode->data.name); printf("math:%.2f ", ptnode->data.math); } }
因为length为节点的个数，我们可以直接由此依次输出，每遍历一次指针后移一个，节点数也就减少一个。
//遍历 void TaverseList(PtList ptlist, void(*Traverse)(PtNode ptnode)) { PtNode ptnode = ptlist->pfront; int num = ptlist->length; while (num) { Traverse(ptnode); ptnode = ptnode->pnext; num--; } }
这样TaverseList(ptlist, SeekData);就可以达到遍历链表的目的。
我们也就可以想到查找就是把固定的节点遍历出来，也就能够解决了，并且修改过之后也可以通过该函数指针遍历出来。
删除节点时要注意length要-1并且最后要返回头节点
PtNode DeleteList(PtList ptlist, PtNode ptlistnode) { PtNode ptnode = ptlist->pfront; if (IsEmpty(ptlist) != 1) { memcpy(ptlistnode, ptnode, sizeof(NODE)); ptlist->pfront = ptlist->pfront->pnext; free(ptnode); ptlist->length--; if (0 == ptlist->length) ptlist->prear = NULL; } return ptlist->pfront; }
与带空头节点的链表相比，不带空头节点的链表更有掌握全局的感觉，但是代码也会更复杂一点。