欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-05-17 23:48:06
备考期间尝试写了一些基本数据结构的c语言实现,现做以下记录(基本数据元以int型为例): 全局定义及依赖: #include #include #define ok 1 #defi...

备考期间尝试写了一些基本数据结构的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;
}