02 数据结构之链表

admin • 2024-03-14 22:08 • 物联网

阅读引言：本文只提供关于我在复习过程中实现的关于链表的代码

/* link_list.h */
#ifndef _LINK_LIST_H_
#define _LINK_LIST_H_

/**********************************************
 *Author: Hewei
 *Date: 2024-3-3
 *Brife: link list some operator method
 *
 *
 *arithmetic evaluate stadend
 *1.validty
 *2.time
 *3.space
 *4.read
 *
 * ********************************************/

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

#define DEBUG(msg) 
	printf("-----%s-----%s------n", __func__, msg);

typedef int data_t;
typedef struct node{
	data_t data;
	struct node *next;            /* 启用的结构体必须有一个结构体名 */
}list_node, *list_link;



/* link list base operator */
list_link list_create();
void list_free(list_link H);
int list_tail_insert(list_link H, data_t value);
void list_show(list_link H);
list_link list_find_pos(list_link H, int positon);
int list_positon_insert(list_link H, data_t value, int positon);
int list_delete_positon(list_link H, int positon);
int list_delete_allnode(list_link H);
int list_reverse(list_link H);
list_link list_adjoin_max(list_link H, data_t *max_value);
int list_oderly_merge(list_link H1, list_link H2);
int list_sort_ascdending(list_link H);


/*link list advance operator */
list_link list_site_reverse(list_link H);
void list_show_nohead(list_link H);
int list_has_cycle(list_link H);
size_t list_length(list_link H); 
list_link find_public_node(list_link H1, list_link H2);
list_link find_rear_knode_normal(list_link H, int rear_num);
list_link find_rear_knode_advance(list_link H, int rear_num);
list_link find_middle_node(list_link H);
int delete_repeate_element(list_link H);

#endif

/* link_list.c */
#include "link_list.h"


/*
 *brife: create a link_list, return the head node of linklist
 *param:none
 *
 * */
list_link list_create()
{
	list_link H = (list_link)malloc(sizeof(list_node));
	if(H == NULL) {
		DEBUG("H equal NULLn");	
		return NULL;
	}
	
	H->data = 0;        /* 链表的头节点的数据域为0 */
	H->next = NULL;

	return H;
}



/*brife: free a linklist
 *param: address fo linklist 
 *return: none
 *
 * */
void list_free(list_link H)
{
	list_link p;
	if(H == NULL) {
		DEBUG("H equal NULLn");	
		return ;
	}
	 
	while(H != NULL) {
		p = H;
		H = p->next;
		printf("free: %d ", p->data);
		free(p);
	}
	puts("");
}


/*brife: insert a value to link_list, from tail
 *param: list_link
 *param: value of insert
 *return: 0 succese -1 failed
 * */
int list_tail_insert(list_link H, data_t value) 
{
	if(H == NULL) {
		DEBUG("H equal NULLn");	
		return -1;
	}

	list_link p = H;
	list_link tmp = (list_link)malloc(sizeof(list_node));
	if(tmp == NULL) {
		DEBUG("tmp node malloc is failed!n");
		return -1;
	}

	tmp->data = value;
	tmp->next = NULL;

	while(p->next != NULL) {
		p = p->next;
	}

	p->next = tmp;

	return 0;
}


/*brife: foreach a linklist
 *param: address of linklist
 *return: none
 *
 * */
void list_show(list_link H)
{
	if(H == NULL) {
		DEBUG("H equal NULLn");	
		return ;
	}
	list_link tmp = H;

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

	puts("");
}


/*brife: return assign pos address of node 
 *
 * */
list_link list_find_pos(list_link H, int positon)
{
	list_link p;

	if(H == NULL) {
		DEBUG("param H is NULL!n");
		return NULL;
	}
	
	p = H;

	if(positon < 0) {
		DEBUG("---1---param positon is invalid!n");
		return NULL;
	}

	while(positon > 0) {
		p = p->next;
		if(p == NULL) {
			DEBUG("---2---param positon is invalid!n");
			return NULL;
		}
		positon--;
	}
	
	return p;
}


/*brife: assign positon insert
 *
 * */
