C语言单双线性及循环链表与实例

C/C++
236
0
0
2023-09-07
C语言学习之柔性数组详解
上一篇
C++11中的可变参数模板/lambda表达式
下一篇
目录
  • 链表思维
  • 顺序存储结构
  • 单链表
  • 单链表存储结构
  •  单链表的读取
  • 单链表的插入
  •  单链表的删除
  •  单链表的整表创建
  •  头插法建立单链表
  • 尾插法建立单链表
  • 单链表的整表删除
  •  单链表实例
  • 单链表学生系统简单实例
  • 双向链表
  • 双链表 
  •  双向链表实现贪吃蛇
  • 思想结构分析：
  • 循环链表
  • 循环链表实现约瑟夫环
  • 实践项目之俄罗斯轮盘赌小游戏
  • 俄罗斯轮盘设计思路

链表思维

顺序存储结构

Operation

InitList(*L):初始化操作，简历一个空的线性表L

ListEmpty(L):判断线性表是否为空表，若线性表为空返回true，否则返回false

ClearList(*L):将线性表清空

GetElem(L,i,*e):将线性表L中的第i个位置返回给e

LocatElem(L,e):在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功，否则，返回0表示失败

ListInsert(*L,i,e):在线性表L中第i个位置插入元素e

ListDelete(*L,i,*e):删除线性表L中的第i个位置的元素，并用e返回其值

ListLength(L):返回线性表L的元素个数

单链表

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以存在内存中未被占用的任意位置。

比起顺序存储结构每个数据元素只需要存储一个位置就可以了。

现在链式存储结构中,除了要存储数据元素信息外,还要存储它的后继元素的存储地址（指针）

我们把存储数据元素信息的域称为数据域,把存储直接后继位置的域称为指针域。指针域中存储的信息称为指针或链。这两部分信息组成数据元素称为存储映像,称为结点(Node)。

n个结点链接成一个链表,即为线性表(a1,a2,a3, …., an)的链式存储结构。

因为此链表的每个结点中只包含一个指针域,所以叫做单链表。

单链表存储结构

 获得链表第i个数据的算法思路:

  • 声明一个结点p指向链表第一个结点,初始化从1开始
  • 当j<i时,就遍历链表，让p的指针向后移动,不断指向一下结点,j+1;
  • 若到链表末尾p为空,则说明第i个元素不存在;
  • 否则查找成功，返回结点p的数据。

 单链表的读取

  • 通俗易懂就是从头开始找,直到第i个元素为止。
  • 由于这个算法的时间复杂度取决于i的位置,当i=1时,则不需要遍历,而i=n时则遍历n-1次才可以。因此最坏情况的时间复杂度为O(n)。
  • 由于单链表的结构中没有定义表长,所以不能实现知道要循环多少次，因此也就不方便使用for控制循环。
  • 其核心思想叫做“工作指针后移”，这其实也是很多算法的常用技术。

单链表的插入

 看图发现我们插入结点不需要向顺序存储一样全部更改，只需要让s -> next和p -> next发生一点指向改变：

  • s -> next = p-> next
  • p -> next = s

如图：

单链表第i个数据插入结点的算法思路:

1.声明一结点p指向链表头结点，初始化j从1开始;-当j<i时，就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1;

2.若到链表末尾p为空，则说明第i个元素不存在;

3.否则查找成功，在系统中生成一个空结点S;

4.将数据元素e赋值给s->data;

5.单链表的插入刚才两个标准语句;

6.返回成功

  • （表示类型）malloc（sizeof（表示长度））开辟一个空间

 单链表的删除

假设元素a2的结点为q，要实现结点q删除单链表的操作，其实就是将它的前继结点的指针绕过指向后面。我们要做的就是上一步

可以写成 p -> next = p ->next -> next

也可以使用

q = p -> next;p -> next = q -> next

