热门标签
热门文章
- 1Java ArrayList 常用操作总结_arraylist类基本操作
- 2基于SpringBoot+Vue的养老院管理系统设计和实现(源码+lw+部署+讲解)
- 3Python实战案例分享：爬取当当网商品数据
- 4微服务Spring Cloud架构详解_springcloud微服务架构
- 5【linux高级IO(一)】理解五种IO模型
- 6关于oracle 11g 循环多判断+continue 用法例子_oracle 多个判定多次执行
- 7【数据结构】双链表_数据结构 双链表
- 8Linux中系统安全及应用_securelevel
- 9GIT和MAVEN基础向_maven git
- 10苹果iOS免签封装APP的原理，如何操作？_苹果网站一键免签打包
当前位置: article > 正文
C语言---数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题_c语言内容要求:建立有序表:12,23,46,67,85建立有序表:5,59,94 两个有序顺序表
作者：寸_铁 | 2024-07-13 03:18:16
赞
踩
c语言内容要求:建立有序表:12,23,46,67,85建立有序表:5,59,94 两个有序顺序表
写在前面
实验的写法多种多样，但本文并未采用#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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
代码下载
链表的基本操作
定义线性表的链式存储结构，定义结点类型，并使用定义的结构实现链表的创建，插入，删除、查询、输出等基本操作。
通讯录管理（必做内容） ； 约瑟夫环（选做内容）
必做内容要求：
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个菜单项的内容和输入提示：
- 通讯录链表的建立
- 通讯者结点的插入
- 通讯者结点的查询
- 通讯者结点的删除
- 通讯录链表的输出
- 退出管理系统
请选择 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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
代码下载
约瑟夫问题
问题分析
约瑟夫（Joseph）问题的一种描述是：30个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分。因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免于难。无奈，大家只好同意这种办法，并议定30个人围成一圈，由第一个人数起，依次报数，数到第9人，便把他投入大海，然后再从他的下一个人数起，数到第9人，再将他扔进大海中，如此循环地进行，直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置？
- 利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各人的编号。
- 为了不失一般性，将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
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 测试结果
对于总人数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. 要解决循环链表问题
通过画图就能知道，每次要让尾节点指向头，每次插入后都需要找到尾节点，改变尾节点的指向
2. 要解决如何找到要删元素的问题
首先说明思路：思路就是把定义一个cur指针，这个指针用来指向要删除的节点，这个思路本身是没有问题的，但是问题在于在实现代码过程中出现了问题
第一个问题在于cur在找要删除元素的过程中是需要经过cur=cur->next，问题就在于循环几次
这个题的要求是删15个元素，每次报到9就删除，因此实际上cur只需要循环8次就能推进到9的位置
第二个问题是删除元素后导致前后不一致的问题，删除元素后如果未对cur节点进行处理，那么cur元素当前位置和最初始的位置实际上是不一样的，假设链表元素是1，2，3…依次排序，那么cur又开始指向1，经过遍历，现在要删除的是元素9，删除掉元素9后，实际上应该对cur再推进一次，这样cur才能指向初始位置的"1"
解决这两个问题后续过程就很简单了，这里代码并没有提前进行宏定义，后续需要进行改变直接进行修改数据即可
代码实现
#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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
推荐阅读
相关标签
