SCAU华南农业大学数据结构oj 实验一
8576 顺序线性表的基本操作
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:
#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)
{
L.elem=new ElemType[LIST_INIT_SIZE];
if(!L.elem)
return(ERROR);
L.length=0;
L.listsize=LIST_INIT_SIZE;
return OK;
}
int Load_Sq(SqList &L)
{
// 输出顺序表中的所有元素
int i;
if(L.length==0) printf("The List is empty!"); // 请填空
else
{
printf("The List is: ");
for(i=0;i<L.length;i++) printf("%d ",L.elem[i]); // 请填空
}
printf("\n");
return OK;
}
int ListInsert_Sq(SqList &L,int i,int e)
{
if(i<1||i>L.length+1)
return ERROR;
if(L.length==LIST_INIT_SIZE)
return ERROR;
for(int j=L.length;j>=i;j--)
{
L.elem[j]=L.elem[j-1];
}
L.elem[i-1]=e;
++L.length;
return OK;
}
int ListDelete_Sq(SqList &L,int i, int &e)
{
if(i<1||i>L.length)
return ERROR;
e=L.elem[i-1];
for(int j=i-1;j<L.length-1;j++)
{
L.elem[j]=L.elem[j+1];
}
L.length--;
return e;
}
int main()
{
SqList T;
int a, i;
ElemType e, x;
if(InitList_Sq(T)) // 判断顺序表是否创建成功
{
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(ListInsert_Sq(T,i,x)==ERROR) printf("Insert Error!\n"); // 执行插入函数，根据返回值判断i值是否合法
else printf("The Element %d is Successfully Inserted!\n", x);
break;
case 2: scanf("%d",&i);
if(ListDelete_Sq(T,i,e)==ERROR) 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;
}
}
}
解析：这是一道基础的实现顺序线性表基本操作的题。
初始化顺序表先申请创建空间，初始化线性表长度（L.length）和线性表大小（L.listsize）。
输出顺序表则一个个遍历输出即可。
插入元素则先检查插入位置i的合理性以及插入后是否溢出，然后从后往前把元素后移直到插入位置。
删除操作则先检查插入位置i的合理性，然后从删除位置开始把元素前移。
8577 合并顺序表
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
提示
输出时注意大小写和标点。
#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 &A)
{
A.elem=new ElemType[LIST_INIT_SIZE];
if(!A.elem)
return(ERROR);
A.length=0;
A.listsize=LIST_INIT_SIZE;
return OK;
}
int pri_Sq(Sqlist &A)
{
int i;
for(i=0;i<A.length;i++)
{
printf("%d ",A.elem[i]);
}
printf("\n");
return OK;
}
int write_Sq(Sqlist &A)
{
int l;
scanf("%d",&l);
int m;
for(int i=0;i<l;i++)
{
scanf("%d",&m);
A.elem[i]=m;
A.length++;
}
return OK;
}
int hebing_Sq(Sqlist &A,Sqlist &B)
{
Sqlist C;
InitList_Sq(C);
int i,j,k;
i=0,j=0,k=0;
while(i<A.length&&j<B.length)
{
if(A.elem[i]<=B.elem[j])
{
C.elem[k]=A.elem[i];
k++;
i++;
C.length++;
}
else if(A.elem[i]>B.elem[j])
{
C.elem[k]=B.elem[j];
k++;
j++;
C.length++;
}
}
while(i<A.length)
{
C.elem[k++]=A.elem[i++];
C.length++;
}
while(j<B.length)
{
C.elem[k++]=B.elem[j++];
C.length++;
}
printf("List C:");
pri_Sq(C);
return OK;
}
int main()
{
Sqlist A,B;
InitList_Sq(A);
InitList_Sq(B);
write_Sq(A);
write_Sq(B);
printf("List A:");
pri_Sq(A);
printf("List B:");
pri_Sq(B);
hebing_Sq(A,B);
return 0;
}
解析：本体就是在上一题的基础上增加了合并顺序表的功能。合并的思路就是创建一个新的顺序表用来存放合并后的顺序表，之后就是利用指针i，j将两个需要合并的数组从小到大进行比较，小者利用指针k存入新数组。
8578 顺序表逆置
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
#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 &A)
{
A.elem=new ElemType[LIST_INIT_SIZE];
if(!A.elem)
return(ERROR);
A.length=0;
A.listsize=LIST_INIT_SIZE;
return OK;
}
int pri_Sq(Sqlist &A)
{
int i;
for(i=0;i<A.length;i++)
{
printf("%d ",A.elem[i]);
}
printf("\n");
return OK;
}
int write_Sq(Sqlist &A)
{
int l;
scanf("%d",&l);
int m;
for(int i=0;i<l;i++)
{
scanf("%d",&m);
A.elem[i]=m;
A.length++;
}
return OK;
}
int nizhi_Sq(Sqlist &A)
{
Sqlist B;
InitList_Sq(B);
int i,j;
for (i = A.length - 1, j = 0; i >= 0; i--, j++)
{
B.elem[j] = A.elem[i];
B.length++;
}
pri_Sq(B);
return OK;
}
int main()
{
Sqlist A;
InitList_Sq(A);
write_Sq(A);
printf("The List is:");
pri_Sq(A);
printf("The turned List is:");
nizhi_Sq(A);
}
解析：逆置的思路也很简单，就是新建立一个顺序表然后从后往前遍历原顺序表，再存入新顺序表
8579 链式线性表的基本操作
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:
#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;//将头指针L赋值给q，让q也指向头结点
for (i=0; i<n; i++)
{
scanf("%d", &e);
p = new LNode; // 生成新结点
p->data=e;// 将e赋值给p的数据域
p->next=NULL;//指针域指向空
q->next=p;//把q和p连起来
q=p;//q指向新的尾结点
}
return OK;
}
int LoadLink_L(LinkList &L)
{
// 单链表遍历
LinkList p = L->next;//p指向首元结点
if(!p)printf("The List is empty!"); //首元结点为空
else
{
printf("The LinkList is:");
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
}
printf("\n");
return OK;
}
int LinkInsert_L(LinkList &L,int i,ElemType e)
{
// 算法2.9
// 在带头结点的单链线性表L中第i个位置之前插入元素e
// 请补全代码
LinkList p=L;//p指向头结点
LinkList s;
int j=0;
while(p&&(j<i-1))//当p指向的结点不为空且计数器j<i-1,即定位到第i个位置前
{
p=p->next;
++j;
}
if(!p||(j>i-1))
return ERROR;
s=new LNode;//找到插入位置前一个结点后，创建新结点s
s->data=e;//e赋值给s的数据域
s->next=p->next;//把p的next赋值给s, 即把p后面一个结点与s链接起来，s和p同时指向p的后一个结点
p->next=s;//p的指针域指向s
return OK;
}
int LinkDelete_L(LinkList &L,int i, ElemType &e)
{
// 算法2.10
// 在带头结点的单链线性表L中，删除第i个元素，并用e返回其值
// 请补全代码
LinkList p=L,q;
LinkList s;
int j=0;
while(p->next&&(j<i-1))
{
p=p->next;
++j;
}
if(!(p->next)||(j>i-1))
return ERROR;
q=p->next;//p定位到要删除的元素的前一个，q定位到要删除的元素
e=q->data;//把要删除的结点的数据域保存到e中
p->next=q->next;//使p的指针域指向q的next ，即p,q,同时指向q的后一个结点
delete q;
return OK;
}
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(CreateLink_L(T,n)) // 判断链表是否创建成功，请填空
{
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(LinkInsert_L(T,i,x)==0) printf("Insert Error!\n"); // 判断i值是否合法，请填空
else printf("The Element %d is Successfully Inserted!\n", x);
break;
case 2:
scanf("%d",&i);
if(LinkDelete_L(T,i,e)==ERROR) 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;
}
}
}
8580 合并链表
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
#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;//将头指针L赋值给q，让q也指向头结点
for (i=0; i<n; i++)
{
scanf("%d", &e);
p = new LNode; // 生成新结点
p->data=e;// 将e赋值给p的数据域
p->next=NULL;//指针域指向空
q->next=p;//把q和p连起来
q=p;//q指向新的尾结点
}
return OK;
}
int LoadLink_L(LinkList &L)
{
// 单链表遍历
LinkList p = L->next;//p指向首元结点
if(!p)printf("The List is empty!"); //首元结点为空
else
{
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
}
printf("\n");
return OK;
}
int LinkInsert_L(LinkList &L,int i,ElemType e)
{
// 算法2.9
// 在带头结点的单链线性表L中第i个位置之前插入元素e
// 请补全代码
LinkList p=L;//p指向头结点
LinkList s;
int j=0;
while(p&&(j<i-1))//当p指向的结点不为空且计数器j<i-1,即定位到第i个位置前
{
p=p->next;
++j;
}
if(!p||(j>i-1))
return ERROR;
s=new LNode;//找到插入位置前一个结点后，创建新结点s
s->data=e;//e赋值给s的数据域
s->next=p->next;//把p的next赋值给s, 即把p后面一个结点与s链接起来，s和p同时指向p的后一个结点
p->next=s;//p的指针域指向s
return OK;
}
int LinkDelete_L(LinkList &L,int i, ElemType &e)
{
// 算法2.10
// 在带头结点的单链线性表L中，删除第i个元素，并用e返回其值
// 请补全代码
LinkList p=L,q;
LinkList s;
int j=0;
while(p->next&&(j<i-1))
{
p=p->next;
++j;
}
if(!(p->next)||(j>i-1))
return ERROR;
q=p->next;//p定位到要删除的元素的前一个，q定位到要删除的元素
e=q->data;//把要删除的结点的数据域保存到e中
p->next=q->next;//使p的指针域指向q的next ，即p,q,同时指向q的后一个结点
delete q;
return OK;
}
int hebing_L(LinkList &A,LinkList &B)
{
LinkList p = A->next, q = B->next;
LinkList C = (LinkList)malloc(sizeof(LNode));
if (C == NULL) return ERROR;
C->next = NULL;
LinkList r = C;
while (p != NULL && q != NULL) {
if (p->data <= q->data) {
r->next = (LinkList)malloc(sizeof(LNode));
if (r->next == NULL) return ERROR;
r->next->data = p->data;
p = p->next;
r = r->next;
} else {
r->next = (LinkList)malloc(sizeof(LNode));
if (r->next == NULL) return ERROR;
r->next->data = q->data;
q = q->next;
r = r->next;
}
}
while (p != NULL) {
r->next = (LinkList)malloc(sizeof(LNode));
if (r->next == NULL) return ERROR;
r->next->data = p->data;
p = p->next;
r = r->next;
}
while (q != NULL) {
r->next = (LinkList)malloc(sizeof(LNode));
if (r->next == NULL) return ERROR;
r->next->data = q->data;
q = q->next;
r = r->next;
}
r->next = NULL;
printf("List C:");
LoadLink_L(C);
return OK;
}
int main()
{
LinkList A, B;
int l1, l2;
scanf("%d", &l1);
CreateLink_L(A, l1);
scanf("%d", &l2);
CreateLink_L(B, l2);
printf("List A:");
LoadLink_L(A);
printf("List B:");
LoadLink_L(B);
hebing_L(A, B);
}
解析：跟合并顺序表思路一致，不解释，但是既然oj是黑盒测试为什么不用stl
#include<string>
#include<queue>
#include<vector>
using namespace std;
int main()
{
int m,n;
scanf("%d",&m);
vector<int> a(m);
for (int i = 0; i < a.size(); i++)
{
int x;
scanf("%d",&x);
a[i] = x;
}
scanf("%d",&n);
vector<int> b(n);
for (int i = 0; i < b.size(); i++)
{
int y;
scanf("%d",&y);
b[i] = y;
}
vector<int> c(m+n);
priority_queue<int> d;
int i=0;
for(i=0;i<a.size();i++)
{
c[i]=a[i];
}
for(int j=0;j<b.size();j++,i++)
{
c[i]=b[j];
}
for(int k=0;k<m+n;k++)
{
d.push(c[k]);
}
for(int k=0;k<m+n;k++)
{
c[k]=d.top();
d.pop();
}
printf("List A:");
for(int k=0;k<m;k++)
{
printf("%d ",a[k]);
}
printf("\n");
printf("List B:");
for(int k=0;k<n;k++)
{
printf("%d ",b[k]);
}
printf("\n");
printf("List C:");
for(int k=c.size()-1;k>=0;k--)
{
printf("%d ",c[k]);
}
}
19080 反转链表
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)
{
_______________________
}
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 <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 *p,*q,*r;
r=NULL;
p=L->next;
while(p!=NULL)
{
q=p->next;
p->next=r;
r=p;
p=q;
}
L->next=r;
}
int main()
{
int n;
LNode *L;
cin>>n;
createList(L,n);
reverseList(L);
trv(L);
return 0;
}
解析：
-
变量初始化：
p、q、r是三个辅助指针，用于遍历和操作链表。r初始化为NULL，作为反转后链表的尾部。 -
遍历链表：
p初始指向链表的第一个节点（L->next）。循环条件为p != NULL，确保遍历完所有节点。 -
指针操作：
q = p->next：保存当前节点p的下一个节点。p->next = r：将当前节点p的next指针指向前驱节点r，实现反转。r = p：r移动到当前节点p，作为下一次迭代的前驱节点。p = q：p移动到之前保存的下一个节点q，继续遍历。
-
头节点处理：
循环结束后，p为NULL，r指向原链表的最后一个节点（即反转后的第一个节点）。L->next = r：将头节点L的next指针指向新的头节点r，完成反转。
更多推荐
33
0- 0
已为社区贡献2条内容
所有评论(0)