实验课：链表实验

50 阅读 0 评论 33 点赞

我是靠谱客的博主难过大象，最近开发中收集的这篇文章主要介绍实验课：链表实验，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

2020/03/27
PTA练习

一、判断题

在这里插入图片描述

二、单选题

在这里插入图片描述

三、填空题

在这里插入图片描述

三、函数题

1、求单链表的表长 (10分)

本题要求实现一个函数，求带头结点的单链表的表长。

函数接口定义：

int Length ( LinkList L );

其中LinkList结构定义如下：

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

L是带头结点的单链表的头指针，函数Length返回单链表的长度。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

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

LinkList Create();/* 细节在此不表 */

int Length ( LinkList L );

int main()
{
    LinkList L = Create();
    printf("%dn", Length(L));
    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：

2 1 4 5 3 -1

输出样例：

5

int Length ( LinkList L ){
    LinkList p=L->next;
    int n=0;
    while(p){
        n++;
        p=p->next;
    }
    return n;
}

2、带头结点的单链表插入操作 (10分)

本题要求实现带头结点的单链表插入操作，插入成功返回1，否则返回0。

函数接口定义：

int insert_link ( LinkList L,int i,ElemType e);

L是单链表的头指针，i为插入位置，e是插入的数据元素，插入成功返回1，否则返回0。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

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

LinkList Create();/* 细节在此不表 */
void print( LinkList L);
int insert_link ( LinkList L,int i,ElemType e);

int main()
{
	int position,insert_data;int flag;
	LinkList L = Create();
	scanf("%d",&position);
	scanf("%d",&insert_data);	
	flag=insert_link(L,position,insert_data);
	if(flag) 
	{
		print(L);
	}
	else 
	{ 
		printf("Wrong Position for Insertion");
	}
	return 0;
}
void print(LinkList L)
{ 
	LinkList p;
	p=L->next;
	while (p)
	{
	     printf("%d ", p->data);
 	     p =p->next;
	}
}
/* 请在这里填写答案 */

输入格式：
输入数据为三行，第一行是若干正整数，最后以-1表示结尾（-1不算在序列内，不要处理）。所有数据之间用空格分隔。第二行数据是插入位置，第三行数据是被插入元素值。

输入样例：

1 2 3 4 5 6 -1
2
100

输出样例：

1 100 2 3 4 5 6

int insert_link ( LinkList L,int i,ElemType e){
    LinkList p=L;
    LinkList s;
    int j=0;
    while(p&&j<i-1){
        p=p->next;j++;
    }
    if(!p||j>i-1) return 0;
    s=(LinkList)malloc(sizeof(struct LNode));
    s->data=e;
    
    s->next=p->next;
    p->next=s;
    return 1;
}

3、带头结点的单链表删除操作 (10分)

本题要求实现删除单链表的第i个元素结点，删除成功返回1，否则返回0。

函数接口定义：

int delete_link ( LinkList L,int i);

L为单链表的头指针，i为删除结点的序号

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

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

LinkList Create();/* 细节在此不表 */
void print( LinkList L);
int delete_link ( LinkList L,int i);

int main()
{
	
	LinkList L = Create();
	int position;int flag;
	scanf("%d",&position);
	flag=delete_link(L,position);
	if(flag) 
	{
		print(L);
	}
	else 
	{ 
		printf("Wrong Position for Deletion");
	}
	return 0;
}
void print(LinkList L)
{ 
		LinkList p;
		p=L->next;
	while (p)
	{
		printf("%d ", p->data);
		p =p->next;
	}
}

/* 请在这里填写答案 */

输入格式：
输入数据为两行，第一行是若干正整数，最后以-1表示结尾（-1不算在序列内，不要处理）。所有数据之间用空格分隔。第二行数据是删除位置。

输入样例：

1 2 3 4 5 6 -1
3

输出样例：

1 2 4 5 6

int delete_link ( LinkList L,int i){
    LinkList p,q;
    p=L;
    int j=0;
    while(p->next && j<i-1){
        p=p->next; j++;
    }
    if(!(p->next)||(j>i-1)) return 0;
    q=p->next;
    p->next=q->next;
    free(q);
    return 1;


}

4、求单链表元素序号 (10分)

本题要求实现一个函数，求带头结点的单链表中元素序号。

函数接口定义：

int Locate ( LinkList L, ElemType e);

L是带头结点的单链表的头指针，e是要查找的元素值。如果e在单链表中存在，函数Locate返回其序号（序号从1开始）；否则，返回0。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

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

LinkList Create();/* 细节在此不表 */

int Locate ( LinkList L, ElemType e);

int main()
{
	ElemType e;
	LinkList L = Create();
	scanf("%d",&e);
	printf("%dn", Locate(L,e));
	return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：

2 1 4 5 3 -1

5

输出样例：

4

int Locate ( LinkList L, ElemType e){
    LinkList p=L->next;
    int i=1;
    if(p==NULL) return 0;
    while((p->next!=NULL)&&p&&(p->data!=e)){
        p=p->next;
        i++;
    } 
    if(p->data==e) return i;
    else return 0;
    

}

5、带头结点的单链表就地逆置 (10分)

本题要求编写函数实现带头结点的单链线性表的就地逆置操作函数。L是一个带头结点的单链表，函数ListReverse_L(LinkList
&L)要求在不新开辟节点的前提下将单链表中的元素进行逆置，如原单链表元素依次为1,2,3,4，则逆置后为4,3,2,1。

函数接口定义：

void ListReverse_L(LinkList &L);

其中 L 是一个带头结点的单链表。

裁判测试程序样例：

//库函数头文件包含
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

//函数状态码定义
#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE -1
#define OVERFLOW   -2

typedef int  Status;
typedef int  ElemType; //假设线性表中的元素均为整型

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

Status ListCreate_L(LinkList &L,int n)
{
    LNode *rearPtr,*curPtr;   //一个尾指针，一个指向新节点的指针
    L=(LNode*)malloc(sizeof (LNode));
    if(!L)exit(OVERFLOW);
    L->next=NULL;               //先建立一个带头结点的单链表
    rearPtr=L;  //初始时头结点为尾节点,rearPtr指向尾巴节点
    for (int i=1;i<=n;i++){  //每次循环都开辟一个新节点，并把新节点拼到尾节点后
        curPtr=(LNode*)malloc(sizeof(LNode));//生成新结点
        if(!curPtr)exit(OVERFLOW);
        scanf("%d",&curPtr->data);//输入元素值
        curPtr->next=NULL;  //最后一个节点的next赋空
        rearPtr->next=curPtr;
        rearPtr=curPtr;
    }
    return OK;
}
void ListReverse_L(LinkList &L);
void ListPrint_L(LinkList &L){
//输出单链表
    LNode *p=L->next;  //p指向第一个元素结点
    while(p!=NULL)
    {
          if(p->next!=NULL)
               printf("%d ",p->data);
          else
               printf("%d",p->data);
          p=p->next;
    }
}
int main()
{
    LinkList L;
    int n;
    scanf("%d",&n);
    if(ListCreate_L(L,n)!= OK) {
          printf("表创建失败！！！n");
          return -1;
    }
    ListReverse_L(L);
    ListPrint_L(L);
    return 0;
}
/* 请在这里填写答案 */

输入格式：

第一行输入一个整数n，表示单链表中元素个数，接下来一行共n个整数，中间用空格隔开。

输出格式：

输出逆置后顺序表的各个元素，两个元素之间用空格隔开，最后一个元素后面没有空格。

输入样例：

4

1 2 3 4

输出样例：

4 3 2 1

void ListReverse_L(LinkList &L)
{
    LinkList p,q;
    p = L->next;
    L->next = NULL;
    while(p)
    {
        q = p;
        p = p->next;
        q->next = L->next;
        L->next = q;
    }
}

6、带头结点的链式表操作集 (10分)

本题要求实现带头结点的链式表操作集。

函数接口定义：

List MakeEmpty(); 
Position Find( List L, ElementType X );
bool Insert( List L, ElementType X, Position P );
bool Delete( List L, Position P );

      
    
其中List结构定义如下：

typedef struct LNode *PtrToLNode;
struct LNode {
    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;

各个操作函数的定义为：

List MakeEmpty()：创建并返回一个空的线性表；

Position Find( List L, ElementType X )：返回线性表中X的位置。若找不到则返回ERROR；

bool Insert( List L, ElementType X, Position P )：将X插入在位置P指向的结点之前，返回true。如果参数P指向非法位置，则打印“Wrong Position for Insertion”，返回false；

bool Delete( List L, Position P )：将位置P的元素删除并返回true。若参数P指向非法位置，则打印“Wrong Position for Deletion”并返回false。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

#define ERROR NULL
typedef enum {false, true} bool;
typedef int ElementType;
typedef struct LNode *PtrToLNode;
struct LNode {
    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;

List MakeEmpty(); 
Position Find( List L, ElementType X );
bool Insert( List L, ElementType X, Position P );
bool Delete( List L, Position P );

int main()
{
    List L;
    ElementType X;
    Position P;
    int N;
    bool flag;

    L = MakeEmpty();
    scanf("%d", &N);
    while ( N-- ) {
        scanf("%d", &X);
        flag = Insert(L, X, L->Next);
        if ( flag==false ) printf("Wrong Answern");
    }
    scanf("%d", &N);
    while ( N-- ) {
        scanf("%d", &X);
        P = Find(L, X);
        if ( P == ERROR )
            printf("Finding Error: %d is not in.n", X);
        else {
            flag = Delete(L, P);
            printf("%d is found and deleted.n", X);
            if ( flag==false )
                printf("Wrong Answer.n");
        }
    }
    flag = Insert(L, X, NULL);
    if ( flag==false ) printf("Wrong Answern");
    else
        printf("%d is inserted as the last element.n", X);
    P = (Position)malloc(sizeof(struct LNode));
    flag = Insert(L, X, P);
    if ( flag==true ) printf("Wrong Answern");
    flag = Delete(L, P);
    if ( flag==true ) printf("Wrong Answern");
    for ( P=L->Next; P; P = P->Next ) printf("%d ", P->Data);
    return 0;
}
/* 你的代码将被嵌在这里 */

输入样例：

6

12 2 4 87 10 2

4

2 12 87 5

输出样例：

2 is found and deleted.

12 is found and deleted.

87 is found and deleted.
Finding Error: 5 is not in.
5 is inserted as the last element.
Wrong Position for Insertion
Wrong Position for Deletion
10 4 2 5

List MakeEmpty()
{
	List head=(List)malloc(sizeof(struct LNode));
	head->Data=0;
	head->Next=NULL;
	return head;
}
Position Find( List L, ElementType X )
{
	List existL=L;
	while(existL)
	{
		if(existL->Data==X)
			return existL;
		existL=existL->Next;	
	}
	return ERROR;
}
bool Insert( List L, ElementType X, Position P )
{
	List temp;
	List pre;
	for(pre=L;pre&&pre->Next!=P;pre=pre->Next);
	if(pre!=NULL)
	{
		temp=(List)malloc(sizeof(struct LNode));
		temp->Next=pre->Next;
		pre->Next=temp;
		temp->Data=X;
		return true;
	}
	else
	{
		printf("Wrong Position for Insertionn");
		return false;
	}
	
	
}
bool Delete( List L, Position P )
{
	List pre;
	for(pre=L;pre&&pre->Next!=P;pre=pre->Next);
	if(pre==NULL || P==NULL)
	{
		printf("Wrong Position for Deletionn");
		return false;
	}
	else
	{
		pre->Next=P->Next;
		free(P);
		return true;
	 } 
	
}

四、编程题

1、两个有序链表序列的合并 (17分)

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。

输入格式:

输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。

输出格式:

在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

输入样例:

1 3 5 -1
2 4 6 8 10 -1

输出样例:

1 2 3 4 5 6 8 10

#include<stdio.h>
typedef struct LNode{
    int data;
    struct LNode *next;

}LNode,*LinkList;
LinkList creat_list();
LinkList hb(LinkList L1,LinkList L2);
void print(LinkList L);
int main()
{
    LinkList L1=creat_list();
    LinkList L2=creat_list();
    LinkList L;
    L=hb(L1,L2);
    print(L);
    
    return 0;
}
LinkList creat_list()//尾插法建表，带有头结点
{
    LinkList L=(LinkList)malloc(sizeof(struct LNode));
    L->next=NULL;
    int e;
    scanf("%d",&e);
    LinkList r=L;
    while(e!=-1)
    {
        LinkList s=(LinkList)malloc(sizeof(struct LNode));
        s->next=NULL;
        s->data=e;
        s->next=r->next;
        r->next=s;
        r=s;
        scanf("%d",&e);
    }
    return L;
}
LinkList hb(LinkList L1,LinkList L2)
{
	
	LinkList r,L;
	r=L=L1;//直接利用L1的头结点，不用另开空间了，最后释放L2的头结点，这里没有释放也对了
    LinkList p1=L1->next,p2=L2->next;
    while(p1&&p2)
    {
    if(p1->data<=p2->data)
    {
       r->next=p1;
	   r=p1; 
	   p1=p1->next;
    }
    else
    {
        r->next=p2;
	   r=p2; 
	   p2=p2->next;
    }
    }
    r->next=p1?p1:p2;//剩余的不用动，直接接上。
	return L->next;//返回首元，直接打印
}

void print(LinkList L)//注意打印时的格式，设置一个标识符
{
    if(!L) printf("NULL");
	int flag=0;
	LinkList p=L;
	while(p)
	{
		if(flag!=0) printf(" "); 
		printf("%d",p->data);
		p=p->next;
		flag=1;
	}
}

2、单链表的创建及遍历 (17分)

读入n值及n个整数，建立单链表并遍历输出。

输入格式:

读入n及n个整数。

输出格式:

输出n个整数，以空格分隔（最后一个数的后面没有空格）。

输入样例:

在这里给出一组输入。例如：
2
10 5

输出样例:

在这里给出相应的输出。例如：
10 5

#include<stdio.h>
#include<malloc.h>
typedef struct node
{
	int data;
	struct node *next;
}LinkListNode;
int main()
{
	int n,i;
	scanf("%d",&n);
	LinkListNode *head,*p,*node;
	if(n == 0)
	{
		return 0;
	}
	node = (LinkListNode*)malloc(sizeof(LinkListNode));
	scanf("%d",&(node->data));
	node->next = NULL;
	p = head = node;
	for(i = 0;i<n-1;i++)
	{
		node = (LinkListNode*)malloc(sizeof(LinkListNode));
		scanf("%d",&(node->data));
		p->next = node;
		p = node;	
	}
	p = head;
	for(i = 0;i<n-1;i++)
	{
		printf("%d ",p->data);
		p = p->next;
	}
	printf("%d",p->data);
	
	return 0;
}

最后

以上就是难过大象为你收集整理的实验课：链表实验的全部内容，希望文章能够帮你解决实验课：链表实验所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：数据结构 PTA练习
浏览次数：50 次浏览
发布日期：2024-08-09 07:30:01
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_7_o_18_f4_12__23_cw.html

实验课：链表实验

概述

一、判断题

二、单选题

三、填空题

三、函数题

1、求单链表的表长 (10分)

2、带头结点的单链表插入操作 (10分)

3、带头结点的单链表删除操作 (10分)

4、求单链表元素序号 (10分)

5、带头结点的单链表就地逆置 (10分)

6、带头结点的链式表操作集 (10分)

四、编程题

1、两个有序链表序列的合并 (17分)

2、单链表的创建及遍历 (17分)

最后

评论列表共有 0 条评论

发表评论取消回复

实验课：链表实验

概述

一、判断题

二、单选题

三、填空题

三、函数题

1、求单链表的表长 (10分)

2、 带头结点的单链表插入操作 (10分)

3、带头结点的单链表删除操作 (10分)

4、求单链表元素序号 (10分)

5、带头结点的单链表就地逆置 (10分)

6、带头结点的链式表操作集 (10分)

四、编程题

1、两个有序链表序列的合并 (17分)

2、单链表的创建及遍历 (17分)

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

2、带头结点的单链表插入操作 (10分)

发表评论取消回复