自己实现单向链表

佚名 6年前 (2019-04-14) 随笔 1972人围观抢沙发百度已收录

实现一个单向链表的：创建、插入、删除、排序（冒泡）、转置、搜索中间节点

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

typedef struct student
{
    int data;
    struct student *next;
} node;

//创建链表
node *create()
{
    node *head;
    node *p;
    node *s;

    int x;
    int cycle = 1;

    head = (node*)malloc(sizeof(node));
    p = head;

    while (cycle)
    {
        printf("input data:");
        scanf("%d", &x);
      if (x != 0)    
        {
            s = (node*)malloc(sizeof(node));
            s->data = x;
            p->next = s;
            p = s;
        }
        else
        {
            cycle = 0;
        }
    }

    p->next = NULL;
    p = head;
    head = head->next;
    free(p);
    p = NULL;
    return head;
}

//计算链表长度
int length(node *head)
{
    int n = 0;
    node *p;
  p = head;    
    while (p != NULL)
    {
        p = p->next;
        n++;
    }

    printf("%d\n", n);
    return n;
}

//显示
void show(node *head)
{
    node *p;
    int n;
    n = length(head);
    p = head;

    if (head == NULL)
    {
        return;
    }

    while(p != NULL)
    {
        printf("data:%d ", p->data); 
        p = p->next;
    }
    printf("\n");
}



//插入节点
node *insert (node *head, int num)
{
    node *p0;
    node *p1;
    node *p2;
    p1 = head;
    p0 = (node*)malloc(sizeof(node));
    p0->data = num;

    while (p0->data > p1->data && p1->next != NULL)
    {
        p2 = p1;
        p1 = p1->next;
    }

    if (p0->data <= p1->data)
    {
        if (head == p1)
        {
            p0->next = p1;
            head = p0;
        }
        else
        {
            p2->next = p0;
            p0->next = p1;
        }
    }
    else
    {
        p1->next = p0;
        p0->next = NULL;
    }

    return head;
}

//删除链表中指定节点
node *del(node *head, int num)
{
    node *p1;  
    node *p2;
    p1 = head;

    while (num != p1->data && p1->next != NULL)
    {
        p2 = p1;
        p1 = p1->next;
    }

    if (num == p1->data)
    {
        if(p1 == head)
        {
            head = p1->next;
            free(p1);
        }
        else
        {
      p2->next = p1->next;
            free(p1);
        }
    }
    else
    {
        printf("not found data to delete\n");
    }

    return head;

}

//链表升序排序（冒泡算法）
node *sort(node *head)
{
    node *p;
    int n;
    int temp;


    if (head == NULL || head->next == NULL)
    {
        return head;
    }

    n = length(head);
    for (int j=1; j<n; ++j)
    {
        p = head;
        for(int i=0; i<n-j; ++i)
        {
            if (p->data > p->next->data)
            {
                temp = p->data;
                p->data = p->next->data;
                p->next->data = temp;
            }

            p = p->next;
        }
    }

    return head;

}

//链表转置
node *reverse(node *head)
{
    node *p1;
    node *p2;
    node *p3;
    if (head == NULL || head->next == NULL)
    {
        return head;
    }

    p1 = head;
    p2 = p1->next;

    while(p2 != NULL)
    {
        p3 = p2->next;
        p2->next = p1;
        p1 = p2;
        p2 = p3;
    }

    head->next = NULL; //转置完后头节点成为尾节点
    head = p1;         //转置完后尾节点成为头节点

    return head;

}

//搜索链表中间节点
//算法：以步长2和1单位同时遍历链表，步长2到末尾，步长1到中间
void searchmid(node *head, node *mid)
{
    node *p1;
    node *p2;
    p1 = head;
    p2 = head;

    while (p1->next != NULL && p1->next->next != NULL)
    {
        p1 = p1->next;
        mid = p1;
        p2 = p2->next->next;
    }

    printf("mid:%d\n", mid->data);
}

int main()
{
    node *head = create();
    int len = length(head);
    show(head);

    head = insert(head, 2);
    show(head);

    head = del(head, 2);
    show(head);

    head = sort(head);
    show(head);
    
    head = reverse(head);
    show(head);

    node *mid;
    searchmid(head, mid);
}