04ds_03day

===========================
2022-8-3
===========================

note

一.不用写调用,只写声明和实现
    实现有头单向不循环链表的
    遍历和销毁

任务(最基本的要求)
    1.大家可以在纸上写出简单的(有头双向循环链表)增删改查
    2.大家可以在电脑上写出通用性强的链表
    3.大家可以使用内核链表(会用)

自己重新写一遍有头单向循环链表的功能
    1.创建头结点		llist_create();
    2.插入数据结点		llist_insert();
        (头插法	尾插法)
    3.遍历链表			llist_display();
    4.销毁链表			llist_destroy();
    -----------------------------------
    5.查找结点			llist_find();
    6.删除结点			llist_delete();
    7.拿出结点			llist_fetch();

==============================
作业
1.把今天讲过的内容完完整整的复习一遍
2.重新写一遍有头单向循环链表的各种功能
3.写一个无头单向不循环的链表
4.完成joseph杀人游戏
==============================
================================================================================

无头单向不循环的链表

/*
    实现 无头单向不循环的链表
        无头 : 代表没有头结点
        在无头的链表中所有的结点都是数据结点
    1.插入数据结点		llist_insert();
        由于没有头结点所以直接把新的数据结点插入到链表最后
    2.遍历链表			llist_display();
    3.销毁链表			llist_destroy();
    ------------------------------------
    4.查找结点			llist_find();
    5.删除结点			llist_delete();
    6.拿出结点			llist_fetch();
*/

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

int main(void)
{
	LLIST *l = NULL;//l指针指向无头链表的第一个结点
	LLIST *find = NULL;//指向找到的结点
	LLIST save;
	int ret = 0;//保存函数的返回值
	int find_id = 100;
	int num = 0;//客户用来录入结点个数的
	char *find_name = "stu9";

	printf("Please Insert Node Number : ");
	scanf("%d", &num);

	l = llist_insert(num);//创建无头链表
	if(l == NULL)//判断是否创建失败
		return -1;//从创建失败,结束程序,并且返回-1
	
	llist_display(l);//遍历链表

	printf("==================\n");
/*	
	find = llist_find(l, find_name);
	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(&l, find_name);
	if(ret != 0)
		printf("Delete It Is Failed!\n");
	else
		printf("Delete It!\n");
#else
	ret = llist_fetch(&l, &find_id, &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(l);

	llist_destroy(l);//销毁链表

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

#define NAMESIZE 20

typedef struct llist_node
{
	int id;
	char name[NAMESIZE];
	int math;
	struct llist_node *next;
}LLIST;

LLIST *llist_insert(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
110
111
112
113
114
115
116
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "llist.h"

LLIST *llist_insert(int num)//插入数据结点
{
	LLIST *l = NULL;//指向无头链表的第一个结点
	LLIST *p = NULL;//辅助l指针
	LLIST *newnode = NULL;//指向新的结点
	LLIST data;//用来存储数据
	int i = 0;//循环变量

	l = malloc(sizeof(LLIST));//为第一个结点开辟空间
	if(l == NULL)//判断是否开辟失败
		return NULL;

	data.id = 100 + i;
	sprintf(data.name, "stu%d", i);
	data.math = 100 - i;
	data.next = NULL;
	memcpy(l, &data, sizeof(LLIST));
	p = l;
	for(i = 1; i < num; i++)
	{
		newnode = malloc(sizeof(LLIST));
		if(newnode == NULL)//判断是否开辟失败
			return l;
		data.id = 100 + i;
		sprintf(data.name, "stu%d", i);
		data.math = 100 - i;
		data.next = NULL;
		memcpy(newnode, &data, sizeof(LLIST));
		p->next = newnode;
		p = p->next;
	}

	return l;//把第一个结点的地址返回
}

void llist_display(LLIST *l)//遍历链表
{
	LLIST *cur = NULL;

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

void llist_destroy(LLIST *l)//销毁链表
{
	LLIST *back = l;
	LLIST *cur = l->next;

	while(cur != NULL)
	{
		back->next = cur->next;
		free(cur);
		cur = back->next;
	}
	free(back);
}

LLIST *llist_find(LLIST *l, const void *find_data)
{
	LLIST *cur = NULL;
	for(cur = l; cur != NULL; cur = cur->next)
	{
		if(cur->id==*(int*)find_data || 
			!(strcmp(cur->name, find_data)))
			return cur;
	}
	return NULL;
}

int llist_delete(LLIST **l, const void *find_data)
{
	LLIST *back = *l;//指向第一个结点
	LLIST *cur = NULL;//指向要删除的结点

	cur = llist_find(*l, find_data);//查找要删除的结点
	if(cur == NULL)//判断是否没有找到
		return -1;//没有找到,结束函数,并且返回-1
	
	if(cur == *l)//判断要删除的结点是否是第一个结点
		(*l) = (*l)->next;//把指向改变为下一个结点
	else
	{
		while(back->next != cur)
			back = back->next;
		back->next = cur->next;
	}
	free(cur);
	return 0;
}

int llist_fetch(LLIST **l, const void *find_data, void *save)
{
	LLIST *back = *l;//指向第一个结点
	LLIST *cur = NULL;//指向要删除的结点

	cur = llist_find(*l, find_data);//查找要删除的结点
	if(cur == NULL)//判断是否没有找到
		return -1;//没有找到,结束函数,并且返回-1
	
	if(cur == *l)//判断要删除的结点是否是第一个结点
		(*l) = (*l)->next;//把指向改变为下一个结点
	else
	{
		while(back->next != cur)
			back = back->next;
		back->next = cur->next;
	}
	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

================================================================================

需要实现有头单向循环链表

/*
    需要实现有头单向循环链表
    1.创建头结点		llist_create();
    2.插入数据结点		llist_insert();
        头插法	尾插法
    3.遍历链表			llist_display();
    4.销毁链表			llist_destroy();
    ===================================
    5.查找结点			llist_find();
    6.删除结点			llist_delete();
    7.拿出数据			llist_fetch();
*/

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
#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.next = NULL;//指针指向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, "stu9");//删除结点
	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
#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 *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
110
#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->next = handler;//头结点的next指针指向自己

	return handler;//把头结点的地址返回
}

