概念解释

数据结构---相互之间存在一种或多种特定关系的数据元素的集合。

集合---结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他联系。

线性结构---结构中的数据元素之间存在一个对一个的关系。

树形结构---结构中的数据元素之间存在一个对多个的关系。

图状结构---结构中的数据元素之间存在多个对多个的关系。

线性结构

链表

数据域存储数据元素信息，指针域指向下一个节点地址。

一般链表（单链表）第一个节点前附设一个头节点，头节点数据域存储链表相关信息，如链表长度等。最后一个节点的指针域为NULL.（线性链表）

链表优点：

1. 插入删除方便，只需要修改指针

2. 没有连续大内存空间的需求

缺点：

随机访问不方便，必须从头节点开始。（优点与缺点和数组相反）

下面代码中用到几个技巧：

类型转换：编译器在匹配数据类型时会尝试一次类型转换，例如：

double d=3;//3直接匹配double不合适，所以一次类型转换为3.0，如果是对象，尝试调用转换构造函数和类型转换函数。

指针引用：int*&p = &n;//链表中必须用，确保是链表中的指针

例如getptr函数，如果返回不是指针引用，就会返回一个临时变量指针，而不是链表中的指针，接下来的插入操作就会出错。

零初始化：T& d = T();//零初始化，T可为任何类型，d的值都为0，通用性较好

