線性表的鏈式存儲之單鏈表的尾插法

對單鏈表進行遍歷、查找、插入、刪除等操作，最終效果如下：

相關C代碼如下：

/*線性表的鏈式存儲之單鏈表的尾插法*/

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

/*定義變量*/
typedef?int?DataType;

typedef?struct?node{?????//定義鏈表結點數(shù)據(jù)結構
	DataType?data;
	struct?node?*?pNext;
}NODE;

typedef?NODE?*?pNODE;???//定義鏈表結點類型指針

/*函數(shù)聲明*/
pNODE?createLinkList(void);???//尾插法建立單鏈表
void?TraverseLinkList(pNODE?pHead);?//遍歷單鏈表各個結點
pNODE?LocateNode(pNODE?pHead,int?k);?//查找鏈表中是否存在某個結點
void?InsertLinkList(pNODE?pHead,int?i,DataType?x);??//向鏈表中插入結點
DataType?DeleteLinkList(pNODE?pHead,int?i);

/*程序正文*/

int?main(void){????????????//主函數(shù)
	pNODE?pHead=NULL;??????//

	pHead?=?createLinkList();??//創(chuàng)建鏈表，并將頭結點地址返回
	TraverseLinkList(pHead);??//將頭結點地址傳入遍歷函數(shù)，遍歷鏈表各個結點
	pNODE?lNode?=?LocateNode(pHead,7);?//在鏈表中查找指定的值
	if(lNode?==?NULL){
		printf("鏈表中不存在你要查找的值\n");
	}else{
		printf("鏈表中存在你要查找的值\n");
	}
	printf("向鏈表中第三個位置插入100\n");
	InsertLinkList(pHead,3,100);
	TraverseLinkList(pHead);?
	printf("刪除鏈表中第四個結點，刪除的結點值是%d\n",DeleteLinkList(pHead,4));
	TraverseLinkList(pHead);?

	return?0;
}

pNODE?createLinkList(void){

	pNODE?pHead,pTail;????//定義頭結點指針和尾結點指針
	int?length,i,val;
	pHead=(pNODE)malloc(sizeof(NODE));??//給頭結點在內存中申請地址空間
	pTail=pHead;???//初始狀態(tài)頭指針和尾指針相同
	
	if(pHead?==?NULL){??????//如果頭結點申請失敗就退出程序
		printf("內存分配頭結點失敗.");
		exit(-1);
	}
	printf("請輸入鏈表的結點個數(shù):");
	scanf("%d",&length);
	for(i=0;i<length;i++){???//手動依次輸入新建鏈表需要的結點值
		printf("請輸入結點%d的值:",i+1);?
		scanf("%d",&val);
		pNODE?pNew=(pNODE)malloc(sizeof(NODE));??//給新結點在內存中申請地址空間
		if(pNew?==?NULL){???//如果新結點地址分配地址空間失敗，就退出程序
			printf("坑爹啊,沒有足夠的內存分配了");
			exit(-1);
		}
		pNew->data=val;???//給新結點賦值
		pTail->pNext=pNew;??//新結點連接到尾結點之后
		pTail=pNew;??//尾指針指向新結點
	}
	pTail->pNext=NULL;	//終端結點指針域置為空,單鏈表生成
	return?pHead;	//返回鏈表頭結點
}

void?TraverseLinkList(pNODE?pHead){
	printf("當前鏈表各個結點的值是:");
	pNODE?pNew?=?pHead->pNext;??//獲取首結點，然后從首結點開始進行遍歷
	while(pNew?!=?NULL){??????//判斷下一個結點是否為空，如果不為空，那么就輸出結點數(shù)據(jù)域里的值
		printf("%d?",pNew->data);
		pNew?=?pNew->pNext;
	}
	printf("\n");
}

pNODE?LocateNode(pNODE?pHead,int?k){??//查看鏈表中是否存在某個值的結點
	pNODE?pNew?=?pHead->pNext;
	while(pNew?&&?pNew->data!=k){
		pNew=pNew->pNext;		
	}
	return?pNew;
}

void?InsertLinkList(pNODE?pHead,int?i,DataType?x){???//向鏈表第i個位置插入結點x
	pNODE?p,s;int?j;
	p=pHead;j=0;
	while(p?!=?NULL?&&?j<i-1){
		p?=?p->pNext;???//是p指向第i-1個結點，即是指向要插入位置的前一個結點
		j++;
	}
	if(p?==?NULL){???????
		printf("插入位置錯誤");
		exit(-1);
	}
	s?=?(pNODE)malloc(sizeof(NODE));??//給新結點申請內存空間
	s->data=x;						//給新結點數(shù)據(jù)域賦值
	s->pNext=p->pNext;??????????????//將新結點指向p指針所指向的結點的下一個結點
	p->pNext=s;?????????????????????//將s結點的地址賦值給p結點所指向結點的指針域，即讓i-1位置的結點指向s結點
}


DataType?DeleteLinkList(pNODE?pHead,int?i){
	pNODE?p,s;int?j;
	DataType?x;
	p=pHead;j=0;
	while(p?!=?NULL?&&?j<i-1){
		p=p->pNext;????//是p指向第i-1個結點，即是指向要插入位置的前一個結點
		j++;
	}

	if(p?==NULL){
		printf("刪除位置錯誤");
		exit(-1);
	}
	s?=?p->pNext;???????????//s結點就是要被刪除的結點
	p->pNext=p->pNext->pNext;??//s前一個結點跳過s結點直接指向s的下一個結點，此時s結點成了幽靈了
	x?=?s->data;??//將s結點的值保存下來
	free(s);??//在內存空間中將s釋放掉
	return?x;???
}