list.cc

资深C++讲师授课代码

#include <iostream>
using namespace std;

typedef int T;
class List{
	struct Node{
		T data;
		Node* next;
		Node(const T& d):data(d),next(NULL){++cnt;}
		~Node(){--cnt;}
		static int cnt;
	};
	Node* head;
	Node*& getp(int pos){
		if(pos<0||pos>size()) pos=0;
		if(pos==0) return head;
		Node* p=head;
		for(int i=1; i<pos; i++)
			p = p->next;
		return p->next;
	}
public:
	List():head(NULL){}
	void clear(){
		while(head!=NULL){
			Node* q = head->next;
			delete head;
			head = q;
		}
	}
	~List(){clear();}
	void travel(){
		Node* p=head;
		while(p!=NULL){
			cout << p->data << ' ';
			p = p->next;
		}
		cout << endl;
	}
	void insert(const T& d, int pos){
		Node* p = new Node(d);
		Node*& q = getp(pos);
		p->next = q;
		q = p;
	}
	bool erase(const T& d){
		int pos=find(d);
		if(pos==-1) return false;
		Node*& pn=getp(pos);
		Node* q = pn;
		pn = pn->next;
		delete q;
	}
	int find(const T& d, int start=0){//返回指数据为d的节点的指针的编号
		int pos=0;
		Node* p=getp(start);//head;
		while(p!=NULL){
			if(p->data==d)
				return pos;
			else{
				p = p->next;
				++pos;
			}
		}
		return -1;//return size();
	}
	bool update(const T& olddata, const T& newdata){
		int pos = find(olddata);
		if(pos==-1) return false;
		getp(pos)->data = newdata;
		return true;
	}
	int size(){
		return Node::cnt;
	}
	T front(){
		if(head==NULL) throw "no head node!";
		return head->data;
	}
	T back(){
		if(head==NULL) throw "no tail node!";
		return getp(size()-1)->data;
	}
	bool empty(){return head==NULL;/*size()==0;*/}
};
int List::Node::cnt = 0;
int main()
{
	List l;
	l.insert(10, 0);
	l.insert(20, 0);
	l.insert(30, 1);
	l.insert(40, l.size());
	l.travel();
	l.update(30, 50);
	l.update(0, 55);
	l.update(20, 88);
	l.travel();
	l.erase(10);
	l.travel();
	l.erase(88);
	l.travel();
	l.erase(40);
	l.travel();
	l.erase(90);
	l.travel();
	l.erase(50);
	l.travel();
}