链表的操作与应用

链表存储结构

链表是一种非常常用的数据存储结构，广泛应用于数据的存储与操作。传统的链表结构存在一些操作不统一的问题，为了统一操作，最终我们根据需求重新定义了链表的存储结构。

最终存储结构

最终采用的链表存储结构为：

头指针

头结点

数据头结点

数据结点

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的元素

删除链表中值为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个元素前面插入元素

在第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/

你可能感兴趣的文章

No 'Access-Control-Allow-Origin' header is present on the requested resource.