链表课后题（2020年5月20日matrix）

请定义以下三个类：

1. 抽象基类 OrderedList，表示一个整数链表，有以下方法：
   • 构造函数：无参数，创建一个空的链表；
   • void insert(int val) 向链表中插入一个元素，在 OrderedList 中该方法应当为纯虚函数；
   • void printList() const 依次在屏幕上输出链表中的元素，元素之间用空格分隔，输出完整个链表后换行；
   • 析构函数：释放链表所占用的空间。
2. 具体类 AscendOrderedList，表示一个升序的链表，继承自 OrderedList，需要重载 void insert(int val) 函数来实现升序。
3. 具体类 DescendOrderedList，表示一个降序的链表，继承自 OrderedList，需要重载 void insert(int val) 函数来实现降序。

已给主函数如下：

int main() {
    int n, x;
    OrderedList * a = new AscendOrderedList, * d = new DescendOrderedList;
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        std::cin >> x;
        a->insert(x);
        d->insert(x);
    }
    a->printList();
    d->printList();
    delete a;
    delete d;
    return 0;
}

思路：

1. 抽象类构造函数就按照题目意思，创建一个空的头节点，然后无参数。具体类的构造不需要特别写其他的内容因为都在抽象基类里写了。
2.  两个具体类的插入函数思路是一样的，只是大于还是小于的问题。首先定义一个temp节点为待插入的节点，定义p1和p2两个指针在链表中一前一后从head向后移动（用while循环），然后找到待插入的位置 break出循环，此时只需要把temp插入到p1和p2中间就行了。
3. 打印链表就从头循环输出直到NULL。
4. 删除也是定义一前一后两个指针，删除前面的，然后前面的指向后面的，后面的指向后面的后面（就是往后移动一个节点。。。），只要注意一下把head也删掉就ok了。

代码如下：

#include 
using namespace std;

typedef struct node{ 
    int data;
    struct node* nextPtr;
}Node;
typedef Node* NodePtr; 

class OrderedList{
    public:
    NodePtr head,tail;
    OrderedList(){
        head=new Node;
        head->nextPtr=NULL;
        head->data=0;
        tail=head;
    }
    virtual void insert(int val)=0;
    virtual void printList() const=0;
    virtual ~OrderedList(){
        delete head;
    }
};

class AscendOrderedList:public OrderedList{
    public:
    AscendOrderedList(){}
    ~AscendOrderedList(){
        NodePtr temp=head;
        while(head!=NULL){
            head=head->nextPtr;
            delete temp;
            temp=head;
        }
    }
    void insert(int num){ 
        NodePtr temp=new Node; 
        temp->data=num;
        NodePtr p1=head,p2=head->nextPtr;
        while(p2!=NULL){
        	if(p2->data>temp->data) break;
			p2=p2->nextPtr;
        	p1=p1->nextPtr;
		}
		p1->nextPtr=temp;
		temp->nextPtr=p2;
    }
    
    void printList() const{
        NodePtr temp=head->nextPtr;
        while(temp!=NULL){
        	cout<data<<' ';	
        	temp=temp->nextPtr;
		}
        cout<nextPtr;
            delete temp;
            temp=head;
        }
    }
    
    void insert(int num){ 
        NodePtr temp=new Node;
        temp->data=num;
        NodePtr p1=head,p2=head->nextPtr;
        while(p2!=NULL){
        	if(p2->datadata) break;
			p2=p2->nextPtr;
        	p1=p1->nextPtr;
		}
		p1->nextPtr=temp;
		temp->nextPtr=p2;
    }
    
    void printList() const{
        NodePtr temp=head->nextPtr;
        while(temp!=NULL){
        	cout<data<<' ';	
        	temp=temp->nextPtr;
		}
        cout< 
后来又改了一下，printList函数完全可以写在抽象基类里，因为打印操作都是一样的嘛。然后删除操作也是，直接在抽象基类写。又去掉了没用到的tail指针（第一次写的时候思路有点离谱后来没用到），我感觉这个才是最符合题目要求的写法吧，大概和题目说的一模一样。
 
#include 
using namespace std;

typedef struct node{ 
    int data;
    struct node* nextPtr;
}Node;
typedef Node* NodePtr; 

class OrderedList{
    public:
    NodePtr head;
    OrderedList(){
        head=new Node;
        head->nextPtr=NULL;
        head->data=0;
    }
    virtual void insert(int val)=0;
    void printList() const{
        NodePtr temp=head->nextPtr;
        while(temp!=NULL){
        	cout<data<<' ';	
        	temp=temp->nextPtr;
		}
        cout<nextPtr;
            delete temp;
            temp=head;
        }
    }
};

class AscendOrderedList:public OrderedList{
    public:
    AscendOrderedList(){}
    void insert(int num){ 
        NodePtr temp=new Node; 
        temp->data=num;
        NodePtr p1=head,p2=head->nextPtr;
        while(p2!=NULL){
        	if(p2->data>temp->data) break;
			p2=p2->nextPtr;
        	p1=p1->nextPtr;
		}
		p1->nextPtr=temp;
		temp->nextPtr=p2;
    }
};

class DescendOrderedList:public OrderedList{
    public:
    DescendOrderedList(){}
    void insert(int num){ 
        NodePtr temp=new Node;
        temp->data=num;
        NodePtr p1=head,p2=head->nextPtr;
        while(p2!=NULL){
        	if(p2->datadata) break;
			p2=p2->nextPtr;
        	p1=p1->nextPtr;
		}
		p1->nextPtr=temp;
		temp->nextPtr=p2;
    }
};
 
以后可以再看一下下面的文章复习复习~ 
 
---链表知识点回顾（单、双、循环）---https://blog.csdn.net/weixin_60634144/article/details/124690268?spm=1001.2014.3001.5502