C++与数据结构 第一次上机实验——线性表
实验一线性表
数据结构（C++语言描述）实验报告
实验一线性表
一、实验目的和要求：
1、掌握线性表顺序存储结构和链式存储结构的基本思想；
2、掌握顺序表和单链表的基本操作。
二、实验原理：
1、线性表的定义：数据之间存在一对一的线性关系的数据结构的称为线性结构，也可
称为线性表。
2、顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关
系是由元素的存储的存储位置来表示的，通常用一维数组来表示。
顺序表的优点：存储密度大、空间利用率高、，无需为表中元素之间的逻辑关系而增加额外的存储空间。
顺序表的缺点：插入和删除操作需要移动大量的元素；表的容量难以确定；造成空间的“碎片”。
在程序设计语言中，通常用一维数组来表示表的存储区域。假设用data[ListSize]来表示一段顺序表，其中ListSize是一个根据实际问题规模定义的足够大的整数，另外用一个实际变量length来表示当前实际元素的个数，表中的数据从data[0]开始依次存放，表空时length=0.
3、链式存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系是
用指针来表示的。
链式存储结构的优点：插入和删除操作方便省时。
链式存储结构的缺点：存储空间的开销大。
链式存储的方法是使用结点构造链。每个结点分为数据域和指针域两部分组成。数据域用来存放数据元素，指针域用来存放后继存储单元的地址。
三、实验内容
1、对于给定的单链表L，设计一个算法，删除L中值为x的结点的直接前驱结点。
2、已知两个单链表LA和LB分别表示两个集合，其元素递增排列，设计算法求出LA
和LB的交集C，要求C同样以递增的单链表形式存储。
四、实验设计：
1、（1）伪算法：
建立链表L；
循环搜索数据值为x的前一结点，若已至表尾，且其值不为value，警告，退出程序；否则，重新拉链，将数值为x的结点的前一结点标记，将被标记的结点断开，回收被删除的结点的内存空间，将链表长度减1。
（2）实验代码：
//对给定的链表L，设计一个算法，删除L中值为x的结点的直接前驱结点#include
#include
using namespace std;
class ListNode //建立结点类
{public:
char data;
ListNode *link;
ListNode(){link=NULL;}
ListNode(int&item,ListNode *next=NULL)
{data=item;
link=next;
}
};
class List //建立链表类
{public:
List(){ListNode *q=new ListNode;first=last=q;}
void Great(List L);
voidInsertL(char zifu);
void Print();
charRemovevalue(char value);
private:
ListNode *first,*last;
int length;
};
void List::Great(List L) //建立链表函数
{
char n;
intl,i;
cout<<"请输入链表的长度：";
cin>>l;
cout<<"请输入数据:";
for(i=1;i { cin>>n; L.InsertL(n);} L.length++; } void List::InsertL(char zifu) { ListNode *newcode=new ListNode; newcode->data =zifu; newcode->link=NULL; if(first==NULL) {first=newcode; last=newcode; } else last->link=newcode; last=newcode; } char List ::Removevalue(char value) //该函数实现删除值为x的结点的前一结点 { ListNode *p=first,*q,*h; while(p->link!=NULL&&p->link->data!=value) {h=p;p=p->link; } if(p->link==NULL&&p->data!=value) return 0; q=h->link; h->link = q->link; delete q; length --; return value; } void List::Print() //打印链表{ ListNode *p; p=first->link; while(p!=NULL) {cout< p=p->link; } cout< } int main() { char value; List a; a.Great(a); cout<<"请输入要删除的的数值；"; cin>>value; a.Removevalue(value); a.Print(); system("PAUSE"); } （3）、运行结果 2、（1）伪算法： 要实现此程序核心问题是寻找集合LA和LB的交集，并将其输出，设计思路： 寻找LA的第i个结点，寻找LB的第j个结点，利用嵌套循环，实现链表LA的每一个结点都和LB的结点进行比较，将相等的元素输出到链表LD中；对链表LD中的元素进行去重，然后将链表中没有重叠的元素存入到链表LC中，将链表LC输出。 （2）程序代码： #include"stdlib.h" #include"iostream" using namespace std; #include"assert.h" class List; //List类的预先声明 class ListNode //结点类的定义 { friend class List; int data; ListNode *link; public: ListNode(){link=NULL;} //缺省构造函数 ListNode(int&item,ListNode *next=NULL) //带参数的构造函数 { data=item; link=next; } }; class List //建立链表类 { public: List() //建立空的链表 { ListNode *q=new ListNode; first=last=q; } voidCreat(List L); void Insert(intnum); ListNode *Find(inti); intGetlength(); int Get(inti); void Print(); private: ListNode *first,*last; int length; }; void List::Creat(List L) //创建一个新链表 { inti,l,x; cin>>l; cout<<"请从小到大输入数据:"; for(i=1;i { cin>>x; L.Insert(x); } L.length++; } void List::Insert(intnum) //将新元素插入到表尾位置 { ListNode *newnode=new ListNode; newnode->data=num; newnode->link=NULL; if(first==NULL) { first=newnode; last=newnode; } else last->link=newnode; last=newnode; } int List::Get(inti) //取出链表中的第i个元素 { ListNode *p=Find(i); assert(p&&p!=first); return p->data; } ListNode *List::Find(inti) //寻找链表中第i个结点元素的地址{ if(i<-1) return NULL; if(i==-1) return first; ListNode *p=first->link; int j=0; while(p!=NULL&&j { p=p->link; j++; } return p; } int List::Getlength() //获得链表的长度 { length=0; ListNode *p=first; while(p->link!=NULL) { p=p->link; length++; } return length; } void List::Print() //输出链表 { ListNode *p; p=first->link; while(p!=NULL) { cout< p=p->link; } cout< } int main() { //输入链表LA和LB的数据 List LA,LB,LC,LD; cout<<"请输入集合LA的长度:"; LA.Creat(LA); cout<<"LA的数据为:"; LA.Print(); cout<<"请输入集合LB的长度:"; LB.Creat(LB); cout<<"LB的数据为:"; LB.Print(); //寻找LA和LB中的相同元素，并将其提取到LC中 intla,lb,ld,ta,tb,td,tdd,tl; la=LA.Getlength(); lb=LB.Getlength(); //得到链表LA和LB的长度 for(inti=0;i { ta=LA.Get(i); //获取链表LA的第i个元素 for(int j=0;j { tb=LB.Get(j); //获取链表LB的第j个元素 if(tb==ta) //利用嵌套循环实现链表LA中第i个元素和链表LB 中所有元素进行比较 {LD.Insert(ta);} //如果相等，将元素提取到LD中 } } ld=LD.Getlength(); for(int m=1;m { td=LD.Get(m-1); tdd=LD.Get(m); if(tdd!=td) LC.Insert(td); //将没有重叠的元素存入链表LC中} tl=LD.Get(ld-1); LC.Insert(tl); cout<<"LA与LB的交集LC:"; LC.Print(); system("PAUSE"); } （3）运行结果： 五、编程心得： 1、实践是学习编程语言必须的经历。这次实验内容完成的并不顺利，尤其是第二题对 于链表LC的输出的实现，每次总是在运行的时候不能输出。 2、其实在理论学习的时候挺不明白链式存储，经过编程发现data域和pointer域的应 用很方便的实现了链表的很多操作，以上两个程序都让我对于这个有了更深的理解。 3、我觉得就C++本身的编程而言是复杂的，但C++可以解决比C语言更加复杂的问题， 尤其是规模较大的问题，因为C++的类和对象成功的将一些数据相统一。 4、编程的过程中遇到了很多的问题，主要是一些基础的格式问题和将书上模板转换成 具体函数的问题，基本上也解决。在编程过程中，将前面学过的模板只是重新学习，实现了链表模板的具体化。 数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 6.0上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>//头文件 #include nodetype *create()//建立单链表，由用户输入各结点data域之值，//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"< 实验一线性表的基本操作 一、实验目的与基本要求 1．掌握数据结构中的一些基本概念。数据、数据项、数据元素、数据类型和数据结构，以及它们之间的关系。 2．了解数据的逻辑结构和数据的存储结构之间的区别与联系；数据的运算与数据的逻辑结构的关系。 3．掌握顺序表和链表的基本操作：插入、删除、查找以及表的合并等运算。4．掌握运用C语言上机调试线性表的基本方法。 二、实验条件 1．硬件：一台微机 2．软件：操作系统和C语言系统 三、实验方法 确定存储结构后，上机调试实现线性表的基本运算。 四、实验内容 1．建立顺序表，基本操作包括：初始化，建立一个顺序存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。 2．建立单链表，基本操作包括：初始化，建立一个链式存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。 3．假设有两个按数据元素值非递减有序排列的线性表A和B，均以顺序表作为存储结构。编写算法将A表和B表归并成一个按元素值非递增有序（允许值相同）排列的线性表C。（可以利用将B中元素插入A中，或新建C表）4．假设有两个按数据元素值非递减有序排列的线性表A和B，均以单链表作为存储结构。编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C。 五、附源程序及算法程序流程图 1.源程序 （1）源程序(实验要求1和3) #include 淮海工学院计算机科学系实验报告书 课程名：《数据结构》 题目: 线性数据结构试验 班级：软嵌151 学号：2０１5123352 姓名: 韩吉 线性表实验报告要求 １目得与要求： １）掌握线性表数据结构得基本概念与抽象数据类型描述; 2)熟练掌握线性表数据结构得顺序与链式存储存表示; 3)熟练掌握线性表顺序存储结构得基本操作算法实现; 4)熟练掌握线性表得链式存储结构得基本操作算法实现； 5）掌握线性表在实际问题中得应用与基本编程技巧； 6)按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结 果); ７）按照报告格式与内容要求，认真书写实验报告，并于下周周二前统一提交实验报告电子版文档（每次实验全体同学必须提交实验报告电子版，实验报告文档文件命名方式：姓名＋学号＋数据结构第X次实验报告）提交给学委，而后由学委以班为单位统一打包（包文件名为：软件14X班－数据结构第X次实验报告)用邮件发给老师;提交纸质报告（每班每次收5份,学委安排，保证每学期每个同学至少提交一次)一起提交给老师。每次提交电子文档时，学委务必统计与上报未交报告人数与具体姓名；凡逾期不交报告者,不再推迟提交，一律按照旷交处理。 8）积极开展实验组组内交流与辅导,严禁直接复制与剽窃她人实验成果，一旦发现严肃处理； 9）上实验课前,要求每个同学基本写好程序，并存储在自己得U盘上，用于实验课堂操作时调试与运行. 2实验内容或题目（在一个主程序中实现全部题目内容） 一、顺序表得基本操作实现实验 要求:数据元素类型ElemＴype取整型inｔ.按照顺序存储结构实现如下算法: 1）创建任意整数线性表（即线性表得元素值随机在键盘上输入）得顺序存储结构(即顺序表），长度限定在25之内； 2)打印/显示（遍历)该线性表（依次打印／显示出表中元素值)； ３）在顺序表中查找第ｉ个元素，并返回其值; 4）在顺序表第i个元素之前插入一已知元素； 5）在顺序表中删除第i个元素； 6)求顺序表中所有元素值（整数)之与; 二、链表（带头结点)基本操作实验 要求:数据元素类型ＥｌemＴype取字符型cｈar。按照动态单链表结构实现如下算法： 1)按照头插法或尾插法创建一个带头结点得字符型单链表（链表得字符元素从键盘输入），长度限定 在10之内； 实验1 线性表的基本操作 一、需求分析 目的： 掌握线性表运算与存储概念，并对线性表进行基本操作。 1.初始化线性表； 2.向链表中特定位置插入数据； 3.删除链表中特定的数据； 4.查找链表中的容； 5.销毁单链表释放空间； 二、概要设计 ●基础题 主要函数： 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 实验步骤： 1，初始化顺序表 2，调用插入函数 3，在顺序表中查找指定的元素 4，在顺序表中删除指定的元素 5，在顺序表中删除指定位置的元素 6，遍历并输出顺序表 ●提高题 要求以较高的效率实现删除线性表中元素值在x到y（x和y自定义）之间的所有元素 方法： 按顺序取出元素并与x、y比较，若小于x且大于y，则存进新表中。 编程实现将两个有序的线性表进行合并，要求同样的数据元素只出现一次。 方法： 分别按顺序取出L1，L2的元素并进行比较，若相等则将L1元素放进L中，否则将L 1，L2元素按顺序放进L。 本程序主要包含7个函数 主函数main() 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 提高题的程序 void Combine(List* L1,List* L2,List* L) void DeleteList3(List* L,int x,int y) 二、详细设计 初始化线性表InitList（List* L，int ms） void InitList(List* L,int ms) { L->list=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); L->size=0; L->MAXSIZE=LIST_INIT_SIZE; 序号 数据结构实验报告 班级姓名同组者/ 成绩 日期 3.9指导教师 实验名称实验一线性表及其应用 一、实验目的 1、深刻理解线性表的逻辑特性及其顺序、链式存储方式的特点。 2、熟练掌握线性表的常用操作（建立、插入、删除、遍历等）在顺序、链式存储上的实现。 3、加深对C/C++等编程语言的相关知识点的理解（如结构体、指针、函数、引用参数等）。 二、实验内容 1、根据给定的整型数组，以尾插法建立一个单链表，并实现以下操作： ①查找：输入一个欲查找的整数，找到则显示第一个相匹配的整数在单链表中所处的位置，若不存在，则显示提示信息。 ②删除：输入一个欲删除的整数e ，若存在则在单链表中删除第一个值为 e 的元素。 ③插入：输入一个欲插入位置i 和欲插入元素e，将e 插入到第i 个整数之前（注意i 的合法性）。 A、算法思想 ①创建 head 为头结点指针，初始时head->next 为NULL ；tail 始终指向当前链表的最后一个元素，其初始时指向头结点；p 始终指向每次申请的新结点，修改p->data 为当前读入的整数；修改tail->next 为p ，修改tail 为p ；最后修改tail->next 为NULL ，。 ②插入 找到插入点的前驱（即第i-1 个结点）的指针p ；s 指向新申请的结点；修改s->data 为参数e，修改s->next 为p->next ，修改p->next 为s 。 ③查找 ……利用p进行遍历，直到节点的数据和所给的数据相同，输出节点的位置 ④删除 ……利用p进行遍历，并总是将p的前一节点的指针赋给pre，一旦找到，则删除节点并 退出循环，没有到话，反馈相关信息 B、算法源码 /* *线性表及其应用 */ #include 《数据结构(C语言)》第一次实验报告 附录代码 集合运算器 #include 北京邮电大学电信工程学院 数据结构实验报告 实验名称：实验1——线性表 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 1、实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 2、实验内容： 题目1： 线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。 2. 程序分析 2.1 存储结构 带头结点的单链表 2.2 关键算法分析 1.头插法 a、伪代码实现：在堆中建立新结点 将x写入到新结点的数据域 修改新结点的指针域 修改头结点的指针域,将新结点加入链表中b、代码实现： Linklist::Linklist(int a[],int n)//头插法 {front=new Node; front->next=NULL; for(int i=n-1;i>=0;i--) {Node*s=new Node; s->data=a[i]; s->next=front->next; front->next=s; } } 2、尾插法 a、伪代码实现：a.在堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 b、代码实现: Linklist::Linklist(int a[],int n,int m)//尾插法 {front=new Node; Node*r=front; for(int i=0;i 实验一链式结构综合设计 班级：信科1403班姓段胜磊学2014040430 名：号：5 一、实验目标 本实验通过定义单向链表的数据结构，设计创建链表、插入结点、遍历结点等基本算法，使学生掌握线性链表的基本特征和算法，并能熟练编写C程序，培养理论联系实际和自主学习的能力，提高程序设计水平。 二、实验内容 设计一个职工信息查询系统。每个职工的信息包括，职工号，姓名，所属部门号，月薪。 （1）建立一个职工信息的单链表L。 （2）在单链表L中查找职工号为t的职工信息，并输出。 （3）在单链表L中删除职工号为t的职工信息。 （4）输出单链表L中所有的节点 三、数据结构的设计 由于职工信息在逻辑结构上是线性的，将其建立为链式结构既使得职工信息的增加可以是动态的，也使得其删除过程容易实现。 具体节点类型定义如下： Typedef struct elem {int no; /职工号 Char n ame[20]; / 职工姓名 Int dep no; /所属部门号 Data 域 Next 域 四、各功能函数的设计 （1）建立链表函数 Lnode *new （void ） 功能：该函数实现建立一个含有头节点的链表 。 具体过程： 1） 建立一个含有头节点的空链表 L 。 2） 输入一个新的职工信息。如为非法信息则建立链表过程结束执行 6），否则继续 3 ）。 3） 建立一个新节点p ，并将输入的信息记录在节点 p 的data 域。 4） 将节点p 跟在链表L 的头节点之后。 5） 继续2） 6） 返回链表的头指针。 Int salary; /月薪 }elemtype Typedef struct node {elemtype data; struct node *n ext; /职工信息域 /链域 }Lnode 节点的示例图 《数据结构》实验报告 专业： 学号： 姓名： 实验二线性表 【实验目的】 1.熟悉VC环境，学习如何使用C语言实现线性表的两种存储结构。 2.通过编程、上机调试，进一步理解线性表的基本概念，东运用C语言实现线性表基本操作。 3.熟练掌握线性表的综合应用问题。 【实验内容】 1、一个线性表有n个元素（n-MAXSIZE.MAXSIZE指线性表的最大长度），且递增有。现有一元素x要插入到线性表的适当位置上，并保持线性表原有的顺序不变。设计程序实现。要求：采用顺序存储表示实现；采用链式存储表示方法实现：比较两种方法的优劣。 2.从单链表中删除指定的元素x，若x在单链表中不存在，给出提示信息。 要求： ①指定的值x由键盘输入； ②程序能处理空链表的情况。 3.设有头结点的单链表，编程对表中的任意值只保留一个结点，删除其余值相同的结点。 要求： ①该算法用函数（非主函数)实现； ②在主函数中调用创建链表的函数创建一个单链表，并调用该函数，验证算法的正确性。LinkedList Exchange（LinkedList HEAD,p) //HEAD是单链表头结点的指针，p是链表中的一个结点。本算法将p所指结点与其后 继结点交换。 （q=head->next；//q是工作指针，指向链表中当前待处理结点。 pre=head；//pre是前驱结点指针，指向q的前驱。 while（q'=null &&q1=p)(pre=q；q=q->next；]/未到p结点，后移指针。 if（p->next==null)printf(“p无后继结点\n”）；/p是链表中最后一个结点，无后继。 else/处理p和后继结点交换 （q=p->next；//暂存p的后继。 pre->next=q://p前驱结点的后继指向p的后继。 p->next=q->next；//p的后继指向原p后继的后继。 q->next=p：//原p后继的后继指针指向p。} }//算法结束。 4.已知非空单链表第一个结点由head指出，请写一算法，交换p所指结点与其下一个结点在链表中的位置。 要求： 哈尔滨工业大学计算机科学与技术学院 实验报告 课程名称：数据结构与算法 课程类型：必修 实验项目名称：线性表实验 实验题目：算术表达式求值 班级：0903201 学号：1090320110 姓名：王岳 一、实验目的 二、实验要求及实验环境 三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系） 1．逻辑设计 2．物理设计 四、测试结果 五、系统不足与经验体会 六、附录：源代码（带注释） #include else { this -> top--; return this -> ss[this -> top + 1]; } } void push(elementtype x) { if (this -> top == 511) printf("error:full!!!\n"); else { this -> top++; this -> ss[this -> top] = x; } } }; void change(int &i,int &j,double *a,char *input,stack 实验一线性表及其应用 一、实验目的 1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。 2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、实现提示 1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。 在此，我们利用C语言的结构体类型定义顺序表： #define MAXSIZE 1024 typedef int elemtype; /* 线性表中存放整型元素*/ typedef struct { elemtype vec[MAXSIZE]; int len; /* 顺序表的长度*/ }sequenlist; 将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。 2. 注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。 3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下： typedef int elemtype; typedef struct node 班级：：学号： 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义； 2、掌握线性表的基本操作，如建立、查找、插入和删除等。 二、实验容 定义一个包含学生信息（学号，，成绩）的顺序表和链表（二选一），使其具有如下功能： (1) 根据指定学生个数，逐个输入学生信息； (2) 逐个显示学生表中所有学生的相关信息； (3) 根据进行查找，返回此学生的学号和成绩； (4) 根据指定的位置可返回相应的学生信息（学号，，成绩）； (5) 给定一个学生信息，插入到表中指定的位置； (6) 删除指定位置的学生记录； (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include typedef int Status; // 定义函数返回值类型 typedef struct { char num[10]; // 学号 char name[20]; // double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; return OK; 数据结构实验报告 实验名称：实验1——线性表 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 1、实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 2、实验内容： 题目1： 线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。 2. 程序分析 存储结构 带头结点的单链表 关键算法分析 1.头插法 a、伪代码实现：在堆中建立新结点 将x写入到新结点的数据域 修改新结点的指针域 修改头结点的指针域,将新结点加入链表中 b、代码实现： Linklist::Linklist(int a[],int n) 堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 b、代码实现: Linklist::Linklist(int a[],int n,int m)取链表长度函数 a、伪代码实现：判断该链表是否为空链表，如果是，输出长度0 如果不是空链表，新建立一个temp指针，初始化整形数n为0 将temp指针指向头结点 判断temp指针指向的结点的next域是否为空，如果不是，n加一，否 则return n 使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next 域为0，返回n b 、代码实现 void Linklist::Getlength()Linklist(); cout< 实验1 顺序表基本操作 实验目的 1．熟悉C语言的上机环境，掌握C语言的基本结构。 2．会定义线性表的顺序存储结构。 3．熟悉对顺序表的一些基本操作和具体的函数定义。 注意事项 在做第一次“数据结构”课程实验之前，要在硬盘上建立好自己的工作目录，专门来存储你所做的实验程序及相关信息，以后每次做实验都采用这个目录。 实验内容 该程序的功能是对元素类型为整型的顺序表进行一些操作。该程序包括顺序表结构类型的定义以及对顺序表操作的具体的函数定义和主函数。 /* 定义ElemType为int类型*/ typedef int ElemType; /*顺序表存储空间的总分配量*/ #define MAXSIZE 100 /* 顺序存储类型*/ typedef struct {ElemType data[MAXSIZE]; /*存放线性表的数组*/ int length; /* length是顺序表的长度*/ }SeqList; /* 初始化顺序表*/ SeqList Seq ListInit( ) /* 清空顺序表*/ SeqList ListClear(SeqList L) /* 求顺序表长度*/ int ListLength(SeqList L) /* 检查顺序表是否为空*/ int ListEmpty(SeqList L) /*检查顺序表是否为满*/ int ListFull(SeqList L) /* 遍历顺序表*/ void ListTraverse(SeqList L) /* 从顺序表中查找元素*/ ElemType ListGet(SeqList L ,int i) /* 从顺序表中查找与给定元素值相同的元素在顺序表中的位置*/ int ListLocate(SeqList L, ElemType x) /* 向顺序表中插入元素*/ SeqList ListInsert(SeqList L，int i，ElemType x) /* 从顺序表中删除元素*/ SeqList ListDelete(SeqList L,int i) /*求顺序表中元素的前驱*/ ElemType ListPrior (SeqList L,ElemType e) /*求顺序表中元素的后继*/ ElemType ListNext(SeqList L,ElemType e) 班级: 姓名: 学号: 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义; 2、掌握线性表的基本操作,如建立、查找、插入与删除等。 二、实验内容 定义一个包含学生信息(学号,姓名,成绩)的顺序表与链表(二选一),使其具有如下功能: (1) 根据指定学生个数,逐个输入学生信息; (2) 逐个显示学生表中所有学生的相关信息; (3) 根据姓名进行查找,返回此学生的学号与成绩; (4) 根据指定的位置可返回相应的学生信息(学号,姓名,成绩); (5) 给定一个学生信息,插入到表中指定的位置; (6) 删除指定位置的学生记录; (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include { char num[10]; // 学号 char name[20]; // 姓名 double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; return OK; } Status GetElem(LinkList L,int i,ElemType &e) // 访问链表,找到i位置的数据域,返回给 e { LinkList p; p=L->next; 实验报告 课程名称____数据结构上机实验__________ 实验项目______线性表的应用____________实验仪器________PC机___________________ 系别_____电子信息与通信学院___ 专业________ ___ 班级/学号______ __ 学生姓名______ ___________ 实验日期_______________________ 成绩_______________________ 指导教师_______________________ 实验一.线性表的应用 1.实验目的：掌握线性链表的存储、运算及应用。利用链 表实现一元多项式计算。 2.实验内容： 1)编写函数，实现用链表结构建立多项式； 2)编写函数，实现多项式的加法运算； 3)编写函数，实现多项式的显示； 4)测试：编写主函数，它定义并建立两个多项式，显示 两个多项式，然后将它们相加并显示结果。变换测试用的多项式，检查程序的执行结果。 选做内容：修改程序，选择实现以下功能： 5)多项式求值：编写一个函数，根据给定的x值计算并 返回多项式f(x)的值。测试该函数（从终端输入一个x的值，调用该函数并显示返回结果）。 6)多项式相减：编写一个函数，求两个多项式相减的多 项式。 7)多项式相乘：编写一个函数，求两个多项式的乘积多 项式。 3.算法说明： 1)多项式的建立、显示和相加算法见讲义。可修改显示 函数，使输出的多项式更符合表达规范。 2)多项式减法：同次项的系数相减（缺项的系数是0）。 例如a(x)=-5x2+2x+3，b(x)= -4x3+3x，则a(x)-b(x) =4x3-5x2-x+3。提示：a(x)-b(x) = a(x)+(-b(x))。 3)多项式乘法：两个多项式的相乘是“系数相乘，指数 相加”。算法思想是用一个多项式中的各项分别与另 一个多项式相乘，形成多个多项式，再将它们累加在 一起。例如，a(x)=-5x2+2x+3，b(x)=-4x3+3x，则 a(x)*b(x) = (-4x3)*(-5x2+2x+3)+(3x)*(-5x2+2x+3) = (20x5-8x4-12x3) + (-15x3+6x2+9x) = 20x5-8x4-27x3+6x2+9x。 4.实验步骤： 根据实验报告的要求，我对文件夹里的C文件进行了丰 富和修改，步骤如下： 链表结构建立多项式： typedef struct polynode { float coef; //系数 int exp; //指数 struct polynode *next; //下一结点指针 } PNode; 编写函数，实现多项式的加法运算； PNode * PolyAdd (PNode *f1, PNode *f2) //实现加法功能。 《计算机软件技术基础》实验报告 I —数据结构 实验一、约瑟夫斯问题求解 一、问题描述 1.实验题目：编号 1,2,....,n的n个人顺时针围坐一圈，每人持有一个密码（正整数）。 开始选择一个正整数作为报数上限m，从第一个人开始顺时针自 1 报数，报到m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从 1 报数，直至所有人全部出列。 2. 基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的编号。 3. 测试数据： n=7,7 个人的密码依次为：3,1,7,2,4,8, 4.m初值为6（正确的出列顺序 应为 6,1,4,77,2,3）。 二、需求分析 1. 本程序所能达到的基本可能： 该程序基于循环链表来解决约瑟夫问题。用循环链表来模拟n 个人围坐一圈，用链表 中的每一个结点代表一个人和他所代表的密码。在输入初始密码后m，对该链表进行遍历，直到第 m个结点，令该结点的密码值作为新的密码值，后删除该结点。重复上述过程，直至所有的结点被释放空间出列。 2. 输入输出形式及输入值范围： 程序运行后提示用户输入总人数。输入人数 n 后，程序显示提示信息，提示用户输入第 i个人的密码，在输入达到预定次数后自动跳出该循环。程序显示提示信息，提示用户输入 初始密码，密码须为正整数且不大于总人数。 3．输出形式 提示用户输入初始密码，程序执行结束后会输出相应的出列结点的顺序，亦即其编号。 用户输入完毕后，程序自动运行输出运行结果。 4.测试数据要求： 测试数据 n=7，7 个人的密码依次为：3， 1， 7， 2， 4， 8， 4。 m初值为 6（正确的出列 顺序应为6， 1， 4，7， 2， 3， 5）。 三、概要设计 为了实现上述功能，应用循环链表来模拟该过程，用结构体来存放其相应的编号和密码 实验报告 实验一线性表 实验目的： 1.理解线性表的逻辑结构特性； 2.熟练掌握线性表的顺序存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用； 3.熟练掌握线性表的链表存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用； 4.掌握双向链表和循环链表的的描述方法，以及在该存储结构下的基本操作。 实验原理： 线性表顺序存储结构下的基本算法； 线性表链式存储结构下的基本算法； 实验内容： 2－21设计单循环链表，要求： （1）单循环链表抽象数据类型包括初始化操作、求数据元素个数操作、插入操作、删除操作、取消数据元素操作和判非空操作。 （2）设计一个测试主函数，实际运行验证所设计单循环链表的正确性。 2－22 .设计一个有序顺序表，要求： （1）有序顺序表的操作集合有如下操作：初始化、求数据元素个数、插入、删除和取数据元素。有序顺序表与顺序表的主要区别是：有序顺序表中的数据元素按数据元素值非递减有序。 （2）设计一个测试主函数，实际运行验证所设计有序顺序表的正确性。 （3）设计合并函数ListMerge（L1,L2,L3）,功能是把有序顺序表L1和L2中的数据元素合并到L3，要求L3中的数据元素依然保持有序。并设计一个主函数，验证该合并函数的正确性。 程序代码： 2－21（1）头文件LinList.h如下： typedef struct node { DataType data; struct node *next; }SLNode; /*（1）初始化ListInitiate(SLNode * * head)*/ void ListInitiate(SLNode * * head) { /*如果有内存空间，申请头结点空间并使头指针head指向头结点*/ if((*head=(SLNode *)malloc(sizeof(SLNode)))==NULL)exit(1); 学 《数据结构》课程 实验报告 实验名称：线性表基本操作的实现实验室(中心)： 学生信息： 专业班级： 指导教师： 实验完成时间： 2016 实验一线性表基本操作的实现 一、实验目的 1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。 2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容及要求 1.顺序线性表的建立、插入、删除及合并。 2.链式线性表的建立、插入、删除及连接。 三、实验设备及软件 计算机、Microsoft Visual C++ 6.0软件 四、设计方案（算法设计） ㈠采用的数据结构 本程序顺序表的数据逻辑结构为线性结构，存储结构为顺序存储；链表的数据逻辑结构依然为线性结构，存储结构为链式结构。 ㈡设计的主要思路 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度，顺序表的长度和元素由用户输入； 2.利用前面建立的顺序表，对顺序表进行插入、删除及合并操作； 3.建立一个带头结点的单链表，结点的值域为整型数据，链表的元素由用户输入； 4.对前面建立的链表进行插入、删除及连个链表的连接操作； ㈢算法描述 1、顺序表 void Init(sqlist &);//初始化顺序表 BOOL Inse(sqlist &,int,char); //在线性表中插入元素 BOOL del(sqlist&,int,char &); //在线性表中删除元素 int Loc(sqlist,char); //在线性表中定位元素 void print(sqlist); //输出顺序表 void combine( sqlist & , sqlist & , sqlist &);//两个线性表的合并 2、链表 void CreaL(LinkList &,int); //生成一个单链表 BOOL LInsert(LinkList &,int,char); //在单链表中插入一个元素 BOOL LDele(LinkList &,int,char &); //在单链表中删除一个元素 BOOL LFind_key(LinkList,char,int &); //按关键字查找一个元素 BOOL LFind_order(LinkList,char &,int); //按序号查找一个元素 void LPrint(LinkList); //显示单链表所有元素 void LUnion(LinkList &,LinkList &,LinkList &,int); //两个链表的连接 五、程序代码 1、顺序表 #include 数据结构实验报告全集
C语言数据结构线性表的基本操作实验报告
淮海工学院数据结构第一次实验报告
数据结构_实验1_线性表的基本操作
数据结构线性表实验报告
数据结构第一次实验报告
数据结构实验一题目一线性表实验报告
数据结构第一次实验报告
数据结构线性表实验报告
哈工大 数据结构 实验一 线性表的实验
《数据结构》实验一 线性表及其应用
数据结构实验一 实验报告
数据结构实验一题目一线性表实验报告
数据结构-实验一顺序表的基本操作
数据结构实验一 实验报告
数据结构线性表的应用实验报告
数据结构实验报告—约瑟夫问题求解
数据结构线性表实验报告
数据结构实验线性表基本操作
- 《数据结构》实验一 线性表及其应用
- 数据结构线性表实验报告
- 实验报告 数据结构 线性表的合并
- 数据结构实验一-线性表
- C语言数据结构线性表的基本操作实验报告
- 数据结构实验报告实验一线性表链式存储运算的算法实现
- 数据结构线性表的应用实验报告
- 数据结构线性表上机报告
- (完整版)数据结构线性表的应用实验报告
- 数据结构线性表实验报告
- 数据结构线性表实验报告
- 数据结构实验报告 线性表
- 数据结构线性表实验报告
- 数据结构实验(1)线性表及其应用
- [信息与通信]贵州大学数据结构实验1-线性表及应用
- 数据结构实验一题目一线性表实验报告.pdf
- 数据结构实验一题目一线性表实验报告
- 数据结构 线性表操作实验报告
- 数据结构实验报告线性表及其应用
- 数据结构线性表的应用实验报告