数据结构与算法教程,数据结构C语言版教程!(第二部分、线性表详解:数据结构线性表10分钟入门)十

2024-01-08 10:00:23

?第二部分、线性表详解:数据结构线性表10分钟入门

线性表,数据结构中最简单的一种存储结构,专门用于存储逻辑关系为"一对一"的数据。

线性表,基于数据在实际物理空间中的存储状态,又可细分为顺序表(顺序存储结构)和链表(链式存储结构)。

本章还会讲解顺序表和链表的结合体——静态链表,不仅如此,还会涉及循环链表、双向链表、双向循环链表等链式存储结构。

十九、数据结构实践项目之俄罗斯轮盘赌小游戏

俄罗斯轮盘赌,想必很多人都听说过,一种残忍的赌博游戏。游戏的道具是一把左轮手枪,其规则也很简单:在左轮手枪中的 6 个弹槽中随意放入一颗或者多颗子弹,在任意旋转转轮之后,关上转轮。游戏的参加者轮流把手枪对着自己,扣动扳机:中枪或是怯场,即为输的一方;坚持到最后的即为胜者。

本节实践项目同轮盘赌类似,游戏规则:n 个参加者排成一个环,每次由主持向左轮手枪中装一颗子弹,并随机转动关上转轮,游戏从第一个人开始,轮流拿枪;中枪者退出赌桌,退出者的下一个人作为第一人开始下一轮游戏。直至最后剩余一个人,即为胜者。要求:模拟轮盘赌的游戏规则,找到游戏的最终胜者。

一、设计思路

解决类似的问题,使用线性表的顺序存储结构和链式存储结构都能实现,根据游戏规则,在使用链式存储结构时只需使用循环链表即可轻松解决问题。

二、顺序存储结构模拟轮盘赌

采用顺序存储结构时,同样要在脑海中将数组的首尾进行连接,即当需要从数组中最后一个位置寻找下一个位置时,要能够跳转到数组的第一个位置。(使用取余运算可以解决)

具体实现代码如下:

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

typedef struct gambler{

????????int number;

}gambler;

int main(){

????????int n;

????????int round=1;

????????int location=1;

????????int shootNum;

????????int i,j;

????????srand((int)time(0));//设置获得随机数的种子(固定代码,没有这句,随机数是固定不变的)

????????printf("输入赌徒的人数(<100):");

????????scanf("%d",&n);

????????printf("将赌徒依次编号为 1-%d\n",n);

????????gambler gamblers[100];//存储赌徒编号的数组

????????for (i=1;i<=n; i++) {//依次为参加者分配编号

????????????????gamblers[i].number=i;

????????}

????????//当只剩余一个人时,此场结束

????????while (n!=1) {

????????????????printf("第 %d 轮开始,从编号为 %d 的人开始,",round,gamblers[location].number

);

????????????????shootNum=rand()%6+1;

????????????????printf("枪在第 %d 次扣动扳机时会响\n",shootNum);

???????????????for (i=location; i<location+shootNum; i++);//找到每轮退出的人的位置(i-1 才是,此处求得的i值为下一轮开始的位置)

????????????????i=i%n;//由于参与者排成的是环,所以需要对求得 i 值进行取余处理

????????????????if (i==1 || i==0) {//当 i=1或者i=0时,实际上指的是位于数组开头和结尾的参与者,需要重新调整 i 的值

????????????????????????i=n+i;

???????? ???????? }

???????????????? printf("编号为 %d 的赌徒退出赌博,剩余赌徒编号依次为:\n",gamblers[i-1].number);

???????????????? //使用顺序存储时,如果删除元素,需要将其后序位置的元素进行全部前移

???????? ???????? for (j=i-1; j+1<=n; j++) {

???????????????? ???????? gamblers[j]=gamblers[j+1];

???????? ???????? }

????????????????n--;//此时参与人数由 n 个人变为 n-1 个人

????????????????for (int k=1; k<=n; k++) {

???????????????? ???????? printf("%d ",gamblers[k].number);

???????????????? }

???????????????? printf("\n");

???????????????? location=i-1;//location表示的是下一轮开始的位置

???????? ???????? //同样注意location值的范围

???????????????? if (location>n) {

???????????????? ???????? location%=n;

???????????????? }

???????? ???????? round++;

????????}

???????? printf("最终胜利的赌徒编号是:%d\n",gamblers[1].number);

}

运行结果示例:

输入赌徒的人数:5
将赌徒依次编号为 1-5
第 1 轮开始,从编号为 1 的人开始,枪在第 4 次扣动扳机时会响
编号为 4 的赌徒退出赌博,剩余赌徒编号依次为:
1 2 3 5
第 2 轮开始,从编号为 5 的人开始,枪在第 6 次扣动扳机时会响
编号为 1 的赌徒退出赌博,剩余赌徒编号依次为:
2 3 5
第 3 轮开始,从编号为 2 的人开始,枪在第 2 次扣动扳机时会响
编号为 3 的赌徒退出赌博,剩余赌徒编号依次为:
2 5
第 4 轮开始,从编号为 5 的人开始,枪在第 5 次扣动扳机时会响
编号为 5 的赌徒退出赌博,剩余赌徒编号依次为:
2
最终胜利的赌徒编号是:2

三、链式存储结构模拟轮盘赌

采用链式存储结构对于求此类问题是最容易理解的,同时也避免了当参与人数较多时,像顺序存储那样频繁地移动数据。

具体实现代码如下:

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

typedef enum {false,true} bool;

typedef struct line{

????????int No;

????????struct line * next;

}line;

//按照赌徒人数,初始化循环链表

void initLine(line ** head,int n){

????????*head=(line*)malloc(sizeof(line));

????????(*head)->next=NULL;

????????(*head)->No=1;

????????line * list=*head;

????????for (int i=1; i<n; i++) {

????????????????line * body=(line*)malloc(sizeof(line));

????????????????body->next=NULL;

????????????????body->No=i+1;

????????????????list->next=body;

????????????????list=list->next;

????????}

????????list->next=*head;//将链表成环

}

//输出链表中所有的结点信息

void display(line * head){

????????line * temp=head;

????????while (temp->next!=head) {

????????????????printf("%d ",temp->No);

????????????????temp=temp->next;

????????}

????????printf("%d\n",temp->No);

}

int main() {

????????line * head=NULL;

????????srand((int)time(0));

????????int n,shootNum,round=1;

????????printf("输入赌徒人数:");

????????scanf("%d",&n);

????????initLine(&head,n);

????????line* lineNext=head;//用于记录每轮开始的位置

???????? //仅当链表中只含有一个结点时,即头结点时,退出循环

????????while (head->next!=head) {

????????????????printf("第 %d 轮开始,从编号为 %d 的人开始,",round,lineNext->No);

????????????????shootNum=rand()%n+1;

????????????????printf("枪在第 %d 次扣动扳机时会响\n",shootNum);

????????????????line *temp=lineNext;

????????????????//遍历循环链表,找到将要删除结点的上一个结点

????????????????for (int i=1; i<shootNum-1; i++) {

????????????????????????temp=temp->next;

????????????????}

????????????????//将要删除结点从链表中删除,并释放其占用空间

???????? ???????? printf("编号为 %d 的赌徒退出赌博,剩余赌徒编号依次为:\n",temp->next->No);

????????????????line * del=temp->next;

????????????????temp->next=temp->next->next;

????????????????if (del==head) {

????????????????????????head=head->next;

????????????????}

????????????????free(del);

????????????????display(head);

????????????????//赋值新一轮开始的位置

????????????????lineNext=temp->next;

????????????????round++;//记录循环次数

????????}

printf("最终胜利的赌徒编号是:%d\n",head->No);

return 0;

}

运行结果示例:

输入赌徒人数:5
第 1 轮开始,从编号为 1 的人开始,枪在第 4 次扣动扳机时会响
编号为 4 的赌徒退出赌博,剩余赌徒编号依次为:
1 2 3 5
第 2 轮开始,从编号为 5 的人开始,枪在第 3 次扣动扳机时会响
编号为 2 的赌徒退出赌博,剩余赌徒编号依次为:
1 3 5
第 3 轮开始,从编号为 3 的人开始,枪在第 4 次扣动扳机时会响
编号为 3 的赌徒退出赌博,剩余赌徒编号依次为:
1 5
第 4 轮开始,从编号为 5 的人开始,枪在第 4 次扣动扳机时会响
编号为 1 的赌徒退出赌博,剩余赌徒编号依次为:
5
最终胜利的赌徒编号是:5

四、总结

本节借轮盘赌小游戏,带领大家重新熟悉了线性表的顺序存储结构和链式存储结构,如果你能够根据项目要求自行完成两种结构代码实现的编写工作,恭喜你可以顺利进入下面章节的学习。

文章来源:https://blog.csdn.net/sinat_41942180/article/details/135153888
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。