看别人写的，自己又写一遍。仅供自己学习。
//单链表的操作
#include<iostream> using namespace std; typedef int DataType; #define Node ElemType #define ERROR NULL //构建一个节点类 class Node{ public: int data;//数据域 Node *next;//指针域 }; //构建一个单链表类 class LinkList{ private: ElemType *head;//头结点 public: LinkList();//构造函数 ~LinkList();//析构函数 void CreateLinkList(int n);//创建一个单链表 void TravalLinkList();//遍历线性表 int GetLength();//获取线性表长度 bool IsEmpty();//判断单链表是否为空 ElemType *Find(DataType data);//查找节点 void InsertElemAtEnd(DataType data);//在尾部插入指定元素 void InsertElemAtIndex(DataType data,int n);//在指定位置插入指定元素 void InsertElemAtHead(DataType data);//在头部插入指定元素 void DeleteElemAtEnd();//删除尾部元素 void DeleteAllElem();//删除全部元素 void DeleteElemAtPoint(DataType data);//删除指定的数据 void DeleteElemAtHead();//删除头部节点 }; //初始化单链表 LinkList::LinkList()//构造函数 { head = new ElemType; head->data = 0;//将头结点的数据域定义为0 head->next = NULL;//将头节点的指针域设置为null } //销毁单链表 LinkList::~LinkList()//析构函数 { delete head; //删除头结点 } //创建一个单链表 void LinkList::CreateLinkList(int n) { ElemType *pnew,*ptemp; ptemp = head; if(n<0) { cout<<"输入的节点个数有误"<<endl; } for(int i = 0;i<n;i++) { pnew = new ElemType; cout<<"请输入第"<<i+1<<"个值:"; cin>>pnew->data;//输入新节点的数据域 pnew->next = NULL;//新节点下一个地址为null ptemp->next = pnew;//将当前节点的指针域指向新节点 ptemp = pnew; //将当前节点设置为新节点 } } //遍历单链表 void LinkList::TravalLinkList() { if(head == NULL||head->next == NULL) { cout<<"链表为空表"<<endl; } ElemType *p = head;//令指针指向头结点 while(p->next!=NULL)//当指针指向的下一个地址不为空 { p = p->next;//p指向p的下一个地址 cout<<p->data<<" "; } } //获取单链表的长度 int LinkList::GetLength() { int count = 0; ElemType *p = head->next; while(p!=NULL) { count++; p = p->next; } return count; } //判断链表是否为空 bool LinkList::IsEmpty() { if(head->next == NULL) { return true; } return false; } //查找与元素data相同的节点 ElemType * LinkList::Find(DataType data) { ElemType *p = head; if(p==NULL||p->next==NULL)//为空表时 { cout<<"此单链表为空表"<<endl; return ERROR; } else{ while(p->next!=NULL) { if(p->data==data) { return p; } p = p->next; } } } //在尾部插入指定元素 void LinkList::InsertElemAtEnd(DataType data) { ElemType *newNode = new ElemType; newNode->data = data; newNode->next = NULL; ElemType *p = head; if(head == NULL)//如果头结点为空时，设置newNode为头结点 { head = newNode; } else { while(p->next!=NULL) p = p->next; p->next = newNode; } } //在指定位置插入指定元素 void LinkList::InsertElemAtIndex(DataType data,int n) { if(n<1||n>GetLength()) { cout<<"输入的值有误"<<endl; } else{ ElemType *ptemp = new ElemType; ptemp->data = data; ElemType *p = head;//创建一个指针指向头结点 int i = 1; while(n>i) { p = p->next; i++; } ptemp->next = p->next; p->next = ptemp; } } //在头部插入指定元素 void LinkList::InsertElemAtHead(DataType data) { ElemType *newNode = new ElemType;//定义一个Node节点指针newNode newNode->data = data; ElemType *p = head; if(head == NULL) { head = newNode; } newNode->next = p->next; p->next = newNode; } //在尾部删除元素 void LinkList::DeleteElemAtEnd() { ElemType *p = head; ElemType *ptemp = NULL; if(p->next = NULL) { cout<<"单链表为空"<<endl; } else{ while(p->next!=NULL) { ptemp = p; p = p->next; } delete p; //p = NULL; ptemp->next = NULL; } } //删除所有数据 void LinkList::DeleteAllElem() { ElemType *p = head->next; ElemType *ptemp = new ElemType; while(p!=NULL) { ptemp = p; p = p->next; head->next = p; ptemp->next = NULL; delete ptemp; } head->next = NULL;//头结点的下一个节点指向NULL,即为空表 } //删除指定元素 void LinkList::DeleteElemAtPoint(DataType data) { ElemType *ptemp = Find(data);//返回元素的序号 if(ptemp == head->next)//判断是否是头结点的下一个节点 { DeleteElemAtHead(); } else{ ElemType *p = head; while(p->next != ptemp) { p = p->next; } p->next = ptemp->next; delete ptemp; //ptemp = NULL; } } //在头部删除节点 void LinkList::DeleteElemAtHead() { ElemType *p = head; if(p == NULL || p->next == NULL)//为空表 { cout<<"单链表为空表"<<endl; } else { ElemType *ptemp = NULL; p = p->next; ptemp = p->next; delete p; //p = NULL; head->next = ptemp; } } //测试函数 int main() { LinkList list; int i; cout << "1.创建单链表 2.遍历单链表 3.获取单链表的长度 4.判断单链表是否为空 5.获取节点\n"; cout << "6.在尾部插入指定元素 7.在指定位置插入指定元素 8.在头部插入指定元素\n"; cout<<"9.在尾部删除元素 10.删除所有元素 11.删除指定元素 12.在头部删除元素 0.退出" << endl; do { cout<<"请输入要执行的操作："; cin>>i; switch(i) { case 1: int n; cout<<"请输出要创建单链表的长度："; cin>>n; list.CreateLinkList(n); break; case 2: list.TravalLinkList(); break; case 3: cout<<"该单链表长度为"<<list.GetLength()<<endl; break; case 4: if(list.IsEmpty() == 1) cout<<"单链表是空表"<<endl; else cout<<"链表不是空表"<<endl; break; case 5: DataType data; cout<<"请输入要获取节点的值:"; cin>>data; cout<<"该节点的值为" << list.Find(data)->data << endl; break; case 6: DataType endData; cout << "请输入要在尾部插入的值: "; cin >> endData; list.InsertElemAtEnd(endData); break; case 7: DataType pointData; int index; cout<<"请输入要插入的数据:"; cin >> pointData; cout << "请输入要插入数据的位置: "; cin >> index; list.InsertElemAtIndex(pointData, index); break; case 8: DataType headData; cout << "请输入要在头部插入的值: "; cin >> headData; list.InsertElemAtHead(headData); break; case 9: list.DeleteElemAtEnd(); break; case 10: list.DeleteAllElem(); break; case 11: DataType pointDeleteData; cout << "请输入要删除的数据: "; cin >> pointDeleteData; list.DeleteElemAtPoint(pointDeleteData); break; case 12: list.DeleteElemAtHead(); break; default: break; } } while (i != 0); return 0; }