首页 > 其他分享 >C语言单链表代码实现

C语言单链表代码实现

时间：2024-04-10 22:30:21浏览次数：21  
标签：10 head 单链 int 代码 next LinkList printf C语言

声明：著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

设计算法，实现线性结构上的单链表的产生以及元素的查找、插入与删除，求表长、有序表插入、元素逆置、2个有序表合并等。

#include <stdio.h>
#include <stdlib.h>

//单链表的定义：
typedef int DataType;		//DataType可以是任何相应的数据类型如int, float或char

typedef struct ListNode			//结点类型定义
{	DataType data;			//结点的数据域
	struct ListNode *next;		//结点的指针域
}ListNode;

typedef ListNode *LinkList;
//测试用例		1 2 3 4 5 6 7 8 9 10 -1
			//	4 6 8 10 12 -1
int main()
{
	int i,j;
	DataType key,x;
	LinkList head=NULL;

	LinkList CreateList();
	void PrintList(LinkList head);
	int LocateNode(LinkList head,DataType key);
	void InsertList(LinkList head,DataType x,int i);
	void DeleteList(LinkList head,int i);
    void ChangeCircList(LinkList head);
	void PrintCircList(LinkList head);
	void InsertOrderList(LinkList head,int x);
	LinkList reverseList(LinkList head);
	void MergeList_L(LinkList La,LinkList Lb,LinkList *Lc);

	char choice;
	while (1)
	{
		system("cls");
		printf("\n\n\n\n");
		printf("\t\t              链表操作  \n");
		printf("\t\t======================================");
		printf("\n\n");
		printf("\t\t             1：建立单链表            \n");
		printf("\t\t             2：显示单链表            \n");
		printf("\t\t             3：查找                  \n");
		printf("\t\t             4：插入                  \n");
		printf("\t\t             5：删除                  \n");
        printf("\t\t             6：改为循环单链表并显示  \n");
        printf("\t\t             7：有序表插入            \n");
        printf("\t\t             8：元素逆置              \n");
        printf("\t\t             9：2个有序表合并         \n");
		printf("\n");
		printf("\t\t             0：退出        \n");
		printf("\n");
		printf("\t\t请选择：");

		choice = getchar();
		system("cls");

		switch(choice)
		{
			case '1':
				printf("输入单链表：");
				head=CreateList();
				printf("链表创建成功！\n");
				getchar();/*第一个getchar会接收到上面createList函数中scanf最后敲击的回车
所以后面再加一个，这样系统才会等待下一个字符进入，才能看得到东西 */
				getchar();
				break;
			case '2':
				PrintList(head);
				getchar();
                getchar();
				break;
			case '3':
		        printf("输入要查找的值：");
            	scanf("%d",&key);
            	j=LocateNode(head,key);	//单链表查找
				printf("要查找的值在第%d个\n",j);
				getchar();
				getchar();
				break;
			case '4':
				printf("请输入欲插入元素的位置：");
	            scanf("%d",&i);
             	printf("请输入欲插入的元素：");
	            scanf("%d",&x);
	            InsertList(head,x,i);	//单链表插入
	            PrintList(head);			//输出顺序表
				getchar();
				getchar();
				break;
			case '5':
				printf("请输入欲删除结点的位置：");
	            scanf("%d",&i);
	            DeleteList(head,i);		//单链表删除
	            PrintList(head);			//输出顺序表
				getchar();
				getchar();
				break;
			case '6':
                ChangeCircList(head);	//修改为循环单链表
                printf("改为循环单链表成功：\n");
				PrintCircList(head);	//输出循环单链表
				getchar();
				getchar();

				break;
			case '7':
				printf("请输入欲插入有序表的元素：");
	            scanf("%d",&x);
				InsertOrderList(head,x);
				PrintList(head);
				getchar();
				getchar();
				break;
			case '8':
				head=reverseList(head);
				printf("逆置成功\n");
				PrintList(head);
				getchar();
				getchar();
				break;
			case '9':
				printf("输入要被合并的顺序表：");
				LinkList Lb;
				LinkList Lc;
				Lb=CreateList();
				printf("链表创建成功！\n");
				MergeList_L(head,Lb,&Lc);
				printf("顺序表合并成功！\n");
				PrintList(Lc);
				getchar();
				getchar();
				break;
			case '0':
				exit(0);
		}
	}
}

