正文
C++实现链表的相关基础操作
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
链表的相关基础操作
# include <iostream>
using namespace std;
typedef struct LNode {
int data; //结点的数据域
struct LNode* next; //结点的指针域
}LNode, * LinkList; //LinkList为指向结构体LNode的指针类型
//typedef: struct LNode == LNode; struct LNode* == LinkList
//链表的初始化
LinkList InitList() {
LNode* L = new LNode; //生成新节点作为头结点,用头指针L指向头结点
L->next = NULL; //头结点的指针域置空
return L;
}
//创建链表：头插法
void CreateList_H(LinkList& L, int n) {
//逆位序输入n个元素的值，建立带头结点的单链表L
L = new LNode;
L->next = NULL; //先建立一个带头结点的单链表
for (int i = 0; i < n; i++) {
LNode* p = new LNode; //生成新结点
cin >> p->data; //输入元素值赋值给新结点的数据域
p->next = L->next;
L->next = p;
}
}
//创建链表：尾插法
void CreateList_R(LinkList& L, int n) {
//正位序输入n个元素的值，建立带头节点的单链表L
L = new LNode;
L->next = NULL; //先建立一个带头结点的空链表
LNode* r = L; //尾指针初始时指向头结点
for (int i = 0; i < n; i++) {
LNode* p = new LNode; //生成新结点
cin >> p->data; //输入元素值赋值给新结点的数据域
p->next = NULL; //p是最后一个结点
r->next = p;
r = p;//r指向新的尾结点p
}
}
//按序号查找结点的值
bool GetElem(LinkList L, int i, int& e) {
//在带头结点的单链表L中根据序号i获取元素的值，用e返回L中第i个数据元素
LNode* p = L->next; //p指向首元结点
int j = 1; //j为计数器
while (p && j < i) { //顺链域向后扫描,直到p指向第i个元素或者扫描完p为空
p = p->next; //p指向下一个结点
j++; //计数器j相应加1
}
if (!p || j > i) return false; //p为空 或者 i值不合法(例如：i > n 或者 i<= 0)
e = p->data; //e保存第i个结点的数据域
return true;
}
//按值查找链表结点
bool LocateElem(LinkList L, int e) {
//在带头结点的单链表L中查找值为e的元素
LNode* p = L->next;
while (p && p->data != e) {//顺链域向后扫描，直到p为空或者p所指结点的数据域等于e
p = p->next; //p指向下一个结点
}
if (!p) return false;
return true;
}
//单链表的插入
/*
和顺序表一样，如果表中有n个结点, 则插入操作中的合法位置有n + 1个
即1<= i <= n+1. 当i = n + 1时，新节点则插在链表尾部
*/
bool InsertList(LinkList& L, int i, int e) {
//在点头结点的单链表L中第i个位置插入值为e的新结点
LNode* p = L; //为啥不能是LNode* p = L->next; int j = 1
int j = 0;
while (p && j < i - 1) { //查找第i-1个结点，p指向该结点
p = p->next;
j++;
}
if (!p || j > i - 1) return false; //i值不合法(例如：i > n + 1 或 i < 1）
LNode* s = new LNode;
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
//单链表的删除
/*
删除算法中的循环条件(p->next && j < i - 1)和插入算法中的循环条件
(p && j < i - 1)是有所区别的。因为插入操作中合法的插入位置有n+1个，而
删除操作中删除的合法位置只有n个，如果使用与插入操作相同的循环条件，则
会出现引入空指针的情况，使删除操作失败。
插入时p指针最多指向第n个结点,此时判断条件为while(p && j < i - 1)
删除时p指针最多指向第n-1个结点,此时判断条件为while(p->next && j < i - 1)
*/
bool DeleteList(LinkList& L, int i) {
//在带头结点的单链表L中，删除第i个位置
LNode* p = L, * q;
int j = 0;
while (p->next && j < i - 1) { //查找第i-1个结点,p指向该结点
p = p->next;
j++;
}
if (!(p->next) || j > i - 1)return false; //当i>n+1 或者i < 1时，删除位置不合理
q = p->next; //临时保存被删结点的地址以备释放空间
p->next = q->next; //改变删除结点前驱结点的指针域
delete q; //释放被删除结点的空间
return true;
}
//单链表的遍历输出
void ListPrint(LinkList L) {
//顺序输出单链表
LNode* p = L->next;
while (p) {
cout << p->data << "\t";
p = p->next;
}
cout << endl;
}
int main() {
int i, n, e, choose;
LinkList L = InitList();
cout << "1. 初始化\n";
cout << "2. 创建单链表(头插法)\n";
cout << "3. 创建单链表(尾插法)\n";
cout << "4. 取值\n";
cout << "5. 查找\n";
cout << "6. 插入\n";
cout << "7. 删除\n";
cout << "8. 输出\n";
cout << "0. 退出\n";
choose = -1;
while (choose != 0) {
cout << "请输入数字进行操作: ";
cin >> choose;
switch (choose) {
case 1: //初始化一个空的单链表
L = InitList();
if (L) {
cout << "成功初始化一个空的单链表" << endl;
}else{
cout << "初始化一个空的单链表失败" << endl;
}
break;
case 2:// 创建单链表(头插法)
cout << "请输入想要创建链表元素个数：";
cin >> n;
cout << "请依次输入" << n << "个元素:";
CreateList_H(L, n);
cout << "头插法创建单链表输出结果：";
ListPrint(L);
break;
case 3:// 创建单链表(尾插法)
cout << "请输入想要创建链表元素个数：";
cin >> n;
cout << "请依次输入" << n << "个元素:";
CreateList_R(L, n);
cout << "尾插法创建单链表输出结果：";
ListPrint(L);
break;
case 4: //取值
cout << "请输入想查找的链表元素序号：";
cin >> i;
GetElem(L, i, e);
cout << "第" << i << "个链表元素的数据域是:" << e << endl;
break;
case 5: //查找
cout << "请输入想查找的链表元素的数据域:";
cin >> e;
if (LocateElem(L, e)) {
cout << "查找成功" << endl;
}
else {
cout << "查找失败" << endl;
}
break;
case 6: //插入
cout << "请输入插入的位置和数据(用空格隔开)：";
cin >> i >> e;
if (InsertList(L, i, e)) {
cout << "插入成功" << endl;
}
else {
cout << "插入失败" << endl;
}
break;
case 7: //删除
cout << "请输入删除的位置：";
cin >> i;
if (DeleteList(L, i)) {
cout << "删除成功" << endl;
}
else {
cout << "删除失败" << endl;
}
break;
case 8: //遍历输出单链表
ListPrint(L);
break;
case 0: //退出
exit(-1);
}
}
return 0;
}
链表的应用
题目1:链表合并(Acwing3639)
# include <iostream>
using namespace std;
typedef struct LNode {
int data; //结点的数据域
struct LNode* next; //结点的指针域
}LNode, * LinkList; //LinkList为指向结构体LNode的指针类型
//typedef: struct LNode == LNode; struct LNode* == LinkList
//链表的初始化
LinkList InitList() {
LNode* L = new LNode; //生成新节点作为头结点,用头指针L指向头结点
L->next = NULL; //头结点的指针域置空
return L;
}
//创建链表：头插法
void CreateList_H(LinkList& L, int n) {
//逆位序输入n个元素的值，建立带头结点的单链表L
L = new LNode;
L->next = NULL; //先建立一个带头结点的单链表
for (int i = 0; i < n; i++) {
LNode* p = new LNode; //生成新结点
cin >> p->data; //输入元素值赋值给新结点的数据域
p->next = L->next;
L->next = p;
}
}
//创建链表：尾插法
void CreateList_R(LinkList& L, int n) {
//正位序输入n个元素的值，建立带头节点的单链表L
L = new LNode;
L->next = NULL; //先建立一个带头结点的空链表
LNode* r = L; //尾指针初始时指向头结点
for (int i = 0; i < n; i++) {
LNode* p = new LNode; //生成新结点
cin >> p->data; //输入元素值赋值给新结点的数据域
p->next = NULL; //p是最后一个结点
r->next = p;
r = p;//r指向新的尾结点p
}
}
//按序号查找结点的值
bool GetElem(LinkList L, int i, int& e) {
//在带头结点的单链表L中根据序号i获取元素的值，用e返回L中第i个数据元素
LNode* p = L->next; //p指向首元结点
int j = 1; //j为计数器
while (p && j < i) { //顺链域向后扫描,直到p指向第i个元素或者扫描完p为空
p = p->next; //p指向下一个结点
j++; //计数器j相应加1
}
if (!p || j > i) return false; //p为空 或者 i值不合法(例如：i > n 或者 i<= 0)
e = p->data; //e保存第i个结点的数据域
return true;
}
//按值查找链表结点
bool LocateElem(LinkList L, int e) {
//在带头结点的单链表L中查找值为e的元素
LNode* p = L->next;
while (p && p->data != e) {//顺链域向后扫描，直到p为空或者p所指结点的数据域等于e
p = p->next; //p指向下一个结点
}
if (!p) return false;
return true;
}
//单链表的插入
/*
和顺序表一样，如果表中有n个结点, 则插入操作中的合法位置有n + 1个
即1<= i <= n+1. 当i = n + 1时，新节点则插在链表尾部
*/
bool InsertList(LinkList& L, int i, int e) {
//在点头结点的单链表L中第i个位置插入值为e的新结点
LNode* p = L; //为啥不能是LNode* p = L->next; int j = 1
int j = 0;
while (p && j < i - 1) { //查找第i-1个结点，p指向该结点
p = p->next;
j++;
}
if (!p || j > i - 1) return false; //i值不合法(例如：i > n + 1 或 i < 1）
LNode* s = new LNode;
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
//单链表的删除
/*
删除算法中的循环条件(p->next && j < i - 1)和插入算法中的循环条件
(p && j < i - 1)是有所区别的。因为插入操作中合法的插入位置有n+1个，而
删除操作中删除的合法位置只有n个，如果使用与插入操作相同的循环条件，则
会出现引入空指针的情况，使删除操作失败。
插入时p指针最多指向第n个结点,此时判断条件为while(p && j < i - 1)
删除时p指针最多指向第n-1个结点,此时判断条件为while(p->next && j < i - 1)
*/
bool DeleteList(LinkList& L, int i) {
//在带头结点的单链表L中，删除第i个位置
LNode* p = L, * q;
int j = 0;
while (p->next && j < i - 1) { //查找第i-1个结点,p指向该结点
p = p->next;
j++;
}
if (!(p->next) || j > i - 1)return false; //当i>n+1 或者i < 1时，删除位置不合理
q = p->next; //临时保存被删结点的地址以备释放空间
p->next = q->next; //改变删除结点前驱结点的指针域
delete q; //释放被删除结点的空间
return true;
}
//单链表的遍历输出
void ListPrint(LinkList L) {
//顺序输出单链表
LNode* p = L->next;
while (p) {
cout << p->data << "\t";
p = p->next;
}
cout << endl;
}
int main() {
int i, n, e, choose;
LinkList L = InitList();
cout << "1. 初始化\n";
cout << "2. 创建单链表(头插法)\n";
cout << "3. 创建单链表(尾插法)\n";
cout << "4. 取值\n";
cout << "5. 查找\n";
cout << "6. 插入\n";
cout << "7. 删除\n";
cout << "8. 输出\n";
cout << "0. 退出\n";
choose = -1;
while (choose != 0) {
cout << "请输入数字进行操作: ";
cin >> choose;
switch (choose) {
case 1: //初始化一个空的单链表
L = InitList();
if (L) {
cout << "成功初始化一个空的单链表" << endl;
}else{
cout << "初始化一个空的单链表失败" << endl;
}
break;
case 2:// 创建单链表(头插法)
cout << "请输入想要创建链表元素个数：";
cin >> n;
cout << "请依次输入" << n << "个元素:";
CreateList_H(L, n);
cout << "头插法创建单链表输出结果：";
ListPrint(L);
break;
case 3:// 创建单链表(尾插法)
cout << "请输入想要创建链表元素个数：";
cin >> n;
cout << "请依次输入" << n << "个元素:";
CreateList_R(L, n);
cout << "尾插法创建单链表输出结果：";
ListPrint(L);
break;
case 4: //取值
cout << "请输入想查找的链表元素序号：";
cin >> i;
GetElem(L, i, e);
cout << "第" << i << "个链表元素的数据域是:" << e << endl;
break;
case 5: //查找
cout << "请输入想查找的链表元素的数据域:";
cin >> e;
if (LocateElem(L, e)) {
cout << "查找成功" << endl;
}
else {
cout << "查找失败" << endl;
}
break;
case 6: //插入
cout << "请输入插入的位置和数据(用空格隔开)：";
cin >> i >> e;
if (InsertList(L, i, e)) {
cout << "插入成功" << endl;
}
else {
cout << "插入失败" << endl;
}
break;
case 7: //删除
cout << "请输入删除的位置：";
cin >> i;
if (DeleteList(L, i)) {
cout << "删除成功" << endl;
}
else {
cout << "删除失败" << endl;
}
break;
case 8: //遍历输出单链表
ListPrint(L);
break;
case 0: //退出
exit(-1);
}
}
return 0;
}
题目1:链表合并(Acwing3639)
有序链表的合并
题目:将两个有序(非递减)单链表La和Lb合并为一个新的有序(非递减)单链表。
解题思路:链表合并不需要再创建空间,只需要进行穿针引线,把两个单链表中的结点，按非递减的顺序串联起来即可。
注意:单链表的头指针不可以移动
# include <iostream>
using namespace std;
typedef struct LNode {
int data; //结点的数据域
struct LNode* next; //结点的指针域
}LNode, * LinkList; //LinkList为指向结构体LNode的指针类型
//尾插法创建单链表
void CreateList_R(LinkList& L, int n) {
L = new LNode;
L->next = NULL; //创建一个空的头结点
LNode* r = L; //尾指针
for (int i = 0; i < n; i++) {
LNode* p = new LNode;
cin >> p->data;
r->next = p;
r = p;
}
r->next = NULL;//将最后一个结点的指针域置空
}
LinkList MergeList(LinkList& L1, LinkList& L2) {
LNode* L = L1; //L是合并的新链表头指针,L指向L1的头结点
LNode* r = L; //尾指针永远指向链表尾部
LNode* p = L1->next, * q = L2->next;//p指针指向L1的第一个元素,q指针指向L2的第一个元素
while (p && q) { //p和q同时不指向空
if (p->data <= q->data) {//把p指向的结点串起来
r->next = p;
r = p;
p = p->next;//p后移到下一结点
}
else {//把q指向的结点串起来
r->next = q;
r = q;
q = q->next;
}
}
//退出循环的条件:1、p为空; 2、q为空
if (!p) r->next = q;//p为空
if (!q) r->next = p;//q为空
//或者r->next = p ? p : q;
delete L2;
return L;
}
void ListPrint(LinkList L) {
//顺序输出单链表
LNode* p = L->next;
while (p) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
int main() {
LinkList L1, L2, L;
int S1, S2;
cin >> S1;
CreateList_R(L1, S1);
cin >> S2;
CreateList_R(L2, S2);
L = MergeList(L1, L2);
ListPrint(L);
return 0;
}
题目2: 链表的中间结点(Leetcode 872)
快慢指针
题目:带有头结点的单链表L,设计一个尽可能高效的算法,求L中的中间结点。如果有两个中间结点,则返回第一个中间结点
提示：给定链表的结点数介于 1 和 100 之间。
解题思路:这样的题型需要使用快慢指针来解决。一个快指针，一个慢指针,快指针走两步满指针走一步,当快指针指向结尾的时候,慢指针刚好指向中间结点
/*
题目:带有头结点的单链表L, 头结点的数据域不存储数据。设计一个尽可能高效的算法, 求L中的中间结点。
如果有两个中间结点, 则返回第一个中间结点.
*/
# include <iostream>
using namespace std;
typedef struct LNode {
int data;
struct LNode* next;
}LNode, * LinkList;
//尾插法建立单链表
void CreateList_R(LinkList& L, int n) {
L = new LNode;
L->next = NULL;
LNode* r = L; //尾指针
for (int i = 0; i < n; i++) {
LNode* p = new LNode;
cin >> p->data;
r->next = p;
r = p;
}
r->next = NULL; //链表最后一个结点的指针域置空
}
LNode* FindMiddle(LinkList L) {
LNode* fast = L;
LNode* slow = L;
while (fast && fast->next) {
fast = fast->next->next; //快指针一次走两步
slow = slow->next; //慢指针一次走一步
}
return slow; //慢指针所指的位置就是中间结点的位置
}
void PrintList(LinkList L) {
LNode* p = L->next;
while (p) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
int main() {
LinkList L;
LNode* middle;
int n;
cout << "输入链表结点个数:";
cin >> n;
cout << "依次输入" << n << "个元素:" ;
CreateList_R(L, n);
cout << "打印链表中的所有元素:";
PrintList(L);
middle = FindMiddle(L);
cout << "链表中间结点元素为:";
cout << middle->data << endl;
system("pause");
return 0;
}
题目:
1.在单链表中查到倒数第k个结点
2.用单链表保存m个整数,结点的结构为(data,next),且|data|<=n(n为正整数)。现在要求设计一个时间复杂度尽可能高效的算法,对于链表中data的绝对值相等的结点,仅保留第一次出现的结点而阐述其绝对值相等的结点。
