データ構造の双方向チェーンテーブル(C++言語記述)
18073 ワード
#include <iostream>
using namespace std;
class ListNode
{
public:
int m_nValue;
ListNode* m_pLeft;
ListNode* m_pRight;
};
ListNode* CreateListNode(int value);//
ListNode* CreateList();//
void PrintListNode(ListNode* pHead);//
void DeleteListMemory(ListNode** pHead);// ,
// 、
ListNode* InsertListNode(ListNode* pHead, int value, int i);// i ,i 0
ListNode* DeleteListNode(ListNode* pHead, int i);// i ,i==1
int main()
{
//int value = 0;
//while (cin >> value)
//{
// ListNode* pNode = NULL;
// pNode = CreateListNode(value);
// if (pNode != NULL) cout << pNode->m_nValue << endl;
// delete pNode;
// pNode = NULL;
//}
ListNode* pHead = NULL;
pHead = CreateList();
if (pHead != NULL) PrintListNode(pHead);
//ListNode* result1 = NULL;
////result1 = InsertListNode(pHead, 0, 0);
////result1 = InsertListNode(pHead, 1, 1);
////result1 = InsertListNode(pHead, 2, 2);
////result1 = InsertListNode(pHead, 4, 4);
//result1 = InsertListNode(pHead, 6, 5);
//if (result1 != NULL) PrintListNode(result1);
//ListNode* result2 = NULL;
//result2 = DeleteListNode(pHead, 1);
//if (result2 != NULL) PrintListNode(result2);
DeleteListMemory(&pHead);
system("pause");
return 0;
}
ListNode* CreateListNode(int value)
{
ListNode* pNode = new ListNode();
if (pNode == NULL)
{
cout << " !" << endl;
return NULL;
}
pNode->m_nValue = value;
pNode->m_pLeft = NULL;
pNode->m_pRight = NULL;
return pNode;
}
ListNode* CreateList()
{
ListNode* pHead = NULL;
ListNode* pNode = NULL;
ListNode* pLastNode = NULL;
int inputValue = 0;
while (cin >> inputValue)
{
pNode = new ListNode();
if (pNode == NULL)
{
cout << " !" << endl;
return NULL;
}
pNode->m_nValue = inputValue;
pNode->m_pLeft = pNode->m_pRight = NULL;
if (pHead == NULL)
{
pHead = pNode;
}
else
{
pLastNode->m_pRight = pNode;
pNode->m_pLeft = pLastNode;
}
pLastNode = pNode;
}
return pHead;
}
void DeleteListMemory(ListNode** pHead)
{
if (pHead == NULL || *pHead == NULL)
{
cout << "List is empty!" << endl;
return;
}
ListNode* pNode = *pHead;
ListNode* pDeleted = NULL;
while (pNode != NULL)
{
pDeleted = pNode;
pNode = pNode->m_pRight;
if(pNode != NULL) pNode->m_pLeft = NULL;
delete pDeleted;
pDeleted = NULL;
}
pHead = NULL;
}
void PrintListNode(ListNode* pHead)
{
if (pHead == NULL)
{
cout << "List is empty!" << endl;
return;
}
ListNode* pNode = pHead;
while (pNode != NULL)
{
cout << pNode->m_nValue<< " ";
pNode = pNode->m_pRight;
}
cout << endl;
}
ListNode* InsertListNode(ListNode* pHead, int value, int i)
{
if (i < 0)
{
cout << "Error:the position is invalid!" << endl;
return NULL;
}
if (pHead == NULL && i == 0)
{
ListNode* pNode = new ListNode();
pNode->m_nValue = value;
pNode->m_pLeft = pNode->m_pRight = NULL;
pHead = pNode;
return pHead;
}
else if (pHead == NULL && i > 0)
{
cout << "Error:the list is empty and the position is invalid!" << endl;
return NULL;
}
else//pHead!=NULL
{
ListNode* pNode = pHead;
int length = 0;
while (pNode != NULL)
{
length++;
pNode = pNode->m_pRight;
}
ListNode* pNewNode = new ListNode();
pNewNode->m_nValue = value;
pNewNode->m_pLeft = pNewNode->m_pRight = NULL;
if (i == 0)
{
pHead->m_pLeft = pNewNode;
pNewNode->m_pRight = pHead;
pHead = pNewNode;
return pHead;
}
else if (i > 0 && i <= length)
{
pNode = pHead;
for (int j = 1; j < i; ++j)
{
pNode = pNode->m_pRight;
}
if (i < length)
{
pNewNode->m_pRight = pNode->m_pRight;
pNode->m_pRight->m_pLeft = pNewNode;
pNewNode->m_pLeft = pNode;
pNode->m_pRight = pNewNode;
}
else//i==length
{
pNode->m_pRight = pNewNode;
pNewNode->m_pLeft = pNode;
}
return pHead;
}
else
{
cout << "Error:the position is longer than list's length!" << endl;
return NULL;
}
}
}
ListNode* DeleteListNode(ListNode* pHead, int i)
{
if (pHead == NULL)
{
cout << "Error:the list is empty!" << endl;
return NULL;
}
if (i <= 0)
{
cout << "Error:the position is invalid!" << endl;
return NULL;
}
ListNode* pNode = pHead;
int length = 0;
while (pNode != NULL)
{
length++;
pNode = pNode->m_pRight;
}
if (i > length)
{
cout << "Error:the position is longer than length!" << endl;
return NULL;
}
pNode = pHead;
for (int j = 1; j < i; ++j)
{
pNode = pNode->m_pRight;
}
if (i == 1)
{
pHead = pNode->m_pRight;
if (pHead != NULL)
{
pHead->m_pLeft = NULL;
}
}
else if (i > 1 && i < length)
{
pNode->m_pRight->m_pLeft = pNode->m_pLeft;
pNode->m_pLeft->m_pRight = pNode->m_pRight;
}
else
{
pNode->m_pLeft->m_pRight = NULL;
}
delete pNode;
pNode = NULL;
return pHead;
}