数据结构之链表

数据结构C语言实现单链表；及相关知识点；亲自手码实际跑可用。

#include 
#include 
#include 
#define bool int
#define true 1
#define false 0
//链表相关知识点： 
//离散存储（链表）；定义，存储个体（节点）物理地址很有可能不连续，个体（节点）间采用指针相连，每个个体（节点）最多指向只有一个前驱或后继个体（节点）；分类，；算法，；优缺点，； 
//术语：首节点、尾节点、头结点（空节点，无有效数据，无链表有效个数），头指针，尾指针
//头结点：头结点的数据类型与首结点数据类型一样；链表第一个有效节点的那个节点；为了更好的操作链表，简化链表算法。
//首节点：链表第一个有效节点
//尾节点：链表最后一个有效节点
//头指针：指向头节点的指针变量
//尾指针：指向尾节点的指针变量
 
//链表分类：单链表，双链表(每个节点有两个指针变量），循环链表（尾节点指针指向首节点），非循环链表 
//算法：遍历，查找，清空，销毁，求长度，排序，删除节点，插入节点
 

//为已有数据类型定义别名,注意一定要有";"结尾。 推荐使用大写，便于识别为别名 
typedef int * pint; 
typedef int sa; 

//定义的struct类型定义别名  节点的成员：有效数据和指向域 (节点间关系纽带） 
typedef struct Node{
	//数据域，可复杂 
	int data; 
	//指针域，指向本类型的数据 
	struct Node * pnext; 
}NODE,* PNODE;  //多个别名，前一个标识结构体指针类型，后一个标识结构体数据类型本身。 备注：* 号的位置没有限制，只要在同一“，”内就可。 
// }*PNODE, NODE;   别名效果一样 
//遍历，查找，清空，销毁，求长度，排序，删除节点，插入节点

//函数声明 
PNODE Created_list();
void Traverse_list(PNODE pHead);
bool Is_empty(PNODE pHead);
int Length_list(PNODE pHead);
bool Insert_list(PNODE pHead,int pos,int val);//插入和删除首地址从1开始计算 
bool Delete_list(PNODE pHead,int pos,int * p_dval);
void Sort_list(PNODE PHead);
int main(int argc, char *argv[]) {
	
	PNODE pHead = NULL; //等价于struct Node * pHead = NULL; 
	pHead = Created_list(); //创建一个非循环单链表，并将该链表的头指针赋值给pHead;
	Traverse_list(pHead);	 
	if(Is_empty(pHead)){
		printf("链表为空n");
	}
	printf("链表长度：%dn",Length_list(pHead));
	Sort_list(pHead);
	Traverse_list(pHead);
	//Insert_list(pHead,6,0);
	int val;
	int * p_dval = &val;
	Delete_list(pHead,3,p_dval);
	Traverse_list(pHead); 
	return 0;
}

//辅助函数 

PNODE Created_list(){
	int len;//链表长度 
	int i; 
	int val; //链表每次的值 
	PNODE pHead = (PNODE)malloc(sizeof(NODE));
	if(pHead == NULL){
		printf("内存动态分配失败n");
		exit(-1);
	} 
	pHead->pnext = NULL; 
	PNODE pCurrt = pHead;
	printf("请输入你需要生成的链表节点的个数：len=");
	scanf("%d",&len);
	for(i = 0;i < len; i++){
		
		
		printf("输入第%d各节点值：val=",i);//从零开始
		scanf("%d",&val);
		//每次循环生成一个新的节点
		PNODE pNew = (PNODE)malloc(sizeof(NODE));
	    if(pNew == NULL){
		printf("内存动态分配失败n");
		exit(-1);
		} 
		pNew->data = val;
		pNew->pnext = NULL;
		pCurrt->pnext = pNew;
		pCurrt = pCurrt->pnext;
	} 
	return  pHead;
}
void Traverse_list(PNODE pHead){
	PNODE p = pHead->pnext;
	printf("链表遍历：");
	while(p != NULL){
		printf("%d ",p->data);
		p = p->pnext; 
	};
	printf("n");
}
bool Is_empty(PNODE pHead){
	if(pHead->pnext == NULL)
	return true;
	else
	return false; 
}
int Length_list(PNODE pHead){
	PNODE p = pHead->pnext;
	int sum = 0;
	while(p != NULL){
		
		sum = sum + 1;
		p = p->pnext; 
	};
	return sum; 
}
void Sort_list(PNODE PHead){ //由小到大 
	if(Is_empty(PHead) == true)
	return;
	PNODE p = PHead->pnext;
	PNODE cur;
	int val;
	for(;p->pnext!=NULL;p=p->pnext){
		for(cur=p->pnext;cur!=NULL;){
			if(p->data < cur->data){
			val=cur->data;
			cur->data=p->data;
			p->data=val;
		    }
			cur=cur->pnext;	
		} 
	}	
	
} 
bool Insert_list(PNODE pHead,int pos,int val){  
	if(1>pos || pos>Length_list(pHead)+1){  //插入位置不正确 
		printf("插入位置不正确n");
		return 0; 
	}	
	PNODE p = (PNODE)malloc(sizeof(NODE));
	if(p == NULL){
		printf("分配内存失败n");
		exit;
	}
	p->data = val;
	PNODE fp=pHead;
	PNODE cur=pHead->pnext;
	int i;
	for(i=1;i
		fp=cur;
		cur=cur->pnext;
	}
	p->pnext=fp->pnext;
	fp->pnext=p;
	return true; 
}
bool Delete_list(PNODE pHead,int pos,int * p_dval){
		if(1>pos || pos>Length_list(pHead)){  //插入位置不正确 
		printf("删除位置不正确n");
		return 0; 
	}	
	
	PNODE fp=pHead;
	PNODE cur=pHead->pnext;
	int i;
	for(i=1;i
		fp=cur;
		cur=cur->pnext;
	}
	*p_dval=cur->data; 
	fp->pnext=cur->pnext;
	free(cur); 
	return true; 
}