线性表之单向链表

链表是物理存储结构上非连续，非顺序的存储结构，但是在逻辑上它是通过链表指针指向而实现的顺序结构

链表与数组的区别

· 数组是静态分布内存，链表是动态分布内存
· 数组在内存中是连续的，链表是不连续的
· 数组利用下表定位，查找的时间复杂度是O(1),链表通过遍历定位元素，查找的复杂度是O(n)
· 数组的插入和移除都需要移动其它元素，时间复杂度是O(n)，；链表的插入或删除不需要移动其它元素，时间复杂度是O(1)

数组的优点

· 随机访问性比较强
· 查找速度快

数组的缺点

· 插入和删除的效率低，需要移动其它元素
· 会造成内存的浪费，因为内存是连续的，所以在申请数组的时候就必须规定内存的大小，如果长度不合适就会照成内存的浪费
· 内存空间的要求高，创建一个数组，必须要有足够的连续内存空间
· 数组的大小是固定的，在创建数组的时候就已经规定好，不能够动态拓展

链表的优点

· 插入和删除的效率高，只需要改变指针的指向就可以进行插入和删除
· 内存利用效率高，不会浪费内存，可以使用内存中细小的不连续空间，只有在有需要的时候才去创建空间，大小不固定，拓展很灵活

链表的缺点

· 查找效率低，因为链表是从第一个节点向后遍历查找

图表演示

结构体构建单向链表

//结构体定义链表节点
typedef struct Listnode{
    int data;       //数据域
    ListNode *next; //后继指针
};

尾插法构建单向链表

//尾插法构建单向链表
struct Listnode* Creat_Listnode(){
    struct Listnode *head,*p,*q;
    head = NULL;
    int x;
    while(scanf("%d",&x) && x>0){
        p = (struct Listnode *)malloc(sizeof(struct Listnode));
        p->data = x;
        p->next = NULL;
        if(head == NULL)
            head = p;
        else
            q->next = p;
        q = p;
    }
    return head;
}

获取链表长度

//获取链表长度
int Length_Listnode(struct Listnode *head){
    int len = 0;
    struct Listnode *t;
    t = head;
    while(t != NULL){
        len++;
        t = t->next;
    }
    return len;
}

链表排序

//链表排序
void Sort_Listnode(struct Listnode *head){
    int len = Length_Listnode(head);
    if (len == 0)
        return;
    struct Listnode *p = head;
    int tmp;
    for (int i = 0; i<len-1; i++){         //冒泡排序的思想
        p = head;
        for (int j = 0; j < len-i-1; j++){
            if (p->data > p->next->data){
                tmp = p->data;
                p->data = p->next->data;
                p->next->data = tmp;
            }
            p = p->next;
        }
    }
}

链表插入节点

·主要头节点与尾节点

//顺序插入节点
struct Listnode* Insert_Listnode(struct Listnode *head, int x){
    struct Listnode *t,*p;
    t = head;
    p = (struct Listnode*)malloc(sizeof(struct Listnode));
    if(x < head->data){         //插入头节点
        p->data = head->data;
        p->next = head->next;
        head->data = x;
        head->next = p;
    }
    else{                   //非头节点插入
        while(t!=NULL){
            if(t->next==NULL || t->next->data >x){
                p->data=x;
                p->next=t->next;        //新增指针的后继指针指向当前后继指针指向的结点
                t->next=p;              //当前指针的后继指针指向当前指针
                break;                  //注意是否要跳出，跳出只删除符合的第一个数吗，不跳则删除所有符合的数
            }
            t=t->next;
        }
    }
    return head;
}

链表删除

·同样是要注意头和尾滴

//删除链表节点
struct Listnode* Delete_Listnode(struct Listnode *head, int x){
    struct Listnode *t,*p;
    t=head;
    if(head->data == x){       //头节点删除
        p = head->next;
        head->data = head->next->data;
        head->next = head->next->next;
        free(p);                //free()释放内存空间
    }
    else{                       //非头节点删除
        while(t != NULL){
            if(t->next->data == x){
                p = t->next;
                t->next = p->next;
               free(p);
                break;
            }
            t = t->next;
        }
    }
    return head;
}

链表打印

//打印链表
void Print_Listnode(struct Listnode *head){
    Listnode *t;
    t = head;
    if(t == NULL)       //判断链表为空
        printf("!链表为空!");
    else{               //顺序打印链表
        while(t != NULL){
            printf("%d ",t->data);
            t = t->next;
        }
    }
}

---

以上就是涉及到链表的所有操作，包括创建、排序、插入、删除、打印等，了解链表的思想，主要是要注意表头，表中和表位，以及地址的指向。emmmm,其实c++，Java应该是用面向对象的写法来写。什么，你没有对象，new一个就好了 //滑稽

完整的代码我就不贴了，略略略(主要是比较长，我都要哭了)