单链表第i个数据删除结点的算法思路:

  • 声明结点p指向链表第一个结点，初始化j=1;
  • 当j < i时，就遍历链表，让P的指针向后移动，不断指向下一个结点，j累加1;
  • 一若到链表末尾p为空，则说明第i个元素不存在;
  • 否则查找成功，将欲删除结点p->next赋值给q;
  • 单链表的删除标准语句p -> next = q -> next ;
  • 将q结点中的数据赋值给e,作为返回;
  • 释放q结点。free(q)

 单链表的整表创建

创建单链表的过程是一个动态生成链表的过程，从“空表“的初始状态起，依次建立各元素结点并逐个插入链表。

所以单链表整表创建的算法思路如下:

  • 声明一结点p和计数器变量i;
  • 初始化一空链表L;
  • 让L的头结点的指针指向NULL,即建立一个带头结点的单链表;
  • 循环实现后继结点的赋值和插入。

 头插法建立单链表

头插法从一个空表开始，生成新结点，读取数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到结束为止。

简单来说，就是把新加进的元素放在表头后的第个位置:

  • 先让新节点的next指向头节点之后
  • 然后让表头的next指向新节点

 嗯，用现实环境模拟的话就是插队的方法，始终让新结点插在第一的位置。

尾插法建立单链表

单链表的整表删除

  • 声明结点p和q;
  • 将第一个结点赋值给p,下一结点赋值给q;
  • 循环执行释放p和将q赋值给p的操作;
#define OK
#define ERROR
#define TRUE
#define FALSE
typedef int Status;
Status ClearList(LinkList *L){
	LinKList p,q;
	p = (*L) -> next;
	while(p){
		q = p -> next;
		free(p);
		p = q;
	}
	(*L) -> next = NULL;
	return OK
}
//这段算法代码里，常见的错误就是有同学会觉得q变量没有存在的必要，只需要在循环体内直接写自由(P)；p=p->下一步；即可？
//可这个世上没有无缘无故的爱，这样做会带来什么问题呢？
//要知道p是一个结点，它除了有数据域，还有指针域.当我们做自由(P)；时候，其实是对它整个结点进行删除和内存释放的工作.而我们整表删除是需要一个个结点删除的，所以我们就需要q来记载p的下一个结点.

 单链表实例

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

struct singleList{
	int data;
	struct singleList *next;
};
//创建一个表
struct singleList*createList(){
	//指针变成结构体变量  
	struct singleList *headNode = (struct singleList *)malloc(sizeof(struct singleList));
	headNode -> next = NULL; //差异化处理，充当表头 
	return headNode; 
}
//创建结点：  战门创建新的结点
//int data
struct singleList* creatNode(int data) {
	struct singleList* newNode = (struct singleList *)malloc(sizeof(struct singleList));
	newNode -> data = data;
	newNode -> next = NULL;
	return newNode;
}
void insertNodeByHead(struct singleList *headNoed,int data){
	 struct singleList *newNode = creatNode(data);
	 newNode -> next = headNoed -> next;
	 headNoed -> next = newNode;
}

void printList(struct singleList* headNode){
	
	//因为第一个结点就是表头，所以 里面没有数据，要从第二个打印
	struct singleList *pMove = headNode -> next;
	while (pMove) {
		printf("%d -> ",pMove -> data);
		pMove = pMove -> next;
	}
	printf("\n");
}
int main(){
	struct singleList*list =createList();
	insertNodeByHead(list,);
	insertNodeByHead(list,);
	insertNodeByHead(list,);
	printList(list);
	system("pause");
	return;
}

单链表学生系统简单实例

此处使用c++语法，请自行切换

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
struct student {
	char name[];
	int age;
	int num;
};