LinkList CreateList()
{
    int num;
    int head_data;
    struct ListNode *s, *r, *h = (struct ListNode *)malloc(sizeof(struct ListNode));
    scanf("%d", &head_data);
    h->data = head_data;
    r = h; /* 尾指针初值指向头结点 */
    scanf("%d", &num);
    while (num != -1)
    {
        s = (struct ListNode *)malloc(sizeof(struct ListNode)); /* 生成新结点*/
        if (s == NULL)
        {
            printf("内存分配失败\n");
            exit(-1);
        }
        s->data = num;
        r->next = s;

        r = s;
        scanf("%d", &num); // 更新输入的 num 值
    }
    r->next = NULL;
    return h; /* 返回头指针 */
}

//单链表的输出：
void PrintList(LinkList head)
{
	int c=0;
    LinkList cur;
    if (head != NULL)
        cur = head;
    else{
        printf("no node");
        return;
    };
	while (cur != NULL){
        printf("%d ", cur->data);
        c++;
        cur = cur->next;
	}
	printf("\n现在表长为：%d", c);
	return;

}

//单链表的查找：
int LocateNode(LinkList head,DataType key)
{
	int c=1;
	ListNode *p=head;//->next; /* 从开始结点比较 */
 	while (p&&p->data!=key){ /* 直到 p 为 NULL 或 p->data 是 key为止 */
 	p=p->next; /* 扫描下一结点 */
 	c++;}
 	return c;
}

//单链表的插入：
void InsertList(LinkList head,DataType x,int i)
{
	ListNode *p=head,*s;
	int j=0;
	int c=2;/* 寻找第 i-1 个结点 */
 	while (p&&c<i){ /* 直到 p 为 NULL 或 p->data 是 key为止 */
 	p=p->next; /* 扫描下一结点 */
 	c++;
	 }
if(p==NULL){
printf(" 插入位置非法 \n");
exit(0);
}
s=(LinkList)malloc(sizeof(ListNode));
s->data=x;
s->next=p->next;
 p->next=s;
}

//单链表的删除：
void DeleteList(LinkList head,int i)
{
	 ListNode *p=head,*q;
 int c=2;/* 寻找第 i-1 个结点 */
 	while (p&&c<i){ /* 直到 p 为 NULL 或 p->data 是 key为止 */
 	p=p->next; /* 扫描下一结点 */
 	c++;
	 }
 if(p==NULL||p->next==NULL){
 printf(" 删除位置非法 \n");
 exit(0);
 }
 q=p->next; // 临时保存被删结点的地址以备释放
 p->next=q->next; // 改变删除结点前驱结点的指针域

 free(q); // 释放删除结点的空间
}


//修改为循环单链表：
void ChangeCircList(LinkList head)
{
	ListNode *p=head;//->next; /* 从开始结点比较 */
 	while (p->next)/* 直到 p->next 为 NULL是 key为止 */
 	p=p->next; /* 扫描下一结点 */
 	p->next=head;

}


//循环单链表的输出：
void PrintCircList(LinkList head)
{
	LinkList cur;
	int c=0;
    if (head != NULL)
        cur = head;
    else{
        printf("no node");
        return;
    };
	while (cur->next != head){
        printf("%d ", cur->data);
        cur = cur->next;
        c++;
	}

	printf("%d ", cur->data);
	c++;
	printf("\n现在表长为：%d ", c);
	return;
}

void InsertOrderList(LinkList head,int x)
{
	ListNode *p=head,*s;
	int j=0;
 	while (p->data<x){
 	p=p->next; /* 扫描下一结点 */
  }
s=(LinkList)malloc(sizeof(ListNode));
s->data=x;
s->next=p->next;
 p->next=s;
}

