有一个不带头结点的单链表：
递归实现以下操作(强调：所有操作必须用递归完成）。
1，插入数据：13，15，8，4，8，3，4，8(可以用递归一次完成，也可以用递归将一个一维数组一个一个的尾部插入)
2，正向输出所有节点值
3，逆向输出所有节点值
4，输出单链表中数据结点个数
5，输出第k个节点的值（k由用户输入，要能给出错误情况）
6，在第k个位置上插入e元素。（k和e由用户输入，要能给出错误情况）
7，正向输出所有节点值
8，删除第k个结点（k由用户输入，要能给出错误情况）
9，正向输出所有节点值
10，删除值为X的数据结点（测试值为：8）
11，正向输出所有节点值
12，删除所有值为X的数据结点（测试值为：4）
13，正向输出所有节点值
14，输出该链表的最大值
15，输出该链表的最小值
16，查找值为X的数据结点在当前链表出现的位置（测试值为：3，要能给出错误情况)。
17，销毁该链表
=================================================
1.定义单链表的数据结构
#include <iostream>
using namespace std;
typedef int ElemType;
/* 定义单链表 */
typedef struct node {
ElemType data;
node* next;
} List;
2.插入元素到链表的第i个位置
在主函数时搭配 for 循环，从数组内的数组一个个插入链表
bool InsertList(List*& L, int i, ElemType e) // 插入第i个位置(逻辑位序)
{
if (i <= 0) // 特判非正整数的非法位置
return false;
else if (1 == i) // 找到了要插入的位置的前一个节点
{
List* s = new List;
s->data = e;
s->next = L;
L = s; // 前一个节点的next指针(在上一层递归中体现)指向新建的节点
return true;
}
if (NULL == L) // 如果这个节点已经是最后一个节点了，那么不用递归下去了
return false;
else
return InsertList(L->next, i - 1, e); // 递归到下一层, 若找到对应节点那么此处的指针值会相应改变
}
3.单链表中数据结点个数
int CountList(List* L)
{
if (NULL == L)
return 0;
return 1 + CountList(L->next); // 1 + 从L->next出发的节点数
}
4.正向输出所有节点值
先输出第一个节点值，然后进行递归到下一个节点，每递归到下一层输出下一层的节点值，直到最后一个节点。
void DispList(List* L)
{
if (NULL == L)
return;
cout << L->data << ' '; // 先输出该元素
DispList(L->next); // 再递归到下一个节点
}
5.逆向输出所有节点值
先递归到最后一个节点，输出该节点值，然后一层一层退出递归，每退出一层输出该层节点值
void DispListRev(List* L)
{
if (NULL == L)
return;
DispListRev(L->next); // 先递归到下一个节点
cout << L->data << ' '; // 返回该函数时，再输出元素
}
6.输出第i个位置上的节点
bool DispOne(List* L, int i, ElemType& e)
{
if (i <= 0 || NULL == L) // 越界判断
return false;
else if (1 == i)
{
e = L->data;
return true;
}
return DispOne(L->next, i - 1, e);
}
7.删除第一个值为e的元素
bool DeleOneByValue(List*& L, ElemType e)
{
if (NULL == L) // 没找到
return false;
if (e == L->data) // 发现了需要删除的元素
{
List* p = L; // 新建一个指针保存要删除的节点的地址值
L = L->next; // 让上一个节点的next指针指向该节点的next指针
delete p; // 删除节点
return true; // 返回true，结束递归
}
return DeleOneByValue(L->next, e); // 如果到此处，证明当前节点没有删除成功，返回值由下一层递归决定
}
8.删除所有值为e的元素
bool DeleAll(List*& L, ElemType e)
{
if (NULL == L)
return false;
if (e == L->data)
{
List* p = L;
L = L->next;
delete p;
DeleAll(L, e); // 删除后L成为未检测过的节点，故递归从L开始
return true; // 最后再返回true，因为至少删除过一个节点了
}
return DeleAll(L->next, e); // 同上一个函数此处的解释
}
9.通过位置删除第i个位置上的元素
bool DeleOneByLocation(List*& L, int i)
{
if (i <= 0) // 按位置查找特殊些, 先判断非正整数越界的情况
return false;
else if (1 == i)
{
List* s = L; // 删除跟之前的差不多
L = L->next;
delete s;
return true;
}
if (L->next) // 如果有下一个节点的话, 就递归下去
return DeleOneByLocation(L->next, i - 1);
else
return false; // 如果没有, 那么查找的位置越界了
}
?10.定位元素e的位置
int LocateElem(List* L, ElemType e)
{
if (e == L->data)
return 1;
else if (L->next)
return 1 + LocateElem(L->next, e);
else
return 2; // 如果是最后一个节点的话, 那么返回2, 使得最终的结果超过链表的长度, 判断为越界
}
11.得到L节点开始的最大值
ElemType maxValue(List* L)
{
if (NULL == L->next) // 当前节点已经是最后一个节点了，返回当前节点data值即可
return L->data;
int nextMax = maxValue(L->next); // 得到该节点的后面的节点的最大值
return L->data > nextMax ? L->data : nextMax; // 判断返回当前data值和后面节点最大值中较大的数
}
12.得到L节点开始的最小值
ElemType minValue(List* L)
{
if (NULL == L->next)
return L->data;
int nextMin = minValue(L->next);
return L->data < nextMin ? L->data : nextMin;
}
13.销毁单链表
void DestroyList(List*& L)
{
if (NULL == L)
return;
DestroyList(L->next); // 先删除后面的节点
delete L; // 递归回到此处时，再删除当前节点
}
=================================================
主函数
int main()
{
int k;
List* L1 = NULL;
ElemType x;
ElemType a[] = {13, 15, 8, 4, 8, 3, 4};
cout << "(1) 插入数据" << endl << endl;
k = sizeof(a) / sizeof(ElemType);
for (int i = 0; i < k; ++i)
{
InsertList(L1, i + 1, a[i]);
}
cout << "(2) 正向输出所有节点值" << endl;
cout << "正向输出所有值为: " ; DispList(L1);
cout << endl << endl;
cout << "(3) 逆向输出所有节点值" << endl;
cout << "逆向输出所有值为: " ; DispListRev(L1);
cout << endl << endl;
cout << "(4) 输出单链表中数据节点的个数" << endl;
cout << "该单链表有" << CountList(L1) << "个节点" << endl << endl;
cout << "(5) 输出第k个节点的值" << endl;
cout << "请输入你要输出的节点的序号: "; cin >> k;
if (DispOne(L1, k, x))
{
cout << "找到第" << k << "个元素: " << x;
}
else
cout << "你输入的位置不正确";
cout << endl << endl;
cout << "(6) 在第k个元素位置上插入e元素" << endl;
cout << "请输入你需要插入的位置: "; cin >> k;
cout << "请输入你要插入的元素: "; cin >> x;
cout << (InsertList(L1, k, x) ? "插入成功" : "插入失败");
cout << endl << endl;
cout << "(7) 正向输出所有节点值" << endl;
cout << "正向输出所有值为: " ; DispList(L1);
cout << endl << endl;
cout << "(8) 删除第k个节点" << endl;
cout << "请输入需要删除的节点的序号: "; cin >> k;
cout << (DeleOneByLocation(L1, k) ? "删除成功" : "删除失败") << endl << endl;
cout << "(9) 正向输出所有节点值" << endl;
cout << "正向输出所有值为: " ; DispList(L1);
cout << endl << endl;
cout << "(10) 删除值为X的数据节点(删除第一个)" << endl;
cout << "请输入需要删除的节点的值: "; cin >> x;
cout << (DeleOneByValue(L1, x) ? "删除成功" : "删除失败") << endl << endl;
cout << "(11) 正向输出所有节点值" << endl;
cout << "正向输出所有值为: " ; DispList(L1);
cout << endl << endl;
cout << "(12) 删除所有值为X的数据节点" << endl;
cout << "请输入你需要删除的值: "; cin >> x;
cout << (DeleAll(L1, x) ? "删除成功" : "删除失败") << endl << endl;
cout << "(13) 正向输出所有节点值" << endl;
cout << "正向输出所有值为: " ; DispList(L1);
cout << endl << endl;
cout << "(14) 输出该链表的最大值" << endl;
cout << "该链表的最大值为: " << maxValue(L1) << endl << endl;
cout << "(15) 输出该链表的最小值" << endl;
cout << "该链表的最小值为: " << minValue(L1) << endl << endl;
cout << "(16) 查找值为X的数据节点在当前链表第一次出现的位置" << endl;
cout << "请输入你需要查找的元素: "; cin >> x;
if ( (k = LocateElem(L1, x) ) <= CountList(L1) )
{
cout << "找到该元素, 它是链表中第" << k << "个元素";
}
else
cout << "找不到该元素";
cout << endl << endl;
cout << "(17) 销毁该链表" << endl;
DestroyList(L1);
return 0;
}
|