By

文章目录 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
 //C++形式的链表的插入,遍历输出，链表倒序等操作
#include<iostream>
#include<stack>
using namespace std;
//节点类
class Node{
    public:
        int data;//节点有数据，还有指向下一个指针
        Node *next;
        Node(int _data){//显式构造函数，
            data=_data;
            next=NULL;
        }
};
class LinkList{
public:
    LinkList(){
        head=NULL;//显示构造函数，每次对新声明的链表类进行初始化，即表示创建一个新的“空”链表，只头指针，并且头指针值为NULL
    }
    void Insert(Node *node,int position);//成员函数
    void Output();
    void Delete(int position);
    void Revers();
private:
    Node *head;//设置为类的私有成员，只有通过类的成员函数才能访问
};
void LinkList::Insert(Node *node,int position){
    if(head==NULL){//链表为空，头节点指向这个插入节点
        head=node;
        return;
    }
    if(position==0){//插入的节点作为新的头节点
        node->next=head;
        head=node;
        return;
    }
    Node *current_node=head;
    int i=0;//从头开始遍历插入的位置
    for( ;current_node!=NULL&&i<position-1;i++)
        current_node=current_node->next;
    if(i==position-1){//找到插入位置的前一个
        node->next=current_node->next;
        current_node->next=node;

    }
}
void LinkList::Output(){
        if(head==NULL)
            return;
        Node* current_node=head;//从头开始遍历
        while(current_node!=NULL){
            cout<<current_node->data<<" ";
            current_node=current_node->next;
        }
        cout<<endl;
}
void LinkList::Delete(int position){
    if(head==NULL)
        return;
    Node *current=head;//从头遍历

    if(position==0){//s删掉头节点
        head=head->next;//下一个节点作为头指针
        delete current;
        return;
    }
    int i=0;//记录遍历过的位置
    while(current->next!=NULL && i<position-1){//找到删除位置的前一个
        current=current->next;
        i++;
    }
    if(i==position-1){
        Node* delete_node=current->next;//current代表的是删除位置的前一个
        current->next=current->next->next;
        delete delete_node;

    }
}
void LinkList::Revers(){//既然可以用栈，就可以改写成递归,但是链表是私有的所以不能改成递归
    stack<Node*> nodes;
    Node* current=head;
    while(current!=NULL){
        nodes.push(current);
        current=current->next;
    }
    while(!nodes.empty()){
        current=nodes.top();
        cout<<current->data<<" ";
        nodes.pop();
    }
 }
int main(void){
    LinkList link;
    for(int i=0;i<10;i++){
        Node* node=new Node(i);//为每个节点开辟一个空间,并赋值
        link.Insert(node,i);//插入
    }
    link.Output();
//    link.Delete(3);
//    link.Output();
    link.Revers();

    return 0;
}
文章目录