【数据结构】链表

基础链表操作：

#include<iostream>
#include<stack>
#include<cstdlib>
#include<cstdio>
using namespace std;
int n,j,pos;
typedef struct LNode{
        int data;
        struct LNode *next;
}LNode,*LinkList;

bool Linklist_Init(LinkList &L){  //初始化
	 L=new LNode;
	 L->next=NULL;
	 return true;
}

void Linklist_creatR(LinkList &L,int n){  //后插法建表
	 LNode *r;
	 LNode *p;
	 r=L;
	 for(int i=0;i<n;i++){
	 	p=new LNode;
	 	cin>>p->data;
	 	p->next=NULL;
	 	r->next=p;
	 	r=p;
	 }

}

bool Linklist_Insert(LinkList &L,int i,int e){ //插入
	 LNode *p;
	 p=L;
	 j=0;
	 while(p&&(j<i-1)){
	 	p=p->next;
	 	++j;
	 }
	 if(!p||j>i-1)
	 return false;
	 LNode *s;
	 s=new LNode;
	 s->data=e;
	 s->next=p->next;
	 p->next=s;
	 n++;
	 return true;
}
bool Linklist_Delete(LinkList &L,int i){ //删除
	 LNode *p;
	 LNode *q;
	 p=L;
	 j=0;
	 while((p->next)&&(j<i-1)){
	 	p=p->next;
	 	++j;
	 }
	 if(!(p->next)||(j>i-1))
		 return false;
   
	 q=p->next;
	 p->next=q->next;
	 delete q;
	 //p->next=p->next->next;
	 return true;

}
LNode *LocateElem(LinkList &L,int e){//按元素值查找
	 LNode *p;
	 p=L->next;
	 pos=1;
	 while(p&&p->data!=e){
	 	p=p->next;
	 	pos++;
	 }
	 return p;
}
void Linklist_Show(LinkList &L){  //显示
	 LNode *p;
	 p=L->next;
//	 int y=n;
//	 while(y){    //虽然n是全局变量，但主函数用了while循环，导致每次刷新后，n未初始化，y无法初始化，程序卡退 
//	 	cout<<p->data<<" ";
//	 	p=p->next;
//	 	y--;
//	 }
    if(p){
		cout<<p->data<<" ";
	    while(p->next){
	    
	    	p=p->next;
			cout<<p->data<<" ";
		} 
	}
	else 
	    cout<<"链表为空，请先创建"<<endl;
	 return; 
}
void menu(){
	 getchar();
     getchar();
     system("cls");
     cout<<"请选择"<<endl;
     cout<<"0,  初始化链表"<<endl;
     cout<<"1,  建表"<<endl;
     cout<<"2,  输出所有元素"<<endl;
     cout<<"3,  删除"<<endl;
     cout<<"4,  插入"<<endl;
     cout<<"5,  退出"<<endl;

}
int main(){
    cout<<"请选择"<<endl;
    cout<<"0,  初始化链表"<<endl;
    cout<<"1,  建表"<<endl;
    cout<<"2,  输出所有元素"<<endl;
    cout<<"3,  删除"<<endl;
    cout<<"4,  插入"<<endl;
    cout<<"5,  退出"<<endl;
    int choose;
	LinkList L=NULL;
	while(cin>>choose){
		switch(choose){
			case 0:{
				if(Linklist_Init(L)){
					cout<<"初始化成功"<<endl;
				}
				else{
				    cout<<"初始化失败"<<endl;
				}
	            menu();
	            continue;
			}
			case 1 :{
				if(L!=NULL){
					cout<<"请输入链表元素个数n"<<endl;
					cin>>n;
					cout<<"请输入n个元素"<<endl;
					Linklist_creatR(L,n);
					cout<<"创建成功！"<<endl;
				}
				else {
					cout<<"链表未初始化"<<endl;
				}
	            menu();
	            continue;
			}
			case 2 :{
				if(L==NULL)
				cout<<"链表未创建"<<endl;
				else
				Linklist_Show(L);
	            menu();
			    continue;
			}
			case 3 :{
				cout<<"请输入要删除的值e"<<endl;
				int e;
				cin>>e;
				LNode *F=LocateElem(L,e);
				if(F==NULL){
					cout<<"没有找到该元素"<<endl<<"链表数据如下："<<endl;
					Linklist_Show(L);
				}
				else {
					if(Linklist_Delete(L,pos)){
						cout<<"删除成功"<<endl<<"链表数据如下："<<endl;
						Linklist_Show(L);
					}
				}
	            menu();
				continue;
			}
			case 4 :{
				cout<<"请输入插入位置t,以及元素值e"<<endl;
				int t,e;
				cin>>t>>e;
				if(Linklist_Insert(L,t,e))
				cout<<"插入成功"<<endl;
				else
				cout<<"插入失败"<<endl;
	            menu();
				continue;
			}
			case 5:{
				cout<<"退出成功！"<<endl;
				break;
			}
			default :{
				cout<<"没有此选项!"<<endl;
	            menu(); continue;
			}
		}
	}
	return 0;
}

约瑟夫环循环链表实现：

#include<iostream>
using namespace std;
struct LNode{
    int data;
    LNode *next;
};
int main(){
	int n,p,k;
	cout<<"请输入数字个数N"<<endl;
	cin>>n;
	cout<<"请输入N个数字"<<endl;
	LNode* L;   //表头 
	LNode* r;   //表尾 (后插法)
	L=new LNode;
	r=new LNode;
	
	L->next=NULL;
	r=L;
	cin>>L->data;     //表头也输入数据，方便操作 
	LNode* pp; 
	for(int i=1;i<=n-2;i++){   //建表 
		pp=new LNode;
	    cin>>pp->data;
	    pp->next=NULL;
		r->next=pp;
		r=pp; 	
	} 
    pp=new LNode;
    cin>>pp->data;  
    pp->next=L;      //循环链表，表位指向表头
    r->next=pp;      //保留最后一个元素的位置 
    
    cout<<"请输入开始位置p,以及循环数k"<<endl;
	cin>>p>>k; 
	cout<<"开始报数"<<endl;
	
	LNode *pos;
	pos=new LNode;  	//先找到开始位置的前驱，方便删除； 
	if(p==1){
	   pos=r->next;	   //第一个元素的前驱是最后一个元素 
	}
	else{
		pos=L;
		int i=1;
		while(i<p-1){
			pos=pos->next;
			i++;
		}
	}
	
	int t=1;   //计数器 
	while(n){
		if(t%k==0){   
			cout<<pos->next->data<<" "; //输出 
			pos->next=pos->next->next;  //删除操作 
			n--; 
		}
		else{
			pos=pos->next;  //往下遍历 
		}
		t++;
	}
	free(L);free(pos);
	free(r);free(pp); 
	cout<<endl<<"报数完毕!"<<endl;    
	return 0;
}