单链表

//存储char类型的单链表 
#include<iostream> 
using namespace std;
struct LNode{
	char data;
	LNode *next;
};
class LinkList{
	private:
		LNode *head;
	public:	
		LNode *createLinkListHead();//头插法创建 
		LNode *createLinkListTail(); //尾插法创建
		int length();//链表长 
		bool empty();//判空
		void show();//输出整个链表 
		
		 //增 
		int insert(int i,char x);//插入一个元素 
		int push_back(char x);//尾插
		int push_front(char x);//头插
		
		 //删 
		int erase(int i);//删除一个元素
		int clear();//清空?
		
		//改
		int updateNode(int i,char x); 
		
		//查 
		char get(int i);//按序号查找
		int locate(char x);//按值查找 
	
};



//头插法建立单链表，数据读入顺序与链表顺序相反

LNode *LinkList::createLinkListHead(){
	char flag=‘.‘;
	LNode *s;
	char x;
	cout<<"输入一串字符‘.‘输入结束。 ";
	cin>>x; 	
	while(x!=flag){
		s=new LNode;
		s->data=x;
		s->next=head->next;
		head->next=s;
		cout<<"please input a char(flag=‘.‘):";
		cin>>x;
	}
	return head;
} 
LNode *LinkList::createLinkListTail(){
	LNode *s,*rear;
	char x;
	cout<<"输入一串字符‘.‘输入结束。 ";
	cin>>x;
	head->next=rear=NULL;
	while(x!=‘.‘){
		s=new LNode();
		s->data=x;
		if(head->next==NULL)
			head->next=s;
		else
			rear->next=s;
		rear=s;
		cin>>x;
	}
	return head;
}
int LinkList::length(){
	int i=0;
	LNode *p;
	p=head;
	while(p->next){
		i++;
		p=p->next;
	}
	return i;
}
bool LinkList::empty(){
	if(head->next==NULL){
		return true;
	}
	return false;
} 
void LinkList::show(){
	LNode *p=head;
	if(p->next==NULL){
		cout<<"表空"; 
	}
	while(p->next!=NULL){
		cout<<p->next->data;
		p=p->next;
	}
	cout<<endl;
}

int LinkList::insert(int i,char x){
	LNode *p=head;
	while(i--){
		p=p->next;
	}
	LNode *s=new LNode;
	s->data=x;
	s->next=p->next;
	p->next=s;
	return 1;
	
}


int LinkList::push_back(char x){
	LNode *p=head,*s;
	while(p->next){
		p=p->next;
	}	
	s=new LNode;
	s->data=x;
	s->next=NULL; 
	p->next=s;
	return 1;
}
int LinkList::push_front(char x){
	LNode *p=new LNode;
	p->data=x;
	p->next=head->next;
	head->next=p;
	return 1;
}
int LinkList::erase(int i){
	LNode *p=head,*s;
	while(i--){
		p=p->next;
	}
	
	s=p->next;
	p->next=s->next; 
	delete s;
	return 1;
}
int LinkList::clear(){
	LNode *p;
	p=head;
	while(p->next){
		LNode *s=new LNode;
		s=p->next;
		p->next=s->next; 
		delete s;
	}
}
int LinkList::updateNode(int i,char x){
	LNode *p,*s,*t;
	p=head;
	while(i--){
		p=p->next;
	}
	t=p->next;
	s=new LNode;
	s->data=x;
	s->next=t->next;
	p->next=s;
	delete t;
}
char LinkList::get(int i){
	LNode *p;
	p=head->next;
	while(i--){
		p=p->next;
	}
	return p->data;
}
int LinkList::locate(char x){
	int i;
	LNode *p;
	p=head->next;
	while(p->data!=x){
		p=p->next;
		i++;
	}
	return i;
}