当前位置： 首页 > article >正文

【数据结构】单链表基本操作的实现

article 2024/11/20 15:15:12

【单链表的头插和尾插】//无头结点

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode
{
	int date;
	struct LNode *next;
}LNode,*LinkList;
LinkList great_LinkList(LinkList L)//头部插入 
{
	
	LinkList s;
	int x,j=1;
	scanf("%d",&x);
	while(x!=0)
	{
		s=(LNode*)malloc(sizeof(LNode));
		s->date=x;
		s->next=L;
		L=s;
		scanf("%d",&x);
		if(s->next)
		{
			s=s->next;
			j++; 
		}
	}
	printf("表长："); 
	printf("%d\n",j);
	return L;
}
LinkList great_LinkList2(LinkList L)//尾部插入 
{
	LinkList s,r=NULL;
	int x;
	scanf("%d",&x);
	while(x!=0)
	{
		s=(LNode*)malloc(sizeof(LNode));
		s->date=x;
		if(L==NULL)
		L=s;
		else
		r->next=s;
		r=s;
		scanf("%d",&x);
		
	}
	r->next=NULL;//必须要有，不然会死循环 
	return L;
}
LinkList printLink(LinkList L)//链表输出 
{
	if(L==NULL)
	printf("表空\n");
	while(L!=NULL)
	{
		printf("%4d",L->date);
		L=L->next;
	}
	printf("\n");
	return L;
}
int main()
{
	LinkList a=NULL,b=NULL;
	printf("你要输入的数据：\n");
	a=great_LinkList(a);
	printf("头插法："); 
	printLink(a);
	printf("你要输入的数据：\n");
	b=great_LinkList2(b);
	printf("尾插法："); 
	printLink(b);
	return 0;
}

【带头结点的尾插法】

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode
{
	int date;
	struct LNode* next;
}LNode,*LinkList;
LinkList Great_LinkList3()//带头结点的尾插法 
{
	LinkList L=NULL;//头结点 
	LNode *R=NULL;//尾结点
	int x;
	L=(LNode*)malloc(sizeof(LNode));//给头结点申请空间 
	L->next=NULL;//置空表 
	R=L;
	scanf("%d",&x);
	while(x!=0)
	{
		R->next=(LNode*)malloc(sizeof(LNode));//为插入元素申请空间 
		R->next->date=x;
		R=R->next;
		scanf("%d",&x);
	 } 
	R->next=NULL;
	return L;
}
void printLink(LinkList L)//有头结点的输出 
{
	if(L->next==NULL)
	printf("表空！");
	else
	while(L->next!=NULL)
	{
		printf("%4d",L->next->date);
		L=L->next;
	}
	printf("\n");
}
int main()
{
	LinkList a=NULL;
	printf("请输入数据："); 
	a=Great_LinkList3();
	printLink(a);
	return 0;
}

注：加入头结点的目的是操作方便，使得第一个结点的问题不再存在，并使“空表”与“非空表”的处理一致，以下代码段没说有无头结点的都是带头结点的

【带头结点表长】

int length_LinkList(LinkList L)
{
    LinkList p=L;
    int j=0;
    while(p->next)
    {
        p=p->next;
        j++;
    }
    return j;
}

【不带头结点表长】

int Length_LinkList2(LinkList L)
{
    LinkList p=L;
    int j;
    if(p==NULL)
    return 0;
    j=1;
    while(p->next)
    {
        p=p->next;
        j++;
    }
    return j;
}

【按序号查找元素值】

int Locate_LinkList(LinkList L,int i)
{
    LinkList p=L;
    int j=0,x;
    while(p->next!=NULL&&j<i)
    {
        p=p->next;
        j++;
    }
    if(j==i)
    return p->date;
} 

【按序号查找结点的位置】

LinkList Get_LinkList(LinkList L,int i)
{
    LinkList p=L;
    int j=0;
    while(p->next!=NULL&&j<i)
    {
        p=p->next;
        j++;
    }
    if(j==i) return p;
    else return NULL;
} 

【后插结点】 

将s结点插入p结点的后面

（1）s->next=p->next;

（2）p->next=s;

【前插结点】 

将s结点插到p的前面，与后插不同的是，先要找到 p的前驱q，然后在q之后插入，相当于q的后插

（1）while(q->next!=p)

                q=q->next;

（2）s->next=q->next;

（3）q->next=s;

 注：后插结点与前插结点的顺序不能颠倒 ，前插必须先（1）后（2），后插同理

【单链表的插入算法】

void insert_LinkList(LinkList L)//在第i个位置插入x
{
    LinkList p,s;
    int i,x;
    printf("请输入要插入的位置：");
    scanf("%d",&i); 
    p=Get_LinkList(L,i-1);
    printf("请输入要插入的数据："); 
    scanf("%d",&x);
    if(p==NULL)
    {
        printf("参数i错误");
    }
    else
    {
        printf("11");
        s=(LinkList)malloc(sizeof(LNode));
        s->date=x;
        s->next=p->next;
        p->next=s;
    }
}

 【删除结点】

实现对结点*p的删除，找到*p的前继结点*q

q->next=p->next;

free(p);

【单链表的删除算法】 

void Del_LinkList(LinkList L)//删除算法 
{
    LinkList p,s;
    int i;
    printf("请输入要删除的第i个结点：");
    scanf("%d",&i); 
    p=Get_LinkList(L,i-1);
    if(p==NULL)
    {
        printf("第i-1个结点不存在："); 
    }
    else if(p->next==NULL)
    {
        printf("第i个结点不存在："); 
    }
    else
    {
        s=p->next;
        p->next=s->next;
        free(s);
    }
} 

