头歌：第1关：有序单链表的插入操作

第1关：有序单链表的插入操作

任务描述

本关任务：已知带头结点的单链表中的元素以值递增有序排列，要求实现一个算法，在单链表中插入一个新整数，并保持该单链表仍然以值递增有序。

相关知识

单链表结点类型定义如下：

typedef  struct  LNode         // 结点类型定义 
{       
    ElemType  data;           //数据域
    struct  LNode  *next;     //指针域
}LNode,*LinkList;             // LinkList为结构指针类型
1
2
3
4
5

为了令算法具有通用性，使其尽可能地适用于各种可能的场合，将要处理的数据类型加以抽象，使其适用于不同类型的数据，是提高代码通用性的重要手段。

单链表中数据类型ElemType可以多种多样，但是在编程实现算法时针对不同数据类型，每类数据元素的输入输出是有区别的，单链表的基本操作算法要在计算机上执行，须针对ElemType类型数据编写输入、输出、比较等函数。

ElemType类型根据实际问题需要灵活定义，但是在编程实现算法时针对不同数据类型，数据元素的输入输出是有区别的，单链表的基本操作算法要在计算机上执行，须针对ElemType类型数据编写输入、输出、比较是否相等、比较大小等函数：

void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);
int compare(ElemType a,ElemType b);
1
2
3
4

ElemType类型根据实际问题需要灵活定义，如果ElemType类型是结构体类型，结构体变量之间整体是不可以比较大小的，结构体变量之间只能比较某个成员的大小；比较两个结构体变量是否相等与比较两个结构体变量某个成员的大小也是有区别的。

在单链表各种操作算法实现时，应根据ElemType类型编写判断两个数据元素是否相应的比较函数equals()和判断两个数据元素大小的比较函数compare()。举例说明：
（1）数据元素的类型ElemType为int类型

typedef  int  ElemType;
int equals(ElemType a,ElemType b)
{ // 根据两个整数a，b是否相等，分别返回1或0
       if (a == b)
         return 1;
       else
           return 0;
}
int compare(ElemType a,ElemType b)
{ // 根据两个整数a，b的大小，分别返回1、0、-1
       if (a > b)
         return 1;
       else
        if (a == b)
           return 0;
        else
        return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

（2）数据元素的类型ElemType为char [20] 类型

typedef  char  ElemType[20];
int equals (ElemType a,ElemType b)
{ // 根据两个字符串a、b是否相等，分别返回1或0 
       if ( strcmp(a,b) == 0 )
         return 1;
       else
           return 0;
}
int compare(ElemType a,ElemType b)
{ // 根据两个字符串a、b的大小，分别返回1、0、-1 
       if ( strcmp(a,b) > 0 )
         return 1;
       else
        if ( strcmp(a,b) == 0 )
             return 0;
        else
               return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

（3）数据元素的类型ElemType为自定义结构体变量类型，判断两个数据元素的大小，就需要比较某个结构体变量成员的大小。

struct student
{ 
      char num[20];
      char name[16];
      int  year;
      float  score;
};
typedef  struct student  ElemType;
int equals (ElemType a, ElemType b) 
{   // 如果a,b的所有成员值相等，返回1，否则返回0
    if ( ( strcmp( a.num, b.num ) != 0 )
        return 0;
    else  if ( strcmp( a.name, b.name ) != 0 )
        return 0;
    else  if  ( a.year != b.year ) 
        return 0;
       else  if ( a.score != b. score ) )
           return 0;
    else
        return 1;
}
int compare(ElemType a,ElemType b) 
{   // 如果要按照学生学号比较大小，则需根据a,b的num成员比较大小的结果，返回1、0、-1
    if ( ( strcmp( a.num, b.num ) > 0 )
        return 1;
    else  if ( strcmp( a.num, b.num ) == 0 )
        return 0;
    else 
        return -1;   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

在有序单链表中插入新的结点，算法的关键问题：

首先必须维护当前结点的前指针，
然后还要维护要插入的位置的前后指针，
每个要插入的结点都要从头开始比较。

编程要求

根据提示，在右侧编辑器 Begin-End 区间补充代码，完成单链表按照值的大小插入函数的定义，具体要求如下：

int ListSortInsert(LinkList &L,ElemType e,int(*compare)(ElemType, ElemType) ); //带头结点的单链表L，其结点存储的数据是递增有序的，将e插入L，并保持该单链表的有序性

说明：

用函数指针compare来实现对ElemType类型数据元素的比较大小的函数的调用。
首先创建带头结点的空单链表，反复调用本函数，构造一个有序单链表。

测试说明

平台会对你编写的代码进行测试：

测试输入： 5 12 47 5 8 69

预期输出： 5 8 12 47 69

输入说明 第一行输入单链表的数据元素的个数N； 第二行输入单链表N个无序的整数。

输出说明 第一行输出递增的有序单链表。

开始你的任务吧，祝你成功！

完整代码：

#include 
#include 
#include 
using namespace std;

/* 定义ElemType为int类型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);
int comp(ElemType a,ElemType b);

/* 单链表类型定义 */
typedef struct LNnode
{	
	ElemType data;
	struct LNnode *next;
}LNnode,*LinkList;

void InitList(LinkList &L);
int ListSortInsert (LinkList &L, ElemType e,int (*compare)(ElemType,ElemType));
void ListTraverse(LinkList L,void(*vi)(ElemType));

int main()               //main() function 
{	
     LinkList A;
     ElemType e;
     InitList(A);
      int n,i;
     // cout<<"Please input the list number ";
     cin>>n;
     for(i=1;i<=n;i++)
     { 
		 cin>>e;
         ListSortInsert(A, e,comp);
      }
	 ListTraverse(A,output) ;
    return  0;  
 }


/*****ElemType类型元素的基本操作*****/
void input(ElemType &s)
{
	cin>>s;
}
void output(ElemType s)
{
	cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{
	if(a==b)
		return  1;
	else
		return  0;
}
int comp(ElemType a,ElemType b)
{
	if(a>b)
		return  1;
	else
		if(a<b)
			return  -1;
		else
		return  0;
}


/*****单链表的基本操作*****/
void InitList(LinkList &L)
{ 
	// 操作结果：构造一个空的单链表L
	/********** Begin **********/ 
	L=(LinkList)malloc(sizeof(LNnode)); // 产生头结点，并使L指向此头结点
	if(!L) // 存储分配失败
		return ;
	L->next=NULL; // 指针域为空
	/********** End **********/
}

void ListTraverse(LinkList L,void(*vi)(ElemType))
{ 
	// 初始条件：单链表L已存在。
	//操作结果：依次对L的每个数据元素调用函数vi()
	/********** Begin **********/ 
	LinkList p=L->next;
	while(p)
	{
		vi(p->data);
		p=p->next;
	}
	printf("\n");
	/********** End **********/
}

int ListSortInsert (LinkList &L, ElemType e,int (*comp)(ElemType,ElemType))
{ 
	/********** Begin **********/ 
	LinkList s,p,q;
    s= (LinkList)malloc(sizeof(LNnode));
    if(!s) return 0;
    s->data =e;
    if(L==NULL || comp(e,L->data)==-1){
        s->next =L;
        L=s;
    }else{
        q=L;
        p=q->next;
    }
    while(p!=NULL && comp(e,p->data)==1){
        q=p;
        p=p->next;
    }
    s->next =p;
    q->next =s;
    
    
    return 1;
	/********** End **********/
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124