对链表相关知识的整理

花了两周整理链表的相关知识

以一个主函数和多个函数的形式来呈现

/*链表合集*/
#include<iostream>
#include<cstdlib>
using namespace std;
typedef struct node{
    int a;
    struct node *next;
} Node;
//排序
void Sort(Node*head){
    node *p, *s, *pt;
    p = head;
    s = p->next;
    while (p->next != NULL){
        while(s->next != NULL){
            if(p->next > s->next){
                pt->next = p->next;
                p->next = s->next;
                s->next = pt->next;
            }
            s = s->next;
        }
        p = p->next;
        pt = s;
    }
}

Node *add(Node*head,int num){//在表尾插入元素
    Node *p = NULL, *pr = head;
    p = (Node *)malloc(sizeof(Node));
    if(p == NULL){
        cout << "no enough memory to allocate";
    }
    if(head == NULL){
        head = p;
    }else{
        while(pr->next != NULL){
            pr = pr->next;
        }
        pr->next = p;
    }
    p->a = num;
    p->next = NULL;
    return head;
}
//打印链表
void show(Node*head){
    Node *p = head;
    while(p != NULL){
        cout << p->a << " ";
        p = p->next;
    }
}

void del(Node*head){//释放申请的内存空间
    Node *p = head, *pr = NULL;
    while(p != NULL){
        pr = p;
        p = p->next;
        free(pr);
    }
}
//删除链表里某一个节点
Node* Delete(Node*head,int num){
    Node *p = head, *pr = head;
    //pr是目标元素前一个节点
    if(head == NULL){
        cout << "empty table";
        return head;//空表退出
    }
    while(num != p->a && p->next != NULL){
        //未找到且不是空表
        pr = p;
        p = p->next;//p直接指向当前节点的下一节点
    }
    if(num == p->a){//找到了待删除节点
        if(p == head){
            head = p->next;//直接让头指针指向待删除结点p的下一节点
        }else{
            pr->next = p->next;
            //前一节点的指针域指向待删除结点的下一节点
        }
        free(p);
    }else{//到表尾且没找到
        cout << "not found";
    }
    return head;
}
//在链表里插入元素
Node* insert(Node*head,int num){
    Node *pr = head, *p = head, *temp = NULL;
    p = (Node *)malloc(sizeof(Node));
    if(p == NULL){
        cout << "no enough memory";
        exit(0);
    }
    p->next = NULL;//待插入节点指针域为空指针
    p->a = num;//待插入节点的数值域为num
    if(head == NULL){
        head = p;//若原链表为空表，待插入节点为头节点
    }else{//若为非空
    //若未找到待插入节点的位置且未找到表尾则继续找
        while(pr->a < num && pr->next != NULL){
            temp = pr;//temp保存当前节点的下一节点
            pr = pr->next;//pr指向当前节点的下一节点
        }
        if(pr->a >= num){
            if(pr == head){//若在头节点前插入新节点
                p->next = head;
            //将新节点的指针域指向原链表的头节点
                head = p;//让head指向新节点
            }else{//在链表中部插入新节点
            //进行排序
                pr = temp;
                p->next = pr->next;
                pr->next = p;
            }
        }else{//若在表尾插入新节点
            pr->next = p;//让末节点的指针域指向新节点
        }
    }
    return head;//返回插入新节点猴的链表头指针head的值
}

int main()
{
    int num;
    char ch;
    struct node *head = NULL;
    do{
        cin >> num;
        if(num >= 0){
            head = add(head, num);
            show(head);
        }
        if(num % 5 ==0){
            cout << "continue?(y/n)";
            cin >> ch;
            if((ch == 'n') || (ch == 'N')){
                break;
            }
        }//避免死循环
    } while (num >= 0);
    del(head);
}