1. Toy模板网首页
  2. > Toy博客

数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题

7月前 作者：海绵宝宝de派小星 分类：Toy博客 阅读(47) 违法举报

这篇具有很好参考价值的文章主要介绍了数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

写在前面

实验的写法多种多样，但本文并未采用#define定义容量的写法，这样写已经是很老旧过时的写法。所有实验主体采用均为动态开辟，后续如果利用C++来写或许会应用更多语法…

本篇展示数据结构的两个实验

其中，重点分析约瑟夫问题

实验中代码的命名风格等均与下方博客风格类似，全程手撕图解

对顺序表和链表不清楚有以下文章介绍

手撕顺序表
手撕单链表

掌握顺序表和单链表后 实验均为上述的简单应用

顺序表的合并

定义线性表的顺序存储结构，并使用定义的结构实现两个线性表的合并。（建立两个有序顺序表，将两个有序顺序表合并为一个有序顺序表）。
内容要求：
建立有序表：12，23，46，67，85
建立有序表：5，59，94
两个有序顺序表合并为一个有序顺序表，验证代码的正确性。

代码实现

//建立有序表：12，23，46，67，85
//建立有序表：5，59，94
//两个有序顺序表合并为一个有序顺序表，验证代码的正确性。

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

typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* a;
	int size;
	int capacity;
}SeqList;

void SListInit(SeqList* ps)
{
	//assert(ps);
	ps->size = 0;
	ps->capacity = 4;
	ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
}

void SListDestroy(SeqList* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->size = 0;
}

void SListCheckCapacity(SeqList* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		SLDataType* tmp = NULL;
		tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * (ps->capacity) * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->a = tmp;
		ps->capacity *= 2;
		//printf("The capacity now:%d\n", ps->capacity);
	}
	else
	{
		return;
	}
}

void SListPushBack(SeqList* ps, SLDataType x)
{
	assert(ps);
	SListCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}