struct singleList {
	//	int data;
	struct student data;
	struct singleList* next;
};
//创建一个表
struct singleList* createList() {
	//指针变成结构体变量  
	struct singleList* headNode = (struct singleList*)malloc(sizeof(struct singleList));
	headNode->next = NULL; //差异化处理，充当表头 
	return headNode;
}
//创建结点：  战门创建新的结点
//int data
struct singleList* creatNode(struct student data) {
	struct singleList* newNode = (struct singleList*)malloc(sizeof(struct singleList));
	newNode->data = data;
	newNode->next = NULL;
	return newNode;
}
void insertNodeByHead(struct singleList* headNoed, struct student data) {
	struct singleList* newNode = creatNode(data);
	newNode->next = headNoed->next;
	headNoed->next = newNode;
}

void printList(struct singleList* headNode) {

	//因为第一个结点就是表头，所以 里面没有数据，要从第二个打印
	struct singleList* pMove = headNode->next;
	printf("请录入信息：姓名\t年龄\t编号\n");
	while (pMove) {
		printf("%s\t%d\t%d\n ", pMove->data.name, pMove->data.age, pMove->data.num);
		//		struct student data
		//		printf("%d -> ",pMove -> data);
		pMove = pMove->next;
	}
	printf("\n");
}

//增删查改
//void saveInfoToFile() 
//菜单
void printMenu() {
	printf("---------------------\n");
	printf("\t\to.退出信息\n");
	printf("\t\t.录入信息\n");
	printf("\t\t.显示信息\n");
	printf("---------------------\n");
}
//按键处理 
struct singleList* list = createList();
void keyDown() {
	int choice =;
	scanf("%d", &choice);
	struct student tempDate;
	switch(choice)
	{
	case:
		printf("正常退出\n");
		system("pause");
		break;
	case:
		printf("请输入学生姓名年龄编号");
		scanf("%s %d %d", tempDate.name, &tempDate.age, &tempDate.num);
		insertNodeByHead(list, tempDate);
		break;
	case:
		printList(list);
		break;
	};
}


int main() {
	//	struct singleList*list =createList();
	//	insertNodeByHead(list,);
	//	insertNodeByHead(list,);
	//	insertNodeByHead(list,);
	//	printList(list);

	while () {
		printMenu();
		keyDown();
		system("pause");
		system("cls");

	}
	system("pause");
	return;
};


//.先写链表，先写数据结构
//.修改data
//.系统应用开发

双向链表

双链表 

  • main.h
#pragma once
#include <stdio.h>
#include <stdlib.h>

//双向链表结构体
typedef struct doubleLink {
    char data;//记录节点所在的行和列
    struct doubleLink* pre;//指向前驱节点的指针
    struct doubleLink* next;//指向后续节点的指针
};

//初始化双链表
struct doubleLink* initDoubleLink();
//查询
struct doubleLink* selectDoubleLink(struct doubleLink* p, int site);
//插入
struct doubleLink* insertDoubleLink(struct doubleLink* p, int site, int value);
//删除
struct doubleLink* deleteDoubleLink(struct doubleLink* p, int site);
//修改
struct doubleLink* updateDoubleLink(struct doubleLink* p, int site, int value);
//打印
void display(doubleLink* head);
  • main.cpp
#include "main.h"

int main() {
	printf("双链表\n");

	struct doubleLink* doubleLink = NULL;
	display(doubleLink);

	doubleLink = initDoubleLink();
	display(doubleLink);
	
	insertDoubleLink(doubleLink,, 100);
	display(doubleLink);

	deleteDoubleLink(doubleLink,);
	display(doubleLink);

	updateDoubleLink(doubleLink,, 100);

	display(doubleLink);

	return;
}
  • doubleLink.cpp
#include "main.h"

struct doubleLink* initDoubleLink() {
	doubleLink* headNode = NULL;
	doubleLink* temp = NULL;

	headNode = (doubleLink*)malloc(sizeof(doubleLink));

	headNode->data =;
	headNode->next = NULL;
	headNode->pre = NULL;

	temp = headNode;

	for (int i =; i <= 4; i++)
	{
		doubleLink* a = (doubleLink*)malloc(sizeof(doubleLink));
		a->data = i;
		a->next = NULL;
		a->pre = temp;

		temp->next = a;
		temp = temp->next;
	}
	return headNode;
}

