devbox
空白诗007
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

2022SCAU数据结构题库汇总_8577 合并顺序表时间限制:1000ms 代码长度限制:10kb提交次数:5339 通过次数:22

作者：空白诗007 | 2024-06-27 07:14:51

赞

踩

8577 合并顺序表时间限制:1000ms 代码长度限制:10kb提交次数:5339 通过次数:2251

实验1.1

8576 顺序线性表的基本操作

时间限制:1000MS  代码长度限制:10KB
提交次数:9027 通过次数:2456

题型: 编程题   语言: G++;GCC

Description

 编写算法，创建初始化容量为LIST_INIT_SIZE的顺序表T，并实现插入、删除、遍历操作。本题目给出部分代码，请补全内容。

#include<stdio.h>
#include<malloc.h>
#define OK 1 
#define ERROR 0
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define ElemType int

typedef struct
{
	int *elem;
	int length;
	int listsize;
}SqList;

int InitList_Sq(SqList &L)
{
// 算法2.3，构造一个空的线性表L，该线性表预定义大小为LIST_INIT_SIZE
// 请补全代码

}

int Load_Sq(SqList &L)
{
// 输出顺序表中的所有元素
	int i;
	if(_________________________) printf("The List is empty!");  // 请填空
	else
	{
		printf("The List is: ");
		for(_________________________) printf("%d ",_________________________);  // 请填空
	}
	printf("\n");
	return OK;
}

int ListInsert_Sq(SqList &L,int i,int e)
{
// 算法2.4，在顺序线性表L中第i个位置之前插入新的元素e
// i的合法值为1≤i≤L.length +1
// 请补全代码

}

int ListDelete_Sq(SqList &L,int i, int &e)
{
// 算法2.5,在顺序线性表L中删除第i个位置的元素，并用e返回其值
// i的合法值为1≤i≤L.length
// 请补全代码

}

int main()
{
	SqList T;
	int a, i;
	ElemType e, x;
	if(_________________________)    // 判断顺序表是否创建成功
	{
		printf("A Sequence List Has Created.\n");
	}
	while(1)
	{
		printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n");
		scanf("%d",&a);
		switch(a)
		{
			case 1: scanf("%d%d",&i,&x);
					if(_________________________) printf("Insert Error!\n"); // 执行插入函数，根据返回值判断i值是否合法
					else printf("The Element %d is Successfully Inserted!\n", x); 
					break;
			case 2: scanf("%d",&i);
					if(_________________________) printf("Delete Error!\n"); // 执行删除函数，根据返回值判断i值是否合法
					else printf("The Element %d is Successfully Deleted!\n", e);
					break;
			case 3: Load_Sq(T);
					break;
			case 0: return 1;
		}
	}
}

输入格式

测试样例格式说明：
根据菜单操作：
1、输入1，表示要实现插入操作，紧跟着要输入插入的位置和元素，用空格分开
2、输入2，表示要实现删除操作，紧跟着要输入删除的位置
3、输入3，表示要输出顺序表的所有元素
4、输入0，表示程序结束

输入样例

1
1 2
1
1 3
2
1
3
0

输出样例

