单链表实现集合的交并差

单链表的交并补

1. 需求分析

任意给定两个包含10-2000个元素的集合A,B（集合中元素类型为任意整型数），求这两个集合的交集、并集和补集。

单链表合并，时间复杂度O(m*n))，空间复杂度O(n) 2. 概要设计

首先设计程序的设计结构用来表示集合

//线性表的单链表存储结构

typedefstructLNode{ char data;

structLNode*next; }LNode,*LinkList;

创建生成次集合的函数

voidCreateList_L(LinkList&L,int n)

以下是本程序的函数

void Bing(LinkListLa,LinkListLb,LinkList&Lc)//求并集

void Jiao(LinkListLa,LinkListLb,LinkList&Lc)//求交集 void Cha(LinkListLa,LinkListLb,LinkList&Lc)//求补集 void output(LinkList L)//输出元素

3. 详细设计

#include #include using namespace std; //线性表的单链表存储结构 typedefstructLNode{ char

江西理工大学软件学院

实 验 报 告

系（部） 机电工程系

课 程 数据结构 专业班级 11机械电子（2）班

姓 名 杨锦其 学 号 11212203 指导教师 刘廷苍

实验题目：用单链表实现集合的操作

一．实验目的

用有序单链表实现集合的判等，交，并和差等基本运算。

二．实验内容

（1）对集合中的元素用有序单链表进行存储；

（2）实现交，并，差等基本运算时，不能另外申请存储空间； （3）充分利用单链表的有序性，要求算法有较好的时间性能。

三．设计与代码

1. 理论知识

集合是由互不相同的元素构成的一个整体，在集合中，元素之间可以没有任何关系，所以，集合也可以作为线性表处理。用单链表实现集合的操作，需要注意集合中元素的唯一性，即在单链表中不存在值相同的结点。本实验要求采用有序单链表，还要注意单链表的有序性。

2. 算

什么单链表的逆置

问题描述

设计一个程序，实现单链表的逆置。

一、需求分析

⑴按程序提示输入并创建一个单链表，带有头结点 ⑵可自定义链表的长度，可自定义链表储存的数据类型，注意更改相应的输入输出方式 ⑶实现单链表的逆置，直观地输出结果

二、概要设计

为实现上述程序功能，需创建以下抽象数据类型：

ADT LinkList {

数据对象：D={ai|ai∈（0，1，…，9），i=0,1，2，…，n，n≥0} 数据关系：R={|ai-1,ai∈D,i=1,2，…，n} 基本操作： InitList（&L） 操作结果：初始化一个链表L。 CreatList（L，L_Length） 初始条件：链表L已存在。 操作结果：创建一个长度为L_Length的单链表。 InverseList（L） 初始条件：链表L已存在。 操作结果：将单链表逆置。 DisplayList（L） 初始条件：链表L已存在。

操作结果：销毁链表L。

} ADT LinkList

本程序包含四个模块，即 1） 主程序模块，接受命令

2） 初始化及链表创建模块，按要求创建链表 3） 单链表逆置模块，实现单链表的逆置 4） 显示模块，输出结果

三、详细设

《数据结构》实验报告

1、实验名称:设计循环单链表 2、实验日期: 2011-3-4 3、基本要求：

1）循环单链表的操作，包括初始化、求数据元素个数、插入、删

除、取数据元素；

2）设计一个测试主函数实际运行验证所设计循环单链表的正确性。

4、测试数据：

依次输入1，2，3，4，5，6，7，8，9，10，删除5，再依次输出

数据元素。

5、算法思想或算法步骤:

主函数主要是在带头结点的循环单链表中删除第i个结点，其主

要思想是在循环单链表中寻找到第i-1个结点并由指针p指示，然后让指针s指向a[i]结点，并把数据元素a[i]的值赋给x，最后把a[i]结点脱链，并动态释放a[i]结点的存储空间。

6、模块划分：

1）头文件LinList.h。头文件LinList.h中包括：结点结构体定

义、初始化操作、求当前数据个数、插入一个结点操作、删除一个结点操作以及取一个数据元素操作；

2）实现文件xhdlb.cpp。包含主函数void main(void)，其功能是测试所设计的循环单链表的正确性。

