单链表

节点

链表的数据节点是一个结构体

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

成员next是指向结构体类型自身的指针(开始我也不理解为什么要这样定义,现在想明白了,指针要有个数据类型,但节点中的指针是指向下一节点的,所以数据类型就是定义的node类型。(结构体类型也属于数据类型)

单链表操作

#include<iostream>
Using namespace std;

//定义一个结构体类型Node
Struct Node
{
    int data; //数据域
    Node *next; //节点类型的指针域
};

Node *L; //定义一个全局类型的节点指针变量L,作为头指针
int length; //定义全局类型的单链表长度变量length

void CreateList(Node *head) //后插法创建单链表
{
    Node *tail,*p; //定义尾指针tail,指针p
    head->next = NULL; //头结点初始化
    tail = head; //尾指针初始化,指向头结点

    for (int i = 0; i < length; i++)
    {
        p = new Node;
        cout <<"请输入一个整型数据: " ;
        cin >> p->data;
        tail->next = p; //新节点插入到尾节点的后面
        tail = p; //尾指针指向新节点
    }
    tail->next = NULL; //尾节点指针域置空,表名链表结束
    cout <<"创建成功!"<< endl;
}

int Insert(Node *head) //插入节点
{
    int position; //插入的位置
    int j = 0;

    Node *p = head; //定义节点指针p指向头结点

    Node *nnode; //生成新节点
    nnode = new Node; //分配存储空间
    cout <<"请输入需要插入的值: ";
    cin >> nnode->data;
    cout <<"请输入需要插入到的位置: ";
    cin >> position;

    if (position > length + 1 || position < 1) //如果插入的位置大于总长度+1或小于1,则结束程序
    {
        cout <<"插入的位置不合法!"<< endl;
        return 0;
    }

    while (j < position - 1) //p先指向positon-1的节点循环position-1次
    {
        p = p->next;//第一次循环时指向第一个节点(首元结点),第二次循环时指向第二个节点...
        j++;
    }

    nnode->next = p->next; //设置插入的节点的指针域
    p->next = nnode; //设置插入节点前的指针域

    length += 1; //链表长度增加一

    cout <<"插入成功!"<< endl;

}

int Remove(Node *head) //删除节点
{
    int position; //要删除的位置
    int j = 0;
    Node *p = head; //定义节点指针p指向头结点

    cout <<"请输入需要删除的位置: ";
    cin >> position;

    if (position > length || position < 1 || length == 0)
        //如果删除的位置大于总长度或小于1,则结束程序(若链表长度为0,则删除任何位置都不合法)
    {
        cout <<"删除的位置不合法!"<< endl;
        return 0;
    }

    while (j < position - 1) //p先指向positon-1的节点
    {
        p = p->next;
        j++;
    }

    Node *q = p->next; //p保存待删除节点的地址
    p->next = q->next; //修改待删除节点前一个节点的指针域
    delete q; //释放q

    length -= 1; //表长减一

    cout <<"删除成功!"<< endl;

}

void Display(Node *head) //输出单链表
{
    int i = 1;
    Node *p = head->next;//定义节点指针p指向首元结点
    while (p) //指针p不为空
    {
        cout <<"第"<< i <<"个元素为: "<< p->data << endl;
        p = p->next;
        i++;
    }
}

void Length()
{
    cout <<"单链表的长度为:"<< length << endl;
}

int Clear(Node *head)
{
    Node *p,*q;//p用于指向下一节点,q用于保存当前待删除节点地址
    p = head->next; //p指向首元结点

    if (head->next == NULL) //若单链表已经为空,则不必再次进行清空操作
    {
        cout <<"单链表已为空!"<< endl;
        return 0;
    }

    while (p)
    {
        q = p; //保存p指向的节点地址,以便清空
        p = p->next; //指向下一节点
        delete q; //删除保存的节点地址
    }
    head->next = NULL; //头结点指向NULL
    length = 0; //单链表长度设为0
    cout <<"清空成功!"<< endl; 
}

int Modify(Node *head)
{
    Node *p = head;
    int j = 0;
    int position, value;
    cout <<"请输入需要修改的位置: ";
    cin >> position;

    if (position > length || position < 1 || length == 0)
    {
        cout <<"输入的位置不合法!"<< endl;
        return 0;
    }

    cout <<"请输入需要修改的值: ";
    cin >> value;

    while (j<position-1)
    {
        p = p->next;
        j++;
    }

    p->next->data = value;
    cout <<"修改成功!"<< endl;

}

int Search(Node *head)
{
    Node *p = head;
    int j = 0;
    int position;
    cout <<"请输入需要查找的位置: ";
    cin >> position;

    if (position<1 || position>length || length == 0)
    {
        cout <<"位置不合法!"<< endl;
        return 0;
    }

    while (j < position - 1)
    {
        p = p->next;
        j++;
    }

    cout <<"位置为"<< position <<"的元素值为: "<< p->next->data << endl;
}

int main()
{
    int options=5;
    cout <<"请输入单链表的长度: ";
    cin >> length;

    L = newNode; //初始化头指针

    CreateList(L); //创建单链表

    while (options != 0)
    {
        cout <<"===================="<< endl;
        cout <<"请输入需要进行的操作,回复数字序号"<< endl;
        cout <<"0.退出操作    1.插入节点    2.删除节点    3.输出所有数据"<< endl;
        cout <<"4.输出长度    5.清空链表    6.修改元素    7.查找元素"<< endl;
        cout <<"===================="<< endl;

        cin >> options;

        if (options == 0)
        {
        cout <<"程序已退出"<< endl;
        }
        else if (options == 1) 
        {
            Insert(L); //插入新节点
        }
        else if (options == 2) 
        {
            Remove(L); //删除节点
        }
        else if (options == 3)
        {
            Display(L); //输出单链表中的数据
        }
        else if (options == 4)
        {
            Length(); //输出单链表的长度
        }
        else if (options == 5)
        {
            Clear(L); //清空单链表
        }
        else if (options == 6)
        {
            Modify(L); //修改元素
        }
        else if (options == 7)
        {
            Search(L); //查找元素
        }

        else
        {
            cout <<"输入的操作序号错误!请重新输入"<< endl;
        }
    }

    system("pause");
    return 0;

}

总结

1.要先判断插入、删除位置是否合法在执行插入、删除操作,即要先将判断代码写到执行代码前面

2.在函数中直接cout,并且无return,即可定义函数为void;若有return 0 或return 1,则要定义函数类型为int型
若要定义返回值为node类型的指针,可以这样定义:

node *函数名(参数表)
{

}

3.为了操作方便,我定义了:

全局变量头指针L:若插入节点后进行删除节点,那么在删除的时候的链表要存有刚插入的节点;

定义全局变量头指针L,则函数执行后修改了全局变量链表L,则函数调用时的链表为最新链表

链表长度length:进行添加删除节点时直接进行加减1;输出链表长度时不需遍历,直接输出length

4.指针变量在定义后,其值是随机的。也就是说该指针变量可能指向内存中某个不确定的内存单元。使用未初始化的指针变量是不安全的,可能会出现难以预料的后果,甚至使系统瘫痪。因此

定义的指针必须先初始化后才可使用

如上述代码声明头指针L,但声明后不能直接传递参数给函数使用,要先分配存储空间

5.删除节点时除了要判断删除的位置是否小于1或者大于表长,还要注意判断此时链表是否为空

6.插入和删除节点相同点:

都需要插入/删除的输入位置;   
都需要判断插入/删除的位置是否合法;   
都要先找到待插入/删除的位置之前的节点位置

7.删除节点时要先将待删除的节点位置保存在一个指针里

8.

while(p) //p为指针变量
{

}

意思即为

while(p!=NULL)
{

}