指针,结构体,链表--C++数据结构与算法
指针
一、概念
指针是存储变量内存地址的变量。通过指针可以直接访问和操作内存中的数据。
指针本质上是地址。
指针的使用可以提高程序的效率和灵活性。
二、指针的声明与初始化
声明：需要指定指针指向的数据类型。例如，声明一个指向整型的指针：
int *ptr;
初始化:
int *ptr = NULL ;
注意：
指针变量不允许赋数值！
给指针变量赋值时不带 * ，给指针指向的变量赋值时带 *
三、指针的解引用
通过解引用操作符*可以访问指针指向的值：
int num = 10;
int *ptr = #
printf("%d", *ptr); // 输出10
需注意，指针声明时的 * 必须区别于解引用时的 * 。
指针声明时的* 没有别的作用，纯粹是声明该变量是指针变量。
解引用时的* 则有具体作用，表示指针指向的具体值。
四、指针的算术运算
指针支持加减运算，移动的步长取决于指针指向的数据类型大小。
例如，整型指针加1会移动4字节（假设int为4字节）：
int arr[3] = {1, 2, 3};
int *ptr = arr;
ptr++; // 指向arr[1]
五、指针与数组
数组名本身是一个指向数组首元素的指针。可以通过指针遍历数组：
int arr[3] = {1, 2, 3};
int *ptr = arr;
for (int i = 0; i < 3; i++) {
printf("%d ", *(ptr + i));
}
//scanf使用数组名,用数组名或指针访问数组。
#include
using namespace std;
int main ()
{
int a[5], i, *pa=a; //定义整型数组和指针,*pa=a可以在下一行pa=a;
for (i=0;i<5;i++)
scanf ("%d", a+i); //可写成pa+i和 &a[i]
for (i=0;i<5;i++)
printf("a[%d]=%d
",i,*(a+i)); //指针访问数组,可写成*(pa+i)或pa[i]或a[i]
return 0;
}
六、指针与函数
指针可以作为函数参数，实现传址调用：
void increment(int *num) {
(*num)++;
}
int main() {
int a = 5;
increment(&a);
printf("%d", a); // 输出6
return 0;
}
七、指针的安全性
使用指针时需注意空指针和野指针问题。未初始化的指针可能导致程序崩溃：
int *ptr; // 未初始化
*ptr = 10; // 未定义行为
八、指针的高级应用
指针可以用于实现复杂的数据结构，如链表和树：
struct Node {
int data;
struct Node *next;
};
struct Node *head = NULL;
结构体
一、概念
结构体（struct）一种用户自定义的数据类型，将不同类型的数据组合成一个整体。
结构体常用于表示具有多个属性的实体，例如学生信息、坐标点等。
定义结构体的语法如下：
struct StructName {
DataType1 member1;
DataType2 member2;
// 更多成员...
};
二、结构体的声明与初始化
声明结构体变量时可以用{ }直接初始化，也可以通过成员赋值的方式初始化。
struct Point {
int x;
int y;
};
// 直接初始化
Point p1 = {10, 20};
// 成员赋值初始化
Point p2;
p2.x = 30;
p2.y = 40;
三、嵌套
结构体可以嵌套其他结构体，形成更复杂的数据结构。
struct Address {
string city;
string street;
};
struct Person {
string name;
int age;
Address addr; // 嵌套结构体
};
四、结构体与函数
结构体可以作为函数的参数或返回值，方便传递复杂数据。
Point addPoints(Point a, Point b) {
Point result;
result.x = a.x + b.x;
result.y = a.y + b.y;
return result;
}
五、结构体与指针
结构体指针可以通过->运算符访问成员，也可以通过动态内存分配创建结构体对象。
ptr->x 完全等价于 (*ptr).x
Point* ptr = &p1;
cout << ptr->x << endl; // 访问成员
// 动态分配内存
Point* dynamicPtr = new Point{50, 60};
delete dynamicPtr; // 释放内存
六、结构体与类的关系
在C++中，结构体和类（class）非常相似，唯一的区别是默认访问权限不同：
- 结构体的成员默认是
public。 - 类的成员默认是
private。
struct MyStruct {
int data; // 默认 public
};
class MyClass {
int data; // 默认 private
};
结构体的应用场景
- 存储多个相关数据（如坐标、日期）。
- 作为函数的参数或返回值，减少参数数量。
- 与文件操作结合，存储结构化数据。
- 在链表、树等数据结构中表示节点。
示例：学生管理系统
struct Student {
string name;
int id;
float gpa;
};
void printStudent(const Student& s) {
cout << "Name: " << s.name << endl;
cout << "ID: " << s.id << endl;
cout << "GPA: " << s.gpa << endl;
}
int main() {
Student s1 = {"Alice", 101, 3.8};
printStudent(s1);
return 0;
}
链表
#include
using namespace std;
struct node
{
int data; // 数据
node *next; // 指向下一个节点的指针
};
// 链表头
node *head = NULL;
void menu() // 菜单
{
cout << "---------------------" << endl;
cout << "| 1->插入节点 |" << endl;
cout << "| 2->查找值 |" << endl;
cout << "| 3->删除节点 |" << endl;
cout << "| 4->遍历节点 |" << endl;
cout << "| 5->修改节点 |" << endl;
cout << "| 0->退出 |" << endl;
cout << "---------------------" << endl;
}
void addnode() // 添加
{
int a;
cout << "请输入一个整数：";
cin >> a;
node *t = new node; // 新建一个节点并分配空间
t->data = a; // t->data 节点数据
if (head == NULL) // 空链表
{
t->next = NULL; // t->next 下一个节点
head = t;
return;
}
if (head->data > a) // 插在开头
{
t->next = head;
head = t;
return;
}
node *p = head;
while (p->next != NULL && p->next->data < a) // p 指向前一个节点
{
p = p->next; // 往下移 一个节点
}
t->next = p->next;
p->next = t;
}
void trave()
{
cout << "遍历：";
node *p = head;
while (p != NULL)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
void search() // 查找
{
int a;
cout << "请输入查找的数据：";
cin >> a;
node *p = head;
while (p != NULL && p->data != a)
{
p = p->next; // 下移
}
if (p != NULL)
{
cout << "找到" << p->data << endl;
}
else
{
cout << "没找到" << endl;
}
}
bool deletenode() // 删除
{
int a;
cout << "请输入删除的数据：";
cin >> a;
if (head == NULL)
{
return false;
}
if (head->data == a) // 删除头节点
{
node *t = head;
head = head->next;
delete t; // 删除，释放空间
return true;
}
node *p = head;
while (p->next != NULL && p->next->data != a) // p 前一个节点
{
p = p->next; // 下移
}
if (p->next == NULL)
{
return false;
}
node *t = p->next;
p->next = p->next->next;
delete t;
return true;
}
void change() // 修改
{
if (deletenode()) // 删除原节点
{
addnode(); // 添加新节点
}
else
{
cout << "修改失败" << endl;
}
}
int main()
{
int choice;
while (1) // 死循环，菜单驱动
{
menu();
cout << "请输入选项：";
cin >> choice;
switch (choice)
{
case 1: addnode(); break;
case 2: search(); break;
case 3: if (deletenode()) { cout << "删除成功" << endl; }
else { cout << "删除失败" << endl; }
break;
case 4: trave(); break;
case 5: change(); break;
case 0: return 0; // 退出
}
}
return 0;
}
