在C语言中，线性表的链式表示通常使用链表来实现。链表中的每个节点都包含两部分：数据域和指针域。数据域用于存储节点的值，而指针域则用于指向链表中的下一个节点。链表的第一个节点称为头节点，它通常包含一个指向第一个数据节点的指针。链表的最后一个节点称为尾节点，其指针域通常设置为NULL，表示链表的结束。
下面是一个简单的C语言程序，展示了如何使用链表来实现线性表的链式表示和基本操作：
|
#include <stdio.h> |
|
#include <stdlib.h> |
|
|
|
// 定义链表节点结构体 |
|
typedef struct ListNode { |
|
int data; // 数据域 |
|
struct ListNode *next; // 指针域，指向下一个节点 |
|
} ListNode; |
|
|
|
// 定义链表结构体 |
|
typedef struct { |
|
ListNode *head; // 头节点指针 |
|
int length; // 链表长度 |
|
} LinkedList; |
|
|
|
// 初始化链表 |
|
void InitList(LinkedList *L) { |
|
L->head = (ListNode *)malloc(sizeof(ListNode)); // 创建头节点 |
|
if (!L->head) { |
|
exit(1); // 分配内存失败，退出程序 |
|
} |
|
L->head->next = NULL; // 头节点指向NULL |
|
L->length = 0; // 链表长度为0 |
|
} |
|
|
|
// 在链表尾部插入节点 |
|
void ListInsert(LinkedList *L, int e) { |
|
ListNode *newNode = (ListNode *)malloc(sizeof(ListNode)); // 创建新节点 |
|
if (!newNode) { |
|
exit(1); // 分配内存失败，退出程序 |
|
} |
|
newNode->data = e; // 设置新节点的数据 |
|
newNode->next = NULL; // 新节点的指针域初始化为NULL |
|
ListNode *tail = L->head; // 从头节点开始查找尾节点 |
|
while (tail->next) { |
|
tail = tail->next; // 遍历到尾节点 |
|
} |
|
tail->next = newNode; // 将新节点插入到尾部 |
|
L->length++; // 链表长度加1 |
|
} |
|
|
|
// 删除链表中的节点 |
|
void ListDelete(LinkedList *L, int i) { |
|
if (i < 1 || i > L->length) { |
|
return; // 删除位置不合法 |
|
} |
|
ListNode *prev = L->head; // prev用于记录待删除节点的前一个节点 |
|
for (int j = 1; j < i; j++) { |
|
prev = prev->next; // 查找待删除节点的前一个节点 |
|
} |
|
ListNode *toDelete = prev->next; // 待删除节点 |
|
prev->next = toDelete->next; // 将待删除节点从链表中移除 |
|
free(toDelete); // 释放待删除节点的内存 |
|
L->length--; // 链表长度减1 |
|
} |
|
|
|
// 获取链表中第i个节点的值 |
|
int GetElem(LinkedList L, int i, int *e) { |
|
if (i < 1 || i > L.length) { |
|
return 0; // 获取位置不合法 |
|
} |
|
ListNode *p = L.head; // 从头节点开始查找 |
|
for (int j = 1; j < i; j++) { |
|
p = p->next; // 查找第i个节点 |
|
} |
|
*e = p->data; // 获取节点的值 |
|
return 1; |
|
} |
|
|
|
// 打印链表 |
|
void PrintList(LinkedList L) { |
|
ListNode *p = L.head->next; // 从头节点的下一个节点开始遍历 |
|
while (p) { |
|
printf("%d ", p->data); |
|
p = p->next; // 移动到下一个节点 |
|
} |
|
printf("\n"); |
|
} |
|
|
|
// 释放链表内存 |
|
void DestroyList(LinkedList *L) { |
|
ListNode *p = L->head; // 从头节点开始遍历链表 |
|
ListNode *tmp; |
|
while (p) { |
|
tmp = p; |
|
p = p->next; // 移动到下一个节点 |
|
free(tmp); // 释放当前节点的内存 |
|
} |
|
L->head = NULL; |
|
L->length = 0; |
|
} |
|
|
|
int main() { |
|
LinkedList L; |
|
InitList(&L); // 初始化链表 |
|
|
|
ListInsert(&L, 10); // 插入节点10 |
|
ListInsert(&L, 20); // 插入节点20 |
|
ListInsert(&L, 30); // 插入节点30 |
|
|
|
PrintList |
