目录
情境引入：
学习了动态链表的输入输出后，若还需要对其进行进一步的操作，要怎么实现呢？为了更好的学习链表的操作，我们不妨根据一个实际情境进一步完善上次的程序：
题目：写一个链表的程序，使其能完成数据的插入，删除与查找
数据包括工人的编号，姓名和年龄
我对上期的代码主要做了如下的修改：结构体的数据数量调整，变为工人的编号，姓名，年龄三个变量；输入输出部分也进行了相应的改动。
#include<iostream>
using namespace std;
struct node
{
char num[30];
char name[30];
int age;
struct node* next;
};
node* head;
void create()
{
node* p = NULL, * s;
s = new node;
cin >> s->num;
cin >> s->name;
cin >> s->age;
head = NULL;
while (s->num != NULL && s->age != NULL && s->name != NULL) {
if (head == NULL)head = s;
else p->next = s;
p = s;
s = new node;
cin >> s->num;
cin >> s->name;
cin >> s->age;
}
p->next = NULL;
delete s;
return;
}
int main()
{
node* p;
create();
p = head;
while (p != NULL)
{
cout << p->num << " " << p->name << " " << p->age << endl;
p = p->next;
}
return 0;
}输出部分如图 ：
一、数据的查找
1.要求：
输入数据在链表中的位置，检索链表输出对应元素
2.思路：
因为插入与删除需要用到数据的查找，调用查找函数找到相应的位置直接进行相应的修改即可，所以我们从查找做起。
我们查找的逻辑是：输入了元素的位置后，先判断输入是否合理（这个变量起码要大于0）我们只需要在函数中添加一个循环控制变量，当变量和我们输入的元素位置的变量相等时返回对应的指针。如果没有遍历到，那么就返回空指针。
所以循环的条件就很容易想到，就是链表指向的元素不能是空指针，如果遍历到空指针还没有返回值，那么就说明这个链表没有这么长，所以返回空指针。
注意！！其实这个函数是可以写成void型直接输出的，但是我们后续的插入和删除需要调用查找函数，所以我们选择指针作为返回类型。
3.程序：
node *search (int search)
{//search变量是要查找的数据，在主函数中输入传入被调函数
if (search <= 0) //非法输入
return NULL;
if (search == 1)//第一个数据返回头指针
return head;
int j = 2;//从第二个数据开始
node* p;
p = head->next;//将头指针向后移
while (j !=search && p != NULL)
{
p = p->next;
j++;
}
return p;
}4.运行 ：
二、数据的插入
1.要求：
输入要插入数据的位置，输入要插入的数据，将数据插入到输入的位置数据的后面。
2.思路：
我们输入插入数据的位置后，我们应当先对输入的数据的合法性进行检测，如果数据小于一，那么应当有报错提示。之后可以通过调用查找函数找到其在链表中的位置(p)，在当前位置开辟新空间（q），将数据写入q，让p的地址部分储存刚开辟的q的地址（p->next = q;），让q的地址部分指向原来p指向的地址即可（q->next = p->next;）。流程图如下：
3.程序：
void insert()
{
int insert;
cout << "请选择你要插入的位置：" << endl;
cin >> insert;
if (insert < 1)//输入合法性判断
{
cout << "您所插入的位置不存在" << endl;
return;
}
node* p = search(insert);
node* q = new node;
cout << "请输入要插入的节点数据编号：";
cin >> q->num;
cout << "请输入要插入的节点数据姓名：";
cin >> q->name;
cout << "请输入要插入的节点数据年龄：";
cin >> q->age;
q->next = p->next;//将q的地址部分指向p原来指向的结构体
p->next = q;//让p的地址部分指向q
return;
}4.运行：
三、数据的删除
1.要求：
输入要删除的元素的位置，将该处的数据从链表中删除。
2.思路：
有了插入的铺垫，删除的原理与之相似，也是输入要删除的数据（p2）的位置，那么我们只需要用查找函数找到该位置结构体的前一位（p1）和后一位（p3），让前一个结构体的地址部分指向它后一个结构体。(也就是p1->next = p3;)这样，这个结构体就不被指向了，或者说，就被“跳过了”。这时我们再用delete关键字释放空间，这个结构体就被彻底删除了。说起来些许抽象，上程序框图：
3.程序：
void remove()
{
int i;
cout << "请选择你要删除的位置：" << endl;
cin >> i;
node* p1 = search(i - 1);
node* p2 = p1->next;
node* p3 = p2->next;
p1->next = p3;//让p1的地址部分直接指向p3
delete p2;//释放内存空间
cout << "删除成功!" << endl;
return;
}4.运行：
四、调整与小结：
至此，我们整个的链表操作系统系列就结束啦！
优化：
为了方便，我在程序中添加了打印链表的print函数，之后又把几个函数整合到一起。同时为了提高程序的实用性，我在程序中添加了switch函数，通过输入不同的数字对链表进行不同的操作，更加便捷，同时也优化了输出，完整程序如下：
#include<iostream>
using namespace std;
struct node
{
char num[20];
char name[20];
int age;
struct node* next;
};
node* head;
void print()
{
node* p;
p = head;
while (p != NULL)
{
cout << p->num << " " << p->name << " " << p->age << endl;
p = p->next;
}
return;
}
void create()//创建链表
{
int stage = 2;
node* p = NULL, * s;
s = new node;
cout << "请输入编号：";
cin >> s->num;
cout << "请输入姓名：";
cin >> s->name;
cout << "请输入年龄：";
cin >> s->age;
head = NULL;
while (s->age != NULL && s->name != NULL && s->num != NULL) {
cout << "正在输入第" << stage << "个元素" << endl;
if (head == NULL)head = s;
else p->next = s;
p = s;
s = new node;
cout << "请输入编号：";
cin >> s->num;
cout << "请输入姓名：";
cin >> s->name;
cout << "请输入年龄：";
cin >> s->age;
stage++;
}
p->next = NULL;
delete s;
return;
}
node *search (int search)//搜索链表
{
if (search <= 0)
return NULL;
if (search == 1)
return head;
int j = 2;
node* p;
p = head->next;
while (j !=search && p != NULL)
{
p = p->next;
j++;
}
return p;
}
void insert()
{
int insert;
cout << "请选择你要插入的位置：" << endl;
cin >> insert;
if (insert < 1)//输入合法性判断
{
cout << "您所插入的位置不存在" << endl;
return;
}
node* p = search(insert);
node* q = new node;
cout << "请输入要插入的节点数据编号：";
cin >> q->num;
cout << "请输入要插入的节点数据姓名：";
cin >> q->name;
cout << "请输入要插入的节点数据年龄：";
cin >> q->age;
q->next = p->next;//将q的地址部分指向p原来指向的结构体
p->next = q;//让p的地址部分指向q
return;
}
void remove()
{
int i;
cout << "请选择你要删除的位置：" << endl;
cin >> i;
node* p1 = search(i - 1);
node* p2 = p1->next;
node* p3 = p2->next;
p1->next = p3;
delete p2;
cout << "删除成功!" << endl;
return;
}
int main()
{
node* p;
int location, operate;
cout << "创建链表：" << endl;
create();
print();
cout << "请输入要进行的操作：1查找，2插入，3删除：";
while (cin >> operate) {
if (operate == 0)
break;
else {
switch (operate) {
case 1:
cout << "请输入要查找的元素位置：";
cin >> location;
cout << search(location)->num << " " << search(location)->name << " " << search(location)->age << endl;
break;
case 2:
insert();
print();
break;
case 3:
remove();
print();
break;
}
}
cout << "请输入要进行的操作：1查找，2插入，3删除：";
}
return 0;
}运行：