struct doubleLink* insertDoubleLink(struct doubleLink* p, int site, int value) {
	doubleLink* body = NULL;
	body = p;
	doubleLink* temp = NULL;

	temp = (doubleLink*)malloc(sizeof(doubleLink));
	temp->data = value;
	temp->pre = NULL;
	temp->next = NULL;

	body = selectDoubleLink(p, site);

	temp->next = body->next;
	temp->pre = body;
	body->next = temp;

	return p;
}

struct doubleLink* deleteDoubleLink(struct doubleLink* p, int site) {
	doubleLink* body = NULL;
	body = p;

	body = selectDoubleLink(p, site);

	body->next = body->next->next;
	body->next->pre = body;

	return p;
}	

struct doubleLink* updateDoubleLink(struct doubleLink* p, int site,int value) {
	doubleLink* body = NULL;
	body = p;

	body = selectDoubleLink(p, site);

	body->next->data = value;

	return p;
}

struct doubleLink* selectDoubleLink(struct doubleLink* p, int site) {
	doubleLink* temp = p;
	int i;
	for (i =; i < site; i++)
	{
		if (temp == NULL) {
			printf("查询失败");
			return p;
		}
		temp = temp->next;
	}
	return temp;
}



void display(doubleLink* head) {
	doubleLink* temp = head;
	while (temp) {
		if (temp->next == NULL) {
			printf("%d\n", temp->data);
		}
		else {
			printf("%d->", temp->data);
		}
		temp = temp->next;
	}
}

 双向链表实现贪吃蛇

贪吃蛇实例展示：

思想结构分析：

1.我们知道，双向链表中各个节点的标准构成是一个数据域和 2 个指针域，但对于实现贪吃蛇游戏来说，由于各个节点的位置是随贪吃蛇的移动而变化的，因此链表中的各节点还需要随时进行定位。

在一个二维画面中，定义一个节点的位置，至少需要所在的行号和列号这 2 个数据。由此，我们可以得出构成贪吃蛇的双向链表中各节点的构成：

//创建表示蛇各个节点的结构体
typedef struct SnakeNode {
    int x, y;//记录节点所在的行和列
    struct SnakeNode *pre;//指向前驱节点的指针
    struct SnakeNode *next;//指向后续节点的指针
}Node, *pNode;

2.贪吃蛇的移动，本质上就是对链表中各个节点的重新定位。换句话说，除非贪吃蛇吃到食物，否则无论怎样移动，都不会对双向链表的整个结构（节点数）产生影响，唯一受影响的就只是各个节点中 (x，y) 这对定位数据。

由此，我们可以试着设计出实现贪吃蛇移动的功能函数，本节所用的实现思想分为 2 步：

  • 从蛇尾（双向链表尾节点）开始，移动向前遍历，过程中依次将当前节点的 (x，y) 修改为前驱节点的 (x，y)，由此可实现整个蛇身（除首元节点外的其它所有节点）的向前移动；
  • 接收用户输入的移动指令，根据用户指示贪吃蛇向左、向右、向上还是向下移动，首元节点中的 (x，y) 分别做 x-1、x+1、y-1 和 y+1 运算。

 如下所示，move() 函数就实现了贪吃蛇的移动：

//贪吃蛇移动的过程，即链表中所有节点从尾结点开始逐个向前移动一个位置
bool Move(pNode pHead, char key) {
    bool game_over = false;
    pNode pt = pTail;
    while (pt != pHead) { // 每个节点依次向前完成蛇的移动
        pt->x = pt->pre->x;
        pt->y = pt->pre->y;
        pt = pt->pre;
    }
    switch (key) {
        case'd': {
            pHead->x +=;
            if (pHead->x >= ROW)
                game_over = true;
            break;
        }
        case'a': {
            pHead->x -=;
            if (pHead->x <)
                game_over = true;
            break;
        }
        case's': {
            pHead->y +=;
            if (pHead->y >= COL)
                game_over = true;
            break;
        }
        case'w': {
            pHead->y -=;
            if (pHead->y <)
                game_over = true;;
            break;
        }
    }
    if (SnakeDeath(pHead))
        game_over = true;
    return game_over;
}
注意，此段代码中还调用了 SnakeDeath() 函数，此函数用于判断贪吃蛇移动时是否撞墙、撞自身，如果是则游戏结束。

