数据结构第二章线性表学习笔记
1.? ??C++程序設(shè)計(jì)模板? ?（關(guān)于template的解釋）【以下內(nèi)容摘自百度】
函數(shù)聲明格式 template <class(或typename)?any(或任意符合規(guī)則的名稱)>（如果還有其他類型名，就用逗號隔開） 返回類型 函數(shù)名(形參表); 函數(shù)定義和聲明格式基本相同，形參表要加上形參名，分號改為函數(shù)體。 聲明的例子： ? ?? 1 template <class type1, class type2> 2 type1 add(type1,type2); 3 template <class type1, class type2> 4 type1 add(type1 a,type2 b) 5 {return a + (type1)b;}?
也可以直接定義函數(shù)，不聲明。 說明： template是一個聲明模板的關(guān)鍵字，表示聲明一個模板關(guān)鍵字class不能省略，如果形參類型多于一個 ，每個形參前都要加class <類型 形參表>可以包含基本數(shù)據(jù)類型或類類。 1 #include <iostream> 2 using std::cout; 3 using std::endl; 4 //聲明一個函數(shù)模版,用來比較輸入的兩個相同數(shù)據(jù)類型的參數(shù)的大小，class也可以被typename代替， 5 //T可以被名稱字代替，只要符合命名規(guī)則即可。 6 template <class T> 7 T min(T& x,T& y) 8 { return(x<y)?x:y;} 9 int main( ) 10 { 11 int n1 = 2,n2 = 10; 12 double d1 = 1.5,d2 = 5.6; 13 cout<< "較小整數(shù):"<<min(n1,n2)<<endl; 14 cout<< "較小實(shí)數(shù):"<<min(d1,d2)<<endl; 15 system("PAUSE"); 16 return 0; 17 }?
程序運(yùn)行結(jié)果： 程序分析：main()函數(shù)中定義了兩個整型變量n1 , n2 兩個雙精度類型變量d1 , d2然后調(diào)用min( n1, n2); 即實(shí)例化函數(shù)模板T min(T x, T y)其中T為int型，求出n1,n2中的最小值．同理調(diào)用min(d1,d2)時，求出d1,d2中的最小值．? ?2.模板
? ? ? 一.模板概述
? ? （1）模板時對具有相同特性的函數(shù)或類的再抽象，模板是一種參數(shù)化的多態(tài)性工具。
? ? （2）所謂參數(shù)化多態(tài)性，是指將程序所處理的對象的類型參數(shù)化，使一段程序代碼可以用于處理多種不同類型? ? ? ? ? ? ? ?的對象。
? ?（3）采用模板編程，可以為各種邏輯功能相同而數(shù)據(jù)類型不同的程序提供一種代碼共享的機(jī)制。
?
? ? ? ?模板實(shí)例化話：函數(shù)通過參數(shù)的實(shí)例化可以構(gòu)建具體的函數(shù)或類，稱為模板函數(shù)和模板類。
? ? ? ??
?
函數(shù)模板定義：template<模板形參表> 返回值類型 函數(shù)名（參數(shù)表） {函數(shù)體 }函數(shù)模板實(shí)例：
template<typename T>//模板定義，T為模板參數(shù)。
T abs(T a) //定義函數(shù)模板
{
return a<?-a:a;
}
說明：template是模板定義的關(guān)鍵字。?<模板形參表>中包含一個或多個用逗號分開的模板形式參數(shù)，每一項(xiàng)
關(guān)鍵字class或typename引導(dǎo)一個由用戶命名的標(biāo)識符，此標(biāo)識符為模板參數(shù)(用來進(jìn)行類型傳遞)
模板參數(shù)表示一種數(shù)據(jù)類型，可以是基本數(shù)據(jù)類型或類類型。該數(shù)據(jù)類型在發(fā)生實(shí)際函數(shù)調(diào)用時將被實(shí)例化，
即調(diào)用出的實(shí)際數(shù)據(jù)類型替代它。 類模板：同函數(shù)模板一樣，類模板是參數(shù)化的類，即用于實(shí)現(xiàn)數(shù)據(jù)類型參數(shù)化的類。應(yīng)用類模板可以使類中的數(shù)據(jù)成員 成員函數(shù)的參數(shù)及成員函數(shù)的返回值根據(jù)模板參數(shù)匹配情況取任意數(shù)據(jù)類型。 類模板定義：template<模板形參表>class 類模板名{成員的聲明；}
實(shí)例：
template <typename T> ? ? ? ? //typename或class
class Square
{??
?
T x;?public:
? ? ? ? Square(T xx):x(xx){ ?}
? ? ? ? T fun(){return x*x;}
};?對于成員函數(shù)在類外定義的時候，有何變化：
double Rectangle::circumference( )
{ ? //普通類的成員函數(shù)在類外定義
return 2*length*width;
}template<class T>
T Rectangle<T>::circumference( )
{ ?//類模板的成員函數(shù)在類外的定義
return 2*length*width;
}?n 設(shè)計(jì)函數(shù)模板，實(shí)現(xiàn)求解兩個數(shù)的最小值：
#include<bits/stdc++.h> using namespace std; template <typename T> T minn(T a,T b) {return a>b?b:a; } int main() {int a,b;double c,d;cin>>a>>b;cin>>c>>d;cout<<minn(a,b)<<endl;cout<<minn(c,d);return 0; } View Coden 設(shè)計(jì)函數(shù)模板，實(shí)現(xiàn)對一組數(shù)據(jù)求和（數(shù)據(jù)放在一維數(shù)組中）：
#include<bits/stdc++.h> using namespace std; template <typename T> T add(T a[],int n) {T ans=0;for(int i=0;i<n;i++){ans+=a[i];}return ans; } int main() {int a[5]={0,1,2,3,4};double b[5]={1.1,2.2,3.3,4.4,5.5};cout<<add(a,5)<<endl;cout<<add(b,5)<<endl;return 0; } View Coden 設(shè)計(jì)一個關(guān)于正方形的類模板，類的成員函數(shù)包括計(jì)算正方形的面積、周長、邊長等函數(shù)，并且有帶參的構(gòu)造函數(shù)，類的成員函數(shù)需要在類的外部實(shí)現(xiàn)：
#include<bits/stdc++.h> using namespace std; template <typename T> class Square{private:T length;public:Square(T x);~Square(){};T area();T Perimeter(); }; template <class T> Square<T>::Square(T x)///此處不應(yīng)該返回void {length=x; } template <class T> T Square<T>::area() {return length*length; } template <class T> T Square<T>::Perimeter() {return length*4; } int main() {Square<int> intx(5);cout<<intx.area()<<endl;cout<<intx.Perimeter()<<endl;Square<double> doublex(2.5);cout<<doublex.area()<<endl;cout<<doublex.Perimeter()<<endl;return 0; } View Code?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 補(bǔ)充：指針
?在存儲空間里存放的信息可以 通過兩種方式訪問（目前我所知道的）：
①通過定義的變量名稱進(jìn)行訪問。例如：int a=5；那么可以通過變量名稱a進(jìn)行訪問存儲空間里的信息。
②通過指針變量進(jìn)行訪問：
#include<iostream> using namespace std; int main() {int a=5;int *p=&a;///此處即為定義一個整型的指針變量， ///然后將變量a的地址通過&取址符賦值給*p,注意p只是一個指針變量也可以改變p的值 cout<<p<<endl;///此處輸出的僅為a的地址結(jié)果為 0x69fef8cout<<*p<<endl;///*為指針變量所指向的地址。 5return 0; }指針：一個變量的地址稱為該變量的指針。
指針變量：一個特殊的變量，專門存放另一個變量地址的變量。（指針變量的值是一個地址）
區(qū)分指針和指針變量：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（1）一個指針是一個地址，是一個常量。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（2）一個指針變量卻可以被賦予不同的指針值，是一個變量。
除此之外還有指向結(jié)構(gòu)體變量的指針以及指向結(jié)構(gòu)體數(shù)組的指針。
數(shù)據(jù)結(jié)構(gòu)中涉及到：結(jié)構(gòu)體變量的指針
可以通過：（*指針變量）.成員名
也可以直接： 指針變量-->成員名
?
關(guān)于指針的內(nèi)容依然很多，這里就不詳細(xì)寫了，只是回顧一下而已。
?線性表的鏈?zhǔn)酱鎯?
#include<bits/stdc++.h>///單鏈表的實(shí)現(xiàn) using namespace std; template<typename T> struct Node {T date;Node<T> *next;///此處的T可以省略 }; template<typename T> class Linklist { public:Linklist(){first=new Node;first->NULL;}///無參構(gòu)造函數(shù)建立空鏈表Linklist(T a[],int n);///有~Linklist();//int Length;///通過一次遍歷可得 長度T Get(int i);///返回鏈表第i個元素int Find(T x);// int Locate(T x);///返回元素X在鏈表中的位置void Insert(int i,T x);///插入元素T Delete(int i);void PrintList(); private:Node<T> *first;///單鏈表的頭指針 }; /* /* 頭插法 *////每次插入到頭指針的后面 template<typename T> Linklist<T>::Linklist(T a[],int n) {first=new Node;first->next=NULL;/// Node<T>*s; ///定義一個結(jié)構(gòu)體指針for(int i=0;i<n;i++){s=new Node<T>;s->date=a[i];///申請一個新的節(jié)點(diǎn)s->next=first->next;first->next=s;} } */ /* 尾插法*////需要借助尾指針的輔助 template<typename T> Linklist<T>::Linklist(T a[],int n) {first=new Node;first->next=NULL;Node<T>*s;Node<T>*r;for(int i=0;i<n;i++){s=new Node<T>;s->date=a[i];r->next=s;r=s;}r->next=NULL; } /*單鏈表的遍歷*/ template<typename T> Linklist<T>::PrintList() {Node<T>*p;p=first->next;while(p){cout<<p->date<<endl;p=p->next;} } /*查找第i個位置的值*/ template<typename T> T Linklist<T>::Get(int i) {Node<T>*p;p=first->next;int count=1;while(p&&count<i){p=p->next;count++:}if(p) return p->date;else throw"位置"; } /*按值查找算法 */ template<typename T> int Linklist<T>::Find(T x) {Node<T>*p;p=first;int j=0;while(p){p=p->next;j++;if(p->data==x){return j;}}return 0; } /*刪除鏈表中第i個元素*/ template<typename T> T Linklist<T>::Delete(int i) {Node<T>*p;p=first;int j=0,x;while (p&&&j<i-1){p=p->next;j++;}if(p==NULL||p->next==NULL) throw"位置";else{Node<T>*q;q=p->next;x=p->date;p->next=p->next->next;delete q;return x;}}/*按位置插入*/ template<typename T> T Linklist<T>::Insert(int i,T x) {Node<T>*p;p=first;int j=0;while(p&&j<i-1){p=p->next;j++;}if(p) throw"位置";else{Node<T>*s;s->date=x;s->next=p->next;p->next=s;} }template<typename T> Linklist<T>::~Linklist() {Node<T>*p;while(first){p=first;first=first->next;delete p;} } int main() {} View Code?
轉(zhuǎn)載于:https://www.cnblogs.com/dean-SunPeishuai/p/10446608.html
總結(jié)
以上是生活随笔為你收集整理的数据结构第二章线性表学习笔记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Understanding HBase
- 下一篇： 理解这几张图，你就是js小牛了