C語言專區------初識鏈表（一）

一、鏈表是什么？

鏈表是一種物理存盤單元上非連續、非順序的存盤結構，資料元素的邏輯順序是通過鏈表中的指標鏈接次序實作的，鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成，每個結點包括兩個部分：一個是存盤資料元素的資料域，另一個是存盤下一個結點地址的指標域，

簡單地說，
鏈表是一種可以將多個資料依次連接起來的存盤結構，

head（h）是該鏈表的頭，"^"所指的為鏈表的尾，

二、鏈表

1.鏈表基礎（連接）

一個鏈表中每個結點應由兩塊組成，資料，指標，

形如：

typdef struct{
	char name[10];			//姓名
	int num;				//資料資訊
	struct date *next;		//指向下一個結點的指標
}student;

資料 即為我們想要存盤的資料，可以是一個，也可以是多個，可以是int型,也可以是結構體，等等，
指標 一般位于每個結點的末尾，用來指向下一個結點，起到連接的作用，

一般當我們申請到第一塊空間時，我們通常會定義一個指標*head 指向這個結點的起始部位,再定義一個指標 *next 指向下一結點的資料內容，這樣就將兩個結點連接在了一起，

以下是將兩個結點a，s連接的代碼：

	student *a=(student*)malloc(sizeof(student))； //申請第一塊空間
	student *head=a;	//創建頭指標，將其指向第一個結點的頭部
		
	int c;				
	scanf("%d",&c);		//讀入第一個資料
	a->num=c;			//存入第一個結點中
	
	studate *s=(student*)malloc(sizeof(student));	//創建新的結點 	
	scanf("%d",&c);		//讀入第二個節點中的資料
	s->num=c;			//將資料存入第二個節點中	 	
	a->next=s;			//將a中的指標*next 指向下一結點的資料
	head=s;				//將頭指標移動到指向第二個節點的資料
	b->next=NULL;		//由于以兩個節點為例，第二個結點的指標應指向NULL

2.添加結點

假設有兩個指標*p，*q ，*p 指向第一個結點的資料，*q 指向第一個結點的指標，此時若想添加節點，只需將第一個結點的指標指向新的結點的資料，第新的結點的指標指向第三個節點的資料就意味著已經連接成功，

但為了方便下一次添加，一般通過 p=p->next 將 *p 指向最后一個結點的資料， q=q->next；q=NULL將 *q 指向最后一結點的指標，

切記最后一個節點的指標需指向空值NULL，

	studate *p,*q;
	int x,y;
	scanf("%d",&y);
	
	p=head;						//p指向第一個結點head
	q=head->next;				//q指向第一個結點head的next
	while(q->num!=y&&q->next!=NULL){	//移動指標直到查詢到或結束
		q=q->next;
		p=p->next;
	}
			/*此時q已指向所要添加結點位置的下一個結點，
				 p已指向所要添加結點位置的上一個結點*/
	printf("have find");
	scanf("%d",&x);
	studate *s=(studate*)malloc(sizeof(studate));//新建結點
	s->num=x;					//將x存盤在新結點的資料域中
	s->next=q;					//新結點的指標指向下一結點（即q）
	p->next=s;					//上一結點的指標（即p）指向新結點

3.洗掉結點

假設有結點a、結點b、結點c

typdef struct{
	int num;				//資料資訊
	struct date *next;		//指向下一個結點的指標
}a,b,c;	//結點a，b，c

想要洗掉結點b，應將結點a的指標指向c的資料即可

	a->next=c;
	c->next=NULL;

4.查詢結點

通過移動指標p、q來確定指定結點位置

	student *p,*q;
	int y;
	scanf("%d",&y);
	
	p=head;					//p指向第一個結點 head
	q=head->next;			//q指向第一個結點的 next
	while(q->num!=y&&q->next!=NULL){	//移動指標直到查詢到或結束
		q=q->next;
		p=p->next;
	}

三.綜合應用

功能：輸入自由多個資料，直到輸入-1停止，并可以進行指定位置的添加，洗掉結點，

話不多說，上原始碼！

#include <stdio.h>
#include <stdlib.h>

			/*結構體*/
typedef struct date{
	int num;
	struct date *next;
}studate;    

			/*函式*/ 
void creat_(studate *b);					//創建鏈表 
void putout_(studate *b,studate *head);		//遍歷鏈表 
void add_(studate *head);					//添加結點 
void del_(studate *head);					//洗掉結點 

int main(void)
{	
	
	studate *head=(studate*)malloc(sizeof(studate)),*b=head;	//創建頭指標
	 
	creat_(b);
	putout_(b,head);
	
	add_(head);
	putout_(b,head);
	
	del_(head);
	putout_(b,head);
	
	free(head);
	return 0;
}
/**********************************************************   
   		
							創建鏈表			
			
**********************************************************/
void creat_(studate *b){
	
	int c;
	printf("輸入資料");
	scanf("%d",&c);
	b->num=c;
	
	do{
		printf("輸入資料");
		scanf("%d",&c);
		studate *s=(studate*)malloc(sizeof(studate));	//創建新的結點 
		s->num=c;				 
		b->next=s;
		b=s;
	}while(c!=-1);	
	b->next=NULL;
}
/**********************************************************   
   		
							添加結點			
			
**********************************************************/	
void add_(studate *head){
	
	studate *p,*q;
	int x,y;
	printf("請輸入插入資料的兩個位置（資料）");
	scanf("%d %d",&x,&y);
	
	p=head;
	q=head->next;
	while(q->num!=y&&q->next!=NULL){
		q=q->next;
		p=p->next;
	}
	
	printf("have find");
	scanf("%d",&x);
	studate *s=(studate*)malloc(sizeof(studate));
	s->num=x;
	s->next=q;
	p->next=s;
} 
/**********************************************************   
   		
							遍歷鏈表			
			
**********************************************************/
void putout_(studate *b,studate *head){
	
	b=head;
	printf("head->");
	while(b->next){
		printf("%d->",b->num);
		b=b->next;
	}
	printf("NULL\n");
}
/**********************************************************   
   		
							洗掉結點			
			
**********************************************************/
void del_(studate *head){
	
	studate *p,*q;
	int x;
	printf("請輸入洗掉的資料");
	scanf("%d",&x);
	
	p=head;
	q=head->next;
	while(q->num!=x&&q->next!=NULL){
		q=q->next;
		p=p->next;
	}
	if(q->num!=x&&q->next==NULL)
		printf("sorry");
	else {
		q=q->next;
		(p->next)=q;
		printf("ok, have delete");
	}
}

！！！最后一定要free掉空間哦，這是個好習慣！！！

四.總結

本文僅簡單介紹了鏈表的使用

其實鏈表有很多優點，也有缺點：
1、空間上，順序比鏈式節約空間，是因為鏈式結構每一個節點都有一個指標存盤域；
2、存盤操作上，順序支持隨機存取，方便操作；
3、插入和洗掉上，鏈式的要比順序的方便

鏈表較順序表來說稍微復雜點，但只要多加練習就一定可以流暢使用，

下一篇我將重點介紹人員管理系統的鏈表方法以及順序表方法的制作， 以對比二者的優缺點，

以上就是今天分享的內容，謝謝，