02 C

  • 开发
  • 11

1、链表

1.1 什么是链表

        链表就是一种数据结构，是一种数据存放的思想。就和数组这个数据结构差不多，但是数组在对数据进行增加、删减的操作时十分麻烦，不灵活。而链表就很好的解决了这个问题，链表的每一项都是一个结构体。

1.2 链表和数组对比

        链表有一个指向自己的指针，

#include <stdio.h>


//数组形式
int main()
{
	int i;
	
	int array[] = {1, 2, 3};
	for(i = 0; i < sizeof(array)/sizeof(array[0]); i++){
		printf("%d", array[i]);
	}
	putchar('\n');
	
	return o;
}
#include <stdio.h>


//链表形式
struct Test
{
	int data;
	struct Test *next;
};

int main()
{
	struct Test t1 = {1, NULL};
	struct Test t2 = {2, NULL};
	struct Test t3 = {3, NULL};	//此时t1、t2、t3之间没有任何关系，是相互独立的
	
	t1.next = &t2;
	t2.next = &t3;	//此时t1、t2、t3之间就串联起来了
	
	printf("use t1 to print three nums");
	print("%d %d %d", t1.data, (t1.next)->data, t1.next->data->data);	//. 的优先级是要高于 -> 的
	
	return 0;
}

1.3 链表的静态添加和动态遍历

#include <stdio.h>


struct Test
{
	int data;
	struct Test *next;
};

void printLink(struct Test *head)
{
	struct Test *point;
	point = head;
	
	while(1){
		if(point != NULL){
			printf("%d ", point->data);
			point = point->next;	
		}
		else{
			putchar('\n');
			break;
		}
	}
}


//使用链表增加一个数据4
int main()
{
	struct Test t1 = {1, NULL};
	struct Test t2 = {2, NULL};
	struct Test t3 = {3, NULL};	
	struct Test t4 = {4, NULL};	
	
	t1.next = &t2;
	t2.next = &t3;	
	t3.next = &t4;
	
	printf("use t1 to print three nums");
//	print("%d %d %d %d", t1.data, (t1.next)->data, t1.next->next->data, t1.next->next->next->data);	//. 的优先级是要高于 -> 的

    //对上面打印链表的语句进行优化
    printLink(&t1);
	
	return 0;
}

        在对应节点后添加，要先检查首尾信息，然后再插入新的信息。、

#include <stdio.h>



struct Test
{
	int data;
	struct Test *next;
};

//在一个节点后插入一个新的数据
int insertFromBehind(struct Test *head, int data, struct Test *new)
{
	struct Test *p = head;
	while(p != NULL){
		if(p->data == data){
			new->next = p->next;
			p->next = new;
			return 1;
		}
		p = p->next;
	}
	return 0;
}

void printLink(struct Test *head)
{
	struct Test *point;
	point = head;
	
	while(1){
		if(point != NULL){
			printf("%d ", point->data);
			point = point->next;	
		}
		else{
			putchar('\n');
			break;
		}
	}
}


//使用链表增加一个数据
int main()
{
	struct Test t1 = {1, NULL};
	struct Test t2 = {2, NULL};
	struct Test t3 = {3, NULL};	
	struct Test t4 = {4, NULL};	
	
	struct Test new = {100, NULL};
	
	t1.next = &t2;
	t2.next = &t3;	
	t3.next = &t4;
	
	printf("use t1 to print three nums");
//	print("%d %d %d %d", t1.data, (t1.next)->data, t1.next->next->data, t1.next->next->next->data);	//. 的优先级是要高于 -> 的
	printLink(&t1);	//1 2 3 4
	puts("after insert behind:\n");
	insertFromBehind(&t1, 2, &new);
	printLink(&t1);	//1 2 100 3 4
	
	
	return 0;
}

        在对应节点前添加，要先检查首尾信息，然后再插入新的信息。此时分两种情况，一种是在目标链表的第一个节点前添加，那么此时链表的头就会发生变化，对于一个链表来说，头结点是十分重要的。第二中就是在目标链表的非首个节点前添加。

#include <stdio.h>



struct Test
{
	int data;
	struct Test *next;
};

