链表常见操作

7.3.1 链表的概念
1、链表的结构

struct node{
    typename data;  //数据域
    node* next ;    //指针域
};

又分为带头结点和不带头结点，头结点一般称为head,data不存放任何内容，next指向第一个数据域有内容的东西

7.3.2使用malloc函数或new运算符为节点分配内存空间

1、使用malloc函数或new运算符为链表节点分配空间（推荐用new)
(1)maloc是c语言中stdlib.h用于申请动态内存的函数，返回类型是申请void类型的指针，参数是size_t，所以需要sizeof(int)之类的，然后再强制转换
申请失败返回空指针null
一般不会失败，申请太大以及无限申请的情况除外

2、new运算符
c++用来申请动态空间的运算符，返回类型同样是申请的同变量类型的指针；
写法：int *p = new int; 即 new + 类型名；
如果失败会启动异常机制，而不是返回NULL，同样，失败可能是申请太大空间

3、内存泄漏
（1）free(p) 同样在stdlib.h头文件下
实现两个效果：将指针变量p所指空间释放，同时将p指向Null

(2) delete(p)
实现效果与free一样

切记，必须成对出现，在一般考试例，分配的空间在程序结束时即被释放，并且内存大小一般够一道题使用，但是，从编程习惯上！一定要成对出现

4、链表的基本操作

1、创建链表

struct node{
    int date;
    node *next; // 指针域
};
记忆：三个指针，头指针，循环复制

//创建链表
void create(int array[]){
    node *p, *pre, *head;   //  pre保存当前节点的前驱节点，head为头结点
    head = new node;    //  创建头结点
    head->next = null;  //头结点不需要数据域，指针域置为null
    pre = head; //记录pre为head
    for(int i = 0;i < 5;i++){
        p = new head;   //创建节点
        //将array[i]赋值给新建的节点作为数据域，也可以scanf输入
        p -> data = array[i];
        p->next = null; //将新节点的指针域设置为null
        pre->next = p;  //前驱节点的指针域设为当前节点的地址
        p = pre;    //将pre设为p，作为下个节点的前驱节点
    }
    return head;    //返回头结点指针
}

2、查找元素

查找有多少个x
记忆：计算器+while循环

int search(node *head,int x){
    int count = 0;  //计数器
    node *p = head->next;   //从第一个节点开始
    while(p != null){   //只要没到链表结尾
        if(p->date == x){   //当前节点的数据域为x，则count++
            count++;
        }
        p = p->next；    //指针移动到下一个节点
    }
    return count;
}

3、插入元素
x插入第3个位置，其实就是插入完成后，第三个元素位置是x

记忆：head开始，for循环找前位，创节点，改指针

void insert(node *head, int pos,int x){
    node *p = head;
    for(int i = 0;i < pos - 1;++I){
        p = p->next;    //pos - 1是为了到前一个节点
    }
    node *q = new node;
    p->data = x;    //新节点的数据域为x
    q->next = p->next;  //新节点的下一个节点指向原先插入位置的节点
    p->next = q;    //前一个位置的节点指向新节点
}

4、删除元素
思想：
第一点，存前驱，while循环，改指针；（否则移）

void del(node* head, int x){
    node *p = head->next;   //从第一个结点开始
    node *pre = head;   //per始终保存p的前驱节点的指针
    while(p != null){
        if(p->data == x){
            pre->next = p->next;
            delete(p);
            p = pre->next;
        }else{
            pre = p;
            p = p->next;
        }
    }
}

7.3.4 静态链表
静态链表
struct Node{
    typename data;
    int next;   //指针域
}node;

注意：next是一个int型整数，存放下一个节点的地址
结构体类型名和结构体名字设成了不同，一般是可以相同的，但是有可能对他们排序，这时候相同sort就会编译错，所以不同

链表常见操作

推荐阅读更多精彩内容