第3章 链表及链式栈、链式队列
3.1 指针（Pointer）
1、什么是指针？
指针（Pointer）：变量的地址，通过它能找到以它为地址的内存单元。
例子：理解指针的概念，区分什么是地址（指针），什么是地址指向的值！
理解如何通过指针修改变量的值！
#include <bits/stdc++.h>
using namespace std;
int main(){
int x = 10;
//定义指针，指向x的地址 int *p = &x;
//p是int*类型的指针（整数的地址） cout<<p<<endl;
//*p不是地址，是p这个地址指向的值 cout<<*p<<endl;
*p = *p + 2;//修改指针指向的变量的值
cout<<p<<" "<<*p<<endl;
cout<<x<<endl;
//数组的本质是数组中下标为0的元素的地址 int arr[5] = {0};
cout<<&arr<<" "<<&arr[0]<<" "<<arr<<endl;
//采用scanf读入 int a,b; scanf("%d%d",&a,&b);
printf("a=%d\n",a); printf("b=%d\n",b); printf("%d+%d=%d\n",a,b,a+b);
return 0; }
问题：对比如下代码输出的结果，理解指针和普通变量的不同；
#include <bits/stdc++.h>
using namespace std;
int main(){
int x = 10; int y = x; y = y + 2; cout<<y<<endl<<x<<endl;
int *p = &x; *p = *p + 2; cout<<*p<<endl<<x<<endl;
int a = 10; int *p2 = &a;
cout<<p2<<" "<<a<<endl;
(*p2)++;//注意++的优先级高于*
cout<<p2<<" "<<a<<endl;
return 0; }
例子：*p++和(*p)++的区别
int x = 10; int *p = &x; cout<<p<<endl<<x<<endl;
*p++; cout<<p<<endl<<x<<endl;
注意：上述代码并不能通过指针修改 x 的值，*p++相当于 p++是在对指针的值自增（相
当于地址值自增）。
2、结构体指针示例
例子：理解结构体指针的各种定义方法。
#include <bits/stdc++.h>
using namespace std;
struct stu{
char name[100];
double score;
};
int main(){
//定义结构体变量 struct stu s;
strcpy(s.name,"ZhangSan");
s.score = 99.99;
//输出结构体
cout<<s.name<<" "<<s.score<<endl;
//定义指针，指向结构体struct stu *stu = &s;//struct可以省略 stu *stu1 = &s;
//在结构体指针中，不能用.来指向结构体成员变量(stu是地址)
cout<<stu1->name<<" "<<stu1->score<<endl;
//(*stu)是结构体
cout<<(*stu1).name<<" "<<(*stu1).score<<endl;
//new结构体对象，直接赋值给一个指针 stu *stu2 = new stu; strcpy(stu2->name,"ZhangSan");
stu2->score = 99.8;
cout<<stu2->name<<" "<<stu2->score<<endl; delete stu2;//释放内存
//malloc结构体对象，直接赋值给一个指针 stu *stu3 = NULL;
stu3 = (stu*)malloc(sizeof(stu));
strcpy(stu3->name,"WangWu");
stu3->score = 98;
cout<<stu3->name<<" "<<stu3->score<<endl; free(stu3);//释放内存
return 0; }
注意：理解 malloc 和 free 函数的作用！
（1）malloc：动态内存分配，用于申请一块连续的指定大小的内存块区域并返回分配
的内存区域地址。
（2）free函数能释放某个动态分配的地址，表明不再使用这块动态分配的内存了，实
现把之前动态申请的内存返还给系统。
（3）如果结构体中有 string 类型的成员，那么不能使用 malloc 动态分配内存（可以
使用 new），这是因为 malloc/free 和 new/delete 的重要区别之一是：
new 会先调用 operator new 函数，申请足够的内存（通常底层使用 malloc 实现）。然
后调用类型的构造函数，初始化成员变量，最后返回自定义类型指针。delete 先调用析构
函数，然后调用 operator delete 函数释放内存（通常底层使用 free 实现）。
malloc/free是库函数，只能动态的申请和释放内存，无法强制要求其做自定义类型对
象构造和析构工作。
所以 string 的构造函数并没有被调用，name 没有被初始化，改为 new 能正常运行。
例子：通过函数输出结构体的 2 种方法示例
#include <bits/stdc++.h>
using namespace std;
struct stu {
string name;
double score;
};
void show(struct stu s) {
cout<<s.name<<" "<<s.score<<endl;
}
void show2(struct stu *s) {
cout<<s->name<<" "<<s->score<<endl;
}
int main() {
struct stu s;
s.name = "ZhangSan";
s.score = 99;
show(s);
stu *t = &s;
show2(t); return 0;
}
3.2 链表
1、链表介绍
（1）线性表的优点
A、无需为表示结点间的逻辑关系而增加额外的存储空间；
B、可方便地随机存取表中的任一元素。
（2）线性表的缺点
A、插入或删除平均需要移动一半的结点；
B、顺序表要求占用连续的存储空间；
问题：存储一个班同学的成绩（人数不确定），如何存储？
解决方法 1：定义尽可能长的数组来存储！
99 100 98 90 88 97 100 92 … 98
解决方法 2：利用链表来存储！
注意：链表结构并不一定占用连续的内存空间，其占用的内存空间可以不连续！
（3）链表的基本概念
A.结点(Node)组成
数据域 指针域
B.数据域：存储数据元素本身
C.指针域：存储邻接元素的存储地址(位置)
D.链接方式：
单链表：每个结点只有一个指针域。
双向链表：每个结点有两个指针域。
循环链表：是一个首尾相接的链表。
E.头指针 ：指向链表头结点的指针。
2、链表的基本操作
（1）要实现的基本操作：
add(int x)：在链表末尾追加元素（注意头结点）
insert(int n,int x)：在链表中插入一个元素（注意头结点）
deldata(int data)：删除链表中第一个出现的 data 的值（注意：如果 data 是头节点）
delpos(int n)：删除链表的第 n 个节点（注意如果 n==1，也就是删除头结点的情况）
display()：显示链表
（2）实现代码：
#include <bits/stdc++.h>
using namespace std;
//结点定义
struct Node{
int data;
struct Node *next;
};
//头结点
Node *head = NULL;
//在链表末尾追加
void add(int x){
//如果有 head的值
if(head != NULL){
//要追加的节点
Node *a = new Node;
a->data = x;
a->next = NULL;
Node *p = head;
//移动到最后一个节点
while(p->next != NULL){
p = p->next;
}
p->next = a;
}else{
head = new Node;
head->data = x;
head->next = NULL;
}
}
//在中间追加元素（在第 n个元素的位置）
void insert(int n,int x){
//新节点
Node *d = new Node;
d->data = x;
d->next = NULL;
//如果是头结点
if(n == 1){
d->next = head;
head = d;
}else{
int i;
Node *p = head;
for(i = 1;i <= n - 2;i++){
p = p->next;
if(p == NULL){
break;
} }
if(p == NULL){
cout<<"n有误"<<endl;
}else{
d->next = p->next;
p->next = d;
}
} }
//删除链表中第一个出现的 data
void deldata(int data){
Node *p = head,*pre = NULL;
while(p != NULL){
if(data == p->data){
if(p == head){
head = p->next; }else{
pre->next = p->next;
}
delete p;
break;
}
pre = p;
p = p->next; }
}