【c语言数据结构】单链表的基本操作

一、目的与要求
1.复习C程序调试、运行的基本操作方法。
2.熟练掌握编辑、编译、连接和运行C 程序的方法。
3.掌握单链表的定义、创建、插入和删除操作程序实现。
二、实验内容
1.定义单链表结构体，获取数据元素。
2.创建链表以输入-1 结束。
3.在第i个节点处插入数据元素X。
4.删除第i个节点。
5.显示链表中的数据元素。
6逆序显示链表中的数据元素

链表节点结构体的定义：

typedef struct Node
{
    int data;
    struct Node *next;
}Node;

创建节点：

Node *create_Node(int n)
{
    Node *node = (Node *)malloc(sizeof(Node));
    if(!node)
    {
        printf("内存不足!\n");
        return NULL;
    }
    node->data = n;
    node->next = NULL;
    return node;
} 

创建单链表：

Node *create_link()
{
    int n=0;
    Node *head = create_Node(0);
    if(!head)
        exit(-1);
    Node *tail;
    tail = head;
    scanf("%d", &n);
    while(n != -1)
    {
        Node *pnew = create_Node(n);
        if(!pnew)
            break;
        tail->next = pnew; //旧节点的指针指向新节点
        tail= pnew;       //新节点变为旧节点
        scanf("%d",&n);
    }
    printf("Input End\n");
    return head;
}

删除单链表：

//删除单链表,释放内存空间
void freeLink(Node *head)
{
    //1.判断链表是否为空，如果为空，则返回
    if(head==NULL)
        return;
    //2.如果非空，则逐个节点释放
    Node *p, *q;
    p = head;
    while(p->next!=NULL)
    {
        q = p->next;
        p->next = q->next;
        free(q);
    }
    free(head);
}

遍历单链表-----正序输出：

//遍历单链表--正序输出
void displayLink(Node *head)
{
    //1.判断链表是否为空，如果为空，则直接返回
    if(!head)
        return;
    //2.打印每一个节点信息
    Node *p = head->next;
    printf("链表正序输出为：\n");
    while(p!=NULL)
    {
        printf("%d\n", p->data);
        p = p->next;
    }
}

遍历单链表-----逆序输出：

//遍历单链表--逆序输出
void Inverse_displayLink(Node *head)
{
    // 1.判断链表是否为空，如果为空，则直接返回
    if (!head)
        return;
    // 2.打印每一个节点信息
    Node *p = head->next;
    int count = 0,i;
    int a[50] = {0};
    printf("链表倒序输出为：\n");
    while (p != NULL)
    {
        a[count] = p->data;
        p = p->next;
        count++;    
    }
    for (i = count-1; i>=0;i--)
    {
        printf("%d\n", a[i]);
    }
}

在指定位置插入节点：

//在指定位置插入节点
void insertNode(Node *head,Node *pnew,int i)
{
    //1.判断链表是否为空，如果为空，则拒绝插入
    if(!head)
        return;
    //2.判断插入的节点是否为空，如果为空，则拒绝插入
    if(!pnew)
        return;
    //3.遍历链表，找到插入位置
    Node *p = head;
    int n = 0;
    for (n = 0; n < i && p->next != NULL;n++)
    {
        p = p->next;
    }
    //4.插入新节点
    pnew->next = p->next;
    p->next = pnew;
}

在指定位置删除节点：

//在指定位置删除节点
void deleteNode(Node *head,int i)
{
    //1.判断链表是否为空，如果为空，则拒绝删除,直接返回
    if(!head)
        return;
    if(i<=0)
        return;
    //2.遍历链表，找到需要删除的位置
    Node *p = head,*q;
    int n = 0;
    for (n = 0; n < i && p->next != NULL;n++)
    {
        p = p->next;
    }
    if(!p)
        return;
    //3.删除找到的节点
    q = p->next;
    p->next = q->next;
    free(q);
}