3. 当贪吃蛇吃到食物时，贪吃蛇需要增加一截，其本质也就是双向链表增加一个节点。前面章节中，已经详细介绍了如何在双向链表中增加一个节点，因此实现这个功能唯一的难点在于：如何为该节点初始化 (x，y)？

本节所设计的贪吃蛇游戏，针对此问题，提供了最简单的解决方案，就是不对新节点 x 和 y 做初始化。要知道，贪吃蛇是时刻移动的，而在上面的 move() 函数中，会时刻修正贪吃蛇每个节点的位置，因此当为双向链表添加新节点后，只要贪吃蛇移动一步，新节点的位置就会自行更正。

也就是说，贪吃蛇吃到食物的实现，就仅是给双向链表添加一个新节点。如下即为实现此功能的代码：

//创建表示食物的结构体，其中只需要记录其所在的行和列
typedef struct Food {
    int x;
    int y;
}Food, *pFood;
//吃食物，等同于链表中新增一个节点
pNode EatFood(pNode pHead, pFood pFood) {
    pNode p_add = NULL, pt = NULL;
    if (pFood->x == pHead->x&&pFood->y == pHead->y) {
        p_add = (pNode)malloc(sizeof(Node));
        score++;
        pTail->next = p_add;
        p_add->pre = pTail;
        p_add->next = NULL;
        pTail = p_add;
        // 检查食物是否出现在蛇身的位置上
        do {
            *pFood = CreateFood();
        } while (FoodInSnake(pHead, pFood));
    }
    return pHead;
}

其中，Food 结构体用来表示食物，其内部仅包含能够定位食物位置的 (x，y) 即可。另外，此段代码中，还调用了 FoodeInSnake() 函数，由于食物的位置是随机的，因此极有可能会和贪吃蛇重合，所以此函数的功能就是：如果重合，就重新生成食物。

FoodInSnake() 函数的实现很简单，这里不再赘述：

//判断食物的出现位置是否和蛇身重合
bool FoodInSnake(pNode pHead, pFood pFood) {
    pNode pt = NULL;
    for (pt = pHead; pt != NULL; pt = pt->next) {
        if (pFood->x == pt->x&&pFood->y == pt->y)
            return true;
    }
    return false;
}

4.贪吃蛇游戏界面的显示，最简单的制作方法就是：贪吃蛇每移动一次，都清除屏幕并重新生成一次。这样实现的问题在于，如果贪吃蛇的移动速度过快，则整个界面在渲染的同时，会掺杂着光标，并且屏幕界面会频繁闪动。

因此，在渲染界面时，有必要将光标隐藏起来，这需要用到<windows.h>头文件，实现代码如下：

// 隐藏光标
void gotoxy(int x, int y) {
    HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE);
    COORD pos;
    pos.X = x;
    pos.Y = y;
    SetConsoleCursorPosition(handle, pos);
}
void HideCursor() {
    CONSOLE_CURSOR_INFO cursor_info = {, 0 };
    SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE), &cursor_info);
}

同时，为了给整个界面渲染上颜色，也需要引入<windows.h>头文件，并使用如下函数:

void color(int m) {
    HANDLE consolehend;
    consolehend = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleTextAttribute(consolehend, m);
}

5.需要注意的一点是，由此结束后，一定要手动释放双向链表占用的堆空间：

