实验二 链表求集合的并集

实验二单链表求集合的并集一．实验目的

1．熟悉数据结构的设计过程，并实现的数据结构链表的设计。

2．用设计的链表实现求集合的并集。

3．设计单链表、单向循环链表、双向链表和双向循环链表。

二、实验内容

1．设计带头结点的单链表：设计头文件LinkList.h，其内容如下：

typedef struct node

{

elemtype data;

node *next;

}Lnode,*LinkList;

void InitList(LinkList &L)

{

L=new Lnode;

L->next=NULL;

}

Lnode *Locate(LinkList L,elemtype e)

{

}

void Insert(LinkList L,int i,elemtype e)

{

}

void Delete(LinkList L,int i)

{

}

void create(LinkList &L,elemtype *a,int n)

{

InitList(L);

for(int i=n-1;i>=0;i--)

{

Lnode *p;

p=new Lnode;

p->data=a[i];

p->next=L->next;

L->next=p;

}

}

void display(LinkList L)

{

Lnode *p;

p=L->next;

while(p)

{

cout<data<<" ";

p=p->next;

}

cout<

}

2．利用单链表求集合的并集：设计测试文件test.cpp，其内容如下：

#include "iostream.h"

#include "stdio.h"

typedef int elemtype;

#include "LinkList.h"

void main()

{

LinkList L;

}

3．思考：

1．带头结点的单向循环链表如何实现。

2．不带头结点的单链表和循环链表如何实现。

3．带头结点的有序链表如何实现？

4．带头结点的双向链表和双向循环链表如何实现？

链表实验报告

C语言程序设计实验报告 实验一：链表的基本操作一·实验目的 1.掌握链表的建立方法 2.掌握链表中节点的查找与删除 3.掌握输出链表节点的方法 4.掌握链表节点排序的一种方法 5.掌握C语言创建菜单的方法 6.掌握结构化程序设计的方法 二·实验环境 1.硬件环境：当前所有电脑硬件环境均支持 2.软件环境：Visual C++6.0 三.函数功能 1. CreateList // 声明创建链表函数 2.TraverseList // 声明遍历链表函数 3. InsertList // 声明链表插入函数 4.DeleteTheList // 声明删除整个链表函数 5. FindList // 声明链表查询函数 四．程序流程图 五．程序代码 #include #include typedef int Elemtype; typedef int Status; typedef struct node//定义存储节点 { int data;//数据域 struct node *next;//结构体指针 } *linklist,node;//结构体变量，结构体名称 linklist creat (int n)//创建单链表 { linklist head,r,p;//定义头指针r,p,指针 int x,i; head=(node *)malloc(sizeof(node));//生成头结点

r=head;//r指向头结点 printf("输入数字:\n"); for(i=n;i>0;i--)//for 循环用于生成第一个节点并读入数据{ scanf("%d",&x); p=(node *)malloc(sizeof(node)); p->data=x;//读入第一个节点的数据 r->next=p;//把第一个节点连在头结点的后面 r=p;//循环以便于生成第二个节点 } r->next=0;//生成链表后的断开符 return head;//返回头指针 } void output (linklist head)//输出链表 { linklist p; p=head->next; do { printf("%3d",p->data); p=p->next; } while(p); printf("\n") } Status insert ( linklist &l,int i, Elemtype e)//插入操作 { int j=0; linklist p=l,s; while(jnext; ++j; } if(!p || j>i-1) return -1; else { s=(node *)malloc(sizeof(node)); s->data=e; s->next=p->next; p->next=s; return 1; } } Status delect ( linklist &l,int i, Elemtype &e)//删除操作 { int j=0; linklist p=l,q; while(jnext) { p=p->next; ++j; } if(!p->next || j>i-1) return -1;

数据结构实验集合的并交差运算实验报告记录

数据结构实验集合的并交差运算实验报告记录

————————————————————————————————作者：————————————————————————————————日期：

实验报告 实验课程：数据结构 实验项目：实验一集合的并交差运算专业：计算机科学与技术 班级： 姓名： 学号： 指导教师：

