数据结构课留的作业...

首先定义结构体：

    typedef struct Node {
        ElemType data;    //define ElemType int
        struct Node *next;
    };

创建链表

void Create(Node *&l) {  //尾插法
        string x;
        l->next = NULL; //头结点
        Node *s,*r = l;  //r为表尾指针,
        cin >> x;
        while (x.compare("+")!=0) {
            s = new Node;  //创建一个新结点s
            s->data = atoi(x.c_str());   
            r->next = s;   //让表尾指针指向结点s
            r = s;         //让r=s，用于循环中的反复使用，最终r就是最后一个结点
            cin >> x;
        }
        r->next = NULL;    //让表尾指针指向NULL 
    }

输出链表中的数据

void Print(Node *&l) { 
        Node *p = l->next;    //让p指向l的首元结点
        while (p != NULL) {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
    }

删除链表

void Delete(Node *&l) {
        Node *p = l;
        Node *q = l->next;  //保存后继指针，防止断链
        while (p!= NULL ) {
            delete p;
            p = q;
            if (q != NULL) {
                q = q->next;
            }
        }
    }

关于delete函数参考：

https://www.runoob.com/cplusplus/cpp-dynamic-memory.html
https://blog.csdn.net/u012936940/article/details/80919880

采用头插法对链表内的数据进行排序

void Sort(Node *&l) { 
    Node *p = l->next, *pre;    //p为l的首元结点    
    Node *r = p->next;          // r为p的首元结点
    p->next = NULL;             //让p的首元结点为NULL
    p = r;                      //让p=r  也就是让p从l的第二个结点开始
    while (p!=NULL) {
        r = p->next;            //让r为p的首元结点
        pre = l;                
        while (pre->next != NULL&&pre->next->data >= p->data) {    //一直循环到pre的next指向的数据小于p指向的数据为止
            pre = pre->next;             
        }
        p->next = pre->next;   //将p插入pre之后，也就是让比较小的数在前面
        pre->next = p;
        p = r;                 //p等于p插入pre之前的next，也就是循环又从p的下一个结点开始了
    }
}

将两个链表连接起来

void Link(Node *&l1,Node *&l2){
        Node *p=l1;
        Node *q=l2;
        while (p->next!=NULL){   //找到尾结点
            p=p->next;
        }
        p->next=q->next;         //让尾结点指向后一个链表的首元结点
    }

主函数

int main() {
        Node *l1 = new Node; //新建结点，并且创建指针
        Node *l2 = new Node;
        Create(l1);
        Create(l2);
        Print(l1);
        Print(l2);
        Link(l1,l2);
        Sort(l1);
        Print(l1);
        Delete(l1);
    }

运行示例

上面的排序是忽略了重复数字的存在的，下面是考虑了重复数字的情况

移除重复数字

void Remove_Repetition(Node *&l){
        Node *p=l->next;
        while (p->next!=NULL){    //如果不到尾结点就一直走下去
            while (p->data ==p->next->data&&p->next!=NULL){        //如果相邻两个数据一直相等就进行循环
                if (p->next->next!=NULL){                     //若p后面第二个结点不为空，让p的下一个结点为此结点，相当于去除了p后面第一个重复的数据
                    p->next=p->next->next;
                } else{
                    p->next=NULL;       //若为空就让p变为尾结点
                    return;             //跳出循环
                }
            }
            p=p->next; 
        }
    }

主函数

int main() {
        Node *l1 = new Node;
        Node *l2 = new Node;
        Create(l1);
        Create(l2);
        Print(l1);
        Print(l2);
        Link(l1,l2);
        Sort(l1);
        Remove_Repetition(l1);
        Print(l1);
        Delete(l1);
    }

运行示例

其他

寻找链表中最大的数值

int Search_max(Node *&l){
        Node *p=l->next;
        int x=p->data;
        while (p->next!=NULL){
            if (x<p->next->data){
                x=p->next->data;
            }
            p=p->next;
        }
        return x;
    }

运行示例：

移除链表中某个结点

void Remove_point(Node *&l,int n){
        Node *p=l;
        for (int i = 1; i <n ; i++) {
        p=p->next;
        }
        p->next=p->next->next;
    }

运行示例：

在一个链表第n个位置插入一个结点

void insert_point(Node *&l1,Node *&l2,int n){
        Node *p=l1;
        Node *q=l2->next;    //让q为首元结点
        for (int i = 0; i < n -1  ; i++) {
            p=p->next;
        }
        q->next=p->next;
        p->next=q;
    }

运行示例：