《数据结构实验与实训教程（第4版）》程序代码(3)

{

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 #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