devbox
煮酒与君饮
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构回顾】_node*list=(node*)malloc(sizeof(node))

作者：煮酒与君饮 | 2024-07-30 07:45:42

赞

踩

node*list=(node*)malloc(sizeof(node))

数据结构回顾

一、单链表

在这里插入图片描述

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

typedef struct Node {
	int data;
	Node *next;
}Node;

Node* initList()
{
	Node *list = (Node*)malloc(sizeof(Node));
	list->data = 0;
	list->next = NULL;
	return list;
}

void headInsert(Node* L, int data)
{
	Node *node = (Node*)malloc(sizeof(Node));
	node->data = data;
	node->next = L->next;
	L->next = node;
	L->data++;
}

void tailInsert(Node* L, int data)
{
	Node *List = L;
	Node *node = (Node*)malloc(sizeof(Node));
	node->data = data;
	while (List->next)
	{
		List = List->next;
	}
	node->next = List->next;
	List->next = node;
	L->data++;
}

int delete_node(Node* L, int data)
{
	Node *pre = L;
	Node *current = L->next;

	while(current)
	{
		if (current->data==data)
		{
			pre->next = current->next;
			free(current);
			L->data--;
			return true;
		}
		else
		{
			pre = current;
			current = current->next;
		}
	}
	return false;
}

void printList(Node* L)
{
	while (L->next)
	{
		L = L->next;
		printf("node = %d\n", L->data);
	}
}

int main()
{
	Node* L = initList();
	headInsert(L, 1);
	headInsert(L, 2);
	headInsert(L, 3);
	headInsert(L, 4);
	headInsert(L, 5);
	tailInsert(L, 6);
	tailInsert(L, 7);
	printList(L);

	if (delete_node(L, 3)) {
		printf("success delete\n");
	}
	else {
		printf("fail delete\n");
	}
	printList(L);

	system("pause");
	return 0;
}

  • 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

二、单循环链表

在这里插入图片描述

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

typedef struct Node {
	int data;
	Node *next;
}Node;

Node* initList() 
{
	Node *L = (Node*)malloc(sizeof(Node));
	L->next = NULL;
	L->data = 0;
	L->next = L;
	return L;
}

void headInsert(Node* L, int data)
{
	Node *node = (Node*)malloc(sizeof(Node));
	node->data = data;
	node->next = L->next;
	L->next = node;
	L->data++;
}

void tailInsert(Node* L, int data)
{
	Node *List = L;
	Node *node = (Node*)malloc(sizeof(Node));
	while (List->next!=L)
	{
		List = List->next;
	}
	node->data = data;
	node->next = L;
	List->next = node;
	L->data++;
}

int delete_node(Node* L, int data)
{
	Node *pre = L;
	Node *current = L->next;
	while (current!=L)
	{
		if (current->data == data)
		{
			pre->next=current->next;
			free(current);
			L->data--;
			return true;
		}
		else
		{
			pre = current;
			current = current->next;
		}	
	}
	return false;
}

void printList(Node* L)
{
	Node *node = L->next;
	while (node !=L)
	{
		printf("%d->", node->data);
		node=node->next;
	}
	printf("NULL\n");
}
int main()
{
	Node* L = initList();
	headInsert(L, 1);
	headInsert(L, 2);
	headInsert(L, 3);
	headInsert(L, 4);
	headInsert(L, 5);
	tailInsert(L, 6);
	tailInsert(L, 7);
	printList(L);
	delete_node(L, 4);
	delete_node(L, 7);
	printList(L);

	system("pause");
	return 0;
}

  • 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

三、双链表

在这里插入图片描述

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

typedef struct Node {
	int data;
	Node *pre;
	Node *next;
}Node;

Node* initList() 
{
	Node *L=(Node*)malloc(sizeof(Node));
	L->data = 0;
	L->next = NULL;
	L->pre = NULL;
	return L;
}

void headInsert(Node* L, int data)
{
	Node *node= (Node*)malloc(sizeof(Node));
	node->data = data;
	node->next = L->next;
	node->pre = L;
	if (L->next!=NULL)
	{
		L->next->pre = node;
	}
	L->next = node;
	L->data++;
}

void tailInsert(Node* L, int data)
{
	Node *n = L;
	Node* node = (Node*)malloc(sizeof(Node));
	node->data = data;
	while (n->next)
	{
		n = n->next;
	}
	node->next = n->next;
	node->pre = n;
	n->next = node;
	L->data++;
}

int delete_Node(Node* L, int data)
{
	Node* n = L->next;
	while (n)
	{
		if (n->data == data)
		{
			n->pre->next = n->next;
			if (n->next != NULL)
			{
				n->next->pre = n->pre;
			}
			free(n);
			L->data--;
			return true;
		}
		else
		{
			n = n->next;
		}
	}
	return false;
}

