データ構造のチェーン表(ヘッドノードチェーン表)

ヘッドノードチェーン表とは、先頭ノードのチェーン表を指します.ここで紹介したのはシングルチェーン表です.比較的にヘッドポインタチェーンテーブルと比べて、利点は挿入削除は空テーブルの問題を考慮する必要がなく、操作はヘッドポインタを変更する必要がなく、二次ポインタを転送しないことです.使うのが便利で、広く使われています.
以下はヘッドチェーンのいくつかの操作の実現についてです.(ヘッダファイルとソースファイルを含む)
ヘッドファイル:LinkList.h

#ifndef __LINKLIST_H__
#define __LINKLIST_H__
#define TRUE 1
#define FALSE 0

typedef int LinkData;
typedef struct _node
{
	LinkData data;
	struct _node *next;
}LinkList;

//    
LinkList *Create_List();

//   
int	Insert_Head(LinkList *h,LinkData data);

//   
int	Insert_Last(LinkList *h,LinkData data);

//  Pos      ， 1  ，   0   ，     
int	Insert_Pos(LinkList *h,int Pos,LinkData data);

//   Pos   ， 1  ，   0   ，     
int Delete_Pos(LinkList *h,int Pos);

//    
int Reverse_List(LinkList *h);

//       
int Delete_Data(LinkList *h, LinkData data);

//     :   ,        
int Find_Element(LinkList* h, LinkData data, int *x);

//          ：      
int Get_Element(LinkList *h, int Pos, LinkData *data);

//      
int Get_Len(LinkList *h,int *len);

//    
int Order_List(LinkList *h)

//       
int Clean_List(LinkList *h);

//     
int Destroy(LinkList *h);

//    
void Display(LinkList *h);

#endif

ソースファイル:LinkList.c

#include 
#include 
#include "LinkList.h"

//    
LinkList *Create_List()
{
	LinkList *head = (LinkList *)malloc(sizeof(LinkList)/sizeof(char));
	if (head == NULL)
	{
		return NULL;
	}
	head -> next = NULL;
	return head;
}

//   
int	Insert_Last(LinkList *h,LinkData data)
{
	if (h == NULL)
	{
		return FALSE;
	}
	LinkList * node = (LinkList *)malloc(sizeof(LinkList)/sizeof(char));
	if (node == NULL)
	{
		return FALSE;
	}
	node -> data = data;
	node -> next = NULL;
	LinkList *tmp = h;
	while (tmp -> next)
	{
		tmp = tmp -> next;
	}
	tmp -> next = node;
	return TRUE;
}

//   
int	Insert_Head(LinkList *h,LinkData data)
{
	if (h == NULL)
	{
		return FALSE;
	}
	LinkList * node = (LinkList *)malloc(sizeof(LinkList)/sizeof(char));
	if (node == NULL)
	{
		return FALSE;
	}
	node -> data = data;
	node -> next = h -> next;
	h -> next = node;
	return TRUE;
}

