C++課程設計，我鏈表類，編完之后感覺對鏈表有了更深刻的認識

//? h9.h???

#ifndef h9_h_

#define h9_h_

#include<iostream>

using namespace std;


typedef struct LNode
{
??? struct LNode* next;
??? struct LNode* prev;
??? int data;
}*LinkList,LNode;


class List
{
private:
??? LinkList HeadList;
??? int LengthList;
public:
??? List();
??? List(const List& temp);
??? ~List();
??? int SearchLNode(int i);
??? bool InsertLNode(int i,int data_);
??? bool DeleteLNode(int i);
??? void ShowList();
??? int GetLengthList();
??? List& operator=(const List& temp);
??? List operator+(const List& temp);
??? List operator-(const List& temp);
??? List& operator+=(List& temp);
??? List& operator-=(const List& temp);
??? friend ostream& operator<<(ostream& out,List& temp);
};

#endif


//? h9.cpp


#include"h9.h"


List::List()
{
??? if(!(HeadList = new LNode))
??? {
??? ??? cout<<"distribute memory fail!\n";
??? ??? return;
??? }
??? HeadList->next = NULL;
??? HeadList->prev = NULL;
??? LengthList=0;
}


List::~List()
{
??? LinkList temp = NULL;
??? while(HeadList->next != NULL)
??? {
??? ??? temp = HeadList->next;
??? ??? HeadList->next = temp->next;
??? ??? delete temp;
??? }
??? LengthList = 0;
??? delete HeadList;
}


List::List(const List& temp)
{
??? LinkList newlist,lastlist,p;
??? p = temp.HeadList->next;
??? HeadList = new LNode;
??? lastlist = HeadList;
??? this->HeadList->next = NULL;
??? this->HeadList->prev = NULL;
??? this->LengthList = temp.LengthList;
??? while(p)
??? {
??? ??? newlist = new LNode;
??? ??? newlist->data = p->data;
??? ??? lastlist->next = newlist;
??? ??? newlist->prev = lastlist;
??? ??? newlist->next = NULL;
??? ??? lastlist = newlist;
??? ??? p = p->next;
??? }
}


bool List::InsertLNode(int i,int data_)
{
??? LinkList p = HeadList->next,Pinsert;
??? int j = 1;
??? Pinsert = new LNode;
??? Pinsert->data = data_;
??? Pinsert->next = NULL;
??? Pinsert->prev = NULL;
??? if(i == 1)
??? {
??? ??? Pinsert->prev = HeadList;
??? ??? HeadList->next = Pinsert;
??? ??? LengthList = 1;
??? ??? return true;
??? }
??? else
??? {
??? ??? while(p != NULL&&j < i-1)??? ??? ??? ??? ??? //查詢第i-1行
??? ??? {
??? ??? ??? p = p->next;
??? ??? ??? j++;
??? ??? }
??? ??? if(p == NULL)
??? ??? {
??? ??? ??? cout<<"illegal operate!\n";???
??? ??? ??? return false;
??? ??? }
??? ??? Pinsert->next = p;
??? ??? p->prev->next = Pinsert;
??? ??? Pinsert->prev = p->prev;
??? ??? p->prev = Pinsert;
??? ??? LengthList++;
??? }
??? return true;
}


int List::SearchLNode(int i)
{
??? int j = 1,temp;
??? LinkList p=HeadList->next;
??? while(p&&j < i)
??? {
??? ??? p = p->next;
??? ??? j++;
??? }
??? if(p == NULL || j > i)
??? {
??? ??? cout << "search fail\n";???
??? ??? return -1;
??? }
??? temp = p->data;
??? return temp;
}




bool List::DeleteLNode(int i)
{
??? int j = 1;
??? LinkList p = HeadList->next;
??? while(p && j < i)??? ??? ??? ??? ???
??? {
??? ??? p = p->next;
??? ??? j++;
??? }
??? if(p == NULL||j > i)
??? {
??? ??? cout << "delete fail!\n";
??? ??? return false;
??? }
??? p->prev->next = p->next;
??? p->next->prev = p->prev;
??? delete p;
??? LengthList--;
??? return true;
}


void List::ShowList()
{
??? LinkList p = HeadList->next;
??? cout<<"Now,this List is? ";
??? for(;p != NULL;p = p->next)
??? {
??? ??? cout << p->data<<"<==>";
??? }
??? cout << "NULL\n";
}

