【数据结构】链表

57 阅读 0 评论 38 点赞

我是靠谱客的博主酷酷信封，最近开发中收集的这篇文章主要介绍【数据结构】链表，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

基础链表操作：

#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;
}