数据结构链表题目

北邮数据结构

链表排序 数据结构实验报告

1. 实验要求

实验目的：

学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。 实验内容：

使用链表实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、冒泡排序 3、快速排序 4、简单选择排序 5、其他 要求：

1、测试数据分成三类：正序、逆序、随机数据

2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。

3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作） 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度 编写测试main()函数测试线性表的正确性

2. 程序分析

2.1 存储结构

双循环链表：

……..

2.2 关键算法分析

1.

1） 插入排序：

void clist::insertsort() { x=0;y=0;

北邮数据结构

int m; node*p=front->next->next; while(p!=front) { m=p->data ; x++; //用于计比较次数的计数器 if(m < p->prior->data ) { s=p->prior

链表C语言源代码

# include <stdio.h>

# include <malloc.h>

# include <stdlib.h>

typedef struct node

{

int date;//数据域

struct node *pnext;//指针域

}NODE,*PNODE;//NODE等价于struct node ，*PNODE等价于struct node *

PNODE create_list(void)

{

int len;//用来存放有效节点的个数

int i;

int val;//用来临时存放用户输入的节点值 //分配首地址 PNODE phead = (PNODE)malloc(sizeof(NODE)); if(NULL == phead) { printf("内存分配失败，程序终止！\n"); exit(-1); } PNODE ptail = phead; ptail->pnext =NULL; printf("请输入您要创建的链表的节点个数：len = "); scanf("%d",&len); if (0 == len) { printf("您输入的节点个数无效！\n"); } //创建链

数据结构实验报告

实验名称： 学生姓名： 班 级： 班内序号： 学 号： 日 期：

实验描述：使用链表实现下面各种排序算法，并进行比较。

排序算法： 1、插入排序 2、冒泡排序 3、快速排序 4、简单选择排序 5、其他 一．程序分析

1.存储结构：双向链表

2.关键算法分析：

a)插入排序：⒈从有序数列和无序数列{a2,a3，…，an}开始进行排序；

⒉处理第i个元素时（i=2,3，…，n），数列{a1,a2，…，ai-1}是已有序的，而数列{ai,ai+1，…，an}是无序的。用ai与ai-1，a i-2，…，a1进行比较，找出合适的位置将ai插入；

⒊重复第二步，共进行n-i次插入处理，数列全部有序。 b)冒泡排序：

1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

3.针对所有的元素重复以上的步骤，除了最后一个。

4.持续每次对越来越少的元素重复

2.3 线性表的链式存储和实现

2.3.1 线性链表 一 线性链表的概念

二 线性链表的基本操作算法

三 静态链表 四 线性链表的其它操作 2.3.2 循环链表 2.3.3 双向链表 一 双向链表的概念 二 双向链表的基本操作算法

2.3.1 线性链表

一、线性链表的概念 1、线性链表 用一组任意的存储单元存储线性表中的数据元素，对每个数据

元素除了保存自身信息外，还保存了直接后继元素的存储位置。

1010 1012 1014 1016 1018 1020 1022 1024 1026

a4 a3 a1

a2

NULL 1010

可以认为利用小的零散空间“串”起来，表示线性表 ，即把线性表的元素分散插入到系统所控制的零散空 间中，然后用“指针”串起来，组成一个有序的线性

1024 1014

表，用指针表示数据元素的逻辑关系。 元素的存储，可以是连续的，也可以不是连续的。 结点至少包括数据元素和指针两个区域。

2、线性链表结构图示

结点：数据元素及直接后继的存储位置组成一个数据元素的 存储结构，称为一个结点。

ai

链表

next

a1

next

a2

next

…

an

NULL

箭头：表示链域中的指针，即相应单元中保存的是它所指向结点的存储地址。

结点：数据元素及直接后继的存储位置组成一个

《数据结构》实验题目

实验一 客房管理（链表）

? 实验目的：熟练掌握单循环链表操作的基本算法实现。

? 实现功能：以带表头结点的单链表为存储结构，实现如下客房管理的设计要求。 ? 实验机时：8 ? 设计要求：

(1)定义客房链表结点结构类型，以Hotel和*HLink命名，数据域：客房名称roomN、标准价格Price、入住价格PriceL(默认值=标准价格*80%)、床位数Beds、入住状态State(空闲、入住、预订，默认值为空闲)，指针域：*next；

(2)实现创建客房基本情况链表函数void Build(HLink &H)，输入客房名称、标准价格、床位数，将入住价格、入住状态修改为默认值，建议用文件操作来输入数据；

(3)实现函数void updateH(HLink &H, int beds, char *state)，将床位数为beds的客房入住状态改为state；

(4)实现输出客房基本情况函数void Exp(HLink H)，输出所有客房的客房名称、标准价格、入住价格、床位数、入住状态；

(5)函数void Add(HLink &H)，将该链表中未入住的客房入住价格均加价20%；

(6)函数void upBed(

《数据结构》课程设计报告内容及其格式

《数据结构课程设计》报告

题目： 单链表操作

专业： 计算机科学与技术 班级：

单链表操作

针对带头结点的单循环链表，编写实现以下操作的算法函数。

《数据结构》课程设计报告内容及其格式

实现要求：

⑴ 单链表建立函数create：先输入数据到一维数组A[M]中，然后根据一维数组A[M]建立一个单循环链表，使链表中个元素的次序与A[M]中各元素的次序相同，要求该函数的时间复杂度为O(m)；

⑵ 定位查找函数Locate：在所建立的单循环链表中查找并返回值为key的第1个元素的结点指针；若找不到，则返回NULL；

⑶ 求出该链表中值最大和次大的元素值，要求该算法的时间复杂度为O(m)，最大和次大的元素值通过指针变量带回，函数不需要返回值；

⑷ 将链表中所有值比key(值key通过形参传入)小的结点作为值为key的结点前驱，所有值比key大的结点作为值为key的结点后继，并尽量保持原有结点之间的顺序，要求该算法的时间复杂度为O(m); ⑸ 设计一个菜单，具有上述处理要求和退出系统功能。

⒈ 本人完成的工作：

一、定义结构体：LNode 二、编写以下函数： （1）建

实验二：单链表的基本操作

一、【实验目的】

1、理解和掌握单链表的类型定义方法和结点生成方法。 2、掌握建立单链表和显示单链表元素的算法。 3、掌握单链表的查找、插入和删除算法 二、【实验内容】 1、建立一个整形数的单链表，手动输入10个数，并从屏幕显示单链表元素列表。 2、从键盘输入一个数，查找在以上创建的单链表中是否存在该数;如果存在，显示它的位置;如果不存在，给出相应提示。 3、删除上述单链表中指定位置的元素。

以下是程序部分代码，请调试并补充使之正确运行：

１．LinList.h

typedef struct Node {

DataType data; struct Node *next; } SLNode;

void ListInitiate(SLNode **head) /*初始化*/ {

/*如果有内存空间，申请头结点空间并使头指针head指向头结点*/ if((*head = (SLNode *)malloc(sizeof(SLNode))) == NULL) exit(1); (*head)->next = NULL; /*置链尾标记NULL */ }

int ListLength(SLNo

实验报告

课程名称数据结构

实验项目实验一线性表的生成与操作

题目一顺序表和链表的创建与基本操作

系 别___ _计算机学院 _ ______ 专 业____计算机大类_ __ 班级/学号__(1406/2014011288)_____ 学生姓名 _______(孙文学)_________ 实验日期 _（2015年10月19日） 成 绩 _______________________

指导教师黄改娟

实验题目：实验一线性表的生成与操作

------顺序表和链表的创建与基本操作（自己所选择实验题目，必

填）

一、 实验目的

1) 掌握线性表的顺序存储和链式存储结构； 2) 验证顺序表及链表的基本操作的实现；(验证)

3) 理解算法与程序的关系，能够将算法转换为对应程序； 4) 体会线性表在实际应用中能够解决的问题。（设计、综合）

