链表基本操作

链表基本操作

首先生成一个结构体，例如
struct node
{
int data;
node *link;
};

1、创建单链表

node *creat()       //创建单链表
{
    node *head, *p;
    head = new node;        //new一个
    p = head;       //防止指针头消失
    int x, cycle = 1;
    while(cycle)
    {
        cout << "Please input the data for single link" << endl;        //输入数据
        cin >> x;
        if(x!=0)
        {
            node *s = new node;     //新节点
            s->data = x;
            cout << "input data:" << x << endl;

            p->link = s;        //当前指针指向下一节点
            p = s;      //然后p变为下一节点
        }
        else
        {
            cout << "done" << endl;

            break;
        }
    }
    head = head->link;      //头指针与
    p->link = NULL;     //最后结点指向空
    return head;
}

2、打印链表

void print(node *head)      //打印单链表
{
    node *p = head;
    while(p != NULL)
    {
        cout << p->data << " ";
        p = p->link;
    }
}

3、删除指定结点

node *del(node *head, int num)      //删除结点
{
    node *p1, *p2;
    p2 = new node;
    p1 = head;
    while(num != p1->data && p1->link != NULL)      //寻找结点
    {
        p2 = p1;
        p1 = p1->link;
    }
    if(num == p1->data)
    {
        if(p1 == head)
        {
            head = p1->link;
            delete p1;
        }
        else
        {
            p2->link = p1->link;
            delete p1;
        }
    }
    else
    {
        cout << num << "could not been found in the current single linker!" << endl;
    }

    return head;
}

4、删除整个链表并释放空间

node *delAll(node *head)        //删除整个链表
{
    node *p = head;
    node *p1;

    while(p != NULL)
    {
        p1 = p->link;       //指向下一个
        delete p;       //删除当前结点
        p = p1;
    }
}

5、插入结点，头节点插入

node *insert(node *head)        //插入
{
    node *s = new node;
    node *p;
    cout << "Please input data" << endl;
    cin >> s->data;
    p = head;
    s->link = p->link;
    p->link = s;
}

6、查看链表长度

int length(node *link)//单链表测试长度
{
    node *p = link;     //将头节点赋予，防止头节点消失
    int count = 0;
    while(p != NULL)
    {
        p = p->link;
        count++;
    }
    return count;
}