데이터 구조 모델 - 단일 체인 표 SimpleLinkList [선두 결점 & & 대상 을 대상 으로 디자인 사상] (C 언어 실현)
단일 체인 테이블 은 체인 액세스 의 구조 로 i 번 째 데이터 요 소 를 찾기 위해 서 는 i - 1 번 째 데이터 요 소 를 먼저 찾 아야 합 니 다.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
//#define DEBUG //
/// V0.0.2
/// ① InsertNode
// data position
// LinkListNode* InsertNode(LinkList *list, int position, ElemType data)
// data pNode
// LinkListNode* AddNode(LinkList *list, LinkListNode *prevNode, ElemType data)
/// ② DelNode
// list position
// ElemType DeleteNode(LinkList *list, int position)
// list prevNode
// ElemType SubNode(LinkListNode *prevNode)
// list currNode
// ElemType DeleteCurrNode(LinkList *list, LinkListNode *currNode)
/// ③ FindNode
// list position
// LinkListNode* FindPosNode(LinkList *list, int position);
// list currNode
// LinkListNode *FindPrevNode(LinkList *list, LinkListNode *currNode);
// node
// int IsNodeInList(LinkList *list, LinkListNode *node);
///*////////////////////////////////////////////////////////////////////////////
///
///
///
///*////////////////////////////////////////////////////////////////////////////
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)
{
if((list->m_head = malloc(sizeof(LinkListNode))) == NULL) //
{ //
fprintf(stderr, "not enough memory when MALLOC HEAD...");
exit(EXIT_FAILURE);
}
list->m_head->m_next = NULL; //
list->m_head->m_data = 0; // 0
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->m_next == NULL); //
// assert(list->m_length == 0);
if(list->m_head != NULL) //
{
free(list->m_head);
list->m_head = NULL;
list->m_length = -1; // -1
}
}
/**
void ClearLinkList(LinkList *list)
list : ，
*/
void ClearLinkList(LinkList *list)
{
while(list->m_head->m_next != 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* FindNodeData(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 >= -1 && position < list->m_length); // w [-1~length]
LinkListNode *pNode = list->m_head;
int pos = -1;
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 = -1;
while(pNode != NULL && pNode != node) // ， position
{
pNode = pNode->m_next;
pos++;
}
if(pNode == NULL)
{ //
return -1;
}
else
{ //
#ifdef DEBUG
printf("Find the [%p] point in the first %d pointer of the list...
", fNode, pos);
#endif // DEBUG
return pos;
}
}
/**
LinkListNode* FindData(LinkList *list, ElemType data, , int *position)
list : ，
data :
node
-1
data
*/
LinkListNode* FindNodeData(LinkList *list, ElemType data, int *position)
{
LinkListNode *node = list->m_head->m_next;
int pos = 0;
while(node != NULL && node->m_data != data)
{
node = node->m_next;
pos++;
}
*position = pos; //
return node; //
}
///*////////////////////////////////////////////////////////////////////////////
///
///
///
/// data prevNode
/// LinkListNode *AddNode(LinkList *list, LinkListNode *prevNode, ElemType data)
///
/// data position
/// LinkListNode *InsertNode(LinkList *list, int position, ElemType data)
///*////////////////////////////////////////////////////////////////////////////
/**
LinkListNode* AddNode(LinkList *list, LinkListNode *prevNode, ElemType data);
list : ，
prevNode :
data :
data prevNode
*/
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;
// newNode pNode
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]
", pNode);
#endif // DEBUG
return newNode;
}
/**
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);
LinkListNode *prevNode = FindPosNode(list, position - 1); //
LinkListNode *newNode = NULL;
// InsertPointNode pNode
if((newNode = AddNode(list, prevNode, data)) != NULL) //
{ //
return newNode; //
#ifdef DEBUG
printf("Insert the value %d into list at position %d...
", data, position);
#endif // DEBUG
}
else
{
return NULL; // 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;
//
// // newNode pNode
// newNode->m_next = prevNode->m_next;
// prevNode->m_next = newNode;
//
// list->m_length++; //
// list->m_head->m_data++; //
// }
}
///*////////////////////////////////////////////////////////////////////////////
///
///
///
/// list prevNode
/// void DeleteNode(LinkList *list, int position)
///
/// list prevNode
/// ElemType SubNode(LinkList *list, LinkListNode *prevNode)
///
/// list prevNode
/// ElemType DeleteCurrNode(LinkList *list, LinkListNode *currNode)
///*////////////////////////////////////////////////////////////////////////////
/**
void DeleteNode(LinkList *list, int position)
list : ，
positon :
list prevNode
*/
ElemType DeleteNode(LinkList *list, int position)
{
assert(list != NULL);
assert(position >=0 && position < list->m_length);
LinkListNode *prevNode = FindPosNode(list, position - 1); // position - 1
// pNode
LinkListNode *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 delNode;
}
/**
ElemType DeleteCurrNode(LinkList *list, LinkListNode *currNode);
list : ，
positon :
list prevNode
*/
ElemType SubNode(LinkList *list, LinkListNode *prevNode)
{
assert(list != NULL); //
assert(prevNode != NULL); //
assert(IsNodeInList(list, prevNode) != -1); //
// pNode
LinkListNode *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(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->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--; //
list->m_head->m_data--; //
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)
{
// assert(list->m_head != NULL)
if(list->m_head == NULL) //
{
fprintf(stderr, "you can't SHOW the list without the list INITLINKLIST...
");
return ;
}
printf("there are %d data in list
", list->m_length);
if(list->m_length == 0)
{
return ;
}
LinkListNode *pNode = list->m_head->m_next; //
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 : ，
positon :
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->m_next == NULL);
}
#define LIST_SIZE 7
//
int main(void)
{
int pos;
printf("TEST 1...
");
LinkList *plist = CreateLinkList( ); //
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);
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 = list.m_head;
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->m_next);
}
ShowList(&list); //
return EXIT_SUCCESS;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
