数据结构实验三

1、.实验三线性表操作一 实验目的1 掌握线性表的基本操作：插入、删除、查找。2 掌握链表遍历器的使用方法。二 实验容1 创建线性表类。线性表的存储结构使用链表。2 提供操作 :自表首插入元素、删除指定元素、搜索表中是否有指定元素、输出链表。3 接收键盘录入的一系列整数（例10,25,8,33,60 ）作为节点的元素值，创建链表。输出链表容。4 输入一个整数（例33），在链表中进行搜索，输出其在链表中的位置。如果不存在输出 0。5 使用链表遍历器实现链表的反序输出。6 创建两个有序链表，使用链表遍历器实现链表的合并。三 知识点介绍1 线性表（亦作顺序表）是最基本、最简单、也是最常用的一种数据结构

2、。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。2 链表遍历器有两个共享成员Initialize 和 Next 。 Initialize 返回一个指针，该指针指向第一个链表节点中所包含的数据，同时把私有变量location设置为指向链表的第一个节点，该变量用来跟踪我们在链表中所处的为位置。成员Next 用来调整location ，使其指向链表中的下一个节点，并返回指向该数据域的指针。四 源码LinearList.h.#ifndef LI

3、NEARLIST_H_INCLUDED#define LINEARLIST_H_INCLUDEDtemplateclass LinearListNode;templateclass LinearList;templateclass LinearListIteratorpublic:T* Initialize(const LinearList& c);T* Next();private:LinearListNode *location;templateclass LinearListNodefriend LinearList;friend LinearListIterator;private:T

4、 data; LinearListNode *link;.templateclass LinearListfriend LinearListIterator;public:LinearList()first = 0;LinearList();LinearList& Insert(T &x);/自表首插入元素LinearList& Delete(int k, T& x);/删除指定元素int Search(const T& x);/搜索表中是否有指定元素void Output();/输出链表LinearList& Create(int *a, int n);/创建链表void Reverse()

5、;/ 反序输出void Merge(LinearList that);/链表合并private:LinearListNode *first;#endif / LINEARLIST_H_INCLUDEDLinearList.cpp#include#include LinearList.husing namespace std;.templateT* LinearListIterator:Initialize(const LinearList& c)location = c.first;if(location)return &location-data;return 0;templateT* Li

6、nearListIterator:Next()if(!location)return 0;location = location-link;if(location)return &location-data;return 0;templateLinearList:LinearList()LinearListNode *next;while(first)next = first-link;delete first;.first = next;templateLinearList& LinearList:Insert(T &x)LinearListNode *y = new LinearListN

7、ode;y-data = x;y-link = first;first = y;return *this;templateLinearList& LinearList:Delete(int k, T& x)if(k1|!first)cout OUT OF BOUNDS!;LinearListNode *p = first;if(k=1)first = first-link;elseLinearListNode *q = first;for(int index=1;indexlink;if(!q|!q-link).cout link;q-link = p-link;x = p-data;dele

8、te p;return *this;templateint LinearList:Search(const T& x)LinearListNode *current = first;int index = 1;while(current¤t-data!=x)current = current-link;index+;if(current)return index;return 0;templatevoid LinearList:Output()LinearListNode *current;.for(current=first;current;current=current-lin

9、k)if(current-link)cout data ;elsecout data endl;/*templatevoid LinearList:Reverse()LinearListNode *p1,*p2,*p3,*current;p1 = first;p2 = first-link;while(p2)p3 = p2-link;p2-link = p1;p1 = p2;p2 = p3;first-link = 0;first = p1;*/.templatevoid LinearList:Reverse()LinearListIterator i;LinearList l;int* x;

10、x = i.Initialize(*this);while(x)l.Insert(*x);x = i.Next();l.Output();templateLinearList& LinearList:Create(int *a, int n)for(int i=0;in;i+)Insert(ai);return *this;templatevoid LinearList:Merge(LinearList that)LinearListIterator i1,i2;LinearList l;int *x1,*x2;.x1 = i1.Initialize(*this);x2 = i2.Initia

11、lize(that);while(x1&x2)if(*x1*x2)l.Insert(*x1);x1 = i1.Next();elsel.Insert(*x2);x2 = i2.Next();while(x1)l.Insert(*x1);x1 = i1.Next();while(x2)l.Insert(*x2);x2 = i2.Next();l.Output();#include .五 测试用例main.cpp#include #include LinearList.h#include LinearList.cppusing namespace std;int main()int num,z;c

12、out num;int *a = new intnum;cout 请输入数据： ;for(int i=0;i ai;cout 创建链表： ;LinearList l,j,k;l.Create(a,num);l.Output();cout 该链表反序输出：;l.Reverse();cout z;cout 它在表中的位置（不存在为0）： l.Search(z) endl;int *b = new int5;b0 = 1;b1 = 3;b2 = 5;b3 = 7;b4 = 9;int *c = new int5;c0 = 0;c1 = 2;c2 = 4;c3 = 6;c4 = 8;cout 创建有序链表1：;j.Create(b