以下为《实验二 单某某的基本算法-实验 (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;
return L;
}
实验代码:
实验结构:
4.3 单某某的插入
如果在第i个位置插入结点,需要从单某某的头地址开始遍历,直到找到第i-1个位置的结点,然后在第i-1个结点之后插入新的结点,假如指针p指向第i-1个结点,指针s指向插入的结点,那么插入的过程如图3.3所示:
图3.3 单某某插入操作示意图
int ListInsert 内容过长,仅展示头部和尾部部分文字预览,全文请查看图片预览。 定值key作比较。
LNode* LocateValue(LinkList L, DataType x)
{
LNode *p;
p=L->next;
while((p!=NULL)&&(p->data!=x))
p=p->next;
return p;
}
实验代码:
实验结构:
5 结果分析与讨论
对于单某某的查找,无论是按序号查找还是按值查找,均是从头结点开始,利用结点的指针域找到后继结点,直到满足结束条件,所以单某某对数据元素的存取是顺序存储。
6 扩展与分析
定义一个计数函数countx(L),统计单某某中结点数据域大于某个数的结点个数。
7 注意事项与资源
在按序号查找的过程中,设单某某的长度为n,要查找表中第i个结点,仅当1≤i≤n时,输入的i值才是合法的。
实验2.3 单某某的应用
(类别:综合性)
1 实验要求与目的
掌握单某某的基本操作
掌握利用单某某的操作解决实际问题
2 实验环境与模块简介
本教程绝大部分实验环境基于 Windows 2000/xp及以上版本,选用的编程环境为Turbo C 2.0或以上兼容版本、 VC++6.0或以上兼容版本。
3 实验原理与背景知识
用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表。存储链表中结点的一组任意的存储单元可以是连续的,也可以是不连续的,甚至是零散分布在内存中的任意位置上的。
为了正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其直接后继结点的地址(或位置),称为指针(pointer)或链(link)。
4 实验步骤
本实验主要包括单某某的建立、查找和插入操作,实现两个非递减单某某的合并。
4.1 建立单某某
利用尾插法动态创建两个非递减的单某某。
4.2 单某某的合并
利用单某某的基本操作实现将两个值非递减有序的单某某合并成一个非递减有序的单某某。假如两个单某某为La和Lb,归并后的单某某为LC,算法包含三部分:
(1) 搜索:需要两个指针La和Lb搜索两个单某某;
(2) 比较:比较两个指针所指结点数据域中数据的大小;
(3) 将数值小的结点插入到LC中,如果La所指的结点数值小,则插入后,La=La->next,指向下一个结点,反之,Lb=Lb->next;
(4) 若一个链表比较完毕,另一个链表的剩余部分将整体插入到LC中。
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)
{
//按值排序的单某某LA,LB,归并为LC后也按值排序
Lc=La; //初始化 ,用La的头结点作为Lc的头结点
La=La->next;
Lb=Lb->next;
while(La&&Lb) //将pa 、pb结点按大小依次插入C中
{
if(La->datadata)
{
Lc->next=La;
Lc=La;
La=La->next;
}
else
{
Lc->next=Lb;
Lc=Lb;
Lb=Lb->next;
}
}
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)》的无排版文字预览,完整格式请下载
下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的,下载的文档就是什么样的。