赞
踩
- /* 链表的操作
- * 实现的功能有: 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.创建新链表并合并
- */
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。