首页 > 其他分享 >数据结构实验2——表的应用

数据结构实验2——表的应用

时间：2024-10-30 18:15:42浏览次数：7  
标签：pre 单链 int NULL next 实验 应用 数据结构 LinkNode

一、实验目的

掌握单链表的基本算法设计。

二、实验内容

1、实现单链表各种基本运算的算法。

2、在main()函数中，调用头插法（CreateListF()函数）和尾插法（CreateListR()函数），创建新链表，并输出结果进行比较。

3、对任务1或者2中创建的某一个单链表{A1,B1,A2,B2,...,An,Bn}，编写一个算法将它拆分为两个单链表，分别为：{A1,A2,...,An}和{Bn,...,B2,B1}。（要求：算法时间复杂度为O(n)，空间复杂度为O(1)）

4、创建的某一个 无序 单链表{A1, B1, A2, B2, ... , An, Bn}，编写一个算法将它拆分为A，B 两个单链表，分别为两个链表进行升序排序。（要求：算法时间复杂度为O(n^{2})，空间复杂度为O(1)）

三、算法设计

1、实现单链表各种基本运算的算法。

#include <iostream>
#include <stdio.h>
#include <malloc.h>
using namespace std;
typedef char ElemType;
typedef struct LNode
{
    ElemType data;
    struct LNode * next;
}LinkNode;

void CreateListF(LinkNode*&L,ElemType a[],int n)
{
    LinkNode * s;
    L=(LinkNode *)malloc(sizeof(LinkNode));
    L->next=NULL;
    for (int i=0;i<n;i++)
    {
        s=(LinkNode*)malloc(sizeof(LinkNode));
        s->data=a[i];
        s->next=L->next;
        L->next=s;
    }
}


void CreateListR(LinkNode *&L,ElemType a[],int n)
{
    LinkNode *s,*r;
    L=(LinkNode *)malloc(sizeof(LinkNode));
    L->next=NULL;
    r=L;
    for(int i=0;i<n;i++)
    {
        s=(LinkNode*)malloc(sizeof(LinkNode));
        s->data=a[i];
        r->next=s;
        r=s;
    }
    r->next=NULL;
}


void InitList(LinkNode *&L)
{
    L=(LinkNode *)malloc(sizeof(LinkNode));
    L->next=NULL;
}


void DestroyList(LinkNode *&L)
{
    LinkNode *pre=L,*p=pre->next;
    while (p!=NULL)
    {
        free(pre);
        pre=p;
        p=pre->next;
    }
    free(pre);
}


bool ListEmpty(LinkNode *L)
{
    return(L->next==NULL);
}


int ListLength(LinkNode *L)
{
    int i=0;
    LinkNode *p=L;
    while(p->next!=NULL)
    {
        i++;
        p=p->next;
    }
    return(i);
}



void DispList(LinkNode *L)
{
    LinkNode *p=L->next;
    while(p!=NULL)
    {
        printf("%c",p->data);
        p=p->next;
    }
     printf("\n");
}

bool GetElem(LinkNode*L ,int i,ElemType &e)
{
    int j=0;
    LinkNode *p=L;
    if (i<=0) return false;
    while(j<i && p!=NULL)
    {
        j++;
        p=p->next;
    }
    if(p==NULL)
        return false;
    else
    {
        e=p->data;
        return true;
    }
}


int LocateElem(LinkNode *L,ElemType e)
{
    int i=1;
    LinkNode *p=L->next;
    while(p!=NULL && p->data!=e)
    {
        p=p->next;
        i++;
    }
    if(p==NULL)
        return(0);
    else
        return(i);
}



bool ListInsert(LinkNode *&L,int i ,ElemType e)
{
    int j=0;
    LinkNode *p=L,*s;
    if(i<=0) return false;
    while (j<i-1 && p!=NULL)
    {
        j++;
        p=p->next;
    }
    if (p==NULL)
        return false;
    else
    {
        s=(LinkNode*)malloc(sizeof(LinkNode));
        s->data=e;
        s->next=p->next;
        p->next=s;
        return true;
    }
}


bool ListDelete(LinkNode *&L,int i,ElemType &e)
{
    int j=0;
    LinkNode *p=L,*q;
    if(i<=0) return false;
    while(j<i-1 && p!=NULL)
    {
        j++;
        p=p->next;
    }
    if(p==NULL)
        return false;
    else
    {
        q=p->next;
        if(q==NULL)
            return false;
        e=q->data;
        p->next=q->next;
        free(q);
        return true;
    }
}

