一步一步写数据结构（链表）

从现在开始认真一步一步的写数据结构，今天先写链表。

链表整体来说难度较低，关键点在于链表的创建，难点是两个指针如何“合作”不断生成新节点。

代码如下，使用的c++类来创建链表，类里包括创建，修改，删除，插入，显示几个成员方法，还有一个成员变量，即指向链表表头的头指针。

#include <iostream>
using namespace std;

//定义节点结构体
struct node
{
    int value;
    node * next;
};


//利用尾插法建立链表元素

node* createList()
{
    //用到的变量
    node *p_new=NULL;
    node *p_old=NULL;
    int n;
    //建立尾结点
    cin>>n;
    node *head=new node;
    head->value=n;
    head->next=NULL;

    //循环建立后续节点
    p_old=head;
    while(cin>>n){
        p_new=new node;
        p_new->value=n;
        p_new->next=p_old;
        p_old=p_new;
    }
    return p_new;

}
//头插法建立链表
node* createFromHead()
{
    int n;
    node * p_old=NULL;
    node * p_new=NULL;
    cin>>n;
    node *head=new node;
    head->value=n;
    p_old=head;
    while (cin>>n) {
        p_new=new node;
        p_new->value=n;
        p_old->next=p_new;
        p_old=p_new;
    }
    return head;
}

//翻转链表

node * reverseList(node * p)
{
    node * p1,*p2,*temp;
    p1=p;
    p2=p1->next;
    p1->next=NULL;
    while(p2)
    {
        temp=p2;
        p2=p2->next;
        temp->next=p1;
        p1=temp;
    }
   return p1;
}
//打印链表
void printlist(node * head)
{
    node *p=head;
    if(head==NULL)
    {
        cout<<"链表为空"<<endl;
    }else
    cout<<"链表内容为：";
    {
        while(p)
        {
            cout<<p->value<<" ";
            p=p->next;
        }
    }
}

int main() {
    node * test=createList();
    node * rtest=reverseList(test);
    printlist(rtest);
    return 0;
}

控制台运行结果如下，符合预期：

最后附一张链表头插法的示意图，画的比较粗糙，主要为了说明下思路：

下面补充一段头插法的建立链表的代码：

1 #include <iostream>
 2 using namespace std;
 3 
 4 //定义节点结构体
 5 struct node
 6 {
 7     int value;
 8     node * next;
 9 };
10 
11 
12 //利用尾插法建立链表元素
13 
14 node* createList()
15 {
16     //用到的变量
17     node *p_new=NULL;
18     node *p_old=NULL;
19     int n;
20     //建立尾结点
21     cin>>n;
22     node *head=new node;
23     head->value=n;
24     head->next=NULL;
25     
26     //循环建立后续节点
27     p_old=head;
28     while(cin>>n){
29         p_new=new node;
30         p_new->value=n;
31         p_new->next=p_old;
32         p_old=p_new;
33     }
34     return p_new;
35     
36 }
37 //头插法建立链表
38 node* createFromHead()
39 {
40     int n;
41     node * p_old=NULL;
42     node * p_new=NULL;
43     cin>>n;
44     node *head=new node;
45     head->value=n;
46     p_old=head;
47     while (cin>>n) {
48         p_new=new node;
49         p_new->value=n;
50         p_old->next=p_new;
51         p_old=p_new;
52     }
53     return head;
54 }
55 //打印链表
56 void printlist(node * head)
57 {
58     node *p=head;
59     if(head==NULL)
60     {
61         cout<<"链表为空"<<endl;
62     }else
63     cout<<"链表内容为：";
64     {
65         while(p)
66         {
67             cout<<p->value<<" ";
68             p=p->next;
69         }
70     }
71 }
72 
73 int main() {
74     printlist(createFromHead());
75     return 0;
76 }

原文链接: https://www.cnblogs.com/jymblog/p/5416657.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