目录一、问题定义及需求分析 （1）实验目的 （2）实验任务 （3）需求分析 二、概要设计： (1)抽象数据类型定义 (2)主程序流程 (3) 模块关系 三、详细设计 (1)数据类型及存储结构 (2)模块设计 四、调试分析 (1)调试分析 (2)算法时空分析 (3)经验体会 五、使用说明 (1)程序使用说明 六、测试结果 (1)运行测试结果截图 七、附录 (1)源代码

一、问题定义及需求分析 （1）实验目的 设计一个能演示集合的并、交、差运算程序。 （2）实验任务 1)采用顺序表或链表等数据结构。 2)集合的元素限定为数字和小写英文字母。 （3）需求分析： 输入形式为:外部输入字符串； 输入值限定范围为:数字和小写英文字母； 输出形式为：字符集； 程序功能:计算两个集合的交、并、差以及重新输入集合功能； 二、概要设计： (1)抽象数据类型定义： 线性表 (2)主程序流程： 调用主菜单函数初始化两个线性表作为集合给两个集合输入数据输出集合数据元素信息另初始化两个线性表创建选择功能菜单界面通过不同选项调用不同功能函数在每个功能函数里面加结束选择功能，实现循环调用功能菜单 计算完毕退出程序； （3）模块关系： 主菜单 差运算并运算交运算新建集合结束/返回 结束 三、详细设计 抽象数据类型定义： typedef struct{ ElemType *elem; int length; int listsize;

(完整版)数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 1 ．实验目的 （1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法； （2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求 （1 ）认真阅读和掌握和本实验相关的教材内容。 （2 ）认真阅读和掌握本章相关内容的程序。 （3 ）上机运行程序。 （4 ）保存和打印出程序的运行结果，并结合程序进行分析。 （5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include// 库头文件------ 动态分配内存空间 typedef int elemtype;// 定义数据域的类型 typedef struct linknode// 定义结点类型 { elemtype data;// 定义数据域 struct linknode *next;// 定义结点指针 }nodetype; 2）创建单链表

nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"<> d; if(d==0) break;// 以0 表示输入结束 if(i==1)// 建立第一个结点 { h=(nodetype*)malloc(sizeof(nodetype));// 表示指针h h->data=d;h->next=NULL;t=h;//h 是头指针 } else// 建立其余结点 { s=(nodetype*) malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s;//t 始终指向生成的单链表的最后一个节点

单链表实验报告

计算机与信息技术学院综合性、设计性实验报告 一、实验目的 (1)熟悉顺序表的创建、取值、查找、插入、删除等算法，模块化程序设计方法。 二、实验仪器或设备 (1)硬件设备：CPU为Pentium 4 以上的计算机，内存2G以上 (2)配置软件：Microsoft Windows 7 与VC++6.0 三、总体设计(设计原理、设计方案及流程等) 设计原理： 单链表属于线性表，线性表的存储结构的特点是：用一组任意存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。因此，对于某个元素来说，不仅需要存储其本身的信息，还需要存储一个指示其直接后继的信息。 设计方案： 采用模块化设计的方法，设计各个程序段，最终通过主函数实现各个程序段的功能。设计时，需要考虑用户输入非法数值，所以要在程序中写入说可以处理非法数值的代码。 设计流程： 1. 引入所需的头文件； 2. 定义状态值； 3. 写入顺序表的各种操作的代码； 写入主函数，分别调用各个函数。在调用函数时，采用if结构进行判断输 入值是否非法，从而执行相应的程序 四、实验步骤(包括主要步骤、代码分析等) #include // EOF(=A Z 或F6),NULL #in clude // srand( ) ,rand( ),exit (n) #in clude // malloc( ),alloc( ),realloc() 等 #in clude // INT_MAX 等 #in clude #in clude #in clude // floor(),ceil( ),abs() #in clude // cout,ci n #in clude // clock( ),CLK_TCK,clock_t #defi ne TRUE 1 #defi ne FALSE 0 #defi ne OK 1 #defi ne ERROR 0 #defi ne INFEASIBLE -1

数据结构实验报告

数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include #include #include #include "Stack.h"//栈的头文件，没有用上 typedefintElemType; //数据类型 typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType data; //数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree; intInsertBST(BiTree&T,int key){//插入二叉树函数 if(T==NULL) { T = (BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1; } else if(keydata){ InsertBST(T->lChild,key); } else if(key>T->data){ InsertBST(T->rChild,key); } else return 0; } BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL; inti=0; while(i

链表实验报告

链表实验报告

————————————————————————————————作者: ————————————————————————————————日期：

《数据结构》实验报告二 系别:嵌入式系统工程系班级:嵌入式1１0０3班 学号:１1160400３１4姓名：孙立阔 日期：2012年４月９日指导教师:申华 一、上机实验的问题和要求： 单链表的查找、插入与删除。设计算法,实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求: 1.从键盘输入1０个字符，产生不带表头的单链表，并输入结点值。 2.从键盘输入1个字符,在单链表中查找该结点的位置。若找到,则显示“找到了”；否则, 则显示“找不到”。 3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插 入在对应位置上，输出单链表所有结点值,观察输出结果。 4.从键盘输入１个整数,表示欲删除结点的位置，输出单链表所有结点值,观察输出结果。 5.将单链表中值重复的结点删除,使所得的结果表中个结点值均不相同,输出单链表所有结 点值,观察输出结果。 6.删除其中所有数据值为偶数的结点，输出单链表所有结点值,观察输出结果。 7.（★)将单链表分解成两个单链表A和B，使A链表中含有原链表中序号为奇数的元素, 而B链表中含有原链表中序号为偶数的元素，且保持原来的相对顺序，分别输出单链表Ａ和单链表B的所有结点值，观察输出结果。 二、程序设计的基本思想，原理和算法描述: (包括程序的结构,数据结构，输入/输出设计,符号名说明等） 创建一个空的单链表，实现对单链表的查找，插入,删除的功能。 三、源程序及注释： #dｅfiｎｅOK 1 #defｉne EＲＲOR 0 #ｄefiｎe INFEASIBLE －1 #defｉne OVEＲFＬOW －2 #deｆine TRUE 1

数据结构实验报告图实验

图实验一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10;

template class MGraph { public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; }; #endif MGraph.cpp

#include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) {

链表习题高考真题

（2）下列程序的功能是实现向head指向的链表中插入新结点s，如图17所示，使该链表按结点的id值保持升序排列。 图17 #include #include typedef struct Node{ int id; char *name; struct Node *next; }Node; void Innode(Node *head,int id,char *str) { int j=0; Node *p,*q,*s; p=head; while( ④) { q=p; p=p->next; } s=(Node*)malloc(sizeof(Node)); s->id=id; s->name=str; ⑤ ⑥ } main() { /*省略创建链表head的代码*/ Innode(head,3,”Jone”); } 36．Merge函数用于将两个升序的链表head1和head2合并成一个链表，并保持合并后链表依然升序。排序的依据为结构体类型Node中的data成员，合并中不得删除节点。下面给出Merge函数的主体框架,在空出的五个位置补充该主体框架缺失的代码段。注意：不能定义新的变量，可不用已定义的某些变量。 typedef struct Node { int data； struct Node *next； }Node； Node *Merge(Node *head1，Node *head2) { if ( head1==NULL) return head2； if(head2==NULL) return headl； Node *head=NULL；//head指针用于指向合并后链表的头结点 Node *pl=NULL； Node *p2=NULL； if(headl->datadata){ head=headl； ______①______

数据结构树的实现实验报告

数据结构设计性实验报告 课程名称_____ ____ 题目名称 学生学院 专业班级 学号 学生姓名 指导教师 2010 年 7 月 6 日

抽象数据类型：树的实现 一．需求分析 树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用，直观来看，树是以分支关系定义的内部结构。树的结构在客观世界广泛存在，如人类社会的族谱和各种社会组织机构都可以用树来形象表示。树在计算机领域中也得广泛应用，如在编译程序中，可用树来表示源程序的语法结构，又如在数据库系统中，树形结构也是信息的重要组织形式之一。 二．实验目的 对某个具体的抽象数据类型，运用课程所学的知识和方法，设计合理的数据结构，并在此基础上实现该抽象数据类型的全部基本操作。通过本设计性实验，检验所学知识和能力，发现学习中存在的问题。进而达到熟练地运用本课程中的基础知识及技术的目的。 三．实验环境 1、硬件：PC机 2、软件：Microsoft Visual C++ 6.0 四．设计说明 本程序采用树的二叉链表（孩子指针-兄弟指针-双亲指针）存储表示，以下是树的结构定义和基本操作： ADT Tree{ 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R： 若D为空集，则称为空树； 若D仅含有一个数据元素，则R为空集，否则R={H}，H是如下二元关系： (1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2) 若D-{root}≠NULL，则存在D-{root}的一个划分D1,D2,D3, …,Dm(m>0)，对于任意j ≠k(1≤j,k≤m)有Dj∩Dk=NULL,且对任意的i(1≤i≤m)，唯一存在数据元素xi∈Di有∈H; (3) 对应于D-{root}的划分，H-{,…,}有唯一的一个划分H1，H2,…,Hm(m>0)，对任意j≠k(1≤j,k≤m)有Hj∩Hk=NULL，且对任意i(1≤i≤m),Hi是Di 上的二元关系，(Di,{Hi})是一棵符合本定义的树，称为根root的子树。 基本操作P： InitTree(&T); 操作结果：构造空树T。 DestroyTree(&T); 初始条件：树T存在。 操作结果：销毁树T。 CreateTree(&T,definition); 初始条件：definition给出树T的定义。 操作结果：按definition构造树T。 ClearTree(&T);

数据结构实验报告2

数据结构实验报告 二．程序设计相关信息 （1）实验题目：编写一个程序algo2-3.cpp，实现双链表的各种基本运算，并在此基础上设计一个主程序完成如下功能： 1.初始化双链表h； 2.依次采用尾插法插入a，b，c，d，e元素； 3.输出双链表h； 4.输出双链表h长度； 5.输出双链表h是否为空； 6.判断双链表h的第3个元素； 7.输出元素‘a’的位置； 8.在第4个元素位置上插入‘f’元素； 9.输出双链表h； 10.删除L的第3个元素； 11.输出双链表h； 12.释放双链表h。 （2）实验目的：熟悉双链表的基本操作并掌握尾插法建表。 （3）算法描述或流程图

(4)源代码 #include #include

typedef struct DNode { char data; struct DNode *next; struct DNode *prior; }DNode,DLinkList; void initlist(DLinkList *&h) { h=(DLinkList*)malloc(sizeof(DLinkList)) ; h->next=NULL; h->prior=NULL; } void destroylist(DLinkList *&h) { DLinkList *p=h,*q=p->next; while(q!=NULL) {free(p); p=q; q=p->next; } free(p); } int getelem(DLinkList *h,int i,char &e) {int j=0; DLinkList *p=h; while(jnext; } if(p==NULL) return 0; else { e=p->data; return 1; } } int listempty(DLinkList *h) { return(h->next==NULL&&h->prior==NULL); } int listlength(DLinkList *h) { DLinkList *p=h;int n=0; while(p->next!=NULL) {n++; p=p->next; } return (n);

两个线性表合并成一个线性表

#include #include //节点结构 struct LinkList { int data; struct LinkList * next; }; void main() { int a[8]={1,3,4,7,7,8,34,45}; int b[9]={1,2,4,7,9,12,33,43,56}; LinkList *pa=NULL; LinkList *pb=NULL; LinkList *pc=NULL; LinkList *la=NULL;//la,lb,lc保存链表首地址 LinkList *lb=NULL; LinkList *lc=NULL; // 初始化单链表 for(int i=7;i>=0;i--) { pa=(LinkList *) malloc(sizeof(struct LinkList)); pa->data=a[i]; pa->next=la; la=pa; } for(int j=8;j>=0;j--) { pb=(LinkList *) malloc(sizeof(struct LinkList)); pb->data=b[j]; pb->next = lb; lb=pb; } lc=pc=(LinkList *) malloc(sizeof(struct LinkList));//LC指向单链表的头节点 //递增排序 while(pa && pb) {

if( (pa->data) <= (pb->data) ) { pc->next=pa; pc=pc->next; pa=pa->next; } else { pc->next=pb; pc=pc->next; pb=pb->next; } } if(pa) { pc->next=pa; } if(pb) { pc->next=pb; } pc=lc->next; while(pc) { printf("%d\t",*pc); pc=pc->next; } printf("\n"); }

C语言链表实验报告

链表实验报告 一、实验名称 链表操作的实现--学生信息库的构建 二、实验目的 （1）理解单链表的存储结构及基本操作的定义 （2）掌握单链表存储基本操作 （3）学会设计实验数据验证程序 【实验仪器及环境】计算机 Window XP操作系统 三、实验内容 1、建立一个学生成绩信息（学号，姓名，成绩）的单链表，按学号排序 2、对链表进行插入、删除、遍历、修改操作。 3、对链表进行读取（读文件）、存储（写文件） 四、实验要求 （1）给出终结报告（包括设计过程，程序）-打印版 （2）对程序进行答辩

五、实验过程、详细内容 1、概念及过程中需要调用的函数 （1）链表的概念结点定义 结构的递归定义 struct stud_node{ int num; char name[20]; int score; struct stud_node *next; }; （2）链表的建立 1、手动输入 struct stud_node*Create_Stu_Doc() { struct stud_node *head,*p; int num,score; char name[20]; int size=sizeof(struct stud_node); 【链表建立流程图】

2、从文件中直接获取 先建立一个 (3)链表的遍历 （4 ）插入结点 （5）删除结点 （6）动态储存分配函数malloc （） void *malloc(unsigned size) ①在内存的动态存储区中分配一连续空间，其长度为size ②若申请成功，则返回一个指向所分配内存空间的起始地址的指针 ③若申请不成功，则返回NULL （值为0） ④返回值类型：(void *) ·通用指针的一个重要用途 ·将malloc 的返回值转换到特定指针类型，赋给一个指针 【链表建立流程图】 ptr ptr ptr->num ptr->score ptr=ptr->next head pt r s s->next = ptr->next ptr->next = s 先连后断 ptr2=ptr1->next ptr1->next=ptr2->next free （ptr2）

链表基本操作实验报告

实验2 链表基本操作实验 一、实验目的 1． 定义单链表的结点类型。 2． 熟悉对单链表的一些基本操作和具体的函数定义。 3． 通过单链表的定义掌握线性表的链式存储结构的特点。 二、实验内容与要求 该程序的功能是实现单链表的定义和主要操作。如：单链表建立、输出、插入、删除、查找等操作。该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。程序中的单链表（带头结点）结点为结构类型，结点值为整型。 要求： 同学们可参考指导书实验2程序、教材算法及其他资料编程实现单链表相关操作。必须包括单链表创建、输出、插入、删除操作，其他操作根据个人情况增减。 三、 算法分析与设计。 头结点 ......

2.单链表插入 s->data=x; s->next=p->next; p->next=s; 3.单链表的删除： p->next=p->next->next;

四、运行结果 1.单链表初始化 2.创建单链表 3.求链表长度 4.检查链表是否为空 5.遍历链表 6.从链表中查找元素 7.从链表中查找与给定元素值相同的元素在顺序表中的位置

8.向链表中插入元素 插入元素之后的链表 9.从链表中删除元素 删除位置为6的元素(是3) 10.清空单链表 五、实验体会 经过这次单链表基本操作实验，自己的编程能力有了进一步的提高，认识到自己以前在思考一个问题上思路不够开阔，不能灵活的表达出自己的想法，虽然在打完源代码之后出现了一些错误，但是经过认真查找、修改，最终将错误一一修正，主要是在写算法分析的时候出现了障碍，经过从网上查找资料，自己也对程序做了仔细的分析，对单链表创建、插入、删除算法画了详细的N-S流程图。

c语言实现单链表的合并 归并算法

#include #include typedef struct Node { int data; struct Node *next; }Node, *LinkList; LinkList LA,LB,LC; void InitList(LinkList *L) //初始化单链表 { *L=(LinkList)malloc(sizeof(Node)); (*L)->next=NULL; } void EnterList(LinkList &L) //尾插法创建单链表。{ Node *s,*r; int flag=1,integer; r=L; while(flag) { scanf("%d",&integer);

if(integer != -1) { s=(Node*)malloc(sizeof(Node)); s->data=integer; r->next=s; r=s; } else { flag=0; r->next=NULL; } } } void UnionList(LinkList &LA,LinkList &LB,LinkList &LC) { Node *p,*q,*r,*y; p=LA->next; q=LB->next; r=LC; while (p)

{ y=(Node*)malloc(sizeof(Node)); y->data=p->data; r->next=y; r=y; p=p->next; } while (q) { y=(Node*)malloc(sizeof(Node)); y->data=q->data; r->next=y; r=y; q=q->next; } r->next=NULL; } void DeSameList(LinkList *LC)//删除c表的相同元素。{ Node *p,*q,*r; for(p=(*LC)->next;p!=NULL;p=p->next)

