不带头结点的单向链表(题目总结！！！)_本题要求求出不带头结点的单链表中的最大值并返回。 /* 求单链表值最大的结点 */

不带头结点的单向链表建立与输出

typedef struct node{
	int data;			//数据域
	struct node*next;	//指针域，存放下一个结点的地址
}ElemSN;
1
2
3
4

• 不带头结点的链表的建立（尾插法，正向建链）

ElemSN *Greatlink(int a[],int n)
{
	ElemSN *h=NULL,*tail,*p;
	for(int i=0;i<n;i++)
	{
		p=(ElemSN *)malloc(sizeof(ElemSN));
		p->data=a[i];
		p->next=NULL;
		
		if(!h)	//h为第一个结点 
			h=tail=p;
		else
			tail=tail->next=p;	//尾插法	
	}
	return h;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 不带头结点的链表的建立（头插法,逆向建链）

ElemSN *Greatlink1(int a[],int n)
{
	ElemSN *h=NULL,*p;
	for(int i=0;i<n;i++)
	{
		p=(ElemSN *)malloc(sizeof(ElemSN));
		p->data=a[i];
		
		p->next=h;
		h=p;	
	}
	return h;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

• 链表的输出

void Printlink(ElemSN*h)
 {
 	ElemSN*p;
 	p=h;
 	while(p){
 		printf("%5d",p->data);
 		p=p->next;
	 }		
 }
1
2
3
4
5
6
7
8
9

• 将建立的链表逆向输出

 void Preprint(ElemSN* h)
 {
 	ElemSN*pend=NULL,*p;		//pend是界限的作用
 	while(pend-h){
 		for(p=h;p->next-pend;p=p->next);
 		printf("%5d",p->data);
 		pend=p;
 		
	 }
  } 
1
2
3
4
5
6
7
8
9
10

3->1->9->5正向建链
5->9->1->3逆向输出

不带头结点链表——习题

1. 输出单向链表尾结点的值

void PrintTailNode(ElemSN*h){
	ElemSN *p;
	for(p=h;p->next!=NULL;p=p->next);
	printf("%d",p->data);
}
1
2
3
4
5

2. 输出单向链表结点的个数

void Print_node_num(ElemSN*h){
	ElemSN *p;
	int cnt;
	for(p=h;p!=NULLL;p=p->next){
		printf("%d",p->data);
		cnt++;
	}
	printf("结点个数为%5d",cnt);
}
1
2
3
4
5
6
7
8
9

3. 输出单向链表奇数（偶数）结点的个数

int CountODD（ElemSN*h）{
	int odd=0;
	ElemSN *p;
	for(p=h;p;p=p->next)
		odd+=p->data%2;	//奇数加1
	return odd;	
}
1
2
3
4
5
6
7

4. 输出单向链表结点中的最大值

void MaxNode(ElemSN *h){
	ElemSN *pmax;
	ElemSN *p;
	pmax=h;
	for(p=h->next;p;p=p->next){
		if(pmax->data  <  p->data)
			pmax=p;
	}
	printf("max node is:%5d",pmax->data);
}
1
2
3
4
5
6
7
8
9
10

5. 查找值为key的结点，并返回结点的地址值，若没有找到，则返回空；

ElemSN * Find_key_node(ElemSN *h,int key){
	ElemSN *p;
	for(p=h;p&&p->data-key;p=p->next);	//p为空或者p的数值为key,跳出循环
	return p;
}
1
2
3
4
5

6. 删除关键字为key的结点，有重复值（先查再删）

ElemSN * Del_key_node(ElemSN *h,int key){
	ElemSN *p，*q;	//删除结点需要两指针联动
	p=h;
	while(p){
		if(p->data-key){		//不是key继续向下遍历
			q=p;
			p=p->next;
		}
		else{
			if(p-h){			//不是头结点
				q->next=p->next;
				free(p);
				p=q->next;
			}
			else{			//是头结点
			h=h->next;
			free(p);
			p=h;
			}
		}
	}
	return h;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

7. 设head指向一个非空单向链表，数据域的值重复且无序，删除链表中的重复值

Del_node(ElemSN *h){
	ElemSN *p,*q,*pt;		//pt相当于关键字key
	pt=h;
	while(pt){
		q=pt;
		p=pt->next;
		while(p){
			if(p->data - q->data){
				q=p;
				p=p->next;
			}
			else{
				q->next=p->next;
				free(p);
				p=q->next;
			}
		}
		pt=pt->next;
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

进阶习题

1. 设head指向一个非空链表，将该链表就地逆置（先删 再头插）
   

ElemSN *Printlink(ElemSN*h)
{
	ElemSN *h1=NULL;
	ElemSN *p;
	while(h){
		p=h;
		h=h->next;
		p->next=h1;
		h1=p;
	}
	return h1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

2. 将无序链表升序排列（找最大值，头插）

ElemSN *SelectSort(ElemSN *h){
	ElemSN *h1,*p,*q,*pm,*qm;
	h1=NULL;
	while(h){
		for(q=pm=h,p=h->next ; p ; q=p,p=p->next)
			if(p->data > pm->data){
				pm=p;
				qm=q;
			}
			//for循环找最大值
		if(pm-h){		//找到的pm不是头结点
				qm->next = pm->next;
			}
		else		h=h->next;
		
		pm->next=h1;	//将pm放到新的链表h1中
		h1=pm;
	}
		return h1;	//返回新链表头结点h1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3. 将无序链表降序排列（找最小值，头插）思路同上一题
4. 将链表中所有奇数结点放到偶数结点之前
   （思路：奇数结点删除然后头插，偶数结点继续遍历）

ElemSN *ODDbehind (ElemSN *h)
{
	ElemSN *q=h,*p=h->next;
	while(p){
		if(p->data%2){				//奇数结点
			q->next=p->next;
			p->next=h;			//删除
			h=p;				//头插
			p=q->next;
		}
		else{
			q=p;
			p=p->next;
		}		
	}
	return h;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

5. 判断一个非空单向链表是否带环（详解）

6.判断两个链表是否有交点