線性表之單連結清單學習小結（初學資料結構必看）

花了好幾個小時，詳細規劃出了整個過程，包括所有基本操作。。。有什麼疑問請下方留言

#include<iostream>
using namespace std;

#define ElemType char
#define ERROR 0
#define OK 1
typedef struct Node
{
	ElemType data;
	struct Node *next;
}Node,*LinkList;

void init_linklist(LinkList L)/*對單連結清單進行初始化*/
{
	L=(Node*)malloc(sizeof(Node)); /*申請結點空間*/
	L->next=NULL;                      /*置為空表*/
}

void CreateFromHead(LinkList   L)
{ 
	Node *s;
	char 	c;
	int 	flag=1,k=0;
	while(flag)   /* flag初值為1，當輸入"$"時，置flag為0，建表結束*/
	{
		c=getchar();   
		if(c!='$')
		{
			s=(LinkList)malloc(sizeof(Node)); /*建立新結點s*/
			s->data=c;
			s->next=L->next;/*将s結點插入表頭*/
			L->next=s;
			if(k==0)
			{k=1;s->next=NULL;}          //具體為啥不知道，但資料結構課程源程式的确是的結尾指向不為空，通過k标記，使得結尾為空
		}
		else
			flag=0;
	}
}

void CreateFromTail(LinkList L)
{ 
	Node *r, *s;
	char c;
	int   flag =1; /*設定一個标志，初值為1，當輸入"$"時，flag為0，建表結束*/
	r=L;                /*r指針動态指向連結清單的目前表尾，以便于做尾插入，其初值指向頭結點*/
	while(flag)         /*循環輸入表中元素值，将建立新結點s插入表尾*/
	{
		c=getchar();
		if(c!='$')
		{
			s=(Node*)malloc(sizeof(Node));
			s->data=c;
			r->next=s;
			r=s;
		}
		else
		{
			flag=0;
			r->next=NULL;   /*将最後一個結點的next鍊域置為空，表示連結清單的結束*/
		}
	}   
} 
ElemType Get (LinkList  L, int i)
/*在帶頭結點的單連結清單L中查找第i個結點，若找到(1≤i≤n)，則傳回該結點的存儲數值; */
{  
	int j;
	Node  *p;
	p=L;
	j=0;   /*從頭結點開始掃描*/ 
	while ((p->next!=NULL)&&(j<i))
	{ 
		p=p->next;    /* 掃描下一結點*/
		j++;   /* 已掃描結點計數器 */
	}
	if(i == j)
		return p->data;   /* 找到了第i個結點 */
	else 
		return NULL;   /* 找不到，i≤0或i>n */
} 
int Locate( LinkList L,ElemType key)
/*在帶頭結點的單連結清單L中查找其結點值等于key的結點，若找到則傳回該結點的位置p，否則傳回NULL*/ 
{ 
	Node *p;
	int k=1;
	p=L->next;    /*從表中第一個結點開始 */
	while (p!=NULL)
	{
		if (p->data!=key)
			p=p->next; 
		else  
			break; /*找到結點值=key時退出循環 */
		k++;
	}
	return k;
} 

int	ListLength(LinkList L)
/*求帶頭結點的單連結清單L的長度*/
{   
	Node *p;
	int j;
	p=L->next;
	j=0;   /*用來存放單連結清單的長度*/
	while(p!=NULL)
	{	  
		p=p->next;
		j++;
	}
	return j;	/*j為求得的單連結清單長度*/
}  