链表基本操作实验报告

实验2 链表基本操作实验 一、实验目的 1． 定义单链表的结点类型。 2． 熟悉对单链表的一些基本操作和具体的函数定义。 3． 通过单链表的定义掌握线性表的链式存储结构的特点。 二、实验容与要求 该程序的功能是实现单链表的定义和主要操作。如：单链表建立、输出、插入、删除、查找等操作。该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。程序中的单链表（带头结点）结点为结构类型，结点值为整型。 要求： 同学们可参考指导书实验2程序、教材算法及其他资料编程实现单链表相关操作。必须包括单链表创建、输出、插入、删除操作，其他操作根据个人情况增减。 三、 算法分析与设计。 头结点

2.单链表插入 s->data=x; s->next=p->next; p->next=s; 3.单链表的删除： p->next=p->next->next;

四、运行结果 1.单链表初始化 2.创建单链表 3.求链表长度 4.检查链表是否为空 5.遍历链表 6.从链表中查找元素 7.从链表中查找与给定元素值相同的元素在顺序表中的位置

8.向链表中插入元素 插入元素之后的链表 9.从链表中删除元素 删除位置为6的元素(是3) 10.清空单链表 五、实验体会 经过这次单链表基本操作实验，自己的编程能力有了进一步的提高，认识到自己以前在思考一个问题上思路不够开阔，不能灵活的表达出自己的想法，虽然在打完源代码之后出现了一些错误，但是经过认真查找、修改，最终将错误一一修正，主要是在写算法分析的时候出现了障碍，经过从网上查找资料，自己也对程序做了仔细的分析，对单链表创建、插入、删除算法画了详细的N-S流程图。