//在对应节点前添加新节点
struct Test* insertFromFront(struct Test *head, int data, struct Test *new)
{
	struct Test *p = head;
	//头结点前
	if(p->data == data){
		new->next = p;
		return new;
	}
	//非头结点前
	while(p->next != NULL){
		if(p->next->data == data){
			new->next = p->next;
			p->next = new;
			printf("ok\n");
			return head;
		}
		p = p->next;
	}
	printf("no this data");
	return head;
}

void printLink(struct Test *head)
{
	struct Test *point;
	point = head;
	
	while(1){
		if(point != NULL){
			printf("%d ", point->data);
			point = point->next;	
		}
		else{
			putchar('\n');
			break;
		}
	}
}


//使用链表增加一个数据
int main()
{
	struct Test t1 = {1, NULL};
	struct Test t2 = {2, NULL};
	struct Test t3 = {3, NULL};	
	struct Test t4 = {4, NULL};	
	
	struct Test *head = NULL;
	
	struct Test new = {100, NULL};
	struct Test new1 = {101, NULL};
	
	head = &t1;
	
	t1.next = &t2;
	t2.next = &t3;	
	t3.next = &t4;
	
	printf("use t1 to print three nums");
//	print("%d %d %d %d", t1.data, (t1.next)->data, t1.next->next->data, t1.next->next->next->data);	//. 的优先级是要高于 -> 的
	printLink(&t1);	//1 2 3 4

	puts("after insert in front of:\n");
	head = insertFromFront(head, 1, &new);
	head = insertFromFront(head, 3, &new1);
	printLink(&head);	//100 1 2 101 3 4
	

	
	return 0;
}

1.4 链表的查找

#include <stdio.h>


struct Test
{
	int data;
	struct Test *next;
};

int main()
{
	struct Test t1 = {1, NULL};
	struct Test t2 = {2, NULL};
	struct Test t3 = {3, NULL};	//此时t1、t2、t3之间没有任何关系，是相互独立的
	
	t1.next = &t2;
	t2.next = &t3;	//此时t1、t2、t3之间就串联起来了
	
	printf("use t1 to print three nums");
	print("%d %d %d", t1.data, (t1.next)->data, t1.next->data->data);	//. 的优先级是要高于 -> 的
	
	return 0;
}

int getLinkTotalNodeNum(struct Test *head)
{
	int cnt = 0;
	while(head != NULL){
		cnt++;
		head = head->next;
	}
	return cnt;
}

int searchLink(struct Test *head, int data)
{
	while(head != NULL){
		if(head->data == data){
			return 1;
		}
		head = head->next;
	}
	return 0;
}


int main()
{
	struct Test t1 = {1, NULL};
	struct Test t2 = {2, NULL};
	struct Test t3 = {3, NULL};	
	struct Test t4 = {4, NULL};	
	
	t1.next = &t2;
	t2.next = &t3;	
	t3.next = &t4;
	
	printf("use t1 to print three nums");
	print("%d %d %d %d", t1.data, (t1.next)->data, t1.next->next->data, t1.next->next->next->data);	//. 的优先级是要高于 -> 的
	int ret = getLinkTotalNodeNum(&t1);
	printf("total num = %d\n", ret);
	int res = searchLink(&t1, 1);
	if(res == 0){
		printf("no 1\n");
	}
	else{
		printf("have 1\n");
	}
	
	return 0;
}

1.5 链表的删除

        链表的删除要考虑两种情况，删除的节点是否是头结点，如果删除的是头结点，那么链表的头将会改变，如果是非头结点，那么删除该节点并不会影响到链表的头。

#include <stdio.h>


struct Test
{
	int data;
	struct Test *next;
};

struct Test* deletNode(struct Test *head, int data)
{
	struct Test *p = head;
	if(p->data == data){
		head = p->next;
		return head;
	}
	while(p->next != NULL){
		if(p->next->data == data){
			p-next = p->next->next;
			return head;
		}
		p = p->next;
	}
	print("no this data\n");
	return head;
}

void printLink(struct Test *head)
{
	struct Test *point;
	point = head;
	
	while(1){
		if(point != NULL){
			printf("%d ", point->data);
			point = point->next;	
		}
		else{
			putchar('\n');
			break;
		}
	}
}


