链表的指针实现
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;
}