用单链表实现集合的操作

《数据结构》课设计报告 2012—2013学年第一学期 课程名称数据结构 设计题目用单链表实现集合的操作 专业班级 姓名 学号 指导教师 一．实验目的

掌握单链表的算法，插入、删除、遍历等。 二．实验内容 （1）对集合中的元素用有序单链表进行存储； （2）实现交、并、差等基本运算时，不能另外申请存储空间； （3）充分利用单链表的有序性，要求算法有较好的时间性能。 三．设计与编码 集合是由互不相同的元素构成的一个整体，在集合中，元素之间可以没有任何关系，所以，集合也可以作为线性表的处理。用单链表实现集合的操作，需要注意集合中元素的唯一性，即在单链表中不存在值相同的结点。 （1）判断A和B是否相等。两个集合相等的条件是不仅长度相同，而且各个对应的元素也相等。由于用单链表表示集合，所以只要同步搜啊秒两个单链表，若从头至尾每个对应的元素都相等，则表明两个集合相等。 （2）求集合A和B的交集。根据集合的运算规则，集合A∩B中包含所有既属于集合A又属于集合B的元素，因此，需要查找单链表A和B中的相同元素并保留在单链表A中。由于用有序单链表表示集合，因此判断某元素是否在B中不需要遍历表B，而是从上次搜索到的位置开始，若在搜索过程中，遇到一个其值比该元素大的结点，便可断定该元素不在单链表中，为此，需要用两个指针p、q分别指向当前被比较的两个结点，会出现以下三种情况： 1、若p->data>q->data，说明还未找到，需在表B中继续查找； 2、若p->datadata，说明表B中无此值，处理表A中下一结点； 3、若p->data=q->data,，说明找到了公共元素。 （3）求集合A和B的并集，集合A∪B中包含所有或属于集合A或属于集合B 的元素。因此，对单链表B中的每一个元素x，在单链表A中进行查找，若存在和x不同的元素，则将该结点出入到单链表A中。 （4）求集合A和B的差集。根基集合的运算规则，集合A-B中包含所有属于集合A而不属于集合B的元素。因此，对单链表B中的每个元素x在单链表A中进行查找，若存在和x相同的结点，则将该结点从链表A中删除。 在主函数中，首先建立两个有序单链表表示集合A和B，然后依次调用相应函数实现集合的判等、交、并和差等运算，并输出运算结果。 代码： #include using namespace std; template struct Node{ T data; Node *next; }; template class LinkList{ public:

