c语言实现单链表建立，插入，删除，查找，循环链表，静态链表

旧城等待， 2022-06-09 00:07 185阅读 0赞

*  单链表结点结构

typedef struct LNode{
        ElemType data;
        struct LNode * next;
    }LNode, *LinkList;

*  元素插入  
    头插法，逆向建立单向链表，每次在头结点之后插入元素

LinkList CreateList1 (LinkList L){
        LinkList s;//链表元素指针
        int x;
        L = (LinkList)malloc(sizeof(LNode));  //不需要预先分配连续的内存空间
        L->next = NULL;
        scanf("%d", &x);
        while (x != 9999){
            s = (LinkList)malloc(sizeof(LNode));
            s->data = x;
            s->next = L->next;
            L->next = s;
            scanf("%d", &x);
        }
        return L;
    }

尾插法，从表头到表尾正向建立，每次在表尾插入元素

LinkList CreateList2 (LinkList L){
       //多了一个尾节点的指针
        LinkList s;//链表元素节点指针
        LinkList r;//尾节点指针
        int x;
        L = (LinkList)malloc(sizeof(LNode));
        r = L;//尾节点先指向头结点
        scanf("%d", &x);
        while (x != 9999){
            s = (LinkList)malloc(sizeof(LNode));
            s->data = x;
            r->next = s;
            r = s;
            scanf("%d", &x);
        }
        r->next = NULL;//别忘记最后一个指的是空指针，这样方便遍历
        return L;
    }

*  取出第i个位置的节点指针

LinkList GetElem(LinkList L, int i){
        int j = 1;
        LinkList p = L->next;//指向j=1对应的结点
        if(i < 1) return NULL;
        if(i == 0) return L;//在第一个位置插入元素就是在头结点后面插入
        while(p && j<i){
            p = p->next;
            j++;
        }
        return p;
    }

*  返回第一个为e的结点的指针

LinkList LocateElem(LinkList L, ElemType e){
        LinkList p = L->next;
        while(p && p->data != e){
            p = p->next;
        }
        return p;
    
    }

*  在第i的位置插入e元素

LinkList InsertElem(LinkList L, ElemType e, int i){
        if(i < 1) return NULL;
        LinkList s;
        s = (LinkList)malloc(sizeof(LNode));
        s->data = e;
        LinkList p = GetElem(L, i-1);
        s->next = p->next;
        p->next = s;
        return L;
    }

*  将i位置的元素删除

LinkList DeleteElem(LinkList L, int i){
        if(i < 1) return NULL;
        LinkList p = GetElem(L, i-1);
        LinkList q = GetElem(L, i);
        p->next = q->next;
        free(q);
        return L;
    }

*  除已知结点p，时间复杂度O(1)

void DeleteNode(LinkList p){  //p为已知结点，要求时间复杂度为1，因此减少查找
        LinkList q = p->next;
        p->data = q->data;
        p->next = q->next;
        free(q);
    }/*相当于删除后继节点，进行值的拷贝，这个思想需要注意*/

**双链表结点**

/*双链表结点*/
    typedef struct DNode{
        ElemType data;
        struct DNode *prior ,*next;
    }DNode, *DLinkList;

**静态链表结点**

typedef struct{
        ElemType data;
        int next;  //下一个元素的下标
    }SLinkList[MaxSize];