数据结构学习笔记

数据结构——链表（Linked List）

1. 关于链表

• 链表与数组的区别

• 链表：由n段不连续的内存组成，又称一段内存又称一个节点，每个节点存放数据和下一个节点的地址

2. 链表的C++实现

#include<iostream>
using namespace std;
struct Node{
    int data;
    struct Node*next;
};//一个节点包含两个元素，一个是节点储存的数据，一个是下一个节点的地址
struct Node*head;//定义一个头节点的指针
void Insert(int x){//Insert函数：在链表前端插入节点
    struct Node*temp=new Node();//为temp开辟一个内存空间
    temp->data=x;
    temp->next=NULL;
    if(head!=NULL)
        temp->next=head;//将temp节点的地址赋值为head的地址
    head=temp;//将头节点地址更新为temp的地址
}
void Print(){//Print函数：打印当前链表的全部节点数据
    struct Node*temp=head;
    cout<<"List is ";
    while(temp!=NULL){//temp=NULL说明遍历到了尾部节点
       cout<<temp->data;//输出当前节点的数据
       temp=temp->next;//地址变为后一个节点的地址
    }
    cout<<endl;
}
int main(){
    head=NULL;//empty list
    cout<<"How many numbers"<<endl;
    int n,i,x;
    cin>>n;
    for(i=0;i<n;i++){
        cout<<"Enter the number"<<endl;
        cin>>x;
        Insert(x);
        Print();
    }
    return 0;
}

输出结果：