A Sequence List Has Created.
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:
The Element 2 is Successfully Inserted!
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:
The Element 3 is Successfully Inserted!
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:
The Element 3 is Successfully Deleted!
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:
The List is: 2 
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:

  1. #include<stdio.h>
  2. #include<malloc.h>
  3. #define OK 1
  4. #define ERROR 0
  5. #define LIST_INIT_SIZE 100
  6. #define LISTINCREMENT 10
  7. #define ElemType int
  8.  
  9. typedef struct
  10. {
  11. 	int *elem;
  12. 	int length;
  13. 	int listsize;
  14. }SqList;
  15.  
  16. int InitList_Sq(SqList &L)
  17. {
  18.     L.elem=new ElemType[LIST_INIT_SIZE];
  19.     if(!L.elem)return ERROR;
  20.     L.length=0;
  21.     return OK;
  22. // 算法2.3，构造一个空的线性表L，该线性表预定义大小为LIST_INIT_SIZE
  23. // 请补全代码
  24.  
  25. }
  26.  
  27. int Load_Sq(SqList &L)
  28. {
  29. // 输出顺序表中的所有元素
  30. 	int i;
  31. 	if(L.length==0) printf("The List is empty!");  // 请填空
  32. 	else
  33. 	{
  34. 		printf("The List is: ");
  35. 		for(i=0;i<L.length;i++) printf("%d ",L.elem[i]);  // 请填空
  36. 	}
  37. 	printf("\n");
  38. 	return OK;
  39. }
  40.  
  41. int ListInsert_Sq(SqList &L,int i,int e)
  42. {
  43.     if(i<1||i>L.length+1)return ERROR;
  44.     if(L.length==LIST_INIT_SIZE) return ERROR;
  45.     for(int j=L.length-1;j>=i-1;j--)
  46.     {
  47.         L.elem[j+1]=L.elem[j];
  48.     }
  49.     L.elem[i-1]=e;
  50.     L.length++;
  51.     return OK;
  52. // 算法2.4，在顺序线性表L中第i个位置之前插入新的元素e
  53. // i的合法值为1≤i≤L.length +1
  54. // 请补全代码
  55.  
  56. }
  57.  
  58. int ListDelete_Sq(SqList &L,int i, int &e)
  59. {
  60.     if(i<1||i>L.length)return ERROR;
  61.     e=L.elem[i-1];
  62.     for(int j=i;j<=L.length-1;j++)
  63.     {
  64.         L.elem[j-1]=L.elem[j];
  65.     }
  66.     L.length--;
  67.     return e;
  68. // 算法2.5,在顺序线性表L中删除第i个位置的元素，并用e返回其值
  69. // i的合法值为1≤i≤L.length
  70. // 请补全代码
  71.  
  72. }
  73.  
  74. int main()
  75. {
  76. 	SqList T;
  77. 	int a, i;
  78. 	ElemType e, x;
  79. 	if(InitList_Sq(T))    // 判断顺序表是否创建成功
  80. 	{
  81. 		printf("A Sequence List Has Created.\n");
  82. 	}
  83. 	while(1)
  84. 	{
  85. 		printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n");
  86. 		scanf("%d",&a);
  87. 		switch(a)
  88. 		{
  89. 			case 1: scanf("%d%d",&i,&x);
  90. 					if(ListInsert_Sq(T,i,x)==ERROR) printf("Insert Error!\n"); // 执行插入函数，根据返回值判断i值是否合法
  91. 					else printf("The Element %d is Successfully Inserted!\n", x);
  92. 					break;
  93. 			case 2: scanf("%d",&i);
  94. 					if(ListDelete_Sq(T,i,e)==ERROR) printf("Delete Error!\n"); // 执行删除函数，根据返回值判断i值是否合法
  95. 					else printf("The Element %d is Successfully Deleted!\n", e);
  96. 					break;
  97. 			case 3: Load_Sq(T);
  98. 					break;
  99. 			case 0: return 1;
  100. 		}
  101. 	}
  102. }

实验1.2

8577 合并顺序表

时间限制:1000MS  代码长度限制:10KB
提交次数:5339 通过次数:2251

题型: 编程题   语言: G++

Description

若线性表中数据元素相互之间可以比较，且数据元素在表中按值递增或递减，则称该表为有序表。

编写算法，将两个非递减有序顺序表A和B合并成一个新的非递减有序顺序表C。

输入格式

第一行：顺序表A的元素个数
第二行：顺序表A的各元素（非递减），用空格分开
第三行：顺序表B的元素个数
第四行：顺序表B的各元素（非递减），用空格分开

输出格式

第一行：顺序表A的元素列表
第二行：顺序表B的元素列表
第三行：合并后顺序表C的元素列表

输入样例

5
1 3 5 7 9
5
2 4 6 8 10

输出样例

List A:1 3 5 7 9 
List B:2 4 6 8 10 
List C:1 2 3 4 5 6 7 8 9 10

提示

输出时注意大小写和标点。
  1. #include <iostream>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5.  
  6. int main()
  7. {
  8.     int a[105]={0},i,len1=0,len2=0;
  9.     cin>>len1;              //输入两个顺序表
  10.     for(i=1;i<=len1;i++)
  11.         cin>>a[i];
  12.     cin>>len2;
  13.     for(i=len1+1;i<=len1+len2;i++)//len1+len2就是a数组的总长度
  14.         cin>>a[i];
  15.  
  16.     cout<<"List A:";        //输出两个顺序表
  17.     for(i=1;i<=len1;i++)
  18.         cout<<a[i]<<" ";
  19.     cout<<endl;
  20.     cout<<"List B:";
  21.     for(i=len1+1;i<=len1+len2;i++)
  22.         cout<<a[i]<<" ";
  23.     cout<<endl;
  24.  
  25.     sort(a+1,a+1+len1+len2);
  26.     cout<<"List C:";
  27.     for(i=1;i<=len1+len2;i++)
  28.         printf("%d ",a[i]);
  29.     return 0;
  30. }

