逆序建立链表(线性表)

逆序建立链表(线性表)

时间: 1ms        内存:128M

描述:

本题只需要提交填写部分的代码

(线性表)逆序建立一个链表,带头结点

代码:

#include <stdio.h>
#include <stdlib.h>
typedef struct number  //定义结构体,NUM为结构体变量名
{
    int date;
    struct number *link;  //指向下一个结点的指针
    struct number *before;//指向结点前驱的指针
}NUM;
void destroy( NUM *head)
{
  NUM *p;
 while(head!=NULL)
 {
  p=head->link;
  delete(head);
  head=p;
 }
}
NUM *creat(int n)
{
    NUM *p,*q,*head;
    head=p=q=(NUM*)malloc(sizeof(NUM));//分别开辟一块内存空间给head,p,q
    head->before=NULL;  //head为头,令head的前驱为NULL
    scanf("%d",&p->date);
    while(--n)  //尾插建表,同时记录每个结点的前驱
    {
        p=(NUM*)malloc(sizeof(NUM));//新建p结点,插入q节点后,不仅要让q的link指向p,还要记录q是p的前驱
        scanf("%d",&p->date);
        /***********/

         添加代码

      /*************/    }
    q->link=NULL;
    return q;
}
void play(NUM *h)
{
    NUM *p;
    for(p=h;p!=NULL;p=p->before)//从后往前倒着输出
        printf("%d ",p->date);
 destroy(p);
}
int main()
{
    int n;
    scanf("%d",&n);
    play(creat(n));
    return 0;
}

输入:

输入链表长度n:5

输入数据:1 2 3 4 5

输出:

5 4 3 2 1

示例输入:

6
10 2 9 7 8 8

示例输出:

8 8 7 9 2 10 

提示:

参考答案(内存最优[748]):

#include <stdio.h>
#include <stdlib.h>
typedef struct shu
{
	int date;
	int link;
	int before;
}S;
S *creat(int n)
{
	S *p,*q,*head;
	head=p=q=malloc(sizeof(S));
	head->before=NULL;
	scanf("%d",&p->date);
	while(--n)
	{
		p=malloc(sizeof(S));
		scanf("%d",&p->date);
		p->before=q;
		q->link=p;
		q=p;
	}
	q->link=NULL;
	return q;
}
void play(S *h)
{
	S *p;
	for(p=h;p!=NULL;p=p->before)
		printf("%d ",p->date);
}
int main()
{
	int n;
	scanf("%d",&n);
	play(creat(n));
	return 0;
}

参考答案(时间最优[0]):

#include <stdio.h>
#include <stdlib.h>
typedef struct shu
{
	int date;
	int link;
	int before;
}S;
S *creat(int n)
{
	S *p,*q,*head;
	head=p=q=malloc(sizeof(S));
	head->before=NULL;
	scanf("%d",&p->date);
	while(--n)
	{
		p=malloc(sizeof(S));
		scanf("%d",&p->date);
		p->before=q;
		q->link=p;
		q=p;
	}
	q->link=NULL;
	return q;
}
void play(S *h)
{
	S *p;
	for(p=h;p!=NULL;p=p->before)
		printf("%d ",p->date);
}
int main()
{
	int n;
	scanf("%d",&n);
	play(creat(n));
	return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注