//退出游戏前，手动销毁链表中各个节点
void ExitGame(pNode *pHead)
{
    pNode p_delete = NULL, p_head = NULL;
    while (*pHead != NULL) {
        p_head = (*pHead)->next;
        if (p_head != NULL)
            p_head->pre = NULL;
        p_delete = *pHead;
        free(p_delete);
        p_delete = NULL;
        *pHead = p_head;
    }
}

循环链表

无论是静态链表还是动态链表，有时在解决具体问题时，需要我们对其结构进行稍微地调整。比如，可以把链表的两头连接，使其成为了一个环状链表，通常称为循环链表。

只需要将表中最后一个结点的指针指向头结点，链表就能成环儿

需要注意的是，虽然循环链表成环状，但本质上还是链表，因此在循环链表中，依然能够找到头指针和首元节点等。循环链表和普通链表相比，唯一的不同就是循环链表首尾相连，其他都完全一样。

循环链表实现约瑟夫环

约瑟夫环问题，是一个经典的循环链表问题，题意是：已知 n 个人（分别用编号 1，2，3，…，n 表示）围坐在一张圆桌周围，从编号为 k 的人开始顺时针报数，数到 m 的那个人出列；他的下一个人又从 1 开始，还是顺时针开始报数，数到 m 的那个人又出列；依次重复下去，直到圆桌上剩余一个人。

如图 2 所示，假设此时圆周周围有 5 个人，要求从编号为 3 的人开始顺时针数数，数到 2 的那个人出列：

实践项目之俄罗斯轮盘赌小游戏

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

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

俄罗斯轮盘设计思路

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

顺序存储结构模拟轮盘
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//链表节点单元 
typedef struct GameMan{
    int Man;
    struct GameMan * next;
}GameMan;

//建立游戏人员循环链表
void InitGameManLine(GameMan **GameMans,int PersonNum){
    *GameMans=(GameMan *)malloc(sizeof(GameMan));//头指针指向首元节点 
    //节点初始化 
	(*GameMans)->next=NULL;
    (*GameMans)->Man=;
    GameMan *tail=*GameMans;//指向链表尾 
    for (int i=;i<=PersonNum;i++){
        GameMan *newnode=(GameMan *)malloc(sizeof(GameMan));//申请新节点 
        //节点初始化 
		newnode->next=NULL;
        newnode->Man=i;
        tail->next=newnode;//将新节点链接到链表尾 
        tail=tail->next;//移动tail到尾指针 
    }
    tail->next=*GameMans;//将链表成环
}

//输出链表中所有游戏成员 
void display(GameMan *GameMans){
    GameMan *temp=GameMans;
    while (temp->next!=GameMans){
        printf("%d ",temp->Man);
        temp=temp->next;
    }
    printf("%d\n\n",temp->Man);
}

int main() {
    GameMan *GameMans=NULL;//游戏成员链表头指针
	int round=; 
    int PersonNum;
	int BulletPos;
//	srand((int)time());//使用当前时间作为rand()函数的随机数的种子 
	srand((unsigned) time(NULL));
	printf("请输入本次游戏人数(<): ");
    scanf("%d",&PersonNum);
    printf("\n为编号为-%d 的游戏人员分配位置!\n\n",PersonNum);
    InitGameManLine(&GameMans,PersonNum);
    GameMan* lineNext=GameMans;//用于记录每轮开始的位置
    //仅当链表中只含有一个结点时，即头结点时，退出循环
    while(GameMans->next!=GameMans){
        BulletPos=rand()%+1;
        printf("第 %d 轮游戏,从编号为 %d 的人开始,枪在第 %d 次扣动扳机时会响!\n\n",round,lineNext->Man,BulletPos);
        GameMan *temp=lineNext;
        //遍历循环链表，找到将要删除结点的上一个结点
        for (int i=;i<BulletPos-1;i++){
            temp=temp->next;
        }
        //如果子弹位置BulletPos==，则要找到当前节点的上一节点 
        if(BulletPos==){
        	while(temp->next!=lineNext){
	        	temp=temp->next;
	        }
        } 
        printf("编号为 %d 的赌徒退出赌博,剩余赌徒编号依次为:",temp->next->Man);
        //将要删除结点从链表中删除，并释放其占用空间
		GameMan * del=temp->next;//记录删除节点 
        temp->next=temp->next->next;//从链表中移除该节点 
        if(del==GameMans)GameMans=GameMans->next;//如果删除的是头节点，将头节点的下一节点作为头节点 
        free(del);//释放del节点 
        display(GameMans);
        //下一轮开始的位置
        lineNext=temp->next;
        round++;//回合次数加一
    }
    printf("最终胜利的游戏人员编号是：%d \n\n",GameMans->Man);
    return;
}

