C语言线性单链表相关函数和算法的基本实现详细教程

备考期间尝试写了一些基本数据结构的c语言实现，现做以下记录（基本数据元以int型为例）：

全局定义及依赖：

#include  
#include 
#define ok  1
#define error  0
#define end null

链表结点定义：

typedef struct lnode
{
	int data;
	struct lnode *next;
}node,*linkedlist;

链表初始化：

//初始化链表 
linkedlist initlist()
{
	node *l;
	l = (node *)malloc(sizeof(node));
	if(l==null)
	{
		printf("init error!");
	}
	l->next = null;
	printf("init ok!\n");
	return l;
}

头插法生成链表 即在头结点后插入新元素 ：

//头插法生成链表 即在头结点后插入新元素 
linkedlist createlisth(int n)
{
	int i = 0;
	node *l;
	l = (node *)malloc(sizeof(node));
	l->next = null;
	
	int x;
	while(idata = x;
		p->next = l->next;
		l->next = p;
		i++;
	}
	return l;
}

尾插法生成链表 即在尾结点后插入新元素：

//尾插法生成链表 即在尾结点后插入新元素
linkedlist createlistt(int n)
{
	int i = 0;
	node *t;
	t = (node *)malloc(sizeof(node));
	t->next = null;
	
	node *r;
	r = t;
	int x;
	while(idata = x;
		r->next = p;
		r = p;
		i++;
	}
	r->next = null;
	return t;
}

计算链表长度：

//calculate the length
int calculatelength(linkedlist l)
{
	int length = 0;
	node *p = l;
	while(p->next)
	{
		length++;
		p = p->next;
	}
	return length;
} 

在指定链表的指定索引处插入新值：

//insert element into index x
int insertelementintox(linkedlist l,int index,int e)
{
	node *p = l;
	int length = calculatelength(l);

	if(index<1||index>length+1){return error;}
	else
	{
		for(int i = 1;inext;
		}
		node *q = (node *)malloc(sizeof(node));
		q->data = e;
		q->next = p->next;
		p->next = q;
		return ok;
	}
}

通过索引删除指定链表中的元素：

//delete element by index
int deleteelementbyindex(linkedlist l,int index)
{
	int length = calculatelength(l);
	if(index<1||index>length){return error;}
	else
	{
		node *p = l;
		for(int i = 1;inext;
		}
		node *q = p->next;
		p->next = q->next;
		free(q);
		return ok;
	}
}

遍历并打印链表中所有结点元素：

//遍历 
void traversallist(linkedlist l)
{
	node *p = l->next;
	while(p!=end)
	{
		printf("%d ",p->data);
		p = p->next;
	}
	printf("\n");
}

对两个链表做非递减归并：

linkedlist mergedecline(linkedlist la,linkedlist lb)
{
	node *a = la->next;
	node *b = lb->next;
	free(la);
	free(lb);
	linkedlist lc = initlist();
	node *temp = lc;
	while(a!=null&&b!=null)
	{
		if(a->data<=b->data)
		{
			temp->next = a;
			a = a->next;
			temp = temp->next; 
		}
		else
		{
			temp->next = b;
			b = b->next;
			temp = temp->next;
		}
	}
	temp->next == null;
	if(a!=null){temp->next = a;}
	if(b!=null){temp->next = b;}
	return lc;
}

删除给定链表中所有重复元素（对重复元素只保留其中一个）：

//delete repeating node  
void deleterepeatingnode(linkedlist l)
{
	node *p,*q,*r;
	p = l->next;
	if(p==null){return;}
	while(p->next)
	{
		q = p;
		while(q->next)
		{
			if(q->next->data==p->data)
			{
				r = q->next;
				q->next=r->next;
				free(r);
			}
			else
			{
				q = q->next;
			}
		}
		p = p->next;
	}
}

将链表中的元素按从小到大进行排序：