int list_positon_insert(list_link H, data_t value, int positon)
{
	list_link p, q;
	if(H == NULL) {
		DEBUG("param H is NULL!n");
		return -1;
	}

	/* new node */
	q = (list_link)malloc(sizeof(list_node));
	if(q == NULL) {
		DEBUG("malloc failed!n");
		return -1;
	}
	q->data = value;
	q->next = NULL;
	
	/* locate positon */
	p = H;
	while(positon - 1 > 0) {
		p = p->next;
		if(p == NULL) {
			DEBUG("param positon is invalid!n");
			return -1;
		}
		positon--;
	}

	/* 先保存后节点的地址 */
	q->next = p->next;
	p->next = q;

	return 0;
	
}


/*brife: delete link list specify node, base positon
 *
 * */
int list_delete_positon(list_link H, int positon)
{
	list_link p, q;
	if(H == NULL) {
		DEBUG("param H is NULL!n");
		return -1;
	}	

	p = H;
	/*locate prior node*/
	while(positon - 1 > 0) {
		p = p->next;
		if(p == NULL) {
			DEBUG("delete positon is invalid!n");
			return -1;
		}
		positon--;
	}
	
	q = p->next;

	p->next = q->next;
	q->data = 0;
	free(q);

	return 0;

}


/*brife: delete all node, but except head node 
 *
 * */
int list_delete_allnode(list_link H)
{
	if(H == NULL) {
		DEBUG("param H is NULL!n");
		return -1;
	}	
	
	list_link p = H->next, q;
	while(p != NULL) {
		q = p;
		p = p->next;
		free(q);
	}

	return 0;
}


/*brife: link list reverse
 *
 * */
int list_reverse(list_link H)
{
	if(H == NULL) {
		DEBUG("param H is NULL!n");
		return -1;
	}

	if(H->next == NULL || H->next->next == NULL) {
		DEBUG("link list only head node or a data node!n");
		return -1;
	}

	list_link p = H->next->next, q;
	H->next->next = NULL;

	while(p != NULL) {
		q = p;
		p = p->next;
		q->next = H->next;
		H->next = q;
	}

	return 0;
	
}


/*brife: return address of adjoin node max value, and max_value
 *
 * */
