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<stdlib.h>

#include<iostream>

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<l+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)

前一结点

{

ListNode *p=first,*q,*h; //建立链表函数 //该函数实现删除值为x的结点的

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->data<<" ";

p=p->link;

}

cout<<endl;

}

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);

L …… 此处隐藏：2609字，全部文档内容请下载后查看。喜欢就下载吧 ……