int main()
{
    LinkNode *h;
    ElemType e;
    printf("单链表的基本运算如下：\n");
    printf(" （1）初始化单链表h\n");
    InitList(h);
    printf(" （2）依次采用尾插法插入a,b,c,d,e元素\n");
    ListInsert(h,1,'a');
    ListInsert(h,2,'b');
    ListInsert(h,3,'c');
    ListInsert(h,4,'d');
    ListInsert(h,5,'e');
    printf(" （3）输出单链表h:");
    DispList(h);
    printf(" （4）单链表h的长度：%d\n",ListLength(h));
    printf(" （5）单链表h为%s\n",(ListEmpty(h)?"空":"非空"));
    GetElem(h,3,e);
    printf(" （6）单链表h的第3个元素：%c\n",e);
    printf(" （7）元素a的位置：%d\n",LocateElem(h,'a'));
    printf(" （8）在第4个元素位置上插入f元素\n");
    ListInsert(h,4,'f');
    printf(" （9）输出单链表h：");
    DispList(h);
    printf(" （10）删除h的第3个元素\n");
    ListDelete(h,3,e);
    printf(" （11）输出单链表h:");
    DispList(h);
    printf(" （12）释放单链表h\n");
    DestroyList(h);
    return 1;
}

2、在main()函数中，调用头插法（CreateListF()函数）和尾插法（CreateListR()函数），创建新链表，并输出结果进行比较。

int main()
{
  LinkNode *M;
  LinkNode *N;
  printf("单链表\n");
  char a[]={'a','b','c','d','e','f'};
  InitList(M);
  InitList(N);
  CreateListR(M,a,6);  //尾插法
  CreateListF(N,a,6);  //头插法
  DispList(M);
  DispList(N);
  return 1;
}

3、对任务1或者2中创建的某一个单链表{A1,B1,A2,B2,...,An,Bn}，编写一个算法将它拆分为两个单链表，分别为：{A1,A2,...,An}和{Bn,...,B2,B1}。（要求：算法时间复杂度为O(n)，空间复杂度为O(1)）

void chaifen(LinkNode *&L,LinkNode *&M,LinkNode *&N)
{
    LinkNode *p=L->next,*q,*r1;
    M=L;
    r1=M;
    N=(LinkNode*)malloc(sizeof(LinkNode));
    N->next=NULL;
    while(p!=NULL)
    {
        r1->next=p;
        r1=p;
        p=p->next;
        q=p->next;
        p->next=N->next;
        N->next=p;
        p=q;
    }
    r1->next=NULL;
}

int main()
{
  LinkNode *h;
  LinkNode *M;
  LinkNode *N;
  printf("单链表");
  char a[]={'a','b','c','d','e','f'};
  InitList(h);
  InitList(M);
  InitList(N);
  CreateListR(h,a,6);
  DispList(h);
  chaifen(h,M,N);
  DispList(M);
  DispList(N);
  return 1;
}

4、创建的某一个 无序 单链表{A1, B1, A2, B2, ... , An, Bn}，编写一个算法将它拆分为A，B 两个单链表，分别为两个链表进行升序排序。（要求：算法时间复杂度为O(n^{2})，空间复杂度为O(1)）

void chaifen(LinkNode *&L,LinkNode *&M,LinkNode *&N)
{
    LinkNode *p=L->next,*q,*r1;
    M=L;
    r1=M;
    N=(LinkNode*)malloc(sizeof(LinkNode));
    N->next=NULL;
    while(p!=NULL)
    {
        r1->next=p;
        r1=p;
        p=p->next;
        q=p->next;
        p->next=N->next;
        N->next=p;
        p=q;
    }
    r1->next=NULL;
}

void chaifenjingxu(LinkNode *&L,LinkNode *&M,LinkNode *&N)
{
    LinkNode *p=L->next,*q,*r1,*r2;
    LinkNode *a,*pre,*b;
    M=L;
    r1=M;
    N=(LinkNode*)malloc(sizeof(LinkNode));
    N->next=NULL;
    r2=N;
    while(p!=NULL)
    {
        r1->next=p;
        r1=p;
        p=p->next;
        q=p->next;
        r2->next=p;
        r2=p;
        p=q;
    }
    r1->next=NULL;
    r2->next=NULL;
    a=M->next->next;
    M->next->next=NULL;
    while(a!=NULL)
    {
        b=a->next;
        pre=M;
        while(pre->next!=NULL && pre->next->data<a->data)
            pre=pre->next;
        a->next=pre->next;
        pre->next=a;
        a=b;
    }
    a=N->next->next;
    N->next->next=NULL; 
    while(a!=NULL)
    {
        b=a->next;
        pre=N;
        while(pre->next!=NULL && pre->next->data<a->data)
            pre=pre->next;
        a->next=pre->next;
        pre->next=a;
        a=b;
    }
}


int main()
{
  LinkNode *h;
  LinkNode *M;
  LinkNode *N;
  printf("单链表");
  int a[]={1,3,6,5,4,7};
  InitList(h);
  InitList(M);
  InitList(N);
  CreateListR(h,a,6);
  DispList(h);
  chaifenjingxu(h,M,N);
  DispList(M);
  DispList(N);
  return 1;
}

四、实验结果

1、实现单链表各种基本运算的算法。

2、在main()函数中，调用头插法（CreateListF()函数）和尾插法（CreateListR()函数），创建新链表，并输出结果进行比较：头插法是将数组的元素从单链表的表头进行插入，最终实现的是元素逆序排列；尾插法将数组的元素从单链表额表尾进行插入，能够实现元素的顺序排列，即跟数组顺序相同。

