数据结构单链表上机报告

《数据结构》实验报告

实验二、单链表的应用

专 业 班 级 学 号 学生姓名 指导老师

河南科技大学管理学院

年 月 日

一、实验目的

熟练掌握线性表的链式存储结构的建立方法以及基本操作算法，并根据实际问题的要求，灵活运用。

二、实验内容

本次实验要求以班级学生信息作为管理对象，根据实验一建立班级学生信息线性表的链式存储结构，并练习使用单链表的基本操作算法，实现对班级学生信息的管理，包括学生信息的插入、学生信息的删除、学生信息的查询和学生信息线性表的输出。

三、完成情况

#include #include

//#define MAXSIZE 100

typedef struct{

char num[8];/*学号*/ char name[9];/*姓名*/ char gender[3];/*性别*/ int score;/*成绩*/ }DataType;

typedef

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

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

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

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

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

题目： 单链表操作

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

单链表操作

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

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

实现要求：

⑴ 单链表建立函数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

数据结构上机报告

课程：有向图中求各顶点之间的最短路径

算法设计：

现设一个矩阵F，用来记录路径长度。初始时，顶点Vi到顶点Vj的最短路径长度F[i][j]=weight[i][j],即弧上的权值。若不存在,则F[][]=∞（程序中用1000表示）。此时，把矩阵F记做F0。F0考虑到了有弧相连直接到达的路径，但这个长度不是最短长度，所以要进行探索。

① 让路径经过V0（第一个顶点），并比较路径（Vi,Vj）和路径（Vi,V0,Vj）的长度，去较短的作为最短路径长度。其中，路径（Vi,V0,Vj）的长度等于路径（Vi,V0）和（V0,Vj）长度之和，即F[i][j]=F[i][0]+F[0][j]。把此时得到的矩阵F记做F1，F1考虑到了各项点间除直接到达的路径外，其他经过V0的路径，只取其中最短的作为最短路径长度。

② 在F1的基础上让路径经过第二个顶点V1，依照?的方法求得最短路径长度，得到F2。

③ 以此类推，经过n次试探，将n个顶点都考虑到路径之中，此时求得最短路径长度。

例：有向图如下：

求任意两个顶点之间的最短路径长度

程序运行如下：

程序代码：

#include using namespace std;

#def

1． 已知长度为n的线性表L采用顺序存储结构，编写一个时间复杂度为O(n)，空间复杂度

为O(1)的算法，该算法删除线性表中所有值为item的数据元素。

2． 用顺序表A和B表示的两个线性表，元素的个数分别为m和n，若表中数据都是由小

到大顺序排列的，且这(m+n)个数据中没有相重的。设计一个算法将些两个线性表合并成一个，仍是数据由小到大排列的线性表，存储到另一个顺序表C中。

3． 已知线性表{a0,a1,……,an-1}按顺序存储，且每个元素都是不相等的整数。设计把所有

的奇数移到所有的偶数前边的算法（要求时间最少，辅助空间最少）。 4． 输入一组整型元素序列，建立单链表。

5． 写出在带头结点的单向链表l中删除第i个结点的算法。

6． 编写算法,将带头结点的单链表拆分成一个奇数链表和一个偶数链表。

7． 设C={a1,b1,a2,b2,……,an,bn}为一线性表，采用带头结点的Hc单链表存放，编写一个

就地算法，将其拆分成两个线性表，使得：A={a1,a2,…..,an} C={b1,b2,….,bn} 8． 编写出判断带头结点的双向循环链表L是否对称相等的算法。 9． 设计一算法，将一带头结点的数据域依次为a1,a2,…,an(n>=3)的单

顺序表

#include using namespace std; template void ins_sq_LList(T*v,int m,int*n,int i,T b) {int k; if(*n==m) {cout<<\ if(i>*n)i=*n+1; if(i<1)i=1; for(k=*n;k>=i;k--) v[k]=v[k-1]; v[i-1]=b; *n=*n+1; return; }

#include using namespace std; template class sq_LList {private: int mm; int nn; T * v; public: sq_LList(){mm=0;nn=0;return;} sq_LList(int);

void prt_sq_LList(); int flag_sq_LList();

void ins_sq_LList(int,T); void del_sq_LList(int); };

template

sq_LList(T)::sq_LList(int m) {mm=m;

v=new

实验报告

课程名称数据结构

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

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

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

指导教师黄改娟

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

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

填）

一、 实验目的

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

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

二、 实验内容

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

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

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

三、 报告内容

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

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

吉林大学

数据结构实验报告

班级： 姓名： 学号：

姓名 实验项目 实验性质 学号 第一次上机 □演示性实验□验证性实验 ?操作性实验□综合性实验 实验地点 计算机楼A108 机器编号 2017年11月24日 时 指导教师 江丽 实验时间 分 一、实验目的及要求 题目1： 线性表、堆栈、队列相关算法的实验验证 [实验目的] 验证单链表及其上的基本操作。 [实验内容及要求] 1、 定义单链表类、链式栈类、顺序队列类。 2、 实验验证如下算法的正确性、各种功能及指标： 1）单链表插入操作：分别在当前结点后、表头、表尾插入值为x的结点； 2）单链表删除操作：分别删除表头结点、表尾结点和当前结点的后继结点； 3）查找操作：查找值为x的元素在单链表中出现的位置（是链表中的第几个元素）； 4）压栈和弹栈操作； 5）出队和入队操作（顺序存储） 3、 为便于观察程序的运行结果，设计的输出函数能在输出设备上以图形或表格或其它直观的形式输出计算结果。例如可将链表输出成如下形式： [1]?[2] ?[3] ?[4] ?[5] 4、 测试程序时，对所有输入变量取遍各种有代表性的值。 5、 为了增强程序的可读性，程序中要有适当的注释。 题目2（选做题）

数据结构上机答案

1.1顺序线性表的基本操作 #include #include #define OK 1 #define ERROR 0

#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define ElemType int

typedef struct { int *elem,length,listsize; }SqList;

int InitList_Sq(SqList &L) { L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; }

int Load_Sq(SqList &L) { int i; if(L.length==0) printf(\ else { printf(\ for(i=0;i

int ListInsert_Sq(SqList &L,int i,int e) { if(i<1||i>L.length+1) return ERROR; ElemType *newbase,