内容：构建线性表的链式存储结构，采用动态分配方式实现单链表的初始化，数据的插入，删除，输出单链表内中各元素，求单链表的长度，实现单链表中数据结点的按值排序，实现单链表的逆置，合并两个有序的单链表（有序的a表和有序的b表合并之后的结果保存在a表中）等操作。
同时：
（1）要有能根据用户的输入来选择不同运算的菜单界面。
（2）单链表中数据元素的类型统一抽象表示为ElemType类型，具体类型不限，可以是整型、实型、字符型、或者是自己构造的一种结构体类型。
代码如下：
#include <iostream>
#define ElemType int
using namespace std;
//带头结点的单链表类，头结点存放单链表长度
class Single_List {
private:
ElemType data;
Single_List* next;
public:
Single_List() {};
//单链表的创建函数，尾插法
Single_List* Create(int len) {
Single_List* prev, * head, * tail;
head = new Single_List;
head->data = len;
head->next = NULL;
prev = head;
if (len == 0) {
goto end;
}
cout << "请输入各个结点的数值：" << endl;
while (len--) {
int data;
tail = new Single_List;
cin >> data;
this->attach(prev, tail, data);
prev = tail;
}
end: return head;
}
void attach(Single_List* prev, Single_List* tail, int data) {
tail->next = NULL;
tail->data = data;
prev->next = tail;
}
int getLength(Single_List* list) {
return list->data;
}
//判断单链表是否为空的函数
bool Isempty(Single_List* list) {
return list->data == 0;
}
//单链表的打印函数
void Print(Single_List* list) {
if (list->Isempty(list)) {
cout << "单链表为空" << endl;
return;
}
int len = list->data;
Single_List* ptrl = list->next;
for (int i = 0; i < len; i++) {
cout << ptrl->data << " ";
ptrl = ptrl->next;
}
}
//在第index个结点后面插入数值为data的结点的函数
Single_List* Insert(Single_List* list, int index, int data) {
Single_List* prev = list;
Single_List* insert;
insert = new Single_List;
int len = list->getLength(list);
//链表为空时,无论index为多少，只能插在第一个位置
if (this->Isempty(list)) {
this->attach(prev, insert, data);
list->data++;
return list;
}
//如果插入的位置大于等于链表长度直接插到末尾，
index = (list->data <= index) ? list->data : index;
for (int i = 0; i < index; i++) {
prev = prev->next;
}
insert->data = data;
insert->next = prev->next;
prev->next = insert;
list->data++;
return list;
}
//寻找第k个结点的函数,只适用链表不为空的情况
Single_List* Findkth(Single_List* list, int k) {
Single_List* prev;
prev = list;
for (int i = 0; i < k; i++) {
prev = prev->next;
}
return prev;
}
//寻找数值为N的结点的函数
int FindN(Single_List* list, int N) {
int result = -1;
Single_List* prev;
prev = list;
int len = this->getLength(list);
for (int i = 0; i < len; i++) {
prev = prev->next;
if (prev->data == N) {
result = i;
break;
}
}
return result;
}
//删除数值为N的结点的函数
void DeleteN(Single_List* list, int N) {
int index = this->FindN(list, N);
//不存在数值为N的情况
if (index == -1) {
cout << "单链表不存在数值为" << N << "的结点" << endl;
return;
}
this->Deletekth(list, index + 1);
}
//删除第k个结点的函数
void Deletekth(Single_List* list, int k) {
int len = list->data;
if (this->Isempty(list)) {
cout << "单链表为空无法删除" << endl;
return;
}
Single_List* del_pre;
del_pre = this->Findkth(list, k - 1);
del_pre->next = del_pre->next->next;
list->data--;
}
//逆转链表函数
Single_List* Reverse(Single_List* list) {
//单链表为空时
if (this->Isempty(list)) {
return list;
}
Single_List* head, * front, * rear, * tag;
head = list; //保存头结点
//front，rear用于逆转，tag用于记录未逆转的链表
front = list->next;
rear = front->next;
front->next = NULL;
while (rear) {
tag = rear->next;
rear->next = front;
front = rear;
rear = tag;
}
head->next = front;
return head;
}
//对两个升序链表进行升序合并函数
Single_List* Merge(Single_List* list1, Single_List* list2) {
if (list1 == NULL) {
return list1;
}
if (list2 == NULL) {
return list2;
}
Single_List* list; //建立合并链表的头结点，存放两个链表长度之和
list = new Single_List;
list->data = list1->data + list2->data;
list->next = NULL;
Single_List* prev1, * prev2, * tail, * head, * tag;
prev1 = list1->next; //指向list32的第一个结点（不是存放长度的头结点，即头结点之后的结点）
prev2 = list2->next;
head = new Single_List; //建立新链表的空头结点
tag = head; //保存空头结点的地址
head->next = NULL;
while (prev1 && prev2) {
tail = new Single_List;
if (prev1->data <= prev2->data) {
this->attach(head, tail, prev1->data);
head = tail;
prev1 = prev1->next;
}
else {
this->attach(head, tail, prev2->data);
head = tail;
prev2 = prev2->next;
}
}
if (prev1) {
head->next = prev1;
}
if (prev2) {
head->next = prev2;
}
list->next = tag->next;
return list;
}
//链表长
int Length(Single_List* list)
{
Single_List* s = list->next;
int length = 0;
while (s)
{
s = s->next;
length++;
}
cout << length << endl;
return length;
}
//链表排序，冒泡排序
Single_List* Sort(Single_List* list)
{
Single_List* head, * prev1, * prev2;
head = list;
prev1 = list->next;
while (prev1) {
prev2 = prev1->next;
while (prev2) {
if (prev1->data > prev2->data) {
prev1->data += prev2->data;
prev2->data = prev1->data - prev2->data;
prev1->data -= prev2->data;
}
prev2 = prev2->next;
}
prev1 = prev1->next;
}
return head;
}
void show_Menu()
{
cout << "请输入要进行的任务" << endl;
cout << "0.退出程序" << endl;
cout << "1.创建两条单链表" << endl;
cout << "2.排序输出" << endl;
cout << "3.插入数值" << endl;
cout << "4.删除(结点)" << endl;
cout << "5.删除(数值)" << endl;
cout << "6.倒置输出" << endl;
cout << "7.输出表长" << endl;
cout << "8.合并两表" << endl;
cout << endl;
}
void ExitSystem()
{
cout << "使用结束" << endl;
system("pause");
exit(0);
}
~Single_List() {};
};
int main()
{
int len, index, data, n;
Single_List tmp;
Single_List* list = NULL;
Single_List* list1 = NULL;
int choice = 0;
while (true)
{
//展示
tmp.show_Menu();
cout << "请输入选择" << endl;
cin >> choice;
switch (choice)
{
case 0://退出
tmp.ExitSystem();
break;
case 1://创建
cout << "请输入初始化单链表 1 的长度:" << endl;
cin >> len;
list = tmp.Create(len);
cout << "单链表如下：" << endl;
tmp.Print(list);
cout << endl;
cout << "请输入初始化单链表 2 的长度:" << endl;
cin >> len;
list1 = tmp.Create(len);
cout << "第二个单链表如下：" << endl;
tmp.Print(list1);
cout << endl;
break;
case 2://排序
cout << "单链表 1 排序后为:" << endl;
list = tmp.Sort(list);
tmp.Print(list);
cout << endl;
cout << "单链表 2 排序后为:" << endl;
list1 = tmp.Sort(list1);
tmp.Print(list1);
cout << endl;
break;
case 3://插入
cout << "请选择进行插入操作的链表 1/2 " << endl;
cin >> n;
if (n == 1)
{
cout << "插入前单链表如下" << endl;
tmp.Print(list);
cout << "请输入插入结点的位置：" << endl;
cin >> index;
cout << "请输入插入结点的数值：" << endl;
cin >> data;
list = tmp.Insert(list, index, data);
cout << "插入后单链表如下" << endl;
tmp.Print(list);
cout << endl;
}
if (n == 2)
{
cout << "插入前单链表如下" << endl;
tmp.Print(list1);
cout << "请输入插入结点的位置：" << endl;
cin >> index;
cout << "请输入插入结点的数值：" << endl;
cin >> data;
list = tmp.Insert(list1, index, data);
cout << "插入后单链表如下" << endl;
tmp.Print(list1);
cout << endl;
}
else
{
cout << " " << endl;
}
break;
case 4://删除(结点)
cout << "请选择进行删除操作的链表 1/2 " << endl;
cin >> n;
if (n == 1)
{
cout << "删除前单链表如下" << endl;
tmp.Print(list);
cout << "请输入删除结点的位置:" << endl;
cin >> index;
tmp.Deletekth(list, index);
cout << "删除后单链表 1 如下" << endl;
tmp.Print(list);
cout << endl;
}
if (n == 2)
{
cout << "删除前单链表如下" << endl;
tmp.Print(list1);
cout << "请输入删除结点的位置:" << endl;
cin >> index;
tmp.Deletekth(list1, index);
cout << "删除后单链表 1 如下" << endl;
tmp.Print(list1);
cout << endl;
}
else
{
cout << " " << endl;
}
break;
case 5://删除(值)
cout << "请选择进行删除操作的链表 1/2 " << endl;
cin >> n;
if (n == 1)
{
cout << "删除前单链表如下" << endl;
tmp.Print(list);
cout << "请输入删除结点的数值:" << endl;
cin >> data;
tmp.DeleteN(list, data);
cout << "删除后单链表 1 如下" << endl;
tmp.Print(list);
cout << endl;
}
if (n == 2)
{
cout << "删除前单链表如下" << endl;
tmp.Print(list1);
cout << "请输入删除结点的数值:" << endl;
cin >> data;
tmp.Deletekth(list1, data);
cout << "删除后单链表 2 如下" << endl;
tmp.Print(list1);
cout << endl;
}
else
{
cout << " " << endl;
}
break;
case 6://倒置
cout << "请选择进行删除操作的链表 1/2 " << endl;
cin >> n;
if (n == 1)
{
cout << "倒置前单链表如下" << endl;
tmp.Print(list);
cout << "倒置后单链表 1 如下" << endl;
list = tmp.Reverse(list);
tmp.Print(list);
}
if (n == 2)
{
cout << "倒置前单链表如下" << endl;
tmp.Print(list1);
cout << "倒置后单链表 2 如下" << endl;
list1 = tmp.Reverse(list1);
tmp.Print(list1);
}
else
{
cout << " " << endl;
}
break;
case 7://表长
cout << "当前两表长为：" << endl;
cout << "表 1 :" << endl;
tmp.Length(list);
cout << "表 2 :" << endl;
tmp.Length(list1);
break;
case 8://合并
cout << "合并后链表为:" << endl;
{Single_List* merge_list = tmp.Merge(list, list1);
tmp.Print(merge_list);
cout << endl; }
break;
default:
system("cls");
break;
}
}
system("pause");
return 0;
}
运行状况如下
