【数据结构】单链表基本操作(C++实现)

代码主体使用结构体＋类+模板进行实现。

1.LinkList.h

//LinkList.h #pragma once #include<iostream> using namespace std; template<class T> struct Node //结点结构 { T data; //结点数据域 Node*link;//指针域 Node() { link = NULL; } Node(T e, Node *next = NULL) { data = e; link = next; } }; template<class T> class LinkList //带表头结点的单链表类 { private: Node<T> *head; //链表指针 public: LinkList(); //构造带表头结点的空单链表 LinkList(T data[], int mSize);//构造有mSize个元素的单链表 ~LinkList() { Clear(); } //析构函数 bool Insert(int pos, const T&x); //在单链表第pos个元素前插入元素x bool Remove(int pos, T&x); //删除单链表第pos个元素 bool Replace(int pos, const T&x); //将修改单链表第pos个元素为x int Length()const; //求表长等不改变数据值，只是读取建议使用常函数const末尾标识 bool IsEmpty() const; //判空操作 void Clear(); //清空操作 void Output() const; //输出链表 bool search(const T&x) const;//查找元素x在表中是否存在 };

3单链表.cpp

//单链表.cpp #include"LinkList.h" #include<iostream> using namespace std; template<class T> LinkList<T>::LinkList() {//初始化链表 head = new Node<T>; head->link = NULL; } template<class T> LinkList<T>::LinkList(T data[], int mSize) {//初始化链表元素 head = new Node<T>; head -> link = NULL; head->data = data[0]; Node < T> *end = head; for (int i = 0; i < mSize; i++) { Node<T> *p = new Node<T>; p->data = data[i]; p->link = NULL; end->link = p; end = p; } } template<class T> bool LinkList<T>::Insert(int pos, T&x) {//插入元素 int cont = 1; Node<T>*p = head;//初始指向头节点 bool flag = false;//初始flag为false while (p != NULL && cont <= pos - 1) { if (cont == pos - 1)//如果p在目标节点处 { Node<T> *add = new Node<T>;//增加节点add add->data = x;//新增节点数据域设为x add->link = p->link;//指针域指向原来p所指向的位置 p->link = add;//p重新指向add新增节点 flag = true; break; } else {//如果没到目标节点，指针一直移动并且计数器++ cont++; p = p->link; } } return flag; } template<class T> bool LinkList<T>::Remove(int pos, T&x)//删除元素 { int cont = 1; Node<T> *p = head;//p指向头节点 bool flag = false; while (p!=NULL&&cont<=pos-1) { if (cont == pos - 1) { Node<T> *del = p->link; p->link=p->link->link;//删除节点（2）后p指向初始节点（1）后面（2）的后面那个元素（3） x = del->data; delete del; flag = true; break; } else { cont++; p = p->link; } } return flag; } template<class T> bool LinkList<T>::Replace(int pos, T&x)//修改元素 { int cont = 1; Node<T>* p = head; bool flag = false; while (p != NULL && cont <= pos) { if (cont == pos) { p->data = x; flag = true; } else { cont++; p = p->link; } } return flag; } template<class T> int LinkList<T>::Length()const//求表长 { int cont = 0; Node<T>*p = head; while (p != NULL) { cont++; p = p->link; } return cont; } template<class T> void LinkList<T>::Clear() {//清空链表 if (head != NULL) { Node<T> *p; p = head->link; while(p != NULL) { Node<T> *del = p; p = p->link; delete del; } head = NULL; } } template<class T> bool LinkList<T>::IsEmpty()const//判空 { return head == NULL;//HEAD为空则返回true } template<class T> bool LinkList<T>::Search(const T&x)const//查询 { bool flag = false; Node<T>*p = head; while (p!=NULL) { if (p->data == x) { flag = true; break; } else { p = p->link; } } return flag; } template<class T> void LinkList<T>::OutPut()const//输出链表 { Node<T> *p = head; int cont = 0; while (p != NULL)\ { cout << p->data << ","; p = p->link; cont++; if (cont % 10 == 0) { cout << endl; } } cout << endl; }

3.测试.cpp

//测试.cpp #include"单链表.cpp" #include<ctime> void menu()//模拟菜单选项 { cout << "********************************************************" << endl; cout << "* 1 ------------输出链表 *" << endl; cout << "* 2 ------------插入元素 *" << endl; cout << "* 3 ------------删除元素 *" << endl; cout << "* 4 ------------销毁链表 *" << endl; cout << "* 5 ------------查找 *" << endl; cout << "* 0 ------------退出系统 *" << endl; cout << "********************************************************" << endl; } const int N = 20; int main() { srand((unsigned)time(NULL));//以系统当前时间初始化随机数发生器 int data[N]; for (int i = 0; i < N; i++) data[i] = rand() % 100;//用随机数发生器产生100以内的整数 LinkList<int> L(data, N);//创建N个元素的单链表 menu(); while (1) //模拟菜单工作方式 { int select; cout << "请输入您的选择："; cin >> select; switch (select) { case 1: //输出单链表 if (L.IsEmpty()) { cout << "链表为空！" << endl; } else L.OutPut(); break; case 2: //插入 int pos, elem; cout << "请输入插入位置："; cin >> pos; cout << "插入元素："; cin >> elem; if (L.Insert(pos, elem)) //插入成功 cout << "在第" << pos << "个元素前成功插入" << elem << endl; else //插入失败 cout << "插入位置不合法！" << endl; break; case 3: //删除 cout << "请输入删除位置："; cin >> pos; int x; if (L.Remove(pos, x))//删除单链表的第pos个元素 cout << "单链表的第" << pos << "个元素" << x << "已被删除。" << endl; else cout << "删除位置不合法！" << endl; break; case 4: //销毁链表 char OK; cout << "确定要销毁链表吗？（y/n）" << endl; cin >> OK; if (OK == 'y' || OK == 'Y') L.Clear(); break; case 5: //查找 cout << "请输入查找元素："; cin >> elem; if (L.Search(elem)) cout << "查找成功！" << endl; else cout << "查找失败！" << endl; break; case 0: //退出 exit(0); default: cout << "您输入的选项有误，请重新输入："; } } return 0; }

4.运行截图