/* 链表的操作
* 实现的功能有： 1.向链表头插入数据2.删除某个数据 3.查找链表中数据 4.正向输出链表5.反向输出链表 6.创建新链表并合并
* 实现代码如下：
* */
#include <iostream>
using namespace std;
struct Node {
int data;
Node *next;
Node *pre;
};
class LinkList {
public:
int size;
Node *head = NULL; //链表头结点
LinkList(); //构造方法
~LinkList(); //析构方法
int length(LinkList *l); //返回链表长度，传入一个链表指针
int getData(LinkList *l, int); //获得链表该位置的内容
Node *Create(int); //创建链表
Node *Insert(int); //向链表头插入数据
Node *Delete(int); //删除链表
void output(); //正向输出链表
void output2(); //反向输出链表
int Find(int); //查找链表中某一节点，返回位置
void changeData(LinkList *l, int a, int index); //改变链表某一位置的值，即将index位置的数据变为a
void sort(LinkList *l); //传入某一链表，对该链表进行排序
LinkList* merge(LinkList *l); //合并两链表，返回新链表
};
LinkList::LinkList() {
}
LinkList *LinkList::merge(LinkList *l) {
LinkList *newlist = new LinkList;
Node *p = head, *q, *m = newlist->head = NULL;
while (p != NULL) {
q = new Node;
q->data = p->data;
if (newlist->head == NULL) {
newlist->head = q;
q->next = NULL;
} else {
m->next = q;
q->pre = m;
q->next = NULL;
}
m = q;
p = p->next;
}
m->next = l->head;
newlist->size = this->size + l->size;
return newlist;
}
void LinkList::changeData(LinkList *list, int a, int index) {
if (index < 0 || index > list->size) {
cout << "Out of Bounds" << endl;
return;
}
Node *current = new Node;
current = list->head;
int j = 1;
if (index == 1) {
current->data = a;
} else {
while (current->next != NULL) {
current = current->next;
j++;
if (j == index)
break;
}
current->data = a;
}
}
int LinkList::getData(LinkList *list, int index) {
if (index < 0 || index > list->size) {
cout << "Out of Bounds" << endl;
return -1;
}
Node *current = new Node;
int result;
current = list->head;
int j = 1;
if (index == 1) {
result = current->data;
} else {
while (current->next != NULL) {
current = current->next;
j++;
if (j == index)
break;
}
result = current->data;
}
return result;
}
void LinkList::sort(LinkList *newlist) {
int temp = 0;
for (int i = 0; i < newlist->size - 1; i++) {
for (int j = i + 1; j < newlist->size; j++) {
if (getData(newlist, i + 1) > getData(newlist, j + 1)) {
temp = getData(newlist, i + 1);
changeData(newlist, getData(newlist, j + 1), i + 1);
changeData(newlist, temp, j + 1);
}
}
}
}
Node* LinkList::Create(int d) {
size = d;
cout << "请输入" << d << "个元素来创建链表" << endl;
Node *p = new Node, *q;
p = head;
for (int i = 0; i < d; i++) {
int input;
cin >> input;
q = new Node;
q->data = input;
if (head == NULL) {
head = q;
q->next = NULL;
} else {
p->next = q;
q->pre = p;
q->next = NULL;
}
p = q;
}
return head;
}
Node *LinkList::Insert(int x) {
Node *p, *q;
p = head;
q = new Node;
q->data = x;
head = q;
q->next = p;
p->pre = q;
size++;
return head;
}
Node *LinkList::Delete(int x) {
Node *p1, *p2;
p1 = head;
if (head == NULL) {
cout << "Null List" << endl;
return head;
}
while (p1->data != x && p1->next != NULL) {
p2 = p1;
p1 = p1->next;
}
if (p1->data == x) {
if (p1 == head) {
head = head->next;
} else {
if (p1->next == NULL) {
p2->next = NULL;
} else {
p1->next->pre = p2;
p2->next = p1->next;
}
}
delete p1;
} else
cout << "Not Found Number:" << endl;
size--;
return head;
}
int LinkList::Find(int x) {
Node *p;
p = head;
int index = 1;
while (p->data != x && p->next != NULL) {
p = p->next;
index++;
}
if (p->data == x)
return index;
else
return 0;
}
void LinkList::output() {
Node *p = head;
while (p != NULL) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
void LinkList::output2() {
Node *p = head;
while (p->next != NULL) {
p = p->next;
}
while (p != head) {
cout << p->data << " ";
p = p->pre;
}
cout << p->data << " ";
cout << endl;
}
int main() {
cout << "请输入第一个链表的大小" << endl;
int x;
cin >> x;
LinkList *a = new LinkList;
a->Create(x);
cout << "链表为:" << endl;
a->output();
while (true) {
cout << "您想进行什么操作？ 1.向链表头插入数据"
"2.删除某个数据 3.查找链表中数据 4.正向输出链表"
"5.反向输出链表 6.创建新链表并合并" << endl;
int w;
cin >> w;
switch (w) {
case 1: {
cout << "请输入要插入的数据" << endl;
int data;
cin >> data;
a->Insert(data);
cout << "插入后的链表是" << endl;
a->output();
break;
}
case 2: {
cout << "请输入要删除的数据" << endl;
int data;
cin >> data;
a->Delete(data);
cout << "删除后的链表:" << endl;
a->output();
break;
}
case 3: {
cout << "请输入要查找的数据，会输出它的位置" << endl;
int data;
cin >> data;
int index = a->Find(data);
cout << "当前链表为:" << endl;
a->output();
if (index == 0)
cout << "数字" << data << "不存在" << endl;
else
cout << "數字" << data << "的位置是" << index << endl;
break;
}
case 4: {
cout << "正向输出:" << endl;
a->output();
break;
}
case 5: {
cout << "反向输出" << endl;
a->output2();
break;
}
case 6: {
cout << "请输入新链表的数据个数" << endl;
LinkList *b = new LinkList;
int x;
cin >> x;
b->Create(x);
LinkList *c = new LinkList;
a->sort(a);
cout << "第一个链表:" << endl;
a->output();
cout << "第二个链表" << endl;
b->sort(b);
b->output();
c = a->merge(b);
c->sort(c);
cout << "合并并排序后新链表如下：" << endl;
c->output();
cout << "大小:" << c->size << endl;
break;
}
}
}
return 0;
}
测试样例：
/*
请输入第一个链表的大小
5
请输入5个元素来创建链表
4 5 7 9 10
链表为:
4 5 7 9 10
您想进行什么操作？ 1.向链表头插入数据2.删除某个数据 3.查找链表中数据 4.正向输出链表5.反向输出链表 6.创建新链表并合并
1
请输入要插入的数据
6
插入后的链表是
6 4 5 7 9 10
您想进行什么操作？ 1.向链表头插入数据2.删除某个数据 3.查找链表中数据 4.正向输出链表5.反向输出链表 6.创建新链表并合并
2
请输入要删除的数据
10
删除后的链表:
6 4 5 7 9
您想进行什么操作？ 1.向链表头插入数据2.删除某个数据 3.查找链表中数据 4.正向输出链表5.反向输出链表 6.创建新链表并合并
3
请输入要查找的数据，会输出它的位置
7
当前链表为:
6 4 5 7 9
數字7的位置是4
您想进行什么操作？ 1.向链表头插入数据2.删除某个数据 3.查找链表中数据 4.正向输出链表5.反向输出链表 6.创建新链表并合并
4
正向输出:
6 4 5 7 9
您想进行什么操作？ 1.向链表头插入数据2.删除某个数据 3.查找链表中数据 4.正向输出链表5.反向输出链表 6.创建新链表并合并
5
反向输出
9 7 5 4 6
您想进行什么操作？ 1.向链表头插入数据2.删除某个数据 3.查找链表中数据 4.正向输出链表5.反向输出链表 6.创建新链表并合并
6
请输入新链表的数据个数
3
请输入3个元素来创建链表
19 16 22
第一个链表:
4 5 6 7 9
第二个链表
16 19 22
合并并排序后新链表如下：
4 5 6 7 9 16 19 22
大小:8
您想进行什么操作？ 1.向链表头插入数据2.删除某个数据 3.查找链表中数据 4.正向输出链表5.反向输出链表 6.创建新链表并合并
*/
