//单链表的操作C++实现
#include <iostream>
using namespace std;//使用命名空间
template<typename dataType> //定义一个数据类型模板
class linkedList{//定义单链表类
struct Node{
dataType data;
Node *next;
Node(const dataType &x,Node *p=NULL):data(x),next(p){}
Node():next(NULL){}
~Node(){}
};
Node *head;
Node *move(int i){//返回第i个节点的地址
i=i-1;
Node * p = head;
while (i-- >= 0) p = p->next;
return p;
}
int currentLength;
public:
linkedList();//构建一个单链表
~linkedList();//销毁一个单链表
void clear();
void insertTail(const dataType &x);// 链表尾部插入元素
void insertPosition(int position,const dataType &x);//链表指定位置插入元素
void remove(int position);//链表删除指定位置元素
dataType visit(int position);// 查找指定位置元素
int search(const dataType &x);//查找某个元素值是否存在
void traverse();//打印链表
void reverse();//逆序链表
};
template<typename dataType>
linkedList<dataType>::linkedList(){//创建一个空的单链表，带表头
head=new Node;
currentLength=0;
}
template<typename dataType>
linkedList<dataType>::~linkedList(){//把单链表清空，再删除头节点
clear();
delete head;
}
template<typename dataType>
void linkedList<dataType>::clear(){//把单链表清空
Node *p = head->next, *tmp;
while (p != NULL)
{
tmp = p;
p = p->next;
delete tmp;
}
head->next = NULL;
currentLength = 0;
}
template<typename dataType>
void linkedList<dataType>::insertTail(const dataType &x){
Node * newNode = new Node; //定义一个Node结点指针newNode
newNode->next = NULL; //定义newNode的数据域和指针域
newNode->data = x;
Node *p=head; //定义指针p指向头结点
if (head == NULL) { //当头结点为空时，设置newNode为头结点
head = newNode;
}
else //循环知道最后一个节点，将newNode放置在最后
{
while (p->next != NULL)
{
p = p->next;
}
p->next = newNode;
}
currentLength++;
}
template<typename dataType>
void linkedList<dataType>::insertPosition(int position,const dataType &x){
Node * pos;
pos = move(position - 1);
pos->next = new Node(x, pos->next);
currentLength++;
}
template<typename dataType>
void linkedList<dataType>::remove(int position) {
Node * pos = move(position-1 ), * tmp;
tmp = pos->next;
pos->next = tmp->next;
delete tmp;
currentLength--;
}
template<typename dataType>
int linkedList<dataType>::search(const dataType &x){
Node * pos = head;
for (int num = 0; num <=currentLength; num++)
//while(pos!=NULL)
{
if (pos->data == x) return num;
pos = pos->next;
}
return -1;
}
template<typename dataType>
dataType linkedList<dataType>::visit(int position){
return move(position)->data;
}
template<typename dataType>
void linkedList<dataType>::traverse(){
Node *p = head->next;
cout<<"输出链表：";
while (p != NULL)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
cout<<endl;
}
template<typename dataType>
void linkedList<dataType>::reverse(){
Node * p = head->next;//头结点之后的第1个节点
Node * q = head->next->next;//头结点之后的第2节点
Node * m = head->next->next->next;//头结点之后的第3个节点
p->next = NULL;//将头接点之后的第1个节点的next指针置为空
//根据m是否为空来判断 以此逆序每一个节点
while(m){
q->next = p;
p = q;
q = m;
m = m->next;
}
//将最后一个节点逆序
q->next = p;
//将头从新指向新的的第1个节点(之前的最后一个节点)
head ->next = q;
}
//template<typename dataType>
int main(){
//template<typename dataType>
linkedList<double> l;
int i;
double d;
int p;
int n;
cout<<endl;
cout << "0.创建一个链表 1.尾部插入元素 2.指定位置插入元素\n";
cout << "3.删除指定位置元素 4.查找指定位置的元素 5.查找某个元素\n";
cout << "6.逆序链表 7.删除链表 其他数字.退出程序\n";
cout <<endl ;
do {
cout<<"请输入要执行的操作：";
cin>>i;
switch(i){
case 0:
cout<<"创建一个链表：";
cout<<"请输入单链表的长度: ";
cin>>n;
for (int i=0; i<n; i++){
cin>>d;
l.insertTail(d);
}
l.traverse();break;
case 1:
cout<<"尾部插入元素：";
cout << "请输入要在尾部插入的值: ";
cin>>d;
l.insertTail(d);
l.traverse();break;
case 2:
cout<<"指定位置插入元素：" ;
cout << "请输入位置: ";
cin>>p;
cout << "请输入要在插入的值: ";
cin>>d;
l.insertPosition(p,d);
l.traverse();break;
case 3:
cout<<"删除指定位置元素：";
cout << "请输入位置: ";
cin>>p;
l.remove(p);
l.traverse();break;
case 4:
cout<<"查找指定位置的元素：";
cout<<"请输入需要查找的位置：";
cin>>p;
cout<<"#"<<p<<": "<<l.visit(p)<< "\n";
cout<<endl;
break;
case 5:
cout<<"查找某个元素：";
cout << "请输入需要查找的数据：";
cin >>d;
if (l.search(d) == -1)
cout << "数据不存在\n";
else{
cout << "值为" <<d<< "的数据存在,"<<"位置为"<< l.search(d)<<"\n";
}
cout<<endl;
break;
case 6:
cout<<"逆序链表：";
l.reverse();
l.traverse();
break;
case 7:
cout<<"链表已删除";
l.~linkedList();cout<<endl<<endl;break;
default:
cout<<"测试结束";cout<<endl<<endl ;
break;
}
}while(i==0||i==1||i==2||i==3||i==4||i==5||i==6||i==7);
system("pause") ;
cout<<"主程序结束" <<endl;
return 0;
}
彭总的做法
/一、单链表类头文件：
#pragma once
#include<iostream>
#include<fstream>
//定义节点
//定义链表的类模板
template <typename T>
class linked_list
{
private:
struct node {
T data;
node * next;
};
node * phead;
int isize;
public:
linked_list(); //构造函数
~linked_list(); //析构函数
void insert_tail(T a);//尾部插入数据
void insert(T a,int n);//指定位置插入数据
bool delete_element(int n);//指定位置删除数据
T find_th(int k);//查找指定位置的数据，如不存在报错
int find_x(T x);//查找指定数据，如不存在返回-1
void show();//打印链表
void reverse();//逆序链表
void menu();
};
//构造函数
template <typename T>
linked_list<T>::linked_list() :phead(NULL), isize(0)
{
phead = new node;
phead->next = NULL;
}
//析构函数
template <typename T>
linked_list<T>::~linked_list()
{
node * temp = NULL;
node * p = phead->next;
while (p != NULL)
{
temp = p->next;
delete p;
p = temp;
}
delete temp;
temp = NULL;
delete phead;
p = NULL;
isize = 0;
}
//尾部插入数据
template <typename T>
void linked_list<T>::insert_tail(T a)
{
node * temp = new node;
node * p = phead;
temp->data = a;
temp->next = NULL;
while (p->next != NULL)
{
p = p->next;
}
p->next = temp;
isize++;
temp = NULL;
p = NULL;
}
//指定位置插入数据
template <typename T>
void linked_list<T>::insert(T a, int n)
{
using std::cout;
using std::endl;
if (n<1 || n>isize)
{
cout << "输入错误！！！" << endl;
}
else
{
node * temp = new node;
temp->data = a;
node *p = phead;
for (int i = 1; i < n; i++)
{
p = p->next;
}
temp->next = p->next;
p->next = temp;
isize++;
}
}
//指定位置删除数据
template <typename T>
bool linked_list<T>::delete_element(int n)
{
using std::cout;
using std::endl;
if (n<1 || n>isize )
{
cout << "输入错误！！！" << endl;
return false;
}
else
{
node * p = phead;
for (int i = 1; i < n; i++)
{
p = p->next;
}
node * temp;
temp = p->next;
p->next = p->next->next;
delete temp;
temp = NULL;
isize--;
return true;
}
}
//查找指定位置的数据，如不存在报错
template <typename T>
T linked_list<T>::find_th(int k)
{
using std::cout;
using std::endl;
if (k<1 || k>isize )
{
cout << "输入错误！！！" << endl;
return -1;
}
else
{
node * p = phead;
for (int i = 1; i < k; i++)
{
p = p->next;
}
return p->next->data;
}
}
//查找指定数据，如不存在返回-1
template <typename T>
int linked_list<T>::find_x(T x)
{
node * p = phead->next;
int i = 1;
while (p != NULL)
{
if (p->data == x)
{
return i;
}
p = p->next;
i++;
}
p = NULL;
return -1;
}
//打印链表
template <typename T>
void linked_list<T>::show()
{
using std::cout;
using std::endl;
int count = 1;
node *temp = NULL;
temp = phead->next;
cout << "当前链表： " << endl;
while (temp != NULL)
{
cout << "#" << count << ": " << temp->data << " ";
if (count % 5 == 0)
cout << endl;
temp = temp->next;
count++;
}
temp = NULL;
cout << endl;
}
//逆序链表
template <typename T>
void linked_list<T>::reverse()
{
node * prenode = NULL;
node * curnode = NULL;
node * nextnode = NULL;
if (isize == 1 || isize == 0)
{
return;
}
else if (isize >= 2)
{
prenode = phead->next;
curnode = prenode->next;
nextnode = curnode->next;
prenode->next = NULL;
while (nextnode != NULL)
{
curnode->next = prenode;
prenode = curnode;
curnode = nextnode;
nextnode = nextnode->next;
}
curnode->next = prenode;
phead->next = curnode;
}
prenode = NULL;
curnode = NULL;
nextnode = NULL;
}
template <typename T>
void linked_list<T>::menu()
{
using std::cout;
using std::endl;
cout << "***********************************************\n";
cout << "功能选择如下：\n";
cout << "0.创建一个链表 1.在尾部插入一个元素 2.在指定位置插入一个元素\n";
cout << "3.删除指定位置元素 4.查找指定位置的元素 5.查找某个元素是否存在\n";
cout << "6.逆序链表 7.打印链表 8.删除链表 \n";
cout << "9.退出程序\n";
cout << "***********************************************\n";
cout << "请根据菜单选择：";
}
///二、单链表类主函数：
#include"single linked list.h"
int main()
{
using std::cin;
using std::cout;
using std::endl;
linked_list<double> mylist;
char choice;
int x;
double y;
mylist.menu();
while (cin >> choice)
{
switch (choice)
{
case'0':
cout << "请输入链表的元素个数N：\n";
cin >> x;
cout << "请输入元素数据：\n";
for (int i = 0; i < x; i++)
{
cin >> y;
mylist.insert_tail(y);
}
mylist.show();
break;
case'1':
cout << "请输入在尾部插入的数据:\n";
cin >> y;
mylist.insert_tail(y);
mylist.show();
break;
case'2':
cout << "请输入位置: \n";
cin >> x;
cout << "请输入数据：\n";
cin >> y;
mylist.insert(y, x);
mylist.show();
break;
case'3':
cout << "请输入需要删除数据的位置：\n";
cin >> x;
if (mylist.delete_element(x) == true)
{
cout << "删除成功\n";
}
else
{
cout << "删除失败\n";
}
mylist.show();
break;
case'4':
cout << "请输入需要查找数据的位置：\n";
cin >> x;
cout << "#" << x << ": " << mylist.find_th(x) << "\n";
break;
case'5':
cout << "\n请输入需要查找数据：\n";
cin >> y;
if (mylist.find_x(y) == -1)
cout << "数据不存在\n";
else
{
cout << "\n值为" <<y << "存在,"<<"位置为"<< mylist.find_x(y)<<"\n";
}
break;
case'6':
mylist.reverse();
cout << "\n逆置成功\n";
mylist.show();
break;
case'7':
mylist.show();
break;
case'8':
mylist.~linked_list();
break;
case'9':
goto exit;
default:
break;
}
cout << "请根据菜单选择：";
//mylist.menu();
}
exit:
cout << "Bye Bye!!!!!";
cin.get();
cin.get();
return 0;
}
