04ds_02day

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

note

malloc calloc realloc 开辟空间
free 释放空间
malloc(sizeof(int) * 4);

线性存储结构
    顺序表
        数组
            一维数组
            多维数组
    链表
        是一种物理存储单元上非连续\非顺序的存储结构
        链表是由一个一个的结点组成的
        每一个结点是由两部分组成 : 数据域 和 指针域
        数据域 : 是用来存储结点的数据的
        指针域 : 是用来存储下一个结点的地址的

        在操作链表时包括有 : 增 删 改 查一系列的操作

        在描述链表时会用到一些属性
            有头链表/无头链表	有没有头结点的意思
            循环链表/不循环链表	链表是否可以构成环
            单向链表/双向链表	遍历链表方向

        有头单向不循环的链表
--------------------------------------------------------------------------------
    创建一个有头单向不循环的链表
    1.创建头结点		llist_create();
    2.插入数据结点		llist_insert();
        先把新创建出的结点挂到链表上,再改变链表之前的结构
        头插法{11,22,33,44,55}
        把数据结点插入到头结点之后的位置
        头结点->NULL
        头结点->11->NULL
        头结点->22->11->NULL
        头结点->33->22->11->NULL
        
        尾插法{11,22,33,44,55}
        把数据结点插入到链表最后的位置
        头结点->NULL
        头结点->11->NULL
        头结点->11->22->NULL
        头结点->11->22->33->NULL
    3.遍历链表			llist_display();
    4.销毁链表			llist_destroy();
        销毁链表或者删除结点时要注意
        单链表再删除时需要一前一后两个指针
    =======================================
    5.查找结点			llist_find();
    6.删除结点			llist_delete();
    7.拿出结点			llist_fetch();

==============================
作业
1.把今天讲过的内容完完整整的复习一遍
2.把有头单向不循环链表再重新的写一遍
3.尝试自己搞定有头单向循环链表
==============================

链表

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

enum MODE {HEADINSERT, TAILINSERT};//头插法和尾插法

#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 = NULL;//让头结点的next指针指向NULL
	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 : newnode->next = p->next; break;
		case TAILINSERT : while(p->next != NULL) p = p->next;
							break;
		default : free(newnode); return -2;
		//模式选择有误,释放空间,结束程序,并且返回-2
	}
	p->next = newnode;
	return 0;
}

void llist_display(LLIST *handler)
{
	LLIST *cur = NULL;//指向每一个数据结点

	for(cur = handler->next; cur != NULL; 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 != NULL)
	{
		back->next = cur->next;//把要释放的结点从链表中拆除
		free(cur);//释放数据结点
		cur = back->next;
	}
	free(back);//释放头结点
}

LLIST *llist_find(LLIST *handler, const void *find_data)
{
	LLIST *cur = NULL;//循环查找的指针

	for(cur = handler->next; cur != NULL; 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;

	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;
	
	while(back->next != cur)
		back = back->next;
	
	back->next = cur->next;
	memcpy(save, cur, sizeof(LLIST));
	free(cur);
	return 0;
}

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

int main(void)
{
	LLIST *handler = NULL;//handler指针指向头结点
	LLIST *find = NULL;//find指针指向将来找到的结点
	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;//让next指针指向空
		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,"stu9",&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;
}

makefile

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