数据结构--单链表

单链表

定义：单链表是用一组任意的存储单元存放线性表的元素，这组存储单元可以连续，也可以不连续，甚至可以零散的分布在内存的任意位置。

单链表的实现

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

//定义单链表的数据类型，设置为int 型
typedef int DataType;
//定义单链表的结构体
typedef struct Node{
	DataType data;
	struct Node * next;
}Node;

//单链表的初始化,生成只有头节点的空单链表
Node * InitList(){
	Node * first = (Node * )malloc(sizeof(Node));
	first->next = NULL;
	return first;
}

//判空操作,判断单链表是否只有头结点
int Empty(Node * first){
	
	if(first->next == NULL) return 1;
	else return 0;
}

//遍历操作
void PringtList(Node * first){
	
	Node * p = first->next;
	while(p!=NULL){
		printf("%d\n",p->data);
		p = p->next;
	}
}

//求链表的长度
int Length(Node * first){
	
	Node * p = first->next;
	int count = 0;
	while(p!=NULL){
		
		p = p->next;
		count++;
	}
	return count;
}

//按值查找
int Locate(Node * first,DataType x){
	
	Node * p = first->next;
	int count = 1;
	while(p!=NULL){
		
		if(p->data == x) return count;
		p = p->next;
		count++;
	}
	return 0;
}

//按位查找
int Get(Node * first,int n,DataType * ptr){
	
	Node * p = first->next;
	int count = 1;
	while( count < n && p != NULL)
	{
		p = p->next;
		count++;
		
	}
	if( p == NULL) {
		printf("位置错误，查找失败\n");
		return 0;
	}else{
		
		*ptr = p->data;
		return 1;
	}
		
	
	
}

//插入操作
int Insert(Node * first,int i,DataType x){
	
	Node * s = NULL;
	Node * p = first;
	int count = 0;
	while(p != NULL && count < i-1){
		
		p = p->next;
		count++;
	}
	if(p == NULL){
		
		printf("位置错误，插入失败\n");
		return 0;
	}else{
		
		s = (Node *)malloc(sizeof(Node));
		s->data = x;
		s->next = p->next;
		p->next = s;
		return 1;
	}
	
	
	
}

//建立单链表,使用尾插法
Node * CreateList(DataType a[],int n){
	
	Node * s = NULL;
	Node * r = NULL;	//尾指针初始化
	Node * first = (Node * )malloc(sizeof(Node));
	r = first;
	for(int i = 0 ; i<n;i++){
		
		s = (Node *)malloc(sizeof(Node));
		s->data = a[i];
		r->next = s;
		r = s;
	}
	r->next = NULL;
	return first;
	
}

//删除操作

int Delete(Node * first,int i,DataType * ptr){
	
	Node *p = first;
	Node *q = NULL;
	int count = 0;
	DataType x;
	
	//查找到 第i-1 个节点
	while(p != NULL && count < i-1){
		count++;
		p = p->next;
		
	}
	
	
	if(p == NULL || p->next == NULL){
		
		printf("位置错误删除失败\n");
		return 0;
	}else{
		
		q = p->next;
		*ptr = q->data;
		p->next = q->next;
		free(q);
		return 1;
		
	}
	
}

//销毁链表

void DestroyList(Node * first){
	
	Node * p = first;
	while(first != NULL)
	{
		first = first->next;
		free(p);
		p = first;
	}
	
}

//单链表的使用
int main(){
	
	int r[5] = {1,2,3,4,5};
	int i,x;
	Node * first = NULL;
	first = CreateList(r,5);
	
	printf("当前单链表的数据为：\n");
	PringtList(first);
	
	printf("执行插入操作\n");
	Insert(first,2,8);
	printf("插入后结果：\n");
	PringtList(first);
	
	printf("当前单链表的长度%d\n",Length(first));
	
	printf("请输入要查找的元素值\n");
	scanf("%d",&x);
	i = Locate(first,x);
	if(i !=  0){
		printf("元素%d的位置为: %d\n",x,i);
	}else{
		
		printf("单链表中没有此元素\n");
	}
	
	printf("请输入删除第几个元素\n");
	scanf("%d",&x);
	if(Delete(first,i,&x) == 1){
		
		printf("删除的数据元素值为%d,删除后数据为：\n",x);
		PringtList(first);
	
	}else{
	
		printf("删除失败\n");
	}
	
	DestroyList(first);
	return 0;
	
}