//sort from small to large
int sortfsl(linkedlist l)
{
	if(l->next==null){return error;}
	else
	{
		node *r = l;
		node *p = r->next;
		node *q = p->next;
		while(p->next)
		{
			while(q)
		 {
			  if(p->data>q->data)
			  {
				int e = p->data;
				p->data = q->data;
				q->data = e;
				q = q->next;
			  }
			
			  else
			  {
				  q = q->next;
			  }
		 }
		 
		 r = r->next;
		 p = p->next;
		 q = p->next;
		}
		return ok;
	}
	
}

删除链表中所有元素值大于x的结点：

int deleteagtx(linkedlist l,int x) 
{
	if(l->next==null){return error;}
	else{
		node *p = l;
		while(p->next)
		{
			if(p->next->data>x)
			{
				node *temp = p->next;
				p->next = p->next->next;
				free(temp);
			}
			else{
				p = p->next;
			}
		}
		return ok;
	}
}

将链表中所有负数前置并排序：

//负数在前排序 
int negativepriority(linkedlist l)
{
	if(l->next==null){return error;}
	else{
		node *p = l;
		while(p->next)
		{
			if(p->next->data<0)
		 {
			  node *temp = p->next;
			  p->next = temp->next;
			  temp->next = l->next;
			  l->next = temp;
		 }
		 else{p = p->next;}
		}
		return ok;
	}
} 

南京航空航天大学922部分真题：

//2014真题-数据结构6
int _2014_t6(linkedlist l)
{
	if(l->next==null){return error; }
	else{
		node *p = l;
		node *t = null;
		node *s = null;
		int count = 1;
		while(p->next)
		{
			if(count%2==0)
			{
				t = p->next;
				p->next = p->next->next; //关键步骤 
				t->next = s;
				s = t;
			}
			else{
				p = p->next;
			}
			count++;
		}
		p->next = s;
		return ok;
	}
} 

//2015真题数据结构6
int _2015_t6(linkedlist l)
{
	if(l->next==null){return error; }
	else{
		node *p = l->next;
		node *q = l->next;
		node *t = l;
		node *top = null;
		while(p->next)
		{
			while(q->next)
			{
				if(q->next->data>p->data)
				{
					p = q->next;
					t = q;
					q = q->next;
				}
				else{
					q = q->next;
				}
			}
			t->next = t->next->next;
			p->next = top;
			top = p;
			t = l;
			p = q = l->next;
		}
		p->next = top;
		return ok;
	}
} 

//2013真题数据结构6
int _2013_t6(linkedlist la,linkedlist lb)
{
	if(la->next==null){return error;}
	else{
		node *a = la;
		node *b = lb;
		int element;
		while(a->next)
		{
			element = a->next->data;
			while(b->next)
			{
				if(b->next->data==element){break;}
				else{b = b->next;}
			}
			
			if(b->next==null)
			{
				node *t = a->next;
				a->next = a->next->next;
				free(t);
			}
			else{a = a->next;} 
			b = lb;
		}
		
		a = la;
		while(a->next)
		{
			node *p = la->next;
			int e;
			while(p->next)
			{
				if(p->next->data>a->next->data)
				{
					e = a->next->data;
					a->next->data = p->next->data;
					p->next->data = e;
				}
				p = p->next;	
			}
			a = a->next;
		}
		return ok;
	}
}

//2011真题-数据结构24
int _2011_t24(linkedlist l)
{
 if(l->next == null){return error;}
 else{
 		node *p = l;
	  int element = p->next->data;
	  while(p->next)
	  {
		 if(element>p->next->data)
		 {
			element = p->next->data;
		 }
		 p = p->next;
	  }
	  p = l;
	  while(p->next)
	  {
	  	if(p->next->data==element)
	  	{
	  		node *t = p->next;
	  		p->next = p->next->next;
	  		free(t);
	  		break;
	  	}
	  	p = p->next;
	  }
	  return ok;
 }
}

