#include <string>
#include <iostream>

#ifndef _LINK_0411
#define _LINK_0411

//定义数据类型为整型
typedef int ElementType;

//定义结点
struct Node{
    ElementType data;
    Node * next;
};

//带头结点链表
class Link
{
public:
    Link();
    ~Link();
    //头部插入
    void insert_head(ElementType data);
    //尾部插入
    void insert_tail(ElementType data);
    //查找结点,返回序号，如果不存在返回-1
    int find(ElementType data);
    //删除结点
    bool delete_node(int pos);
    //逆置
    void reverse();
    //打印链表
    void display();
    //打印提示信息
    void printhelp();
    //返回长度
    int size();
private:
    //头结点指针
    Node * pHead;
    //链表长度
    size_t iSize;
};

#endif

  1 #include "Link.h"
  2 
  3 Link::Link():pHead(NULL), iSize(0)
  4 {
  5     pHead = new Node;
  6     pHead->next = NULL;
  7 }
  8 
  9 Link::~Link()
 10 {
 11     Node * tmpNode = NULL;
 12     Node * p = pHead->next;
 13     while (p != NULL)
 14     {
 15         tmpNode = p->next;
 16         delete p;
 17         p = tmpNode;
 18     }
 19     delete tmpNode;
 20     tmpNode = NULL;
 21 
 22     delete pHead;
 23     p = NULL;
 24 
 25     iSize = 0;
 26 }
 27 
 28 /********************************
 29    链表头部插入
 30 *****************************/
 31 void Link::insert_head(ElementType data)
 32 {
 33     Node * tmpNode = new Node;
 34     tmpNode->data = data;
 35     
 36     tmpNode->next = pHead->next;
 37     pHead->next = tmpNode;
 38     
 39     iSize++;
 40 
 41     tmpNode = NULL;
 42 }
 43 
 44 /********************************
 45    链表尾部插入
 46 *****************************/
 47 void Link::insert_tail(ElementType data)
 48 {
 49     Node * tmpNode = new Node;
 50     tmpNode->data = data;
 51     tmpNode->next = NULL;
 52 
 53     Node * p = NULL;
 54     p = pHead;
 55     while (p->next != NULL)
 56     {
 57         p = p->next;
 58     }
 59 
 60     p->next = tmpNode;
 61     iSize++;
 62 
 63     //delete tmpNode;
 64     tmpNode = NULL;
 65     //delete p;
 66     p = NULL;
 67 }
 68 
 69 /********************************
 70    打印链表
 71 *****************************/
 72 void Link::display()
 73 {
 74     int count = 1;
 75     Node * tmpNode = NULL;
 76 
 77     tmpNode = pHead->next;
 78     while (tmpNode != NULL)
 79     {
 80         std::cout<<tmpNode->data<<" ";
 81         tmpNode = tmpNode->next;
 82 
 83         /********************************
 84         *  输出格式控制，每行10个
 85         **********************************/
 86         if (count % 10 == 0)
 87         {
 88             std::cout<<std::endl;
 89         }
 90         count++;
 91     }
 92     std::cout<<std::endl;
 93     tmpNode = NULL;
 94 }
 95 
 96 /********************************
 97    查找结点
 98 *****************************/
 99 int Link::find(ElementType data)