void SListPrint(SeqList* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

void SListMerge(SeqList* ps1, SeqList* ps2)
{
	assert(ps1);
	assert(ps2);
	SeqList ps;
	SListInit(&ps);
	int cur1 = 0, cur2 = 0;
	while (cur1 < ps1->size && cur2 < ps2->size)
	{
		if (ps1->a[cur1] <= ps2->a[cur2])
		{
			SListPushBack(&ps, ps1->a[cur1]);
			cur1++;
		}
		else
		{
			SListPushBack(&ps, ps2->a[cur2]);
			cur2++;
		}
	}
	while (cur1 < ps1->size)
	{
		SListPushBack(&ps, ps1->a[cur1]);
		cur1++;
	}
	while (cur2 < ps2->size)
	{
		SListPushBack(&ps, ps2->a[cur2]);
		cur2++;
	}
	printf("The result of merging two seqlists is:\n");
	SListPrint(&ps);
}

int main()
{
	SeqList ps1;
	SeqList ps2;
	SListInit(&ps1);
	SListInit(&ps2);
	int quantity1 = 0, quantity2 = 0, input = 0;

	printf("Input quantity of seqlist1-> ");
	scanf("%d", &quantity1);
	for (int i = 0; i < quantity1; i++)
	{
		scanf("%d", &input);
		SListPushBack(&ps1, input);
	}

	printf("Input quantity of seqlist2-> ");
	scanf("%d", &quantity2);
	for (int i = 0; i < quantity2; i++)
	{
		scanf("%d", &input);
		SListPushBack(&ps2, input);
	}

	SListMerge(&ps1, &ps2);
	return 0;
}

代码下载

Gitee下载链接

链表的基本操作

定义线性表的链式存储结构，定义结点类型，并使用定义的结构实现链表的创建，插入，删除、查询、输出等基本操作。
通讯录管理（必做内容） ； 约瑟夫环（选做内容）
必做内容要求：
1.通讯者的结点类型定义如下：
typedef struct {
char num[5] ; //编号
char name[9] ; //姓名
char sex[3] ; //性别
char phone[13]; //电话
char addr[31] ; //地址
]DataType ;
2.线性表的链式存储结构定义如下：
typedef struct node { //结点类型定义
DataType data ; //结点数据域
struct node * next ; //结点指针域
} ListNode ;
typedef ListNode * LinkList ;
ListNode * p ; //定义一个指向结点的指针变量
LinkList head ; //定义指向单链表的头指针
3.主控菜单设计要求
程序运行后，给出6个菜单项的内容和输入提示：

  1. 通讯录链表的建立
  2. 通讯者结点的插入
  3. 通讯者结点的查询
  4. 通讯者结点的删除
  5. 通讯录链表的输出
  6. 退出管理系统
    请选择 0——5
    使用数字0——5来选择菜单项，其他输入则不起作用。

选做内容要求：
约瑟夫（Joseph）问题的一种描述是：30个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分。因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免于难。无奈，大家只好同意这种办法，并议定30个人围成一圈，由第一个人数起，依次报数，数到第9人，便把他投入大海，然后再从他的下一个人数起，数到第9人，再将他扔进大海中，如此循环地进行，直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置？

1.利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各人的编号。
2.为了不失一般性，将30改为一个任意输入的正整数n，而报数上限（原为9）也为一个任选的正整数k。这样该算法描述如下：
（1）创建含有n个结点的单循环链表；
（2）生者与死者的选择：
p指向链表第一个结点，初始i 置为1；
while (i<=n/2) //删除一半的结点
{ 从p指向的结点沿链前进k-1步；
删除第k个结点（q所指向的结点）；p指向q的下一个结点；
输出其位置q->data；
i自增1；
}
（3）输出所有生者的位置。

3.测试结果
对于总人数30，报数上限为9，则
死者编号为：9，18，27，6，16，26，7，19，30，12，24，8，22，5，23
生者编号为：1，2，3，4，10，11，13，14，15，17，20，21，25，28，29

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <stdbool.h>

typedef  struct
{
	char  num[5];    //编号
	char  name[9];   //姓名
	char  sex[3];     //性别
	char  phone[13];  //电话
	char  addr[31];   //地址
}DataType;

typedef struct node
{
	DataType data;
	struct node* next;
}ListNode;

//头节点用head
//定义一个指向结点的指针变量 ListNode* p;

ListNode* BuyListNode(DataType x);

void ListNodePush(ListNode** phead);

DataType Buynewdata();

void ListNodePrint(ListNode** phead);

int ListNodeFind(ListNode* head, const char* Findname);

void ListNodePop(ListNode** phead, const char* Popname);

ListNode* BuyListNode(DataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->next = NULL;
	newnode->data = x;
	return newnode;
}

DataType Buynewdata()
{
	DataType newdata;
	printf("请依次输入编号 姓名 性别 电话 地址\n");
	scanf("%s %s %s %s %s",
		newdata.num, newdata.name, newdata.sex, newdata.phone, newdata.addr);
	return  newdata;
}

void ListNodePush(ListNode** phead)
{
	assert(phead);
	ListNode* newnode = BuyListNode(Buynewdata());
	if (*phead == NULL)
	{
		*phead = newnode;
	}
	else
	{
		newnode->next = *phead;
		*phead = newnode;
	}
}

void ListNodePrint(ListNode** phead)
{
	ListNode* cur = *phead;
	printf("%-5s%-10s%-8s%-13s%-31s\n",
		"编号", "姓名", "性别", "电话", "地址");
	while (cur)
	{
		printf("%-5s%-10s%-8s%-13s%-31s\n",
			cur->data.num, cur->data.name, cur->data.sex,
			cur->data.phone, cur->data.addr);
		cur = cur->next;
	}
}

int ListNodeFind(ListNode* head, const char* Findname)
{
	ListNode* cur = head;
	while (cur)
	{
		if (strcmp(Findname, cur->data.name) == 0)
		{
			printf("找到了,该人的信息如下\n");
			printf("%-5s%-10s%-8s%-13s%-31s\n",
				"编号", "姓名", "性别", "电话", "地址");
			printf("%-5s%-10s%-8s%-13s%-31s\n",
				cur->data.num, cur->data.name, cur->data.sex,
				cur->data.phone, cur->data.addr);
			return 1;
		}
		else
		{
			cur = cur->next;
		}
	}
	printf("找不到信息\n");
	return 0;
}

void ListNodePop(ListNode** phead, const char* Popname)
{
	assert(*phead);
	assert(phead);
	if (ListNodeFind(*phead, Popname))
	{
		ListNode* Findnode = *phead;
		ListNode* prev = *phead;
		while (strcmp(Findnode->data.name, Popname) != 0)
		{
			prev = Findnode;
			Findnode = Findnode->next;
		}
		prev->next = Findnode->next;
		free(Findnode);
		Findnode = NULL;
		printf("删除该人信息成功\n");
		return;
	}
	else
	{
		printf("找不到该人信息\n");
		return;
	}
}

void menu()
{
	printf("*********************************************\n");
	printf("****1.建立信息表************** 2.插入信息 ****\n");
	printf("****3.查询信息  ************** 4.删除信息 ****\n");
	printf("****5.打印信息  ************** 0.退出     ****\n");
	printf("*********************************************\n");
}

void SetupListNode(ListNode** phead)
{
	int num = 0;
	printf("建立链表成功，开始录入信息\n");
	printf("输入要录取信息的个数->");
	scanf("%d", &num);
	while (num--)
	{
		ListNodePush(phead);
	}
}

void FindFunction(ListNode* head)
{
	char Findname[20] = { 0 };
	printf("输入要查找的人名");
	scanf("%s", Findname);
	ListNodeFind(head, Findname);
}

void PopFunction(ListNode** phead)
{
	char Popname[20] = { 0 };
	printf("输入要查找的人名");
	scanf("%s", Popname);
	ListNodePop(phead, Popname);
}

int main()
{
	menu();
	int input = 0;
	ListNode* head = NULL;
	do
	{
		printf("请选择->");
		scanf("%d", &input);
		switch (input)
		{
		case 1:
			SetupListNode(&head);
			break;
		case 2:
			if (head == NULL)
			{
				printf("通讯录还未建立，请先建立\n");
				break;
			}
			else
			{
				ListNodePush(&head);
				break;
			}
		case 3:
			if (head == NULL)
			{
				printf("通讯录还未建立，请先建立\n");
				break;
			}
			else
			{
				FindFunction(head);
				break;
			}
		case 4:
			if (head == NULL)
			{
				printf("通讯录还未建立，请先建立\n");
				break;
			}
			else
			{
				PopFunction(&head);
				break;
			}
		case 5:
			if (head == NULL)
			{
				printf("通讯录还未建立，请先建立\n");
				break;
			}
			else
			{
				ListNodePrint(&head);
				break;
			}
		case 0:
			break;
		default:
			printf("请重新选择\n");
			break;
		}
		menu();
	} while (input);
	return 0;
}

代码下载

Gitee下载链接

约瑟夫问题

问题分析

约瑟夫（Joseph）问题的一种描述是：30个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分。因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免于难。无奈，大家只好同意这种办法，并议定30个人围成一圈，由第一个人数起，依次报数，数到第9人，便把他投入大海，然后再从他的下一个人数起，数到第9人，再将他扔进大海中，如此循环地进行，直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置？

  1. 利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各人的编号。
  2. 为了不失一般性，将30改为一个任意输入的正整数n，而报数上限（原为9）也为一个任选的正整数k。这样该算法描述如下：
（1） 创建含有n个结点的单循环链表；

（2） 生者与死者的选择：

p指向链表第一个结点，初始i 置为1；

while (i<=n/2)   //删除一半的结点

{  
从p指向的结点沿链前进k-1步；

删除第k个结点（q所指向的结点）；

p指向q的下一个结点；

输出其位置q->data；

i自增1；
}

（3） 输出所有生者的位置。
  1. 测试结果
    对于总人数30，报数上限为9，则
    死者编号为：9，18，27，6，16，26，7，19，30，12，24，8，22，5，23
    生者编号为：1，2，3，4，10，11，13，14，15，17，20，21，25，28，29

传统的约瑟夫问题可以采用循环数组来解决，在前面介绍vector中就提及过利用循环数组解决约瑟夫问题，那么这里题目要求我们用链表来解决这个问题

那么现在整个流程就分为这么几个阶段，首先要搭建好链表，其次将数据插入进链表中，再把所求元素删除链表外，最后将链表输出即可

整个流程中需要注意的有下面几个问题

1. 要解决循环链表问题

通过画图就能知道，每次要让尾节点指向头，每次插入后都需要找到尾节点，改变尾节点的指向

数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题,知识总结,数据结构,c语言,数据结构,链表,c语言
2. 要解决如何找到要删元素的问题

首先说明思路：思路就是把定义一个cur指针，这个指针用来指向要删除的节点，这个思路本身是没有问题的，但是问题在于在实现代码过程中出现了问题

第一个问题在于cur在找要删除元素的过程中是需要经过cur=cur->next，问题就在于循环几次
这个题的要求是删15个元素，每次报到9就删除，因此实际上cur只需要循环8次就能推进到9的位置

第二个问题是删除元素后导致前后不一致的问题，删除元素后如果未对cur节点进行处理，那么cur元素当前位置和最初始的位置实际上是不一样的，假设链表元素是1，2，3…依次排序，那么cur又开始指向1，经过遍历，现在要删除的是元素9，删除掉元素9后，实际上应该对cur再推进一次，这样cur才能指向初始位置的"1"

解决这两个问题后续过程就很简单了，这里代码并没有提前进行宏定义，后续需要进行改变直接进行修改数据即可文章来源地址https://www.toymoban.com/news/detail-562751.html

代码实现

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

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
}ListNode;

