04ds_04day

============================
2022-8-4
============================

note

1.写出有头单向循环链表的插入功能(头插 尾插)
2.实现冒泡法排序
    void sort(int *arr, int size);
有头单向循环链表的功能

无头单向不循环链表

约瑟夫环(约瑟夫杀人游戏)

--------------------------------------------
作业 :
1.把今天讲过的内容完完整整的复习一遍
2.把之前写过的5种链表都重新写一遍
    1)有头单向不循环链表
    2)有头单向循环链表
    3)无头单向不循环链表
    4)无头单向循环链表
    5)有头双向循环链表
--------------------------------------------

约瑟夫环(约瑟夫杀人游戏)

main.c

 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
#include <stdio.h>
#include "joseph.h"

int main(void)
{
	JOSEPH *j = NULL;//j指针指向第一个有效结点
	int player_num = 0;//保存玩家个数
	int kill_num = 0;//数的数字
	int alive = 0;//保存存活下来的人的ID

	printf("Please Insert Player Number : ");
	scanf("%d", &player_num);
	j = joseph_insert(player_num);//插入数据结点
	if(j == NULL)
		return -1;
	printf("===========================\n");
	joseph_display(j);//遍历链表
	printf("===========================\n");
	printf("Please Insert Kill Number : ");
	scanf("%d", &kill_num);
	printf("***************************\n");
	alive = joseph_play(j, player_num, kill_num);
	printf("\n***************************\n");
	printf("alive = %d\n", alive);

	return 0;
}

joseph.h

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#ifndef __JOSEPH_H
#define __JOSEPH_H

typedef struct llist_node
{
	int id;//编号
	struct llist_node *next;
}JOSEPH;

JOSEPH *joseph_insert(int );

JOSEPH *joseph_display(JOSEPH *);

int joseph_play(JOSEPH *, int , int);

#endif

joseph.c

 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
#include <stdio.h>
#include <stdlib.h>
#include "joseph.h"

JOSEPH *joseph_insert(int player_num)
{
	JOSEPH *j = NULL;//j指针指向第一个数据结点
	JOSEPH *p = NULL;//p指针代替j指针进行移动
	JOSEPH *newnode = NULL;//指针指向新创建的结点
	int i = 1;//循环变量
	
	j = malloc(sizeof(JOSEPH));
	if(j == NULL)
		return NULL;
	j->id = i;
	j->next = j;
	p = j;

	for(i = 2; i <= player_num; i++)
	{
		newnode = malloc(sizeof(JOSEPH));
		if(newnode == NULL)
			return j;
		newnode->id = i;
		newnode->next = p->next;
		p->next = newnode;
		p = p->next;
	}

	return j;
}

JOSEPH *joseph_display(JOSEPH *j)
{
	JOSEPH *cur = NULL;

	for(cur = j; cur->next != j; cur = cur->next)
		printf("%d ", cur->id);
	printf("%d\n", cur->id);
}

int joseph_play(JOSEPH *j, int player_num, int kill_num)
{
	JOSEPH *back = j;
	JOSEPH *cur = NULL;
	int p_n = player_num;
	int k_n = kill_num;
	int alive = 0;

	while(back->next != j)//为了找第一个结点的前一个位置
		back = back->next;
	
	while(--p_n)
	{
		for(k_n = kill_num - 1; k_n > 0; k_n--)
			back = back->next;
		cur = back->next;
		back->next = cur->next;
		printf("%d ", cur->id);
		free(cur);
	}
	alive = back->id;
	free(back);

	return alive;
}

makefile

joseph : main.o joseph.o
    gcc -o $@ $^
clean :
    rm -rf *.o joseph

有头双向循环链表

/*
    有头双向循环链表
    1.创建头结点					llist_create();
    2.插入数据结点(头插法 尾插法)	llist_insert();
    3.遍历链表						llist_display();
    4.销毁链表						llist_destroy();
*/

main.c

 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
#include <stdio.h>
#include "llist.h"

