在实验6-2的单向链表代码基础上,增加插入节点的函数,实现在链表中按升序的顺序将指定的数值 data 插入相应的节点。也就是将data插入在第一个大于data的节点之前。
插入节点函数接口:
struct link *InsertNode(struct link *head, int data)
head ?是链表头节点的指针data 是要插入的节点的数值。- 函数返回插入相应节点后,头节点的指针。
主函数示例:
#include <stdio.h>
#include <stdlib.h>
struct link
{
int data;
struct link *next;
};
struct link *AppendNode(struct link *head,int data);
void DisplyNode(struct link *head);
void DeleteMemory(struct link *head);
struct link * DeleteNode(struct link *head,int data);
struct link *InsertNode(struct link *head, int nodeData);
int main()
{
char c;
int data = 0;
struct link *head = NULL; /* 链表头指针 */
while (1)
{
scanf("%d",&data);
if (data==-1)
break;
head = AppendNode(head,data);/* 向head为头指针的链表末尾添加节点 */
}
DisplyNode(head); /* 显示当前链表中的各节点信息 */
scanf("%d",&data);
head = InsertNode(head,data);
DisplyNode(head); /* 显示当前链表中的各节点信息 */
DeleteMemory(head); /* 释放所有动态分配的内存 */
return 0;
}
输入格式:
第一行: 一系列以-1 结束的数值,用以构建单向链表。
第二行: 指定的数值,将此数值插入链表中第一个大于该数值的节点之前。
输出格式:
在构建单向链表后,显示整个链表。 在插入指定数值后,再次显示整个链表。
输入样例:
在这里给出一组输入。例如:
1 3 5 7 9 -1
6
输出样例:
在这里给出相应的输出。例如:
1->3->5->7->9
1->3->5->6->7->9
输入样例:
在这里给出一组输入。例如:
1 3 5 3 1 -1
4
输出样例:
在这里给出相应的输出。例如:
1->3->5->3->1
1->3->4->5->3->1
?
#include <stdio.h>
#include <stdlib.h>
struct link
{
int data;
struct link *next;
};
struct link *AppendNode(struct link *head,int data);
void DisplyNode(struct link *head);
void DeleteMemory(struct link *head);
struct link * DeleteNode(struct link *head,int data);
struct link *InsertNode(struct link *head, int nodeData);
int main()
{
char c;
int data = 0;
struct link *head = NULL; /* 链表头指针 */
while (1)
{
scanf("%d",&data);
if (data==-1)
break;
head = AppendNode(head,data);/* 向head为头指针的链表末尾添加节点 */
}
DisplyNode(head); /* 显示当前链表中的各节点信息 */
scanf("%d",&data);
head = InsertNode(head,data);
DisplyNode(head); /* 显示当前链表中的各节点信息 */
DeleteMemory(head); /* 释放所有动态分配的内存 */
return 0;
}
struct link *AppendNode(struct link *head,int data){
struct link *p=NULL, *q=head;
p=(struct link*)malloc(sizeof(struct link));
if(p==NULL){
exit(0);
}
if(head==NULL){
head=p;
}
else{
while(q->next!=NULL){
q=q->next;
}
q->next=p;
}
p->data=data;
p->next=NULL;
return head;
}
void DisplyNode(struct link *head){
struct link*p;
p=head;
int i=1;
while(p!=NULL)
{
if(i==1){
printf("%d",p->data);
}else{
printf("->%d",p->data);
}
i++;
p=p->next;
}
}
void DeleteMemory(struct link *head)
{
struct link *p = NULL;
struct link *pr = head;
while(pr!=NULL)
{
p = pr;
pr = pr->next;
free(p);
}
}
struct link * DeleteNode(struct link *head,int data){
printf("\n");
struct link*pr=head;
if(head==NULL){
return(head);
}
int i=2;
while(i){
struct link*p=head;
while(p->data!=data&&p->next!=NULL){
pr=p;
p=p->next;
}
if(p->data==data){
if(p==head){
head=p->next;
}else{
pr->next=p->next;
}
free(p);
}
i--;
}
return head;
}
struct link *InsertNode(struct link *head, int data){
printf("\n");
struct link *p=head,*pr=head,*temp=NULL;
p=(struct link*)malloc(sizeof(struct link));
p->next=NULL;
p->data=data;
if(head==NULL){
head=p;
}
else{
while(pr->data<data&&pr->next!=NULL){
temp=pr;
pr=pr->next;
}
if(pr->data>=data){
if(pr==head){
p->next=head;
head=p;
}
else{
pr=temp;
p->next=pr->next;
pr->next=p;
}
}
else{
pr->next=p;
}
}
return head;
}
?
|