[数据结构与算法]1805 类设计练习6：设计整型链表类List

肇砖oj题，仅供参考，不怕被钟sir封号三周你就抄

Description

设计一个整型链表类?List，能够实现链表节点的插入?insert()?、按位置删除节点?deleteByPos()?、按值删除节点?deleteByVAlue()?，以及链表数据的输出操作?print()。

构造函数、析构函数这些都不用说也知道要写的吧。

提示：链表节点用如下结构定义：

struct?Node?{?//?节点的结构
???int?data;
???Node?*next;

???Node()?{
???????data?=?0;
???????next?=?nullptr;
???}

???~Node()?{?}
};

链表类?List?有一个数据成员?head，类型是?Node *

根据题目要求完善下面的程序：

Input

#include?<iostream>
using?namespace?std;

///?节点的结构
struct?Node?{
???int?data;
???Node?*next;

???Node()?{
???????data?=?0;
???????next?=?nullptr;
??}

??~Node()?{?}
};

///?链表类
class?List?{
private:
???Node?*head;

public:

??你写的代码放在这里

};

int?main()?{
???List?l1;??///?创建一个空链表对象?l1

???l1.insert(?0,?10?);?///?在第?0?个节点的后面插入值为?10?的新节点，也即在链表头部插入新的节点
???l1.insert(?0,?66?);
???l1.insert(?1,?292?);??///?在第?1?个节点的后面插入值为?10?的新节点
???l1.print(?);??///?从头到尾输出链表节点的值，每个值后跟一空格

???l1.deleteByValue(?66?);??///?删除链表中第一个值为?66?的节点
???l1.print(?);

???l1.insert(?2,?-2?);??///?在第?2?个节点的后面插入值为?-2?的新节点
???l1.insert(?1,?3?);??///?在第?1?个节点的后面插入值为?3?的新节点
???l1.print(?);

???l1.deleteByPos(?2?);??///?删除链表中第2个位置的节点，那么“3”就被删掉了
???l1.print(?);

???l1.deleteByValue(?999?);
???l1.print(?);

???return?0;
}

Output

见样例输出

Sample Input

NULL

Sample Output

66 292 10?
292 10?
292 3 10 -2?
292 10 -2?
not found data: 999
292 10 -2?

?

#include <iostream>
using namespace std;

/// 节点的结构
struct Node {
   int data;
   Node *next;

   Node() {
       data = 0;
       next = nullptr;
  }

  ~Node() { }
};

/// 链表类
class List {
private:
   Node *head;

public:
	List(){
		head=new Node; 
	}
	~List(){
		Node *p=head,*r;
		while(p){
			r=p;
			delete r;
			p=p->next;
		}
	}
	void insert(int n,int m){
		int i=0;
		Node *r,*p;
		r=head;
		while(i<=n){
			if(r->next==nullptr) r->next =new Node;
			r=r->next;
			i++;
		}
		p=new Node; 
		p->data=m;
		p->next=r->next;
		r->next=p;
	}
	void print(){
		Node *p;
		p=head->next;
		while(p->next){
			p=p->next;
			cout<<p->data<<" ";
		}
		cout<<endl;
	}
	void  deleteByValue(int n){
		Node *r,*p=head;
		while(p->next->next){
			p=p->next;
			if(p->next->data==n){
				r=p->next;
				p->next=r->next;
				delete r;
				return ;       }
		}
		cout<<"not found data: "<<n<<endl;
	}
	void deleteByPos(int n){
		Node *p=head,*r;
		int i=0;
		while(i<n){
			p=p->next;
			i++;
		}
		r=p->next;
		p->next=r->next;
		delete r;
		}
};

int main() {
   List l1;  /// 创建一个空链表对象 l1

   l1.insert( 0, 10 ); /// 在第 0 个节点的后面插入值为 10 的新节点，也即在链表头部插入新的节点
   l1.insert( 0, 66 );
   l1.insert( 1, 292 );  /// 在第 1 个节点的后面插入值为 10 的新节点
   l1.print( );  /// 从头到尾输出链表节点的值，每个值后跟一空格

   l1.deleteByValue( 66 );  /// 删除链表中第一个值为 66 的节点
   l1.print( );

   l1.insert( 2, -2 );  /// 在第 2 个节点的后面插入值为 -2 的新节点
   l1.insert( 1, 3 );  /// 在第 1 个节点的后面插入值为 3 的新节点
   l1.print( );

   l1.deleteByPos( 2 );  /// 删除链表中第2个位置的节点，那么“3”就被删掉了
   l1.print( );

   l1.deleteByValue( 999 );
   l1.print( );

   return 0;
}