#include 
    
     using namespace std;typedef int T;class List{	struct Node{		T 		data;		Node* 	next;		Node(const T& d=T()):data(d),next(0){}//零初始化	};	Node* head;//头指针，用来保存头节点的地址	int len;public:	List():head(NULL),len(0){ }	void push_front(const T& d){//前插		insert(d,0);	}	List& push_back(const T& d){//尾插		insert(d,size());		return *this;	}	int size()const{		return len;	}	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 insert(const T& d, int pos){//在任意位置插入		Node*& pn = getptr(pos);		Node* p = new Node(d);		p->next = pn;		pn = p;		++len;	}	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;//			cout << "delete " << head << endl;			delete head;			head = p;		}		len = 0;	}	~List(){//		cout << this << "*******" << head << endl;		clear();	}	void erase(int pos){//有效位置为0～size()-1		if(pos<0||pos>=size()) return;		Node*& pn = getptr(pos);		Node* p = pn;		pn = pn->next;		delete p;		--len;	}	void remove(const T& d){		int pos;		while((pos=find(d))!=-1)			erase(pos);	}	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 set(int pos, const T& d){		if(pos<0||pos>=size()) return;		getptr(pos)->data = d;	}	bool empty()const{return head==NULL;}	T front()const{if(empty())throw "空";return head->data;}	T back()const{		if(empty())throw "空";		Node* p=head;		while(p->next!=NULL)			p = p->next;		return p->data;	}};int main(){	List l;	l.push_front(5);//5	l.push_front(8);//8 5	l.push_front(20);//20 8 5	l.insert(9,2);//20 8 9 5	l.insert(6,100);//6 20 8 9 5	l.insert(7,-10);//7 6 20 8 9 5	l.insert(1,2);//7 6 1 20 8 9 5	l.push_back(10).push_back(15).travel();	l.erase(0);//x7:6 1 20 8 9 5 10 15	l.erase(l.size()-1);//x15:6 1 20 8 9 5 10	l.erase(2);//x20:6 1 8 9 5 10	l.travel();	l.push_back(6);//6 1 8 9 5 10 6	l.insert(6, 3);//6 1 8 6 9 5 10 6	l.travel();	l.remove(6);//1 8 9 5 10	l.travel();	l.set(0, 666);	l.set(4, 789);	l.set(l.find(9),123);	l.set(1, 777);	l.travel();	cout << l.front() << "..." << l.back() << ',' << l.size() << "个" << endl;	while(!l.empty()) l.erase(0);	cout << "size:" << l.size() << endl;	return 0;}

栈stack

栈就是限定仅在表尾进行插入和删除操作的线性表。表尾为栈顶，表头为栈底。

由于只能在栈顶插入和删除，就决定了栈

后进先出的特性。

链表可以实现栈，数组也可以实现栈，下面代码分别实现：

链表实现栈代码（直接用上面的链表）

#include 
    
     using namespace std;typedef int T;#include "01list.h"class Stack{	List l;public:	void push(const T& d);//数据入栈成为栈顶	T pop();//栈顶数据出栈，下一个数据成为栈顶	const T& top()const;//取得栈顶数据	bool empty()const{return l.empty();}//是否空栈	bool full()const{return false;}//是否已满	void clear(){l.clear();}//栈清空（复位）	int size()const{return l.size();}//栈中数据个数};void Stack::push(const T& d){	l.push_front(d);}T Stack::pop(){	T t = l.front();	l.erase(0);	return t;}const T& Stack::top()const {	return l.front();}int main(){	Stack s;	try{	s.push(1);	s.push(2);	s.push(3);	s.push(4);	s.push(5);	s.push(6);	}	catch(const char* e){		cout << "异常:" << e << endl;	}	while(!s.empty()){		cout << s.pop() << endl;	}}

数组实现栈代码

#include 
    
     using namespace std;#include 
     
      typedef std::string T;class Stack{	T a[5];	int cur;public:	Stack():cur(0){}	void push(const T& d)throw(const char*);//数据入栈成为栈顶	T pop()throw(const char*);//栈顶数据出栈，下一个数据成为栈顶	const T& top()const throw(const char*);//取得栈顶数据	bool empty()const{return cur==0;}//是否空栈	bool full()const{return cur==5;}//是否已满	void clear(){cur=0;}//栈清空（复位）	int size()const{return cur;}//栈中数据个数};void Stack::push(const T& d)throw(const char*){	if(full()) throw "满";	a[cur++] = d;}T Stack::pop()throw(const char*){	if(empty()) throw "空";	return a[--cur];}const T& Stack::top()const throw(const char*){	if(empty()) throw "空";	return a[cur-1];}int main(){	Stack s;	try{	s.push("芙蓉");	s.push("凤姐");	s.push("春哥");	s.push("曾哥");	s.push("权哥");	s.push("犀利");	}	catch(const char* e){		cout << "异常:" << e << endl;	}	while(!s.empty()){		cout << s.pop() << endl;	}}

队列queue

队列就是限定仅在表尾进行插入和表头删除操作的线性表。表尾为队尾，表头为队头。

由于只能在队尾插入，对头删除删除，就决定了栈

先进先出的特性。

链表可以实现队列，数组也可以实现队列，下面代码分别实现：

链表实现队列（直接用上面的链表）

#include 
    
     using namespace std;typedef int T;#include "01list.h"class Queue{	List l;public:	Queue& push(const T& d){l.push_back(d);return *this;}	T pop(){T t=front();l.erase(0);return t;}	const T& front()const{return l.front();}	const T& back()const{return l.back();}	int size()const{return l.size();}	void clear(){l.clear();}	bool empty()const{return l.empty();}	bool full()const{return false;}};int main(){	Queue q;	q.push(1).push(2).push(3);	q.push(4).push(5);	cout << q.pop() << endl;	cout << q.pop() << endl;	q.push(6).push(7).push(8);	while(!q.empty())		cout << q.pop() << endl;}

数组实现队列

#include 
    
     using namespace std;typedef int T;class Queue{	T a[5];	int b, n;//队首位置和有效元素个数public:	Queue():b(0),n(0){}	Queue& push(const T& d){		if(full()) throw "满";		a[(b+n++)%5] = d;		return *this;	}	T pop(){		if(empty()) throw "空";		--n;		return a[b++%5];	}	const T& front()const{return a[b%5];}	const T& back()const{return a[(b+n-1)%5];}	int size()const{return n;}	void clear(){b=0, n=0;}	bool empty()const{return n==0;}	bool full()const{return n==5;}};int main(){	Queue q;	try{	q.push(1).push(2).push(3);	q.push(4).push(5);	cout << q.pop() << endl;	cout << q.pop() << endl;	q.push(6).push(7).push(8);	}	catch(const char* e){		cout << "异常:" << e << endl;	}	while(!q.empty())		cout << q.pop() << endl;}

你可能感兴趣的文章