单链表实现

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <stdlib.h>
  4 
  5 typedef int ElemType;
  6 typedef struct ListNode{
  7     struct ListNode* next;
  8     ElemType data;
  9 }*LinkList, ListNode;
 10 
 11 //  初始化链表
 12 LinkList init_list(LinkList &list)
 13 {
 14     list->next = NULL;
 15     list->data = 0;
 16     return list;
 17 }
 18 
 19 // * 建立链表
 20 // * 头插法
 21 // * 王道 P.27
 22 // *
 23 
 24 LinkList create_list(LinkList &list)
 25 {
 26     ListNode *n_node;
 27     ElemType x;
 28     list = (LinkList)malloc(sizeof(ListNode));
 29     list->next = NULL;
 30     list->data = 0;
 31     scanf("%d", &x);
 32     while(x != 9999)                             ///输入9999表示结束
 33     {
 34         n_node = (LinkList)malloc(sizeof(ListNode));
 35         n_node->data = x;
 36 
 37         n_node->next = list->next;               ///核心的地方
 38         list->next = n_node;
 39         scanf("%d", &x);
 40     }
 41     return list;
 42 }
 43 
 44 
 45 // * 尾插法
 46 // * 王道 P.28
 47 // *
 48 
 49 LinkList create_list2(LinkList &list)
 50 {
 51     ElemType x;
 52     list = (LinkList)malloc(sizeof(ListNode));
 53     ListNode *n_node, *rear = list;             ///rear 指向链表尾
 54     list->next = NULL;
 55     list->data = 0;
 56     scanf("%d", &x);
 57     while(x != 9999)                            ///输入9999表示结束
 58     {
 59         n_node = (LinkList)malloc(sizeof(ListNode));
 60         n_node->data = x;
 61 
 62         rear->next = n_node;                    ///核心的地方
 63         rear = n_node;
 64         scanf("%d", &x);
 65     }
 66     rear->next = NULL;
 67     return list;
 68 }
 69 
 70 
 71 // * 打印链表的信息
 72 // *
 73 
 74 void show_list(LinkList list)
 75 {
 76     printf("
show list
");
 77     //因为加了头结点，所以跳过头结点
 78     list = list->next;
 79     while(list != NULL)
 80     {
 81         printf("%d ", list->data);
 82         list = list->next;
 83     }
 84     return;
 85 }
 86 
 87 
 88 // * 按序号查找结点的值
 89 // * 王道 P.28
 90 // *
 91 
 92 ListNode* get_elem(LinkList list, int i)
 93 {
 94     int j = 1;
 95     ListNode* tmp = list->next;
 96     if(i == 0)
 97         return list;
 98     if(i < 0)
 99         return NULL;
100     while(tmp && i > j)
101     {
102         tmp = tmp->next;
103         j++;
104     }
105     return tmp;
106 }
107 
108 // * 按值查找表结点
109 // * 王道 P.29
110 // *
111 
112 ListNode* locate_elem(LinkList list, ElemType x)
113 {
114     ListNode* tmp = list->next;
115     while(tmp && tmp->data != x)
116         tmp = tmp->next;
117     return tmp;
118 }
119 
120 
121 // * 在指定位置上插入一个结点，返回当且要插入结点的指针
122 // * 王道 P.29
123 // *
124 
125 ListNode* insert_node(LinkList &list, int position, ElemType x)
126 {
127     int i = 1;
128     ListNode* p = list->next;
129     while(i < position)
130     {
131         p = p->next;
132         i++;
133     }
134     ListNode* tmp = (LinkList)malloc(sizeof(ListNode));
135     tmp->data = x;
136     tmp->next = p->next;                                    //这是核心
137     p->next = tmp;
138     return tmp;
139 }
140 
141 // * 删除一个结点
142 // * 王道 P.30
143 // *
144 
145 ElemType delete_node(LinkList &list, int position)
146 {
147     int i = 1;
148     ListNode* p = list->next;
149     ListNode* pre = list;
150 
151     while(i < position)
152     {
153         pre = p;
154         p = p->next;
155         i++;
156     }
157     i = p->data;
158     pre->next = p->next;
159     free(p);
160     return i;
161 }
162 
163 // * 求链表的=长度
164 // * 王道 P.31
165 // *
166 
167 int list_length(LinkList list)
168 {
169     int len = 0;
170     ListNode* tmp = list->next;
171     while(tmp)
172     {
173         tmp = tmp->next;
174         len++;
175     }
176     return len;
177 }
178 /*
179  * swap function
180  * 用来交换两个结点的信息
181  * */
182 void swap(ListNode *n1, ListNode *n2)
183 {
184     ElemType  tmp;
185     tmp = n1->data;
186     n1->data = n2->data;
187     n2->data = tmp;
188 }
189 /*
190  * 单链表的插入排序
191  * http://www.cnblogs.com/Camilo/p/3927912.html
192  * 基本思想：假设前面n-1个结点有序，将第n个结点插入到前面结点的适当位置，使这n个结点有序。
193  * 实现方法：
194  * 将链表上第一个结点拆下来，成为含有一个结点的链表(head1)，其余的结点自然成为另外一个链表(head2)，此时head1为含有一个结点的有序链表；
195  * 将链表head2上第一个结点拆下来，插入到链表head1的适当位置，使head1仍有序，此时head1成为含有两个结点的有序链表；
196  * 依次从链表head2上拆下一个结点，插入到链表head1中，直到链表head2为空链表为止。最后，链表head1上含所有结点，且结点有序。
197  * */
198 LinkList insert_sort(LinkList list)
199 {
200     ListNode *list2, *current, *p, *q;
201     if(!list || !(list->next))
202         return  list;
203 
204     //第一次拆分
205     list2 = list->next;
206     list->next = NULL;
207 
208     while(list2)
209     {
210         current = list2;
211         list2 = list2->next;
212         //寻找插入位置，插入位置为p和q之间
213         for(p = NULL, q = list; q && q->data <= current->data; p = q, q = q->next);
214 
215         if(q == list)
216             list = current;  //current插入到最前面
217         else
218             p->next = current;
219 
220         current->next = q;
221     }
222     return list;
223 }
224 
225 /*
226  * 单链表冒泡排序
227  * 还是自己理解的东西，写自己的风格超级舒服
228  * */
229 LinkList bubble_sort(LinkList list)
230 {
231     if(!list || !(list->next))
232         return  list;
233     ListNode *p, *q;
234     for(p = list; p != NULL; p = p->next)
235     {
236         for(q = p; q->next != NULL; q = q->next)
237         {
238             if(q->data > q->next->data)
239                 swap(q, q->next);
240         }
241     }
242     return list;
243 }
244 /*
245 int main()
246 {
247     LinkList list;
248     //list = create_list(list);
249     LinkList pNode = create_list2(list);
250     list = pNode;
251     show_list(list);
252 
253 //    ListNode* get_elem1 = get_elem(list, 3);
254 //    printf("
%d 
", get_elem1->data);
255 //
256 //    ListNode* locate_elem1 = locate_elem(list, 4);
257 //    printf("
this is a pointer : %d
", locate_elem1->data);
258 //
259 //    insert_node(list, 3, 9999);
260 //    show_list(list);
261 //
262 //    delete_node(list, 3);
263 //    show_list(list);
264 
265     printf("
the list`s length is %d
", list_length(list));
266 
267     //bubble_sort(list);
268     insert_sort(list);
269     show_list(list);
270 
271     return 0;
272 }
273 
274 */

#include <iostream>

using namespace std;

class Node
{
public:
    int data;
    Node *next;
};

class LinkList
{
public:
    LinkList();

    ~LinkList();
    void CreateLinkList(int n); 
    void TravalLinkList();
    int GetLength();
    bool IsEmpty();
    Node *Find(int data);
    void InsertElemAtEnd(int data);
    void InsettElemHead(int data);
    void DeleteElemAtEnd();

private:
    Node *head;

};

LinkList::~LinkList() {
    delete head;
}

LinkList::LinkList() {
    head = new Node();
    head->data = 0;
    head->next = NULL;
}

void LinkList::CreateLinkList(int n) {
    Node *p_new, *p_tmp;
    p_tmp = head;
    if(n <= 0){
        cout << "node cnt error" << endl;
    }
    for(int i=0;i<n;++i)
    {
        p_new = new Node();
        cout << "input n nums" << endl;
        cin >> p_new->data;
        p_new->next = NULL;
        p_tmp->next = p_new;
        p_tmp = p_new;
    }
}

void LinkList::TravalLinkList() {
    if(head == NULL || head->next == NULL)
        cout << "empty list" << endl;

    Node *p_tmp = head;
    while(p_tmp->next != NULL)
    {
        p_tmp = p_tmp->next;
        cout << p_tmp->data << " ";
    }
}

int LinkList::GetLength() {

    int cnt = 0;
    Node *p_tmp = head->next;
    while(p_tmp !=NULL)
    {
        cnt++;
        p_tmp = p_tmp->next;
    }

    return cnt;
}

bool LinkList::IsEmpty() {
    if(head->next == NULL)
        return true;
    return false;
}

Node *LinkList::Find(int data) {

    Node *p = head;
    if(p == NULL)
    {
        cout << "llist empty" << endl;
        return NULL;
    }

    while(p->next != NULL)
    {
        if(p->data == data)
            return p;
        p = p->next;
    }


    return nullptr;
}

void LinkList::InsertElemAtEnd(int data) {
    Node *node_n = new Node();
    node_n->next = NULL;
    node_n->data = data;
    Node *p = head;

    if(head == NULL)
        head = node_n;
    else
    {
        while(p->next != NULL)
            p=p->next;
        p->next = node_n;
    }
}

void LinkList::InsettElemHead(int data) {
    Node *node_n = new Node();
    node_n->data = data;
    Node *p=head;

    if(head == NULL)
        head = node_n;
    node_n->next = p->next;
    p->next = node_n;
}

void LinkList::DeleteElemAtEnd() {
    Node *p = head;
    Node *p_tmp = NULL;

    if(p->next != NULL)
        cout << "llist is empty" << endl;
    else{
        while(p->next != NULL)
        {
            p_tmp = p;
            p = p->next;
        }

        delete p;
        p = NULL;
        p_tmp->next = NULL;
    }
}

int main() {

    LinkList llist;
    int n;
    cin >> n;
    llist.CreateLinkList(n);
    cout << llist.GetLength() << endl;

    cout << llist.IsEmpty() << endl;
    cout << llist.Find(12)->data << endl;
    llist.InsertElemAtEnd(11);
    llist.InsettElemHead(21);
    llist.DeleteElemAtEnd();

    llist.TravalLinkList();
    return 0;
}

View Code