04ds_07day

============================
2022-8-9
============================

note

一.温故知新
    栈式的存储结构(受限制的存储结构)
    特点 : 先进后出
    线性表中的特殊存储形式
    通过顺序表来实现栈式存储结构
    通过链表来实现栈式存储结构

#define STACKSIZE 6

struct node
{
    int stack_buf[STACKSIZE];
    int stack_ind;
};

    队列式的存储结构(受限制的存储结构)
    特点 : 先进先出
    线性表中的特殊存储形式
    通过顺序表来实现队列式的存储结构
    通过链表来实现队列式的存储结构

#define QUEUESIZE 6

struct node
{
    int queue[QUEUESIZE];
    int front;
    int rear;
};

早测
快慢指针
struct llist_node 
{
    int val;
    struct llist_node *next;
};
1.反转链表
给你一个无头单向不循环链表的首结点l ，请你反转链表，
并返回反转后的链表首结点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
struct llist_node *func(struct llist_node *l)
{
	struct llist_node *cur = l;//指向当前要反转的结点
	struct llist_node *p = NULL;//指向原链表cur之后的位置
	struct llist_node *next = NULL;//指向反转链表之后cur之后的位置

	while(cur != NULL)//遍历所有结点
	{
		p = cur->next;
		cur->next = next;
		next = cur;
		cur = p;
	}
	return next;
}

2.链表的中间结点
给定一个头结点为handler的单向不循环链表,返回链表的中间结点
如果有两个中间结点，则返回第二个中间结点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
struct llist_node *fund(struct llist_node *handler)
{
	struct llist_node *s = handler;//慢指针
	struct llist_node *f = handler;//快指针
	
	while(f != NULL && f->next != NULL)//判断只有一个结点
	{
		s = s->next;
		f = f->next->next;
	}

	return s;
}

===================================
作业
1.把今天讲过的内容完完整整的复习一遍
2.把队列式的存储结构的实现方法再写一遍
3.写个链表,把早测的功能函数写程序实现
===================================

库的制作

在Linux环境中,以.a结尾的库文件是静态库文件
在Linux环境中,以.so结尾的库文件是动态库文件

静态库 : 是在程序编译时会被连接到目标代码中,当编译完之后
        程序运行时将不再需要该静态库,
        所以可执行程序的体积比较大
动态库 : 是在程序编译时仅仅简单的引用,当编译完之后
        程序运行时需要该动态库,
        所以可执行程序的体积比较小
查看可执行代码的依赖的共享库：ldd命令 – 打印程序依赖的共享库
注意 : 如果静态库和动态库同时存在的情况下优先使用动态库

静态库的制作方法

1.把.c文件编译成.o目标文件
    gcc -c -o xxxx.o xxxx.c
2.把.o目标文件编译成.a静态库文件
    ar -cr libxxxx.a xxxx.o
3.生成索引
    ranlib libxxxx.a
4.把静态库放到/lib目录中
    mv libxxxx.a /lib
5.把头文件放到/usr/include目录中
    mv xxxx.h /usr/include
6.编译主程序
    gcc main.c -lxxxx
如果没有把libxxxx.a和xxxx.h文件放到指定目录下
    gcc main.c -I[头文件的路径] -L[库文件的路径] -lxxxx
注意 : [头文件的路径] 和 [库文件的路径]只写路径不写文件名
    -I	指定头文件的路径
    -L	指定库文件的路径
    -l	链接库的名字

动态库的制作

1.把.c文件编译成.o目标文件
    gcc -fPIC -c -o xxx.o xxx.c
    -fPIC	使用gcc编译必须与位置无关
2.把.o目标文件编译成动态库文件
    gcc -shared -o libxxx.so xxx.o
3.把动态库文件移动到/lib目录中
    mv libxxx.so /lib
4.把头文件移动到/usr/include目录中
    mv xxx.h /usr/include
5.编译文件
    gcc main.c -lxxx

-------------------------------------
long arr[5] = {11,22,33,44,55};
与位置有关
    比如 : arr 0x1000
    arr[0]		*(long *)(0x1000)
    arr[1]		*(long *)(0x1008)
与位置无关
    比如 : arr 0x2000
    arr[0]		*(long *)(0x2000)
    arr[1]		*((long *)(0x2000) + 1);
-------------------------------------

quueu_arr队列

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

int main(void)
{
	QUEUE *q = NULL;//q指针指向队列
	int data[] = {11,22,33,44,55,66,77,88,99};
	int i = 0;//循环变量
	int ret = 0;//用来接收返回值的变量
	int save = 0;//用来保存出队的数据

	q = queue_create();//创建队列
	if(q == NULL)
		return -1;
	
	for(i = 0; i < sizeof(data) / sizeof(*data); i++)
	{
		ret = queue_en(q, data[i]);//入队
		if(ret == -1)//判断队列是否满了
		{
			printf("Queue Is Full!\n");
			break;
		}
	}

	queue_display(q);//遍历队列
	
	printf("***********************\n");
	
	ret = queue_de(q, &save);
	if(ret == -1)
		printf("Queue Is Empty!\n");
	else
		printf("Save = %d\n", save);
	
	printf("***********************\n");
	
	queue_display(q);//遍历队列
	
	queue_en(q, 999);

	queue_display(q);//遍历队列

	queue_destroy(q);//释放队列

	return 0;
}

