美文网首页
单链表-带头结点

单链表-带头结点

作者: 又是一只小白鼠 | 来源:发表于2020-04-04 22:32 被阅读0次

带头结点的单链表是指，在单链表的首元结点之前增加一个特殊的结点，称为头结点。
头结点的作用：使所有链表（包括空表）的头指针非空，并使对单链表的插入，删除操作不需要区分是否为空表或是否在第一个位置进行，从而与其他位置的插入，删除操作一致。

结构体

#include "seqlistlink.h"
#include <stdlib.h>
#include <assert.h>

typedef int ElemType;

typedef struct LinkNode
{
    ElemType data;
    struct LinkNode *next;
}Node,*pNode;

创建结点

//为新节点开辟空间 这个一块存储空间 包括一个数据域+一个指针域
pNode NewSpace(ElemType data)
{
    pNode tmp = (Node *)malloc(sizeof(Node));
    tmp->data = data;
    tmp->next = NULL;
    return tmp;
}

初始化

//初始化
void InitNodeList(pNode *pHead) {
    *pHead = (Node *)malloc(sizeof(Node));
    if(*pHead == NULL) {
        printf("申请空间失败...\n");
        return;
    }
    (*pHead)->next = NULL;
}

打印

//打印链表
void PrintNodeList(pNode head) {
    pNode p = head; //创建临时结点temp
    if (p == NULL) {
        printf("PrintNodeList---error...\n");
        return;
    }
    if (p->next == NULL) {
        printf("PrintNodeList---这是一个空表...\n");
        return;
    }
    p = p->next;
    while (p) {
        printf("%d\t", p->data);
        p = p->next;
    }
    printf("\n");
}

插入结点

//尾插
void InsertNodeBack(pNode *pHead, ElemType e) {
    assert(*pHead);
    pNode p = *pHead;
    pNode new = NewSpace(e);
    if(p->next == NULL) {
        p->next = new;
        new->next = NULL;
    }
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = new;
    new->next = NULL;
}
//头插
void InsertNodeFront(pNode *pHead, ElemType e) {
    assert(*pHead);
    pNode p = *pHead;
    pNode next = p->next;
    pNode new = NewSpace(e);
    if (p->next == NULL) {
        p->next = new;
        new->next = NULL;
    }
    else {
        p->next = new;
        new->next = next;
    }
}
//指定位置插入
void InsertNodePos(pNode *pHead, ElemType data, int pos) {
    assert(*pHead);
    pNode p = (*pHead)->next;
    pNode new = NewSpace(data);
    if (p == NULL) {
        printf("InsertNodePos----这是一个空表...\n");
        return;
    }
    if (pos < 1) {
        printf("InsertNodePos插入位置错误...\n");
        return;
    }
    if (pos == 1) {
        (*pHead)->next = new;
        new->next = p;
    }
    else {
        for (int i=1; i<pos-1; i++) {
            p = p->next;
            if (p == NULL) {
                printf("InsertNodePos找不到，超过链表最大长度...\n");
                return;
            }
        }
        new->next = p->next;
        p->next = new;
    }
}

删除结点

//尾删
void RemoveNodeBack(pNode *pHead) {
    assert(pHead);
    pNode p = (*pHead)->next;
    if (p == NULL) {
        printf("RemoveNodeBack---Seqlist is Empty...\n");
        return;
    }
    if (p->next == NULL) {
        free(p);
        (*pHead)->next = NULL;
        printf("RemoveNodeBack---删除成功， 这是一个空表了...\n");
        return;
    }
    else {
        pNode pre = p;
        p = p->next;
        while (p->next != NULL) {
            pre = p;
            p = p->next;
        }
        pre->next = NULL;
        free(p);
    }
}
//首删
void RemoveNodeFront(pNode *pHead) {
    assert(pHead);
    pNode p = *pHead;
    if (p->next == NULL) {
        printf("RemoveNodeFront---Seqlist is Enpty...\n");
        return;
    }
    pNode del = p->next;
    if (del->next == NULL) {
        free(del);
        p->next = NULL;
        printf("RemoveNodeFront---这是一个空表了...\n");
        return;
    }
    else {
        p->next = del->next;
        free(del);
    }
}
//指定位置删除
void RemoveNodePos(pNode *pHead, int pos) {
    assert(pHead);
    pNode p = *pHead;
    pNode del = p->next;
    if (p->next == NULL) {
        printf("RemoveNodePos---这是一张空表...\n");
        return;
    }
    if (pos == 1) {
        p->next = del->next;
        free(del);
    }
    else {
        for (int i=1; i<pos; i++) {
            p = p->next;
            if(p->next == NULL) {
                printf("RemoveNodePos---找不到要删除的坐标，超过了最大长度...\n");
                return;
            }
        }
        del = p->next;
        p->next = del->next;
        free(del);
    }
}

