数据结构之链表

思维导图

练习

头文件

#ifndef __HEAD_H__
#define __HEAD_H__



#include <stdio.h>
#include <string.h>
#include <stdlib.h>
enum
{
	FALSE=-1,
	SUCCESS
};
typedef int datatype;
//定义节点结构体
//节点：数据域　指针域

typedef struct Node
{
	//数据域：存储数据元素
	datatype data;
	//指针域：存储指针
	struct Node *next;	
}*Linklist;


Linklist creat();
Linklist insert_head(Linklist head,datatype element);
void output(Linklist head);
Linklist insert_rear(Linklist head,datatype element);
Linklist delete_head(Linklist head);
Linklist delete_rear(Linklist head);
Linklist insert_pos(Linklist head,int pos,datatype element);
Linklist delete_pos(Linklist head,int pos);
Linklist change_pos(Linklist head,int pos,datatype element);
void search_pos(Linklist head,int pos);
int search_element(Linklist head,datatype element);
Linklist rev(Linklist head);
int search_transpos(Linklist head,int pos);
Linklist chang_element(Linklist head,datatype key,datatype element);
Linklist delete_element(Linklist head,datatype key);
void Bubble(Linklist head);
void Select(Linklist head);
Linklist free_space(Linklist head);



#endif

自定义函数

#include "head.h"
/*
 * function:    创建新节点
 * @param [ in] 
 * @param [out] 
 * @return      
 */
Linklist creat()
{
	Linklist s=(Linklist)malloc(sizeof(struct Node));
	if(NULL==s)
		return NULL;
	//成功则初始化
	s->data=0;
	s->next=NULL;
	return s;
}
/*
 * function:    头插入
 * @param [ in] 
 * @param [out] 
 * @return    
 *       如果形参头指针发生指向的改变，则必须返回
 */
Linklist insert_head(Linklist head,datatype element)
{
	//创建新节点s
	Linklist s=creat();
	s->data=element;
	//判断链表是否为空
	if(head==NULL)
	{
		head=s;
	}
	else
	{
		s->next=head;
		head=s;
	}
	return head;
}



/*
 * function:    遍历输出
 * @param [ in] 
 * @param [out] 
 * @return      
 */
void output(Linklist head)
{
	if(NULL==head)
		return;
	Linklist p=head;
	while(p!=NULL)//也可以是while(p)
	{
		printf("%-5d",p->data);
		p=p->next;
	}
	puts("");
}

/*
 * function:    尾插入
 * @param [ in] 
 * @param [out] 
 * @return      
 */

Linklist insert_rear(Linklist head,datatype element)
{
	Linklist s=creat();
	s->data=element;
	Linklist p=head;
	if(NULL==head)
		head=s;
	else
	{
		while(p->next!=NULL)
		{
			p=p->next;
		}
		p->next=s;
	}
	return head;
}
/*
 * function:   头删
 * @param [ in] 
 * @param [out] 
 * @return      
 */
Linklist delete_head(Linklist head)
{
	if(head==NULL)
		return NULL;
	else
	{
		Linklist del=head;
		head=head->next;
		free(del);	
		del=NULL;
	}
	return head;
}
/*
 * function:    尾删
 * @param [ in] 
 * @param [out] 
 * @return      
 */
Linklist delete_rear(Linklist head)
{
	if(head==NULL)
		return NULL;
	else if(head->next==NULL)
	{
		free(head);
		head==NULL;
		return head;
	}
	else
	{
		Linklist del=head;
		while(del->next->next!=NULL)
		{
			del=del->next;
		}
		free(del->next);
		del->next=NULL;
	}
	return head;
}
/*
 * function:    计算链表长度
 * @param [ in] 
 * @param [out] 
 * @return      
 */
int length(Linklist head)
{
	int len=0;
	while(head!=NULL)
	{
		head=head->next;
		len++;
	}
	return len;
}


/*
 * function:    按任意位置插入
 * @param [ in] 
 * @param [out] 
 * @return      
 */
Linklist insert_pos(Linklist head,int pos,datatype element)
{
	if(pos<0||pos>length(head)+1)
		return head;
	Linklist s=creat();
	s->data=element;
	if(pos==1)
	{
		head=insert_head(head,element);
		return head;
	}
	Linklist p=head;
	for(int i=1;i<pos-1;i++)	
	{
		p=p->next;	
	}		
	s->next=p->next;	
	p->next=s;	
	return head;
}
/*
 * function:    按任意位置删除
 * @param [ in] 
 * @param [out] 
 * @return      
 */
Linklist delete_pos(Linklist head,int pos)
{
	if(pos<0||pos>length(head)+1)
		return head;
	if(pos==1)
	{
		head=delete_head(head);
		return head;
	}
	Linklist p=head;
	for(int i=1;i<pos-1;i++)	
	{
		p=p->next;	
	}		
	Linklist s=p->next;	
	p->next=s->next;
	free(s);
	s=NULL;
	return head;
}
/*
 * function:    按任意位置修改
 * @param [ in] 
 * @param [out] 
 * @return      
 */
Linklist change_pos(Linklist head,int pos,datatype element)
{
	if(pos<0||pos>length(head)+1)
		return head;
	if(pos==1)
	{
		head->data=element;
		return head;
	}
	Linklist p=head;
	for(int i=1;i<pos;i++)	
	{
		p=p->next;	
	}		
	p->data=element;
	return head;
}
/*
 * function:    按任意位置查找
 * @param [ in] 
 * @param [out] 
 * @return      
 */
