线性表的链式表示

我不是女神ヾ 2022-07-14 15:52 298阅读 0赞

上篇文章是线性表的顺序表示，本篇便是线性表的链式表示。

主函数的步骤包括，输入线性表数据，对链表的删除，插入。利用指针进行对链表的访问。

同时为了增加程序可读性，将结构体定义为LNode，\*linklist。

#include<iostream>
    //线性表的链式表示
    using namespace std;
    typedef struct LNode
    {
    	int data;
    	struct LNode *next;
    }LNode,*linklist;//指向结构体的指针变量 
    int initlist(linklist &l)//初始化链表 
    {
    	l=new LNode;//新的头节点 
    	l->next=NULL;
    	return 1;//成功初始化 
    }
    int getelem(linklist l,int i,int &e)//链表的取值 
    {
    	LNode *p;
    	p=l->next;
    	int j=1;
    	while(p&&i<j)
    	{
    		p=p->next;
    		j++;
    	}
    	if(!p||i>=j)  return 0;
    	e=p->data;
    	return 1;
    }
    int loateelem(linklist l,int e)//查找 
    {
    	linklist p;
    	int i;
    	p=l;
    	while(p)
    	{
    		p=p->next;
    		if (p->data==e)
    		  return 1;
    	}
    	if(!p)
    	 return 0;
    }
    int listinsert(linklist &l,int i,int e)//线性表的插入 
    {
    	linklist p,s;
    	s=new LNode;
    	int j=0;
    	p=l;
    	while(p&&j<(i-1))
    	{
    		p=p->next;
    		j++;
    	}
    	if(!p||j>(i-1))  return 0;
    	s->data=e;
    	s->next=p->next;
    	p->next=s;
    	return 1;
    }
    int listdelet(linklist &l,int i)//链表的删除 
    {
    	linklist p,q;
    	int j=0;
    	p=l;
    	while(p->next && j<(i-1))
    	{
    		p=p->next;
    		j++;
    	}
    	if(!(p->next)||j>(i-1))  return 0;
    	q=p->next;
    	p->next=p->next->next;
    	delete q;
    	
    	return 1;
    }
    void creatlist(linklist &l,int n)//创建链表 
    {
    	l=new LNode;
    	linklist p;
    	l->next=NULL;
    	for(int i=0;i<n;i++)
    	{
    		p=new LNode;
    		cin>>p->data;
    		p->next=l->next;
    		l->next=p;
    	}
    
    }
    int main()
    {
    	linklist l,p;
    	int n,i,j,k;
    	cin>>n;
    	initlist(l);//初始化链表 
    	creatlist(l,n);//创建链表 
    	p=l->next;//p指向首元节点 
    	for(i=0;i<n;i++)
    	{
    		cout<<p->data<<" ";//输出节点的数据域 
    		p=p->next;//p继续指向下一个节点 
    	}
    	cout<<endl<<"删除的数据：";//删除链表数据 
    	cin>>k;
    	if(listdelet(l,k)) 
    	{
    		cout<<"删除成功"<<endl;
    		p=l->next;
    		for(i=0;i<n-1;i++)
    		{
    			cout<<p->data<<" ";//输出节点的数据域 
    			p=p->next;//p继续指向下一个节点 
    		}
    	}
    	else cout<<"删除失败"<<endl;
    	cout<<endl<<"输入插入的位置与数值：";//插入数据 
    	cin>>j>>k;
    	if(listinsert(l,j,k));
    		{	
    			cout<<"插入成功"<<endl;
    			p=l->next;//p指向首元节点 
    			for(i=0;i<n;i++)
    			{
    				cout<<p->data<<" ";//输出节点的数据域 
    				p=p->next;//p继续指向下一个节点 
    			}
    		}
    	if(!listinsert(l,j,k))	cout<<"插入失败"<<endl;
    	return 0;	
    }