单链表的基本操作

存储结构

线性表的链式存储结构特点是用一种任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。这就意味这些数据元素可以存在内存未被占用的任意位置。 

优点:不要求大片连续空间,改变容量方便
缺点:不可随机存取,要耗费一定空间存放指针,存储密度小

顺序表和链表的时间复杂度的比较

名称访问查找插入删除
数组O(1)O(n)O(n)O(n)
有序数组O(1)O(logN)O(n)O(n)
链表O(n)O(n)O(1)O(1)
有序链表O(n)O(n)O(n)O(n)

*这里的链表插入删除时间复杂度是在已知该节点的前驱节点的情况下

#include <stdio.h>
#include <stdlib.h>
//链表中节点的结构
typedef struct link {
    int  elem;
    struct link* next;
    int length;
}Link;
Link* initLink() {
    int i = 0;
    //1、创建头指针
    Link* p = NULL;
    //2、创建头结点
    Link* temp = (Link*)malloc(sizeof(Link));
    temp->elem = 0;
    temp->next = NULL;
    //头指针指向头结点
    p = temp;
    //3、每创建一个结点,都令其直接前驱结点的指针指向它
    while (1) {
        //创建一个结点
        Link* a = (Link*)malloc(sizeof(Link));
        scanf("%d", &i);
        if(i == -99) {
            return p;
        }
        a->elem = i;
        a->next = NULL;
        //每次 temp 指向的结点就是 a 的直接前驱结点
        temp->next = a;
        //temp指向下一个结点(也就是a),为下次添加结点做准备
        temp = temp->next;
        p->length++;
    }
    return p;
}
//p为链表,elem为目标元素,add为要插入的位置
void insertElem(Link* p, int elem, int add) {
    int i;
    Link* c = NULL;
    Link* temp = p;//创建临时结点temp
    //首先找到要插入位置的上一个结点
    for (i = 1; i < add; i++) {
        temp = temp->next;
        if (temp == NULL) {
            printf("插入位置无效\n");
            return;
        }
    }
    //创建插入结点c
    c = (Link*)malloc(sizeof(Link));
    c->elem = elem;
    //① 将新结点的 next 指针指向插入位置后的结点
    c->next = temp->next;
    //② 将插入位置前结点的 next 指针指向插入结点;
    temp->next = c;
    p->length++;
}
//p为原链表,elem 为要删除的目标元素
int delElem(Link* p, int elem) {
    Link* del = NULL, *temp = p;
    int find = 0;
    //1、找到目标元素的直接前驱结点
    while (temp->next) {
        if (temp->next->elem == elem) {
            find = 1;
            break;
        }
        temp = temp->next;
    }
    if (find == 0) {
        return -1;//删除失败
    }
    else
    {
        //标记要删除的结点
        del = temp->next;
        //2、将目标结点从链表上摘除
        temp->next = temp->next->next;
        //3、释放目标结点
        free(del);
        p->length--;
        return 1;
    }
}
//p为原链表,elem表示被查找元素
int selectElem(Link* p, int elem) {
    int i = 1;
    //带头结点,p 指向首元结点
    p = p->next;
    while (p) {
        if (p->elem == elem) {
            return i;
        }
        p = p->next;
        i++;
    }
    return -1;//返回-1,表示未找到
}
//p 为有头结点的链表,oldElem 为旧元素,newElem 为新元素
int amendElem(Link* p, int oldElem, int newElem) {
    p = p->next;
    while (p) {
        if (p->elem == oldElem) {
            p->elem = newElem;
            return 1;
        }
        p = p->next;
    }
    return -1;
}
//输出链表中各个结点的元素
void display(Link* p) {
    p = p->next;
    while (p) {
        printf("%d ", p->elem);
        p = p->next;
    }
    printf("\n");
}
//释放链表
void Link_free(Link* p) {
    p->length=0;
    Link* fr = NULL;
    while (p->next)
    {
        fr = p->next;
        p->next = p->next->next;
        free(fr);
    }
    free(p);
}
int main() {
    Link* p = initLink();
    printf("初始化链表为:\n");
    display(p);
    printf("在第 3 的位置上添加元素 6:\n");
    insertElem(p, 6, 3);
    display(p);
    printf("删除元素4:\n");
    delElem(p, 6);
    display(p);
    printf("查找元素 2:\n");
    printf("元素 2 的位置为:%d\n", selectElem(p, 2));
    printf("更改元素 1 的值为 6:\n");
    amendElem(p, 1, 6);
    display(p);
    Link_free(p);
    return 0;
}
点赞

发表回复

电子邮件地址不会被公开。必填项已用 * 标注