链表的C++实现——创建-插入-删除-输出-清空

注：学习了数据结构与算法分析后，对链表进行了C++实现，参考博文：http://www.cnblogs.com/tao560532/articles/2199280.html

环境：VS2013

//节点的声明

#pragma once

class structNode
{
public:
    structNode();
    ~structNode();
    struct Node
    {
        int Data;
        Node *next;
    };

};
typedef structNode::Node listNode;

//链表的创建

1 #include "creatLinkList.h"
 2 #include <iostream>
 3 using namespace std;
 4 
 5 
 6 creatLinkList::creatLinkList()
 7 {
 8     
 9 }
10 
11 creatLinkList::~creatLinkList()
12 {
13 
14 }
15 
16 listNode *creatLinkList::create()
17 {
18     head = (listNode *)new(listNode);
19     head->next = NULL;
20     tem = head;
21 
22     int n;
23     cout << "please input the number of the node: " << 'n';
24     scanf_s("%d", &n);
25 
26     for (int i = 1; i <= n; i++)
27     {
28         printf("input the data of %d : ", i);
29         p = (listNode *)new(listNode);
30         scanf_s("%d", &p->Data);
31         tem->next = p;
32         tem = p;
33     }
34     p->next = NULL;
35     return head;
36 }

//链表的插入

1 #include "insertLinkList.h"
 2 #include <iostream>
 3 using namespace std;
 4 
 5 
 6 insertLinkList::insertLinkList()
 7 {
 8 }
 9 
10 
11 insertLinkList::~insertLinkList()
12 {
13 }
14 
15 //在链表的第i个位置后添加一个节点，该节点的数据元素为x
16 listNode *insertLinkList::insertList(listNode *h)
17 {
18     listNode *tem, *p;
19     int i, x;
20     tem = (listNode*)new(listNode);
21     p = (listNode*)new(listNode);
22     tem = h->next;
23     int count = 1;
24     cout << "Please input the position: " << 'n';
25     scanf_s("%d", &i);
26 
27     //在第1个位置插入节点
28     if (i == 0)
29     {
30         cout << "Please input the first data: " << 'n';
31         scanf_s("%d", &x);
32         p->Data = x;
33         p->next = tem;
34         h->next = p;
35         return h;
36     }
37     //在其他位置插入节点
38     while ((count != i) && (tem->next != NULL))
39     {
40         tem = tem->next;
41         count++;
42     }
43     if (count != i)
44         std::cout << "out of space! insert the new data at last of the list" << 'n';
45 
46 
47     cout << "Please input the data: " << 'n';
48     scanf_s("%d", &x);
49     p->Data = x;
50     p->next = tem->next;
51     tem->next = p;
52     return h;
53 
54 }

//链表的删除

1 #include "deleteLinkList.h"
 2 #include <iostream>
 3 using namespace std;
 4 
 5 
 6 deleteLinkList::deleteLinkList()
 7 {
 8 }
 9 
10 
11 deleteLinkList::~deleteLinkList()
12 {
13 }
14 
15 //删除链表中数据元素为x的节点
16 listNode *deleteLinkList::deleteList(listNode *h)
17 {
18     listNode *tem, *p;
19     int x;
20     tem = (listNode*)new(listNode);
21     tem = h->next;
22 
23     cout << "Please input the data to delete : " << 'n';
24     scanf_s("%d", &x);
25 
26     //如果删除第一个节点
27     if (tem->Data == x)
28     {
29         p = tem;
30         h->next = p->next;
31         free(p);
32         return h;
33     }
34     //如果删除其余节点
35     while (tem->next != NULL && tem->next->Data != x)
36         tem = tem->next;
37     if (tem->next == NULL)
38         cout << "oops! out of space!" << 'n';
39     else
40         p = (listNode*)new(listNode);
41         p = tem->next;
42         tem->next = p->next;
43         delete(p);
44     return h;
45 }

//链表的输出

1 #include "outputList.h"
 2 #include "creatLinkList.h"
 3 #include <iostream>
 4 using namespace std;
 5 
 6 
 7 outputList::outputList()
 8 {
 9 }
10 
11 
12 outputList::~outputList()
13 {
14 }
15 
16 void outputList::coutLinkList(listNode *h)
17 {
18     listNode *currentNode;
19     currentNode = h->next;
20     while (currentNode)
21     {
22         std::cout << currentNode->Data << " ";
23         currentNode = currentNode->next;
24     }
25     cout << "n";
26 }

//链表的清空

#include "deleteWholeList.h"
#include <iostream>


deleteWholeList::deleteWholeList()
{
}


deleteWholeList::~deleteWholeList()
{
}

listNode* deleteWholeList::endList(listNode *h)
{
    listNode *p,*tem;
    p = h->next;
    h->next = NULL;
    /*tem = p;*/
    while (p != NULL)
    {
        tem = p->next;
        free(p);
        /*p = tem->next;*/
        p = tem;
    }
    return h;
}

//主函数

1 #include "creatLinkList.h"
 2 #include "outputList.h"
 3 #include "structNode.h"
 4 #include "insertLinkList.h"
 5 #include "deleteLinkList.h"
 6 #include "deleteWholeList.h"
 7 #include <iostream>
 8 using namespace std;
 9 int main()
10 {
11     cout << 'n' <<"***************************************"<< 'n' << 'n';
12     cout << "Welcome to the linkList world! " << 'n';
13     cout << 'n' <<"***************************************" << 'n' << 'n';
14 
15     int i = 0;
16     //int j = 1;
17     listNode *h = NULL;
18     creatLinkList a;
19     outputList b;
20     insertLinkList c;
21     deleteLinkList d;
22     deleteWholeList e;
23     while (1)
24     {
25         cout << 'n' << "***************************************" << 'n';
26         cout << " 0 : end the linkList " << 'n';
27         cout << " 1 : creat a linkList " << 'n';
28         cout << " 2 : display a linkList  " << 'n';
29         cout << " 3 : insert a node in the linkList  " << 'n';
30         cout << " 4 : delete a node from the linkList  " << 'n';
31         cout << "***************************************" << 'n';
32         cout << "Please input the function your want with the number above : " << 'n';
33         scanf_s("%d",&i);
34         
35         switch (i)
36         {
37         case 1:
38             cout << "CreatList now begin : ";
39             h = a.create();
40             break;
41         case 2:
42             cout << "List now is : ";
43             b.coutLinkList(h);
44             break;
45         case 3:
46             cout << "InsertList now begin : ";
47             h = c.insertList(h);
48             break;
49         case 4:
50             cout << "DeleteList now begin : ";
51             h = d.deleteList(h);
52             break;
53         default:
54             cout << "End the list. ";
55             h = e.endList(h);
56             //j = 0;
57             break;
58         }
59 
60         //structNode::Node *h;
61         //cout << "CreatList now begin : ";
62         //creatLinkList a;
63         //h = a.create();
64 
65         //cout << "List now is : ";
66         //outputList b;
67         //b.coutLinkList(h);
68 
69         //cout << "InsertList now begin : ";
70         //insertLinkList c;
71         //h = c.insertList(h);
72         //cout << "List after insert is : ";
73         //b.coutLinkList(h);
74     
75         //cout << "DeleteList now begin : ";
76         //deleteLinkList d;
77         //h = d.deleteList(h);
78         //cout << "List after delete is : ";
79         //b.coutLinkList(h);
80     }
81 
82 }

部分运行效果如下：

原文链接: https://www.cnblogs.com/Lunais/p/5444289.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