학 빈 학 데이터 구조 (04) - 링크 [링크 의 조작]

# include 
# include 
# include 

typedef struct Node
{
	int data; //   
	struct Node * pNext; //   
}NODE, *PNODE; //NODE   struct Node    PNODE   struct Node *

//    
PNODE create_list(void);  //    
void traverse_list(PNODE pHead);  //    
bool is_empty(PNODE pHead);  //        
int length_list(PNODE);  //     
bool insert_list(PNODE pHead, int pos, int val);  // pHead       pos              ，      val，   pos    1  
bool delete_list(PNODE pHead, int pos, int * pVal);  //     pos   ，           pVal       ,    pos    1  
void sort_list(PNODE);  //       


int main(void)
{
	PNODE pHead = NULL; //    struct Node * pHead = NULL;
	int val;

	pHead = create_list();  //create_list()  ：          ，              pHead
	traverse_list(pHead);
	
	//insert_list(pHead, -4, 33);
	if ( delete_list(pHead, 4, &val) )
	{
		printf("    ，       : %d
", val);
	}
	else
	{
		printf("    !         !
");
	}

	traverse_list(pHead);
	
	//int len = length_list(pHead);
	//printf("      %d
", len);

	//sort_list(pHead);
	//traverse_list(pHead);
	
/*	if ( is_empty(pHead) )
		printf("    !
");
	else
		printf("    !
");
*/
	return 0;
}

PNODE create_list(void)
{
	int len;  //           
	int i;
	int val; //               

	//                
	PNODE pHead = (PNODE)malloc(sizeof(NODE));
	if (NULL == pHead)
	{
		printf("    ,     !
");
		exit(-1);
	}
	PNODE pTail = pHead;
	pTail->pNext = NULL;

	printf("                : len = ");
	scanf("%d", &len);
	
	for (i=0; iPNODE pNew = (PNODE)malloc(sizeof(NODE));
		if (NULL == pNew)
		{
			printf("    ,     !
");
			exit(-1);
		}
		pNew->data = val;
		pTail->pNext = pNew;
		pNew->pNext = NULL;
		pTail = pNew;
	}
	
	return pHead;
}

void traverse_list(PNODE pHead)
{
	PNODE p = pHead->pNext;

	while (NULL != p)
	{
		printf("%d  ", p->data);
		p = p->pNext;
	}
	printf("
");
	
	return;
}

bool is_empty(PNODE pHead)
{
	if (NULL == pHead->pNext)
		return true;
	else
		return false;
}

int length_list(PNODE pHead)
{
	PNODE p = pHead->pNext;
	int len = 0;

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

	return len;
}

void sort_list(PNODE pHead)
{
	int i, j, t;
	int len = length_list(pHead);
	PNODE p, q;
	
	for (i=0,p=pHead->pNext; ipNext)
	{
		for (j=i+1,q=p->pNext; jpNext)
		{
			if (p->data > q->data)  //       :  a[i] > a[j]
			{
				t = p->data;//       :  t = a[i];
				p->data = q->data; //       :  a[i] = a[j];
				q->data = t; //       :  a[j] = t;
			}
		}
	}

	return;
}

// pHead       pos              ，      val，   pos    1  
bool insert_list(PNODE pHead, int pos, int val)
{
	int i = 0;
	PNODE p = pHead;

	while (NULL!=p && ipNext;
		++i;
	}

	if (i>pos-1 || NULL==p)
		return false;

	//             p      pos-1   ,  pos-1          
	//      
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	if (NULL == pNew)
	{
		printf("        !
");
		exit(-1);
	}
	pNew->data = val;
	
	//       p     
	PNODE q = p->pNext;
	p->pNext = pNew;
	pNew->pNext = q;

	return true;
}


bool delete_list(PNODE pHead, int pos, int * pVal)
{
	int i = 0;
	PNODE p = pHead;

	while (NULL!=p->pNext && ipNext;
		++i;
	}

	if (i>pos-1 || NULL==p->pNext)
		return false;
	
	//             p      pos-1   ，   pos       
	PNODE q = p->pNext;  //q        
	*pVal = q->data;  

	//  p       
	p->pNext = p->pNext->pNext;
	
	//  q           
	free(q);
	q = NULL;
	
	return true;

}