データ構造テンプレート----単一チェーン表SimplelinkList[率先して結点しない&疑似OO](C言語で実現)

17424 ワード

前にシングルチェーン表を書くのは率先して結点しますが、他のこのような書き方のシングルチェーン表では、頭の結点は実はそんなに必要ではありません.私達のシングルチェーンテーブル構造体にm_が追加されました.length
下の頭の結点をプラスしないシングルチェーン表を提出します.
率先して接合しないシングルチェーン構造体
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>



///*////////////////////////////////////////////////////////////////////////////
///
///	         
///
///	  		LinkList* CreatLinkList(void)
///	   	void InitLinkList(LinkList *list)
///*////////////////////////////////////////////////////////////////////////////

typedef int ElemType;		//        

//typedef struct LinkListNode*	PLinkListNode;			//        

//        
typedef struct LinkListNode
{
	ElemType			m_data;			//    
	struct LinkListNode	*m_next;			//    
}LinkListNode;

//          
typedef struct LinkList
{
	LinkListNode	*m_head;				//      
	int				m_length;			//             
}LinkList;


///*////////////////////////////////////////////////////////////////////////////
///
///	         
///
///	           ,       ,              
///	LinkList* CreatLinkList(void)
///
///	      
///	void InitLinkList(LinkList *list)
///*///////////////////////////////////////////////////////////////////////////

