04ds_08day

============================
2022-8-10
============================

note

一.温故知新
    栈式的存储结构
        先进后出
    队列式的存储结构
        先进先出
    无论是顺序表还是链表都可以实现
    栈式
    struct node
    {
        int stack[6];
        int ind;
    };
    队列
    struct node
    {
        int queue[6];
        int front;
        int rear;
    };

    静态库和动态库
早测 
1.链表中倒数第k个结点
给定一个头结点为handler的单向不循环链表
输出该链表中倒数第k个结点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
struct llist_node *func(struct llist_node *l, int k)
{
	struct llist_node *s = l;//慢指针
	struct llist_node *f = l;//快指针

	while(k--)
	{
		if(f == NULL)//判断链表是否提前结束
			return NULL;
		f = f->next;
	}
	while(f != NULL)
	{
		s = s->next;
		f = f->next;
	}
}

2.合并两个有序链表
将两个升序的无头单向不循环链表合并为一个新的升序链表并返回
新链表是通过拼接给定的两个链表的所有节点组成的

 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
struct llist_node *func(struct llist_node *l1, struct llist_node *l2)
{
	struct llist_node *l = NULL;//指向合并之后的链表
	struct llist_node *cur = NULL;

	if(l1 == NULL)
		return l2;
	if(l2 == NULL)
		return l1;
	if(l1->val < l2->val)
	{
		l = cur = l1;
		l1 = l1->next;
	}
	else
	{
		l = cur = l2;
		l2 = l2->next;
	}
	while(l1 != NULL && l2 != NULL)
	{
		if(l1->val < l2->val)
		{
			cur->next = l1;
			l1 = l1->next;
		}
		else
		{
			cur->next = l2;
			l2 = l2->next;
		}
		cur = cur->next;
	}
	if(l1 != NULL)
		cur->next = l1;
	if(l2 != NULL)
		cur->next = l2;

	return l;
}

3.简答题
给定一个有头单向不循环链表的头结点handler和要删除的结点p

内核链表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
/usr/src/linux-hwe-5.4-headers-5.4.0-122/include/linux
list.h

struct list_head
{
	struct list_head *prev;
	struct list_head *next;
};

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)

LIST_HEAD(handler);

替换成
struct list_head handler = {&handler, &handler};

==============================
作业
1.把今天讲过的内容完完整整的复习一遍
2.把使用内核链表的功能补充完整
3.把早测的内容在电脑上写一遍
4.刷题
5.写项目
==============================

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

struct list_head
{
	struct list_head *prev;
	struct list_head *next;
};

struct stu
{
	int id;
	char name[20];
	int math;
	struct list_head node;
};

int main(int argc, char *argv[])
{
	struct stu s;

	printf("&s = %p\n", &s);
	printf("&s.id = %p\n", &s.id);
	printf("s.name = %p\n", s.name);
	printf("&s.math = %p\n", &s.math);
	printf("&s.node = %p\n", &s.node);
	printf("SIZE=%ld\n", (size_t)&(((struct stu *)0)->node));

	return 0;
}
/*
	struct stu a = 0;//假如说a的地址是0x12345678
	struct stu *p = &a;//p 保存的地址是0x12345678

	p->node
	(size_t)&((struct stu *)(0)->node)
*/

kernellist

list.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
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
#ifndef _MYTEST_LIST_H
#define _MYTEST_LIST_H

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

#define container_of(ptr, type, member) ({			\
	const typeof( ((type *)0)->member ) *__mptr = (ptr);	\
	(type *)( (char *)__mptr - offsetof(type,member) );})

struct list_head {
	struct list_head *prev;
	struct list_head *next;
};

#define LIST_HEAD_INIT(name) { &(name), &(name) }
//struct list_head name = {&name, &name};
#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)

static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
	list->prev = list;
}
static inline void __list_add(struct list_head *new,
			      struct list_head *prev,
			      struct list_head *next)
{
	next->prev = new;
	new->next = next;
	new->prev = prev;
	prev->next = new;
}

static inline void list_add(struct list_head *new, struct list_head *head)
{
	__list_add(new, head, head->next);
}

static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
	__list_add(new, head->prev, head);
}

static inline void __list_del(struct list_head * prev, struct list_head * next)
{
	next->prev = prev;
	prev->next = next;
}

static inline void list_del(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
	entry->next = NULL;
	entry->prev = NULL;
}

#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

#define list_for_each(pos, head) \
	for (pos = (head)->next; pos != (head); pos = pos->next)

/*
	list_for_each(pos, head)
		遍历链表
		pos		指向每个数据节点的node
		head	指向头节点的指针
	list_entry(ptr, type, member)
		得到数据的首地址	
		ptr		node的地址
		type	客户的结构体名
		member	结构体中node的成员名
*/


#endif

kernellist.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
/*
	内核链表
		有头双向循环链表
		1.创建头结点
		2.插入数据结点(头插法 尾插法)
		3.遍历链表
		4.销毁链表
		==================
		5.查找结点
		6.删除结点
		7.拿出结点
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"

#define NAMESIZE 20

typedef struct stu
{
	int id;
	char name[NAMESIZE];
	int math;
	struct list_head node;
}STU;

void print(const void *data)
{
	const STU *p = data;
	printf("%d	%s	%d\n", p->id, p->name, p->math);
}

int id_cmp(const void *data, const void *key)
{
	const STU *p = data;
	const int *k = key;
	
	return !(p->id - *k);
}

int name_cmp(const void *data, const void *key)
{
	const STU *p = data;
	const char *k = key;
	return !(strcmp(p->name, k));
}

int main(void)
{
	LIST_HEAD(handler);//创建头结点
	STU *data = NULL;//将来指向开辟的空间,存储数据
	STU *datap = NULL;//将来指向数据结点的首地址
	struct list_head *pos = NULL;//pos指针指向每个数据结点
	int i = 0;//循环变量
	int find_id = 100;//要查找的ID号
	char *find_name = "stu4";//要查找的名字

	for(i = 0; i < 5; i++)
	{
		data = malloc(sizeof(STU));//开辟空间
		if(data == NULL)
			continue;
		data->id = 100 + i;
		sprintf(data->name, "stu%d", i);
		data->math = 100 - i;
		//list_add(&data->node, &handler);//头插法
		list_add_tail(&data->node, &handler);//尾插法
	}

	//不要加 ; 因为list_for_each是一个宏
	list_for_each(pos, &handler)//遍历链表
	{
		datap = list_entry(pos, STU, node);
		//获取数据结点的首地址
		print(datap);//打印数据
	}

	printf("----------------------\n");
	
	list_for_each(pos, &handler)//查找结点
	{
		datap = list_entry(pos, STU, node);
		if(name_cmp(datap, "stu9"))
		{
			printf("Find It!\n");
			print(datap);
		}
	}
	
	printf("----------------------\n");

	list_for_each(pos, &handler)//销毁链表
	{
		datap = list_entry(pos, STU, node);//找到首地址
		list_del(pos);//把数据结点从链表摘除
		free(datap);//释放空间
		pos = &handler;//指向头结点
	}

	return 0;
}