void printList(Node* L)
{
	Node *n = L->next;
	while (n)
	{
		printf("%d -> ", n->data);
		n = n->next;
	}
	printf("NULL\n");
}

int main()
{
	Node *L= initList();
	headInsert(L, 1);
	headInsert(L, 2);
	headInsert(L, 3);
	headInsert(L, 4);
	tailInsert(L, 5);
	tailInsert(L, 6);
	printList(L);
	delete_Node(L, 6);
	printList(L);
	delete_Node(L, 3);
	printList(L);

	system("pause");
	return 0;
}

  • 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

四、双循环链表

在这里插入图片描述

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

typedef struct Node {
	int data;
	Node *pre;
	Node *next;
}Node;

Node * initList()
{
	Node * L = (Node*)malloc(sizeof(Node));
	L->data = 0;
	L->next = L;
	L->pre = L;
	return L;
}

void headInsert(Node* L, int data)
{
	Node *node = (Node*)malloc(sizeof(Node));
	node->data = data;
	node->next = L->next;
	node->pre = L;
	L->next->pre = node;
	L->next = node;
	L->data++;
}

void tailInsert(Node* L, int data)
{
	Node *n = L;
	Node* node = (Node*)malloc(sizeof(Node));
	while (n->next != L)
	{
		n=n->next;
	}
	node->data = data;
	node->next = n->next;
	node->pre = n;
	n->next->pre = node;
	n->next = node;
	L->data++;
}

int delete_Node(Node* L, int data)
{
	Node* n=L->next;
	while (n!=L)
	{
		if (n->data == data)
		{
			n->pre->next = n->next;
			n->next->pre = n->pre;
			free(n);
			L->data--;
			return true;
		}
		n = n->next;
	}
	return false;
}

void printList(Node* L)
{
	Node *n = L->next;
	while (n!=L)
	{
		printf("%d -> ",n->data);
		n=n->next;
	}
	printf("NULL\n");
}

int main()
{
	Node* L = initList();
	headInsert(L, 1);
	headInsert(L, 2);
	headInsert(L, 4);
	headInsert(L, 5);
	printList(L);
	tailInsert(L, 6);
	tailInsert(L, 7);
	printList(L);
	delete_Node(L, 7);
	printList(L);
	delete_Node(L, 4);
	printList(L);

	system("pause");
	return 0;
}

  • 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

五、栈（先进后出）

在这里插入图片描述
在这里插入图片描述

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

typedef struct Node {
	int data;
	Node *next;
}Node;

Node *initStack()
{
	Node *S = (Node*)malloc(sizeof(Node));
	S->next = NULL;
	S->data = 0;
	return S;
}

void push(Node *S, int data)
{
	Node *node = (Node*)malloc(sizeof(Node));
	node->data = data;
	node->next = S->next;
	S->next = node;
	S->data++;
}


void printStack(Node *S)
{
	Node* node = S->next;
	while (node)
	{
		printf("%d --> ",node->data);
		node = node->next;
	}
	printf("NULL\n");
}

int isEmpty(Node *S)
{
	if (S->next == NULL||S->data==0)
	{ 
		return 1;
	}
	else
	{
		return 0;
	}
}

int pop(Node *S)
{
	if (isEmpty(S))
		return -1;
	Node *node = S->next;
	S->next = node->next;
	int data = node->data;
	free(node);
	S->data--;
	return data;
}

int main()
{
	Node *stack = initStack();
	push(stack, 1);
	push(stack, 2);
	push(stack, 3);
	push(stack, 4);
	printStack(stack);
	printf("pop = %d\n", pop(stack));
	printStack(stack);
	printf("pop = %d\n", pop(stack));
	printStack(stack);
	push(stack, 5);
	push(stack, 6);
	push(stack, 7);
	push(stack, 8);
	printStack(stack);

	system("pause");
	return 0;
}

  • 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

六、队列（先进先出）

在这里插入图片描述

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

typedef struct Node{
	int data;
	Node *next;
}Node;

Node *initQueue()
{
	Node *Q = (Node*)malloc(sizeof(Node));
	Q->next = NULL;
	Q->data = 0;
	return Q;
}

void enQueue(Node *Q,int data)
{
	Node *q = Q;
	Node *node = (Node*)malloc(sizeof(Node));
	node->data = data;
	int value = Q->data;
	while (value--)
	{
		q=q->next;
	}
	node->next = q->next;
	q->next = node;
	Q->data++;
}