/**
LinkList* CreatLinkList(void)
  
	list	:	        ,        
   
	               
  
	           ,       ,              
  
	  CreateLinkList      ,   DestroyLinkList   
	        
*/
LinkList* CreateLinkList(void)
{
	LinkList *list = NULL;
	if((list = (LinkList *)malloc(sizeof(LinkList))) == NULL)		//         
	{	//     
        fprintf(stderr, "not enough memory when CREATE LIST...
"); exit(EXIT_FAILURE); } InitLinkList(list); // return list; } /** void InitLinkList(LinkList *list) list : , , ① ② [ ] InitLinkList ( malloc m_head ) FinitLinkList ( free m_head ) */ void InitLinkList(LinkList *list) { list->m_head = NULL; // list->m_length = 0; // 0 } ///*//////////////////////////////////////////////////////////////////////////// /// /// /// /// CreateLinkList /// void DestroyLinkList(LinkList *list) /// /// , /// void FinitLinkList(LinkList *list) /// /// /// void ClearLinkList(LinkList *list) ///*//////////////////////////////////////////////////////////////////////////// /** void DestroyLinkList(LinkList *list) list : , CreateLinkList , ① ② ③ CreateLinkList , DestroyLinkList */ LinkList* DestroyLinkList(LinkList *list) { ClearLinkList(list); // FinitLinkList(list); // if(list != NULL) // { free(list); list = NULL; } } /** void FinitLinkList(LinkList *list) list : , , ① ② [ ] InitLinkList ( malloc m_head ) FinitLinkList ( free m_head ) */ void FinitLinkList(LinkList *list) { assert(list->m_head == NULL); // // list->m_head = NULL; list->m_length = -1; // -1 } /** void ClearLinkList(LinkList *list) list : , */ void ClearLinkList(LinkList *list) { while(list->m_head != NULL) { DeleteNode(list, 0); } } ///*//////////////////////////////////////////////////////////////////////////// /// /// /// /// list position /// LinkListNode* FindPosNode(LinkList *list, int position) /// /// list currNode /// LinkListNode *FindPrevNode(LinkList *list, LinkListNode *currNode) /// /// node /// int IsNodeInList(LinkList *list, LinkListNode *node) /// /// data /// LinkListNode* FindDataNode(LinkList *list, ElemType data, int *position) ///*//////////////////////////////////////////////////////////////////////////// /** LinkListNode* FindPosNode(LinkList *list, int position) list : , positon : NULL : list position */ LinkListNode* FindPosNode(LinkList *list, int position) { assert(list != NULL); // assert(position >= 0 && position < list->m_length); // [0, length) LinkListNode *pNode = list->m_head; int pos = 0; while(pNode != NULL && pos < position) // , position { pNode = pNode->m_next; pos++; } if(pNode == NULL || pos < position) { return NULL; } else { #ifdef DEBUG printf("Find the %d point SUCCESS...[%p]
", position, pNode); #endif // DEBUG return pNode; } } /** LinkListNode *FindPrevNode(LinkList *list, LinkListNode *currNode); list : , currNode : NULL list currNode */ LinkListNode *FindPrevNode(LinkList *list, LinkListNode *currNode) { assert(list != NULL); assert(currNode != NULL); LinkListNode *pNode = list->m_head; while(pNode->m_next != NULL && pNode->m_next != currNode) { pNode = pNode->m_next; } if(pNode->m_next == currNode) // { return pNode; } else // { return NULL; } } /** int IsNodeInList(LinkList *list, LinkListNode *node) list : , node : node -1 node */ int IsNodeInList(LinkList *list, LinkListNode *node) { assert(list != NULL); // assert(Node != NULL); // LinkListNode *pNode = list->m_head; int pos = 0; while(pNode != NULL && pNode != node) // , position { 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...
", fNode, pos); #endif // DEBUG return pos; } } ///*//////////////////////////////////////////////////////////////////////////// /// /// /// /// data prevNode /// LinkListNode *AddNode(LinkList *list, LinkListNode *prevNode, ElemType data) /// /// data position /// LinkListNode *InsertNode(LinkList *list, int position, ElemType data) ///*//////////////////////////////////////////////////////////////////////////// /** void InsertNode(LinkList *list, int position, ElemType data) list : , positon : data : : data position */ LinkListNode* InsertNode(LinkList *list, int position, ElemType data) { assert(list != NULL); // assert(position >=0 && position < list->m_length + 1); // [0-length] LinkListNode *prevNode = NULL; LinkListNode *newNode = NULL; // if((newNode = (LinkListNode *)malloc(sizeof(LinkListNode))) == NULL) // { // fprintf(stderr, "not enough memeory
"); exit(EXIT_FAILURE); } else { // newNode->m_data = data; newNode->m_next = NULL; } // if(position == 0) // { /// , , if(list->m_head == NULL) // { list->m_head = newNode; // } else // { //prevNode = list->m_head; newNode->m_next = list->m_head; // list->m_head = newNode; } } else // { prevNode = FindPosNode(list, position - 1); // // newNode pNode newNode->m_next = prevNode->m_next; prevNode->m_next = newNode; } list->m_length++; // #ifdef DEBUG printf("Insert the value %d into list at position %d...
", data, position); #endif // DEBUG return newNode; // } /** LinkListNode* AddNode(LinkList *list, LinkListNode *prevNode, ElemType data); list : , prevNode : data : : data prevNode [ ] , , , prevNode list */ LinkListNode *AddNode(LinkList *list, LinkListNode *prevNode, ElemType data) { assert(prevNode != NULL); // LinkListNode *newNode = NULL; if((newNode = (LinkListNode *)malloc(sizeof(LinkListNode))) == NULL) // { // fprintf(stderr, "not enough memeory
"); exit(EXIT_FAILURE); } //else //{ // newNode->m_data = data; newNode->m_next = NULL; if(prevNode == (LinkListNode *)list) { /// , , if(list->m_head == NULL) // { list->m_head = newNode; // } else // { //prevNode = list->m_head; newNode->m_next = list->m_head; // list->m_head = newNode; } } else { // newNode pNode newNode->m_next = prevNode->m_next; prevNode->m_next = newNode; } list->m_length++; // //} #ifdef DEBUG printf("The new node is inserted after point pointer[%p]
", pNode); #endif // DEBUG return newNode; } ///*//////////////////////////////////////////////////////////////////////////// /// /// /// /// list prevNode /// void DeleteNode(LinkList *list, int position) /// /// list prevNode /// ElemType SubNode(LinkList *list, LinkListNode *prevNode) /// /// list prevNode /// ElemType DeleteCurrNode(LinkList *list, LinkListNode *currNode) ///*//////////////////////////////////////////////////////////////////////////// /** ElemType DeleteNode(LinkList *list, int position) list : , positon : position */ ElemType DeleteNode(LinkList *list, int position) { assert(list != NULL); // assert(position >=0 && position < list->m_length); // LinkListNode *delNode = NULL; ElemType delElem = -1; if(position == 0) // , { // delNode = list->m_head; if(list->m_head->m_next == NULL) // { list->m_head = NULL; } else // { list->m_head = delNode->m_next; } } else // { LinkListNode *pNode = FindPosNode(list, position - 1); // position - 1 // pNode delNode = pNode->m_next; pNode->m_next = delNode->m_next; } delElem = delNode->m_data; // free(delNode); list->m_length--; // #ifdef DEBUG printf("Delete the list in the first %d node...
", position); #endif // DEBUG return delElem; } /** ElemType SubNode(LinkList *list, LinkListNode *prevNode) list : , positon : list prevNode */ ElemType SubNode(LinkList *list, LinkListNode *prevNode) { assert(list != NULL); // assert(prevNode != NULL); // assert(IsNodeInList(list, prevNode) != -1); // LinkListNode *delNode = NULL; ElemType delElem = -1; if(prevNode == list) // , [ list] { // delNode = list->m_head; // if(list->m_head->m_next == NULL) // { list->m_head = NULL; } else // { list->m_head = delNode->m_next; } } else // { // pNode delNode = prevNode->m_next; prevNode->m_next = delNode->m_next; } delElem = delNode->m_data; free(delNode); list->m_length--; // list->m_head->m_data--; // return delElem; } /** ElemType DeleteCurrNode(LinkList *list, LinkListNode *currNode); list : , positon : list prevNode */ ElemType DeleteCurrNode(LinkList *list, LinkListNode *currNode) { assert(list != NULL); // assert(currNode != NULL); // assert(IsNodeInList(list, currNode) != -1); // ElemType delElem = -1; // LinkListNode *delNode = NULL; // if(currNode == list->m_head) // { // , , delNode = list->m_head; // if(list->m_head->m_next == NULL) // { list->m_head = NULL; } else // { list->m_head = delNode->m_next; } } else // { if(currNode->m_next != NULL) // { // , // currNode delNode , delNode = currNode->m_next; currNode->m_next = delNode->m_next; // delNode // delNode delNode delElem = currNode->m_data; // delElem currNode currNode->m_data = delNode->m_data; // currNode , currNode } else // { // , delNode = currNode; // currnNode [ O(n)] LinkListNode *prevNode = FindPrevNode(list, currNode); prevNode->m_next = NULL; } } free(delNode); list->m_length--; // return delElem; } ///*//////////////////////////////////////////////////////////////////////////// /// /// /// /// /// void ShowList(LinkList *list /// /// list prevNode /// void SetNode(LinkList *list, int position, ElemType data) /// /// list position /// ElemType GetNode(LinkList *list, int position) /// /// list [ ] /// int LengthLinkList(LinkList *list) /// /// /// bool IsEmptyLinkList(LinkList *list) ///*//////////////////////////////////////////////////////////////////////////// /** void ShowLinkList(LinkList *list) list : , */ void ShowList(LinkList *list) { printf("there are %d data in list
", list->m_length); LinkListNode *pNode = list->m_head; // while(pNode != NULL) // { printf("%d ", pNode->m_data); pNode = pNode->m_next; } printf("
"); // ElemType data; // for(int pos = 0; pos < list->m_length; pos++) // { // data = GetNode(list, pos); // printf("%d ", data); // } // printf("
"); } /** void SetNode(LinkList *list, int position, ElemType data) list : , positon : data : list position data */ void SetNode(LinkList *list, int position, ElemType data) { LinkListNode *pNode = FindPosNode(list, position); // position pNode->m_data = data; } /** ElemType GetNode(LinkList *list, int position list : , positon : list position */ ElemType GetNode(LinkList *list, int position) { LinkListNode *pNode = FindPosNode(list, position); // position return pNode->m_data; } /** int LengthLinkList(LinkList *list) list : , */ int LengthLinkList(LinkList *list) { return list->m_length; } /** bool IsEmptyLinkList(LinkList *list) list : , , true false */ bool IsEmptyLinkList(LinkList *list) { return (list->m_length == 0); // return (list->m_head == NULL); } #define LIST_SIZE 7 // main int main(void) { int pos; printf("TEST 1...
"); LinkList *plist = CreateLinkList( ); // for(int pos = 0; pos < LIST_SIZE; pos++) // { InsertNode(plist, pos, pos + 1); printf("HEAD = %p
", plist->m_head); } ShowList(plist); // DeleteNode(plist, 0); // ShowList(plist); DeleteNode(plist, 1); // ShowList(plist); ClearLinkList(plist); // ShowList(plist); DestroyLinkList(plist); // plist = NULL; printf("

TEST 2...
"); LinkList list; InitLinkList(&list); // for(int pos = 0; pos < LIST_SIZE; pos++) // { InsertNode(&list, pos, pos + 1); } ShowList(&list); // ClearLinkList(&list); // // FinitLinkList(&list); // ERROR== list->m_head->m_next == NULL ShowList(&list); printf("

TEST 3...
"); LinkListNode *prevNode = NULL; LinkListNode *addNode = NULL; prevNode = InsertNode(&list, 0, 1); // // for(int pos = 1; pos < LIST_SIZE; pos++) { if((addNode = AddNode(&list, prevNode, pos + 1)) != NULL) { prevNode = addNode; } } // LinkListNode *prevNode = (LinkListNode*)&list; // LinkListNode *addNode = NULL; // for(int pos = 0; pos < LIST_SIZE; pos++) // { // if((addNode = AddNode(&list, prevNode, pos + 1)) != NULL) // { // prevNode = addNode; // } // } ShowList(&list); while(IsEmptyLinkList(&list) != true) // { DeleteCurrNode(&list, list.m_head); // } ShowList(&list); // return EXIT_SUCCESS; }