100 {
101     int pos = 0;
102     Node * tmpNode = NULL;
103 
104     tmpNode = pHead->next;
105     while (tmpNode != NULL)
106     {
107         if ( tmpNode->data == data)
108         {
109             return pos;
110         }
111         tmpNode = tmpNode->next;
112         pos++;
113     }
114 
115     tmpNode = NULL;
116     return -1;
117 }
118 
119 /********************************
120    删除结点
121 *****************************/
122 bool Link::delete_node(int pos)
123 {
124     //序号超过链表范围则报错退出
125     if (pos > iSize -1)
126     {
127         return false;
128     }
129     else
130     {
131         int k = 0;
132         Node * tmpNode = NULL;
133         tmpNode = pHead;
134         while ( k < pos)
135         {
136             tmpNode = tmpNode->next;
137             k++;
138         }
139         Node * p = NULL;
140         p = tmpNode->next;
141 
142         tmpNode->next = tmpNode->next->next;
143         delete p;
144         p = NULL;
145         iSize--;
146         return true;
147     }
148 }
149 
150 /********************************
151    返回链表的长度
152 *****************************/
153 int Link::size()
154 {
155     return iSize;
156 }
157 
158 /********************************
159    链表的逆置
160 *****************************/
161 void Link::reverse()
162 {
163     Node * preNode = NULL;
164     Node * curNode = NULL;
165     Node * afterNode = NULL;
166 
167     if ( iSize == 1 || iSize == 0)
168     {
169         return;
170     }
171     else if ( iSize >= 2)
172     {
173         preNode = pHead->next;
174         curNode = preNode->next;
175         afterNode = curNode->next;
176 
177         preNode->next = NULL;
178         
179         while (afterNode != NULL)
180         {
181             curNode->next = preNode;
182 
183             preNode = curNode;
184             curNode = afterNode;
185 
186             afterNode = afterNode->next;
187         }
188 
189         /********************************************************************
190         * 将当前结点的next置为前一个结点的过程是在每一次循环的开始，而最后一次
191         * 循环后无法进入下一次循环，需要补一次设置curNode的next的过程
192         *********************************************************************/
193         curNode->next = preNode;
194 
195         pHead->next = curNode;
196     }
197     preNode = NULL;
198     curNode = NULL;
199     afterNode = NULL;
200 }
201 
202 void Link::printhelp()
203 {
204     std::cout<<"*****************************************\n";
205     std::cout<<"当前链表为:"<<std::endl;
206     if (iSize == 0)
207         std::cout<<"NULL"<<std::endl;
208     else
209         display();
210     std::cout<<"输入你的选择:\n"
211         "0.从头部插入结点\n"
212         "1.从尾部插入结点\n"
213         "2.逆置链表\n"
214         "3.打印链表\n"
215         "4.删除结点\n"
216         "5.输出链表长度\n"
217         "6.查找结点\n"
218         "7.退出"<<std::endl;
219     std::cout<<"*****************************************\n";
220 }

 1 #include "Link.h"
 2 
 3 
 4 int main(int argc, char * argv[])
 5 {
 6     Link myLink;
 7     int pos;
 8     char choice;
 9     ElementType find_num = 3;
10     int delchoice;
11 
12     for (int i = 0 ; i < 48; i ++)
13     {
14         myLink.insert_head(rand()%100);
15     }
16 
17     myLink.printhelp();
18     std::cout<<"请选择:";
19     while ( std::cin>> choice)
20     {
21         switch(choice)
22         {
23         case ‘0‘:
24         case ‘1‘:
25             std::cout<<"\n暂无此功能!\n";
26             break;
27         case ‘2‘:
28             myLink.reverse();
29             std::cout<<"\n逆置成功!\n";
30             break;
31         case ‘3‘:
32             myLink.display();
33             std::cout<<"\n打印成功!\n";
34             break;
35         case ‘4‘:
36             std::cout<<"\n输入要删除的节点序号:";
37             std::cin>>delchoice;
38             if (myLink.delete_node(delchoice) == true)
39             {
40                 std::cout<<"\n删除成功!\n";
41             }
42             else 
43             {
44                 std::cout<<"\n删除失败!\n";
45             }
46             break;
47         case ‘5‘:
48             std::cout<<"链表长为:"<<myLink.size()<<std::endl;
49             break;
50         case ‘6‘:
51             goto exit;
52             break;
53         case ‘7‘:
54             goto exit;
55             break;
56         default:
57             break;
58         }
59         myLink.printhelp();
60         std::cout<<"请选择:";
61     }
62 
63 exit:    
64     system("pause");
65     return 0;
66 }