版权声明:本文为博主原创文章 && 转载请著名出处 @ http://blog.csdn.net/gatieme
-
#include <stdio.h>
-
#include <stdlib.h>
-
#include <stdbool.h>
-
#include <assert.h>
-
-
-
-
-
-
-
-
-
typedef int ElemType;
-
-
-
-
-
typedef struct CirLinkListNode
- {
- ElemType m_data;
- struct CirLinkListNode *m_next;
- }CirLinkListNode;
-
-
-
typedef struct CirLinkList
- {
- CirLinkListNode *m_head;
- CirLinkListNode *m_tail;
- int m_length;
-
- }CirLinkList;
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- CirLinkList* CreateCirLinkList(void)
- {
- CirLinkList *list = NULL;
- if((list = (CirLinkList *)malloc(sizeof(CirLinkList))) == NULL)
- {
- fprintf(stderr, "not enough memory when CREATE LIST...\n");
- exit(EXIT_FAILURE);
- }
-
- InitCirLinkList(list);
-
- return list;
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
void InitCirLinkList(CirLinkList *list)
- {
- if((list->m_head = malloc(sizeof(CirLinkListNode))) == NULL)
- {
- fprintf(stderr, "not enough memory when MALLOC HEAD...");
- exit(EXIT_FAILURE);
- }
-
-
- list->m_head->m_next = list->m_head;
- list->m_head->m_data = 0;
- list->m_length = 0;
- list->m_tail = list->m_head;
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- CirLinkList* DestroyCirLinkList(CirLinkList *list)
- {
- ClearCirLinkList(list);
- FinitCirLinkList(list);
- if(list != NULL)
- {
- free(list);
- list = NULL;
- }
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
void FinitCirLinkList(CirLinkList *list)
- {
- assert(list->m_head->m_next == list->m_head);
-
- if(list->m_head != NULL)
- {
- free(list->m_head);
-
- list->m_head = NULL;
- list->m_length = -1;
- }
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
void ClearCirLinkList(CirLinkList *list)
- {
- while(list->m_head->m_next != list->m_head)
- {
- DeleteNode(list, 0);
- }
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- CirLinkListNode* FindPosNode(CirLinkList *list, int position)
- {
- assert(list != NULL);
- assert(position >= -1 && position < list->m_length);
-
- CirLinkListNode *pNode = list->m_head->m_next;
-
-
- if(position == -1)
- {
- return list->m_head;
- }
-
- int pos = 0;
-
- while(pNode != list->m_head && pos < position)
- {
- pNode = pNode->m_next;
- pos++;
- }
-
- if(pos < position)
- {
- return NULL;
- }
- else
- {
-
#ifdef DEBUG
- printf("Find the %d point SUCCESS...[%p]\n", position, pNode);
-
#endif // DEBUG
- return pNode;
- }
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- CirLinkListNode *FindPrevNode(CirLinkList *list, CirLinkListNode *currNode)
- {
- assert(list != NULL);
- assert(currNode != NULL);
-
- CirLinkListNode *pNode = list->m_head;
-
-
- while(pNode->m_next != list->m_head && pNode->m_next != currNode)
- {
- pNode = pNode->m_next;
- }
-
- if(pNode->m_next == currNode)
- {
- return pNode;
- }
- else
- {
- return NULL;
- }
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
int IsNodeInList(CirLinkList *list, CirLinkListNode *node)
- {
- assert(list != NULL);
-
- CirLinkListNode *pNode = list->m_head->m_next;
-
- int pos = 0;
-
- while(pNode != list->m_head && pNode != node)
- {
- pNode = pNode->m_next;
- pos++;
- }
-
- if(pNode != node)
- {
- return -1;
- }
- else
- {
-
#ifdef DEBUG
- printf("Find the [%p] point in the first %d pointer of the list...\n", fNode, pos);
-
#endif // DEBUG
- return pos;
- }
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- CirLinkListNode* FindDataNode(CirLinkList *list, ElemType data, int *position)
- {
- CirLinkListNode *node = list->m_head->m_next;
-
-
- int pos = 0;
- while(node != list->m_head && node->m_data != data)
- {
- node = node->m_next;
- pos++;
- }
- *position = pos;
-
- return node;
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- CirLinkListNode* AddNode(CirLinkList *list, CirLinkListNode *prevNode, ElemType data)
- {
- assert(prevNode != NULL);
-
- CirLinkListNode *newNode = NULL;
-
- if((newNode = (CirLinkListNode *)malloc(sizeof(CirLinkListNode))) == NULL)
- {
- fprintf(stderr, "not enough memeory\n");
- exit(EXIT_FAILURE);
- }
- else
- {
-
- newNode->m_data = data;
- newNode->m_next = NULL;
- }
-
-
- newNode->m_next = prevNode->m_next;
- prevNode->m_next = newNode;
-
- list->m_length++;
- list->m_head->m_data++;
-
-
#ifdef DEBUG
- printf("The new node is inserted after point pointer[%p]\n", pNode);
-
#endif // DEBUG
- return newNode;
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
- CirLinkListNode* InsertNode(CirLinkList *list, int position, ElemType data)
- {
- assert(list != NULL);
- assert(position >=0 && position < list->m_length + 1);
-
- CirLinkListNode *prevNode = FindPosNode(list, position - 1);
- CirLinkListNode *newNode = NULL;
-
-
- if((newNode = AddNode(list, prevNode, data)) != NULL)
- {
- return newNode;
-
#ifdef DEBUG
- printf("Insert the value %d into list at position %d...\n", data, position);
-
#endif // DEBUG
- }
- else
- {
- return NULL;
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- ElemType DeleteNode(CirLinkList *list, int position)
- {
- assert(list != NULL);
- assert(position >=0 && position < list->m_length);
- CirLinkListNode *prevNode = FindPosNode(list, position - 1);
-
-
- CirLinkListNode *delNode = prevNode->m_next;
- ElemType delElem = delNode->m_data;
- prevNode->m_next = delNode->m_next;
- free(delNode);
-
- list->m_length--;
- list->m_head->m_data--;
-
- return delElem;
- }
-
-
-
-
-
-
-
-
-
-
-
-
- ElemType SubNode(CirLinkList *list, CirLinkListNode *prevNode)
- {
- assert(list != NULL);
- assert(prevNode != NULL);
- assert(IsNodeInList(list, prevNode) != -1);
-
-
- CirLinkListNode *delNode = prevNode->m_next;
- ElemType delElem = delNode->m_data;
- prevNode->m_next = delNode->m_next;
- free(delNode);
-
- list->m_length--;
- list->m_head->m_data--;
-
- return delElem;
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
- ElemType DeleteCurrNode(CirLinkList *list, CirLinkListNode *currNode)
- {
- assert(list != NULL);
- assert(currNode != NULL);
- assert(IsNodeInList(list, currNode) != -1);
-
- ElemType delElem = -1;
- CirLinkListNode *delNode = NULL;
-
-
-
-
-
-
-
- if(currNode->m_next != list->m_head)
- {
-
- delNode = currNode->m_next;
- currNode->m_next = delNode->m_next;
-
-
- delElem = currNode->m_data;
- currNode->m_data = delNode->m_data;
- }
- else
- {
-
- delNode = currNode;
-
- CirLinkListNode *prevNode = FindPrevNode(list, currNode);
- prevNode->m_next = list->m_head;
- }
- free(delNode);
- list->m_length--;
- list->m_head->m_data--;
-
- return delElem;
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
void ShowList(CirLinkList *list)
- {
-
- if(list->m_head == NULL)
- {
- fprintf(stderr, "you can't SHOW the list without the list INITLINKLIST...\n");
- return ;
- }
-
-
- printf("there are %d data in list\n", list->m_length);
- if(list->m_length == 0)
- {
- return ;
- }
-
- CirLinkListNode *pNode = list->m_head->m_next;
-
- while(pNode != list->m_head)
- {
- printf("%d ", pNode->m_data);
- pNode = pNode->m_next;
- }
- printf("\n");
-
-
-
-
-
-
-
-
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
void SetNode(CirLinkList *list, int position, ElemType data)
- {
- CirLinkListNode *pNode = FindPosNode(list, position);
-
- pNode->m_data = data;
- }
-
-
-
-
-
-
-
-
-
-
-
- ElemType GetNode(CirLinkList *list, int position)
- {
- CirLinkListNode *pNode = FindPosNode(list, position);
-
- return pNode->m_data;
- }
-
-
-
-
-
-
-
-
-
-
-
-
int LengthCirLinkList(CirLinkList *list)
- {
- return list->m_length;
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
bool IsEmptyCirLinkList(CirLinkList *list)
- {
- return (list->m_head->m_next == list->m_head);
-
- }
-
-
-
-
-
-
-
-
-
-
-
- CirLinkListNode* GetFisrtNode(CirLinkList *list)
- {
- return list->m_head->m_next;
-
- }
-
-
-
-
-
-
-
-
-
-
-
- CirLinkListNode* GetHeadNode(CirLinkList *list)
- {
- return list->m_head;
-
- }
-
-
-
-
-
-
-
#define LIST_SIZE 7
-
-
int main(void)
- {
- int pos;
-
- printf("TEST 1...\n");
- CirLinkList *plist = CreateCirLinkList( );
- for(int pos = 0; pos < LIST_SIZE; pos++)
- {
- InsertNode(plist, pos, pos + 1);
- }
- ShowList(plist);
-
- DeleteNode(plist, 0);
- ShowList(plist);
- DeleteNode(plist, 1);
- ShowList(plist);
-
- ClearCirLinkList(plist);
- ShowList(plist);
- DestroyCirLinkList(plist);
- plist = NULL;
-
- printf("\n\nTEST 2...\n");
- CirLinkList list;
- InitCirLinkList(&list);
- for(int pos = 0; pos < LIST_SIZE; pos++)
- {
- InsertNode(&list, pos, pos + 1);
- }
- ShowList(&list);
- ClearCirLinkList(&list);
-
- ShowList(&list);
-
- printf("\n\nTEST 3...\n");
- CirLinkListNode *prevNode = list.m_head;
- CirLinkListNode *addNode = NULL;
- for(int pos = 0; pos < LIST_SIZE; pos++)
- {
- if((addNode = AddNode(&list, prevNode, pos + 1)) != NULL)
- {
- prevNode = addNode;
- }
- }
- ShowList(&list);
- while(IsEmptyCirLinkList(&list) != true)
- {
-
- DeleteCurrNode(&list, list.m_head->m_next);
- }
- ShowList(&list);
-
- return EXIT_SUCCESS;
- }
转载:http://blog.csdn.net/gatieme/article/details/42714079