已知性线表中的元素以值递增有序排列,并以单链表作存储结构。写一高效的算法,删除表中所有%D

Answer 1

#include<stdio.h>

typedef struct list{
int key;
struct list *next;
}LIST;

typedef struct{
LIST *next;
int size;
}HEAD;

LIST *insert_to_inorder(LIST *old_listp,int key)
{
LIST *new_listp;

if(old_listp == NULL)
{
new_listp = (LIST *)malloc(sizeof(LIST));
new_listp->key = key;
new_listp->next = NULL;
}
else if(old_listp->key >= key)
{
new_listp = (LIST *)malloc(sizeof(LIST));
new_listp->key = key;
new_listp->next = old_listp;
}
else
{
new_listp = old_listp;
new_listp->next = insert_to_inorder(old_listp->next,key);
}
return new_listp;
}

void insert_to(HEAD *headp,int key)
{
++(headp->size);
headp->next = insert_to_inorder(headp->next,key);
}

LIST *delete_to_inorder(LIST *old_listp,int target,int *is_deletedp)
{
LIST *tempp,*new_listp;
if(old_listp == NULL)
{
*is_deletedp = 0;
new_listp = NULL;
}
else if(old_listp->key == target)
{
*is_deletedp = 1;
tempp = old_listp;
new_listp = old_listp->next;
free(tempp);
}
else if(old_listp->key > target)
{
*is_deletedp = 0;
new_listp = old_listp;
}
else
{
new_listp = old_listp;
new_listp->next = delete_to_inorder(new_listp->next,target,is_deletedp);
}

return new_listp;
}

int delete_to(HEAD *headp,int target)
{
int is_deleted;

headp->next = delete_to_inorder(headp->next,target,&is_deleted);

if(is_deleted)
--(headp->size);

return is_deleted;
}

void print_to(HEAD *head)
{
LIST *temp;
for(temp = head->next;temp != NULL;temp = temp->next)
printf("%d\n",temp->key);
}

int main(void)
{
HEAD head = {NULL,0};

insert_to(&head,4);
insert_to(&head,3);
insert_to(&head,2);
insert_to(&head,1);

delete_to(&head,3);

print_to(&head);

getchar();

return 0;
}