二、 实验内容

1) 根据实验一题目列表，选定题目，说明题目的主要需求；

2) 结合所选定的题目，定义存储结构，并完成对应应用的线性表创建、插入、删除、

查找等基本操作的算法描述； 3) 程序编码实现，并获得运行结果。

三、 报告内容

1) 实验题目及主要存储结构定义

（提示：请根据所选定题目，描述

实验2链表的基本操作

一、 需求分析 1，初始化链表

2，调用插入函数建立一个链表 3，链表的插入和删除 4，链表元素的查找

4，将链表分为奇链表和偶链表 5，链表的逆置

二、 概要设计

1. 基础题

1) 编写链表基本操作函数

typedefstructlist

{

Int data;

Struct list* next }LIST;

LIST* InitList()

//初始化

//向链表指定位置插入元素

LIST* InsertList(LIST * L,intitem,intre)

LIST* InsertOrderList(LIST *L,intitem) //向有序链表指定位置插入元素 void FindList(LIST*L, intitem)//查找链表中的元素 void display(LIST *L)//显示链表

void divide(LIST* La, LIST *Lb)//拆分链表 LIST * turn(LIST *L)//转置链表

2) 调用上述函数实现下列操作，操作步骤如下。 A. 初始化链表

B. 调用插入函数建立一个链表 C. 在链表中寻找指定的元素 D. 在链表中删除指定值的元素 E. 遍历并输出链表

数据结构笔试题题目

一、 选择题

1. 下面哪种排序法对123456798在空间和时间上最优( )

A. 快速排序 B. 冒泡排序 C. 插入排序 D. 堆排序

2. 2.就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是（ ） A．堆排序〈 快速排序〈归并排序 B．堆排序〈 归并排序〈 快速排序 C．堆排序〉 归并排序 〉快速排序 D．堆排序 > 快速排序 > 归并排序 E．以上答案都不对

3. 3.一株二叉树的以某种遍历方式的序列为A、B、C、D、E、F、G，.若该二叉树的根结

点为E,则它的一种可能的前序遍历为____ ,相应的后序遍历为____

A. ECBADFG, BDCAFGE C. ECBADGF, EACBDGF

B. ECBADFG, EFACDBG D. EACBDGF, BDCAFGE

（常见题型，给出树的前序遍历和中序遍历，中序和后续遍历，推出二叉树） 4. 关于图和树，下面说法正确的是________

A. 树和图都允许有环

B. 图的深度遍历和广度遍历结果可能一样 C. 二叉树是每个节点都有两个孩子节点的树

D. 二叉树的前序遍历和后序遍历结果肯定不一样

5. 完成在双循