运行结果示例：

 链表实现俄罗斯轮盘
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//链表节点单元 
typedef struct GameMan{
    int Man;
    struct GameMan * next;
}GameMan;

//建立游戏人员循环链表
void InitGameManLine(GameMan **GameMans,int PersonNum){
    *GameMans=(GameMan *)malloc(sizeof(GameMan));//头指针指向首元节点 
    //节点初始化 
	(*GameMans)->next=NULL;
    (*GameMans)->Man=;
    GameMan *tail=*GameMans;//指向链表尾 
    for (int i=;i<=PersonNum;i++){
        GameMan *newnode=(GameMan *)malloc(sizeof(GameMan));//申请新节点 
        //节点初始化 
		newnode->next=NULL;
        newnode->Man=i;
        tail->next=newnode;//将新节点链接到链表尾 
        tail=tail->next;//移动tail到尾指针 
    }
    tail->next=*GameMans;//将链表成环
}

//输出链表中所有游戏成员 
void display(GameMan *GameMans){
    GameMan *temp=GameMans;
    while (temp->next!=GameMans){
        printf("%d ",temp->Man);
        temp=temp->next;
    }
    printf("%d\n\n",temp->Man);
}

int main() {
    GameMan *GameMans=NULL;//游戏成员链表头指针
	int round=; 
    int PersonNum;
	int BulletPos;
//	srand((int)time());//使用当前时间作为rand()函数的随机数的种子 
	srand((unsigned) time(NULL));
	printf("请输入本次游戏人数(<): ");
    scanf("%d",&PersonNum);
    printf("\n为编号为-%d 的游戏人员分配位置!\n\n",PersonNum);
    InitGameManLine(&GameMans,PersonNum);
    GameMan* lineNext=GameMans;//用于记录每轮开始的位置
    //仅当链表中只含有一个结点时，即头结点时，退出循环
    while(GameMans->next!=GameMans){
        BulletPos=rand()%+1;
        printf("第 %d 轮游戏,从编号为 %d 的人开始,枪在第 %d 次扣动扳机时会响!\n\n",round,lineNext->Man,BulletPos);
        GameMan *temp=lineNext;
        //遍历循环链表，找到将要删除结点的上一个结点
        for (int i=;i<BulletPos-1;i++){
            temp=temp->next;
        }
        //如果子弹位置BulletPos==，则要找到当前节点的上一节点 
        if(BulletPos==){
        	while(temp->next!=lineNext){
	        	temp=temp->next;
	        }
        } 
        printf("编号为 %d 的赌徒退出赌博,剩余赌徒编号依次为:",temp->next->Man);
        //将要删除结点从链表中删除，并释放其占用空间
		GameMan * del=temp->next;//记录删除节点 
        temp->next=temp->next->next;//从链表中移除该节点 
        if(del==GameMans)GameMans=GameMans->next;//如果删除的是头节点，将头节点的下一节点作为头节点 
        free(del);//释放del节点 
        display(GameMans);
        //下一轮开始的位置
        lineNext=temp->next;
        round++;//回合次数加一
    }
    printf("最终胜利的游戏人员编号是：%d \n\n",GameMans->Man);
    return;
}

C语言学习之柔性数组详解
上一篇
C++11中的可变参数模板/lambda表达式
下一篇