在一个递增有序链表中插入新结点并保持链表递增顺序不变

墨蓝 2022-06-13 07:38 142阅读 0赞

下列给定程序中已建立一个带头结点的单向链表,链表中各节点按节点数据域中的数据**递增有序**链接。函数fun的功能是:把形参x的值**放入一个新节点**并插入列表中使插入后各节点数据域中的数据**仍保持递增有序**。   
请在程序的下画线处填入正确的内容并将下画线删除，使程序得出正确的结果。

**结合例子**逐步分析可能比较容易理解。本题目我们只需要**关注****fun这个函数**。

试题程序。

\#include<stdio.h>  
\#include<stdlib.h>  
\#define N  8  
typedef struct list   **//定义链表结构体**  
\{   
int data;  
struct list \*next;

\} SLIST;

void fun(SLIST \*h, int x)    ** ** **//插入新结点并保持递增顺序**  
\{

SLIST \*p, \*q, \*s;     //s为新插入的结点，p、q两个结点分别用来记录当前链表结点位置的前一个结点和后一个结点

s = (SLIST \*)malloc(sizeof(SLIST));  
s->data = 1 ;         //**此处填：x，待插入的值**  
q = h;  
p = h->next;  
while (p != NULL && x > p->data)  
\{   
q = 2 ;        //**此处填：****p或q->next，意思是如果p不为空并且待插入的值x大于p位置的值，因为要满足递增顺序,**  
p = p->next;    //**就需要把p和q往后移动**  
\}  
s->next = p;  
/\*\*\*\*\*\*\*\*\*\* found \*\*\*\*\*\*\*\*\*\*/  
q->next = 3 ;        //**此处填：****s**

SLIST \*crealist(int \*a)    **//创建链表**  
\{   
SLIST \*h, \*p, \*q; int i;  
**h = p =** (SLIST \*)malloc(sizeof(SLIST));  
for (i = 0; i < N; i++)  
\{   
q = (SLIST \*)malloc(sizeof(SLIST));  
q->data = a\[i\]; p->next = q; p = q;  
\}  
p->next = 0;  
return h;

void outlist(SLIST \*h)  **//输出链表**  
\{   
SLIST \*p;  
p = h->next;  
if (p == NULL)  
printf("\\nThe list is NULL!\\n");  
else  
\{   
printf("\\nHead");  
do  
\{   
printf("->%d", p->data);  
p = p->next;  
\}  
while (p != NULL);  
printf("NULL");  
printf("->End\\n");  
\}

main( )  
\{   
SLIST \*head; int x;  
int a\[N\] = (11, 12, 15, 18, 19, 22, 25, 29);  
head = creatlist(a);  
printf("\\nThe list before inserting:\\n");  
oulist(head);  
printf("\\nEnter a number: "); scanf("%d", &x);  
fun(head, x);  
printf("\\nThe list after intserting:\\n");  
outlist(head);  
\}