《数据结构实验与实训教程(第4版)》程序代码 下载本文

#include

void del( int *A, int *n, int x, int y ) { int i, j; for( i = j = 0; i < *n; i++ ) if( A[i] > y || A[i] < x ) // 不在x到y之间,则保留 1 ; 2 = j; }

void output( int *A, int n ) { int i; printf( \数组有%d个元素:\\n\ for( i = 0; i < n; i++ ) { printf( \ if( ( i + 1 ) % 10 == 0 ) printf( \ }

printf( \}

void main() {

int n; n = N; output( A, n ); 3 ; output( A, n ); }

8

实验2 链表的基本操作

四、参考程序

程序1:题1 链表基本操作函数 #include #include typedef struct list { int data;

struct list *next; }LIST;

void InitList( LIST **p ) /* 初始化链表 */ {

1 /*编写初始化链表子程序*/ }

void InsertList1( LIST **p, int item, int rc ) /* 向链表指定位置[rc]插入元素[item] */ {

int i; LIST *u, *q, *r;

/* u:新结点 q:插入点前驱 r:插入点后继 */

u = ( LIST * )malloc( sizeof(LIST) ); u->data = item;

for( i = 0, r = *p ; 2 ; i++ ) { q = r; r = r->next; }

if( 3 ) /* 插入首结点或p为空指针 */ *p = u; else

4

u->next = r; }

void InsertList2( LIST **p, int item )

/* 向有序链表[p]插入键值为[item]的结点 */

9

{

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