数据结构考研分类复习真题 第二章 答案[42]

()要求编程实现带头结点的单链表的逆置首先建立一单链表然后逆置

typedef struct node

{int data;∥假定结点数据域为整型

struct node *next;

}node*LinkedList;

LinkedList creat( )

{LinkedList headp

int x;

head=(LinkedList)malloc(sizeof(node));

head>next=null; /*设置头结点*/

scanf(%d&x);

while(x!=) /*约定输入时退出本函数*/

{p=(LinkedList)malloc(sizeof(node));

p>data=x;

p>next=head>next;/* 将新结点链入链表*/

head>next=p;

scanf(%d&x);

}

return(head);

}∥结束creat函数

LinkedList invert(LinkedList head)

/*逆置单链表*/

{LinkedList p=head>next; /*p为工作指针*/

head>next=null;

while(p!=null)

{r=p>next; /*暂存p的后继*/

p>next=head>next;

head>next=p;

p=r;

}

return(head);

}/*结束invert函数*/

main()

{LinkedList la;

la=creat( ); /*生成单链表*/

la=invert(la);/*逆置单链表*/

}

()本题要求将数据项递减有序的单链表重新排序使数据项递增有序要求算法复杂度为O(n)虽没说要求将链表逆置这只是叙述不同本质上是将单链表逆置现编写如下

LinkedList invert(LinkedList la)∥la是带头结点且数据项递减有序的单链表本算法将其排列成数据项递增有序的单链表

{p=la>next; /*p为工作指针*/

la>next=null;

while(p!=null)

{r=p>next; /*暂存p的后继*/

p>next=la>next;/*将p结点前插入头结点后*/

la>next=p;p=r;

}

}∥结束算法

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []