美文网首页数据结构
数据结构重学日记(九)单链表增删改查

数据结构重学日记(九)单链表增删改查

作者: 南瓜方糖 | 来源:发表于2019-01-10 23:04 被阅读0次

    上一节学完了单链表的基本操作,这里再像顺序表一样跑一下代码。毕竟只靠看是记不住多少东西的。

    单链表结构

    
    typedef int ElemType;
    
    typedef struct LNode {
        ElemType data;
        struct LNode *next;
    } LNode, *LinkList;
    
    // 遍历输出单链表
    void PrintLists(LinkList L) {
        LNode *  p = L->next;  //  LinkList p 也是可以的
        while (p) {
            printf("%d", p->data);
            p = p->next;
            printf("\r\n");
        }
    
    }
    
    

    创建

    单链表创建有两种模式,尾插法和头插法,具体概念在上一节已经写了。

    头插法

    
    
    LinkList CreatList(LinkList L) {
        int x;
        LNode *s; //辅助指针
        L = (LinkList) malloc(sizeof(LNode)); //创建头结点
        L->next = NULL; //初始为空表
        scanf("%d", &x); // 读取标准输入
        while (x != 999) { //输入999表示结束
            s = (LNode *) malloc(sizeof(LNode)); // 申请一个空间,强制类型转换
            s->data = x; //对新结点的数据域赋值
            s->next = L->next; //新节点的后继指向第一个结点
            L->next = s; //头结点的后继指向新结点
            scanf("%d", &x); //读取标准输入
        }
        return L;
    }
    
    

    在main 方法中初始化并调用:

    
    LinkList L;
    LinkList search;
    L = CreatList(L); // 输入数据为 2 3 4 999
    PrintLists(L);
    
    /*运行结果
    5
    
    4
    
    3
    
    2
    */
    

    尾插法 L = CreatList2(L);

    
    LinkList creatList2(LinkList L) {
        int x;
        L = (LinkList) malloc(sizeof(LNode));
        LNode *s, *r = L; // r为表尾指针,指向表尾
        scanf("%d", &x);
        while (x != 999) {
            s = (LNode *) malloc(sizeof(LNode));
            s->data = x;
            s->next = L->next;
            r->next = s;
            r = s;
            scanf("%d", &x);
        }
        r->next = NULL;
        return L;
    
    }
    
    /*
    2
    
    3
    
    4
    
    5
    */
    

    插入InsertElem(L, 2, 90)

    LNode *InsertElem(LinkList L, int i, ElemType x) {
    
        LNode * p = GetElem(L, i - 1);
        LinkList s = (LNode *) malloc(sizeof(LNode));
        s->next = p->next;
        s->data = x;
        p->next = s;
    }
    
    /*
    5
    
    90
    
    4
    
    3
    
    2
    */
    

    按序号查找 search = GetElem(L, 2)

    
    LNode *GetElem(LinkList L, int i) {
        int j = 1; // 计数 从1开始
        LNode * p = L->next; // 第一个节点指针赋予 p a1
    
        if (i == 0) return L; // 若 i = 0 ,返回头结点
    
        if (i < 1) return NULL; // i 无效,返回 null
    
        while (p && j < i) { // 从第一个结点开始查找,直到 i
            p = p->next; // 下一个结点指针
            j++;
    
        }
        if (j == i) {
            return p;
        } else {
            return NULL;
        }
    }
    
    /*
    按序号查找成功
    
    4
    */
    

    按值查找 LNode(L,2)

    
    LNode *LocateElem(LinkList L, ElemType e) {
        LNode * p = L->next;
        while (p != NULL && p->data != e) { // 从第一个结点开始查找 data 域为 e 的结点
            p = p->next;
        }
        return p;
    }
    /*
    按值查找成功
    
    2
    */
    

    删除 DeleElem(L, 2)

    
    LNode *DeleElem(LinkList L, int i) {
        LNode * p = GetElem(L, i - 1);
        LinkList q;
        q = p->next;
        p->next = q->next;
        free(q);
    }
    
    

    相关文章

      网友评论

        本文标题:数据结构重学日记(九)单链表增删改查

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