[数据结构与算法]顺序表—单链表

单链表的基本操作

• 创建空链表
• 判断链表是否为空
• 插入结点
• 查找结点
• 打印结点
• 删除结点
• 回收结点

一、单链表的定义

/*定义单链表*/
struct node
{
    int data;             //数值域
	struct node *next;    //指针域
};

二、创建空链表

?

/*创建只有一个头结点的空链表*/ 
struct node *create_list()
{
	struct node *list = (struct node*) malloc (sizeof(struct node));			/*为链表申请空间*/ 
	if(list != NULL)
	{
		list->next = NULL;
		list->data = 0;
	}
	else printf(" Fail to create! ");										/*申请失败*/ 
	return list;
}

三、判断链表是否为空

/*判断链表是否为空*/
int judge_list(struct node *list){
	return(list->next == NULL);
}

四、插入结点

• 核心代码段

??

?????????插入结点

add->next = p->next;
p->next = add;

• 头插法插入数据

/*链表表头插入数据*/
void insert_head(struct node *list,int data)
{
   	struct node *Head=(struct node*)malloc(sizeof(struct node));
   	
	Head->data = data;
	Head->next = list->next;
	list->next = Head;
}

• 尾插法插入数据

/*链表表尾插入数据*/
void insert_tail(struct node *list,int data)
{
	struct node *Tail = (struct node*)malloc(sizeof(struct node));
	struct node *tra = list;

	while(tra->next != NULL) tra = tra->next;					/*寻找链表表尾结点*/ 
	
	Tail->data = data;
	tra->next = Tail;
	Tail->next = NULL;	
}

• 指定位置serial前插入数据

/*链表指定位置serial前插入数据*/
int insert_assign(struct node *list,int serial,int data){
	int tra = 1;
	struct node *pre = list;
	struct node *p = list->next;
	struct node *add = (struct node *)malloc(sizeof(struct node));

	while(p != NULL && tra < serial)					/*寻找指定位置的结点*/ 
	{
		pre = p;
		p = p->next;
		tra++;
	}
	if(p == NULL || serial <= 0){
		printf("Illegal serial.\n");
		return 0;
	}
	else{
	add->data = data;
	add->next = pre->next;
	pre->next = add;
	return 1;
	}
}

五、删除结点

• 核心代码段???

?????????寻找del所指向结点的前置结点pre

while(pre != NULL && pre->next != del)  
    pre = pre->next;

? ? ?

????????删除结点del

pre->next = del->next;
free(del);

• 删除第一个数值为data的结点

/*删除第一个数值为data的结点*/
int delete_first(struct node *list,int data)
{
	struct node *pre,*del;
	pre = list;
	
	if(list == NULL){
		printf("The list is NULL.\n");
		return 0;
	}
	
	while(pre->next != NULL && pre->next->data != data) pre = pre->next;	/*寻找数值为data的前置结点*/ 
	if(pre->next == NULL){
		printf("No exist.\n");							            /*找不到数据data的结点*/ 
		return 0;
	}
	else{
		del = pre->next;		
		pre->next = del->next;
		free(del);
		printf("The data has been deleted.\n");
		return 1;
	}
}

• 删除序号为serial的结点

/*删除序号为serial的结点*/
int delete_assign(struct node *list,int serial){
	int tra = 1;
	struct node *p = list;
	struct node *del;

	while(p != NULL && tra < serial)					/*寻找指定位置的结点*/ 
	{
		p = p->next;
		tra++;
	}
	if(p == NULL || serial <= 0){
		printf("Illegal serial\n");
		return 0;
	}
	else{
	del = p->next;		
	p->next = del->next;
	free(del);
	return 1;
	}
}

六、查找结点

• 查找第一个数值为data的结点

/*查找第一个数值为data的结点*/
int find_first(struct node *list,int data){
	struct node *find = list->next;

	if(list == NULL){
		printf("The list is NULL.\n"); 
		return 0;
	}
	while(find != NULL && find->data != data) find = find->next;			/*寻找数值为data的结点*/ 
	if(find == NULL){
		printf("No exist.\n"); 
		return 0;
	}
	else{
		printf("The data has been found.\n"); 
		return 1;
	}
}

• 查找所有数值为data的结点及序号

/*查找所有数值为data的结点及序号*/
int find_all(struct node *list,int data)
{
	int num = 1;
	struct node *find = list->next;

	if(list == NULL){
		printf("The list is NULL.\n"); 
		return 0;
	}
	while(find != NULL)														
	{
		if(find->data == data)	 printf("<%d> : %d\n",num,data);			/*寻找数值为data的结点和序号*/
		if(find == NULL){													/*未找到数据data的结点*/
			printf("No exist.\n"); 
			return 0;
		}
		find = find->next;	
		num++;
	}
	return 1;
}

七、打印链表

/*遍历并打印链表*/
void print_list(struct node *list)
{
	struct node *tra = list->next;
	while(tra->next != NULL)
	{
		printf("%d -> ",tra->data);
		tra = tra->next;
	}
	printf("%d\n",tra->data);
}

八、回收链表

• 回收链表空间

/*回收链表空间*/
void destroy_list(struct node *list)
{
	struct node *clean;
	while(list)
	{
		clean = list;
		list = list->next;
		free(clean);
	}
}