逆置链式链表(线性表)

逆置链式链表(线性表)

时间: 1ms        内存:128M

描述:

本题只需要提交填写部分的代码
(线性表)试编写算法将线性表就地逆置,以链式存储结构实现。
代码:
#include <stdio.h>
#include <malloc.h>
struct Num
{
    int n;
    struct Num *next;
}num;
struct Num *createlist(struct Num *head);
void print(struct Num *head);
void destroy(struct Num *head);
void destroy(struct Num *head)
{
 struct Num *p;
 while(head!=NULL)
 {
  p=head->next;
  delete(head);
  head=p;
 }
}
int main()
{
    struct Num *head=NULL;
    head=createlist(head);       //建立
    print(head);//输出
 destroy(head);
    return 0;
}
struct Num *createlist(struct Num *head)                //头插法建立链表
{
    struct Num *p;
    p=head=(struct Num*)malloc(sizeof(struct Num));
    head=NULL;                                    
    p=(struct Num*)malloc(sizeof(struct Num));            //p建立新结点
    while(scanf("%d",&p->n)!=EOF)                      //将新结点插到开头的位置
    {
        /***************/
            添加代码
        /*****************/
        p=(struct Num*)malloc(sizeof(struct Num));         //p每次建立新结点
    }
    return head;
}
void print(struct Num *head)
{
    struct Num *current=head;
    while(current!=NULL)
    {
        printf("%d ",current->n);
        current=current->next;
    }
}

输入:

1 2 3 4 5 6 7 8 9

输出:

9 8 7 6 5 4 3 2 1

示例输入:

10 23 56 89 11

示例输出:

11 89 56 23 10 

提示:

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

#include<iostream>
using namespace std;
struct line
{
	int num;
	line *next;
};
line *creat()
{
	line *head;
	line *p;
	p=head=new line;
	while(cin>>p->num)
	{
		p->next=new line;
		p=p->next;

	}
	p->next=NULL;
	return head;
}
line *nizhi(line *head)
{
	line *pFront,*pRear,*p;
	p=pFront=pRear=head;
	p=p->next;
	pFront->next=NULL;
	if(p==NULL)return head;
	pRear=p->next;
	p->next=pFront;
	while(pRear)
	{
		pFront=p;
		p=pRear;
		pRear=p->next;
		p->next=pFront;
	}
	head=p;
	return head;
}
void print(line *head)
{
	head=head->next;
	while(head)
	{
		cout<<head->num<<" ";
		head=head->next;
	}
}
int main()
{
	line *head;
	head=creat();
	head=nizhi(head);
	print(head);
	return 0;

}

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

#include<stdio.h>
#include<malloc.h>
#define NULL 0
#define LEN sizeof(struct date)

int t,m=0;
struct date
{
	int num;
	struct date *next;
};
struct date * creat()
{
	struct date *head;
	struct date *p1,*p2;
	t=0;
	p1=p2=(struct date *)malloc(LEN);
	head=NULL;
	while(scanf("%d",&p1->num)!=EOF)
	{
		t++;
		m++;
		if(t==1)
			head=p1;
		else
			p2->next=p1;
		p2=p1;
		p1=(struct date *)malloc(LEN);
	}
	p2->next=NULL;
	return (head);
}
void print(struct date *head)
{
	struct date *p;
	p=head;
	if(head!=NULL)
		do
		{
			printf("%d ",p->num);

			p=p->next;
		}while(p!=NULL);
	printf("\n");
}

int main()
{
	struct date *p,*p3,*p4,*p5;
	p3=creat();
    p=p3; 
    p4=p; 
    p=p->next; 
    while(p) 
    { 
        p3=p4; 
        p4=p; 
        p5=p->next; 
        p4->next=p3; 
        p=p5;      
    }
	p=p4; 
    while(m--) 
        p=p->next; 
    p->next->next=NULL; 
    print(p4);
	return 0;
}

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

点赞

发表评论

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