單連結清單

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>

#include<assert.h>

using namespace std;

//實作單連結清單：

typedef int DataType;

typedef struct ListNode

{

struct ListNode *_pNext;

DataType _data;

}ListNode;

ListNode* NewNode(DataType x)

ListNode *tem = (ListNode *)malloc(sizeof(ListNode));

tem->_data = x;

tem->_pNext = NULL;

return tem;

}

void Display(const ListNode* pHead)

while (pHead)

cout << pHead->_data <<"-";

pHead = pHead->_pNext;

cout << endl;

void PushFront(ListNode*& pHead,DataType x)

if (pHead == NULL)

pHead = NewNode(x);

else

ListNode *cur = NewNode(x);

cur->_pNext = pHead;

pHead = cur;

void PopFront(ListNode*& pHead)

if (pHead != NULL)

ListNode *del = pHead;

free(del);

void PushBack(ListNode*& pHead, DataType x)

ListNode *tem = pHead;

while (tem->_pNext != NULL)

tem = tem->_pNext;

}//>>>>>>>>>>>>>>>循環到末尾

tem->_pNext = cur;

cur->_pNext = NULL;

void PopBack(ListNode*& pHead)

while (tem->_pNext->_pNext != NULL)

free(tem->_pNext);

ListNode* Find(ListNode*pHead, DataType x)

if (tem->_data == x)

void Insert(ListNode*& pos, DataType x)

assert(pos);

ListNode* cur = NewNode(x);

cur->_pNext = pos->_pNext;

pos->_pNext = cur;

DataType tem = pos->_data;

pos->_data = cur->_data;

cur->_data = tem;

void Erase(ListNode*&pHead, ListNode*& pos)//>>>>>>>

assert(pHead);

ListNode *cur = pHead;

while (cur->_pNext->_data != pos->_data)

cur = cur->_pNext;

if (cur->_pNext == NULL)

cout << "找不到此節點！" << endl;

free(pos);

void Reverse(ListNode*& pHead)

ListNode* cur = pHead->_pNext;

pHead->_pNext = NULL;

while (cur != NULL)

PushFront(pHead, cur->_data);

ListNode* tem = cur;

free(tem);

ListNode* FindMiddle(ListNode*& pHead)

ListNode* first = pHead;

ListNode* slow = pHead;

while (first->_pNext != NULL)

first = first->_pNext;

if (first->_pNext != NULL)

first = first->_pNext->_pNext;

slow = slow->_pNext;

return slow;

void EraseLastNode(ListNode*& pos)

ListNode *cur = pos->_pNext;

pos->_pNext = cur->_pNext;

free(cur);

//test   PushFront and  PopFront

void test1()

ListNode *pHead = NULL;

PushFront(pHead, 1);

PushFront(pHead, 2);

PushFront(pHead, 3);

Display(pHead);

PopFront(pHead);

//test    PushBack     PopBack

void test2()

PushBack(pHead, 1);

PushBack(pHead, 2);

PushBack(pHead, 3);

PopBack(pHead);

//test    Insert  Erase  Reverse

void test3()

ListNode *pos = Find(pHead, 2);

Insert(pos, 10);

//Erase(pHead, pos);

//Display(pHead);

Reverse(pHead);

//test FindMiddle   EraselastNode

void test4()

PushBack(pHead, 4);

PushBack(pHead, 5);

//ListNode *cur = FindMiddle(pHead);

//cout << cur->_data << endl;

EraseLastNode(pos);

int main()

//test1();

//test2();

//test3();

test4();

system("pause");

return 0;

本文轉自 ye小灰灰  51CTO部落格，原文連結：http://blog.51cto.com/10704527/1719274，如需轉載請自行聯系原作者