{
LIST *u, *q, *r;
/* u:新结点 q:插入点前驱 r:插入点后继 */
u = ( LIST * )malloc( sizeof(LIST) ); u->data = item;
for( r = *p; 5 && r->data < item; q = r, r = r->next ) ; /* 从链表首结点开始顺序查找 */ if( r == *p )
/* 插入首结点或p为空指针 */
6 else
q->next = u; u->next = r; }
/* 删除键值为[item]的链表结点, 返回0: 删除成功 1: 没找到 */ int DeleteList( LIST **p, int item ) {
LIST *q, *r; /* q:结点前驱 r:结点后继 */ q = *p;
if( q == NULL )
/* 链表为空 */
return 1;
if( q->data == 7 ) { /* 要删除链表首结点 */ p = q->link; /* 更改链表首指针 */
8 /* 释放被删除结点的空间 */ return 0; /* 删除成功 */ }
for( ; 9 && 10 ; r = q, q = q->next ) ; /* 寻找键值为[item]的结点 */ if( q->data == item ) { /* 找到结点 */
q->next=r->next /* 被删结点从链表中脱离 */ free( q ); /* 释放被删除结点的空间 */ return 0; /* 删除成功 */ }
return 1; /* 没有指定值的结点, 删除失败 */ }
/* 查找键值为[item]的链表结点位置, 返回>=1: 找到 -1: 没找到 */ int FindList( LIST *p, int item ) { int i;
for( i = 1; p->data != item && p != NULL ; 11 , i++ )
10
; /* 查找键值为[item]的结点 */ return ( p == NULL ) ? -1 : i; /* 找到返回[i] */ }
void OutputList( LIST *p ) /* 输出链表结点的键值 */
{
while( 12 ) { printf( p = p->next; /* 遍历下一个结点 */ } }
void FreeList( LIST **p ) /* 释放链表空间 */
{
LIST *q, *r;
for( q = *p; q != NULL; ) { 13 q = q->next; 14 }
*p = NULL; /* 将链表首指针致空 */
}
程序2：题2
void main() {
LIST *p; int op, i, rc;
InitList( &p );
/* 初始化链表 */
while( 1 ) { printf( 请选择操作 1：指定位置追加 2: 升序追加 3: 查找结点\n ); printf( 4: 删除结点 5: 输出结点 6: 清空链表 0：退出\n fflush( stdin ); /* 清空标准输入缓冲区 */ scanf( %d switch( op ) { case 0: /* 退出 */ return; case 1: /* 指定位置追加结点 */
printf( 请输入新增结点键值和位置： );
11
scanf( %d%d, &rc ); 1 ; break; case 2: /* 按升序追加结点 */ printf( 请输入新增结点键值： scanf( %d ); InsertList2( &p, i ); break; case 3: /* 查找结点 */ printf( 请输入要查找结点的键值： scanf( %d ); rc = 2 ; if( rc > 0 )
printf( 位置为[%d]\n
else
printf( 没找到\n break; case 4: /* 删除结点 */
printf( 请输入要删除结点的键值：
scanf( %d );
rc = 3 ; if( rc == 0 ) printf( 删除成功\n, rc ); else
printf( 没找到\n break; case 5: /* 输出结点 */ printf( 链表内容为:\n ); 4 ; break; case 6: /* 清空链表 */
5 ;
break;
} } }
程序3：题3
#include
12
typedef struct node { int x; struct node *next; }NODE;
void input( NODE **a ) { NODE *p, *q; int i;
printf( 请输入链表的元素，-1表示结束\n *a = NULL; while( 1 ) { scanf( if( i == -1 ) break; p = ( NODE * )malloc( sizeof(NODE) ); p->x = i; p->next = NULL; if( *a == NULL ) *a = q = p; else { q->next = p; q = q->next;
}
} }
void output( NODE *a )
{ int i; for( i = 0; a != NULL; i++, a = a->next ) { printf( if( ( i + 1 ) % 10 == 0 ) printf( }
printf( }
void disa( NODE *a, NODE **b ) {
13
NODE *r, *p, *q; p = a;
r = *b = ( a == NULL ) ? NULL : a->next; // 如果链表a为空，则链表b也为空 while( 1 && 2 ) { q = p->next; // q指向偶数序号的结点 3 // 将q从原a链表中删除
r->next = q; // 将q结点加入到b链表的末尾 4 // r指向b链表的最后一个结点
p = p->next; // p指向原a链表的奇数序号的结点
} r->next = NULL;
// 将生成b链表中的最后一个结点的next域置空
}
void main() { NODE *a, *b; input( &a );
printf( 链表a的元素为:\n output( a ); 5 printf( 链表a的元素（奇数序号结点）为:\n output( a ); printf( 链表b的元素（偶数序号结点）为:\n output( b ); }
14