数据结构编程--查找与排序 题
发布网友
发布时间：2022-04-22 11:08
共2个回答
热心网友
时间：2023-10-12 00:21
#include <stdio.h>
typedef struct node
{
int data;
struct node* next;
struct node* pre;
}node,*link;
int droplink( link &L );
//检查表是否存在,是返回true,否返回false
bool checklink( link &L )
{
if ( L==NULL )
{
return false;
}
else
{
return true;
}
}
//新建一个结点,以data作为它的值,返回指向这个结点的指针
link createnode( int data )
{
link p;
if ( (p = (link)malloc(sizeof(node)))==NULL )
{
printf("malloc failed!@createnode\n");
return NULL;
}
else
{
p->data = data;
p->next = NULL;
p->pre = NULL;
return p;
}
}
//创建一个带头结点的链表，成功返回0，失败返回-1
int create( link &L )
{
if ( checklink(L) )
{
printf( "链表已经存在,先销毁再创建!\n" );
droplink( L );
}
if ( (L = (link)malloc(sizeof(node)))==NULL )
{
printf("malloc failed!\n");
return -1;
}
L->next = NULL;
L->pre = NULL;
return 0;
}
//统计链表长度,成功返回链表长度，失败返回-1
int getlength( link &L )
{
int length = 0;
link p = L;
while ( p->next != NULL )
{
length++;
p = p->next;
}
return length;
}
//根据值查询结点
link findpos( link &L, int data )
{
if ( !checklink(L) )
{
printf( "无此链表\n" );
return NULL;
}
link p = L;
while ( p!=NULL )
{
if ( p->data == data )
{
return p;
}
p = p->next;
}
}
//找出第pos位置上的结点，返回指向这个结点的指针
link findnode( link &L, int pos )
{
if ( !checklink(L) )
{
printf( "无此链表\n" );
return NULL;
}
if ( pos <= 0 )
{
printf("位置过小!@findnode\n");
return NULL;
}
link p = L;
for ( int i=0; i<pos; i++ )
{
if ( p==NULL )
{
printf("位置超出链表长度!@findnode\n");
return NULL;
}
p = p->next;
}
return p;
}
//把n插入至rear之后，成功返回0，失败返回-1
int pushback( link &L, link &n )
{
if ( !checklink(L) )
{
printf( "无此链表\n" );
return -1;
}
int length = getlength(L);
link rear = NULL;
if ( length==0 )
{
rear = L;
}
else
{
rear = findnode( L, length );
}
rear->next = n;
n->pre = rear;
rear = n;
return 0;
}
//把n插入至L的第pos位（0代表头结点），成功返回0，失败返回-1
int insert( link &L, link &n, int pos )
{
if ( !checklink(L) )
{
printf( "无此链表\n" );
return -1;
}
link p = findnode( L, pos );
if ( p==NULL )
{
printf( "查找结点失败!@insert\n" );
return -1;
}
n->next = p->next;
p->next = n;
n->pre = p;
n->next->pre = n;
return 0;
}
//把L链表第pos位置上的结点删除 （0代表头结点），成功返回0，失败返回-1
int delnode( link &L, int pos )
{
if ( !checklink(L) )
{
printf( "无此链表\n" );
return -1;
}
link p = findnode( L, pos );
if ( p==NULL )
{
printf( "查找结点失败!@delnode\n" );
return -1;
}
p->pre->next = p->next;
p->next->pre = p->pre;
free( p );
p = NULL;
return 0;
}
//销毁链表L 成功返回0，失败返回-1
int droplink( link &L )
{
if ( !checklink(L) )
{
printf( "无此链表\n" );
return -1;
}
int length = getlength(L);
while ( length>0 )
{
delnode( L, length );
length = getlength(L);
}
free( L );
L = NULL;
return 0;
}
//对链表进行排序 type为1时是升序排列，为-1时为降序 (冒泡排序法)
void sort( link &L, int type )
{
int length = getlength( L );
if ( length <= 0 )
{
printf("升序过小!\n");
return;
}
switch( type )
{
case 1: printf( "升序排列链表!\n" );break;
case -1: printf( "降序排列链表!\n" );break;
default: printf( "参数错误!\n" );return;
}
for( int i=1; i<length; i++ )
{
for( int j=1; j<length; j++ )
{
printf("i=%d,j=%d,",i,j);
printf("findnode(L,j)->data =%d, findnode(L,j+1)->data=%d\n",findnode(L,j)->data,findnode(L,j+1)->data);
if ( type == -1 )
{
//降序
if ( findnode(L,j)->data < findnode(L,j+1)->data )
{
int t = findnode(L,j)->data;
findnode(L,j)->data = findnode(L,j+1)->data;
findnode(L,j+1)->data = t;
}
}
else
{
//升序
if ( findnode(L,j)->data > findnode(L,j+1)->data )
{
int t = findnode(L,j)->data;
findnode(L,j)->data = findnode(L,j+1)->data;
findnode(L,j+1)->data = t;
}
}
}
}
}
void output( link &L )
{
link p=L->next;
int i=0;
while ( p!=NULL )
{
printf( "[%d]=\t%d\n", i, p->data );
i++;
p=p->next;
}
}
main()
{
int length;
link L = NULL;
//新建链表
create( L );
printf("===输入数据===\n");
printf("请输入链表结点数量:");
scanf( "%d", &length );
if ( length<=0 )
{
printf("数量错误!退出程序\n");
return -1;
}
int i=0;
int data;
link tmp = NULL;
while ( i!=length )
{
printf("请输入data值:" );
scanf( "%d", &data );
tmp = createnode(data);
pushback( L, tmp );
i++;
}
output(L);
printf("===插入新节点===\n");
printf("请输入data值:" );
scanf( "%d", &data );
tmp = createnode(data);
insert( L, tmp, 2 );
output(L);
printf("===查询节点===\n");
printf("请输入要查询的data值:" );
scanf( "%d", &data );
findpos( L, data );
printf("===链表长度为%d===\n", getlength(L));
printf("升序排序后链表为:\n");
sort(L, 1 );
output(L);
printf("降序排序后链表为:\n");
sort(L,-1);
output(L);
getchar();
}
热心网友
时间：2023-10-12 00:22