实验1.3

8578 顺序表逆置

时间限制:1000MS  代码长度限制:10KB
提交次数:3660 通过次数:2149

题型: 编程题   语言: G++;GCC

Description

顺序表的基本操作代码如下：
#include<stdio.h>
#include<malloc.h>
#define OK 1
#define ERROR 0
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define ElemType int

typedef int Status;
typedef struct
{
    int *elem;
    int length;
    int listsize;
}SqList;

Status InitList_Sq(SqList &L) 
{  // 算法2.3
  // 构造一个空的线性表L。
  L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
  if (!L.elem) return OK;        // 存储分配失败
  L.length = 0;                  // 空表长度为0
  L.listsize = LIST_INIT_SIZE;   // 初始存储容量
  return OK;
} // InitList_Sq

Status ListInsert_Sq(SqList &L, int i, ElemType e) 
{  // 算法2.4
  // 在顺序线性表L的第i个元素之前插入新的元素e，
  // i的合法值为1≤i≤ListLength_Sq(L)+1
  ElemType *p;
  if (i < 1 || i > L.length+1) return ERROR;  // i值不合法
  if (L.length >= L.listsize) {   // 当前存储空间已满，增加容量
    ElemType *newbase = (ElemType *)realloc(L.elem,
                  (L.listsize+LISTINCREMENT)*sizeof (ElemType));
    if (!newbase) return ERROR;   // 存储分配失败
    L.elem = newbase;             // 新基址
    L.listsize += LISTINCREMENT;  // 增加存储容量
  }
  ElemType *q = &(L.elem[i-1]);   // q为插入位置
  for (p = &(L.elem[L.length-1]); p>=q; --p) *(p+1) = *p;
                                  // 插入位置及之后的元素右移
  *q = e;       // 插入e
  ++L.length;   // 表长增1
  return OK;
} // ListInsert_Sq

Status ListDelete_Sq(SqList &L, int i, ElemType &e) 
{  // 算法2.5
  // 在顺序线性表L中删除第i个元素，并用e返回其值。
  // i的合法值为1≤i≤ListLength_Sq(L)。
  ElemType *p, *q;
  if (i<1 || i>L.length) return ERROR;  // i值不合法
  p = &(L.elem[i-1]);                   // p为被删除元素的位置
  e = *p;                               // 被删除元素的值赋给e
  q = L.elem+L.length-1;                // 表尾元素的位置
  for (++p; p<=q; ++p) *(p-1) = *p;     // 被删除元素之后的元素左移
  --L.length;                           // 表长减1
  return OK;
} // ListDelete_Sq

设有一顺序表A=（a0,a1,..., ai,...an-1)，其逆顺序表定义为A'=( an-1,..., ai,...,a1, a0)。设计一个算法，将顺序表逆置，要求顺序表仍占用原顺序表的空间。



 

输入格式

第一行：输入顺序表的元素个数
第二行：输入顺序表的各元素，用空格分开


 

输出格式

第一行：逆置前的顺序表元素列表
第二行：逆置后的顺序表元素列表


 

输入样例

10
1 2 3 4 5 6 7 8 9 10


 

输出样例

The List is:1 2 3 4 5 6 7 8 9 10 
The turned List is:10 9 8 7 6 5 4 3 2 1
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. int main()
  4. {
  5.     int i,t,n;
  6.     scanf("%d",&n);
  7.     int a[n];
  8.     for(i=1;i<=n;i++)
  9.     {
  10.     scanf("%d",&a[i]);
  11.     }
  12.     printf("The List is:");
  13.     for(i=1;i<=n;i++)
  14.     {
  15.     printf("%d ",a[i]);
  16.     }
  17.     printf("\n");
  18.     printf("The turned List is:");
  19.     for(i=n;i>=1;i--)
  20.     {
  21.      printf("%d ",a[i]);
  22.     }
  23.     return 0;
  24. }