例：实现对单链表的插入、求表长、按序号查找值、按序号查找结点的位置 、在链表中随机插入以及删除链表中的任意值

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode
{
	int date;
	struct LNode* next;
}LNode,*LinkList;
LinkList Great_LinkList3()//带头结点的尾插法 
{
	LinkList L=NULL;//头结点 
	LNode *R=NULL;//尾结点
	int x;
	L=(LNode*)malloc(sizeof(LNode));//给头结点申请空间 
	L->next=NULL;//置空表 
	R=L;
	scanf("%d",&x);
	while(x!=0)
	{
		R->next=(LNode*)malloc(sizeof(LNode));//为插入元素申请空间 
		R->next->date=x;
		R=R->next;
		scanf("%d",&x);
	 } 
	R->next=NULL;
	return L;
}
void printLink(LinkList L)//有头结点的输出 
{
	if(L->next==NULL)
	printf("表空！");
	else
	while(L->next!=NULL)
	{
		printf("%4d",L->next->date);
		L=L->next;
	}
	printf("\n");
}
int length_LinkList(LinkList L)//表长 
{
	LinkList p=L;
	int j=0;
	while(p->next)
	{
		p=p->next;
		j++;
	}
	return j;
}
int Locate_LinkList(LinkList L,int i)//按序号查找值 
{
	LinkList p=L;
	int j=0,x;
	while(p->next!=NULL&&j<i)
	{
		p=p->next;
		j++;
	}
	if(j==i)
	return p->date;
}
LinkList Get_LinkList(LinkList L,int i)//按序号查找结点位置 
{
	LinkList p=L;
	int j=0;
	while(p->next!=NULL&&j<i)
	{
		p=p->next;
		j++;
	}
	if(j==i) return p;
	else return NULL;
}
void insert_LinkList(LinkList L)//在第i个位置插入x
{
	LinkList p,s;
	int i,x;
	printf("请输入要插入的位置：");
	scanf("%d",&i); 
	p=Get_LinkList(L,i-1);
	printf("请输入要插入的数据："); 
	scanf("%d",&x);
	if(p==NULL)
	{
		printf("参数i错误");
	}
	else
	{
		printf("11");
		s=(LinkList)malloc(sizeof(LNode));
		s->date=x;
		s->next=p->next;
		p->next=s;
	}
}
void Del_LinkList(LinkList L)//删除算法 
{
	LinkList p,s;
	int i;
	printf("请输入要删除的第i个结点：");
	scanf("%d",&i); 
	p=Get_LinkList(L,i-1);
	if(p==NULL)
	{
		printf("第i-1个结点不存在："); 
	}
	else if(p->next==NULL)
	{
		printf("第i个结点不存在："); 
	}
	else
	{
		s=p->next;
		p->next=s->next;
		free(s);
	}
}
int main()
{
	LinkList a=NULL;
	int b=0,c=0;
	printf("请输入数据："); 
	a=Great_LinkList3();
	printLink(a);
	b=length_LinkList(a);
	printf("表长：%d\n",b); 
	printf("请输入要查找的元素序号：\n");
	scanf("%d",&c);
	printf("%d\n",Locate_LinkList(a,c)); 
	insert_LinkList(a);
	printf("插入后的链表：");
	printLink(a);
	Del_LinkList(a);
	printf("删除后的链表：");
	printLink(a);
	return 0;
}


http://www.kler.cn/a/132415.html

相关文章：

  • Spring、SpringMVC、SpringBoot、Mybatis小结
  • Pandas-3：数据输入与输出
  • 为何数据库推荐将IPv4地址存储为32位整数而非字符串？
  • 【会话文本nlp】对话文本解析库pyconverse使用教程版本报错、模型下载等问题解决超参数调试
  • sqli—labs靶场 5-8关 （每日4关练习）持续更新！！！
  • 【2】猫眼娱乐后端开发面试题整理
  • pytorch的backward()的底层实现逻辑
  • 滑动窗口题目总结(持续更新中)
  • CGAL Mesh网格分割（基于平面）
  • “流量为王”的时代一去不返！如何押注互联网下一个黄金十年
  • [RK-Linux] recovery分区详解（一）
  • 3GPP TS38.201 NR； Physical layer； General description （Release 18）
  • GEM5 Garnet DVFS / NoC DVFS教程：ruby.clk_domain ruby.voltage_domain
  • Unity 问题 之 Text 组件空格导致 自动/强制 换行 的问题处理
  • JVM虚拟机：垃圾回收器ZGC和Shenandoah算法
  • Unity中Shader纹理的多级渐远Mipmap
  • LLVM学习笔记（62)
  • Flask 接口
  • 每天一道算法题：216. 组合总和 III
  • 【智能家居】4、智能家居框架设计和代码文件工程建立
  • ​软考-高级-系统架构设计师教程（清华第2版）【第12章 信息系统架构设计理论与实践（P420~465）-思维导图】​
  • 浅谈智能安全配电装置应用在银行配电系统中
  • 运行软件报错mfc140.dll丢失？分享mfc140.dll丢失的解决方法
  • Kafka中topic（主题）、broker（代理）、partition（分区）和replication（副本）它们的关系
  • Java基础笔记
  • Java将List转换为Tree数据