鏈表——基於C語言

最近複習了C語言的一些知識，使用C語言實現了數據結構中的鏈表。

下面 下麪是Main.c檔案：

#include "LinkList.h"
#include <stdio.h>

int main()
{
	LinkList *list = LinkListCreate();
 
 	if(list != NULL)
 	{
  		int i;
  		printf("len = %d\n\n", LinkListLength(list));
  
  		for(i = 0; i < 10; i++)
  		{
   			LinkListInsert(list, LinkListLength(list), i);
  		}
  
  		printf("len = %d\n\n", LinkListLength(list));
		
		 for(i = 0; i < 5; i++)
  		{
   			LinkListDelete(list, 0, NULL);
  		}
  
  		printf("len = %d\n\n", LinkListLength(list));
  
  		i = 0;
  		printf("開始列印鏈表：\n");
  		for(LinkListMove(list, 0); !LinkListEnd(list); LinkListNext(list), i++)
  		{
  			printf("list[%d] = %d\n", i, LinkListCurrent(list));
  		}
  
  		list = LinkListDestroy(list);
	}

	return 0;
}

下面 下麪是LinkList.h檔案

#ifndef __LINKLIST_H__
#define __LINKLIST_H__

typedef int DataType;

#define deBug() printf("File = %s\nLine = %d\n", __FILE__, __LINE__)

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

#ifndef __cplusplus
 typedef int Bool;
 #define true 1
 #define false 0
#else
 typedef bool Bool;
#endif

#define MALLOC(type, size) (type*)malloc(sizeof(type) * size)
#define FREE(p)    (free(p), p = NULL)

#define STRUCT(type)  typedef struct __struct##type type;\
      struct __struct##type

STRUCT(LLNode)
{
 	DataType data;
 	LLNode *next;
};

STRUCT(LinkList)
{
 	int len;
 	LLNode *next;
 	LLNode *m_current;
};

LinkList* LinkListCreate(void);
LinkList* LinkListDestroy(LinkList *list);
int LinkListLength(LinkList *list);
Bool LinkListInsert(LinkList *list, int i, DataType data);
Bool LinkListDelete(LinkList *list, int i, DataType *data);
int LinkListFind(LinkList *list, DataType data); 
Bool LinkListGet(LinkList *list, int i, DataType *data);
LLNode* LinkListMove(LinkList *list, int i);
Bool LinkListEnd(LinkList *list);
void LinkListNext(LinkList *list);
DataType LinkListCurrent(LinkList *list);

#endif

下面 下麪是LinkList.c檔案

#include "LinkList.h"


LinkList* LinkListCreate(void)  //O(1)
{
 	LinkList *list = MALLOC(LinkList, 1);
 
 	if(list != NULL)
 	{
  		list->len = 0;
  		list->next = NULL;
  		list->m_current = NULL;
 	}
 
 	return list;
}

LinkList* LinkListDestroy(LinkList *list)	//O(n)
{
 	if(list != NULL)
 	{
  		while(list->next != NULL)
  		{
   			LinkListDelete(list, 0, NULL);
  		}
  
  		FREE(list);
 	}
 
 return NULL;
}

int LinkListLength(LinkList *list) //O(1)
{
 	return (list != NULL) ? list->len : -1;
}

Bool LinkListInsert(LinkList *list, int i, DataType data)  //O(n)
{
 	Bool ret = (list != NULL) && (i >= 0) && (i <= LinkListLength(list));
 
 	if(ret)
 	{
  		LLNode *node = MALLOC(LLNode, 1);
  
 		if(node != NULL)
  		{   
   			if(0 == i)
   			{
   		 		node->data = data;
    				node->next = list->next;
    
    				list->next = node;
   			}
   			else
   			{
    				LLNode *pre = LinkListMove(list, i - 1);
    
    				node->data = data;
    				node->next = pre->next;
    
    				pre->next = node;
   			}
   
   			list->len++;
  		}
  		else
  		{
   			ret = false;
  		}
 	}
 
 	return ret;
}

Bool LinkListDelete(LinkList *list, int i, DataType* data) //O(n)
{
 	Bool ret = (i >= 0) && (i < LinkListLength(list));
 
 	if(ret)
 	{
  		LLNode *node = list->next;
  
  		if(0 == i)
  		{
   			if(data) *data = node->data;
   			list->next = node->next;
  		}
  		else
  		{
  			LLNode *pre = LinkListMove(list, i - 1);
   
   			node = pre->next;
   
   			if(data) *data = node->data;
   
   			pre->next = node->next; 
  		}
  
  		free(node);
  		list->len--;
 	}
 
 	return ret;
}

Bool LinkListGet(LinkList *list, int i, DataType* data) //O(n)
{
 	return ((data != NULL) && (i >= 0) && (i < LinkListLength(list))) ? (*data = LinkListMove(list, i)->data, true) : false;
}

//下面 下麪四個配合使用用於遍歷鏈表，時間複雜度爲O(n)
LLNode* LinkListMove(LinkList *list, int i)
{
 	LLNode *ret = NULL;
 
 	list->m_current = NULL;
 
 	if((list != NULL) && (i >= 0) && (i < LinkListLength(list)))
 	{  
  		LLNode *node = list->next;
  
  		if(node != NULL)
  		{
   			int j;
   
   			for(j = 0; j < i; j++)
   			{
   				node = node->next; 
   			}
   
  			ret = node;
   			list->m_current = node;    
  		} 
 	}
 
 return ret;
}

Bool LinkListEnd(LinkList *list)
{
 	return (list != NULL) ? (list->m_current == NULL) : false;
}

void LinkListNext(LinkList *list)
{
 	if((list != NULL) && (list->m_current != NULL))
 	{
  		list->m_current = list->m_current->next; 
 	} 
}

DataType LinkListCurrent(LinkList *list)
{
 	return ((list != NULL) && (list->m_current != NULL)) ? list->m_current->data : (DataType)0;
}

int LinkListFind(LinkList *list, DataType data) //O(n)
{
 	int ret = -1;  
 
 	if(list)
 	{
  		int i = 0;
  
  		for(LinkListMove(list, 0); !LinkListEnd(list); LinkListNext(list), i++)
  		{
   			if(LinkListCurrent(list) == data)
   			{
    				ret = i;
    				break;
   			}
  		}  
 	}
 
 return ret;
}

下面 下麪是DOS執行的結果：