链表在C语言的实现
- C语言
- 10小时前
- 37热度
- 0评论
本文以图书馆的书目信息表为例，讲解链表在C语言的实现。
定义链表
链表存储的元素称为节点，节点由数据域和至少一个指针域构成，数据域存储数据，指针域存储指向该节点前驱或后驱节点的指针。若节点只有一个指针域，一般指向该节点的后驱节点，若无后驱节点，则该指针域为空或NULL。
C语言实现链表节点
typedef struct Node{
void* data; //数据域
struct Node *pnode; //指针域
}Node;
Node结构有两个成员：data为数据域，类型为void指针，可以指向任何类型的数据；pnode为指针域，指向Node结构。链表节点动态申请，当链表不再使用时，开发者需要删除链表节点，动态申请节点的链表也称为动态链表。
C语言定义图书书目结构
typedef struct{
char strIndex[30]; // 索引号
char name[50]; // 图书名称
char author[15]; // 作者
char press[50]; // 出版社
}BOOKINFO;
BOOKINFO结构共有四个字符数组成员，分别存储图书的索引号、图书名称、作者和出版社。链表节点的数据域为指向BOOKINFO结构的指针。
前面定义了链表节点和图书书目结构，下面实现单链表的HEAD节点（头节点），HEAD节点一般是个空节点，仅是作为链表的一个头节点，节点的数据域可以存储链表内的元素数量。
C语言实现链表HEAD节点
Node *pHead;
pHead = (Node*)malloc(sizeof(Node));
pHead->data = (void*)malloc(sizeof(int));
pHead->data = 0;
pHead->pnode = NULL;
代码使用C语言的malloc()函数从内存申请链HEAD表节点空间，HEAD节点的数据域指向整数类型的数据，用于存储链表内的元素数量，指针域默认为空值。存储链表HEAD节点的变量pHead建议声明为全局变量。
下面来实现单链表的插入运算，并探讨插入算法的复杂度，链表的其它运算请同学们参照插入运算自行给出。
插入运算
在链表插入一个节点，一般是在链表的索引位置插入一个节点。虽然链表存储的节点物理上不连续，但逻辑上是连续的，因此链表的索引位置为链表内节点的序号。例如在索引为2的位置插入一个新节点，需要将索引为1节点的指针域指向新节点，新节点的指针域指向原索引2的节点，节点插入成功后，插入位置之后的节点索引都会顺序加1，链表的节点数量也会加1。
C语言实现链表节点的插入
void insert(Node* pHead,int index,BOOKINFO* pBookInfo)
{
Node *p = pHead->pnode;
Node *pNewNode,*pPreNode;
int i = 0;
while( NULL != p && i < index )
{
pPreNode = p;
p = p->pnode;
i++;
}
if( NULL == p )
{
printf("没有查询到索引为%d的节点",index);
return;
}
// 申请一个新节点
pNewNode = (Node*)malloc(sizeof(Node));
pNewNode->data = (void*)pBookInfo;
pNewNode->pnode = p;
pPreNode->pnode = pNewNode;
}
参数pHead为链表HEAD节点指针，index为新节点插入的索引位置，pBookInfo为书目结构指针。函数将HEAD节点的指针域赋值给指针变量p，使用while循环查询索引位置为index的节点，循环条件是p不为空且变量i小于index，在循环过程中，将p的指针域赋值给p，并将p赋值给指针变量pPreNode，作为当前节点的前驱节点（前一个节点）。
循环结束后，若p为空值，则链表内没有索引位置为index的节点，函数返回。否则申请一个新的节点pNewNode，将pBookInfo赋值给新节点的数据域，p赋值给新节点的指针域，pNewNode赋值给pPreNode，新节点成功插入到链表内。
该运算在长度为n的链表中插入一个节点，插入前链表的长度为n，插入后链表的长度为n+1，index为插入节点的位置。虽然在链表内插入新的节点，不需要节点在内存中移动，只需要修改相应节点的指针域即可，但算法需要遍历链表找到index的插入位置，因此算法的时间复杂度为O(n)。
访问运算
在链表结构中，要访问index位置的元素，需要从链表的头结点开始，依次遍历链表中的每个元素，直至找到index位置的元素，因此链表访问运算的时间复杂度为O(n)，其中n为链表的长度。
C语言实现
Node* query(Node* pHead,int index)
{
Node *p = pHead->pnode;
int i = 0;
while( NULL != p )
{
if( i == index )
break;
p = p->pnode;
i++;
}
return p;
}
query()函数从链表的头结点开始，通过循环遍历链表中的每个节点，当节点序号与index相等时，该节点就是要查找的元素。
删除运算
从链表中删除一个节点，需要将被删节点的前驱节点的指针域指向下一个节点，并释放被删节点占用的内存。若被删节点为链表的第一个节点，需要将HEAD节点的指针域指向链表的第二个节点；若被删节点为链表的最后一个节点，需要将链表前驱节点的指针域置空。
C语言实现
// 删除节点
void deleteNode(Node* pHead, int index) {
Node *p = pHead->pnode;
Node *pre = pHead;
int i = 0;
while( NULL != p )
{
// 删除节点
if( i == index )
{
pre = p->pnode;
free(p);
break;
}
p = p->pnode;
pre = p;
i++;
}
}
函数使用了两个Node*指针，p指针用于遍历链表，pre指针指向当前节点的前驱节点，若当前节点为删除节点，则直接将p->pnode指针赋值给pre指针，并释放当前节点占用的内存空间。