使用单链表实现数制转换（1-10进制）：

//数制转换（1-10进制）
void transcoder(int num,int r)
{
	linkedlist l = initlist();
	l->data = -1;
	node *top = null;
	int i;
	while(num>0)
	{
		i = num%r;
		top = (node *)malloc(sizeof(node));
		top->data = i;
		top->next = l;
		l = top;
		num = num/r;
	}
	printf("the result is: ");
	while(top->data!=-1)
	{
		printf("%d ",top->data);
		top = top->next;
	}	
} 

测试：

int main()
{
	int n = 0;
	
	printf("please enter the length:\n");
	scanf("%d",&n);
	linkedlist la = createlistt(n);
	printf("traversal the list a:\n");
	traversallist(la);
	
	printf("please enter the length:\n");
	scanf("%d",&n);
	linkedlist lb = createlistt(n);
	printf("traversal the list b:\n");
	traversallist(lb);

 traversallist(mergedecline(la,lb)); //merge
 
 printf("please enter the length:\n");
	scanf("%d",&n);
	linkedlist ld = createlistt(n);
	traversallist(ld);
 deleterepeatingnode(ld);  //delete repeating node
 traversallist(ld);
 
 int index,element;
 printf("please enter the length:\n");
	scanf("%d",&n);
	linkedlist le = createlistt(n);
	traversallist(le);
	printf("please enter the index:\n");
	scanf("%d",&index);
	printf("please enter the element:\n");
	scanf("%d",&element);
	insertelementintox(le,index,element);  //insert element into index x
	traversallist(le);
	
	int index;
	printf("please enter the length:\n");
	scanf("%d",&n);
	linkedlist lf = createlistt(n);
	traversallist(lf);
	printf("please enter the index:\n");
	scanf("%d",&index);
	deleteelementbyindex(lf,index);  //delete element by index
	traversallist(lf);
	
 printf("please enter the length:\n");
	scanf("%d",&n);
	linkedlist lg = createlistt(n);
	traversallist(lg);
	sortfsl(lg);//sort from small to large
	traversallist(lg);
 
 int x;
 printf("please enter the length:\n");
	scanf("%d",&n);
	linkedlist lh = createlistt(n);
	traversallist(lh);
	printf("please enter the value:\n");
	scanf("%d",&x);
	deleteagtx(lh,x);//p3-3-2-3-1 删除所有元素值大于x的结点
	traversallist(lh);
	
 printf("please enter the length:\n");
	scanf("%d",&n);
	linkedlist li = createlistt(n);
	traversallist(li);
	negativepriority(li);//负数在前排序
	traversallist(li);
	
	printf("please enter the length:\n");
	scanf("%d",&n);
	linkedlist lj = createlistt(n);
	traversallist(lj);
	_2014_t6(lj);//2014真题-数据结构6
	traversallist(lj);
	
	printf("please enter the length:\n");
	scanf("%d",&n);
	linkedlist lk = createlistt(n);
	traversallist(lk);
	_2015_t6(lk);//2015真题-数据结构6
	traversallist(lk);
	
	printf("please enter the length:\n");
	scanf("%d",&n);
	linkedlist ll = createlistt(n);
	traversallist(ll);
	printf("please enter the length:\n");
	scanf("%d",&n);
	linkedlist lm = createlistt(n);
	traversallist(lm);
	_2013_t6(ll,lm);//2013真题-数据结构6
	traversallist(ll);
	
 printf("please enter the length:\n");
	scanf("%d",&n);
	linkedlist ln = createlistt(n);
	traversallist(ln);
	_2011_t24(ln);
	traversallist(ln);  //2011真题-数据结构24
	
	int num;
	printf("please enter the num:\n");
	scanf("%d",&num);
	printf("please enter the r:\n");
	scanf("%d",&n);
	transcoder(num,n);
	
	return 0;
}