///////////////////////////////////////////////////////////////// //日期：2014-11-03 //作者：Davis //功能：单链表的定义与操作实现 ///////////////////////////////////////////////////////////////// #pragma once template<class T> struct Node { T data; //数据域，存放表元素 Node *next; //指针域。指向下一个结点 }; template<class T> class linkList { private: Node<T> *Head; //链表头指针 public: //构造函数、创建空链表 linkList(void) { Head = new Node<T>; Head->next = NULL; } //析构函数、删除空链表 ~linkList(void) { Node<T> *p; while(Head) { p = Head;//从头节点开始，依次释放结点 Head = Head->next; delete p; } Head = NULL;//头结点指向空 } //创建具有n个元素的线性链表 void createList(int n) { //尾插法（正序）创建具有n个元素的线性表 Node<T> *p,*s; //设置工作指针，p指向尾结点 p=Head; cout<<"请依次输入"<<n<<"个元素值"<<endl; for(int i=1;i<=n;i++) { s = new Node<T>; //新建元素结点 cin>>s->data; //输入新建数据元素值 s->next = p->next; //新结点链入表尾 p->next = s; p = s; //p是工作指针 } } //在表中第i个位置插入元素 void Insert(int i,T e) { int j = 0; Node<T> *p; p = Head; //工作指针p指向头结点 while(p && j<i-1) //查找第i-1个结点 { p = p->next; j++; } if(!p || j>i-1)throw"位置异常"; else { Node<T> *s; s = new Node<T>; //创建新节点 s->data = e; s->next = p->next;//结点s链到p结点之后 p->next = s; } } T Delete(int i)//删除表中第i个元素 { T x; Node<T> *p,*q; p = Head; //从头结点开始查找 int j = 0; //计数器初始化 while(p->next && j<i-1)//p定位到删除结点的前驱 { p = p->next; j++; } if(!p->next || j>i-1)throw"位置异常";//删除位置不合理 else //删除位置合理 { q = p->next; //暂存删除结点位置 p->next = q->next;//从链表中摘除删除结点 x = q->data; //取删除数据元素的值 delete q; //释放删除点 return x; //返回删除元素的值 } } //获取第i个元素的值 T getElem(int i) { Node<T> *p; //设置工作指针 p = Head->next; //从首结点开始 int j = 1; //计数器初始化 while(p && j<i) //定位到第i个元素结点 { p = p->next; j++; } if(!p || j>i) { throw "位置异常"; } else //位置合理 { return p->data; } } //在链表中查找值为e的元素 int Locate(T e) { int j = 1; Node<T> *p; p = Head->next; while(p && p->data != e) { p = p->next; j++; } if(!p )//未找到，范围0 { return 0; } else //找到，返回位序 { return j; } } //返回元素e的前驱 T prior(T e) { Node<T> *p,*q; p = Head; q = p->next; while(q && q->data != e) { p = q; q = q->next; } if(p == Head) { throw "首元素，无前驱"; } else if(!q) { throw "元素不存在"; } else { return p->data; } } //测表空 int Empty() { if(Head->next == NULL) return 1; //空表返回1 else return 0; //非空表，返回0 } //测表长 int Length() { int len = 0; //计数器初始化 Node<T> *p; //设置头指针 p=Head; //指向头指针 while(p->next) { len++; p = p->next; } return len; //返回表长 } //输出表元素 void listDisplay() { Node<T> *p; p = Head->next; int i = 1; while(p) { cout<<i<<" "; cout<<p->data<<endl; p = p->next; i++; } } }; ///////////////////////////////////////////////////////////////// //功能：单链表类的测试 ////////////////////////////////////////////////////////////////// // linkList_Test.cpp : 定义控制台应用程序的入口点。 #include "stdafx.h" #include "linkList.h" #include "process.h"//exit() #include<iostream> using namespace std; char pause; typedef int T; int _tmain(int argc, _TCHAR* argv[]) { int i; T e,prior_e; linkList<int>L; //建立整形空链表 system("cls"); //执行系统命令，清屏 int choice; do { cout<<"1-创建链表 "; cout<<"2-在链表第i个位置插入元素 "; cout<<"3-删除链表中第i个位置的元素 "; cout<<"4-返回第i个元素的值 "; cout<<"5-元素定位 "; cout<<"6-按值求前驱 "; cout<<"7-测表空 "; cout<<"8-测表长 "; cout<<"9-显示链表 "; cout<<"10-退出 "; cout<<"Enter choice:"; cin>>choice; switch(choice) { case 1://创建链表 cout<<"请输入要创建的链表中元素的个数:"; cin>>i; cout<<endl; L.createList(i); break; case 2://元素插入 cout<<"请输入插入的位置"; cin>>i; cout<<endl; cout<<"请输入插入元素的值:"; cin>>e; cout<<endl; try { L.Insert(i,e); } catch(char* err) { cout<<err<<endl; } break; case 3://元素删除 cout<<"请输入删除位置"; cin>>i; cout<<endl; try { e = L.Delete(i); cout<<"被删除元素为："<<e<<endl; } catch(char* err) { cout<<err<<endl; } cin.get(pause); system("pause"); break; case 4://返回第i个元素值 cout<<"请输入要查询的元素位置:"; cin>>i; try { e = L.getElem(i); cout<<"第"<<i<<"个元素值为:"<<e<<endl; } catch(char* err) { cout<<err<<endl; } cin.get(pause); system("pause"); break; case 5://按值进行元素查询 cout<<"请输入要查询的元素值："; cin>>e; i = L.Locate(e); cout<<"查询元素"<<e<<"在链表中的位置为："<<i<<endl; cin.get(pause); system("pause"); break; case 6://求元素前驱 cout<<"请输入要求前驱元素的值："; cin>>e; try { prior_e = L.prior(e); cout<<"元素"<<e<<"的前驱值为:"<<prior_e<<endl; } catch(char *err) { cout<<err<<endl; } cin.get(pause); system("pause"); break; case 7://测表空 i = L.Empty(); if(i) { cout<<"表空"<<endl; } else { cout<<"表不空"<<endl; } cin.get(pause); system("pause"); break; case 8://测表长 cout<<"链表长度为:"<<L.Length()<<endl; cin.get(pause); system("pause"); break; case 9://遍历输出表 L.listDisplay(); cout<<endl; cin.get(pause); system("pause"); break; case 10://退出 break; default://非法选择 cout<<"Invalid choice"; break; } }while(choice != 10); return 0; }