数据结构实验+链表的基本操作

亦凉 2022-11-05 14:51 176阅读 0赞

## 链表的基本操作 ##

#include <stdio.h>
    
    //2-1存储结构
    typedef struct LNode
    {
    	int data;
    	struct LNode *next;
    }LNode,*LinkList;
    
    //2-2创建一个长度为n的链表、前插法
    void CreatList_H(LinkList &L,int n)   //前插法创建单链表
    {
    	LNode *p;
    	L=new LNode;
    	L->next=NULL;
    	for(int i=0;i<n;++i)
    	{
    		p=new LNode;
    		scanf("%d",&p->data);
    		p->next=L->next;
    		L->next=p;
    	}
    }
    
    //2-2创建一个长度为n的链表、尾插法
    void CreatList_R(LinkList &L,int n)   //后插法创建单链表
    {
    	LNode *p,*r;
    	L=new LNode;
    	L->next=NULL;
    	r=L;
    	for(int i=0;i<n;++i)
    	{
    		p=new LNode;
    		scanf("%d",&p->data);
    		p->next=NULL;
    		r->next=p;
    		r=p;
    	}
    }
    
    //2-3在链表的第i个位置插入一个元素
    void ListInsert(LinkList &L,int i,int e) //在i位置插入e
    {
     	LNode *p,*s;
     	p=L;
     	int j=0;
     	while (p && (j<i-1))
     	{
     		p=p->next;
     		++j;
     	}
    	if(!p || j>i-1) return;
    	s=new LNode;
    	s->data =e;
    	s->next=p->next;
    	p->next=s;
    }
    
    //2-4删除链表的第j个位置的元素
    void ListDelete(LinkList &L,int i) //删除i位置结点
    {
    	LNode *p,*q;
    	p=L;
    	int j=0;
    	while ((p->next) && (j<i-1))
    	{
    		p=p->next;
    		++j;
    	} 
    	if(!(p->next) || (j>i-1)) return;
    	q=p->next;
    	p->next=q->next;
    	delete q;
    }
    
    //2-5获取链表中第k个位置的数据元素的值
    int GetElem(LinkList &L,int i) //获取链表中第i个元素的值
    {
    	LNode *p;
    	p=L->next;
    	int j=1;
    	while (p && j<i)
    	{
    		p=p->next;
    		++j;
    	}
    	if(!p || j>i) return -1;
    	return p->data;
    }
    
    //2-6查找链表中第1个与e相等的元素，若查找成功，则返回该元素在表中的位置序号，若查找失败，则返回0。
    int LocateElem(LinkList L,int e)
    {
    	LNode *p;
    	p=L->next;
    	int j=1;
    	while(p && p->data!=e)
    	{
    		p=p->next;
    		++j;
    	}
    	if(p==NULL)
    		return 0;
    	else
    		return j;
    }
    
    //主函数
    int main()
    {
    	LinkList L;
    	LNode *p;
    	int n,i,j,k,e;
    
    	printf("请输入初始状态的元素个数：");
    	scanf("%d",&n);
    	while(n<1)
    	{
    		printf("元素个数n小于1，请重新输入：");
    		scanf("%d",&n);
    	}
    	printf("请依次输入%d个元素（逆序）：",n);//前插法
    	CreatList_H(L,n);
    	//printf("请依次输入%d个元素：\n",n);//后插法
    	//CreatList_R(L,n);
    	printf("链表中的原始数据为：");
    	p=L->next;
    	while (p!=NULL)
    	{	
    		printf("%4d",p->data);
    		p=p->next;
    	}
    	printf("\n");
    
    	printf("请输入在链表中插入数据的位置i：");
    	scanf("%d",&i);
    	printf("请输入要插入的数据：");
    	scanf("%d",&e);
    	ListInsert(L,i,e);
    	printf("在链表的第%d个位置插入%d后的结果：",i,e);
    	p=L->next;
    	while (p!=NULL)
    	{	
    		printf("%4d",p->data);
    		p=p->next;
    	}
    	printf("\n");
    
    	printf("请输入在链表中删除数据的位置j：");
    	scanf("%d",&j);
    	ListDelete(L,j);
    	printf("删除链表的第%d个元素后的结果：",j);
    	p=L->next;
    	while (p!=NULL)
    	{	
    		printf("%4d",p->data);
    		p=p->next;
    	}
    	printf("\n");
    
    	printf("请输入在链表中获取数据的位置k：");
    	scanf("%d",&k);
    	i=GetElem(L,k);
    	if(i==-1)
    		printf("取值失败。\n");
    	else
    		printf("链表的第%d个元素是%d。\n",k,i);
    
    	printf("请输入在链表中查找的数据e：");
    	scanf("%d",&e);
    	i=LocateElem(L,e);
    	if(i==0)
    		printf("查找失败。\n");
    	else
    		printf("查找成功，元素%d在链表的第%d个位置。\n",e,i);
    }

![Xnip2020-12-21\_22-05-53][Xnip2020-12-21_22-05-53]

[Xnip2020-12-21_22-05-53]: /images/20221023/62a58c01cfa94cf1a508c9b1fd7a4b97.png