naoemb
0%

04ds_06day

发表于 更新于
本文字数： 12k 阅读时长 ≈ 10 分钟

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

note

一.温故知新
线性表
        是n个具有相同类型的数据元素的集合
        线性表是一种使用比较广泛的数据结构
        线性表在逻辑上是线性的结构,也就相当于是一条直线
        但是在物理结构上并不一定是连续的
        线性表在物理存储时,通常以数组或者链表的形式存储
    顺序表
        是用一段连续的存储空间依次存储数据元素的线性结构
        一般情况下使用的就是数组,在数组中做增删改查的操作
        定长的顺序表 : 使用定长的数组
            适用于确定成员个数的场景
        不定长的顺序表 : 使用动态开辟的数组
            可以根据需求灵活开辟空间
    链表
        在逻辑结构上是线性的存储,
        但是在物理结构体并不是连续的存储结构
        链表中数据的顺序根据链表中结点的指针的指向来确定
顺序表的优缺点
    优点 : 使用的是连续的存储空间
            可以使用下标快速定位到某个成员
    缺点 : 定长的顺序表定义之后不能再扩容
            插入新的成员以及删除成员,需要挪动后续所有成员
链表的优缺点
    优点 : 插入新的成员和删除成员方便,不会造成空间的浪费
    缺点 : 访问链表的成员不方便

总结 : 顺序表和链表是相辅相成的,需要在适合的场景下使用
如果写项目工程使用有头双向循环链表合适
如果在笔试面试中碰到链表的题目,一般来说考无头单向链表
===================================
早测
1.移出链表元素
给你一个无头单向不循环链表的首结点l和一个整数 val 
请你删除链表中所有等于 val 的节点，并返回新的首结点 。

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
struct llist_node
{
	int val;
	struct llist_node *next;
};

struct llist_node* remove(struct llist_node* l, int val)
{
	struct llist_node *cur = l;//指向要删除的结点
	struct llist_node *back = NULL;
	//指向要删除的结点的前一个位置

	while(cur != NULL)//判断是否遍历完所有的结点
	{
		if(cur->val == val)//判断是否是要删除的数据
		{
			if(back == NULL)//判断删除的是否是第一个结点
			{
				l = l->next;//改变l的位置
				free(cur);//释放第一个结点
				cur = l;//改变cur的位置
			}
			else
			{
				back->next = cur->next;
				free(cur);
				cur = back->next;
			}
		}
		else
		{
			back = cur;
			cur = cur->next;
		}
	}
	return l; 
}

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

线性表
    两种特殊的线性存储结构(受限制的存储形式)
    栈式存储结构
        一定要和内存中的栈区区分开
        stack
        特点 : 先进后出
        可以把栈式存储结构抽象成有底的容器
        把数据存储到栈式存储结构中	入栈|进栈|压栈|push
        从栈式存储结构中取出数据	出栈|退栈|弹栈|pop
        存入数据或者取出数据的一端	栈顶|ind
        另外一端					栈底
    由于栈式存储结构属于线性表中特殊的存储形式
    所以既可以用顺序表来实现,也可以用链表来实现
        入栈时需要判断,栈是否满了
        出栈时需要判断,栈是否空了

    队列式存储结构

=================================
作业
1.把今天讲过的内容完完整整的复习一遍
2.把栈式存储结构(三种方式)再重新实现一遍
3.把早测的功能函数再重新实现一遍
=================================

1
2
3
4
5
6
l
|
V
11->22->11->33->11->44->11->NULL

11

数组栈

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

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

	for(i = 0; i < sizeof(data) / sizeof(*data); i++)
	{
		ret = stack_push(data[i]);//入栈	
		if(ret == -1)//判断是否栈满
		{
			printf("Stack Is Full!\n");
			break;
		}
	}

	stack_display();//遍历栈

	printf("*******************\n");
	
	ret = stack_pop(&save);//出栈
	if(ret == -1)//判断栈是否为空
		printf("Stack Is Empty!\n");
	else
		printf("Save = %d\n", save);
	
	printf("*******************\n");
	stack_display();//遍历栈

	stack_push(999);
	stack_display();//遍历栈

	return 0;
}

stack.h

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

#define STACKSIZE 6

int stack_arr[STACKSIZE];//栈
int stack_ind;//栈顶元素

int stack_push(int data);

int stack_pop(int *save);

void stack_display(void);

#endif

stack.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 "stack.h"

int isfull(void)
{
	return !(stack_ind - STACKSIZE);
}

int isempty(void)
{
	return !(stack_ind);
}

int stack_push(int data)
{
	if(isfull())//判断是否栈满了
		return -1;
	stack_arr[stack_ind++] = data;//入栈
}

int stack_pop(int *save)//出栈
{
	if(isempty())//判断栈是否为空
		return -1;
	*save = stack_arr[--stack_ind];
}

void stack_display(void)
{
	int i = stack_ind;//循环变量

	while(i--)
	{
		printf("	%d\n", stack_arr[i]);
	}
	printf("===================\n");
}

makefile

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

