数据结构――动态链表（C++）

定义一个节点：

#include 
  
   
using namespace std;

typedef int T;

struct Node{
	T data;
	Node* next;
	Node(const T& d):data(d), next(NULL){}
	operator T(){
		return data;
	}
};

int main(){
	Node a(10), b(20);
	cout << "a=" << a << ", b=" << b << endl;
	return 0;
}
  

输出一段简单的链表

#include 
  
   
using namespace std;

typedef int T;

struct Node{
    T data;
    Node* next;
    Node(const T& d):data(d), next(NULL){}
    operator T(){
        return data;
    }   
};

int main(){
    Node a(10), b(20), c(30), d(40), e(50);
    a.next = &b; 
    b.next = &c; 
    c.next = &d; 
    Node *p = &a; 
    while(p != NULL){
        cout << *p << ' ';
        p = p->next;
    }
    cout << endl;
    return 0;
}
  

#include 
  
   
using namespace std;

typedef int T;

struct Node{
	T data;
	Node* next;
	Node(const T& d):data(d), next(NULL){}
	operator T(){
		return data;
	}
};

//输出链表
void showlist(Node* p){
	while(p != NULL){
		cout << *p << ' ';
		p = p->next;
	}
	cout << endl;
}

int main(){
	Node a(10), b(20), c(30), d(40), e(50);
	a.next = &b;
	b.next = &c;
	c.next = &d;
	showlist(&a);
	//添加一个节点
	Node* & p = b.next;//取b.next指针的别名
	e.next = p;
	p = &e;
	showlist(&a);
	//再添加一个节点
	Node* k = new Node(70);
	Node*& r = c.next;
	k->next = r;
	r = k;

	return 0;
}
  

一个C++实现的链表如下：

#include 
  
   
using namespace std;

typedef int T;

class List{
	struct Node{
		T data;
		Node * next;
		//T()零初始化
		Node(const T& d=T()):data(d), next(0){}
	};
	Node * head; //头指针
	int len;
public:
	List():head(NULL),len(0){ }

	//插入到任何位置
	//1、在链表里找到指向那个位置的指针pn
	//2、让新节点的next成员和pn指向同一个地方
	//3、再让pn指向新节点
	void insert(const T&d, int pos){
		Node*& pn = getptr(pos);
		Node* p = new Node(d);
		p->next = pn;
		pn = p;
		len++;	
	}
	
	//返回链表长度
	int size()const{
		return len;
	}

	//尾插
	void push_back(const T& d){
		insert(d, size());
	}

	//找链表中指向指定位置的指针
	Node*& getptr(int pos){
		if(pos<0 || pos>size()) pos = 0;
		if(pos==0) return head;
		Node* p = head;
		for(int i=1; i
   
    next; return p->next; } //前插 void push_front(const T& d){ insert(d, 0); } //遍历 void travel()const{ Node* p = head; while(p!=NULL){ cout << p->data << ' '; p = p->next; } cout << endl; } //清空 void clear(){ while(head!=NULL){ Node * p = head->next; delete head; head = p; } len = 0; } ~List(){ clear(); } //按照位置删除 //1、找到链表中指向那个位置的指针 //2、把那个指针另存一份 //3、让那个指针指向下一个节点 //4、释放那个指针的动态内存 void erase(int pos){ if(pos<0 || pos>=size()) return; Node *& pn = getptr(pos); Node * p = pn; pn = pn->next; delete p; --len; } //根据元素查找位置 int find(const T& d)const{ int pos = 0; Node* p = head; while(p){ if(p->data==d) return pos; p = p->next; ++pos; } return -1; } //根据元素删除 void remove(const T& d){ int pos; while((pos = find(d)) != -1) erase(pos); } }; int main(){ List l; l.push_front(5); l.push_front(8); l.push_front(20); //在第2个位置插入9 l.insert(9, 2); l.travel(); return 0; } 
   
  

通过上图可以看出来，如果我们要插入一个节点，就需要找到指向该位置的指针（或者前一个结点），比如上图的p->next指针就是我们需要找到的。删除一个节点也一样，需要找到指向该节点的指针。