《数据结构》实验报告

《数据结构》实验报告 实验序号：4 实验项目名称：栈的操作

附源程序清单： 1. #include #define MaxSize 100 using namespace std; typedef int ElemType; typedef struct { ElemType data[MaxSize]; int top; }SqStack; void InitStack(SqStack *st) //初始化栈 { st->top=-1; } int StackEmpty(SqStack *st) //判断栈为空{ return (st->top==-1); } bool Push(SqStack *st,ElemType x) //元素进栈{ if(st->top==MaxSize-1)

{ return false; } else { st->top++; //移动栈顶位置 st->data[st->top]=x; //元素进栈 } return true; } bool Pop(SqStack *st,ElemType &e) //出栈 { if(st->top==-1) { return false; } else { e=st->data[st->top]; //元素出栈 st->top--; //移动栈顶位置} return true; } //函数名：Pushs //功能：数组入栈 //参数：st栈名,a->数组名，i->数组个数 bool Pushs(SqStack *st,ElemType *a,int i) { int n=0; for(;n数组名，i->数组个数 bool Pops(SqStack *st,ElemType *a,int i) { int n=0; for(;n

实验报告03-两个有序链表的合并

实验目的及要求： 了解和掌握链表的特点； 掌握链表基本操作的实现； 掌握两个有序链表合并的算法 要求完成链表的初始化、插入、有序表合并、显示操作的实现。实验设备环境及要求： PC机一台，内存要求128M以上，VC++6.0集成开发环境。 实验内容与步骤： 1、在VC++6.0环境中新建一个工程和C++文件； 2、实现链表初始化、插入、有序合并算法，代码如下： #include #include typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; int InitList_L(LinkList &L){ L= (LinkList)malloc(sizeof(LNode)); L->next=NULL; return 1; } int ListInsert_L(LinkList &L,int i,ElemType e){ LinkList p; p=L; int j=0; while(p&&jnext; ++j; } if(!p||j>i-1) return 0; LinkList s=(LinkList)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; return 1; } void Disp_L(LinkList L){

LinkList p=L->next; if(!p) printf("此链表为空！"); while(p){ printf("%d",p->data); p=p->next; } printf("\n"); } void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){ LinkList pa=La->next; LinkList pb=Lb->next; LinkList pc=Lc=La; while(pa&&pb){ if(pa->data<=pb->data){ pc->next=pa;pc=pa;pa=pa->next; } else{ pc->next=pb;pc=pb;pb=pb->next; } } pc->next=pa?pa:pb; free(Lb); } void main(){ LinkList La,Lb,Lc; InitList_L(La); InitList_L(Lb); InitList_L(Lc); ListInsert_L(La,1,2); ListInsert_L(La,2,3); ListInsert_L(La,3,5); Disp_L(La); ListInsert_L(Lb,1,1); ListInsert_L(Lb,2,4); ListInsert_L(Lb,3,6); ListInsert_L(Lb,4,7); Disp_L(Lb); MergeList_L(La,Lb,Lc); printf("合并之后的链表为:\n"); Disp_L(Lc); }实验指导与数据处理：