3、对任务1或者2中创建的某一个单链表{A1,B1,A2,B2,...,An,Bn}，编写一个算法将它拆分为两个单链表，分别为：{A1,A2,...,An}和{Bn,...,B2,B1}。（要求：算法时间复杂度为O(n)，空间复杂度为O(1)）的思路：将一个单链表拆分成两个单链表，第一个单链表取原链表的奇数项，利用尾插法实现顺序排列；第二个单链表取原链表的偶数项，利用头插法实现逆序排列。

4、创建的某一个 无序 单链表{A1, B1, A2, B2, ... , An, Bn}，编写一个算法将它拆分为A，B 两个单链表，分别为两个链表进行升序排序。（要求：算法时间复杂度为O(n^{2})，空间复杂度为O(1)）的思路：在上一题的基础上进行改进，先利用尾插法将一个单链表分成两个顺序排列的单链表。以其中一个单链表为例，将其拆分成两个部分，从有序表的表头进行比较，遍历原单链表所有余下节点，实现升序排列。另一个表同理操作，升序排列，最后输出。

五、总结

1、顺序表与单链表的类型声明不同点在于：

顺序表的类型声明需要包括存放顺序表的长度，有固定的空间大小；单链表的声明需要指向后继节点。  

2、顺序表和单链表ListInsert()函数的不同之处在于：

顺序表：顺序表插入元素时，需要改变表的长度，并将插入元素序号以及之后元素都进行后移操作；单链表：单链表插入元素时，需要找到需要插入位置的后一个元素，将插入元素的后继改成这个元素，并将前一个元素的后继指向插入元素，即完成元素插入。

3、实验问题：出现了空指针异常的问题。在附加题一开始的时候只能实现奇数个元素的拆分，偶数个元素数组的最后一个元素无法分类，后面对算法进行改进，规避了该问题。

标签：pre,单链,int,NULL,next,实验,应用,数据结构,LinkNode
From： https://blog.csdn.net/BYBONNIR/article/details/143371454

相关文章

  • Prompt工程八大技巧：打造高效LLM应用
    文章目录前言一、明确认知过程边界二、明确指定输入/输出三、实施防护栏四、与人类认知过程对齐（一）模仿人类思维的步骤分解（二）多步骤/代理的应用五、利用结构化数据六、精心设计上下文数据七、保持简单八、不断迭代零基础入门AI大模型1.学习路线图2.视频教程3.......
  • 溯源与取证分析实验
       作业题目溯源取证分析作为网络攻防过程中重要环节，准确找到攻击者的入侵线索(尤其是攻击突破口、攻击IP地址、域名、工具等信息)，对于企业或者团队安全运营团队来说都是必备技能。常规攻击取证过程中往往会结合流量、Web访问日志、终端系统或者软件日志等信息来挖掘或者推......
  • 嗅探与欺诈实验
       作业题目包嗅探和欺骗是网络安全中的两个重要概念；它们是网络通信中的两大威胁。能够理解这两种威胁对于理解网络中的安全措施至关重要。有许多包嗅探和欺骗工具，如Wireshark、Tcpdump、Netwox等。其中一些工具被安全专家以及攻击者广泛使用。能够使用这些工具对学生来说......
  • TCP攻击实验
       作业题目本实验的学习目标是让学生获得有关漏洞以及针对这些漏洞的攻击的第一手经验。聪明人从错误中学习。在安全教育中，我们研究导致软件漏洞的错误。研究过去的错误不仅有助于学生理解为什么系统容易受到攻击，为什么“看似良性”的错误会变成灾难，以及为什么需要许多安......
  • 4、片元着色器之光线步进及其和兰伯特光照模型的结合应用
    1、什么是光线步进？光线步进(RayMarching)是一种用于渲染和追踪的技术，尤其在处理体积数据和隐式表面时非常有效。与传统的光线追踪方法不同，光线步进不直接计算光线与物体的交点，而是通过在光线上逐步前进来寻找相交的表面。这种方法通常用于场景中存在复杂几何体或体积效果......
  • 缓冲区溢出实验
       作业题目本实验的学习目标是让学生将从课堂上学到的有关缓冲区溢出漏洞的知识进行实践，从而获得有关该漏洞的第一手经验。缓冲区溢出是指程序试图将数据写入预先分配的固定长度缓冲区边界之外的情况。恶意用户可利用此漏洞改变程序的流控制，甚至执行任意代码。此漏洞是由......
  • shellcode编写实验
       作业题目shellcode广泛用于许多涉及代码注入的攻击中。编写shellcode是相当有挑战性的。虽然我们可以很容易地从互联网上找到现有的shellcode，但是能够从头开始编写我们自己的shellcode总是令人兴奋的。shellcode中涉及到几种有趣的技术。本实验室的目的是帮助学生理解这......
  • 环境变量与set-uid实验
       作业题目本实验室的学习目标是让学生了解环境变量如何影响程序以及系统行为。环境变量是一组动态命名值，可以影响正在运行的进程将在计算机上运行。大多数操作系统都使用它们，因为它们是1979年引入Unix。尽管环境变量会影响程序行为，但它们是如何实现的这一点很多程序员都......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99