int InsList(LinkList L,int i,ElemType e)
/*在帶頭結點的單連結清單L中第i個位置插入值為e的新結點*/
{  
	Node *pre,*s;
	int k;
	if(i<=0)return ERROR;
	pre=L;  
	k=0;                     /*從"頭"開始，查找第i-1個結點*/
	while(pre!=NULL&&k<i-1)  /*表未查完且未查到第i-1個時重複，找到pre指向第i-1個*/ 
	{ 
		pre=pre->next;
		k=k+1; 
	}									/*查找第i-1結點*/
	if(!pre)      /*如目前位置pre為空表已找完還未數到第i個，說明插入位置不合理*/ 
	{ 
		printf("插入位置不合理!");
		return ERROR;
	}
	s=(Node*)malloc(sizeof(Node));   /*申請一個新的結點S */
	s->data=e;                       /*值e置入s的資料域*/
	s->next=pre->next;				/*修改指針，完成插入操作*/
	pre->next=s;
	return OK;
}
int DelList(LinkList L,int i,ElemType *e)
/*在帶頭結點的單連結清單L中删除第i個元素，并将删除的元素儲存到變量*e中*/
{  
	Node *pre,*r;
	int k;
	pre=L;
	k=0;
	while(pre->next!=NULL && k<i-1)	/*尋找被删除結點i的前驅結點i-1使p指向它*/
	{ 
		pre=pre->next; 
		k=k+1;
	}								/*查找第i-1個結點*/
	if(!(pre->next))     /* 即while循環是因為p->next=NULL或i<1而跳出的,而是因為沒有找到合法的前驅位置，說明删除位置i不合法。*/
	{
		printf("删除結點的位置i不合理!");
		return ERROR;
	}
	r=pre->next;
	pre->next=pre->next->next;    /*修改指針，删除結點r*/
	*e = r->data;
	free(r);    /*釋放被删除的結點所占的記憶體空間*/
	printf("成功删除結點!");
	return OK;
}
LinkList MergeLinkList(LinkList LA, LinkList LB)
/*将遞增有序的單連結清單LA和LB合并成一個遞增有序的單連結清單LC*/
{  
	Node *pa,*pb;
	Node *r;
	LinkList LC;
	/*将LC初始置空表。pa和pb分别指向兩個單連結清單LA和LB中的第一個結點,r初值為LC*/
	pa=LA->next;
	pb=LB->next;
	LC=LA;
	LC->next=NULL;
	r=LC;
	/*當兩個表中均未處理完時，比較選擇将較小值結點插入到新表LC中。*/
	
	while(pa!=NULL && pb!=NULL)
	{
		if(pa->data <= pb->data)
		{
			r->next=pa;
			r=pa;
			pa=pa->next;
		}
		else
		{
			r->next=pb;
			r=pb;
			pb=pb->next;
		}
	}
	if(pa) /*若表LA未完，将表LA中後續元素鍊到新表LC表尾*/
		r->next=pa;
	else	 /*否則将表LB中後續元素鍊到新表LC表尾*/
		r->next=pb;
	//	free(LB);         原文是這麼寫的，不過釋放失敗，原因請看我的部落格"淺析C語言malloc與free"
	
	return(LC);
}
void print(LinkList L)
{
	LinkList p=L->next;
	int i=0;
	while(p!=NULL)
	{
		cout<<p->data<<"  ";
		p=p->next;
	}
	cout<<endl;
}
int main()
{
	Node LA,LB;
	LinkList LC;
	int n;
	ElemType key;
	init_linklist(&LA);
	init_linklist(&LB);
	
	cout<<"以尾插法建立連結清單LB：(輸入$結束)"<<endl;
	CreateFromTail(&LA);
	print(&LA);
	
	cout<<"以頭插法建立連結清單LB：(輸入$結束)"<<endl;
	CreateFromHead(&LB);
	print(&LB);
	
	cout<<"在LA中按序号查找某元素輸出值"<<endl;
	cin>>n;
	cout<<Get (&LA,n)<<endl;
	
	cout<<"在LA中按值查找某元素輸出序号"<<endl;
	cin>>key;
	cout<<Locate(&LA,key)<<endl;
	
	cout<<"求LA表的節點長度："<<endl;
	cout<<ListLength(&LA)<<endl;
	
	cout<<"在LA表中插入數e(輸入位置和e,注意此時的ElemType是char類型，最大支援讀入9)"<<endl;
	cin>>n;
	cin>>key;
	if(InsList(&LA,n,key))
	{
		cout<<"插入成功！"<<endl;
		print(&LA);
	}
	else
		cout<<"插入失敗！"<<endl;
	
	cout<<"在LA表中删除第i個元素(輸入位置i)"<<endl;
	cin>>n;
	if(DelList(&LA,n,&key))
		cout<<"删除的元素為:"<<key<<endl;
	else
		cout<<"删除失敗！"<<endl;
	
	cout<<"合并LA，LB後的連結清單為："<<endl;
	LC=MergeLinkList(&LA,&LB);
	print(LC);
	return 0;
}

附帶：循環連結清單的合并算法

