1、實驗三線性表操作一實驗目的1 掌握線性表的基本操作：插入、刪除、查找。2 掌握鏈表遍歷器的使用方法。二實驗內(nèi)容1 創(chuàng)建線性表類。線性表的存儲結構使用鏈表。2 提供操作：自表首插入元素、刪除指定元素、搜索表中是否有指定元素、輸出鏈表。3 接收鍵盤錄入的一系列整數(shù)（例 10,25,8,33,60）作為節(jié)點的元素值，創(chuàng)建鏈表。輸出鏈表內(nèi)容。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ù)，同時把私有變量locatio n 設置為指向鏈表的第一個節(jié)點，該變量用來跟蹤我們在鏈表中所處的為位置。成員Next 用來調(diào)整locati on ，使其指向鏈表中的下一個節(jié)點，并返回指向該數(shù)據(jù)域的指針。四源碼實驗三線性表操作Lin earList.htempla

3、tevclass T#ifndef LINEARLIST_ HN CLUDED#defi ne LINEARLIST_ HN CLUDED templatevclass T class Lin earListNode;templatevclass T class Lin earList;templatevclass Tclass Lin earListlteratorpublic:T* In itialize(c onst Lin earList& c);T* Next();private:Lin earListNode *locati on;；templatevclass Tclas

4、s Lin earListNodefriend Lin earList;friend Lin earListlterator;private:T data;LinearListNode *link;class Lin earList friend Lin earListlterator;public:Li nearList()first = 0;Li nearList();Li nearList & In sert(T &x);自表首插入元素templatevclass TLi nearListvT & Delete(i nt k, T& x);刪除指定元素in

5、t Search(co nst T& x);搜索表中是否有指定元素void Output。;/輸出鏈表Li nearListvT & Create( int *a, i nt n);/創(chuàng)建鏈表void Reverse。;/反序輸出void Merge(Li nearListvTthat);/鏈表合并private:LinearListNode *first;#en dif / LINEARLIST_H_INCLUDEDLin earList.cpp#in clude#i nclude Lin earList.husing n amespace std;T* Lin earLis

6、tlterator:l nitialize(c onst Li nearListvT & c)locati on = c.first;if(locati on)retur n &locati on-data;return 0; templatevclass TT* Li nearListIterator:Next()if(!locati on)return 0;locati on = locati on-li nk; if(locati on)retur n &locati on-data;return 0;templatevclass TLi nearListvT:L

7、i nearList()Lin earListNode *n ext; while(first)n ext = first-li nk;delete first;first = n ext;templatevclass TLinearListvT& LinearList:lnsert(T &x)Lin earListNode *y = new Lin earListNode;y-data = x; y-li nk = first; first = y;return *this; templatevclass TLinearListvT& LinearList:Delet

8、e(int k, T& x)if(k1|!first)cout OUT OF BOUNDS!;Lin earListNode *p = first;if(k=1)first = first-li nk;elseLin earListNode *q = first;for(i nt in dex=1;i ndexli nk;if(!q|!q-li nk)cout li nk;q-li nk = p-li nk;x = p-data;delete p; return *this; templatevclass Tin t Lin earList:Search(co nst T& x

9、)Lin earListNode *curre nt = first; int in dex = 1;while(curre nt&curre nt-data!=x)curre nt = curre nt-li nk;in dex+;if(curre nt)return in dex;return 0;templatevclass Tvoid Lin earList:Output()Lin earListNode *curre nt;for(curre nt=first;curre nt;curre nt=curre nt-li nk)if(curre nt-li nk)cout da

10、ta ;elsecout data void Lin earList:Reverse()LinearListNode *p1,*p2,*p3,*current;pl = first;p2 = first-li nk;while(p2)p3 = p2-li nk;p2-li nk = p1;p1 = p2;p2 = p3;first-li nk = 0;first = p1;*/ templatevclass Tvoid Lin earList:Reverse()Lin earListIterator i;Lin earList l;int* x;x = i.I nitialize(*this)

11、;while(x)l.I nsert(*x);x = i.Next();I.Output(); templatevclass TLin earList& Lin earList:Create(i nt *a, int n)for(i nt i=0;i void Lin earList:Merge(L in earList that)Lin earListIterator i1,i2;Lin earList l;int *x1,*x2;x1 = il.I nitialize(*this);x2 = i2.I ni tialize(that);while(x1 &x2)if(*x1

12、*x2)l.I nsert(*x1);x1 = i1.Next();elsel.I nsert(*x2);x2 = i2.Next();while(x1)l.I nsert(*x1);x1 = i1.Next();while(x2)l.I nsert(*x2);x2 = i2.Next();l.0utput();#in elude 五測試用例mai n.cpp#in clude #in clude Lin earList.h #in clude Lin earList.cpp using n amespace std;int mai n()int nu m,z;cout num;int *a

13、= new in t nu m;cout 請輸入數(shù)據(jù)：;for(i nt i=0;i ai;cout l,j,k;I.Create(a, nu m);I.Output();cout 該鏈表反序輸出：;I.Reverse();cout z;cout 它在表中的位置(不存在為 0)vv en dl;int *b = new in t5;b0 = 1;b1 = 3;b2 = 5;b3 = 7;b4 = 9;int *c = new in t5;c0 = 0；c1 = 2;c2 = 4;c3 = 6;c4 = 8;cout 創(chuàng)建有序鏈表 1:j.Create(b,5);j. Output();cout 創(chuàng)建有序鏈表 2:k. Create(c,5);k.Output();cout 合并兩表：;j.Merge(k)