实验1.4

8579 链式线性表的基本操作

时间限制:1000MS  代码长度限制:10KB
提交次数:5567 通过次数:2176

题型: 编程题   语言: G++;GCC

Description

 编写算法，创建一个含有n个元素的带头结点的单链表L并实现插入、删除、遍历操作。本题目提供部分代码，请补全内容。

#include<stdio.h>
#include<malloc.h>
#define ERROR 0
#define OK 1 
#define ElemType int

typedef struct LNode
{
 int data;
 struct LNode *next;
}LNode,*LinkList;

int CreateLink_L(LinkList &L,int n){
// 创建含有n个元素的单链表
  LinkList p,q;
  int i;
  ElemType e;
  L = new LNode;
  L->next = NULL;              // 先建立一个带头结点的单链表
  q = L;
  for (i=0; i<n; i++) {
    scanf("%d", &e);
    p = new LNode;  // 生成新结点
    // 请补全代码

  }
  return OK;
}

int LoadLink_L(LinkList &L){
// 单链表遍历
 LinkList p = L->next;
 if(___________________________)printf("The List is empty!"); // 请填空
 else
 {
	 printf("The LinkList is:");
	 while(___________________________)    // 请填空
	 {
		printf("%d ",p->data); 
		___________________________    // 请填空
	 }
 }
 printf("\n");
 return OK;
}

int LinkInsert_L(LinkList &L,int i,ElemType e){
// 算法2.9
// 在带头结点的单链线性表L中第i个位置之前插入元素e
// 请补全代码

}

int LinkDelete_L(LinkList &L,int i, ElemType &e){
// 算法2.10
// 在带头结点的单链线性表L中，删除第i个元素，并用e返回其值
// 请补全代码

}

int main()
{
 LinkList T;
 int a,n,i;
 ElemType x, e;
 printf("Please input the init size of the linklist:\n");
 scanf("%d",&n);
 printf("Please input the %d element of the linklist:\n", n);
 if(___________________________)     // 判断链表是否创建成功，请填空
 {
	 printf("A Link List Has Created.\n");
	 LoadLink_L(T);
 }
 while(1)
	{
		printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n");
		scanf("%d",&a);
		switch(a)
		{
			case 1: scanf("%d%d",&i,&x);
				  if(___________________________) printf("Insert Error!\n"); // 判断i值是否合法，请填空
				  else printf("The Element %d is Successfully Inserted!\n", x); 
				  break;
			case 2: scanf("%d",&i);
				  if(___________________________) printf("Delete Error!\n"); // 判断i值是否合法，请填空
				  else printf("The Element %d is Successfully Deleted!\n", e);
				  break;
			case 3: LoadLink_L(T);
				  break;
			case 0: return 1;
		}
	}
}



 

输入格式

测试样例格式说明：
根据菜单操作：
1、输入1，表示要实现插入操作，紧跟着要输入插入的位置和元素，用空格分开
2、输入2，表示要实现删除操作，紧跟着要输入删除的位置
3、输入3，表示要输出顺序表的所有元素
4、输入0，表示程序结束


 

输入样例

3
3 6 9
3
1
4 12
2
1
3
0


 

输出样例