//使用链表增加一个数据
int main()
{
	struct Test t1 = {1, NULL};
	struct Test t2 = {2, NULL};
	struct Test t3 = {3, NULL};	
	struct Test t4 = {4, NULL};	
	
	struct Test *head = NULL;
	
	struct Test new = {100, NULL};
	struct Test new1 = {101, NULL};
	
	head = &t1;
	
	t1.next = &t2;
	t2.next = &t3;	
	t3.next = &t4;
	
	printf("use t1 to print three nums");
	printLink(&t1);	//1 2 3 4

	
	puts("delete node:\n");
	head = deletNode(head, 1);
	printLink(&head);	//2 3 4
	head = deletNode(head, 3);
	printLink(&head);	//2 4
	

	
	return 0;
}

1.6 链表的动态创建

        头插法，新插入的节点作为原链表的头加入。

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



struct Test
{
	int data;
	struct Test *next;
};


void printLink(struct Test *head)
{
	struct Test *point;
	point = head;
	
	while(1){
		if(point != NULL){
			printf("%d ", point->data);
			point = point->next;	
		}
		else{
			putchar('\n');
			break;
		}
	}
}

struct Test* insertFromHead(struct Test *head)
{
	struct Test *new;
	
	//申请sizeof(struct Test)这么大的空间，并且强制转换成struct Test*类型
	new = (struct Test*)malloc(sizeof(struct Test));
	printf("please input new data\n");
	scanf("%d", &(new->data));
	if(head == NULL){
		head = new;
		return head;
	}
	else{
		new->next = head;
		head = new;
	}

	return head;
}


//使用链表增加一个数据
int main()
{
	struct Test t1 = {1, NULL};
	struct Test t2 = {2, NULL};
	struct Test t3 = {3, NULL};	
	struct Test t4 = {4, NULL};	
	
	struct Test *head = NULL;
	
	struct Test new = {100, NULL};
	struct Test new1 = {101, NULL};
	
	head = &t1;
	
	t1.next = &t2;
	t2.next = &t3;	
	t3.next = &t4;
	
	printf("use t1 to print three nums");
	printLink(&t1);	//1 2 3 4
	
	puts("add node:\n");
	head = insertFromHead(head);
	printLink(&t1);	//如果输入5，那就是5 1 2 3 4 


	
	return 0;
}

        尾插法，新插入的节点作为原链表的尾加入。

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



struct Test
{
	int data;
	struct Test *next;
};


void printLink(struct Test *head)
{
	struct Test *point;
	point = head;
	
	while(1){
		if(point != NULL){
			printf("%d ", point->data);
			point = point->next;	
		}
		else{
			putchar('\n');
			break;
		}
	}
}



struct Test* insertBehind(struct Test *head)
{
	struct Test *p = head;
	struct Test *new;
	
	//申请sizeof(struct Test)这么大的空间，并且强制转换成struct Test*类型
	new = (struct Test*)malloc(sizeof(struct Test));
	printf("please input new data\n");
	scanf("%d", &(new->data));
	
	if(p == NULL){
		head = new;
		return head;
	}
	while(p->next != NULL){
		p = p->next;
	}
	p->next = new;
	
	return head;
}


//使用链表增加一个数据
int main()
{
	struct Test t1 = {1, NULL};
	struct Test t2 = {2, NULL};
	struct Test t3 = {3, NULL};	
	struct Test t4 = {4, NULL};	
	
	struct Test *head = NULL;
	
	struct Test new = {100, NULL};
	struct Test new1 = {101, NULL};
	
	head = &t1;
	
	t1.next = &t2;
	t2.next = &t3;	
	t3.next = &t4;
	
	printf("use t1 to print three nums");
	printLink(&t1);	//1 2 3 4
	


	puts("add node:\n");
	head = insertBehind(head);
	printLink(&head);	//如果输入100，那就是1 2 3 4 100

	

	
	return 0;
}

2、贪吃蛇

        是在linux环境下，基于Ncurse图形库的小游戏。

        在该项目中不仅使用到了C语言基础（变量、流程控制、函数、指针、结构体等）、数据结构链表基础、并且使用到了linux系统编程相关知识（文件编程、进程、线程、通信、第三方包等），具有承前启后。承上启下的作用。

