前言：我愛(ài)編程，編程使我快樂(lè)！！

我們知道，數(shù)組式計(jì)算機(jī)根據(jù)事先定義好的數(shù)組類型與長(zhǎng)度自動(dòng)為其分配一連續(xù)的存儲(chǔ)單元，相同數(shù)組的位置和距離都是固定的，也就是說(shuō)，任何一個(gè)數(shù)組元素的地址都可一個(gè)簡(jiǎn)單的公式計(jì)算出來(lái)，因此這種結(jié)構(gòu)可以有效的對(duì)數(shù)組元素進(jìn)行隨機(jī)訪問(wèn)。但若對(duì)數(shù)組元素進(jìn)行插入和刪除操作，則會(huì)引起大量數(shù)據(jù)的移動(dòng)，從而使簡(jiǎn)單的數(shù)據(jù)處理變得非常復(fù)雜，低效。 為了能有效地解決這些問(wèn)題，一種稱為“鏈表”的數(shù)據(jù)結(jié)構(gòu)得到了廣泛應(yīng)用。1． 鏈表概述鏈表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，他的特點(diǎn)是用一組任意的存儲(chǔ)單元（可以是連續(xù)的，也可以是不連續(xù)的）存放數(shù)據(jù)元素。鏈表中每一個(gè)元素成為“結(jié)點(diǎn)”，每一個(gè)結(jié)點(diǎn)都是由數(shù)據(jù)域和指針域組成的，每個(gè)結(jié)點(diǎn)中的指針域指向下一個(gè)結(jié)點(diǎn)。Head是“頭指針”，表示鏈表的開(kāi)始，用來(lái)指向第一個(gè)結(jié)點(diǎn)，而最后一個(gè)指針的指針域?yàn)镹ULL(空地址)，表示鏈表的結(jié)束。可以看出鏈表結(jié)構(gòu)必須利用指針才能實(shí)現(xiàn)，即一個(gè)結(jié)點(diǎn)中必須包含一個(gè)指針變量，用來(lái)存放下一個(gè)結(jié)點(diǎn)的地址。實(shí)際上，鏈表中的每個(gè)結(jié)點(diǎn)可以用若干個(gè)數(shù)據(jù)和若干個(gè)指針。結(jié)點(diǎn)中只有一個(gè)指針的鏈表稱為單鏈表，這是最簡(jiǎn)單的鏈表結(jié)構(gòu)。再c++中實(shí)現(xiàn)一個(gè)單鏈表結(jié)構(gòu)比較簡(jiǎn)單。例如，可定義單鏈表結(jié)構(gòu)的最簡(jiǎn)單形式如下   