Please input the init size of the linklist:
Please input the 3 element of the linklist:
A Link List Has Created.
The LinkList is:3 6 9 
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:
The LinkList is:3 6 9 
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:
The Element 12 is Successfully Inserted!
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:
The Element 3 is Successfully Deleted!
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:
The LinkList is:6 9 12 
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:

  1. #include<stdio.h>
  2. #include<malloc.h>
  3. #define ERROR 0
  4. #define OK 1
  5. #define ElemType int
  6.  
  7. typedef struct LNode
  8. {
  9.  int data;
  10.  struct LNode *next;
  11. }LNode,*LinkList;
  12.  
  13. int CreateLink_L(LinkList &L,int n){
  14. // 创建含有n个元素的单链表
  15.   LinkList p,q;
  16.   int i;
  17.   ElemType e;
  18.   L = new LNode;
  19.   L->next = NULL;
  20.   q= new LNode;             // 先建立一个带头结点的单链表
  21.   q = L;
  22.   for (i=0; i<n; i++) {
  23.     scanf("%d", &e);
  24.     p = new LNode;  // 生成新结点
  25.     p->data=e;
  26.     p->next=NULL;
  27.     q->next=p;
  28.     q=p;
  29.   }
  30.   return OK;
  31. }
  32.  
  33. int LoadLink_L(LinkList &L){
  34. // 单链表遍历
  35.  LinkList p = L->next;
  36.  if(!p) printf("The List is empty!"); // 请填空
  37.  else
  38.  {
  39. 	 printf("The LinkList is:");
  40. 	 while(p)    // 请填空
  41. 	 {
  42. 		printf("%d ",p->data);
  43. 		p=p->next;    // 请填空
  44. 	 }
  45.  }
  46.  printf("\n");
  47.  return OK;
  48. }
  49.  
  50. int LinkInsert_L(LinkList &L,int i,ElemType e){
  51.    int j;
  52.    LNode *p,*s;
  53.    p=L;///这句话不要忘记
  54.    j=0;
  55.    while(p&&(j<i-1))///这里是i-1，因为是在i前面插入
  56.    {
  57.        p=p->next;
  58.        j++;
  59.    }
  60.    if(!p||j>i-1)
  61.    return ERROR;
  62.    s=new LNode;///这句话也不要忘了
  63.    s->data=e;
  64.    s->next=p->next;
  65.    p->next=s;
  66.    return OK;
  67. }
  68.  
  69. int LinkDelete_L(LinkList &L,int i, ElemType &e){
  70. // 算法2.10
  71. // 在带头结点的单链线性表L中，删除第i个元素，并用e返回其值
  72.    int j;LNode *p,*q;
  73.    p=L;j=0;
  74.    while((p->next)&&(j<i-1))///这里是p->next，不能到尽头，要不然没东西删了，同样是i-1
  75.    {
  76.        p=p->next;
  77.        j++;
  78.    }
  79.    if(!(p->next)||(j>i-1))///不能到尽头，要不然没东西删了
  80.       return ERROR;
  81.     q=p->next;
  82.     p->next=q->next;
  83.     e=q->data;
  84.     delete q;
  85.     return OK;
  86. }
  87.  
  88. int main()
  89. {
  90.  LinkList T;
  91.  int a,n,i;
  92.  ElemType x, e;
  93.  printf("Please input the init size of the linklist:\n");
  94.  scanf("%d",&n);
  95.  printf("Please input the %d element of the linklist:\n", n);
  96.  if(CreateLink_L(T,n))// 判断链表是否创建成功，请填空
  97.  {
  98. 	 printf("A Link List Has Created.\n");
  99. 	 LoadLink_L(T);
  100.  }
  101.  while(1)
  102. 	{
  103. 		printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n");
  104. 		scanf("%d",&a);
  105. 		switch(a)
  106. 		{
  107. 			case 1: scanf("%d%d",&i,&x);
  108. 				  if(LinkInsert_L(T,i,x)==ERROR) printf("Insert Error!\n"); // 判断i值是否合法，请填空
  109. 				  else printf("The Element %d is Successfully Inserted!\n", x);
  110. 				  break;
  111. 			case 2: scanf("%d",&i);
  112. 				  if(LinkDelete_L(T,i,e)==ERROR) printf("Delete Error!\n"); // 判断i值是否合法，请填空
  113. 				  else printf("The Element %d is Successfully Deleted!\n", e);
  114. 				  break;
  115. 			case 3: LoadLink_L(T);
  116. 				  break;
  117. 			case 0: return 1;
  118. 		}
  119. 	}
  120. }

实验1.5

8580 合并链表

时间限制:1000MS  代码长度限制:10KB
提交次数:3724 通过次数:2077

题型: 编程题   语言: G++;GCC

Description

线性链表的基本操作如下：
#include<stdio.h>
#include<malloc.h>
#define ERROR 0
#define OK 1 
#define ElemType int

typedef int Status;
typedef struct LNode
{
 int data;
 struct LNode *next;
}LNode,*LinkList;


Status ListInsert_L(LinkList &L, int i, ElemType e) {  // 算法2.9
  // 在带头结点的单链线性表L的第i个元素之前插入元素e
  LinkList p,s;
  p = L;   
  int j = 0;
  while (p && j < i-1) {  // 寻找第i-1个结点
    p = p->next;
    ++j;
  } 
  if (!p || j > i-1) return ERROR;      // i小于1或者大于表长
  s = (LinkList)malloc(sizeof(LNode));  // 生成新结点
  s->data = e;  s->next = p->next;      // 插入L中
  p->next = s;
  return OK;
} // LinstInsert_L