LinkList   merge_1(LinkList LA,LinkList LB)
{  /*此算法将兩個采用頭指針的循環單連結清單的首尾連接配接起來*/
	Node *p, *q;
	p=LA;
	q=LB;
	while (p->next!=LA)	p=p->next;	/*找到表LA的表尾，用p指向它*/
	while (q->next!=LB)	q=q->next;	/*找到表LB的表尾，用q指向它*/
	q->next=LA;	/*修改表LB 的尾指針，使之指向表LA 的頭結點*/
	p->next=LB->next; /*修改表LA的尾指針，使之指向表LB 中的第一個結點*/
	free(LB);
	return(LA);
}
LinkList  merge_2(LinkList RA,LinkList RB)
{  /*此算法将兩個采用尾指針的循環連結清單首尾連接配接起來*/
	Node *p;
	p=RA->next; /*儲存連結清單RA的頭結點位址*/
	RA->next=RB->next->next;/*連結清單RB的開始結點鍊到連結清單RA的終端結點之後*/
	free(RB->next);/*釋放連結清單RB的頭結點*/
	RB->next=p;/*連結清單RA的頭結點鍊到連結清單RB的終端結點之後*/
    return  RB;/*傳回新循環連結清單的尾指針*/
}

雙向連結清單的插入與删除

int DlinkIns(DoubleList L,int i,ElemType e)
{
	DNode  *s,*p;
	int k;
	p=L;  
	k=0;                     /*從"頭"開始，查找第i-1個結點*/
	while(p->next!=L&&k<i)  /*表未查完且未查到第i-1個時重複，找到p指向第i個*/ 
	{ 
		p=p->next;
		k=k+1; 
	}									/*查找第i-1結點*/
	if(p->next == L)      /*如目前位置p為空表已找完還未數到第i個，說明插入位置不合理*/ 
	{ 
		printf("插入位置不合理!");
		return ERROR;
	}
	s=(DNode*)malloc(sizeof(DNode));
 	if (s)
	{
		s->data=e;
		s->prior=p->prior;		
		p->prior->next=s;	
		s->next=p;			
		p->prior=s;			
		return OK;
	}
	else 
		return ERROR;
}
int	DlinkDel(DoubleList L,int i,ElemType *e)
{
	DNode  *p;
	int k;
	p=L;  
	k=0;                     /*從"頭"開始，查找第i個結點*/
	while(p->next!=L && k<i)  /*表未查完且未查到第i個時重複，找到p指向第i個*/ 
	{ 
		p=p->next;
		k=k+1; 
	}								
	if(p->next == L)       
	{ 
		return ERROR;
	}
	else
	{
		*e=p->data;
		p->prior->next=p->next;
		p->next->prior=p->prior;
		free(p);
		return OK;
	}
}

靜态連結清單的初始化，節點配置設定&回收

void initial(StaticList space, int *av)
{
    int k;
	space[0].cursor=0;      /*設定已用靜态單連結清單的頭指針指向位置0*/
	for(k=0;k<Maxsize-1;k++)
		space[k].cursor=k+1;    /*連鍊*/
	space[Maxsize-1].cursor=0;    /*标記鍊尾*/
	*av=1;  /*設定備用連結清單頭指針初值*/
}
int getnode(StaticList space, int *av)
/*從備用連結清單摘下一個結點空間，配置設定給待插入靜态連結清單中的元素*/
{
	int i;
	i=*av;
	*av=space[*av].cursor;
	return i;
}
void   freenode(StaticList space, int *av, int k)
/*将下标為 k的空閑結點插入到備用連結清單*/
{
	space[k].cursor=*av;
	*av=k;
}

線性表之單連結清單學習小結（初學資料結構必看）

繼續閱讀

goalng nil interface淺析持續學習

模組化：數學模組化

開源軟體：NoSql資料庫 - 圖資料庫 Neo4j轉載自原文位址：http://www.cnblogs.com/loveis715/p/5277051.html

資料在網絡7層中的傳輸過程

當今世界十大經典算法

字元串功能實作

【算法提高班】貪婪政策

《貪婪的動态規劃》

分治法實作求解最大子數組

UVA 10154:Weights and Measures Weights and Measures

Linux Kernel Development　學習

動态規劃、最小費用流例題 — nyoj_712 探尋寶藏

計算機開路人阿蘭·圖靈

基礎算法之二分查找

poj3249

PAT 1089 Insert or Merge[難]