int main(void)
{
	LLIST *handler = NULL;//指针指向链表的头结点
	LLIST *find = NULL;//指针指向要查找的结点
	LLIST data;//存储用户的数据
	LLIST save;//保存取出的数据
	int i = 0;//循环变量
	int ret = 0;//接收函数的返回值
	int find_id = 100;//要查找的ID号
	char *find_name = "stu4";//要查找的名字

	handler = llist_create();//创建头结点
	if(handler == NULL)//判断头结点是否创建失败
		return -1;//创建失败,结束程序,并且返回-1
	
	for(i = 0; i < 5; i++)
	{
		data.id = 100 + i;//获取数据
		sprintf(data.name, "stu%d", i);//获取数据
		data.math = 100 - i;//获取数据
		data.prev = data.next = NULL;//prev和next指向NULL
		llist_insert(handler, &data, TAILINSERT);
		//插入数据结点
	}

	llist_display(handler);//遍历链表
	
	printf("====================\n");
/*
	find = llist_find(handler, "stu9");//查找结点
	if(find == NULL)//判断是否没有找到
		printf("Not Find It!\n");
	else
		printf("Find It!	%d	%s	%d\n",find->id, find->name,find->math);
*/
#if 0
	ret = llist_delete(handler, &find_id);
	if(ret != 0)
		printf("Delete It Is Failed!\n");
	else
		printf("Delete It!\n");
#else
	ret = llist_fetch(handler, find_name, &save);
	if(ret != 0)
		printf("Fetch It Is Failed!\n");
	else
		printf("Fetch It!	%d	%s	%d\n",save.id, save.name, save.math);
#endif
	printf("====================\n");

	llist_display(handler);//遍历链表

	llist_destroy(handler);//销毁链表

	return 0;
}

llist.h

 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
#ifndef __LLIST_H
#define __LLIST_H

#define HEADINSERT 0//头插法
#define TAILINSERT 1//尾插法
#define NAMESIZE 20//字符数组的成员个数

typedef struct llist_node//链表中结点的结构体
{
	int id;//数据域
	char name[NAMESIZE];//数据域
	int math;//数据域
	struct llist_node *prev;//prev指针指向前一个结点
	struct llist_node *next;//next指针指向后一个结点
}LLIST;

LLIST *llist_create();//创建头结点

int llist_insert(LLIST *, const void *, int );//插入数据

void llist_display(LLIST *);//遍历链表

void llist_destroy(LLIST *);//销毁链表

LLIST *llist_find(LLIST *, const void *);//查找结点

int llist_delete(LLIST *, const void *);//删除结点

int llist_fetch(LLIST *, const void *, void *);//取出结点

#endif

llist.c

  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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "llist.h"

LLIST *llist_create()
{
	LLIST *handler = NULL;//指向头结点的指针

	handler = malloc(sizeof(LLIST));//为头结点开辟空间
	if(handler == NULL)//判断头结点空间是否开辟失败
		return NULL;//开辟空间失败,结束函数,返回NULL
	
	handler->prev = handler->next = handler;
	//让头结点的前后指针都指向自己

	return handler;//返回指向头结点的指针
}

int llist_insert(LLIST *handler,const void *data,int mode)
{
	LLIST *p = handler;//代替handler指针进行移动
	LLIST *newnode = NULL;//指向新创建的数据结点

	newnode = malloc(sizeof(LLIST));//为数据结点开辟空间
	if(newnode == NULL)//判断数据结点是否开辟失败
		return -1;//开辟空间失败,结束函数,并且返回-1
	
	memcpy(newnode, data, sizeof(LLIST));//拷贝数据

	switch(mode)
	{
		case HEADINSERT : break;
		case TAILINSERT : p = p->prev; break; 
		default : free(newnode); return -2;
	}
	newnode->next = p->next;
	newnode->prev = p;
	newnode->next->prev = newnode;
	newnode->prev->next = newnode;
	return 0;
}

void llist_display(LLIST *handler)
{
	LLIST *cur = NULL;//指向每一个数据结点

	for(cur = handler->next;cur!=handler;cur=cur->next)
		printf("%d	%s	%d\n",cur->id,cur->name,cur->math);
}

void llist_destroy(LLIST *handler)
{
	LLIST *cur = NULL;

	for(cur=handler->next;cur!=handler;cur=handler->next)
	{
		cur->next->prev = cur->prev;
		cur->prev->next = cur->next;
		free(cur);//释放数据结点
	}
	free(cur);//释放头结点
}

LLIST *llist_find(LLIST *handler, const void *find_data)
{
	LLIST *cur = NULL;

	for(cur=handler->next;cur!=handler;cur=cur->next)
	{
		if(cur->id==*(int *)find_data || 
			!(strcmp(cur->name, find_data)))
		{
			return cur;
		}
	}
	return NULL;
}

int llist_delete(LLIST *handler, const void *find_data)
{
	LLIST *cur = NULL;

	cur = llist_find(handler, find_data);
	if(cur == NULL)
		return -1;
	
	cur->prev->next = cur->next;
	cur->next->prev = cur->prev;
	free(cur);

	return 0;
}

int llist_fetch(LLIST *handler, const void *find_data, void *save)
{
	LLIST *cur = NULL;

	cur = llist_find(handler, find_data);
	if(cur == NULL)
		return -1;

	cur->prev->next = cur->next;
	cur->next->prev = cur->prev;
	memcpy(save, cur, sizeof(LLIST));
	free(cur);

	return 0;
}

makefile

1
2
3
4
llist : main.o llist.o
	gcc -o $@ $^
clean :
	rm -rf *.o llist