C++數據結構 單鏈表(模板類)

C++數據結構 單鏈表(模板類)

利用模板類實現單鏈表及其功能

需要實現的操作:

[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->datanext;
            }
            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

#include"List.h" int main() { List mylist; int select = 1; int Item; int pos; while(select) { cout<<"**************************************"<"; cin>>select; switch(select) { case 1: cout<<"請輸入要插入的值(-1結束):>"; while(cin>>Item, Item!=-1) { mylist.push_back(Item); } break; case 2: cout<<"請輸入要插入的值(-1結束):>"; while(cin>>Item, Item!=-1) { mylist.push_front(Item); } break; case 3: mylist.show_list(); break; case 4: mylist.pop_back(); break; case 5: mylist.pop_front(); break; case 6: cout<<"請輸入要插入的值:>"; cin>>Item; mylist.insert_val(Item); break; case 7: cout<<"請輸入要刪除的值:>"; cin>>Item; mylist.delete_val(Item); break; case 8: cout<<"請輸入要查找的值:>"; cin>>Item; mylist.find(Item); break; case 9: mylist.length(); break; case 10: mylist.clear(); break; case 11: mylist.destroy(); break; case 12: mylist.reserv(); break; case 13: mylist.sort(); break; default: break; } } }