queue.h

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#ifndef __QUEUE_H
#define __QUEUE_H

#define QUEUESIZE 6

typedef struct node
{
	int queue[QUEUESIZE];//队列
	int front;//队头
	int rear;//队尾
}QUEUE;

QUEUE *queue_create();//创建队列

int queue_en(QUEUE *q, int data);//入队

int queue_de(QUEUE *q, int *save);//出队

void queue_display(QUEUE *q);//遍历队列

void queue_destroy(QUEUE *q);//销毁队列

#endif

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

QUEUE *queue_create()//创建队列
{
	QUEUE *q = NULL;//将来指向队列

	q = malloc(sizeof(QUEUE));//为队列开辟空间
	if(q == NULL)
		return NULL;
	q->front = q->rear = 0;//把队头和队尾都标记到0的位置
	return q;
}

int queue_en(QUEUE *q, int data)//入队
{
	if((q->rear + 1) % QUEUESIZE == q->front)//判断队满
		return -1;
	q->rear = (q->rear + 1) % QUEUESIZE;//移动队尾的标志
	q->queue[q->rear] = data;//入队数据
}

int queue_de(QUEUE *q, int *save)//出队
{
	if(q->front == q->rear)
		return -1;
	q->front = (q->front + 1) % QUEUESIZE;
	*save = q->queue[q->front];
}

void queue_display(QUEUE *q)//遍历队列
{
	int i = (q->front + 1) % QUEUESIZE;

	if(q->front == q->rear)//判断是否是空队列
		return ;
	printf("------------------------\n");
	while(i != q->rear)
	{
		printf("%d\t", q->queue[i]);
		i = (i + 1) % QUEUESIZE;
	}
	printf("%d\n", q->queue[i]);
	printf("------------------------\n");
}

void queue_destroy(QUEUE *q)//销毁队列
{
	free(q);
}

makefile

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

queue_llist_队列

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

int main(void)
{
	QUEUE *q = NULL;//q指针指向队列
	int data[] = {11,22,33,44,55,66,77,88,99};
	int i = 0;//循环变量
	int ret = 0;//用来接收返回值的变量
	int save = 0;//用来保存出队的数据

	q = queue_create();//创建队列
	if(q == NULL)
		return -1;
	
	for(i = 0; i < sizeof(data) / sizeof(*data); i++)
	{
		ret = queue_en(q, data[i]);//入队
		if(ret == -1)//判断队列是否满了
		{
			printf("Queue Is Full!\n");
			break;
		}
	}

	queue_display(q);//遍历队列
	
	printf("***********************\n");
	
	ret = queue_de(q, &save);
	if(ret == -1)
		printf("Queue Is Empty!\n");
	else
		printf("Save = %d\n", save);
	
	printf("***********************\n");
	
	queue_display(q);//遍历队列
	
	queue_en(q, 999);

	queue_display(q);//遍历队列

	queue_destroy(q);//释放队列

	return 0;
}

queue.h

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

#include "llist.h"

typedef LLIST QUEUE;

QUEUE *queue_create();//创建队列

int queue_en(QUEUE *q, int data);//入队

int queue_de(QUEUE *q, int *save);//出队

void queue_display(QUEUE *q);//遍历队列

void queue_destroy(QUEUE *q);//销毁队列

#endif

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

QUEUE *queue_create()//创建队列
{
	return llist_create();
}

int queue_en(QUEUE *q, int data)//入队
{
	return llist_insert(q, &data, TAILINSERT);
}

int queue_de(QUEUE *q, int *save)//出队
{
	if(llist_empty(q))
		return -1;
	_fetch(q, save);
}

void queue_display(QUEUE *q)//遍历队列
{
	llist_display(q);
}

void queue_destroy(QUEUE *q)//销毁队列
{
	llist_destroy(q);
}

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
32
33
34
35
#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 *);//取出结点

int llist_empty(LLIST *);//判断链表为空链表

int _fetch(LLIST *, 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
117
118
119
120
121
122
123
124
125
126
#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;//指向每一个数据结点

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

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)
		{
			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;
}

int llist_empty(LLIST *handler)
{
	return handler == handler->next;
}

int _fetch(LLIST *handler, void *save)//取出第一个数据结点
{
	LLIST *cur = handler->next;

	cur->next->prev = cur->prev;
	cur->prev->next = cur->next;
	memcpy(save, cur, sizeof(cur->id));
	free(cur);
	return 0;
}

makefile

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