JZTXT

单链表的应用

发布时间 2023-09-27 08:11:54作者: 捞起月亮的小北

单链表的应用

实验时间：第3，4周

实验目的：掌握单链表的数据类型定义、头插法建单链表（算法2.11）、尾插法建单链表、输出单链表中的元素、插入单链表元素，删除单链表指定节点的元素

实验要求：

  1. 认真阅读和掌握教材上和本实验相关的内容和算法。
  2. 上机将相关算法实现。
  3. 实现上面实验目的要求的功能，并能进行简单的验证

实验代码框架：

//实验二

#include <malloc.h>#include <stdio.h> 

//线性表的单链表存储结构：结点结构及自定义数据类型……

//从表头插入新结点创建带表头结点的单链表，对应教材P30算法2.11。

void CreateListFromHead(LinkList &L, int n){    ……}

 //从表尾插入新结点创建带表头结点的单链表。

void CreateListFromTail(LinkList &L, int n){    ……}

//在屏幕上输出单链表中的元素

void PrintList(LinkList L){    ……} 

//销毁单链表

void DestroyList(LinkList &L){    ……}

//在第i个位置之前插入元素

 //删除第i个元素 

//主函数

void main(){    int n; //表长    printf("请输入要建立的线性表的长度:\n");    scanf("%d",&n);        

//头插法建立单链表

LinkList L = NULL;    

printf("\n开始头插法建单链表，请逆序输入线性表的各元素...\n");    

CreateListFromHead(L,n);    

printf("下面输出刚建立的线性表中元素:\n");   

 PrintList(L);   

插入元素 

打印链表 

删除元素  

打印链表。

}

代码实现

#include <malloc.h>
#include <stdio.h>

//线性表的单链表存储结构：结点结构及自定义数据类型
typedef struct LNode
{
    int data;
    struct LNode *next;
} LNode, *LinkList;

//从表头插入新结点创建带表头结点的单链表，对应教材P30算法2.11。
void CreateListFromHead(LinkList &L, int n)
{
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;

    printf("请输入线性表的各元素:\n");
    for (int i = 0; i < n; i++)
    {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        scanf("%d", &s->data);
        s->next = L->next;
        L->next = s;
    }
}

//从表尾插入新结点创建带表头结点的单链表。
void CreateListFromTail(LinkList &L, int n)
{
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;

    printf("请输入线性表的各元素:\n");
    LNode *tail = L;
    for (int i = 0; i < n; i++)
    {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        scanf("%d", &s->data);
        s->next = NULL;
        tail->next = s;
        tail = s;
    }
}

//在屏幕上输出单链表中的元素
void PrintList(LinkList L)
{
    LNode *p = L->next;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

//销毁单链表
void DestroyList(LinkList &L)
{
    LNode *p = L;
    while (p != NULL)
    {
        LNode *temp = p;
        p = p->next;
        free(temp);
    }
    L = NULL;
}

//在第i个位置之前插入元素
void InsertElement(LinkList L, int i, int data)
{
    if (i < 1)
    {
        printf("Invalid position.\n");
        return;
    }

    LNode *p = L;
    int count = 0;
    while (p != NULL && count < i - 1)
    {
        p = p->next;
        count++;
    }

    if (p == NULL)
    {
        printf("Invalid position.\n");
        return;
    }

    LNode *newNode = (LNode *)malloc(sizeof(LNode));
    newNode->data = data;
    newNode->next = p->next;
    p->next = newNode;
}

//删除第i个元素
void DeleteElement(LinkList L, int i)
{
    if (i < 1)
    {
        printf("Invalid position.\n");
        return;
    }

    LNode *p = L;
    int count = 0;
    while (p != NULL && count < i - 1)
    {
        p = p->next;
        count++;
    }

    if (p == NULL || p->next == NULL)
    {
        printf("Invalid position.\n");
        return;
    }

    LNode *delNode = p->next;
    p->next = delNode->next;
    free(delNode);
}

//主函数
int main()
{
    int n; //表长
    printf("请输入要建立的线性表的长度:\n");
    scanf("%d", &n);

    //头插法建立单链表
    LinkList L1 = NULL;
    printf("\n开始头插法建单链表，请逆序输入线性表的各元素...\n");
    CreateListFromHead(L1, n);
    printf("下面输出刚建立的线性表中元素:\n");
    PrintList(L1);

    //尾插法建立单链表
    LinkList L2 = NULL;
    printf("\n开始尾插法建单链表，请顺序输入线性表的各元素...\n");
    CreateListFromTail(L2, n);
    printf("下面输出刚建立的线性表中元素:\n");
    PrintList(L2);

    //插入元素
    int insertPos, insertData;
    printf("\n请输入要插入的位置和元素:\n");
    scanf("%d %d", &insertPos, &insertData);
    InsertElement(L2, insertPos, insertData);
    printf("插入元素后的线性表:\n");
    PrintList(L2);

    //删除元素
    int deletePos;
    printf("\n请输入要删除的位置:\n");
    scanf("%d", &deletePos);
    DeleteElement(L2, deletePos);
    printf("删除元素后的线性表:\n");
    PrintList(L2);

    //释放链表内存
    DestroyList(L1);
    DestroyList(L2);

    return 0;
}

实验效果

image-20230927080518183