实验一线性表数据结构（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的结点的直接前驱结点#include<stdlib.h>#include<iostream>usingnamespacestd;classListNode//建立结点类{public:chardata;ListNode*link;ListNode(){link=NULL;}ListNode(int&item,ListNode*next=NULL){data=item;link=next;}};classList//建立链表类{public:List(){ListNode*q=newListNode;first=last=q;}voidGreat(ListL);voidInsertL(charzifu);voidPrint();charRemovevalue(charvalue);private:ListNode*first,*last;intlength;};voidList::Great(ListL)//建立链表函数{charn;intl,i;cout<<"请输入链表的长度：";cin>>l;cout<<"请输入数据:";for(i=1;i<l+1;i++){cin>>n;L.InsertL(n);}L.length++;}voidList::InsertL(charzifu){ListNode*newcode=newListNode;newcode->data=zifu;newcode->link=NULL;if(first==NULL){first=newcode;last=newcode;}elselast->link=newcode;last=newcode;}charList::Removevalue(charvalue)//该函数实现删除值为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)return0;q=h->link;h->link=q->link;deleteq;length--;returnvalue;}voidList::Print()//打印链表{ListNode*p;p=first->link;while(p!=NULL){cout<<p->data<<"";p=p->link;}cout<<endl;}intmain(){charvalue;Lista;a.Grea