C语言实现链表基本操作

「爱情、让人受尽委屈。」 2022-06-16 23:45 189阅读 0赞

# C语言实现链表基本操作 #

--------------------

之前说过顺序表的基本操作。显然，顺序表有一个很大的缺点，就是做插入删除操作的时候，往往要做很大量的元素移动的操作。这里我们讨论另外一种线性表的表示方法——链式存储结构。由于它不需要逻辑上的相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具有的弱点，但是同时也失去了顺序表的可随机存取的有点。

--------------------

*  结构

#include <stdio.h>
    #include <stdlib.h>
    typedef int ElemType;      //数据元素的类型，假设是int型的
    
    typedef struct LNode{
        ElemType    data;   //数据域
        struct LNode *next; //下一个节点的指针
    }LNode, *LinkList;

*  创建链表

//创建链表
    void createList(LinkList &L,int n)
    {
        L = (LinkList)malloc(sizeof(ElemType));
        L->next = NULL; //创建头节点
    
        LinkList p,q;
        q = L;
        for(int i=0;i<n;i++)
        {
            p = (LinkList)malloc(sizeof(LNode)); //一个新的节点
            printf("请输入值");
            scanf("%d",&p->data);
            p->next = NULL;
            q->next = p;
            q = q->next;
        }
    }

*  遍历输出链表

//遍历输出链表
    void toString(LinkList L)
    {
        LinkList p;
        p = L->next;
        printf("Head->");
        while(p)
        {
            printf("%d->",p->data);
            p = p->next;
        }
        printf("NULL\n");
    }

*  插入一个元素

int LinkListInsert(LinkList L,int i,ElemType e)
    {
        LinkList p = L;
        int j=0;
        while(p && j<i-1)
        {
            p = p->next;
            j++;
        }
    
        if(!p||j>i-1)
        {
            printf("给出的位置错误");
            return -1;
        }
    
        LinkList s = (LinkList)malloc(sizeof(LNode));
        s->data = e;
        s->next = p->next;
        p->next = s;
        return 1;
    }

*  删除一个元素

//删除一个元素
    int LinkListDelete(LinkList L,int i,ElemType &e)
    {
        LinkList p = L;
        int j=0;
        while(p && j<i-1)
        {
            p = p->next;
            j++;
        }
    
        if(!p||!(p->next)||j>i-1)
        {
            printf("给出的位置错误");
            return -1;
        }
    
        LinkList s = p->next;
    
        p->next = s->next;
    
        return 1;
    }

*  主函数

int main()
    {
        int n ;
        LinkList L;
        printf("请输入n\n");
        scanf("%d",&n);
        createList(L,n);
        toString(L);
        LinkListInsert(L,5,9);
        toString(L);
        int e;
        LinkListDelete(L,6,e);
        toString(L);
    }

*  测试结果

![测试结果][SouthEast]

[SouthEast]: /images/20220617/923b36fb7308477cb5c12a5f6a1675dc.png