单链表实验报告

单链表实验报告

————————————————————————————————作者：————————————————————————————————日期：

计算机与信息技术学院综合性、设计性实验报告 专业：网络工程年级／班级：大二 2016—2017学年第一学期 课程名称数据结构指导教师李四 学号姓名16０8３2４０XX 张三 项目名称单链表的基本操作实验类型综合性／设计性实验时间2017.10.3 实验地点216机房 一、实验目的 （１）熟悉顺序表的创建、取值、查找、插入、删除等算法，模块化程序设计方法。 二、实验仪器或设备 (1)硬件设备：CＰU为Pｅntium 4以上的计算机,内存２G以上 （２）配置软件:Microsｏft Windｏws 7与VC++6．０ 三、总体设计（设计原理、设计方案及流程等) 设计原理： 单链表属于线性表,线性表的存储结构的特点是：用一组任意存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。因此,对于某个元素来说，不仅需要存储其本身的信息,还需要存储一个指示其直接后继的信息。 设计方案: 采用模块化设计的方法，设计各个程序段,最终通过主函数实现各个程序段的功能。设计时，需要考虑用户输入非法数值,所以要在程序中写入说可以处理非法数值的代码。 设计流程: 1.引入所需的头文件; 2.定义状态值； 3.写入顺序表的各种操作的代码； 写入主函数,分别调用各个函数。在调用函数时，采用iｆ结构进行判断输入值是否非法,从而执行相应的程序 四、实验步骤（包括主要步骤、代码分析等） #inclｕdｅ<ｓtdio．h＞／/ EOF(=^Z或F6）,ＮUＬL #inclｕde＜ｓtdlｉb.ｈ＞ // sｒand（），raｎd（）,eｘｉt(n) #inｃlude＜ｍalloｃ.h> // mａlloc( )，alloc( ),ｒｅａllｏc（）等 ＃iｎcluｄe /／IＮT_MAX等 #iｎclude #ｉｎｃｌuｄe // floor(),ceil( ),abs( ) #ｉnclude＜ｉosｔreａm．h＞ // coｕt,cｉn ＃iｎclｕde // clｏｃk（),ＣLK＿ＴCK,ｃlock＿t #ｄefine ＴRＵＥ 1 #define FALSE 0 ＃ｄeｆine ＯＫ 1 ＃define ERROR 0