int List::GetLengthList()
{
??? return LengthList;
}


List& List::operator=(const List& temp)
{
??? LinkList newlist,lastlist,p;
??? p = temp.HeadList->next;
??? HeadList = new LNode;
??? lastlist = HeadList;
??? this->HeadList->next = NULL;
??? this->HeadList->prev = NULL;
??? this->LengthList = temp.LengthList;
??? while(p)
??? {
??? ??? newlist = new LNode;
??? ??? newlist->data = p->data;
??? ??? lastlist->next = newlist;
??? ??? newlist->prev = lastlist;
??? ??? newlist->next = NULL;
??? ??? lastlist = newlist;
??? ??? p = p->next;
??? }
??? return *this;
}


List List::operator+(const List& temp)
{
??? List nowList,tempList(*this);
??? LinkList p = tempList.HeadList->next,q = temp.HeadList->next;
??? while(p->next != NULL)
??? {
??? ??? p = p->next;
??? }
??? p->next = q;
??? q->prev = p;
??? delete temp.HeadList;
??? nowList=tempList;
??? nowList.LengthList = tempList.LengthList + temp.LengthList;
??? return nowList;
}


List& List::operator-=(const List& temp)
{
??? List t(temp);
??? LinkList p ,q = t.HeadList->next,r;
??? while(q != NULL)
??? {
??? ??? p = this->HeadList->next;
??? ??? while(p != NULL)
??? ??? {
??? ??? ??? if(p->data == q->data)
??? ??? ??? {
??? ??? ??? ??? r = p->prev;
??? ??? ??? ??? p->prev->next=p->next;
??? ??? ??? ??? p->next->prev=p->prev;
??? ??? ??? ??? delete p;
??? ??? ??? ??? this->LengthList--;
??? ??? ??? ??? p = r;
??? ??? ??? }
??? ??? ??? p = p->next;
??? ??? }
??? ??? q = q->next;
??? }
??? return *this;
}


List& List::operator+=(List& temp)
{
??? LinkList p = this->HeadList->next,q = temp.HeadList->next;
??? while(p->next != NULL)
??? {
??? ??? p = p->next;
??? }
??? p->next = q;
??? q->prev = p;
??? delete temp.HeadList;
??? this->LengthList += temp.LengthList;
??? return *this;
}


List List::operator-(const List& temp)
{
??? List t(temp),m(*this);
??? LinkList p,q = t.HeadList->next,r;
??? while(q != NULL)
??? {
??? ??? p = m.HeadList->next;
??? ??? while(p != NULL)
??? ??? {
??? ??? ??? if(p->data == q->data)
??? ??? ??? {
??? ??? ??? ??? r = p->prev;
??? ??? ??? ??? p->prev->next = p->next;
??? ??? ??? ??? p->next->prev = p->prev;
??? ??? ??? ??? delete p;
??? ??? ??? ??? m.LengthList--;
??? ??? ??? ??? p = r;
??? ??? ??? }
??? ??? ??? p = p->next;
??? ??? }
??? ??? q = q->next;
??? }
??? return m;
}


ostream& operator<<(ostream& out,List& temp)
{
??? List t(temp);
??? out << "length of List:"<< t.GetLengthList() << endl;
??? out << "data of List:";
??? for(int i = 0;i < t.GetLengthList();i++)
??? {
??? ??? out << t.HeadList->next->data << "?? ";
??? ??? t.HeadList = t.HeadList->next;
??? }
??? out<<"\n";
??? return out;
}


// h9main.cpp??


#include"h9.h"

int main(void)
{
?? List l,t,lt;
??? int temp;
??? l.InsertLNode(1,10);
??? l.InsertLNode(2,20);
?? l.InsertLNode(3,30);
?? l.InsertLNode(4,40);
??? l.ShowList();
??? t.InsertLNode(1,20);
??? t.InsertLNode(2,40);
?? t.InsertLNode(3,70);
?? t.InsertLNode(4,80);
?? t.ShowList();
??? l-=t;
??? l.ShowList();
?? cout<<l;??????
??? return 0;
}

posted on 2007-03-21 19:56 honker 閱讀(470) 評論(0)  編輯 收藏 引用