//  Pos      ， 1  ，   0   ，     
int	Insert_Pos(LinkList *h,int Pos,LinkData data)
{
	if (h == NULL || Pos < 1)
	{
		return FALSE;
	}
	int i;
	LinkList *tmp = h;
	for (i = 0;i < Pos -1;i++)
	{
		tmp = tmp -> next;
		if(tmp == NULL)
		{
			printf ("      
");
			return FALSE;
		}
	}
	LinkList * node = (LinkList *)malloc(sizeof(LinkList)/sizeof(char));
	if (node == NULL)
	{
		return FALSE;
	}
	node -> data = data;
	node -> next = tmp -> next;
	tmp -> next = node;
	return TRUE;
}

//   Pos   ， 1  ，   0   ，     
int Delete_Pos(LinkList *h,int Pos)
{
	if (h == NULL || Pos < 1)
	{
		return FALSE;
	}
	int i;
	LinkList *tmp = h;
	for (i = 0;i < Pos -1;i++)
	{
		tmp = tmp -> next;
		if(tmp -> next == NULL)
		{
			printf ("      
");
			return FALSE;
		}
	}
	LinkList *p = tmp -> next;
	tmp -> next = p -> next;
	free (p);
	return TRUE;
}

//    
int Reverse_List(LinkList *h)
{
	if(h == NULL || h->next == NULL || h->next->next == NULL)
	{
		return FALSE;
	}
	LinkList *pre = h -> next;
	LinkList *cur = h -> next -> next;
	LinkList *tmp;
	while (cur)
	{
		tmp = cur -> next;
		cur -> next = pre;
		pre = cur;
		cur = tmp;
	}
	h -> next -> next = NULL;
	h -> next = pre;
	return  TRUE;;
}

//       
int Delete_Data(LinkList *h, LinkData data)
{
	if(h == NULL)
	{
		return FALSE;
	}
	LinkList *tmp = h;
	while (tmp -> next)
	{
		if (tmp -> next -> data == data)
		{
			LinkList *p = tmp -> next;
			tmp -> next = p -> next;
			free (p);
			return TRUE;
		}
		tmp = tmp -> next;
	}
	printf ("    ，      
");
	return FALSE;
}

//     :   ,        
int Find_Element(LinkList* h, LinkData data, int *x)
{
	if(h == NULL || x == NULL)
	{
		return FALSE;
	}
	LinkList *tmp = h -> next;
	int count = 1;
	while (tmp)
	{
		if (tmp -> data == data)
		{
			*x = count;
			return TRUE;
		}
		tmp = tmp -> next;
		count++;
	}
	printf ("    ，      
");
	return FALSE;
}

//          ：      
int Get_Element(LinkList *h, int Pos, LinkData *data)
{
	if(h == NULL || Pos < 1 ||data == NULL)
	{
		return FALSE;
	}
	int i;
	LinkList *tmp = h;
	for (i = 0;i < Pos;i++)
	{
		tmp = tmp -> next;
		if(tmp == NULL)
		{
			printf ("      
");
			return FALSE;
		}
	}
	*data = tmp -> data;
	return TRUE;
}

//      
int Get_Len(LinkList *h,int *len)
{
	if(h == NULL || len == NULL)
	{
		return FALSE;
	}
	int count = 0;
	LinkList *tmp = h;
	while(tmp -> next)
	{
		tmp = tmp -> next;
		count++;
	}
	*len = count;
	return TRUE;
}

//    
int Order_List(LinkList *h)
{
	if(h == NULL || h -> next == NULL || h -> next -> next == NULL)
	{
		return FALSE;
	}
	int len;
	Get_Len(h,&len);
	LinkList * tmp = (LinkList *)malloc(sizeof(LinkList)/sizeof(char));
	if (tmp == NULL)
	{
		return FALSE;
	}
	int i,j;
	for (i = 1;i < len;i++)
	{
		LinkList* min = h -> next;
		LinkList* max = h -> next -> next;
		for (j = 1;j < len - i + 1;j++)
		{
			if (min -> data > max -> data)
			{
				tmp -> data = min -> data;
				min -> data = max -> data;
				max -> data = tmp -> data;
			}
			min = min -> next;
			max = max -> next;
		}
	}
	free (tmp);
	return TRUE;
}

//       
int Clean_List(LinkList *h)
{
	if(h == NULL)
	{
		return FALSE;
	}
	LinkList *tmp = h;
	while (tmp -> next)
	{
		Delete_Pos(h,1);
	}
	return TRUE;
}

//     
int Destroy(LinkList *h)
{
	if(h == NULL)
	{
		return FALSE;
	}
	Clean_List(h);
	free (h);
	return TRUE;
}

//    
void Display(LinkList *h)
{
	if (h == NULL)
	{
		printf ("     
");
		return;
	}
	int count = 0;
	LinkList *tmp = h -> next;
	while(tmp)
	{
		if(count++ % 4 == 0)
		{
			printf ("
");
			
		}
		printf ("%8d",tmp -> data);
		tmp = tmp -> next;
	}
	printf ("
");
}

ヘッドチェーンの機能については、みんなで一緒に実現できます.