查找元素位置

//查找元素位置
int FindNodePos(pNode *pHead, ElemType data) {
    assert(*pHead);
    pNode p = (*pHead)->next;
    if(p == NULL) {
        printf("FindNodePos---空链表...\n");
        return -1;
    }
    int count = 1;
    while (p) {
        if (p->data == data) {
            return count;
        }
        else {
            p = p->next;
            count ++;
        }
    }
    printf("FindNodePos---找不到...\n");
    return -1;
}

删除值为data的结点

//删除第一个值为data的结点
void RemoveNodeNode(pNode *pHead, ElemType data) {
    assert(*pHead);
    int pos = FindNodePos(pHead, data);
    if (pos != -1) {
        RemoveNodePos(pHead, pos);
    }
    else {
        return;
    }
}
//删除所有值为data的结点
void RemoveNodeDataAll(pNode *pHead, ElemType data) {
    assert(pHead);
    pNode pre = (*pHead)->next;
    if (pre == NULL) {
        printf("RemoveNodeDataAll---链表为空...\n");
        return;
    }
    pNode front = *pHead;
    while (1) {
        if (pre->data == data) {
            front->next = pre->next;
            free(pre);
            pre = front->next;
        }
        else {
            front = pre;
            pre = pre->next;
        }
        if (pre == NULL) {
            return;
        }
    }
}

计算链表长度

//计算链表长度
int NodeLength(pNode pHead) {
    assert(pHead);
    int count = 0;
    pNode pre = pHead->next;
    while (pre) {
        count ++;
        pre = pre->next;
    }
    return count;
}

逆置

//链表逆置，一种比较简单的方法是将链表元素按照首插的方法插到新链中完成逆置
void ReverseNode1(pNode *pHead) {
    assert(pHead);
    pNode pre = (*pHead)->next;
    if (pre == NULL) {
        printf("ReverseNode1---链表为空...\n");
        return;
    }
    pNode new = NULL;
    while (pre) {
        pNode cur = pre;
        pNode temp = NewSpace(pre->data);
        temp->next = new;
        pre = pre->next;
        new = temp;
        free(cur);
    }
    (*pHead)->next = new;
}
//链表逆置，另一种比较简单的方法是将链表节点按照首插的方法插到新链中完成逆置
void ReverseNode2(pNode *phead) {
    assert(phead);
    pNode pre = (*phead)->next;
    pNode new = NULL;
    while (pre) {
        pNode cur = pre;
        pre = pre->next;
        cur->next = new;
        new = cur;
    }
    (*phead)->next = new;
}
//链表逆置
void ReverseNode3(pNode *phead) {
    assert(phead);
    pNode temp = (*phead)->next;
    pNode temp_pre = NULL;
    pNode temp_next = NULL;
    if (temp->next == NULL) {
        return;
    }
    else if(temp->next->next == NULL) {
        return;
    }
    while (temp) {
        temp_next = temp->next;// 保存当前节点的下一个节点
        temp->next = temp_pre;//更新当前节点的指针域
        temp_pre = temp;//更新当前节点上一个节点的位置
        temp = temp_next;//更新当前节点的位置
    }
    (*phead)->next = temp_pre;
}

拼接链表

