(1).试编写算法将带头结点单链表就地逆置,所谓“就地”是指辅助空间为O(1)
【解析】
此问题有两种解法。
a 把头节点摘下来,然后用头插法建链表就形成所谓的就地逆置
b 依次遍历将指针反转,不过最后一个节点需要注意一下
两算法时间复杂度都是O(n),空间都是O(1)
【算法】
第一种算法:
//就地反转
int LinkListRerverse(LinkList *head){
LinkList *q,*p;
p = head->next;
head->next = NULL;
while(p != NULL){
q = p->next;
p->next = head->next;
head->next = p;
p = q;
}
return 0;
}
完整例子:
#include<stdio.h>
#include<malloc.h>
typedef struct Node
{
int data;
struct Node *next;
}LinkList;
//就地反转
int LinkListRerverse(LinkList *head){
LinkList *q,*p;
p = head->next;
head->next = NULL;
while(p != NULL){
q = p->next;
p->next = head->next;
head->next = p;
p = q;
}
return 0;
}
//输出数据
int LinkListPrintf(LinkList *head){
LinkList *p;
p = head;
while(p->next){
p = p->next;
printf("%d ",p->data);
}
printf("\n");
return 0;
}
//创建链表
int LinkListCreate(LinkList *head,int n){
LinkList *p,*newNode;
head->next = NULL;
p = head;
//输入数据
for(int i = 0;i < n;i++){
//创建节点
newNode = (LinkList*)malloc(sizeof(LinkList));
scanf("%d",&newNode->data);
newNode->next = p->next;
p->next = newNode;
p = newNode;
}
return 0;
}
int main()
{
int n;
while(scanf("%d",&n) != EOF){
LinkList *head;
head = (LinkList*)malloc(sizeof(LinkList));
//创建链表(n个节点)
LinkListCreate(head,n);
//输出已建链表
LinkListPrintf(head);
//就地反转
LinkListRerverse(head);
//输出反转后结果
LinkListPrintf(head);
}
return 0;
}
分享到:
相关推荐
1、建立含有若干个元素的单链表; 2、对已建立的单链表实现查找、逆置和计算线性表长度等操作。 void main( ) { int r[100],n,i,x; cout请输入线性表中元素的个数!"; cin>>n; cout请输入线性表中每个元素!"; ...
实现单链表的基本操作:头插法建立单链表、尾插法建立单链表、查找指定位置上的元素值、查找指定元素的位置、插入若干元素、删除若干元素、合并两个单链表、求两个合集的差、求单链表长度、逆置单链表、访问单链表各...
1.若干城市的信息存入一个带头结点的单链表,结点中的城市信息包括城市名、城市的位置坐标。要求: (1)给定一个城市名,返回其位置坐标。 (2)给定一个位置坐标P和一个距离D,返回所有与P的距离小于等于D的城市。
将若干城市的信息存入一个带头结点的单链表, 结点中的城市信息包括城市名、城市的位置坐标 要求: (1)给定一个城市名,返回其位置坐标; (2)给定一个位置坐标P和一个距离D,返回所有 与P的距离小于等于D的城市。
创建单链表,加入三个学生的分数成绩,并遍历显示
本文章比较详细论述了单链表的用法,并且列举了详细的例子供参考!本文章比较详细论述了单链表的用法,并且列举了详细的例子供参考!
(1)通过终端或文件输入若干学生的班级号、学号、成绩,将每个班的数据分别保存在不同的单链表中,数据元素按成绩由高到低的顺序存放;然后分别按顺序(由高到低)输出各班的成绩表。 (2)输入班级、学号和成绩...
将若干城市的信息,存入一个带头结点的单链表。结点中的城市信息包括:城市名,城 市的位置坐标。要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。
(1)通过终端或文件输入若干学生的班级号、学号、成绩,将每个班的数据分别保存在不同的单链表中,数据元素按成绩由高到低的顺序存放;然后分别按顺序(由高到低)输出各班的成绩表。 (2)输入班级、学号和成绩...
编写程序完成单链表的下列基本操作: (1)初始化单链表La。 (2)在La中第i个元素之前插入一个新结点。 (3)删除La中的第i个元素结点。 (4)在La中查找某结点并返回其位置。 (5)打印输出La中的结点元素值。
输入一组数字,换行,输入要删除的元素,输出删除后的元素和元素个数。若输入字母,浮点型数据可判错。
(1).键盘输入一组元素,建立一个无头结点的单向链表(无序)。 (2).遍历(打印)单向链表。...判断算法1和算法5生成单链表所表示的集合是否相等。 (10).在主函数中设计一个简单的菜单,分别调试上述算法。
链表(linked list)是一种在物理上非连续,非顺序的数据结构,由若干节点(node)组成 单链表每一个节点又包含两部分,1是存放数据的变量data,2是存放指向下一个结点的指针next 双向链表每一个节点包含三部分,在...
本程序的目的是模拟实现一个简单的单链表操作的类,可以向其中添加若干字母(A-Z)作为其节点元素。 要求:使用字符用户界面。程序功能: 1. 可以随机选取若干个字母,添加到自制的单链表中。字母取值范围是[A,Z] 2. ...
数据结构中的线性表的若干操作,1、建立一个顺序方式存储的线性表向表中输入若干元素后进行以下操作 1向线性表的表头、表尾或合适位置插入元素 2对线性表按升序或降序输出 2、建立一个动态链接...
如数组的大小在定义时要事先规定,不能在程序中进行调整,这样一来,在程序设计中针对不同问题有时需要3 0个大小的数组,有时需要5 0个数组的大小,难于统一。我们只能够根据可能的最大需求来定义数组,常常会造成...
(1)建立含有若干个元素的带表头的单链表; 要求从键盘输入和文件读入两个多项式,显示并保存。 (2)设有一元多项式Am(x)和Bn(x). Am(x)=A0+A1x1+A2x2+A3x3+...+Amxm Bn(x)=B0+B1x1+B2x2+B3x3+...+Bnxn 请实现...
1.输入的形式和输入值的范围:在所有输入中,学生的姓名和学号都是字符串,成绩是整数。 2.输出的形式:建立顺序表后显示顺序表的内容,也可以随时手动查询顺序表的内容。 3.程序所能达到的功能:完成栈的建立、...
在数据结构中对线性表的基本增,删,改,查操作
C语言的12个实验,只要熟练掌握,C语言考试一定没有问题