7、数据结构：

链表中的结点的结构体定义如下：

typedef struct Node {

DataType d

安徽工程大学机电学院

课程设计说明书

课程设计名称： C语言程序设计 课程设计题目： 简单通讯录 指导老师： 伊芸芸 专业班级： 电气2132 学生姓名： 洪培鑫 学号： 313107040208

起止日期：2014年6月23日 ~ 14年7月4日

第一章

1.1 题目要求 简单通讯录 1.2主要任务

问题要求及任务描述

1、建立并保存新的通讯录，信息至少包含姓名、性别、电话号码、地址； 2、能够把通讯者信息插入通讯录；

3、、能够提供按不同方式查询的功能，如按姓名或性别等； 4、能够提供按不同方式删除的功能，如按姓名或性别等； 5、能够输出文件中的通讯录信息； 6、 可以退出通信录管理系统；

1.3进行概要的需求分析。

(根据功能需求，设计系统的总体结构。系统总体功能模块图，菜单的设计) 菜单：

菜单：

系统总体功能模块：

主菜单 添加 学生 信息 删除学生信息 查询学生信息 查询全部学生信息 退出程序 第二章解决问题的主要方法和思路

2.1关键问题

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

武汉理工大学《数据结构》课程设计

课程设计任务书

学生姓名： 专业班级： 软件100班 指导教师： 工作单位：计算机科学与技术学院 题 目: 单链表函数库的设计 初始条件：

理论：学习了《数据结构》课程，掌握了一种计算机高级语言。 实践：计算机技术系实验中心提供计算机及软件开发环境。

要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写

等具体要求）

1、系统应具备的功能： （1）建立单链表

（2）对单链表实现定位，插入，删除，查找，排序及其他操作 （3）输出单链表 2、数据结构设计； 3、主要算法设计； 4、编程及上机实现；

5、撰写课程设计报告，包括： （1）设计题目；

（2）摘要和关键字（中文和英文）；

（3）正文，包括引言、需求分析、数据结构设计、算法设计、有关技术

的讨论、设计体会等； （4）结束语； （5）参考文献。

时间安排： 2012年1月2日－6日 （第18周）

1月2日 查阅资料

1月3日 系统设计，数据结构设计，算法设计 1月4日-5日 编程并上机调试 1月6日 撰写报告

1月7日 验收程序，提交设计报告书。

指导教师签名：

#include #include #include struct memory //内存块 { char pro; //内存块的内容，'o'代表操作系统，'\\0'代表空闲块，其它代表被进程占有 int size; //内存块的大小 int begin; //内存块的起始地址 memory *next; //下一块内存块 };

memory *base; //代表内存，一个头指针,内存总大小为256k void init(int manage) //内存的初始化 { memory *p,*q; if(base!=NULL) //这一块是释放链表 { p=base; while(p) { q=p->next; delete p; p=q; } } base=new memory; //操作系统，大小5k,起始地址是0k base->begin=0; base->pro='o'; base->size=5; if(manage==0) //静态内存，初始化7个内存块，第一个内存块是操作系统 { p=base; q=new memory; //空闲块1，

#include #include #include struct memory //内存块 { char pro; //内存块的内容，'o'代表操作系统，'\\0'代表空闲块，其它代表被进程占有 int size; //内存块的大小 int begin; //内存块的起始地址 memory *next; //下一块内存块 };

memory *base; //代表内存，一个头指针,内存总大小为256k void init(int manage) //内存的初始化 { memory *p,*q; if(base!=NULL) //这一块是释放链表 { p=base; while(p) { q=p->next; delete p; p=q; } } base=new memory; //操作系统，大小5k,起始地址是0k base->begin=0; base->pro='o'; base->size=5; if(manage==0) //静态内存，初始化7个内存块，第一个内存块是操作系统 { p=base; q=new memory; //空闲块1，

《数据结构》实验报告

实验二、单链表的应用

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

河南科技大学管理学院

年 月 日

一、实验目的

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

二、实验内容

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

三、完成情况

#include #include

//#define MAXSIZE 100

typedef struct{

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

typedef