指针栈

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 "stack.h"

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

	s = stack_create();//开辟栈式存储结构的空间
	if(s == NULL)//判断是否开辟空间失败
		return -1;//开辟失败,结束程序,并且返回-1

	for(i = 0; i < sizeof(data) / sizeof(*data); i++)
	{
		ret = stack_push(s, data[i]);//入栈
		if(ret == -1)//判断栈是否满了
		{
			printf("Stack Is Full!\n");
			break;
		}
	}

	stack_display(s);//遍历栈

	printf("*******************\n");
	
	ret = stack_pop(s, &save);
	if(ret == -1)
		printf("Stack Is Empty!\n");
	else
		printf("Save = %d\n", save);
	
	printf("*******************\n");
	
	stack_display(s);//遍历栈
	
	stack_push(s, 999);
	
	stack_display(s);//遍历栈

	stack_destroy(s);//销毁栈

	return 0;
}

stack.h

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

#define STACKSIZE 6

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

STACK *stack_create();//创建栈

int stack_push(STACK *s, int data);//入栈

int stack_pop(STACK *s, int *save);//出栈

void stack_display(STACK *s);//遍历栈

void stack_destroy(STACK *s);//销毁栈

#endif

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

STACK *stack_create()//创建栈
{
	STACK *s = NULL;//s指针指向开辟的空间

	s = malloc(sizeof(STACK));//开辟空间
	if(s == NULL)//判断是否开辟失败
		return NULL;
	s->stack_ind = 0;//把栈顶元素先清零

	return s;
}

int isfull(STACK *s)
{
	return !(s->stack_ind - STACKSIZE);
}

int isempty(STACK *s)
{
	return !(s->stack_ind);
}

int stack_push(STACK *s, int data)//入栈
{
	if(isfull(s))//判断栈是否满了
		return -1;
	s->stack_buf[s->stack_ind++] = data;
}

int stack_pop(STACK *s, int *save)//出栈
{
	if(isempty(s))
		return -1;
	*save = s->stack_buf[--s->stack_ind];
}

void stack_display(STACK *s)//遍历栈
{
	int i = s->stack_ind;

	while(i--)
		printf("	%d\n", s->stack_buf[i]);
	printf("==================\n");
}

void stack_destroy(STACK *s)//销毁栈
{
	free(s);
}

makefile

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

链表栈

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 "stack.h"

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

	s = stack_create();//开辟栈式存储结构的空间
	if(s == NULL)//判断是否开辟空间失败
		return -1;//开辟失败,结束程序,并且返回-1

	for(i = 0; i < sizeof(data) / sizeof(*data); i++)
	{
		ret = stack_push(s, data[i]);//入栈
		if(ret == -1)//判断栈是否满了
		{
			printf("Stack Is Full!\n");
			break;
		}
	}

	stack_display(s);//遍历栈

	printf("*******************\n");
	
	ret = stack_pop(s, &save);
	if(ret == -1)
		printf("Stack Is Empty!\n");
	else
		printf("Save = %d\n", save);
	
	printf("*******************\n");
	
	stack_display(s);//遍历栈
	
	stack_push(s, 999);
	
	stack_display(s);//遍历栈

	stack_destroy(s);//销毁栈

	return 0;
}

stack.h

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

#include "llist.h"

typedef LLIST STACK;

STACK *stack_create();//创建栈

int stack_push(STACK *s, int data);//入栈

int stack_pop(STACK *s, int *save);//出栈

void stack_display(STACK *s);//遍历栈

void stack_destroy(STACK *s);//销毁栈

#endif

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

STACK *stack_create()//创建栈
{
	return llist_create();
}

int isempty(STACK *s)
{
	return llist_empty(s);
}

int stack_push(STACK *s, int data)//入栈
{
	return llist_insert(s, &data, HEADINSERT);
}

int stack_pop(STACK *s, int *save)//出栈
{
	if(isempty(s))
		return -1;
	_fetch(s, save);
}

void stack_display(STACK *s)//遍历栈
{
	llist_display(s);
}

void stack_destroy(STACK *s)//销毁栈
{
	llist_destroy(s);
}

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
#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\n",cur->id);
	printf("==================\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
stack : main.o llist.o stack.o
	gcc -o $@ $^
clean :
	rm -rf *.o stack

汉诺塔

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

#define HANOISIZE 7

struct
{
	int hanoi[HANOISIZE];
	int ind;
}hanoi_arr[3] = {{{7,6,5,4,3,2,1}, 7}, {}, {}};

void draw(void)
{
	int i = 0, j = 0;

	system("clear");
	for(i = 0; i < 3; i++)//铁柱的遍历
	{
		for(j = 0; j < hanoi_arr[i].ind; j++)
			printf("%d", hanoi_arr[i].hanoi[j]);
		for(; j < 10; j++)
			printf("-");
		printf("\n");
	}
	getchar();
}

void move(int src, int dest)
{
	hanoi_arr[src].ind--;
	hanoi_arr[dest].hanoi[hanoi_arr[dest].ind] = hanoi_arr[src].hanoi[hanoi_arr[src].ind];
	hanoi_arr[dest].ind++;
	draw();
}

void play(int src, int dest, int tmp, int num)
{
	if(num == 1)
	{
		move(src, dest);
		return ;
	}
	play(src, tmp, dest, num - 1);
	move(src, dest);
	play(tmp, dest, src, num - 1);
}

int main(int argc, char *argv[])
{
	draw();
	
	play(0, 1, 2, HANOISIZE);

	return 0;
}