//拼接C=A+B 新建结点值为pa->data或者pb->data，将pc的next指向new结点，pc=new；pa=pa->next或者pb=pb->next
void JointNodeNew(pNode *La, pNode *Lb, pNode *Lc) {
    assert(*La);
    assert(*Lb);
    assert(*Lc);
    pNode pa = (*La)->next;
    pNode pb = (*Lb)->next;
    pNode pc = *Lc;
    if (pa == NULL  && pb) {
        pc->next = pb;
        return;
    }
    if (pb == NULL && pa) {
        pc->next = pa;
        return;
    }
    while (pa && pb) {
        if (pa->data <= pb->data) {
            pNode next = pa->next;
            pNode new = NewSpace(pb->data);
            pc->next = new;
            pc= new;
            pa = next;
        }
        else {
            pNode next = pb->next;
            pNode new = NewSpace(pb->data);
            pc->next = new;
            pc= new;
            pb = next;
        }
    }
    while(pa) {
        pNode new = NewSpace(pa->data);
        pc->next = new;
        pc = new;
        pa = pa->next;
    }
    while(pb) {
        pNode new = NewSpace(pb->data);
        pc->next = new;
        pc = new;
        pb = pb->next;
}
//链接拼接 A = A+B temp->next = pa
//pa->next = NULL 说明temp是最后一个元素， 只需要把Lb拼接到La
//temp->next = pb;
//使用一个tmp指向Lb的头节tmp=pb;
//当要把pb的节点拼接到La,首先把头节点只想pb的下一个节点tmp=pb->next
//把pb插入到La中之后，再把pb指向Lb的头节点tmp
void JointNode(pNode *La, pNode *Lb) {
    assert(La);
    assert(Lb);
    pNode pa = (*La)->next;
    pNode pb = (*Lb)->next;
    pNode temp = *La;
    pNode tmp = *Lb;
    if (pa && pb == NULL) {
        return;
    }
    if (pb && pa == NULL) {
        (*La)->next = pb;
        return;
    }
    while (pa && pb) {
        if (pa->data > pb->data) {
            tmp = pb->next;
            temp->next = pb;
            pb->next = pa;
            temp = pb;
            pb = tmp;
        }
        else {
            temp = pa;
            pa = pa->next;
        }
    }
    if (pb == NULL) {
        return;
    }
    if (pb != NULL) {
        temp->next = pb;
    }
}

约瑟夫环

//约瑟夫环
void NodeJosephCycle(pNode *pHead, int k) {
    assert(pHead);
    pNode cur = (*pHead)->next;
    //第一步，先让链表构成环，即需要一个变量（tail）遍历至最后一个节点，
    //然后让最后一个结点的next指向*phead
    pNode tail = *pHead;
    while (tail->next != NULL) {
        tail = tail->next;
    }
    tail->next = (*pHead)->next;
    //第二步，让链表从起始地址进行查询，找到k的位置，然后删掉这个结点，
    //从该结点的下一个结点继续找K个位置，再次删掉，直到剩一个结点为止
    //cur是我们要删除的结点，用pre来标识cur的上一个位置。
    while (cur->next != cur) {
        pNode pre = NULL;
        for (int i=0; i<k-1; i++) {
            pre = cur;
            cur = cur->next;
        }
        pre->next = cur->next;
        printf("delete....%d\n", cur->data);
        free(cur);
        cur = pre->next;
    }
    printf("save...%d\n", cur->data);
    cur->next = NULL;
}

查找是否含有某一元素

//查找是否含有某一元素
int FindDataExit(pNode *head, int data) {
    assert(*head);
    pNode p = (*head)->next;
    if (p == NULL) {
        printf("链表为空...\n");
        return -1;
    }
    while (p) {
        if (p->data == data) {
            return 1;
        }
        else
            p = p->next;
    }
    return -1;
}

找出两个单链表的共同结点

//找出两个单链表的共同结点
void FindPublicNode(pNode *L1, pNode *L2, pNode *head) {
    pNode new = *head;
    pNode p1 = (*L1)->next;
    pNode p2 = (*L2)->next;
    while (p1) {
        while (p2) {
            if (p1->data == p2->data) {
                if (FindDataExit(&new, p1->data) == -1) {
                    InsertNodeBack(&new, p1->data);
                    p2 = p2->next;
                }
                else
                    p2 = p2->next;
            }
            else {
                p2 = p2->next;
            }
        }
        p2 = (*L2)->next;
        p1 = p1->next;
    }
}

倒数顺序查找

//查找倒数第k位置上的结点
int FindLastData(pNode head, int k) {
    assert(head);
    pNode p = head->next;
    int length = NodeLength(head);
    if (p == NULL) {
        printf("空链表...\n");
        return 0;
    }
    if (length-k < 0) {
        printf("找不到k位置的结点...\n");
        return 0;
    }
    for (int i=0; i<length-k; i++) {
        p = p->next;
    }
    int data = p->data;
    printf("%d\n", data);
    return 1;
}

//查找倒数第k位置上的结点-一次遍历完成
int search_k(pNode head, int k) {
    pNode p = head->next;
    pNode q = head->next;
    if (p == NULL) {
        printf("空表...\n");
        return 0;
    }
    for (int i=0; i<k; i++) {
        p = p->next;
        if (p == NULL) {
            printf("超出链表长度...\n");
            return 0;
        }
    }
    while (p) {
        p = p->next;
        q = q->next;
    }
    printf("%d\n", q->data);
    return 1;
}

测试

void testSeqlist() {
    Node list;
    pNode head = &list;
    InitNodeList(&head);
    pNode head2 = &list;
    InitNodeList(&head2);
    pNode head3 = &list;
    InitNodeList(&head2);
    pNode head4 = &list;
    InitNodeList(&head4);
    pNode head5 = &list;
    InitNodeList(&head5);
    InsertNodeBack(&head, 12);
    InsertNodeBack(&head, 15);
    InsertNodeFront(&head, 9);
    PrintNodeList(head);
    RemoveNodeBack(&head);
    PrintNodeList(head);
    RemoveNodeFront(&head);
    PrintNodeList(head);
    InsertNodePos(&head, 23, 2);
    PrintNodeList(head);
    RemoveNodePos(&head, 3);
    PrintNodeList(head);
    printf("%d\n", FindNodePos(&head, 12));
    RemoveNodeNode(&head, 34);
    PrintNodeList(head);
    InsertNodeBack(&head, 12);
    InsertNodeBack(&head, 15);
    InsertNodeFront(&head, 23);
    InsertNodeBack(&head, 30);
    InsertNodeBack(&head, 33);
    InsertNodeFront(&head, 23);
    InsertNodeBack(&head, 23);
    PrintNodeList(head);
    RemoveNodeDataAll(&head, 23);
    PrintNodeList(head);
    printf("%d\n", NodeLength(head));
    printf("ReverseNode1...\n");
    ReverseNode1(&head);
    PrintNodeList(head);
    ReverseNode2(&head);
    PrintNodeList(head);
//    ReverseNode3(&head);
//    PrintNodeList(head);
    InsertNodeBack(&head2, 12);
    InsertNodeBack(&head2, 15);
    InsertNodeFront(&head2, 9);
    InsertNodeBack(&head2, 20);
    InsertNodeBack(&head2, 33);
    InsertNodeFront(&head2, 4);
    InsertNodeBack(&head2, 45);
    printf("JointNodeNew...\n");
    PrintNodeList(head);
    PrintNodeList(head2);
    JointNodeNew(&head, &head2, &head3);
    PrintNodeList(head3);
    printf("JointNode...\n");
    PrintNodeList(head);
    PrintNodeList(head2);
    JointNode(&head, &head2);
    PrintNodeList(head);
//    printf("NodeJosephCycle...\n");
//    NodeJosephCycle(&head2, 5);
    printf("FindDataExit...\n");
    PrintNodeList(head3);
    printf("%d\n", FindDataExit(&head3, 33));
    InsertNodeBack(&head4, 12);
    InsertNodeBack(&head4, 15);
    InsertNodeBack(&head4, 29);
    InsertNodeBack(&head4, 33);
    InsertNodeBack(&head4, 45);
    InsertNodeBack(&head4, 50);
    InsertNodeBack(&head4, 54);
    printf("head4...\n");
    PrintNodeList(head4);
    printf("head2...\n");
    PrintNodeList(head2);
    FindPublicNode(&head2, &head4, &head5);
    PrintNodeList(head5);
    printf("head...\n");
    PrintNodeList(head);
    printf("length======%d\n", NodeLength(head));
    FindLastData(head, 13);
    search_k(head, 13);
}

相关文章

  • C语言实现常用数据结构：不带头结点的单链表（第4篇）

    使用示例 带头结点的单链表请参见： [C语言实现常用数据结构：带头结点的单链表（第3篇）(https://www....

  • java实现单向循环链表

    链表图解 带头结点的链表： 不带头结点的链表： 区别 带头结点的链表容易代码实现不带头结点的容易实现循环链表和双向...

  • 王道数据结构 第二章 线性表（3） 编程题上半部分

    设计一个递归算法，删除不带头结点的单链表L中的所有值为x的结点。 在带头结点的单链表L中，删除所有值为x的结点，并...

  • 线性表存储结构

    数组实现 结构体实现 带头结点的单循环链表 带头结点的双循环链表 带头结点 带头结点的单循环链表和双循环链表 不管...

  • 单链表-带头结点

    带头结点的单链表是指，在单链表的首元结点之前增加一个特殊的结点，称为头结点。头结点的作用：使所有链表（包括空表）的...

  • 数据结构_无头结点链表的插入定位和删除操作

    不带头结点的单链表各种操作（定位，插入，删除）的实现，从中可以明白单链表带头结点的优势，可以保证循环代码的一致性，...

  • 线性表最值问题

    找最小值 找最大值 顺序表求最大值 顺序表求最小值 带头结点单链表求最大值 带头结点单链表求最小值 q是 最大值/...

  • 单链表-不带头结点

    链表，别名链式存储结构或单链表，用于存储逻辑关系为 "一对一" 的数据。与顺序表不同，链表不限制数据的物理存储状态...

  • 数据结构课程 第三周 线性表--链式表

    逻辑次序和物理次序不一定相同 带头结点的单链表 单链表上的操作实现 初始化 判空 单链表销毁 清空单链表（头指针和...

  • 链表的练习题

    编码实现：设带头结点L的单链表，从尾到头反向输出每个结点的值 void reverse(LinkList L) {...

网友评论

      本文标题：单链表-带头结点

      本文链接：https://www.haomeiwen.com/subject/lyxephtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|单链表-带头结点|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！