单链表插入删除完整版

#include<iostream>

#include<iomanip>

using namespace std;

//c++中默认的格式，在iomanip这个头文件中，io表示输出，manip是manipulator(操纵器)的缩写(在c++中只能通过输入缩写才有效))

typedef struct Lnode

{

    int data;

    Lnode *next;

}Lnode,*Linklist;//相当于typedef struct Lnode Lnode与typedef struct Lnode *Linklist两条语句，且结点中数据是整形，指针是结点类型。

void createlist(Linklist &L,int n)//对头指针L使用引用，无需return直接可以返回L的值，还有一个形参n用来接收用户传来的值

{

    L=new Lnode();//申请一个结点的内存空间并且让头指针L指向它

    L->next=NULL;//头指针指向的指针域为空

    cout<<"输入该表的数据："<<endl;//当主函数调用该函数时，执行到此是会输出这几个汉字

    for(int i=1;i<=n;i++)//使用一个for循环，逐个插入数据

    {

        Linklist p=new Lnode;//申请一个结点空间并且用结点型指针变量p指向它

        cin>>p->data;//用户输入数据传到结点的数据域中

        p->next=L->next;//把头结点后面一个结点的地址传到刚申请结点的指针域中，即把刚申请的结点指向紧邻着头结点的下一个结点。使用的是前插法

        L->next=p;//把刚创建结点的地址放到首结点的地址域中

    }

}

void displist(Linklist L)//这个函数的主要作用是把刚才使用前插法创建的单链表输出

{

    Linklist p=L->next;//定义一个指针变量p，并且它指向单链表L的首元结点

    while(p)//当p所指向的结点不是NULL的时候则执行下面的循环

    {

        cout<<"->"<<p->data;//当执行这个循环的时候每循环一次要输出->和p所指向的数据

        p=p->next;//p指向下一个结点。

    }//执行完一次循环之后会输出一个->和一个结点中的数据，以及p会指向下一个结点则在输出最后一个结点的数据之后，p所指向的为NULL，循环结束。

}

bool listinsert(Linklist &L,int i,int e)//bool型说明在函数调用这个函数之后的返回值要么是true,要么是false.括号中的都是形参，头指针L采用了引用，整型变量i和e用来接收用户传来的数据。

{

    Linklist p=L;int j=0;//定义了结点型指针变量p，并且与L的指向相同，它们两个同时指向头结点。并且定义整形变量j的值等于0.

    while(p&&j<i-1)//在这里while循环的条件是结点型指着变量所指向的结点不为空的时候并且j小于i-1的时候循环继续执行。这个循环的目的是为了将结点型指针变量p指向第i-1结点的位置。

    {

        p=p->next;//循环进来以后首先将p指向p的下一个结点。

        j++;//j的值自增1.

    }//这个循环的目的就是让p和j一齐后移增大。不断地靠近条件的边界。

if(!p||j>i-1)//这个if语句的判断条件是如果p指向的结点为空或者j大于i-1的值，这两个条件有一个满足就会执行该if语句。

{

    cout<<"i is error!";//如果i的值是负数，或者i-1的值大于单链表的长度，即都是用户输入i值得错误将会导致插入失败。会提醒i is error!

    return false;

}//该if语句的主要作用就是为了给出来一个信号以及使算法的健壮性得以体现。如果i的值用户输入了-1则会提醒出错了。如果p的值为空了同样也会输出去i的值是错误的。p指向的结点为空表示p已经指向表尾了还没指向i-1的位置。说明i-1的值过大。j>i-1说明用户输入i的值是负数。

Linklist s=new Lnode();//在i的值既不是负数又部超出链表的长度范围时即开始执行以下操作。申请一个新的结点空间并用结点型指针变量s指向它。

s->data=e;//刚申请新结点的数据域为e

s->next=p->next;//由于p指向的是i-1的结点，则p指向的下一个结点是i的结点。即把i的结点位置放到新结点的指针域内。即将要插入的结点指向第i个结点。

p->next=s;//把新结点的位置放到第i-1个结点的指针域内。即第i-1个结点指向将要插入的新结点s

return true;//在这一切完成以后返回true,说明插入成功，插入失败则是因为i的原因。

}

bool listdelete(Linklist &L,int m)//创建一个删除结点的函数，用于删除指定的结点

{

    Linklist p=L;int j=0;//定义一个结点型指针变量p指向头结点，并且定义一个整形变量j等于0.

    while(p&&j<m-1)//引进一个while循环，循环的判断条件是p不为空，以及j的值要小于i-1这样循环才会继续执行下去。

    {

        p=p->next;//无论实在插入函数或是删除函数中，一进入while循环，结点型指针变量p就指向下一个结点。这是因为单向链表只能对后面的结点进行操作，所以每次只能寻找到i-1项。

        j++;//在插入和删除操作中while循环的作用都是为了使结点型指针变量p指向第i-1个结点。

    }

    if(!p||j>m-1)//if语句的判断条件是p的值非空或者输入i的值为负数

    {

        cout<<"i is error!";//如果该if语句成立，说明要么p指向结点的值为空，这时说明i-1的值大于该单链表的长度即用户输入的i值过大，如果j>i-1成立说明用户输入i的值为负数。

        return false;

    }//总的来说，在插入删除操作中前两步操作调用while循环以及if循环语句都是相同的，看看用户传来的i值是否符合这个单链表，而且他们的作用都是为了使结点型指针变量p指向第i-1个结点。

    Linklist q=p->next;//目的是删除第i个结点，先定义一个结点型指针变量q指向第i个结点,即保存第i个结点的地址。

    p->next=q->next;//由于q的下一个结点是第i+1个结点，放在左边的p->next表示把右边的地址当道p的指针域中，由于p指向的是第i-1个结点，即把第i+1个结点的地址放到第i-1的指针域中，最终目的使第i-1的结点指向i+1;

    delete q;//删除q指向的结点，即删除第i个结点。当结点型指针变量单个出现时表示的是这个指针所指向的结点。

    return true;//如果执行到这一步说明删除操作已经结束，返回给操作者一个正确的回应true.

}

int main()//主函数，后面没有冒号，没有返回值

{

    int n; Linklist L;//定义一个整形变量n，以及一个结点型指针变量L，也就是头指针。

    cout<<"请输入链表的长度："<<endl;//编译后会输出“请输入链表的长度这句话”，但cin却看不到

    cin>>n;//从键盘输入n的值。

    createlist(L, n);//调用函数就更加简单了，直接把函数名以及后面的形参列表复制过来，删去形参的类型即可。

    displist(L);//先创建单链表，后输出单链表

    int i,e;

    cout<<"请输入插入的位置和数值："<<endl;

    cin>>i>>e;

    listinsert(L, i, e);

    displist(L);//在调用函数之前要在主函数中先定义函数中需要用到的变量，并且用cout输出,接下来用cin从键盘中输入刚才定义变量的值。

    int m;

    cout<<"请输入删除的位置：";

    cin>>m;

    listdelete(L,m);

     displist(L);

}