基于单链表实现集合的并交差运算实验报告

基于单链表实现集合的并交差运算实验报告 一实验题目: 基于单链表实现集合的并交差运算二实验要求: 2.2: 编写一个程序，实现顺序表的各种基本运算 (1) 初始化单链表h； (2) 依次采用尾插法插入a,b,c,d,e 元素; (3) 输出单链表h (4) 输出单链表h 的长度 (5) 判断单链表h 是否为空 (6) 输出单链表h 的第三个元素 (7) 输出元素在a 的位置 (8) 在第4 个元素位置上插入f 元素 (9) 输出单链表h (10) 删除L的第3个元素 (11) 输出单链表 (12) 释放单链表 2.2: 编写一个程序，采用单链表表示集合( 集合中不存在重复的元素), 并将其按照递增的方式排序，构成有序单链表，并求这样的两个集合的并交和差。三实验内容: 3.1 线性表的抽象数据类型: ADT List{ 数据对象;D= { a i |a i ElemSet ,i 1,2,...,n,n 0} 数据关系:R1={ a i 1,a i |a i 1,a i D,i 2,..., n} 基本操作： InitList(&L) 操作结果; 构造一个空的线性表L

DestroyList(&L) 初始条件：线性表L 已存在操作结果：销毁线性表L ClearList(&L) 初始条件：线性表L 已存在操作结果：将L 置为空表 ListEmpty(L) 初始条件：线性表已存在操作结果：若L为空表，则返回 TRUE否则返回FALSE ListLength(L) 初始条件：线性表已存在 操作结果：返回L 中数据元素的个数GetElem(L,i) 初始条件: 线性表已存在，1<=i<=ListLength(L) 操作结果：用e返回L中第i个数据元素的值LocateElem(L,i,e) 初始条件：线性表已存在，用循环遍历整个线性表，如果中的元素相同； 操作结果：用此时的i+1 返回该元素在线性表的位序 ListInsert(&L,i,e) 初始条件：线性表存在，1<=i<=ListLength(L)+1; 操作结果：在L 中第i 个位置之前插入新的数据元素,e,L ListDelete(&L,i,&e) 初始条件: 线性表L 已存在且非空， 1<=i<=ListLength(L) 操作结果：删除L的第i个数据元素，并用e返回其值， 1 }ADT List 3.2 存储结构的定义; typedef char ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LinkList; 3.3 基本操作实现 /* 单链表的初始化*/ void InitList(LinkList *&L) { L = (LinkList *)malloc(sizeof(LinkList)); L->next=NULL; } /* 向单链表中插入数据元素*/ bool ListInsert(LinkList *&L,int x,char e) { int j = 0; LinkList *p = L, *s; e 与线性表的长度加1。L 的长度减