2.1 ncurse

        使用C语言标准库，对于图形的建立以及上下左右键的获取响应不够友好，因此需要引入第三方的ncurse库来解决。

        ncurse早期是在linux内核配置上经常使用的一个编程库，它提供了一系列的函数以便使用者调用它们去生成基于文本的用户界面，现在已经被逐渐淘汰了。这里使用它，主要是为了获取按键的快速响应。

        安装该库

sudo apt-get install libncurses5-dev

        调用该库

//调用ncurses库
#include <ncurses.h>


int main()
{
    initscr();    //ncurses界面的初始化函数
    printw("This is a curses window.\n");    //在nurces模式下的printf
    getch();    //等待用户输入，如果没有这句话，程序就退出了，看不到程序运行的结果，也就是看不到上面那句话
    endwin();    //程序退出，调用该函数来恢复shell终端的显示，如果没有这句话，shell终端字会乱码，坏掉
    return 0;
}

        编译

#编译这个文件要加-lcurses，因为curses不是默认系统带有的，需要去手动链接它
#-llibrary，使用-l指令制定编译的时候使用的库library
gcc demo_curses.c -lcurses

2.1.1 使用ncurses获取键盘的上下左右键

#include <ncurses.h>

int main()
{
	char c;
	//因为上下左右键在ncurses库中的定义是0x0403之类的，所以要用过int型数据来存放
	int key;
	
	initscr();
	//使用keypad函数来获取键盘的功能性按键，从标准的stdscr中接收功能键，第二个参数代表是否接收（1代表是）
	keypad(stdscr, 1);
	
	while(1){
		key = getch();
		/*
		switch(key){
			case 0402:
				printw("Key_Down\n");
				break;
			case 0403:
				printw("Key_Up\n");
				break;
			case 0404:
				printw("Key_Left\n");
				break;
			case 0405:
				printw("Key_Right\n");
				break;
		}
		*/
		//这种方式也可以
		switch(key){
			case KEY_DOWN:
				printw("Key_Down\n");
				break;
			case KEY_UP:
				printw("Key_Up\n");
				break;
			case KEY_LEFT:
				printw("Key_Left\n");
				break;
			case KEY_RIGHT:
				printw("Key_Right\n");
				break;
		}
		
		printw("input：%d\n", key);
	}	
	endwin();
	
	return 0;
}

2.1.2 地图规划

        设计地图大小为20x20，竖直方向上的边界是“|”*20，水平方向的边界是“--”*20，贪吃蛇的身体是“[ ]”，贪吃蛇的食物是“##”。

#include <ncurses.h>

void initNcurses()
{
	initscr();
	keypad(stdscr, 1);
}

void gameMap()
{
	int hang;
	int lie;
	for(hang = 0; hang < 20; hang++){
		if((hang == 0) || (hang == 19)){
			for(lie = 0; lie < 20; lie++){
				printw("--");
			}
			printw("\n");
		}
		else{
			for(lie = 0; lie <= 20; lie++){
				if((lie == 0) || (lie == 20)){
					printw("|");
				}
				else{
					printw("  ");
				}
			}
			printw("\n");
		}
	}
}

int main()
{
	
	initNcurses();
	gameMap();
	getch();
	
	endwin();
	
	return 0;
}

2.1.3 贪吃蛇身体

        为贪吃蛇的身体设计一个结构体，这个结构体包含行坐标、列坐标以及下一个节点的位置（地址/指针）。

struct Body
{
	int hang;
	int lie;
	struct Body *next;
}；

        显示贪吃蛇的身体

#include <ncurses.h>

struct Body
{
	int hang;
	int lie;
	struct Body *next;
};

struct Body node1 = {2, 2, NULL};
struct Body node2 = {2, 3, NULL};
struct Body node3 = {2, 4, NULL};

node1.next = &node2;
node2.next = &node3;

int hasSnakeNode(int i, int j)
{
	struct Body *p;
	p = &node1;
	
	while(p != NULL){	
		if(p->hang == i && p->lie == j){
		return 1;
		}
		p = p->next;
	}
	
	
	return 0;
}


if(hasSnakeNode(hang, lie)){
    printw("[]");
}

        显示贪吃蛇的身体，进一步优化。

struct Body
{
	int hang;
	int lie;
	struct Body *next;
};

struct Body *head;    //头结点
struct Body *tail;    //尾结点

