本文共 3835 字，大约阅读时间需要 12 分钟。
http://blog.csdn.net/itcastcpp/article/details/39274891
//尹成 单链表操作#include using namespace std;class LinkList;struct LinkNode{public: LinkNode(int value =0):m_value(value),pNext(NULL){} ~LinkNode(){pNext = NULL;} friend class LinkList; int m_value; LinkNode* pNext;};//带头结点的链表class LinkList{public: LinkList(); ~LinkList(); void Insert(int data); void Delete(int data); void Sort(); bool IsEmpty(); void Reverse(); void Destroy(); int Length(); LinkNode* Find(int data); bool IsLoop(); void Print(); LinkNode* FindIndex(int index);//使用下标 LinkNode* FindLastNum(int n);//使用两个指针private: LinkNode* pHead;};LinkList::LinkList(){ pHead = new LinkNode();}LinkList::~LinkList(){ Destroy();}//从大到小插入void LinkList::Insert(int data){ if(NULL == pHead) { cout<<"料表未创建"< pNext != NULL) { if(pCur->pNext->m_value < data) break; pCur = pCur->pNext; } LinkNode* pTmp = new LinkNode(data); pTmp->pNext = pCur->pNext; pCur->pNext = pTmp;}void LinkList::Delete(int data){ if(NULL == pHead) { cout<<"链表未创建"< pNext) { cout<<"链表为空"< pNext) { //指向要删除节点的前一个节点 if(pCur->pNext->m_value == data) { LinkNode* pDel = pCur->pNext; pCur->pNext = pCur->pNext->pNext; pDel = NULL; delete pDel; } else pCur = pCur->pNext; }}//从小到大排序void LinkList::Sort(){ if(pHead == NULL) { cout<<"链表未创建"< pNext == NULL) { cout<<"链表为空"< pNext; LinkNode* p = pNewHead; //将pTmp插入到新的链表中 插入时候按照从小到大顺序 while(p->pNext) { if(p->pNext->m_value > pTmp->m_value) { break; } p = p->pNext; } if(pTmp != pHead) { pTmp->pNext = p->pNext; p->pNext = pTmp; } //delete pHead;//释放掉原来的内存 这里不注释掉 导致二次释放指针？ pHead = pNewHead; }}bool LinkList::IsEmpty(){ if(NULL == pHead) { cout<<"链表未创建"< pNext == NULL;}int LinkList::Length(){ if(NULL == pHead) { cout<<"链表未创建"< pNext; while(pCur) { nLength++; pCur=pCur->pNext; } return nLength;}void LinkList::Reverse(){ if(NULL == pHead) { cout<<"链表未创建"< pNext == NULL) { cout<<"链表为空"< pNext->pNext; LinkNode* pPre = pHead->pNext; LinkNode* pnext = NULL; while(pCur) { pnext = pCur->pNext; pCur->pNext = pPre; pPre = pCur; pCur = pnext; } pHead->pNext->pNext =NULL; pHead->pNext = pPre; }}void LinkList::Destroy(){ if(pHead == NULL) { cout<<"链表未创建"< pNext) { LinkNode* pDel = pHead->pNext; pHead->pNext = pDel->pNext; delete pDel; pDel = NULL; } delete pHead; pHead = NULL;}LinkNode* LinkList::Find(int data){ if(NULL == pHead) { cout<<"链表未创建"< pNext) { cout<<"链表为空"< pNext; while(pCur) { if(pCur->m_value == data) return pCur; pCur= pCur->pNext; } return NULL;}void LinkList::Print(){ if(NULL == pHead) { cout<<"链表未创建"< pNext) { cout<<"链表为空"< pNext; while(pCur) { cout< m_value<<" "; pCur = pCur->pNext; } cout< pNext) { cout<<"链表为空"< pNext; LinkNode* pLow = pHead->pNext; //pFast->pNext != NULL 这个条件是很关键的 while(pFast != NULL && pLow != NULL && pFast->pNext !=NULL) { pFast = pFast->pNext->pNext; pLow = pLow->pNext; if(pFast == pLow) return true; } return false;}//返回倒数第n个节点LinkNode* LinkList::FindIndex(int n){ if(n <= 0 || n > Length()) return NULL; LinkNode* pCur = pHead->pNext; for(int i = 1;i < n;i++) { pCur = pCur->pNext; } return pCur;}//这一种方法利用了中间间隔LinkNode* LinkList::FindLastNum(int n){ if(pHead == NULL || pHead->pNext == NULL||n < 0) return NULL; LinkNode* pCur = pHead->pNext; LinkNode* pFirst = pHead->pNext; while(n > 0) { pFirst = pFirst->pNext; if(NULL == pFirst) return NULL; n--; } while(pFirst->pNext) { pFirst = pFirst->pNext; pCur = pCur->pNext; } return pCur;}int main(){ LinkList list; list.Insert(12); list.Insert(14); list.Insert(2); list.Insert(122); list.Insert(5); list.Insert(4); list.Insert(7); list.Print(); int k; cout << "请输入要查询倒数第几个结点(计数从0开始):"; cin >> k; LinkNode *p = list.FindIndex(list.Length() - k); if (p) { cout << p->m_value << endl; } LinkNode *p2 = list.FindLastNum(k); if (p2) { cout << p2->m_value << endl; } cout<<"链表进行排序之后的结果:"<