全部代码：

/*
实现的内容有：
1.定义单链表结构体
2.创建链表以输入-1结束
3.在第i个节点处插入数据元素x
4.删除第i个节点
5.显示链表中的数据元素
6.逆序显示链表中的数据元素
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
    int data;
    struct Node *next;
}Node;

Node *create_Node(int n)
{
    Node *node = (Node *)malloc(sizeof(Node));
    if(!node)
    {
        printf("内存不足!\n");
        return NULL;
    }
    node->data = n;
    node->next = NULL;
    return node;
} 

Node *create_link()
{
    int n=0;
    Node *head = create_Node(0);
    if(!head)
        exit(-1);
    Node *tail;
    tail = head;
    scanf("%d", &n);
    while(n != -1)
    {
        Node *pnew = create_Node(n);
        if(!pnew)
            break;
        tail->next = pnew; //旧节点的指针指向新节点
        tail= pnew;       //新节点变为旧节点
        scanf("%d",&n);
    }
    printf("Input End\n");
    return head;
}
//删除单链表,释放内存空间
void freeLink(Node *head)
{
    //1.判断链表是否为空，如果为空，则返回
    if(head==NULL)
        return;
    //2.如果非空，则逐个节点释放
    Node *p, *q;
    p = head;
    while(p->next!=NULL)
    {
        q = p->next;
        p->next = q->next;
        free(q);
    }
    free(head);
}
//遍历单链表--正序输出
void displayLink(Node *head)
{
    //1.判断链表是否为空，如果为空，则直接返回
    if(!head)
        return;
    //2.打印每一个节点信息
    Node *p = head->next;
    printf("链表正序输出为：\n");
    while(p!=NULL)
    {
        printf("%d\n", p->data);
        p = p->next;
    }
}
//遍历单链表--逆序输出
void Inverse_displayLink(Node *head)
{
    // 1.判断链表是否为空，如果为空，则直接返回
    if (!head)
        return;
    // 2.打印每一个节点信息
    Node *p = head->next;
    int count = 0,i;
    int a[50] = {0};
    printf("链表倒序输出为：\n");
    while (p != NULL)
    {
        a[count] = p->data;
        p = p->next;
        count++;    
    }
    for (i = count-1; i>=0;i--)
    {
        printf("%d\n", a[i]);
    }
}
//在指定位置插入节点
void insertNode(Node *head,Node *pnew,int i)
{
    //1.判断链表是否为空，如果为空，则拒绝插入
    if(!head)
        return;
    //2.判断插入的节点是否为空，如果为空，则拒绝插入
    if(!pnew)
        return;
    //3.遍历链表，找到插入位置
    Node *p = head;
    int n = 0;
    for (n = 0; n < i && p->next != NULL;n++)
    {
        p = p->next;
    }
    //4.插入新节点
    pnew->next = p->next;
    p->next = pnew;
}
//在指定位置删除节点
void deleteNode(Node *head,int i)
{
    //1.判断链表是否为空，如果为空，则拒绝删除,直接返回
    if(!head)
        return;
    if(i<=0)
        return;
    //2.遍历链表，找到需要删除的位置
    Node *p = head,*q;
    int n = 0;
    for (n = 0; n < i && p->next != NULL;n++)
    {
        p = p->next;
    }
    if(!p)
        return;
    //3.删除找到的节点
    q = p->next;
    p->next = q->next;
    free(q);
}
int main()
{
    Node *head = create_link();
    displayLink(head);
    Inverse_displayLink(head);
    printf("插入新节点后的单链表\n");
    int n = 0;
    scanf("%d", &n);
    Node *pnew = create_Node(n);
    insertNode(head, pnew, 2);
    displayLink(head);
    printf("删除指定位置的节点之后的单链表\n");
    deleteNode(head, 2);
    displayLink(head);
    freeLink(head);
    system("pause");
    return 0;
}