自己写的c++实现的链表类

桃扇骨 2022-09-18 02:49 91阅读 0赞

\#include<iostream>  
using namespace std;  
struct Node  //结点信息  
\{  
    int Data;  
    Node \*Next;  
\};  
class ListLink  //链表类  
\{  
private:  
Node \*Head;  //头结点  
int Length;  
public:  
    ListLink();  
    ListLink(int length);  
    void Clear();  
    ~ListLink();  
    bool AddNode(Node \*in);  
    bool InsertToFirst(Node \*in);  
    bool InsertInOrder1(Node \*p);  
    bool InsertInOrder2(Node \*p);  
    bool DelNode(int tar);  
    bool DelNode(Node \*tar);  
    int GetLength();  
    void sort();  
    void show();  
    Node \* SearchData(int tar);  
    void ReverseList();  
\};  
  
  
ListLink::ListLink()  
\{  
Length = 0;  
Head=NULL;  
\}  
void ListLink::Clear()  
\{  
    Node \*p1,\*p2;  
    for(p1=Head;p1!=NULL;)  
    \{  
        p2=p1;  
        p1=p1->Next;  
        delete p2;  
    \}  
    Head=NULL;  
\}  
ListLink::ListLink(int length)  
\{  
    int i;  
    Length = length;  
    Node \*Current,\*Last;  
    Head=Current=new Node;  
    Last = new Node;  
    Last->Data=0;  
    for(i=0;i<length;i++)  
    \{  
        Current->Next=Last;  
        Current=Last;  
        Last=new Node;  
        Last->Data=0;  
    \}  
    Current->Next=NULL;  
    delete Last;  
\}  
ListLink::~ListLink()  
\{  
    Node \*p1=NULL,\*p2=NULL;  
    for(p1=Head;p1!=NULL;)  
    \{  
        p2=p1;  
        p1=p1->Next;  
        delete p2;  
    \}  
    Head=NULL;  
\}  
bool ListLink::AddNode(Node \*in)  
\{  
    Node \*p = Head;  
    while(p->Next!=NULL)  
    \{  
        p=p->Next;  
    \}  
    p->Next=in;  
    in->Next=NULL;  
    Length++;  
    return true;  
\}  
bool ListLink::InsertToFirst(Node \*in)  
\{  
    Node \*p = Head;  
    Head->Next=in;  
    in->Next=p->Next;  
    Length++;  
    return true;  
\}  
bool ListLink::InsertInOrder1(Node \*in)//降序  
\{  
Node \*p=Head;  
while(p->Next!=NULL&&p->Next->Data>in->Data)  
p=p->Next;  
in->Next=p->Next;  
p->Next=in;  
Length++;  
return true;  
\}  
bool ListLink::InsertInOrder2(Node \*in)//升序  
\{  
Node \*p=Head;  
while(p->Next!=NULL&&p->Next->Data<in->Data)  
p=p->Next;  
in->Next=p->Next;  
p->Next=in;  
Length++;  
return true;  
\}  
bool ListLink::DelNode(int tar)  
\{  
Node \*p=Head,\*temp;  
while(p->Next!=NULL&&p->Next->Data!=tar)  
p=p->Next;  
temp=p->Next;  
if(temp)  
\{  
p->Next=temp->Next;  
delete temp;  
Length--;  
return 1;  
\}  
return 0;  
\}  
bool ListLink::DelNode(Node \*tar)  
\{  
Node \*p=Head,\*temp;  
while(p->Next!=NULL&&p->Next->Data!=tar->Data)  
p=p->Next;  
temp=p->Next;  
if(temp)  
\{  
p->Next=temp->Next;  
delete temp;  
Length--;  
return 1;  
\}  
return 0;  
\}  
int ListLink::GetLength()  
\{  
return Length;  
\}  
void ListLink::sort()   //dubble sort升序  
\{  
int i,j;  
Node \*p=Head;  
for(i=0;i<Length-1;i++)  
for(j=0,p=Head;j<Length-i-1;j++,p=p->Next)  
if(p->Next->Data>p->Next->Next->Data)  
\{  
Node \*temp1,\*temp2,\*temp3;  
temp1=p->Next;  
temp2=p->Next->Next;  
temp3=p->Next->Next->Next;  
p->Next=temp2;  
temp2->Next=temp1;  
temp1->Next=temp3;  
\}  
\}  
void ListLink::show()  
\{  
Node \*p = Head->Next;  
while(p!=NULL)  
\{  
cout<<p->Data<<endl;  
p=p->Next;  
\}  
\}  
Node \* ListLink::SearchData(int tar)  
\{  
Node \*p=Head;  
while(p->Next!=NULL&&p->Next->Data!=tar)  
p=p->Next;  
if(p->Next)  
\{  
return p->Next;  
\}  
return NULL;  
\}  
  
  
void ListLink::ReverseList()  
\{  
    if(Head->Next == NULL || Head->Next->Next == NULL)  
    \{  
return ;               //if the list have one or two links,return  
    \}  
  
  
    Node \*t = NULL,  
\*p = Head->Next,  
\*q = Head->Next->Next;  
    while(q != NULL)  
    \{  
t = q->Next;  
q->Next = p;  
p = q;  
q = t;  
    \}  
  
  
    Head->Next->Next = NULL;  
    Head->Next = p;  
    return ;  
\}  
  
  
int main()  
\{  
/\*List t(7);  
Node \*in=new Node;  
t.show();  
cout<<(t.SearchData(0))->Data<<endl;  
t.~List();\*/  
return 0;  
\}  
/\*  
List::List();  
List::List(int l);  
List::~List() ;  
bool List::AddList(Node \*in) ;//move to the last and insert the node  
bool List::InsertToFirst(Node \*in);//move to the first and insert the node  
bool List::InsertInOrder1(Node \*in);//move to the first and insert the node  
bool List::InsertInOrder2(Node \*in);//move to the first and insert the node  
bool DelNode(int tar);  
bool DelNode(Node \*tar);  
int List::GetLength();  
void List::sort();   //dubble sort  
void List::show();  
void List::ReverseList();  
Node \*SearchData(int tar);  
\*/