单链表

2016-07-16  本文已影响11人  科学旅行者
以下代码仅供参考:
#include <iostream>
using namespace std;
typedef int Status;
struct node { //定义结点类型;
    Status data;
    node *next;
};
node *creat_linklist() { //创建链表;
    node *head;
    node *p = new node;
    head = p;
    p -> next = nullptr;
    head -> next = nullptr;
    return head;
}
node *push_front(node *head,Status num) { //头插法;
    node *p = new node;
    p -> data = num;
    p -> next = head -> next;
    head -> next = p;
    return head;
}
node *push_back(node *head,Status num) { //尾插法;
    node *p = new node;
    p -> data = num;
    node *ptail;
    for (ptail = head;ptail -> next;ptail = ptail -> next);
    ptail -> next = p;
    ptail = p;
    return head;
}
int statistic_element(node *head) { //统计链表中元素的个数;
    int len = 0;
    node *pi;
    for (pi = head -> next;pi;pi = pi -> next) {
        len++;
    }
    return len;
}
node *selectsort(node *head) { //链表的排序(元素从小到大);
    node *pi,*pj;
    node tnode;
    if (!head -> next) {
        return 0;
    }
    for (pi = head -> next;pi -> next;pi = pi -> next) {
        for (pj = pi -> next;pj;pj = pj -> next) {
            if (pi -> data > pj -> data) {
                tnode = *pi;
                *pi = *pj;
                *pj = tnode;
                node *tnode = pi -> next;
                pi -> next = pj -> next;
                pj -> next = tnode;
            }
        }
    }
    return head;
}
int find_node(node *head,Status num1) { //查找指定元素在链表中的个数;
    node *pi;
    int count = 0;
    //node *pr = nullptr;
    if (head -> next) {
        for (pi = head -> next;pi;pi = pi -> next) {
            if (pi -> data == num1) {
                count++;
            }
        }
    }
    return count;
}
node *delete_linklist(node *head,Status num1) { //删除链表中的结点;
    node *pi;
    node *pfront,*pnext;
    for (pi = head;pi -> next;pi = pi -> next) {
        if (pi -> next -> data == num1) {
            pfront = pi;
            pnext = pi -> next;
            break;
        }
    } 
    pfront -> next = pnext -> next;
    delete pi -> next;
    return head;
}
node *find_plast(node *head) { //查找链表中的尾元素;
    node *plast = nullptr;
    if (head -> next) {
        for (plast = head;plast -> next;plast = plast -> next);
    }
    return plast;
}
node *insert_selectedlinklist(node *head,Status num2) { //按顺序插入链表;
    node *p = new node;
    p -> data = num2;
    if (head -> next == nullptr) {
        head -> next = p;
        p -> next = nullptr;
    }
    else {
        node *plast = find_plast(head);
        if (num2 > plast -> data) {
            plast -> next = p;
            p -> next = nullptr;
        }
        else if (p -> data < head -> next -> data) {
            node *pt = head -> next;
            head -> next = p;
            p -> next = pt;
        }
        else {
            node *pfront,*pnext;
            node *pi;
            for (pi = head -> next;pi -> next;pi = pi -> next) {
                if (pi -> next -> data >= p -> data) {
                    pfront = pi;
                    pnext = pi -> next;
                    break;
                }
            }
            pfront -> next = p;
            p -> next = pnext;
        }
    }
    return head;
}
void output(node *head) { //输出链表中的元素;
    node *pi;
    for (pi = head -> next;pi;pi = pi -> next) {
        cout << pi -> data << " ";
    }
    cout << endl;
}
int main() { //测试;
    node *head = creat_linklist();
    output(head);
    Status num;
    cout << "input num:" << endl;
    while (cin >> num && num) {
        //head = push_front(head,num);
        head = push_back(head,num); 
    }
    output(head);
    int len = statistic_element(head);
    cout << "len = " << len << endl;
    head = selectsort(head);
    cout << "selected:" << endl;
    output(head);
    Status num1;
    cout << "What number do you want to delete?" << endl;
    cin >> num1;
    int count = find_node(head,num1);   
    if (count == 0) {
        cout << "This linklist hasn't this num!" << endl;
    }
    else {
        while (count--) {
            head = delete_linklist(head,num1);
        }
    }
    output(head);
    cout << "input number???" << endl;
    Status num2;
    while (cin >> num2 && num2) {
        head = insert_selectedlinklist(head,num2);
    }
    output(head);
    return 0;
}
上一篇 下一篇

猜你喜欢

热点阅读