本文共 5199 字，大约阅读时间需要 17 分钟。
头文件list.h
#pragma once#includeusing namespace std;//ListNode类template class ListNode { public: ListNode() :link(NULL) { } //默认构造函数 ListNode(T value) :link(NULL), data(value) { } //带参构造函数 ~ListNode() { }; void SetLink(ListNode * next); //将参数next的值赋给节点中的数据成员link void SetData(T value); ListNode * GetLink(); //返回节点的数据成员link T& Getdata();private: T data; ListNode * link;};template void ListNode ::SetLink(ListNode * next) { link = next;}template void ListNode ::SetData(T value) { data = value;}template ListNode * ListNode ::GetLink() { return link;}template T& ListNode ::Getdata() { return data;}//List类template class List { public: List(); ~List(); //向单链表的表尾添加节点 bool AddTail(T value); //删除表尾节点 bool RemoveTail(); //用来在索引index指定的位置添加一个数据成员是value的节点 bool InsertAt(int index, T value); //用来删除指定索引index指定位置的节点 bool RemoveAt(int index); //根据索引index返回单链表中相应节点所保存的data值 T& GetAt(int index); //判断单链表是否为空 bool IsEmpty(); //获得当前链表中节点的个数 int GetCount(); //删除链表中的所有节点 void RemoveAll(); //顺序输出链表中所有节点的值 void printAll(); //返回链表表头指针 ListNode * GetHead(); //返回链表表尾指针 ListNode * GetTail(); //返回链表中指向index索引位置的指针 ListNode * GetNodeAt(int index); //用来返回cur ListNode * GetCur(); //使cur向后移动一个节点，并返回移动后的cur ListNode * TowardCur();private: ListNode * head; ListNode * tail;};//向单链表的表尾添加节点template bool List ::AddTail(T value) { ListNode * address = new ListNode (value); //把新建节点链入表尾，成为新表尾 tail->SetLink(address); //移动表尾指针置新表尾处 tail = tail->GetLink(); tail->SetLink(NULL); if (tail != NULL) { return true; } else { return false; }}//在索引值指向的节点前插入一个新节点的成员函数实现template bool List ::InsertAt(int index, T value) { //判断索引值是否正确 if (index > this->GetCount() - 1 || index < 0) { cout << "A wrong position!" << endl; return false; } //从头节点处开始寻找 ListNode * current = head; while (index) { //如果没有找到，则顺序移动cur current = current->GetLink(); --index; } ListNode * address = new ListNode (value); //将新建节点链入链表 address->SetLink(current->GetLink()); current->SetLink(address); if (current->GetLink() != NULL) { return true; } else { return false; }}//删除表尾节点template bool List ::RemoveTail() { //利用RemoveAt(int index)实现 return RemoveAt(this->GetCount() - 1);}//按索引值删除节点template bool List ::RemoveAt(int index) { if (index > this->GetCount() - 1 || index < 0) { cout << "A wrong position!" << endl; return false; } //用两个节点指针协作完成删除，其中，cur指向要删除节点的前一个节点 //preCur指向要删除的节点 ListNode * cur, * preCur; cur = head; //置preCur到cur后 preCur = cur->GetLink(); while (index) { cur = cur->GetLink(); preCur = preCur->GetLink(); --index; } //如果要删除的节点位于链表表尾，则把cur置为新的表尾 if (tail == preCur) { tail = cur; } //将被删除节点从链表中摘下 cur->SetLink(preCur->GetLink()); delete preCur; if (preCur != NULL) { return true; } else { return false; }}//创建表头节点，并初始化head与tailtemplate List ::List() { head = new ListNode (); tail = head; tail->SetLink(NULL);}template List ::~List() { RemoveAll(); delete head;}//返回索引值节点中的valuetemplate T& List ::GetAt(int index) { if (index > this->GetCount() - 1 || index < 0) { cout << "A wrong position!" << endl; } ListNode * cur; cur = head->GetLink(); while (index) { cur = cur->GetLink(); --index; } return cur->Getdata();}//判空函数template bool List ::IsEmpty() { return head->GetLink() == NULL;}//获得当前链表中节点的个数template int List ::GetCount() { int count = 0; ListNode * current = head->GetLink(); while (current != NULL) { ++count; current = current->GetLink(); } return count;}//删除链表中的所有节点template void List ::RemoveAll() { ListNode * cur; while (head->GetLink() != NULL) { cur = head->GetLink(); head->SetLink(cur->GetLink()); delete cur; } tail = head; //置表尾为表头处}//返回索引值为Index的节点的指针template ListNode * List ::GetNodeAt(int index) { if (index > this->GetCount() - 1 || index < 0) { cout << "A wrong position!" << endl; } //handle即为所求指针，它指向的索引值是index的节点 ListNode * handle = head->GetLink(); while (index) { handle = handle->GetLink(); --index; } return handle;}//顺序输出链表中所有节点的值template void List ::printAll() { int count; int index = 0; ListNode * ptr; count = this->GetCount(); while (count) { ptr = GetNodeAt(index); printf("%d ", ptr->Getdata()); --count; ++index; } return;}
main函数测试程序
//有序链表的合并算法//每次取出listSecond中的第一个节点，将这个节点插入到listFirst中相应的位置#include "list.h"int main() { //创建两个链表 List listFirst; List listSecond; //初始化链表listFirst listFirst.AddTail(1); listFirst.AddTail(6); listFirst.AddTail(8); listFirst.AddTail(9); listFirst.AddTail(13); //初始化链表listSecond listSecond.AddTail(0); listSecond.AddTail(3); listSecond.AddTail(4); listSecond.AddTail(6); listSecond.AddTail(11); listSecond.AddTail(17); //当listSecond非空时持续循环 while (listSecond.GetCount() != 0) { int indexFirst = 0; //每次把listSecond中的第一个数插入到listFirst中 //用while循环语句寻找插入位置 while (listSecond.GetAt(0) > listFirst.GetAt(indexFirst)) { ++indexFirst; //如果listFirst已到链表尾，结束本次循环 if (indexFirst == listFirst.GetCount()) { break; } } if (indexFirst == listFirst.GetCount()) { //插入位置在listFirst链表尾 listFirst.AddTail(listSecond.GetAt(0)); listSecond.RemoveAt(0); } else { //插入位置在listFirst链表中 listFirst.InsertAt(indexFirst, listSecond.GetAt(0)); listSecond.RemoveAt(0); } } listFirst.printAll(); return 0;} 转载地址：http://fxxmb.baihongyu.com/