利用模板类实现单链表及其功能
需要实现的操作:
[1] push_back [2] push_front
[3] show_list [0] quit_system
[4] pop_back [5] pop_front
[6] insert_val [7] delete_val
[8] find [9]length
[10] clear [11]destroy
[12] reserv [13]sort
头文件源代码:
?
#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED
#include
using namespace std;
template
class List; template
class ListNode { friend class List
; public: ListNode():data(Type()),next(NULL) {} ListNode(Type d, ListNode
*n=NULL) :data(d),next(n) {} ~ListNode() {} public: void SetData(Type d) {data = d;} Type GetData()const {return data;} private: Type data; ListNode
*next; }; template
class List { public: List() { first = last = Buynode(); } ~List() { List
::destroy(); } public: void push_back(const Type &x); void push_front(const Type &x); void show_list()const; void pop_back(); void pop_front(); void insert_val(const Type &x); void delete_val(const Type &x); bool find(const Type &x); Type length(); void clear(); void destroy(); //摧毁该顺序表 void reserv(); //反转 void sort(); protected: ListNode
* Buynode(Type x = Type()) { ListNode
*p = new ListNode
(x); return p; } private: ListNode
*first; ListNode
*last; }; template
void List
::push_back(const Type &x) { ListNode
*s = Buynode(x); last->next = s; last = s; first->data++; } template
void List
::push_front(const Type &x) { ListNode
*s = Buynode(x); s->next=first->next ; first->next=s; if(first == last) last = s; first->data++; } template
void List
::show_list()const { ListNode
*p = first->next; while(p != NULL) { cout<
data<<" "; p = p->next; } cout<
void List
::pop_back() { if(first->data == 0) return; ListNode
*p = first; while(p->next != last) p = p->next; ListNode
*q = p->next; p->next = NULL; last = p; delete q; first->data--; } template
void List
::pop_front() { ListNode
*p = first->next; first->next = p->next; p = NULL; delete p; if(first->data == 1) last = first; first->data--; } template
void List
::insert_val(const Type &x) { ListNode
*s = Buynode(x); ListNode
*p = first->next; if(p->data > s->data) { push_front(s->data); } else if(last->data < s->data) { push_back(s->data); } else { while((p->data < x )&& (p->next->data
next; } s->next=p->next ; p->next = s; first->data++; } } template
void List
::delete_val(const Type &x) { ListNode
*p = first->next; ListNode
*s = Buynode(x); if(x == p->data) { pop_front(); } else { while((p->data != x) && (p->next->data != x)) { p = p->next; } p->next = p->next->next; ListNode
*q = p->next; delete q; first->data--; } } template
bool List
::find(const Type &x) { ListNode
*p = first->next; while(p!=NULL && p->data!=x) p = p->next; return p; } template
Type List
::length() { cout<<"length = "<
data<
data; } template
void List
::clear() { while(first->data >0) pop_front(); } template
void List
::destroy()//摧毁该顺序表 { clear(); delete first; first = last = NULL; } template
void List
::reserv() //反转，将整个表空间逆置 { ListNode
*p = first->next; ListNode
*curr = p->next; ListNode
*tmp = NULL; first->next->next = NULL; while (curr) //将将直接后继指向当前指针的next { tmp = curr->next; curr->next = p; p = curr; curr = tmp; } first->next = p; } template
void List
::sort() { ListNode
*s = first->next; while (s->next) { ListNode
*p = s; while(p->next) { if(s->data > p->next->data) { Type tmp = s->data; s->data = p->next->data; p->next->data = tmp; } p = p->next; } s = s->next; } } #endif // LIST_H_INCLUDED
主函数:
?
?
#inclu