文章目录

  • 写在前面
  • 顺序表的合并
    • 代码实现
    • 代码下载
  • 链表的基本操作
    • 代码实现
    • 代码下载
  • 约瑟夫问题
    • 问题分析
    • 代码实现

写在前面

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

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

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

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

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

手撕顺序表
手撕单链表

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

顺序表的合并

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

代码实现

//建立有序表:12,23,46,67,85//建立有序表:5,59,94//两个有序顺序表合并为一个有序顺序表,验证代码的正确性。#include #include #include 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);for (int i = 0; i < ps1->size; i++){SListPushBack(&ps, ps1->a[i]);}for (int i = 0; i < ps2->size; i++){SListPushBack(&ps, ps2->a[i]);}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 #include #include #include #include typedefstruct{charnum[5];//编号charname[9]; //姓名charsex[3]; //性别charphone[13];//电话charaddr[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);returnnewdata;}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 置为1while (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. 要解决循环链表问题

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


2. 要解决如何找到要删元素的问题

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

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

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

解决这两个问题后续过程就很简单了,这里代码并没有提前进行宏定义,后续需要进行改变直接进行修改数据即可

代码实现

#include #include #include 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;}