데이터 구조 - 선형 표 의 체인 구조 (C 언어)

체인 저장: 노드 의 방식 으로 저장 합 니 다. 노드 는 데이터 필드 와 포인터 필드 를 포함 하고 포인터 필드 의 바늘 은 다음 노드 의 저장 위 치 를 가리 키 며 데이터 의 저장 은 연속 되 지 않 을 수 있 습 니 다.헤드 포인터 는 링크 의 색인 으로 링크 의 조작 을 편리 하 게 하고 헤드 포인터 가 머리 노드 를 가리 키 며 머리 노드 는 첫 번 째 노드 를 가리 키 며 이런 식 으로 꼬리 노드 까지 유추 합 니 다.
다음은 원본 프로그램 입 니 다.
함수 선언

#ifndef List_H
#define List_H

typedef struct Node *PNode;//      
typedef int Item;//      

typedef struct Node//      
{
	Item data;//   
	PNode next;//   
}node;

typedef PNode Position;
typedef PNode List;

/**    **/
/***     ，       ***/
List Creat_Empty(List);

/***        ***/
int Is_Empty(List);

/***    ，      ***/
List Make_List();

/***      ***/
List Invert(List);

/***        ***/
int Is_Last(Position);

/***       ***/
int Length(List);

/***    ***/
void Traverse_List(List); 

/***             ***/
void Insert(Item,List,Position);

/***           ，       ***/
int Search(Item,List);

/***           ，            ***/
Position Search_Previous(Item,List);

/***           ，            ***/
Position Search_Next(Item,List); 

/***  P     ***/
Position Advance(Position P);

/***           ***/
void Delete(Item,List);

/***              ***/
void Delete_List(List); 

/***  P      ***/
int Get_Item(Position P);
#endif

함수 정의

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include"List.h"

/**    **/
/***     ，       ***/
List Creat_Empty(List L)
{
	L=(PNode)malloc(sizeof(node));
	L->next=NULL;
	L->data=0;
	return L;
}

/***        ***/
int Is_Empty(List L)
{
	return L->next==NULL;
	/*
	if(NULL==L->next)
		return 1;
	else
		return 0;
	*/
}

/***    ，     ***/
List Make_List()
{
	int val;
	PNode pHead =(PNode)malloc(sizeof(node));  
	PNode pCurrent = pHead;  
	pCurrent->next = NULL;
	if(NULL==pHead)
		{
			printf("Malloc the list is failed.");
			exit(1);
		}
	printf("Input the first data:");
	while(scanf("%d",&val)==1)
		{
			PNode pNew=(PNode)malloc(sizeof(node));
			if(NULL==pNew)
			{
				printf("Malloc the pNew is failed.");
				exit(1);
			}
			pNew->data=val;
			pCurrent->next=pNew;
			pNew->next=NULL;
			pCurrent=pNew;
			printf("Please input the next data:");
		}
	return pHead;
}

/***       ***/
List Invert(List Head)
{
    PNode middle, trail;
    middle = NULL;

    PNode temp = Head->next;
    while(temp)
    {
        trail = middle;
        middle = temp;
        temp = temp->next;
        middle->next = trail;
    }
    Head->next = middle;
    return Head;
}


/***        ***/
int Is_Last(Position P)
{
	return P->next==NULL;
}
/***       ***/
int Length(List L)
{
	int len=0;
	PNode PCurrent=L->next;
	while(NULL!=PCurrent)
	{
		len++;
		PCurrent=PCurrent->next;
	}
	return len;
}

/***    ***/
void Traverse_List(List L)
{
	PNode PCurrent=L->next;
	printf("The data of list are:
");
	while(NULL!=PCurrent)
	{
		printf("%d   ",PCurrent->data);
		PCurrent=PCurrent->next;
	}
	printf("
");
}

/***             ***/
void Insert(Item val,List L,Position P)
{
	PNode temp;
	temp=(PNode)malloc(sizeof(node));
	if(NULL==temp)
		exit(0);
	temp->data=val;
	temp->next=P->next;
	P->next=temp;
}

/***           ，       ***/
int Search(Item val,List L)
{
	Position P;
	P=L->next;
	if(P!=NULL && P->data !=val)
		P=P->next;
	return P->data;
}

/***           ，            ***/
Position Search_Previous(Item val,List L)
{
	Position P;
	P=L;
	if(P->next!=NULL && P->next->data!=val)
		P=P->next;
	return P;
}

/***           ，            ***/
Position Search_Next(Item val,List L)
{
	Position P;
	P=L;
	if(P!=NULL && P->data!=val)
		P=P->next;
	return P;
}
/*
    P       
*/  
Position Advance(Position P)  
{  
    if(P!=NULL)  
    return P->next;  
}

/***           ***/
void Delete(Item val,List L)
{
	Position P, temp;
	P=Search_Previous(val,L);
	if(!Is_Last(P))
	{
		temp=P->next;
		P->next=temp->next;
		free(temp);
	}

}

/***    L          ***/
void Delete_List(List L)
{
	Position P, temp;
	P=L->next;
	L->next=NULL;
	while(P!=NULL)
	{
		temp=P->next;
		free(P);
		P=temp;
	}
}

/***  P        ****/
int Get_Item(Position P)  
{  
    if(P!=NULL)  
    return P->data;  
} 

테스트 프로그램

#include<stdio.h>
#include<stdlib.h>
#include"List.h"
#define NUMBER 5
#define N 3




int main(void)
{
List list;
Position P;
int len,val;
list=NULL;
List L=NULL;

L=Creat_Empty(L);//     
printf("The empty of list is created.
");
if(Is_Empty(L))//        
printf("The list is empty.
");


list=Make_List();//           
Traverse_List(list);//     

list=Invert(list);//    
Traverse_List(list);//     

len=Length(list);//     
if(!Is_Empty(list))
printf("The length of list is:%d
",len);


P=list;
Insert(NUMBER,list,P);//         
P= Advance(P);//  P      
if(P)
printf("Insert the new data of %d is successed
",Get_Item(P));
else
printf("Insert the data of %d is failed.
",NUMBER);
Traverse_List(list);//     


val=Search(N,list);//            
if(val==N)
printf("Search the data of %d is successed.
",N);
else
printf("Search the data of %d is failed.
",N);


Delete(NUMBER,list);//     
Traverse_List(list);//     


Delete_List(list);//    
if(Is_Empty(list))
printf("The list is destroied.");
return 0;
}