一、在学习链表时我们需要了解几个基础概念：
1.
结点：当我们在使用动态分配方法为一个结构分配内存空间时，每次分配一块空间可用来存放一个结构体对象的数据，这块空间我们可以称之为结点。
2.指针域：指针可以用于节点之间的联系，在结点结构体中定义一个结构体成员项来存放下一结点的首地址（指针），这个成员称为指针域。使用动态分配时，结点之间可以不连续，但结点内是连续的。
3.链表：我们可以在第一个结点的指针域内存入第二个结点的首地址，在第二个结点的指针域内存如第三个结点的首地址，这样串联下去直到最后一个结点。最后一个结点因为没有后续结点，其指针域可以赋值为0。像我们这样连接的方式，称为链表。
二、链表的基本操作：
1.建立链表
2.链表的查找和输出
3.插入一个结点
4.删除一个结点
三、创建一个简单的链表
如下代码:
#include <iostream>
#define NULL_VALUE 0
#define TYPE_FUNC struct student
#define LEN sizeof (struct student)
using namespace std;
struct student
{
int num;
int age;
struct student *next;
};
TYPE_FUNC *creat(int n)
{
struct student *head = nullptr ,*banner = nullptr,*bottom;
int i;
for (i = 0; i < n ; i++)
{
//bottom = (TYPE_FUNC *)malloc(LEN);
bottom = new TYPE_FUNC[LEN]();
cout << "Please enter num and age : " << endl;
cin >> bottom->num;
cin.get();
cin >> bottom->age;
i == 0?banner = head = bottom:banner->next = bottom;
bottom->next = NULL_VALUE;
banner = bottom;
}
return head;
}
int main(int argc, const char * argv[])
{
cout << "请输入结点个数 ：" << endl;
int num;
cin >> num;
creat(num);
return 0;
}
说明
creat函数用于建立一个有n个节点的链表，它是一个指针函数返回值为一个指向student结构体的指针。在该函数内部，定义了三个student结构体的指针变量。head为头指针，banner为指向两个相邻结点的前一个结点的指针变量，bottom为后一结点的指针变量
四、链表的输出
如下代码：
void Print(struct student *head)
{
struct student *pStudent;
pStudent = head;
if (head != NULL)
{
cout << "Head is : " << head << endl;
do
{
cout << pStudent << endl << pStudent->age << endl << pStudent->num << " " << endl << " " << endl;
pStudent = pStudent->next;
} while (pStudent != NULL);
}
}
输出结果：
请输入节点个数 ：
3
Please enter num and age :
12
23
Please enter num and age :
34
45
Please enter num and age :
56
67
Head is : 0x10020a290
0x10020a290
23
12
0x100400000
45
34
0x100300160
67
56
Program ended with exit code: 0
五、删除结点
#pragma mark -- 删除结点
TYPE_FUNC *deleList(TYPE_FUNC *head,int num)
{
TYPE_FUNC *pStudent1;//保存当前需要检查的结点的地址
TYPE_FUNC *pStudent2 = nullptr;//保存当前检查过的结点的地址
if (head == NULL)//是空链表
{
cout << "List is NULL " << endl;
return head;
}
pStudent1 = head;//定位要删除的结点
/*
*pStudent1指向的结点不是所要查找的且pStudent1不是最后一个节点，那就继续查找
*/
while (pStudent1->num != num && pStudent1->next != NULL)
{
pStudent2 = pStudent1;//保存当前结点的地址
pStudent1 = pStudent1->next;//查找下一个结点
}
/**找到了需要的结点**/
if (pStudent1->num == num)
{
if (pStudent1 == head)//如果要删除的是第一个结点
{
/*
*头指针指向第一个结点的指针域，第一个结点就不存在链表中了
**/
head = pStudent1->next;
} else
{
/*
*如果是其他结点，则让原来指向它的结点指向它的下一个结点，这样就完成删除
**/
pStudent2->next = pStudent1->next;
}
delete pStudent1;
pStudent1 = NULL;
cout << "Delete Success!" << endl;
}else//没有查找到需要的结点
{
cout << "The list not been found !" << endl;
}
return head;
}
六、插入结点
#pragma mark 插入结点
TYPE_FUNC *insertList(TYPE_FUNC *head,int num,TYPE_FUNC *node)
{
//pStudent1用来保存当前需要检查的结点的地址（指针）
TYPE_FUNC *pStudent1;
//如果链表为空，就让插入的结点作为第一个结点
if (head == NULL)
{
head = node;
node->next = NULL;
return head;
}
pStudent1 = head;
while (pStudent1->num != num && pStudent1->next != NULL)
{
pStudent1 = pStudent1->next;
}
if (pStudent1->num == num)
{
/*
*node的下一结点就是原pStudent1的next
*插入后，原pStudent1的下一结点就是要插入的node
*/
node->next = pStudent1->next;
pStudent1->next = node;
cout << "Insert Success !" << endl;
}
else
{
cout << "List Not Found !" << endl;
}
return head;
}
int main(int argc, const char * argv[])
{
cout << "请输入节点个数 ：" << endl;
int number;
cin >> number;
TYPE_FUNC *head = creat(number);
cout << "请输入需要插入的结点信息" << endl;
TYPE_FUNC *node = new TYPE_FUNC[LEN]();
cin >> node->num;
cin.get();
cin >> node->age;
cout << "请输入需要插入的位置信息" << endl;
int number2;
cin >> number2;
cin.get();
insertList(head, number2, node);
delete [] node;
return 0;
}
输出结果：
请输入节点个数 ：
2
Please enter num and age :
12
23
Please enter num and age :
34
45
请输入需要插入的结点信息
78
90
请输入需要插入的位置信息
34
Insert Success !
Program ended with exit code: 0
七、链表的遍历
#pragma mark ---遍历链表
void traverseList(TYPE_FUNC *head)
{
TYPE_FUNC *pStudent1;//记录将要遍历的结点
if (head == NULL) {
cout << "List is temp !" << endl;
}
pStudent1 =head;//从头开始
while (pStudent1 != NULL) {
cout << "*************************" << endl;
cout << pStudent1->age << endl << pStudent1->num << endl;
cout << "*************************" << endl;
pStudent1 = pStudent1->next;
}
cout << "Traverse Success !" << endl;
}
控制台输出显示：
请输入节点个数 ：
3
Please enter num and age :
12
23
Please enter num and age :
34
45
Please enter num and age :
56
67
*************************
12
23
*************************
*************************
34
45
*************************
*************************
56
67
*************************
Traverse Success !
Program ended with exit code: 0
八、链表的销毁
#pragma mark --销毁链表
void destroyList(TYPE_FUNC *head)
{
TYPE_FUNC *sthdent;
if (head == NULL) {
cout << "List is NULL" << endl;
return;
}
while (head) {
sthdent = head->next;
delete [] head;
head = sthdent;
cout << "Leading..." << endl;
}
cout << "Destroy Success !" << endl;
return;
}
destroyList(head);
cin.get();
cin.get();
traverseList(head);
控制台输出显示：
请输入节点个数 ：
3
Please enter num and age :
12
23
Please enter num and age :
34
45
Please enter num and age :
56
67
Destroy Success !
*************************
0
0
*************************
Traverse Success !
Program ended with exit code: 0
九、链表的清空
#pragma mark --清空链表
void clearList(TYPE_FUNC *head)
{
TYPE_FUNC *student1,*student2;
if (head == NULL) {
cout << "List is NULL !" << endl;
return;
}
student1 = head->next;
while (head) {
student2 = student1->next;
delete [] student1;
student1 = student2;
}
head->next = NULL;
cout << "Clear Success !" << endl;
return;
}
十、链表的逆置（普通方法）
TYPE_FUNC *reverseList(TYPE_FUNC *head)
{
if (head == NULL || head->next == NULL) {
cout << "List is NULL !" << endl;
return head;
}
TYPE_FUNC *student2 = NULL;
TYPE_FUNC *student1 = head;
while (student1) {
TYPE_FUNC *student3 = student1;
student1 = student1->next;
student3->next = student2;
student2 = student3;
}
return student2;
}