list_link list_adjoin_max(list_link H, data_t *max)
{
	if(H == NULL) {
		DEBUG("param H is NULL!n");
		return NULL;
	}
	
	if(H->next == NULL || H->next->next == NULL) {
		DEBUG("no adjoin max value!n");
		return NULL;
	}

	data_t max_value = 0;	
	list_link p, q;
	p = H->next;
	q = p->next;
	max_value = p->data + q->data;

	while(q != NULL) {
		if(p->data + q->data > max_value) {
			max_value = p->data + q->data;
		}

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

	*max = max_value;

	return p;
}


/*brife: two oderly linklist merge
 *
 * */
int list_oderly_merge(list_link H1, list_link H2)
{                                       
	if(H1 == NULL || H2 == NULL) {
		DEBUG("param H1 or H2 is NULL!n");	
		return -1;
	}	

	if(H1->next == NULL || H2->next == NULL) {
		DEBUG("data node too few!n");
		return -1;
	} 

	list_link p, q, r;
	p = H1->next;
	q = H2->next;
	r = H1;
	H1->next = NULL;
	H2->next = NULL;

	while(p != NULL && q != NULL) {
		if(p->data > q->data) {
			r->next = q;
			q = q->next;
			r = r->next;
			r->next = NULL;
		} else {
			r->next = p;
			p = p->next;
			r = r->next;
			r->next = NULL;
		}
	}

	/* 一定有一个先到尾部 */
	if(p == NULL) {
		r->next = q;
	} else {
		r->next = p;
	}
	
	return 0;
}


/*
*  brife： insert sort
**/
int list_sort_ascdending(list_link H)
{
	if(H == NULL) {
		DEBUG("param H is NULL!n");
		return -1;
	}

	list_link p, q, r;
	p = H->next;
	H->next = NULL;

	while(p != NULL) {
		q = p;
		r = H;
		p = p->next;

		while(r->next != NULL && r->next->data < q->data)
			r = r->next;
		q->next = r->next;
		r->next = q;
	}

	return 0;
}




/********************************************************************************/
/**          link list some advance method                    **/
/********************************************************************************/
/*brife: on site reverse
 *return: new address of link list
 *
 * */
list_link list_site_reverse(list_link H)
{
	if(H == NULL || H->next == NULL) {
		DEBUG("param is NULL or can not reverse because node too few!n");
		return NULL;
	}

	list_link p, q, r;

	p = H->next;
	q = p->next;
	r = q->next;
	p->next = NULL;

	while(r != NULL) {
		q->next = p;
		p = q;
		q = r;
		r = q->next;
	}

	q->next = p;

	return q;
}


void list_show_nohead(list_link H)
{
	if(H == NULL) {
		DEBUG("param H is NULL!n");
		return ;
	}

	list_link p = H;
	while(p != NULL) {
		printf("%d ", p->data);
		p = p->next;
	}
	puts("");
	
}


/*brife: judge a link list has cycle
 *return 0:have -1 no have
 *
 * */
int list_has_cycle(list_link H)
{
	if(H == NULL) {
		DEBUG("param H is NULL!n");
		return -1;
	}

	list_link fast = H, slow = H;
	while(fast != NULL) {
		slow = slow->next;
		if(fast->next == NULL) {
			return -1;
		}
		fast = fast->next->next;

		if(fast == slow) {
			return 0;
		}
	}

	return -1;
}


/*brife: get link list length, contain head node
 *
 * */
size_t list_length(list_link H)
{
	if(H == NULL) {
		DEBUG("param H is NULL!n");
		return -1;
	}

	list_link p = H;
	unsigned int len = 0;

	while(p != NULL) {
		len++;
		p = p->next;
	}

	return len;
}

/*brife: find two public node of link list 
 *
 * */
list_link find_public_node(list_link H1, list_link H2)
{
	if(H1 == NULL || H2 == NULL) {
		DEBUG("param is NULL!n");
		return NULL;
	}

	size_t len1, len2, len_differ;
	len1 = list_length(H1);
	len2 = list_length(H2);

	list_link p = H1, q = H2;

	if(len1 > len2) {
		len_differ = len1 - len2;
		while(p != NULL && len_differ > 0) {
			p = p->next;
			len_differ--;
		}
	} else {
		len_differ = len2 - len1;
		while(q != NULL && len_differ > 0) {
			q = q->next;
			len_differ--;
		}
	}
	
	while(p != NULL && q != NULL) {
		if(p == q) {
			return p;
		}
		p = p->next;
		q = q->next;
	}

	return NULL;
}

/*brife: find list rear K node address
 *
 * */
list_link find_rear_knode_normal(list_link H, int rear_num)
{
	if(H == NULL) {
		DEBUG("param is NULL!n");
		return NULL;
	}

	size_t len = list_length(H);
	int i = 0;
	list_link p = H;

	for(;i < len - rear_num; i++) {
		p = p->next;	
	}

	return p;
}


/*brife: find list rear K node address, advance verssion
 *
 * */
list_link find_rear_knode_advance(list_link H, int rear_num)
{
	if(H == NULL) {
		DEBUG("param is NULL!n");
		return NULL;
	}

	list_link p = H, q = H;
	while(rear_num > 0) {
		q = q->next;
		rear_num--;
	}

	while(q->next != NULL) {
		p = p->next;
		q = q->next;
	}

	return p;
}


/*brife: find middle node of link list 
 *
 * */
list_link find_middle_node(list_link H)
{
	if(H == NULL) {
		DEBUG("param is NULL!n");
		return NULL;
	}

	if(H->next == NULL) {
		DEBUG("only head node!n");
		return NULL;
	}

	list_link slow = H, fast = H;
	while(fast->next != NULL) {
		slow = slow->next;
		if(fast->next->next == NULL) {
			return slow;
		}
		fast = fast->next->next;
	}

	return slow;
}



/*brife: delete link list repeate element
 *
 * */
int delete_repeate_element(list_link H)
{
	if(H == NULL) {
		DEBUG("param is NULL!n");
		return -1;
	}

	if(H->next == NULL || H->next->next == NULL) {
		DEBUG("only head node or a data node!n");
		return -1;
	}

	list_link p = H->next, q;

	while(p != NULL) {
		while(p->next != NULL && p->data == p->next->data) {
			q = p->next;
			p->next = q->next;
			free(q);
		}
		p = p->next;
	}


	return 0;
}

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。

THE END

数据结构链表

二维码

Rust 语言的 for 循环用法

< <上一篇

rust的 || 是什么，怎么使用?

下一篇>>

搜索内容

02 数据结构之链表

最新文章

分类

标签云