数据结构与算法——递增链表的插入

我就是我 2022-12-24 10:53 153阅读 0赞

题目描述  
给定一个递增整数序列和某个整数M，构造出此递增序列对应的链表，并创建以M为值的新结点插入到链表中，使其结果序列依然保持递增顺序。

输入  
每个输入包含一个测试用例，第1行包含原序列长度N（任意long int范围内的正整数）与待插入的整数M；第2行包含N个递增的整数代表原递增数列。

输出  
根据此递增数列，构造出此递增链表，然后将M插入到链表中，输出插入后的链表对应的数列。数字间隔一个空格，但末尾不能有空格。

样例输入  
6 2  
\-10 -3 1 5 9 30

样例输出  
\-10 -3 1 2 5 9 30

本题很忌讳使用两个指针同时指向同一动态内存的做法，如下：

void InsNode(LinkList PHead,DataType data)
    { 
    	Node *p;
    	Node *s;
    	Node *q;
    	p=PHead;
    	q=PHead;    //此处p和q同时指向链表头结点，从思维上来说感觉没问题 
    	p=p->Next;  //这样很容易产生误导，实际上这样做会出现一个严重问题
    	while(p->Next!=NULL&&p->Data<data) 
    	{        //两个指针变量如果指向同一动态内存，一个指针结束生命期释放内存 
    		p=p->Next;//另一指针所指地址虽被释放，但该指针不等于NULL而是随机值
    		q = q->Next;//此举十分容易引发野指针，导致内存破坏
    	}
    	if (p->Data > data)
    	{ 
    			s=(Node*)malloc(sizeof(Node));
    			s->Data=data;
    			s->Next=q->Next;
    			q->Next=s;
    	}
    	else
    	{ 
    		s = (Node*)malloc(sizeof(Node));
    		s->Data = data;
    		p->Next = s;
    		s->Next = NULL;
    	}
    }

具体代码如下：

#include <stdio.h>
    #include<stdlib.h>
    typedef struct Node{ 
    	int data;
    	struct Node *next;
    }Node,*LinkList;
    //链表初始化
    void InitList(LinkList *P){ 
    	*P = (LinkList)malloc(sizeof(Node));
    	if(*P==NULL){ 
    		return; 
    	}
    	(*P)->next=NULL;	
    } 
    //链表插入（尾插法）
    void CFromBack(LinkList P,int n){ 
    	int data,i;
    	Node *p,*s;
    	s=P;
    	for(i=0;i<n;i++){ 
    		scanf("%d",&data);
    		p=(LinkList)malloc(sizeof(Node));
    		p->data=data;
    		p->next=s->next;
    		s->next=p;
    		s=p;
    	}
    } 
    //在链表中插入数据
    LinkList function(LinkList P,int m){ 
    	Node *p,*s;
    	p=P;
    	s=(LinkList)malloc(sizeof(Node));
    	s->data=m;
    	s->next=NULL;
    	while(P->next!=NULL&&P->next->data<m){    //寻找插入位置
    		P=P->next;
    	}
    	s->next=P->next;
    	P->next=s;
    	return p;
    }
    //打印链表
    void PrintList(LinkList P){ 
    	Node *p;
    	p=P;
    	while(p->next!=NULL){ 
    		p=p->next;
    		printf("%d ",p->data);
    	}
    }
    
    int main(){ 
    	int M,N;
    	LinkList L;
    	InitList(&L);
    	scanf("%d %d",&N,&M);
    	CFromBack(L,N);
    	L=function(L,M);
    	PrintList(L);
    }