slinklist.cpp

静态链表,c++语言描述

#include <iostream>
#include <cstdlib>
#define MAXSIZE 100

using namespace std;

template <class T>
class SLinklistNode {
public:
	SLinklistNode();
	T data;
	int cur;
};


template <class T> 
class Vector : public SLinklistNode<T> {
public:
	Vector() : status(0) {};
	int status;
};


template <class T>
class SLinklist {
public:
	SLinklist();
	int Malloc();
	void Free();
	Vector<T>& search( const T v1);
	int insert(const T v1,int &sort);
	int isempty();
	void print();
	void print(const Vector<T> &ptr);
	T v1;
	int sort;
private:
	int free;
	Vector<T> pser;
	SLinklistNode<T> SL[MAXSIZE];
};


template <class T>
SLinklistNode<T>:: SLinklistNode() : cur(0) {}


template <class T>
SLinklist<T>:: SLinklist() {
	for (int i = 1; i < MAXSIZE-1; i++) {
		SL[i].cur = i + 1;
	}
	SL[0].cur = 0;
	SL[MAXSIZE-1].cur = 0;
	free = 1;
}


template <class T> 
int  SLinklist<T>:: Malloc() {
	int i = free;
	if ( i > 0) {
		free = SL[free].cur;
		SL[i].cur = 0;
	}
	return i;// 不能返回局部变量的引用！
}


template <class T>
void SLinklist<T>:: Free() {
	T v1;
	int i,j;
	if(!isempty()) {
		cout<<"the element you want FREE:";
	    cin>>v1;
		for(j = SL[0].cur; (j != 0) && (SL[j].data != v1); j = SL[j].cur) {
			i = j;
		}
	    SL[i].cur = SL[j].cur;
	    SL[j].cur = free;
	    free = j;
	}
	else cout<<"SLinklist is empty!"<<endl;
}

template <class T>
Vector<T>& SLinklist<T>:: search(const T v1) {
	int i;
	for( i = SL[0].cur; (i != 0) && (SL[i].data != v1); i = SL[i].cur) {}
	if( i != 0) {
		pser.data = SL[i].data;
	    pser.cur = SL[i].cur;
		pser.status = 1;
	}
	return pser;
}


template <class T>
int SLinklist<T>:: insert(const T v1,int& sort) {
	char get;
	int i,j,k = 0,count = 1;
		for( j = SL[0].cur; (count < sort) && (j != 0);++count){
		     k = j;
			 j = SL[j].cur;
		}
		if( isempty() || (j == 0) ) {
			if(isempty()) cout<<"\a"<<"the list is empty,the data is recomended to be the first "<<endl<<"y(yes)/n(no)"<<endl;
			else cout<<"\a"<<"it's the last location,it is reconmended to be the last one"<<endl<<"y(yes)/n(no)"<<endl;
			cin>>get;
			if(get == 'n') return 0;
		}
			if((i = Malloc()) > 0) {  //一定要注意优先级；不确定的统统加括号。Be Ware: bug!!
				SL[i].data = v1;
				SL[k].cur = i;
				SL[i].cur = j;
			}
			else return 0;
	return count;
}


template <class T>
int SLinklist<T>:: isempty() {
	return SL[0].cur == 0;
}


template <class T>
void SLinklist<T>:: print() {
	for(int i = SL[0].cur; i != 0; i = SL[i].cur) {
		cout<<"data: "<<SL[i].data<<" cursorto: "<<SL[i].cur<<endl;
	}
}


template <class T>
void SLinklist<T>:: print(const Vector<T>& ptr) {
	if(ptr.status) {
		cout<<"data: "<<ptr.data<<" cursorto: "<<ptr.cur<<endl;
	}
	else cout<<"\a"<<"none exist."<<endl;
}


int main(int argc, char* argv[]) {
	Vector<int> ptr ;     //指针才要 new(),类的实例对象不用new().
	SLinklist<int> SLL ;
	int info,menu,token = 0;
	int status = 1;
	while(status) {
		system("cls");
		cout<<"*****************************"<<endl;
		cout<<"1.creat & init SLinklist"<<endl;
		cout<<"2.insert data node"<<endl;
		cout<<"3.delete data node"<<endl;
		cout<<"4.search informatin"<<endl;
		cout<<"5.skan all the information"<<endl;
		cout<<"6.quit"<<endl;
		cin.clear();     //重置输入流条件状态为全有效状态；
        fflush(stdin);  //刷新残余输入流，也即清空输入流缓冲区；
        fflush(stdout); //刷新残余输出流，也即清空输出流缓冲区；
		cin>>menu;
		switch(menu) {
			case 1:   break;
			case 2: while(cin>>SLL.v1) {
				while(cin>>SLL.sort) {             // !!!
					if( (info = SLL.insert(SLL.v1,SLL.sort)) > 0 )
						cout<<"it's inserted at "<<info<<" node"<<endl;
					else cout<<"it's not inserted yet."<<endl;
					token = 1;
					break;
				}
				if(token == 0){
					SLL.sort = 1;
					info = SLL.insert(SLL.v1,SLL.sort);
					cout<<"it's inserted in array"<<info<<endl;
				}
				token = 0;
					}
					break;
			case 3: SLL.Free(); break;
			case 4: cout<<"the keyword:";
				    cin>>SLL.v1;
					ptr = SLL.search(SLL.v1);
					SLL.print(ptr); break;
			case 5: SLL.print(); break;
			case 6: status = 0; break;
			default : cout<<"Wrong option! choose again"<<endl; break;
		}

	}
	return 0;
}