以下为《实验二 单某某的基本算法-实验 (1)》的无排版文字预览，完整格式请下载

下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。

实 验 报 告

实验二 单某某的基本算法

姓 名：

王某某



指导教师：

崔某某 助教



学 院：

信息科学与***



专 业：

计算机科学与技术（云计算）



班 级：

2020级云计算本科1班



完成日期：

2021年04月15日





实验二 单某某的基本算法

指导老师：崔某某

学生：王某某

学号：***0137

2020年04月15日

实验2.1 单某某的基本操作

(类别:验证性)

1 实验要求与目的

掌握链表的存储结构

掌握链表的各种基本操作

2 实验环境与模块简介

本教程绝大部分实验环境基于 Windows 2000/xp及以上版本，选用的编程环境为Turbo C 2.0或以上兼容版本、 VC++6.0或以上兼容版本。

3 实验原理与背景知识

用一组任意的存储单元存储线性表的数据元素，可以是零散分布在内存中的任意位置上的。链表中结点的逻辑次序和物理次序不一定相同。利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素。

每个数据元素，除存储本身信息外，还需存储其直接后继的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。

4 实验步骤

本实验三主要包括单某某的建立、插入和删除操作。

4.1 设计单某某存储结构

建立单某某的存储结构。单某某存储结构描述如下：

typedef struct Lnode {

DataType data; //数据域

struct Lnode *next; //指针域

}Lnode, *LinkList; // *LinkList为Lnode类型的指针

图3.1 单某某结点的结构示意图

4.2 建立单某某

建立单某某（尾插法）：建立链表的过程是一个动态生成的过程，从空表状态，依次建立各元素结点，并逐个插入，每次均在链表表尾插入。为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。具体算法描述如下：

从一个空表开始，重复读入数据：

?生成新结点；

将读入数据存放到新结点的数据域中；

将该新结点插入到链表的表尾，即新结点插在尾指针的后面；

直到读入数据结束为止。

图3.2 建立单某某插入节点前

图3.2 插入节点p后

LinkList createListR ( void )

{

int i=0;

DataType ch;

LinkList L= (LinkList) malloc (sizeof (LNode)); //建立表头结点

LNode *q, *r = L;

printf("请输入%d个整数构建单某某：\n",N);

for(i=0;idata = ch; //建立新结点

r ->next = q; r =q; //插入到表末端

}

r ->next = NULL;

内容过长，仅展示头部和尾部部分文字预览，全文请查看图片预览。 }

Lc->next = La?La:Lb ; //插入剩余段

} //MergeList_L，O(n1+n2)

实验代码：

实验结构：

5 结果分析与讨论

若La，Lb两个链表的长度分别是m，n，则链表合并的时间复杂度为O(m+n) 。

6 扩展与分析

定义一个逆置函数diverse(L)，把链表进行逆置。在主程序中调用该函数，分析操作结果。

7 注意事项与资源

通过上述程序处理后，LC指针并不是指向归并后新单某某的头结点，La和Lb也不指向两个链表的表头， LC和La共用一个头结点，所以在调用该函数时，需要备份La的头结点或头指针，用于最后输出LC所指链表。

[文章尾部最后300字内容到此结束,中间部分内容请查看底下的图片预览]

以上为《实验二 单某某的基本算法-实验 (1)》的无排版文字预览，完整格式请下载

下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。