void search_pos(Linklist head,int pos)
{	
	if(pos<0||pos>length(head))
		return;
	if(head==NULL)
		return;
	Linklist p=head;
	for(int i=1;i<pos;i++)
	{
		p=p->next;
	}
	printf("%d\n",p->data);
}


/*
 * function:    按任意元素查找
 * @param [ in] 
 * @param [out] 
 * @return      
 */
int  search_element(Linklist head,datatype element)
{
	if(head==NULL)
		return FALSE;
	Linklist p=head;
	int pos=0;
	while(p)
	{
		pos++;
		if(p->data==element)
		{
			return pos;
		}
		p=p->next;
	}
	if(pos==0)
		return FALSE;
}
/*
 * function:    逆置链表
 * @param [ in] 
 * @param [out] 
 * @return      
 */
Linklist rev(Linklist head)
{
	if(head==NULL)
		return head;
	Linklist p=head->next;
	head->next=NULL;
	Linklist t=p;
	while(p)
	{
		t=p;
		p=p->next;
		t->next=head;
		head=t;
	}
	return head;
}


/*
 * function:    查找倒数第ｎ个值
 * @param [ in] 
 * @param [out] 
 * @return      
 */
int search_transpos(Linklist head,int pos)
{
	if(head==NULL)
		return FALSE;
	if(pos<0||pos>length(head))
		return FALSE;
	Linklist p=head;
	Linklist q=head;
	for(int i=0;i<pos;i++)
	{
		p=p->next;
	}
	while(p)
	{
		p=p->next;
		q=q->next;
	}
	return q->data;
}
/*
 * function:    按任意元素修改
 * @param [ in] 
 * @param [out] 
 * @return      
 */
Linklist chang_element(Linklist head,datatype key,datatype element)
{
	if(head==NULL)
		return NULL;
	int pos=search_element(head,key);
	head=change_pos(head,pos,element);
	return head;
}

/*
 * function:    按任意元素删除
 * @param [ in] 
 * @param [out] 
 * @return      
 */
Linklist delete_element(Linklist head,datatype key)
{
	if(head==NULL)
		return NULL;
	int pos=search_element(head,key);
	head=delete_pos(head,pos);
	return head;
}
/*
 * function:    冒泡排序(从小到大)
 * @param [ in] 
 * @param [out] 
 * @return      
 */
void Bubble(Linklist head)
{
	if(head==NULL)
		return;

	for(int i=0;i<length(head)-1;i++)
	{
		Linklist p=head;
		for(int j=0;j<length(head)-i-1;j++)
		{
			if(p->data >p->next->data)
			{
				datatype temp=p->data;
				p->data=p->next->data;
				p->next->data=temp;
			}
			p=p->next;
		}
	}
}

/*
 * function:    简单选择排序(从大到小)
 * @param [ in] 
 * @param [out] 
 * @return      
 */
void Select(Linklist head)
{
	if(head==NULL)
		return;
	Linklist p=head;
	for(int i=0;i<length(head)-1;i++)
	{
		datatype max=p->data;
		Linklist q=p->next;
		for(int j=i+1;j<length(head);j++)
		{
			if(p->data<q->data)
			{
				max=q->data;
			}
			q=q->next;
		}
		chang_element(head,max,p->data);
		p->data=max;
		p=p->next;
	}
}
/*
 * function:    释放空间
 * @param [ in] 
 * @param [out] 
 * @return      
 */
Linklist free_space(Linklist head)
{
	if(head==NULL)
		return NULL;
	for(int i=0;i<length(head);i++)
	{
		Linklist s=head;
		head=head->next;
		free(s);
		s=NULL;
	}
	return head;
}

主函数

#include "head.h"
int main(int argc, const char *argv[])
{
	//定义单链表的头指针
	Linklist head=NULL;
	int n;
	//插入的值
	datatype element;
	
	printf("请输入链表长度\n");
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		printf("请输入第%d个值:",i+1);
		scanf("%d",&element);
		//head=insert_head(head,element);
		head=insert_rear(head,element);
	}
//	head=delete_head(head);
//	head=delete_rear(head);
// 按位置插入
	int pos;
/*
	printf("请输入要插入的位置");
	scanf("%d",&pos);
	printf("请输入要插入的值");
	scanf("%d",&element);
	head=insert_pos(head,pos,element);
	output(head);
	printf("请输入要删除的位置");
	scanf("%d",&pos);
	head=delete_pos(head,pos);
	output(head);
*/
/*
	printf("请输入要修改的位置");
	scanf("%d",&pos);
	printf("请输入要修改后的值");
	scanf("%d",&element);
	head=change_pos(head,pos,element);
	output(head);
	printf("请输入要查找的位置");
	scanf("%d",&pos);
	search_pos(head,pos);
*/
	printf("请输入要查找的值");
	scanf("%d",&element);
	pos=search_element(head,element);
	printf("%d\n",pos);
//	head=rev(head);
	output(head);

/*	printf("请输入要查找倒数第几个");
	scanf("%d",&pos);
	int num=search_transpos(head,pos);
	printf("倒数第%d个的值为:%d\n",pos,num);
*/
	int key;

	printf("请输入要修改的值");
	scanf("%d",&key);
	printf("请输入修改后的值");
	scanf("%d",&element);
	head=chang_element(head,key,element);
	output(head);
	printf("请输入要删除的值");
	scanf("%d",&element);
	head=delete_element(head,element);
	output(head);

	Bubble(head);
	output(head);
	Select(head);
	output(head);
	free_space(head);
	return 0;
}

效果图

?