c/c++语言开发共享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;  }