数据结构之链表（C++）

墨蓝 2023-02-11 03:21 5阅读 0赞

参考资料：《数据结构与算法（第四版）》机械工业出版社

**链表**是通过一组任意的存储单元来存储线性表中的数据元素的。

### 文章目录 ###

*   *   *  单链表基本操作
         *  数组模拟链表

### 单链表基本操作 ###

**单链表的初始化，表头插入， 表尾插入，删除，任意位置插入，计算表长，显示整个链表，按序号查找，按值查找。**  
C语言代码：[C语言版本][C]  
C++代码：

#include <iostream>
    #include <cstdlib>
    #include <cstdio> 
    using namespace std;
    typedef struct lnode{ 
    	int data;     //定义元素类型为int类型
    	struct lnode *next;   //定义指向下一个元素位置的指针
    }LNode,*LinkList;
    LinkList L=NULL;
    
    //建立线性表链式存储，从表头插入元素
    LinkList Creat_LinkList_1(){ 
    
    	LNode *s;
    	int x,flag=-1;
    	printf("从表头插入元素（-1结束）："); 
    	cin >> x;
    	while(x!=flag){ 
    		s=(LNode *)malloc(sizeof(LNode));
    		s->data=x;
    		s->next=L;
    		L=s;
    		cin >> x;
    	}
    	return L;
    } 
    
    //建立线性表链式存储，从表尾插入元素
    LinkList Creat_LinkList_2(){ 
    	LNode *s,*r=NULL;
    	int x,flag=-1;
    	cin>>x;
    	while(x!=flag){ 
    		s=(LNode *)malloc(sizeof(LNode));
    		s->data=x;
    		if(L==NULL) L=s;
    		else r->next=s;
    		r=s;
    		cin>>x;
    	}
    	if(r!=NULL) r->next=NULL;
    	return L;
    }
    
    //求表长（不带头结点）
    int Length_LinkList(LinkList L){ 
    	LNode *p=L;
    	int j=0;
    	while(p){ 
    		j++;
    		p=p->next; 
    	}
    	return j;
    } 
    
    //按序号查找
    LNode *Get_LinkList(LinkList L,int i){ 
    	LNode *p=L;
    	int j=0;
    	while(p->next!=NULL&&j<i){ 
    		p=p->next;
    		j++;
    	}
    	if(j==i) return p;
    	else return NULL;
    } 
    
    //按值查找 
    LNode *Locate_LinkList(LinkList L,int x){ 
    	LNode *p=L;
    	while(p!=NULL&&p->data!=x){ 
    		p=p->next;	
    	}
    	
    	return p;
    }
    
    //单链表插入
    int Insert_LinkList(LinkList L,int i,int x){ 
    	LNode *p,*s;
    	p=Get_LinkList(L,i-1);
    	if(p==NULL){ 
    		cout<<"插入失败"<<endl;
    		return 0; 
    	}
    	else { 
    		s=(LNode *)malloc(sizeof(LNode));
    		s->data=x;
    		s->next=p->next;
    		p->next=s;
    		return 1;
    	}
    } 
    
    //单链表删除
    int Del_LinkList(LinkList L,int i){ 
    	LinkList p,s;
    	p=Get_LinkList(L,i-1);
    	if(p==NULL){ 
    		cout<<"第i-1个结点不存在"<<endl;
    		return -1; 
    	}
    	else if(p->next==NULL){ 
    		cout<<"第i个结点不存在"<<endl;
    		return 0;
    	}
    	else{ 
    		s=p->next;
    		p->next=s->next;
    		free(s);
    		return 1;
    	}
    } 
    
    //单链表显示
    void show(LinkList L){ 
    	LNode *p=L;
    	for(;p!=NULL;p=p->next)
    		cout<<p->data<<" ";
    	cout<<endl;
    }
    
    //主函数
    int main(){ 
    	int n;
    	printf("从表头/表尾插入元素：1/2 元素+ | 删除操作：D 位置 | 插入操作：I 位置 元素 |\n 序号查找： X | 数值查找： Z | 求表长：C | 显示所有链表：S\n操作次数：");
    	cin>>n;
    	while(n--){ 
    		char a;
    		cin>>a;
    		if(a=='1')   //从表头插入元素
    			Creat_LinkList_1();
    		else if(a=='2')   //从表尾插入元素
    			Creat_LinkList_2();
    		else if(a=='I'){    //从任意位置插入元素
    			int s,d;
    			cin>>s>>d;
    			Insert_LinkList(L,s-1,d);
    		}
    		else if(a=='D'){    //删除元素
    			int s;
    			cin>>s;
    			Del_LinkList(L,s-1);
    		}
    		else if(a=='Z'){    //按值查找元素
    			int x,num=1;
    			LNode *p,*s=L;
    			cin>>x;
    			p=Locate_LinkList(L,x);
    			while(p!=s){ 
    				s=s->next;
    				num++;
    			}
    			cout<<num<<endl;
    		}
    		else if(a=='X'){    //按序号查找元素
    			int x,num=0;
    			LNode *p;
    			cin>>x;
    			p=Get_LinkList(L,x-1);
    			cout<<p->data<<endl;
    		}
    		else if(a=='C')    //求表长
    			cout<<Length_LinkList(L)<<endl;
    		else if(a=='S')   //显示链表所有元素
    			show(L);		
    	}
    	return 0;
    }

![单链表代码实现][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70]  
（数组模拟要比STL快）

### 数组模拟链表 ###

#include<iostream>
    #include<cstdio>
    using namespace std;
    const int N=100010;
    int e[N],ne[N],idx,head;
    
    void Val(){ 
        head=-1;
        idx=0;
    }
    void add_head(int x){ 
        e[idx]=x;
        ne[idx]=head;
        head=idx++;
    }
    void Insert(int k,int x){ 
        e[idx]=x;
        ne[idx]=ne[k];
        ne[k]=idx;
        idx++;
    }
    void Delect(int k){ 
        ne[k]=ne[ne[k]];
    }
    
    int main(){ 
        int n;
        Val();
        scanf("%d",&n);
        getchar();
        while(n--){ 
            char c;
            scanf("%c",&c);
            getchar();
            if(c=='H'){ 
                int b;
                scanf("%d",&b);
                getchar();
                add_head(b);
                
            }
            else if(c=='I'){ 
                int a,b;
                scanf("%d%d",&a,&b);
                getchar();
                Insert(a-1,b);
            }
            else if(c=='D'){ 
                int a;
                scanf("%d",&a);
                getchar();
                if(!a) head=ne[head];
                Delect(a-1);
            }
        }
        for(int i=head;i!=-1;i=ne[i])
          cout<<e[i]<<" ";
        return 0;
    }

[C]: https://paste.ubuntu.com/p/HxsBQYrdRh/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200521215307770.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw==,size_16,color_FFFFFF,t_70