本文共 4360 字，大约阅读时间需要 14 分钟。
链表是一种非常常用的数据存储结构，广泛应用于数据的存储与操作。传统的链表结构存在一些操作不统一的问题，为了统一操作，最终我们根据需求重新定义了链表的存储结构。
最终采用的链表存储结构为：
typedef struct LDataNode { int x; struct LDataNode *next; // 结点指针} LDataNode;typedef struct LHeadNode { LDataNode *next; // 头 LDataNode *tail; // 尾} LHeadNode, *LinkList; 这种结构通过头结点存储链表的信息，避免了传统链表操作中的一些特殊情况，使得所有操作更加统一化。
链表的初始化需要创建一个头结点，并为其分配一个数据结点。
int InitList(LinkList *head) { // 初始化链表 *head = (LinkList)malloc(sizeof(LHeadNode)); LDataNode *vhNode = (LDataNode *)malloc(sizeof(LDataNode)); if (*head == NULL || vhNode == NULL) { return -1; // 申请失败 } vhNode->next = NULL; (*head)->next = vhNode; (*head)->tail = vhNode; return 0;} 由于头结点的指针域中包含尾指针，链表末尾添加元素变得非常简单。
int AddList(LinkList *head, int a) { // 链表末尾添加元素 LDataNode *vhNode = (LDataNode *)malloc(sizeof(LDataNode)); if (vhNode == NULL) { return -1; // 申请失败 } vhNode->x = a; vhNode->next = NULL; (*head)->tail->next = vhNode; // 挂到末尾 (*head)->tail = vhNode; // 尾指针更新 return 0;} 遍历链表时，只需访问元素，无需修改结点，因此只需单重指针即可。
int LTraverse(LinkList head) { // 遍历输出链表 LDataNode *p = head->next->next; // 第一个数据节点 while (p) { printf("%d ", p->x); p = p->next; } printf("\n"); return 0;} 删除链表中指定位置元素需要找到目标结点并调整指针。
int DeleteList(LinkList *head, int i, int *e) { if (i < 1) return -1; // 不合法 int num = 1; LDataNode *p = (*head)->next; // 指向第一个结点 while (num != i && p->next != NULL) { p = p->next; num++; } if (p->next == NULL) return -1; // 不合法 *e = p->next->x; p->next = p->next->next; // 删除 return 0;} 删除链表中值为e的元素需要根据值进行查找。
int DeleteList_value(LinkList *head, int e) { LDataNode *p = (*head)->next; // 指向第一个结点 while (p->next->x != e) { p = p->next; } if (p->next == NULL) return -1; // 没找到 p->next = p->next->next; // 删除 return 0;} 在第i个元素前面插入元素需要调整链表的指针。
int InsertList(LinkList *head, int i, int e) { if (i < 1) return -1; // 不合法 int num = 1; LDataNode *p = (*head)->next; // 指向第一个结点 while (num != i && p->next != NULL) { p = p->next; num++; } if (p->next == NULL) return -1; // 不合法 LDataNode *vhNode = (LDataNode *)malloc(sizeof(LDataNode)); if (vhNode == NULL) { return -1; // 申请失败 } vhNode->x = e; vhNode->next = p->next; p->next = vhNode; return 0;} 循环链表的区别在于最后一个元素指向头结点。
int InitList(LinkList *head) { *head = (LinkList)malloc(sizeof(LHeadNode)); LDataNode *vhNode = (LDataNode *)malloc(sizeof(LDataNode)); if (*head == NULL || vhNode == NULL) { return -1; } vhNode->next = (*head)->next; // 最后一个元素指向开头 (*head)->next = vhNode; (*head)->tail = vhNode; return 0;} 双向链表增加了前驱指针，便于向前遍历。
typedef struct LDataNode { int x; // 系数 int z; // 指数 struct LDataNode *next; // 下一个结点 struct LDataNode *pre; // 前驱结点} LDataNode;typedef struct LHeadNode { LDataNode *next; // 下一个结点 LDataNode *tail; // 尾结点} LHeadNode, *LinkList; 将两个多项式相加，首先需要将它们表示为链表形式。每个多项式有五项，输入每一项的系数和指数，按指数升序输入。
int AddList(LinkList *head, int a1, int a2) { LDataNode *vhNode = (LDataNode *)malloc(sizeof(LDataNode)); if (vhNode == NULL) { return -1; } vhNode->x = a1; vhNode->z = a2; vhNode->next = NULL; (*head)->tail->next = vhNode; (*head)->tail = vhNode; return 0;}int Add_LinkList(LinkList *H1, LinkList *H2, LinkList *H3) { LDataNode *p = (*H1)->next->next; LDataNode *q = (*H2)->next->next; while (q && p) { if (q->z == p->z) { AddList(H3, q->x + p->x, q->z); q = q->next; p = p->next; } else if (q->z > p->z) { AddList(H3, q->x, q->z); q = q->next; } else { AddList(H3, p->x, p->z); p = p->next; } } while (q) { AddList(H3, q->x, q->z); q = q->next; } while (p) { AddList(H3, p->x, p->z); p = p->next; } return 0;} int main() { LinkList H1, H2, H3; InitList(&H1); InitList(&H2); InitList(&H3); int T1 = 5, T2 = 5; while (T1--) { scanf("%d%d", &a1, &a2); AddList(&H1, a1, a2); } while (T2--) { scanf("%d%d", &a1, &a2); AddList(&H2, a1, a2); } Add_LinkList(&H1, &H2, &H3); LTraverse(H3);} 转载地址：http://evuf.baihongyu.com/