双向链表的建立

我发现,链表真的是一个很神奇的东西,它非常有用。是许多算法的基础。

今天突然想到为什么链表只有一个方向。为什么不能倒着输出数据。原谅我以前还真不知道有双向链表东东。

我们假设有3个学生,学号分别为1,2,3;

我们最初学的链表是这样的,

额,我习惯以一个负无穷为链表的头节点…

可能是学跳跃表时的习惯吧,怕加入的数小于头节点…

然后我们建立链表的方式是这样的:

结构体是这样写的:

struct stu
{
    int num;
    struct stu *next;
};

完整代码:n为学生个数

#include <iostream>
#include <stdlib.h>
using namespace std;
struct stu
{
    int num;
    struct stu *next;
};
void show(struct stu *q)
{
    while(q->next!=NULL)
    {
        cout<<q->next->num<<" ";
        q=q->next;
    }
    cout<<endl;
}
int main()
{
    struct stu *p,*q;
    int n;
    while(cin>>n)
    {
        p=(struct stu *)malloc(sizeof(struct stu));
        q=p;
        p->num=-999999;
        for(int i=0;i<n;i++)
        {
            p->next=(struct stu *)malloc(sizeof(struct stu));
            p=p->next;
            cin>>p->num;
        }
        p->next=NULL;
        show(q);
    }
}

然后双向链表怎么写呢?
看看双向链表的结构:

只是多了一个结构体元素而已,而已

于是我们可以在结构体里加一条:

struct stu
{
    struct stu *last;
    int num;
    struct stu *next;
};

指针last储存上一个元素的地址。
然后在代码中可以增加一个指针t,记录上一个元素。把t赋给这个元素的last,就可以了。

代码:

#include <iostream>
#include <stdlib.h>
using namespace std;
struct stu
{
    struct stu *last;
    int num;
    struct stu *next;
};
void show1(struct stu *q)
{
    while(q->next!=NULL)
    {
        cout<<q->next->num<<" ";
        q=q->next;
    }
    cout<<endl;
}
void show2(struct stu *k)
{
    while(k->last!=NULL)
    {
        cout<<k->num<<" ";
        k=k->last;
    }
    cout<<endl;
}
int main()
{
    int n;
    struct stu *p,*q,*t,*k;
    while(cin>>n)
    {
       p=(struct stu *)malloc(sizeof(struct stu));
       q=p;
       p->last=NULL;
       p->num=-99999;
       for(int i=0;i<n;i++)
       {
           t=p;
           p->next=(struct stu *)malloc(sizeof(struct stu));
           p=p->next;
           p->last=t;
           cin>>p->num;
       }
       p->next=NULL;
       k=p;
       show1(q);
       show2(k);
    }
    return 0;
}

运行后结果是这样的:
input:

6
5 6 2 3 1 2

output:

5 6 2 3 1 2
2 1 3 2 6 5

很酷吧?

链表真是个很神奇的东西!

加油!

0

Leave a Reply

Your email address will not be published.