void ListNodePush(ListNode** phead,LTDataType x)
{
	assert(phead);
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;

	if (*phead == NULL)
	{
		*phead = newnode;
		newnode->next = newnode;
	}
	else
	{
		ListNode* tail = *phead;
		while (tail->next != *phead)
		{
			tail = tail->next;
		}
		newnode->next = *phead;
		*phead = newnode;
		tail->next = *phead;
	}
}

void ListNodePop(ListNode** phead,ListNode* cur)
{
	ListNode* prev = *phead;
	ListNode* next = *phead;
	while (prev->next != cur)
	{
		prev = prev->next;
	}
	next = cur->next;
	prev->next = next;
	//free(cur);
	//cur = NULL;
}

void ListNodePrint(ListNode* head)
{
	assert(head);
	ListNode* cur = head->next;
	printf("%d->", head->data);
	while (cur!=head)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
}

int main()
{
	ListNode* plist = NULL;
	for (int i = 30; i > 0; i--)
	{
		ListNodePush(&plist, i);
	}
	int a = 15;
	ListNode* cur = plist;
	while (a--)
	{
		for (int i = 0; i < 8; i++)
		{
			cur = cur->next;
		}
		ListNodePop(&plist, cur);
		cur = cur->next;
	}
	ListNodePrint(plist);
	return 0;
}

到了这里，关于数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构和算法初阶(C语言)】复杂链表（随机指针，随机链表的复制）题目详解+链表顺序表结尾

    【数据结构和算法初阶(C语言)】复杂链表（随机指针，随机链表的复制）题目详解+链表顺序表结尾

    目录  1.随机链表的复制 1.2题目描述  1.3题目分析 1.4解题： 2.顺序表和链表对比 2.1cpu高速缓存利用率 3.结语 一个长度为  n  的链表，每个节点包含一个额外增加的随机指针  random   该指针可以指向链表中的任何节点或空节点。        构造这个链表的  深拷贝 。 深拷贝

    2024年03月10日
    浏览(60)
  • 数据结构2.2,将两个非递减的有序链表合并为一个非递增的有序链表，要求结果链表仍使用原来两个链表的存储空间，不占用其他的存储空间。表中允许有重复的数据。

    数据结构2.2,将两个非递减的有序链表合并为一个非递增的有序链表，要求结果链表仍使用原来两个链表的存储空间，不占用其他的存储空间。表中允许有重复的数据。

    大概思路：1.先写出建立链表的函数（creatlist）：分配头节点，尾指针置空。 2.写出插入节点的代码函数：申请一片空间存放要插入的节点，把新插入的节点置空，令指向链表的头节点的下一个指针指向该节点，在把该指针指向新插入的节点。用if函数写出当输入的指小于零时

    2024年02月05日
    浏览(34)
  • ＜数据结构＞ 链表 - 链表的概念及结构

    ＜数据结构＞ 链表 - 链表的概念及结构

    概念： 链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的 逻辑顺序 是通过链表中的 指针链接 次序实现的 1、链表由一系列结点（链表中每一个元素称为结点）组成。 2、结点可以在运行时动态(malloc)生成。 3、每个结点包括两个部分：一个是存储数据元素的

    2023年04月09日
    浏览(32)
  • 【数据结构】反转链表、链表的中间节点、链表的回文结构（单链表OJ题）

    【数据结构】反转链表、链表的中间节点、链表的回文结构（单链表OJ题）

    正如标题所说，本文会图文详细解析三道单链表OJ题，分别为：  反转链表 （简单）  链表的中间节点 （简单）  链表的回文结构 （较难） 把他们放在一起讲的原因是：  反转链表 和  链表的中间节点 是  链表的回文结构 的基础 为什么这样说？请往下看： 目录 1. 反转链

    2024年02月13日
    浏览(39)
  • 【数据结构】顺序表的定义

    【数据结构】顺序表的定义

    🎈个人主页：豌豆射手^ 🎉欢迎 👍点赞✍评论⭐收藏 🤗收录专栏：数据结构 🤝希望本文对您有所裨益，如有不足之处，欢迎在评论区提出指正，让我们共同学习、交流进步！ 在数据结构的世界里，顺序表是一种常见且基础的线性数据结构。它以其简洁、直观的特性，广

    2024年04月08日
    浏览(40)
  • 【数据结构】顺序表的学习

    【数据结构】顺序表的学习

    前言:在之前我们学习了C语言的各种各样的语法，因此我们今天开始学习数据结构这一个模块，因此我们就从第一个部分来开始学习\\\" 顺序表 \\\"。 💖 博主CSDN主页:卫卫卫的个人主页 💞 👉 专栏分类:数据结构 👈 💯代码仓库:卫卫周大胖的学习日记💫 💪关注博主和博主一起学

    2024年02月05日
    浏览(35)
  • 【数据结构】--顺序表的实现

    【数据结构】--顺序表的实现

    什么是顺序表？顺序表（SeqList）是线性表中的一类。而线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、字符串、栈、队列... 注意：线性表在逻辑上是线性结构，也就是说是一条连续的直线。但在

    2024年04月17日
    浏览(34)
  • 数据结构：顺序表的奥秘

    数据结构：顺序表的奥秘

    🎉个人名片： 🐼作者简介： 一名乐于分享在学习道路上收获的大二在校生 🐻‍❄个人主页🎉：GOTXX 🐼个人WeChat：ILXOXVJE 🐼本文由GOTXX原创，首发CSDN🎉🎉🎉 🕊系列专栏：零基础学习C语言----- 数据结构的学习之路 🐓每日一句：如果没有特别幸运，那就请特别努力！🎉

    2024年03月10日
    浏览(42)
  • 【（数据结构）- 顺序表的实现】

    【（数据结构）- 顺序表的实现】

    先来看两张图片 数据结构是由“数据”和“结构”两词组合⽽来。 什么是数据？ 常见的数值1、2、3、4…、教务系统里保存的用户信息（姓名、性别、年龄、学历等等）、网页里肉眼可以看到的信息（文字、图片、视频等等），这些都是数据 什么是结构？ 当我们想要使用大

    2024年02月07日
    浏览(36)
  • 数据结构--顺序表的查找

    数据结构--顺序表的查找

    目标： GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。 代码实现 时间复杂度 O(1) 由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素——“随机存取”特性 目标： LocateElem(Le):按值查找操作。在表L中查找具有给

    2024年02月11日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包