int isEmpty(Node *Q)
{
	if (Q->data == 0 || Q->next == NULL)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

int deQueue(Node *Q)
{
	Node *node = Q->next;
	if (isEmpty(Q))
		return -1;
	int data = node->data;
	Q->next = node->next;
	free(node);
	Q->data--;
	return data;
}

void printQueue(Node *Q)
{
	Node *node = Q->next;
	while (node)
	{
		printf("%d --> ",node->data);
		node = node->next;
	}
	printf("NULL\n");
}

int main()
{
	Node * q = initQueue();
	enQueue(q, 1);
	enQueue(q, 2);
	enQueue(q, 3);
	enQueue(q, 4);
	printQueue(q);
	printf("dequeue = %d\n", deQueue(q));
	printf("dequeue = %d\n", deQueue(q));
	printQueue(q);
	printf("dequeue = %d\n", deQueue(q));
	printf("dequeue = %d\n", deQueue(q));
	printQueue(q);
	enQueue(q, 1);
	enQueue(q, 2);
	enQueue(q, 3);
	printf("dequeue = %d\n", deQueue(q));
	printf("dequeue = %d\n", deQueue(q));
	printQueue(q);
	enQueue(q, 5);
	enQueue(q, 6);
	printQueue(q);

	system("pause");
	return 0;
}

  • 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

七、循环队列

在这里插入图片描述

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

#define MAXSIZE 5

typedef struct Queue {
	int front;
	int real;
	int data[MAXSIZE];
}Queue;

Queue* initQueue()
{
	Queue *q = (Queue*)malloc(sizeof(Queue));
	q->front = q->real = 0;
	return q;
}

void printQueue(Queue* Q) 
{
	int length = (Q->real - Q->front + MAXSIZE) % MAXSIZE;
	int index = Q->front;
	while (length--)
	{
		printf("%d --> ", Q->data[index]);
		index = (index + 1) % MAXSIZE;
	}
	printf("NULL\n");
}

int isFull(Queue* Q)
{
	if ((Q->real + 1) % MAXSIZE == Q->front)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

int isEmpty(Queue* Q)
{
	if (Q->front==Q->real)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

int enQueue(Queue* Q, int data)
{
	if (isFull(Q))
		return -1;
	Q->data[Q->real] = data;
	Q->real = (Q->real + 1) % MAXSIZE;
	return 0;
}

int deQueue(Queue* Q)
{
	if (isEmpty(Q))
		return -1;
	int data = Q->data[Q->front];
	Q->front = (Q->front + 1) % MAXSIZE;
	return data;
}

int main()
{
	Queue* Q = initQueue();
	enQueue(Q, 1);
	enQueue(Q, 2);
	enQueue(Q, 3);
	enQueue(Q, 4);
	printQueue(Q);
	printf("dequeue = %d\n", deQueue(Q));
	printQueue(Q);
	printf("dequeue = %d\n", deQueue(Q));
	printQueue(Q);
	enQueue(Q, 5);
	enQueue(Q, 6);
	enQueue(Q, 7);
	printQueue(Q);
	
	system("pause");
	return 0;

}

  • 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

八、冒泡排序

#include <stdio.h>

void printArray(int array[], int length)
{
	for (int i = 0; i < length; i++)
	{
		printf("%d ",array[i]);
	}
	printf("\n");
}

void bubbleSort(int array[], int length)
{
	for (int j = 0; j < length-1; j++)
	{
		for (int i = 0; i < length-1-j; i++)
		{
			if (array[i] > array[i + 1])
			{
				int temp = array[i];
				array[i] = array[i + 1];
				array[i + 1] = temp;
			}
		}
		printArray(array,length);
	}
}

int main()
{
	int array[8] = { 49, 38, 65, 97, 76, 13, 27, 49 };
	bubbleSort(array, 8);

	return 0;
}

  • 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 <string.h>

void printArray(int array[], int length)
{
	for (int i = 0; i < length; i++)
	{
		printf("%d ", array[i]);
	}
	printf("\n");
}

int partition(int array[], int i, int j)
{
	int x = array[i];
	while (i < j)
	{
		while(i<j&&array[j]>=x)
		{
			j--;
		}
		if (i < j)
		{
			array[i] = array[j];
			i++;
		}
		while (i<j&&array[i]<x)
		{
			i++;
		}
		if (i < j)
		{
			array[j] = array[i];
			j--;
		}

	}
	array[i] = x;
	return i;
}

void quickSort(int array[], int i, int j)
{
	if (i < j)
	{
		int index = partition(array,i,j);
		printArray(array, 8);
		quickSort(array,i,index-1);
		quickSort(array, index+1,j);
	}
}

int main()
{ 
	int array[8] = { 27, 38, 13, 49, 76, 97, 65, 49 };
	quickSort(array,0,7);
	return 0;
}

  • 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
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/煮酒与君饮/article/detail/902696
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号