Status ListDelete_L(LinkList &L, int i, ElemType &e) {  // 算法2.10
  // 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
  LinkList p,q;
  p = L;
  int j = 0;
  while (p->next && j < i-1) {  // 寻找第i个结点，并令p指向其前趋
    p = p->next;
    ++j;
  }
  if (!(p->next) || j > i-1) return ERROR;  // 删除位置不合理
  q = p->next;
  p->next = q->next;           // 删除并释放结点
  e = q->data;
  free(q);
  return OK;
} // ListDelete_L

设计一个算法将两个非递减有序链表A和B合并成一个新的非递减有序链表C。



 

输入格式

第一行：单链表A的元素个数
第二行：单链表A的各元素（非递减），用空格分开
第三行：单链表B的元素个数
第四行：单链表B的各元素（非递减），用空格分开


 

输出格式

第一行：单链表A的元素列表
第二行：单链表B的元素列表
第三行：合并后单链表C的元素列表


 

输入样例

6
12 24 45 62 84 96
4
15 31 75 86


 

输出样例

List A:12 24 45 62 84 96 
List B:15 31 75 86 
List C:12 15 24 31 45 62 75 84 86 96
  1. #include <iostream>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5.  
  6. int main()
  7. {
  8.     int a[105]={0},i,len1=0,len2=0;
  9.     cin>>len1;              //输入两个顺序表
  10.     for(i=1;i<=len1;i++)
  11.         cin>>a[i];
  12.     cin>>len2;
  13.     for(i=len1+1;i<=len1+len2;i++)//len1+len2就是a数组的总长度
  14.         cin>>a[i];
  15.  
  16.     cout<<"List A:";        //输出两个顺序表
  17.     for(i=1;i<=len1;i++)
  18.         cout<<a[i]<<" ";
  19.     cout<<endl;
  20.     cout<<"List B:";
  21.     for(i=len1+1;i<=len1+len2;i++)
  22.         cout<<a[i]<<" ";
  23.     cout<<endl;
  24.  
  25.     sort(a+1,a+1+len1+len2);
  26.     cout<<"List C:";
  27.     for(i=1;i<=len1+len2;i++)
  28.         printf("%d ",a[i]);
  29.     return 0;
  30. }

实验1.6

19080 反转链表

时间限制:1000MS  代码长度限制:10KB
提交次数:0 通过次数:0

题型: 填空题   语言: 不限定

Description

一道经典的题目

给定一个单链表的头结点L，长度为n，反转该链表后，返回新链表的表头。

要求：空间复杂度 O(1) ，时间复杂度 O(n)。

如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。


#include <iostream>//C++
using namespace std;
struct LNode
{
    int data;
    LNode * next;
};
void createList(LNode * &L,int n)
{
    /**< 尾插法创建单链表 */
    LNode *r, *p;
    r=L=new LNode;/**< 创建头结点 */
    L->next=NULL;
    for(int i=1; i<=n; i++)
    {
        p=new LNode;
        cin>>p->data;
        p->next=NULL;
        r->next=p;
        r=p;
    }
}
void trv(LNode * L)
{
    /**< 一个简单的链表遍历函数，供编程过程中测试使用 */
    L=L->next;
    while(L)
    {
        cout<<L->data<<' ';
        L=L->next;
    }
}
void reverseList(LNode * &L) 
{
    LNode *pre = NULL;/**< 用三个指针分别表示前驱，当前，后继 */
    LNode *cur = L->next;/**< 当前是第一个节点a1 */
    LNode *nex = NULL; /**<思考如何用这三个指针实现翻转，另外，三个指针也要同步后移 */
    while (cur)
    {
        _______________________
    }
    L->next=pre;
}
int main()
{
    int n;
    LNode *L;
    cin>>n;
    createList(L,n);
    reverseList(L);
    trv(L);
    return 0;
}

 

输入格式

第一行一个整数n，代表链表长度。
第二行n个整数。


 

输出格式

输出逆置后的单链表。


 

输入样例

5
1 2 3 4 5


 

输出样例

5 4 3 2 1
#include &l
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/空白诗007/article/detail/761683?site
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号