链表

今天的伪优先队列（仅供参考）

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e9+7;
const int INF = 0x3f3f3f3f;
const int inf = INT_MAX;

struct student{
    int height;
    struct student *next;
}*Head;///建立链表

struct student *insert_sort(struct student *Head,int idx)
{
     struct student *p = Head;
     struct student *q;///需要插入的
     ///q = new struct student;
     q = (struct student *)malloc(sizeof(struct student));///两种都可以
     q -> height = idx;
     if ( !Head ) Head = q;///考虑第一种情况  如果链表为空
     else{
        if (p->height >= idx)///考虑第二种情况  如果第一个就大于它，他就要被放到第一个
        {
            q->next = p;
            Head = q;
            return Head;
        }
        else
        {
            while (p->next)///直接向后面找出第一个大于它的数所在的地址
            {
                if (p->next->height >= idx)break;
                p = p->next;
            }
            if (!(p->next))p->next = q;///第三种情况，如果遍历到链表的最后，就直接尾插入  
            ///链表长度为1的情况也考虑在内
            else
            {
                q->next = p->next;
                p->next = q;
            }
        }
     }
    return Head;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);///关闭同步流
    Head = NULL;
    int n;
    cin>>n;
    for (int i=0;i<n;++i)
    {
         int x;
         cin>>x;
         Head = insert_sort(Head,x);
    }
    struct student *p = Head;
    while (p)
    {
        cout<<p->height<<' ';
        p = p->next;
    }
    cout<<endl;
    return 0;
}

按照之前迅哥所讲 我们所构建的链表应该是这样的

public:
    struct Node{
        int data;
        Node *next;
        Node (int a,Node *b):data(a),next(b){}
    };
public:
    Node *head;
    int size;
LinkedList::LinkedList(int value,,int n):head(0),size(n)
{
   head=new Node(0,0);
   Node *q=head;
   for(int i=0;i<n;++i)
   {
        q->next=new Node(value,0);
        q=q->next;
   }
}
LinkedList:: Node* LinkedList::advance(int pos)const
{
    Node *p=head;///由于最先的一个是空的表头，所以要从-1开始
    for (int i=-1;i<pos;++i)
    {
        p=p->next;
    }
    return p;
}

而这个Head是个空的头结点，但是这个空头结点等于new Node(0,0);所以它存在一个初地址，系统给他分配了一个内存，所以下列操作就是可以的

int a=3;
Head->next = &a;

#include<bits/stdc++.h>
using namespace std;
#define ll  long long
const int maxn=1e3+7;
inline int read()
{
    char c = getchar();
    int x = 0,fh = 0;
    while(c < '0' || c > '9'){fh |= c == '-';c = getchar();}
    while(c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}
    return fh?-x:x;
}
typedef struct student {
    int idx;
    struct student *next;
};
int  main()
{
    struct student *Head;
    Head = new struct student;
    int n,m;
    cin>>n>>m;
    struct student *p;
    p = new struct student;
    p = Head;
    p-> next = 0;
    struct student *q ;
    q = new struct student;
    q->idx=m;
    p->next = q;
    printf("%d",q->idx);
    return 0;
}

但是你发现数据结构老师所讲的

他的是

#include<bits/stdc++.h>
using namespace std;
#define ll  long long
const int maxn=1e3+7;
inline int read()
{
    char c = getchar();
    int x = 0,fh = 0;
    while(c < '0' || c > '9'){fh |= c == '-';c = getchar();}
    while(c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}
    return fh?-x:x;
}
typedef struct student {
    int idx;
    struct student *next;
};
int  main()
{
    int n; cin>>n;
    struct student *Head;
    Head = NULL;//头结点是空的
    struct student *p;
    p = new struct  student;
    p->idx = 0;
    Head = p;//现在把指针Head指向p
    struct student *q;
    q = new struct  student;
    q->idx = n;
    p->next = q;
    cout<<p->next->idx<<endl;
    return 0;
}

也就是他这个 头结点本身就是不存在分配的地址，是虚假的，然后把他指向第一个数据 也就是说Head就是和第一个共地址

迅哥的是单独一个地址Head->next的地址才是第一个地址

以下皆是错的

    Head = NULL;//头结点是空的
    struct student *p;
    p = new struct  student;
    p->idx = 0;
    Head ->next = p;/

此时的Head = NULL没有地址分配他的next也是空的，就不像迅哥那样new了一个地址，所以会指针越界

所以我们只要Head = new struct student

下列这个错误之处在于原本你想以Head为第一个存在的地址执行Head->next 但是Head = NULL；又被收回了这个地址

Head = new struct student;
Head = NULL；

 struct student *Head;
    Head = new struct student;
    Head = NULL；
    int n,m;
    cin>>n>>m;
    struct student *p;
    p = new struct student;
    p = Head;
    p-> next = 0;
    struct student *q ;
    q = new struct student;
    q->idx=m;
    p->next = q;
    printf("%d",q->idx);