链表的指针实现

1.指针

#include<iostream>
using namespace std;
int main(){
	int a = 5;
	int *p; // int 型的指针
	double *q; //double 型的指针
	p = &a;// 
	cout << p 指向 a
	cout << *p << endl; //间接输出 a
	return 0;
}

2.申请动态内存（malloc）

#include<cstdio>
#include<cstdlib>
using namespace std;
int main(){
	int *p;
	p = (int *)malloc(sizeof(int)); //指针p 获取动态分配的空间内存地址
	*p = 5; // 在 p 指向的空间内存中存入 5
	cout << *p; // 输出 p 指向空间中的内容
	return 0;
}

3.链表

输入n 个数并以链表的格式存储

#include<iostream>
#include<cstdlib>
using namespace std; 
//保存一个链结，需要该链接的存储内容（例如int 型），还需要一个指针指向下一个结点
struct node {
    int data;
    struct node *next; // 同类型指针
};

int main(){
    struct node *head, *p, *q, *t;
    int i, n, a;
    cin >> n;
    head = NULL; // 先清空头指针
    for(int i = 1; i <= n; i++){ // 逐个输入n 链结的内容
        cin >> a; 
        p = (struct node *)malloc(sizeof(struct node)); // 用于输入当前链结
        p->data = a;//指针类型结构体成员调用 ->
        // int 型的内容
        p->next = NULL;//暂时指向空
        if(head == NULL) head = p; // 将头指针指向下一个链结
        else q->next = p; // 将上一个链结的指针指向该链结
        q = p; // q 中存储上一个 p链结中的信息
    }

    t = head; // 从链结的第一个位置开始遍历, head 相当于第一个 p
    while(t != NULL){// 直到链表为空，停止遍历
        cout << t->data << " ";
        t = t->next; // 更新为下一个链结
    }
    return 0;
}

链结的插入

    // 按升序插入一个数到链表中
    cin >> a;
    t = head;
    for(int i = 1; i <= n; i++){
        if(t == NULL || t -> next -> data > a) {
            p = (struct node *)malloc(struct node);
            p -> data = a;
            p -> next = t -> next;
            t -> next = p;
            break;
        }
        t = t -> next;
    }

完整代码

#include<iostream>
#include<cstdlib>
using namespace std; 

struct node {
    int data;
    struct node *next;
};

int main(){
    struct node *head, *p, *q, *t;
    int i, n, a;
    cin >> n;
    head = NULL;
    for(int i = 1; i <= n; i++){
        cin >> a;
        p = (struct node *)malloc(sizeof(struct node));// 每次申请一个动态空间存储一个链结信息
        p->data = a;//指针类型结构体成员调用
        p->next = NULL;
        if(head == NULL) head = p;
        else q->next = p; // 将上一个链结的指针指向该链结
        q = p; // q 中存储上一个 p链结中的信息    
    }

    // 按升序插入一个数到链表中
    cin >> a;
    t = head;
    for(int i = 1; i <= n; i++){
        if(t == NULL || t -> next -> data > a) {
            p = (struct node *)malloc(struct node);
            p -> data = a;
            p -> next = t -> next;
            t -> next = p;
            break;
        }
        t = t -> next;
    }

    // 输出全部
    t = head; // head 相当于第一个 p
    while(t != NULL){
        cout << t->data << " ";
        t = t->next;
    }

    return 0;
}

数组模拟链表

用data[ ]存储值，right[ ]存储下一个节点地址

#include<iostream>
using namespace std;

int main(){
    int data[101], right[101]; // 用两个数组，一个记录数据，另一个指向下一个节点
    int n, len, t;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> data[i];
        if(i != n) right[i] = i+1;
        else right[i] = 0;
    }
    len = n;

    len ++;
    cin >> data[len]; // 升序插入
    t = 1;
    while(t != 0){
        if(data[right[t]] > data[len]){
            right[len] = right[t];
            right[t] = len;
            break;
        }
        t = right[t];
    }

    // 输出全部
    t = 1;
    while(t != 0) {
        cout << data[t] << " ";
        t = right[t];
    }

    return 0;
}