dhu编程练习

2 在链表指定位置插入结点

#include <stdio.h>
#include <stdlib.h>
struct student
{
    
	int  num;
	struct student  *next;
};
//从键盘读入数据创建链表，新结点插入到尾部
struct student *createByTail()
{
    
	struct student *head;
	struct student *p1, *p2;
	int n;
	n = 0;
	p1 = p2 = (struct student*)malloc(sizeof(struct student));
	scanf("%d", &p1->num);
	head = NULL;  //首先置链表为空链表
	while (p1->num != -1)    //num为-1，意味着用户输入结束
	{
    
		n = n + 1;
		if (n == 1)            //创建第一个结点
			head = p1;
		else
			p2->next = p1;
		p2 = p1;            //p2始终指向最后一个结点（即尾指针）
		p1 = (struct student*)malloc(sizeof(struct student)); //p1指向新结点
		scanf("%d", &p1->num);
	}
	p2->next = NULL;  //最后一个结点的next赋值为NULL
	return head;
}
//输出链表中的信息（num）
void  displayLink(struct student *head)
{
    
	struct student *p;
	p = head;
	printf("head-->");
	while (p != NULL)
	{
    
		printf("%d-->", p->num);
		p = p->next;
	}
	printf("tail\n");
}
//在链表中第index处插入s指针所指向的结点。index从1开始。
//由于可能插在第一个结点，所以函数返回头指针给主调函数
struct student *insertNode(struct student *head, struct student *s, int index)
{
    
	//计算原链表有多少结点，为后面判断index下标是否正常铺垫
	struct student *p;
	p = head;
	int n=0;
	while (p)
	{
    
		n++;
		p = p->next;
	}
	//插入结点，考虑第一个位置插入的特殊情况
	struct student *q;
	q = head;
	if (index <= n + 1)//保证index下标的可行性
	{
    
		if (index == 1)
		{
    
			s->next = q;
			head = s;
		}
		else if (index!=0) {
     //Warning:这里index下标必须要注意判断！！
			for (int i = 2; i < index; i++)//保证q指向插入结点位置的前驱结点
			{
    
				q = q->next;
			}
			s->next = q->next;
			q->next = s;

		}
	}
	return head;
}
int main()
{
    
	struct student *head;
	int index, data;
	head = createByTail();
	while (scanf("%d%d", &index, &data) != -1)
	{
    
		struct student * s = (struct student *) malloc(sizeof(struct student));
		s->num = data;
		head = insertNode(head, s, index);
		displayLink(head);
	}
	return 0;
}