linklist_head.cpp

设计模式：工厂模式、单例模式的基本实现

/************************************
* Copyright (c) 2008,LDCI
*
* 文件名称： LinkList_Head.cpp
* 摘要：
*		使用 C 语言实现对链式存储结构的线性表（带头结点的单链表）
* 时间：
*		2008-5-4
* 作者：
*		左建华
************************************/
#include <stdlib.h>
#include <stdio.h>

typedef char DataType;
typedef struct stNode
{
	DataType data;
	struct stNode *next;
}ListNode;

typedef ListNode *LinkList;

//ListNode *p; // 定义一个结点的指针
//LinkList head; // 定义一个链表(头结点指针)


void Error(char* _pchMessage)
{
	fprintf(stderr, "Error: %s\n", _pchMessage);
}


///*
// 实现方式3：带结点的单链表
LinkList CreateList(void)
{
	char chTemp;
	LinkList pHead = (LinkList)malloc(sizeof(ListNode));
	
	ListNode *pNode, *pR;
	pR = pHead;

	while( (chTemp=getchar()) != '\n' )
	{
		pNode = (ListNode*)malloc(sizeof(ListNode));		// 生成新结点
		pNode->data = chTemp;								// 将读入的新数据存入新结点
		pR->next = pNode;									// 添加到结尾
		pR = pNode;											// 指向结尾的指针自身变化
	}

	pR->next = NULL;										//  全部创建完成后，将最后一个结点的next置空
		
	return pHead;

}
//*/

void ShowList(ListNode *pNode)
{
	while(pNode != NULL)
	{
		printf("%c, ", pNode->data);
		pNode = pNode->next;
	}
	printf("\n");
}

// 在带头结点的单链表_pHead中查找第_nIndex个结点，若找到(0<=_nIndex<=n), 则返回该结点位置，否则返回NULL
ListNode* GetNode(LinkList _pHead, int _nIndex)
{
	// 如果是查找第一个元素前面的节点，则直接将头指针返回
	if(_nIndex < 0)
	{
		return _pHead;
	}

	int nIndexTemp=0;
	ListNode *pNode;

	// 带头结点的单链表
	pNode = _pHead->next;

	// 开始查找
	while( pNode->next && nIndexTemp<_nIndex )
	{
		pNode = pNode->next;
		nIndexTemp++;
	}

	// 返回查找结果
	if(_nIndex==nIndexTemp)
	{
		return pNode;
	}
	else
	{
		return NULL;
	}
}

// 按值查找(带头结点的链表)
ListNode* LocateNode(LinkList _pHead, DataType _key)
{
	ListNode *pNode = _pHead->next;

	// 如果结点存在，并且值不是_key，就继续向下找
	while( pNode && pNode->data!= _key)
	{
		pNode = pNode->next;
	}
	
	// 若pNode为NULL则表示查找失败，否则pNode指向要找到的值为_key的结点
	return pNode; 
}	

//  插入
// 将值为_x的新结点插入到带头结点的单链表_pHead的第_nIndex个结点位置上
void InsertList(LinkList _pHead, DataType _x, int _nIndex)
{
	ListNode *pS, *pNode;
	
	pS = GetNode(_pHead, _nIndex-1);	// 查找_nIndex-1个结点，即要插入位置处的上一个结点
	
	if(pS == NULL)
	{
		Error("Error position.");
		return ;
	}

	pNode = (ListNode*)malloc(sizeof(ListNode));
	pNode->data = _x;
	pNode->next = pS->next;				// 让新节点指向原位置_nIndex出的结点
	pS->next = pNode;					// 将_nIndex-1结点的next指向新节点
}

// 删除带头结点链表_pHead上第_nIndex个结点
void DeleteList(LinkList _pHead, int _nIndex)
{
	ListNode *pS, *pR;

	pS = GetNode(_pHead, _nIndex-1);	// 查找_nIndex-1个结点，即要删除结点的上一个结点	
	
	if(pS==NULL || pS->next==NULL)		// 如果_nIndex出结点或_nIndex-1结点不存在，则报错
	{
		Error("Error position.");
		return ;	
	}
	
	pR = pS->next;						// 指向被删除结点

	pS->next = pR->next;				// 让被删除节点的上一个节点的next指针，指向被删除节点的下一个节点
	
	free(pR);							// 释放被删除的节点

}

// 释放链表中结点的空间
void DestroyList(ListNode* pNode)
{
	if(pNode == NULL)			// 1. 如果链表为空，直接返回
	{
		return ;
	}

	ListNode *pTemp = NULL;		// 2. 定义临时结点指针，保存被删除结点的 next 内容(即下一个结点的地址)
	
	while (pNode != NULL) 
	{
		pTemp = pNode->next;	// 3. 保存被删除结点的 next 内容
		free(pNode);			// 4. 删除结点
		pNode = pTemp;			// 5. 指向被保存的结点
	}
}

int main(int argc, char** argv)
{

	/* 
	LinkList pList = CreateList();
	ShowList(pList->next);

	if( LocateNode(pList, 'a') )
	{
		printf("find...\n");
	}
	else
	{
		printf("not find...\n");
	}
	*/


	// 显示带头结点的链表
//	ShowList(pList->next);


	/*
	// 测试GetNode()
	int nIndex = 2;
	ListNode *pNode = GetNode(pList, nIndex);

	if(pNode)
		printf("=== %c\n", pNode->data);
	else
		printf("Not find ...\n");
	*/



	/*

	LinkList pList = CreateList();
	ShowList(pList->next);

	// 测试Insert
	InsertList(pList, 'Z', 0);
	InsertList(pList, 'A', 1);
	InsertList(pList, 'X', 2);
	
	ShowList(pList->next);

	// 测试Delete
	DeleteList(pList, 0);
	DeleteList(pList, 0);
	DeleteList(pList, 3);

	ShowList(pList->next);


	DestroyList(pList);
	pList = NULL;
	
	*/




	return ;
}