[C++知识库]数据结构2

带头结点单链表

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MALLOC_OK 1
#define MALLOC_NO 0
#define CREATE_OK 1
#define CREATE_NO 0

typedef struct node
{
	int num;
	struct node *next;
}Node;

typedef Node * Hlink;

int is_malloc_ok(Hlink new_node)
{
	if(NULL == new_node)
	{
		printf("malloc fail!\n");
		return MALLOC_NO;
	}
	else
	{
		return MALLOC_OK;
	}
}

int create_node(Hlink *new_node)
{
	*new_node = (Hlink) malloc(sizeof(Node));

	if(MALLOC_OK == is_malloc_ok(*new_node))
	{
		return CREATE_OK;
	}
	else
	{
		return CREATE_NO;
	}
}

void create_hlink(Hlink *head)
{
	if(CREATE_OK == create_node(head))
	{
		(*head)->next = NULL;
	}

	else
	{
		return;
	}
}

void insert_node_head(Hlink head,Hlink new_node)
{
	new_node->next = head->next;
	head->next = new_node;
}

void insert_node_tail(Hlink head,Hlink new_node)
{
	Hlink p = NULL;
	p = head;
	while(p->next != NULL)
	{
		p = p->next;
	}

	p->next = new_node;
	new_node->next = NULL;
}

void insert_node_mid_before(Hlink head,Hlink new_node,int loc)
{
	Hlink p,q = NULL;
	q = head;
	p = head->next;
	while(p != NULL && p->num != loc)
	{
		q = p;
		p = p->next;
	}

	q->next = new_node;
	new_node->next = p;
	
}

void insert_node_mid_after(Hlink head,Hlink new_node,int loc)
{
	Hlink p = NULL;
	p = head;
	while(p != NULL && p->num != loc)
	{
		p = p->next;
	}

	new_node->next = p->next;
	p->next = new_node;
}



void display_hlink(Hlink head)
{
	Hlink p = NULL;
	
	if(NULL == head)
	{
		printf("no such hlink!\n");
	}

	else if(NULL == head->next)
	{
		printf("The hlink is empty!\n");
	}

	else
	{
		p = head->next;

		while(p != NULL)
		{
			printf("%d ",p->num);
			p = p->next;
		}
	}
}

void make_empty(Hlink head)
{
	Hlink p = NULL;
	p = head->next;
	while(p != NULL)
	{
		head->next = p->next;
		free(p);
		p = head->next;
	}
}

void release_hlink(Hlink *head)
{
	Hlink p = NULL;
	p = *head;
	while(p != NULL)
	{
		*head = (*head)->next;
		free(p);
		p = *head;
	}
	printf("release hlink ok!\n");
}

void insert_node_sort(Hlink head,Hlink new_node)
{
	Hlink p,q = NULL;
	q = head;
	p = head->next;
	while(p != NULL && p->num < new_node->num)
	{
		q = p;
		p = p->next;
	}

	q->next = new_node;
	new_node->next = p;
	
}

Hlink find_node(Hlink head,int num)
{
	Hlink p = NULL;
	p = head->next;
	while(p != NULL && p->num != num)
	{
		p = p->next;
	}
	
	if(p == NULL)
	{
		return NULL;
	}
	else
	{
		return p;	
	}
}

void reverse_hlink(Hlink head)
{
	Hlink p,q;
	p = head->next;
	head->next = NULL;
	while(p != NULL)
	{
		q = p;
		p = p->next;
		q->next = head->next;
		head->next = q;
	}
}

void delete_node(Hlink head,int num)
{
	Hlink p,q = NULL;
	q = head;
	p = head->next;
	while(p != NULL && p->num != num)
	{
		q = p;
		p = p->next;
	}

	if(NULL == p)
	{
		printf("no such node!\n");
	}
	else
	{
		q->next = p->next;
		free(p);
	}
}

int Length_link(Hlink head)
{
	Hlink p = NULL;
	p = head;
	int count = 0;
	while(p != NULL)
	{
		p = p->next;
		count++;
	}
	return count;
}


int main(int argc, const char *argv[])
{
	Hlink head = NULL;
	Hlink new_node = NULL;
	int i;
	int loc;
	int num,num1;
	Hlink p = NULL;
	srand((unsigned)time(NULL));

    create_hlink(&head);

	for(i = 0; i < 10; i++)
	{
		if(CREATE_OK == create_node(&new_node))
		{
		//	new_node->num = i + 1;
			new_node->num = rand() % 100;

			insert_node_sort(head,new_node);

		//	insert_node_head(head,new_node);

	   //	insert_node_tail(head,new_node);
		}
	}
    
	display_hlink(head);
	printf("\n");
//	reverse_hlink(head);
//	display_hlink(head);
//	printf("\n");
	//printf("The hlink length is:%d\n",Length_link(head));
	printf("input you want to find num:");
 	scanf("%d",&num1);
	p = find_node(head,num1);
	if(p != NULL)
	{
		printf("%p\n",p);
		printf("%d",p->num);
	}
	else
	{
		printf("The num does not exit!\n");
	}
	printf("\n");
//	printf("input you want to delete num:");
//	scanf("%d",&num);
//	delete_node(head,num);
//	display_hlink(head);
//	printf("\n");

#if 0
	printf("input location:");
	scanf("%d",&loc);
	if(CREATE_OK == create_node(&new_node))
	{
		printf("input num:");
		scanf("%d",&new_node->num);
	//	insert_node_mid_before(head,new_node,loc);
		insert_node_mid_after(head,new_node,loc);
	}

	display_hlink(head);

	printf("\n");

//	release_hlink(&head);
#endif

//	make_empty(head);

//	display_hlink(head);
//	printf("\n");


	return 0;
}

带头逆序?

太牛逼了！

void reverse_hlink(Hlink head)
{
	Hlink p,q;
	p = head->next;
	head->next = NULL;
	while(p != NULL)
	{
		q = p;
		p = p->next;
		q->next = head->next;
		head->next = q;
	}
}