int llist_insert(LLIST *handler,const void *data,int mode)
{
	LLIST *p = handler;//通过指针p代替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 : while(p->next != handler)
							p = p->next;
							break;
		default : free(newnode); return -2;
				  //释放空间,结束函数,并且返回-2
	}
	newnode->next = p->next;
	p->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 *back = handler;//指向头结点的指针
	LLIST *cur = handler->next;//指向数据结点的指针

	while(cur != handler)
	{
		back->next = cur->next;
		free(cur);
		cur = back->next;
	}
	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;//没有找到结点,返回NULL
}

int llist_delete(LLIST *handler, const void *find_data)
{
	LLIST *back = handler;//指向头结点的指针
	LLIST *cur = NULL;//指向要删除的结点的指针

	cur = llist_find(handler, find_data);//查找删除的结点
	if(cur == NULL)//判断是否没有找到
		return -1;//删除失败,函数结束,并且返回-1
	
	while(back->next != cur)//查找要删除结点的前一个位置
		back = back->next;

	back->next = cur->next;//把删除的结点从链表中摘除
	free(cur);//释放要删除的结点
	return 0;
}

int llist_fetch(LLIST *handler, const void *find_data, void *save)
{
	LLIST *back = handler;//指向头结点的指针
	LLIST *cur = NULL;//指向要删除的结点的指针

	cur = llist_find(handler, find_data);//查找删除的结点
	if(cur == NULL)//判断是否没有找到
		return -1;//删除失败,函数结束,并且返回-1
	
	while(back->next != cur)//查找要删除结点的前一个位置
		back = back->next;

	back->next = cur->next;//把删除的结点从链表中摘除
	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