数据结构

---

单链表操作案例

  关于单链表的一些描述可以参考数据结构-第二章（5）-链式存储结构和数据结构-第二章（6）-单链表基本操作的实现

一、制作界面

//界面制作
void showMenu()
{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 << "*****  [9]----对链表销毁----*******" << endl;cout << "*****  [10]---单链表的合并--*******" << endl;cout << "***********************************" << endl;
}

二、链表类型定义

typedef struct Lnode//声明结点的类型和指向结点的指针类型
{ElemType data;//结点的数据域struct Lnode* next;//结点的指针域,next中存的是地址,指向Lnode这个类型的指针
}Listnode, * Linklist;//linklist为指向结构体Lnode的指针类型,里面存了个地址（Lnode变量的地址）

三、创建链表

头插法：

void head_insert(Linklist& L)
{int n;std::cout << "请输入单链表元素个数：";std::cin >> n;for (int i = n; i > 0; --i){Listnode* p = new Listnode;cin >> p->data;p->next = L->next;//插入到表头L->next = p;}
}

尾插法：

void tail_insert(Linklist& L)
{int n;std::cout << "请输入单链表元素个数：";std::cin >> n;Listnode* r = L;//尾指针r指向头结点for (int i = 0; i < n; i++){Listnode* p = new Listnode;std::cin >> p->data;p->next = NULL;r->next = p;//插入到表尾r = p;//r指向新的尾结点}
}

创建单链表

void CreatList(Linklist& L)
{//1、生成新结点作为头结点L = new Listnode;//2、头结点的指针域next置空L->next = NULL;std::cout << "单链表已初始化，请创建单链表" << std::endl;std::cout << "输入1为选择头插法建立单链表，输入2为选择尾插法建立单链表" << std::endl;int select;std::cin >> select;if (select == 1){head_insert(L);}else if (select == 2){tail_insert(L);}else{std::cout << "你的输入有误，请重新输入！" << std::endl;}}//CreatList

四、单链表判空

简单写法：

  这种写法在没创建单链表的条件下会报错!

void ListEmpty(Linklist& L)
{if (L->next)//非空{std::cout << "这不是一个空链表" << endl;}else{std::cout << "这是一个空链表" << endl;}
}

完善写法：

void ListEmpty(Linklist& L)
{if (L == NULL){std::cout << "链表不存在，请尝试选择1创建单链表" << std::endl;return;}if (L->next) std::cout << "这不是一个空链表" << endl;else std::cout << "这是一个空链表" << endl;
}

五、求链表长度

void ListLength(Linklist& L)
{/*Linklist p;p = L;*/Listnode* p = L;if (p == NULL){std::cout << "链表不存在，请尝试选择1创建单链表" <<std::endl;return;}int i = 0;while (p){p = p->next;i++;}std::cout << "单链表表长为：" << i - 1 << std::endl;
}//ListLength

六、对链表取值

  和上面不同的是，后面的形参类型为指针，但意思其实一样。

void GetElem(Listnode* L)
{Listnode* p;ElemType e;int i;if (L == NULL){std::cout << "链表不存在，请尝试选择1创建单链表" << std::endl;return;}std::cout << "请输入你要取出单链表元素的位置：";std::cin >> i;p = L->next; //变量初始化，p指向第一个节点int j = 1;while (p && j < i){p = p->next;++j;}if (!p || j > i){std::cout << "链表中不存在第" << i << "个节点，请重新输入！" << std::endl;//链表中不存在第i个节点return;}e = p->data; //取到第i个元素std::cout << "取出的元素为:" << e << std::endl;
}//GetElem

七、单链表的查找

	void LocateElem(Listnode* L){Listnode* p;ElemType e;int i = 0;if (L == NULL){std::cout << "链表不存在，请尝试选择1创建单链表" << std::endl;return;}p = L;std::cout << "请输入要查找的元素：";std::cin >> e;while (p && p->data != e){i++;p = p->next;}if (p) std::cout << "所找元素的位置为：" << i << std::endl; else std::cout << "所找的元素不存在，请重新选择！" << std::endl; }//LocateElem

八、单链表的插入

void ListInsert(Listnode* L)
{//在单链表L的第i个结点前插入值为e的新结点Listnode* p, *s, *q;int i, j;ElemType e;if (L == NULL){std::cout << "链表不存在，请尝试选择1创建单链表" << std::endl;return;}p = L; j = 0;std::cout << "请输入插入节点的位置及插入的元素：";std::cin >> i >> e;while (p && j < i - 1){ //查找第i- 1个节点，并令指针p指向该节点p = p->next; ++j;}//whileif (!p || j > i - 1){std::cout << "参数不合法，i小于1或者大于表长加1" << std::endl; return;}s = new Listnode;if (!s) exit(1); //存储空间失败s->data = e; //创建新元素节点s->next = p->next; p->next = s; //修改指针std::cout << "插入后的单链表：";q = L->next;while (q){std::cout << q->data << ' ';q = q->next;}std::cout << std::endl;
}//ListInsert

九、单链表的删除

void ListDelete(Listnode* L)
{//删除单链表L的第i个元素元素，输出删除元素后的顺序表Listnode *p, *q, *r;int i, j;if (L == NULL){std::cout << "链表不存在，请尝试选择1创建单链表" << std::endl;return;}std::cout << "请输入删除节点的位置：";std::cin >> i;p = L; j = 0;while (p->next && j < i - 1){ //寻找第i个节点，并令指针p指向其前驱p = p->next; ++j;}//whileif (!(p->next) || j > i - 1){std::cout << "删除位置不合法"; //删除位置不合法return;}q = p->next; p->next = q->next; //修改指针delete(q); //释放节点空间std::cout << "删除后的单链表：";r = L->next;while (r){std::cout << r->data << ' ';r = r->next;}std::cout << std::endl;
}//ListDelete

十、清空单链表

void ClearList(Listnode* L)
{if (L == NULL){std::cout << "链表不存在" << std::endl;return;}Listnode* p, * q;p = L->next;while (p){q = p -> next;delete p;p = q;}L->next = NULL;std::cout << "单链表已清空" << std::endl;
}

十一、销毁单链表

void DestroyList(Listnode* L)
{if (L == NULL){std::cout << "链表不存在，请尝试选择1创建单链表" << std::endl;return;}Listnode* p;while (L){p = L;L = L->next;delete p;}//whileL = NULL; std::cout << "链表已销毁" << std::endl;
}//DestroyList

十二、合并单链表

void MergeList()
{//按值排序的单链表La,Lb,归并为Lc后也按值排序Linklist La, Lb, Lc, pa, pb, pc, ra, rb, q;int m, n, j;std::cout << "请输入单链表La元素个数：";std::cin >> m;La = new Listnode;ra = La;if (!La) exit(0); //存储空间分配失败std::cout << "请输入单链表La的元素：";for (j = 0; j < m; j++){pa = new Listnode; //生成新节点std::cin >> pa->data; //输入元素值ra->next = pa; ra = pa; //插入到表头}ra->next = NULL;std::cout << "请输入单链表Lb元素个数：";std::cin >> n;Lb = new Listnode;rb = Lb;if (!Lb) exit(0); //存储空间分配失败std::cout << "请输入单链表Lb的元素：";for (j = 0; j < n; j++){pb = new Listnode; //生成新节点std::cin >> pb->data; //输入元素值rb->next = pb; rb = pb; //插入到表头}rb->next = NULL;pa = La->next; pb = Lb->next; Lc = pc = La; q = Lc->next;while (pa && pb){if (pa->data <= pb->data){pc->next = pa; pc = pa; pa = pa->next;}else{pc->next = pb; pc = pb; pb = pb->next;}}pc->next = pa ? pa : pb;delete Lb; //释放Lb头节点j = 0;std::cout << "合并后的单链表为：";while (j < m + n){std::cout << q->data << ' ';q = q->next;j++;}std::cout << std::endl;
}//MergeList

完整版

#include<iostream>
#include<string>
#include <stdlib.h>
using namespace std;
//界面制作
void showMenu()
{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 << "*****  [9]----对链表销毁----*******" << endl;cout << "*****  [10]---单链表的合并--*******" << endl;cout << "***********************************" << endl;
}typedef int ElemType;typedef struct Lnode//声明结点的类型和指向结点的指针类型
{ElemType data;//结点的数据域struct Lnode* next;//结点的指针域,next中存的是地址,指向Lnode这个类型的指针
}Listnode, * Linklist;//linklist为指向结构体Lnode的指针类型,里面存了个地址（Lnode变量的地址）void CreatList(Linklist& L);
void ListEmpty(Linklist& L);
void ListLength(Linklist& L); 
void GetElem(Listnode* L);
void LocateElem(Listnode* L);
void ListInsert(Listnode* L);
void ListDelete(Listnode* L);
void ClearList(Listnode* L);
void DestroyList(Listnode* L);
void MergeList();int main(void)
{Linklist L;L = NULL;int select;while (true){showMenu();std::cout << "请输入您的选择：";std::cin >> select;switch (select){case 0:std::cout << "已退出系统" << std::endl;break;case 1: CreatList(L);break;case 2: ListEmpty(L);break;case 3:ListLength(L);break;case 4:GetElem(L);//取值break;case 5:LocateElem(L);break;case 6:ListInsert(L);break;case 7:ListDelete(L);break;case 8:ClearList(L);break;case 9:DestroyList(L);break;case 10:MergeList();break;default:std::cout << "无效选项!" << std::endl; system("pause");}}	}void head_insert(Linklist& L)
{int n;std::cout << "请输入单链表元素个数：";std::cin >> n;for (int i = n; i > 0; --i){Listnode* p = new Listnode;cin >> p->data;p->next = L->next;//插入到表头L->next = p;}
}
void tail_insert(Linklist& L)
{int n;std::cout << "请输入单链表元素个数：";std::cin >> n;Listnode* r = L;//尾指针r指向头结点for (int i = 0; i < n; i++){Listnode* p = new Listnode;std::cin >> p->data;p->next = NULL;r->next = p;//插入到表尾r = p;//r指向新的尾结点}
}//尾插法建立单链表
void CreatList(Linklist& L)
{//1、生成新结点作为头结点L = new Listnode;//2、头结点的指针域next置空L->next = NULL;std::cout << "单链表已初始化，请创建单链表" << std::endl;std::cout << "输入1为选择头插法建立单链表，输入2为选择尾插法建立单链表" << std::endl;int select;std::cin >> select;if (select == 1){head_insert(L);}else if (select == 2){tail_insert(L);}else{std::cout << "你的输入有误，请重新输入！" << std::endl;}}//CreatListvoid ListEmpty(Linklist& L)
{if (L == NULL){std::cout << "链表不存在，请尝试选择1创建单链表" << std::endl;return;}if (L->next) std::cout << "这不是一个空链表" << endl;else std::cout << "这是一个空链表" << endl;
}void ListLength(Linklist& L)
{Listnode* p = L;if (p == NULL){std::cout << "链表不存在，请尝试选择1创建单链表" <<std::endl;return;}int i = 0;while (p){p = p->next;i++;}std::cout << "单链表表长为：" << i - 1 << std::endl;
}//ListLengthvoid GetElem(Listnode* L)
{Listnode* p;ElemType e;int i;if (L == NULL){std::cout << "链表不存在，请尝试选择1创建单链表" << std::endl;return;}std::cout << "请输入你要取出单链表元素的位置：";std::cin >> i;p = L->next; int j = 1;while (p && j < i){ p = p->next;++j;}if (!p || j > i){std::cout << "链表中不存在第" << i << "个节点，请重新输入！" << std::endl;return;}e = p->data; std::cout << "取出的元素为:" << e << std::endl;
}//GetElemvoid LocateElem(Listnode* L){Listnode* p;ElemType e;int i = 0;if (L == NULL){std::cout << "链表不存在，请尝试选择1创建单链表" << std::endl;return;}p = L;std::cout << "请输入要查找的元素：";std::cin >> e;while (p && p->data != e){i++;p = p->next;}if (p) std::cout << "所找元素的位置为：" << i << std::endl; else std::cout << "所找的元素不存在，请重新选择！" << std::endl; }//LocateElemvoid ListInsert(Listnode* L)
{Listnode* p, *s, *q;int i, j;ElemType e;if (L == NULL){std::cout << "链表不存在，请尝试选择1创建单链表" << std::endl;return;}p = L; j = 0;std::cout << "请输入插入节点的位置及插入的元素：";std::cin >> i >> e;while (p && j < i - 1){ p = p->next; ++j;}if (!p || j > i - 1){std::cout << "参数不合法，i小于1或者大于表长加1" << std::endl; return;}s = new Listnode;if (!s) exit(1); //存储空间失败s->data = e; //创建新元素节点s->next = p->next; p->next = s; //修改指针std::cout << "插入后的单链表：";q = L->next;while (q){std::cout << q->data << ' ';q = q->next;}std::cout << std::endl;
}//ListInsertvoid ListDelete(Listnode* L)
{//删除单链表L的第i个元素元素，输出删除元素后的顺序表Listnode *p, *q, *r;int i, j;if (L == NULL){std::cout << "链表不存在，请尝试选择1创建单链表" << std::endl;return;}std::cout << "请输入删除节点的位置：";std::cin >> i;p = L; j = 0;while (p->next && j < i - 1){ //寻找第i个节点，并令指针p指向其前驱p = p->next; ++j;}if (!(p->next) || j > i - 1){std::cout << "删除位置不合法"; //删除位置不合法return;}q = p->next; p->next = q->next; //修改指针delete(q); //释放节点空间std::cout << "删除后的单链表：";r = L->next;while (r){std::cout << r->data << ' ';r = r->next;}std::cout << std::endl;
}//ListDeletevoid ClearList(Listnode* L)
{if (L == NULL){std::cout << "链表不存在" << std::endl;return;}Listnode* p, * q;p = L->next;while (p){q = p -> next;delete p;p = q;}L->next = NULL;std::cout << "单链表已清空" << std::endl;
}void DestroyList(Listnode* L)
{if (L == NULL){std::cout << "链表不存在，请尝试选择1创建单链表" << std::endl;return;}//销毁以L为头指针的单链表，释放链表中所有节点的空间Listnode* p;while (L){p = L;L = L->next;delete p;}L = NULL; std::cout << "链表已销毁" << std::endl;
}//DestroyListvoid MergeList()
{Linklist La, Lb, Lc, pa, pb, pc, ra, rb, q;int m, n, j;std::cout << "请输入单链表La元素个数：";std::cin >> m;La = new Listnode;ra = La;if (!La) exit(0); //存储空间分配失败std::cout << "请输入单链表La的元素：";for (j = 0; j < m; j++){pa = new Listnode; //生成新节点std::cin >> pa->data; //输入元素值ra->next = pa; ra = pa; //插入到表头}ra->next = NULL;std::cout << "请输入单链表Lb元素个数：";std::cin >> n;Lb = new Listnode;rb = Lb;if (!Lb) exit(0); //存储空间分配失败std::cout << "请输入单链表Lb的元素：";for (j = 0; j < n; j++){pb = new Listnode; //生成新节点std::cin >> pb->data; //输入元素值rb->next = pb; rb = pb; //插入到表头}rb->next = NULL;pa = La->next; pb = Lb->next; Lc = pc = La; q = Lc->next;while (pa && pb) {if (pa->data <= pb->data){pc->next = pa; pc = pa; pa = pa->next;}else{pc->next = pb; pc = pb; pb = pb->next;}}pc->next = pa ? pa : pb;delete Lb; j = 0;std::cout << "合并后的单链表为：";while (j < m + n){std::cout << q->data << ' ';q = q->next;j++;}std::cout << std::endl;
}//MergeList

总结

期待大家和我交流，留言或者私信，一起学习，一起进步！