LinkList reverseList(LinkList head)
{
	if (head == NULL || head->next == NULL) {
        return head;
    }
    // 例：1->2->3->4->5-null，从 if 递归出口返回时 newHead = 5, head = 4（递归特点：谁调用返回给谁）
    LinkList newHead =reverseList(head->next);
    // head = 4, newHead = 5, head.next.next = 4.next.next = 5.next = 4
    head->next->next = head;
    // 避免链表成环，5->4->null
    head->next = NULL;
    // 返回新的头节点
   	return newHead;
}


void MergeList_L(LinkList La, LinkList Lb, LinkList *Lc) { // 修改参数类型，
    LinkList pa = La;
    LinkList pb = Lb;
    LinkList pc;

    if (La->data < Lb->data) {
        pc = La;
        *Lc = La;
        pa = La->next;
    } else {
        pc = Lb;
        *Lc = Lb;
        pb = Lb->next;
    }

    while (pa && pb) {
        if (pa->data <= pb->data) {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        } else {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }

    pc->next = pa != NULL ? pa : pb; // 插入剩余段
    //free(Lb);
}
四、运行输出结果：
LinkList CreateList();
输入单链表：1 2 3 4 5 6 7 8 9 10 -1
链表创建成功！
	void PrintList(LinkList head);
1 2 3 4 5 6 7 8 9 10
现在表长为：10
	int LocateNode(LinkList head,DataType key);
输入要查找的值：5
要查找的值在第5个
	void InsertList(LinkList head,DataType x,int i);
请输入欲插入元素的位置：2
请输入欲插入的元素：4
1 4 2 3 4 5 6 7 8 9 10
现在表长为：11
	void DeleteList(LinkList head,int i);
请输入欲删除结点的位置：2
1 2 3 4 5 6 7 8 9 10
现在表长为：10
void ChangeCircList(LinkList head);void PrintCircList(LinkList head);
改为循环单链表成功：
1 2 3 4 5 6 7 8 9 10
现在表长为：10
	void InsertOrderList(LinkList head,int x);
请输入欲插入有序表的元素：4
1 2 3 4 4 5 6 7 8 9 10
现在表长为：11
	LinkList reverseList(LinkList head);
逆置成功
10 9 8 7 6 5 4 3 2 1
现在表长为：10
	void MergeList_L(LinkList La,LinkList Lb,LinkList *Lc);
输入要被合并的顺序表：4 6 8 10 12 -1
链表创建成功！
顺序表合并成功！
1 2 3 4 4 5 6 6 7 8 8 9 10 10 12
现在表长为：15

运行输出结果：

LinkList CreateList();

输入单链表：1 2 3 4 5 6 7 8 9 10 -1

链表创建成功！

void PrintList(LinkList head);

1 2 3 4 5 6 7 8 9 10

现在表长为：10

int LocateNode(LinkList head,DataType key);

输入要查找的值：5

要查找的值在第5个

void InsertList(LinkList head,DataType x,int i);

请输入欲插入元素的位置：2

请输入欲插入的元素：4

1 4 2 3 4 5 6 7 8 9 10

现在表长为：11

void DeleteList(LinkList head,int i);

请输入欲删除结点的位置：2

1 2 3 4 5 6 7 8 9 10

现在表长为：10

void ChangeCircList(LinkList head);void PrintCircList(LinkList head);

改为循环单链表成功：

1 2 3 4 5 6 7 8 9 10

现在表长为：10

void InsertOrderList(LinkList head,int x);

请输入欲插入有序表的元素：4

1 2 3 4 4 5 6 7 8 9 10

现在表长为：11

LinkList reverseList(LinkList head);

逆置成功

10 9 8 7 6 5 4 3 2 1

现在表长为：10

void MergeList_L(LinkList La,LinkList Lb,LinkList *Lc);

输入要被合并的顺序表：4 6 8 10 12 -1

链表创建成功！

顺序表合并成功！

1 2 3 4 4 5 6 6 7 8 8 9 10 10 12

现在表长为：15

标签：10,head,单链,int,代码,next,LinkList,printf,C语言
From： https://blog.csdn.net/skhoole/article/details/137571590

相关文章

  • AtomGit 代码托管平台评测赛——完整操作指南
    AtomGit优势功能：基于Git的代码管理平台，基础功能完整，并且有一套完整的对照文档，看到了一个新功能代码扫描，是个新鲜点。性能：整体测试，包括5G以内文件测试，都是以自身网速极限的状态完成，性能非常棒。易用性：与git操作无异，方便的是国内网络，配置完基本信息后操作特别顺畅。页面功能......
  • 数据结构：单链表
    一.链表的概念及结构概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。但是在逻辑结构上是顺序的。链表的结构其实就像的火车：车厢是独立存在的，且每节车厢都有车门。想象⼀下这样的场景，假设每节车厢的车门都是锁......
  • C语言笔记二的补充（实例应用）——猜数游戏的简单实现
    猜数字游戏要求：电脑自动生成1~100的随机数玩家猜数字，猜数字的过程中，根据猜测数据的大小给出反馈，直至才对，游戏结束。基础知识搭建：随机数的生成使用rand函数intrand(void);rand函数会返回一个伪随机数，这个随机数的范围是在0~RAND_MAX之间，这个RAND_MAX的大小是依赖编......
  • C语言笔记二——分支和循环（上）
    分支和循环1.if语句1.1if语句的语法形式如下：if(表达式)语句表达式成立（为真）语句执行；表达式不成立（为假）语句不执行。在C语言中，0为假，非0为真。//instance#include<stdio.h>intmain(){  intnum=0;  scanf("%d",&num);  if(num%2==1){   ......
  • 加入预测新数据，最小二乘支持向量机（lssvm）回归预测（多输入单输出）-附代码
    最小二乘支持向量机（lssvm）回归预测最小二乘支持向量机（LeastSquaresSupportVectorMachine,LS-SVM）是支持向量机（SupportVectorMachine,SVM）的一种变体，用于回归问题。其原理基本上与标准的支持向量机相似，但在损失函数和优化过程上有所不同。最小二乘支持向量机（LS-SVM）回归预......
  • C语言: 字符串函数(下)
    片头在上一篇中,我们介绍了字符串函数。在这一篇章中，我们将继续学习字符串函数，准备好了吗？开始咯！1.strncpy函数1.1strncpy函数的用法strncpy是C语言中的一个字符串处理函数，它用于将一个字符串的一部分内容复制到另一个字符串中。其函数原型为:char*strncpy(char*dest......
  • 用代码验证，esm 导出的是值的引用，commonjs导出的是值的拷贝
    首先需要学习一下esm和commonjs的区别，其中一条关于导出值我们可以手动验证一下，先记住结论esm导出的是值的引用commonjs导出的是值的拷贝没错我又遇到这个问题了，面试官先问我commonjs和esm有啥区别？然后问如果commonjs导出一个模块，在模块内部改变一个值，模块外部......
  • 用本小组项目中实际的例子来重现如下问题： 1、代码覆盖率对于“应该写但是没有写的代
    例子1-代码覆盖率无法检测资源管理问题：假设在移动充电桩应用中有一个负责与服务器通信的模块，它从服务器下载充电站的实时状态信息。开发者编写了一段代码来连接服务器、发送请求并接收响应数据，但是在处理完响应后，忘记关闭网络连接或释放相关资源：JavapublicclassChargingSta......
  • C语言分支和循环详解
    在程序中基础的三种结构为顺序结构,选择结构(分支结构),循环结构,几乎所有日常可见的事均可分为这三种结构或者这三种结构的组合.今天,我们就来详细了解一下关于C语言分支和循环语句.在正式介绍之前呢,先给大家提及一下C语言的控制语句:C语言共有9种控制语句,可以分为3类:......
  • Obsidian自定义代码块样式成Typora
    先来效果图修改前效果:修改后效果:编辑模式:预览模式:两种模式的表现间距略有不同,但不影响.添加自定义css样式.markdown-source-view.mod-cm6.cm-content>.HyperMD-codeblock{border-width:01px01px;border-style:solid;border-color:#E7EAE......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99