void addNode()
{
	struct Body *new = (struct Body*)malloc(sizeof(struct Body));
	//直接在尾节点上加更方便
	new->hang = tail->hang;
	new->lie = tail->lie + 1;
	new->next = NULL;
	
	tail->next = new;
	//此时新节点作为尾节点
	tail = new;
}

void initSnakeBody()
{
	head = (struct Body*)malloc(sizeof(struct Body));
	head->hang = 2;
	head->lie = 2;
	head->next = NULL;
	
	tail = head;
	
	addNode();
	addNode();
}

2.1.4 贪吃蛇身体向右移动

        原理是在原身体的基础上删除头结点，并增加一个尾节点，另两个节点保持不变。

2.1.5 贪吃蛇撞墙

        对边界进行检测，检测到边界，让游戏重新开始。

2.1.6 贪吃蛇方向变换

        让贪吃蛇一直自行移动以及改变位置，这是两个并行的任务，使用一个while函数无法实现，通过linux多线程（Linux线程是指函数在运行过程中是从上到下的一个线性关系的进程，而当原函数执行到某一步可以通过创建线程，使得原函数继续往下执行的过程中，同时执行别的任务）。

        在使用两个线程刷新任务的时候，图形界面出现了乱码，后来使用互斥锁解决了这个问题。

2.1.7 贪吃蛇四处移动

        定义一个方向，然后在创建贪吃蛇身体的时候给定一个初始方向，当按下方向键的时候，设定的方向值改变，根据改变的值不同，添加不一样的节点。

        在上述的过程中，贪吃蛇可以上下，左右在一条直线上移动，看着像一个可以往返的传送带那样，有点别扭，要让它在一条直线上只能往一个方向上移动。

2.1.8 贪吃蛇食物

        创建方法和贪吃蛇身体类似。

阅读全部

相关推荐

  1. 02 C

    2024-05-03 13:38:10       12 阅读

  5. 【PTA】L1-021 L1-022 L1-023 L1-024 L1-025(C)第四天

    2024-05-03 13:38:10       25 阅读

  9. 02_c/c++开源库ZeroMQ

    2024-05-03 13:38:10       25 阅读

最近更新

  4. TCP协议是安全的吗?

    2024-05-03 13:38:10       18 阅读

  12. 阿里云服务器执行yum，一直下载docker-ce-stable失败

    2024-05-03 13:38:10       19 阅读

  13. 【Python教程】压缩PDF文件大小

    2024-05-03 13:38:10       18 阅读

  18. 通过文章id递归查询所有评论（xml）

    2024-05-03 13:38:10       20 阅读

热门阅读

  3. Python的定义和调用函数

    2024-05-03 13:38:10       13 阅读

  5. 初识Vue-组件化开发（详解各个组件）

    2024-05-03 13:38:10       11 阅读

  9. Pytorch学习笔记——Transforms的使用

    2024-05-03 13:38:10       13 阅读

  11. 区块链 | IPFS：Merkle DAG

    2024-05-03 13:38:10       14 阅读

  14. ES常用查询方式

    2024-05-03 13:38:10       14 阅读

  16. 服务器分类

    2024-05-03 13:38:10       10 阅读

  19. Android 编译文件简述(Android.mk)

    2024-05-03 13:38:10       12 阅读

  23. c++自定义数据结构适配std::sort

    2024-05-03 13:38:10       14 阅读

  25. 21-ESP32-S3实时时钟（RTC）

    2024-05-03 13:38:10       13 阅读

  26. LeetCode刷题笔记第168题：Excel表列名称

    2024-05-03 13:38:10       13 阅读

  27. 目标检测YOLO实战应用案例100讲-基于FPGA的目标检测硬件加速技术及其应用研究(下)

    2024-05-03 13:38:10       11 阅读

  28. 抖音视频评论区用户采集 根据视频链接批量获取用户信息

    2024-05-03 13:38:10       30 阅读

  30. [机缘参悟-168] ：婚姻不是简单的两人的搭伙过日子，婚姻是两个人的荷尔蒙和身体、是两个人的生活方式、是两个人的金钱和经济基础、是两个人思想和三观、是两个大家庭、是各自整个社会关系网的融合和交织；

    2024-05-03 13:38:10       13 阅读