Question

求C语言大神帮忙，一道数据结构题，删除单链表中最大和次最大的数，感激不尽

Answer 1

#include <stdio.h>

#define elemType int
#define status int
#define OVERFLOW -1
#define ERROR 0
#define OK 1

/* 单链表数据结构 */
typedef struct lNode {
	elemType data;
	struct lNode *next;
} lNode, *linkList;

/******************************** 以下为函数声明 ********************************/
void initList (linkList *L);							/* 初始化 */
status listIsEmpty (linkList L);						/* 判断单链表是否为空 */
status listInsertNode (linkList L, int i, elemType e);	/* 单链表指定位置插入新元素 */
status listDeleteNode (linkList L, int i, elemType *e);	/* 删除单链表指定位置元素 */
status listOutput (linkList L);							/* 输出链表 */
/******************************** 以上为函数声明 ********************************/

/* 初始化 */
/* 操作结果：构造一个空的单链表L */
void initList (linkList *L) {
	*L = (linkList) malloc (sizeof (struct lNode)); /* 产生头节点，并使L指向此头节点 */
	if(!*L) /* 内存分配失败 */
		exit (OVERFLOW);
	(*L)->next = NULL; /* 指针域为空 */
}

/* 判断单链表是否为空 */
/* 初始条件：单链表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
status listIsEmpty (linkList L) {
	return L->next == NULL;
}

/* 单链表指定位置插入新元素 */
/* 操作结果：在带头结点的单链表L中第i个位置之前插入元素e */
status listInsertNode (linkList L, int i, elemType e) {
	int j=0;
	linkList p=L,s;
	
	while (p && j<i-1) { /* 寻找第i-1个结点 */
		p = p->next;
    	j++;
	}
	
	if (!p || j>i-1) /* 插入位置不合理：i小于1或者大于表长 */
		return ERROR;

	/* 生成新结点，并插入L中 */
	s = (linkList) malloc (sizeof (struct lNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	
	return OK;
}

/* 删除单链表指定位置元素 */
/* 操作结果：在带头结点的单链线性表L中，删除第i个元素，并由e返回其值 */
status listDeleteNode (linkList L, int i, elemType *e) {
	int j = 0;
	linkList p = L, q;
	
	while (p->next && j<i-1) { /* 寻找第i个结点，并令p指向其前驱结点 */
    	p = p->next;
		j++;
	}
	
	if (!p->next || j>i-1) /* 删除位置不合理：i小于1或者大于表长 */
		return ERROR;
	
	/* 删除并释放结点 */
	q = p->next;
	p->next = q->next;
	*e = q->data;
	free (q);
	
	return OK;
}

/* 输出链表 */
status listOutput (linkList L) {
	linkList p = L->next; /* p指向第一个结点 */
	while (p!=NULL) {
		printf ("%d\t",p->data);
		p = p->next;
	}
	putchar ('\n');
	return OK;
}

/*寻找链表中最大数*/
/*操作结果：L为带头结点的单链表的头指针。最大值的位置赋值给maxIndex。*/
status findSpecificElem  (linkList L, int *maxIndex) {
	int i=1;
	elemType maxData; /*记录最大数*/
	
	linkList p = L->next; /* p指向第一个结点 */
	maxData = p->data;
	
	while (p) { /* 遍历链表寻找最大数 */
		if (p->data > maxData) {
			maxData = p->data;
			*maxIndex = i;
		}
		p = p->next; /* p指向下一个结点 */
		i++;
	}
	
	return OK;	
}

int main (void) {
	linkList L;
	int m1Index,m2Index; /*记录最大、次大数的位置*/
	elemType m1Data,m2Data; /*记录最大、次大数*/
	
	/*构造一个链表，其中最大数为12，在第6位；次大数为9，在第3位。*/
	initList (&L);
	listInsertNode (L, 1, 7);
	listInsertNode (L, 2, 5);
	listInsertNode (L, 3, 9);
	listInsertNode (L, 4, 2);
	listInsertNode (L, 5, 4);
	listInsertNode (L, 6, 12);
	listInsertNode (L, 7, 6);
	
	/*输出链表*/
	puts ("链表原始内容为："); 
	listOutput (L);
	putchar ('\n');
	
	/*先找到当前链表最大数，删除该元素；再找一遍当前链表最大数，再删除该元素。*/
	/*如此实现删除链表中最大数、次大数*/
	findSpecificElem  (L, &m1Index);
	listDeleteNode (L, m1Index, &m1Data);
	
	findSpecificElem  (L, &m2Index);
	listDeleteNode (L, m2Index, &m2Data);
	
	printf ("最大数：%d\n次大数：%d\n", m1Data, m2Data);
	putchar ('\n');
	
	puts ("删除最大数、次大数后的链表内容为："); 
	listOutput (L);
	
	getch (); /*屏幕暂留*/ 
	return 0 ;
}

运行结果