struct Node{ int Data; Node*next;};這里用到了結(jié)構(gòu)體類型。其中，*next是指針域，用來(lái)指向該結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)；Data是一個(gè)整形變量，用來(lái)存放結(jié)點(diǎn)中的數(shù)據(jù)。當(dāng)然，Data可以是任何數(shù)據(jù)類型，包括結(jié)構(gòu)體類型或類類型。在此基礎(chǔ)上，我們?cè)诙x一個(gè)鏈表類list，其中包含鏈表結(jié)點(diǎn)的插入，刪除，輸出等功能的成員函數(shù)。
class list{ Node*head;public: list(){head=NULL;} void insertlist(int aDate,int bDate);//鏈表結(jié)點(diǎn)的插入 void Deletelist(int aDate);//鏈表結(jié)點(diǎn)的刪除 void Outputlist();//鏈表結(jié)點(diǎn)的輸出 Node*Gethead(){return head;}};2． 鏈表結(jié)點(diǎn)的訪問(wèn)由于鏈表中的各個(gè)結(jié)點(diǎn)是由指針鏈接在一起的，其存儲(chǔ)單元文筆是連續(xù)的，因此，對(duì)其中任意結(jié)點(diǎn)的地址無(wú)法向數(shù)組一樣，用一個(gè)簡(jiǎn)單的公式計(jì)算出來(lái)，進(jìn)行隨機(jī)訪問(wèn)。只能從鏈表的頭指針（即head）開(kāi)始，用一個(gè)指針p先指向第一個(gè)結(jié)點(diǎn)，然后根據(jù)結(jié)點(diǎn)p找到下一個(gè)結(jié)點(diǎn)。以此類推，直至找到所要訪問(wèn)的結(jié)點(diǎn)或到最后一個(gè)結(jié)點(diǎn)（指針為空）為止。下面我們給出上述鏈表的輸出函數(shù)；
void list::outputlist(){ Node*current=head; while(current!=NULL) {  cout<Data<<" ";  current=current->next; } cout<<endl; }3． 鏈表結(jié)點(diǎn)的插入如果要在鏈表中的結(jié)點(diǎn)a之前插入結(jié)點(diǎn)b，則需要考慮下面幾點(diǎn)情況。（1） 插入前鏈表是一個(gè)空表，這時(shí)插入新結(jié)點(diǎn)b后。（2） 若a是鏈表的第一個(gè)結(jié)點(diǎn)，則插入后，結(jié)點(diǎn)b為第一個(gè)結(jié)點(diǎn)。（3） 若鏈表中存在a,且不是第一個(gè)結(jié)點(diǎn)，則首先要找出a的上一個(gè)結(jié)點(diǎn)a_k，然后使a_k的指針域指向b，在令b的指針域指向a，即可完成插入。（4） 如鏈表中不存在a，則插在最后。先找到鏈表的最后一個(gè)結(jié)點(diǎn)a_n，然后使a_n的指針域指向結(jié)點(diǎn)b，而b指針的指針為空。以下是鏈表類的結(jié)點(diǎn)插入函數(shù)，顯然其也具有建立鏈表的功能。
void list::insertlist(int aDate,int bDate)  //設(shè)aDate是結(jié)點(diǎn)a中的數(shù)據(jù)，bDate是結(jié)點(diǎn)b中的數(shù)據(jù){	Node*p,*q,*s;        //p指向結(jié)點(diǎn)a，q指向結(jié)點(diǎn)a_k，s指向結(jié)點(diǎn)b	s=(Node*)new(Node);  //動(dòng)態(tài)分配一個(gè)新結(jié)點(diǎn)	s->Data=bDate;   //設(shè)b為此結(jié)點(diǎn)	p=head;	if(head==NULL)  //若是空表，使b作為第一個(gè)結(jié)點(diǎn)	{		head=s;		s->next=NULL;	}	else		if(p->Data==aDate)   //若a是第一個(gè)結(jié)點(diǎn)		{			s->next=p;			head=s;		}		else		{			while(p->Data!=aDate&&p->next!=NULL)//查找結(jié)點(diǎn)a			{				q=p;				p=p->next;			}			if(p->Data==aDate)     ///若有結(jié)點(diǎn)a			{				q->next=s;				s->next=p;			}			else                    //若沒(méi)有結(jié)點(diǎn)a；			{				p->next=s;				s->next=NULL;			}		}}4． 鏈表結(jié)點(diǎn)的刪除如果要在鏈表中刪除結(jié)點(diǎn)a并釋放被刪除的結(jié)點(diǎn)所占的存儲(chǔ)空間，則需要考慮下列幾種情況。（1） 若要?jiǎng)h除的結(jié)點(diǎn)a是第一個(gè)結(jié)點(diǎn)，則把head指向a的下一個(gè)結(jié)點(diǎn)。（2） 若要?jiǎng)h除的結(jié)點(diǎn)a存在于鏈表中，但不是第一個(gè)結(jié)點(diǎn)，則應(yīng)使a得上一個(gè)結(jié)點(diǎn)a_k-1的指針域指向a的下一個(gè)結(jié)點(diǎn)a_k+1。（3） 空表或要?jiǎng)h除的結(jié)點(diǎn)a不存在，則不做任何改變。 以下是鏈表類的結(jié)點(diǎn)刪除函數(shù)。
void list::deletelist(int aDate)  //設(shè)aDate是要?jiǎng)h除的結(jié)點(diǎn)a中的數(shù)據(jù)成員{	Node*p,*q;            //p用于指向結(jié)點(diǎn)a,q用于指向結(jié)a的前一個(gè)結(jié)點(diǎn)	p=head;	if(p==NULL)  //若是空表		return;	if(p->Data==aDate)  //若a是第一個(gè)結(jié)點(diǎn)	{		head=p->next;		delete p;	}	else	{		while(p->Data!=aDate&&p->next!=NULL)  //查找結(jié)點(diǎn)a		{			q=p;			p=p->next;		}		if(p->Data==aDate)    //若有結(jié)點(diǎn)a		{			q->next=p->next;			delete p;		}	}}例題；利用以上三個(gè)鏈表操作成員函數(shù)insertlist,deletelist.outputlist,可形成以下的簡(jiǎn)單鏈表操作程序。#include"iostream.h"struct Node{	int Data;	Node*next;};class list{	Node*head;public:	list(){head=NULL;}	void insertlist(int aData,int bData);	void deletelist(int aData);	void outputlist();	Node*gethead(){return head;}};void list::insertlist(int aData,int bData)  //設(shè)aData是結(jié)點(diǎn)a中的數(shù)據(jù)，bData是結(jié)點(diǎn)b中的數(shù)據(jù){	Node*p,*q,*s;        //p指向結(jié)點(diǎn)a，q指向結(jié)點(diǎn)a_k，s指向結(jié)點(diǎn)b	s=(Node*)new(Node);  //動(dòng)態(tài)分配一個(gè)新結(jié)點(diǎn)	s->Data=bData;   //設(shè)b為此結(jié)點(diǎn)	p=head;	if(head==NULL)  //若是空表，使b作為第一個(gè)結(jié)點(diǎn)	{		head=s;		s->next=NULL;	}	else		if(p->Data==aData)   //若a是第一個(gè)結(jié)點(diǎn)		{			s->next=p;			head=s;		}		else		{			while(p->Data!=aData && p->next!=NULL)//查找結(jié)點(diǎn)a			{				q=p;				p=p->next;			}			if(p->Data==aData)     ///若有結(jié)點(diǎn)a			{				q->next=s;				s->next=p;			}			else                    //若沒(méi)有結(jié)點(diǎn)a；			{				p->next=s;				s->next=NULL;			}		}}void list::deletelist(int aData)  //設(shè)aData是要?jiǎng)h除的結(jié)點(diǎn)a中的數(shù)據(jù)成員{	Node*p,*q;            //p用于指向結(jié)點(diǎn)a,q用于指向結(jié)a的前一個(gè)結(jié)點(diǎn)	p=head;	if(p==NULL)  //若是空表		return;	if(p->Data==aData)  //若a是第一個(gè)結(jié)點(diǎn)	{		head=p->next;		delete p;	}	else	{		while(p->Data!=aData&&p->next!=NULL)  //查找結(jié)點(diǎn)a		{			q=p;			p=p->next;		}		if(p->Data==aData)    //若有結(jié)點(diǎn)a		{			q->next=p->next;			delete p;		}	}}void list::outputlist(){	Node*current=head;	while(current!=NULL)	{		cout<Data<<" ";		current=current->next;	}	cout<<endl;}void main(){	list A,B;	int Data[10]={25,41,16,98,5,67,9,55,1,121};	A.insertlist(0,Data[0]); //建立鏈表A首結(jié)點(diǎn)	for(int i=1;i<10;i++)		A.insertlist(0,Data[i]); //順序向后插入	cout<<"/n鏈表A:";	A.outputlist();	A.deletelist(Data[7]);	cout<<"刪除元素Data[7]后";	A.outputlist();	B.insertlist(0,Data[0]); //建立鏈表B首結(jié)點(diǎn)	for(i=0;i<10;i++)		B.insertlist(B.gethead()->Data,Data[i]); //在首結(jié)點(diǎn)處順序向后插入	cout<<"/n鏈表B:";	B.outputlist();	B.deletelist(67);	cout<<"刪除元素67后";	B.outputlist(); }
程序運(yùn)行結(jié)果為鏈表A；25，41，16，98，5，67，9，55，1，121刪除元素Data[7]后；25，41，16，98，5，67，9，1，121鏈表B；121，1，55，9，67，5，98，16，41，25，刪除元素67后；121，1，55，9，5，98，16，41，25，
     下面是楊輝三角的代碼：
int main(){	const int n=11;	int i,j,a[n][n];	for(i=1;i<n;i++)	{		a[i][i]=1;		a[i][1]=1;	}	for(i=3;i<n;i++)	{		for(j=2;j<=i-1;j++)  			a[i][j]=a[i-1][j-1]+a[i-1][j];  	}	for(i=1;i<n;i++)	{		for(j=1;j<=i;j++)			cout<<setw(5)<<a[i][j]<<" ";		cout<<endl;	}	cout<<endl;	return 0;}