數(shù)據(jù)結構實驗三

1、.實驗三線性表操作一 實驗目的1 掌握線性表的基本操作：插入、刪除、查找。2 掌握鏈表遍歷器的使用方法。二 實驗容1 創(chuàng)建線性表類。線性表的存儲結構使用鏈表。2 提供操作 :自表首插入元素、刪除指定元素、搜索表中是否有指定元素、輸出鏈表。3 接收鍵盤錄入的一系列整數(shù)（例10,25,8,33,60 ）作為節(jié)點的元素值，創(chuàng)建鏈表。輸出鏈表容。4 輸入一個整數(shù)（例33），在鏈表中進行搜索，輸出其在鏈表中的位置。如果不存在輸出 0。5 使用鏈表遍歷器實現(xiàn)鏈表的反序輸出。6 創(chuàng)建兩個有序鏈表，使用鏈表遍歷器實現(xiàn)鏈表的合并。三 知識點介紹1 線性表（亦作順序表）是最基本、最簡單、也是最常用的一種數(shù)據(jù)結構

2、。線性表中數(shù)據(jù)元素之間的關系是一對一的關系，即除了第一個和最后一個數(shù)據(jù)元素之外，其它數(shù)據(jù)元素都是首尾相接的。線性表的邏輯結構簡單，便于實現(xiàn)和操作。因此，線性表這種數(shù)據(jù)結構在實際應用中是廣泛采用的一種數(shù)據(jù)結構。2 鏈表遍歷器有兩個共享成員Initialize 和 Next 。 Initialize 返回一個指針，該指針指向第一個鏈表節(jié)點中所包含的數(shù)據(jù)，同時把私有變量location設置為指向鏈表的第一個節(jié)點，該變量用來跟蹤我們在鏈表中所處的為位置。成員Next 用來調整location ，使其指向鏈表中的下一個節(jié)點，并返回指向該數(shù)據(jù)域的指針。四 源碼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);/創(chuàng)建鏈表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 請輸入數(shù)據(jù)： ;for(int i=0;i ai;cout 創(chuàng)建鏈表： ;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 創(chuàng)建有序鏈表1：;j.Create(b