C++与数据结构第一次上机实验线性表.docxVIP

实验一 线性表数据结构（C++语言描述）实验报告    实验一 线性表 实验目的和要求： 掌握线性表顺序存储结构和链式存储结构的基本思想； 掌握顺序表和单链表的基本操作。 实验原理： 线性表的定义：数据之间存在一对一的线性关系的数据结构的称为线性结构，也可称为线性表。 顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系是由元素的存储的存储位置来表示的，通常用一维数组来表示。 顺序表的优点：存储密度大、空间利用率高、，无需为表中元素之间的逻辑关系而增加额外的存储空间。 顺序表的缺点：插入和删除操作需要移动大量的元素；表的容量难以确定；造成空间的“碎片”。 在程序设计语言中，通常用一维数组来表示表的存储区域。假设用data[ListSize]来表示一段顺序表，其中ListSize是一个根据实际问题规模定义的足够大的整数，另外用一个实际变量length来表示当前实际元素的个数，表中的数据从data[0]开始依次存放，表空时length=0. 链式存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系是用指针来表示的。 链式存储结构的优点：插入和删除操作方便省时。 链式存储结构的缺点：存储空间的开销大。 链式存储的方法是使用结点构造链。每个结点分为数据域和指针域两部分组成。数据域用来存放数据元素，指针域用来存放后继存储单元的地址。 实验内容 对于给定的单链表L，设计一个算法，删除L中值为x的结点的直接前驱结点。 已知两个单链表LA和LB分别表示两个集合，其元素递增排列，设计算法求出LA和LB的交集C，要求C同样以递增的单链表形式存储。 实验设计： 1、（1）伪算法： 建立链表L； 循环有哪些信誉好的足球投注网站数据值为x的前一结点，若已至表尾，且其值不为value，警告，退出程序；否则，重新拉链，将数值为x的结点的前一结点标记，将被标记的结点断开，回收被删除的结点的内存空间，将链表长度减1。 （2）实验代码： //对给定的链表L，设计一个算法，删除L中值为x的结点的直接前驱结点 #includestdlib.h #includeiostream 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); void InsertL(char zifu); void Print(); char Removevalue(char value); private: ListNode *first,*last; int length; }; void List::Great(List L) //建立链表函数 { char n; int l,i; cout请输入链表的长度：; cinl; cout请输入数据:; for(i=1;il+1;i++) { cinn; 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!=NULLp-link-data!=value) {h=p;p=p-link; } if(p-link==NULLp-data!=value)