当前位置: 代码迷 >> 综合 >> PTA 数据结构 6-2 单链表元素定位
  详细解决方案

PTA 数据结构 6-2 单链表元素定位

热度:29   发布时间:2024-01-18 18:26:56.0
6-2 单链表元素定位(12 分)

本题要求在链表中查找第一个数据域取值为x的节点,返回节点的位序。L是一个带头结点的单链表,函数ListLocate_L(LinkList L, ElemType x)要求在链表中查找第一个数据域取值为x的节点,返回其位序(从1开始),查找不到则返回0。例如,原单链表各个元素节点的元素依次为1,2,3,4,则ListLocate_L(L, 1)返回1,ListLocate_L(L, 3)返回3,而ListLocate_L(L, 100)返回0。

函数接口定义:

int ListLocate_L(LinkList L, ElemType x);

其中 L 是一个带头节点的单链表。 x 是一个给定的值。函数须在链表中查找第一个数据域取值为x的节点。若找到则返回其位序(从1开始),找不到则返回0。

裁判测试程序样例:


//库函数头文件包含
#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   -2typedef 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;
}
//下面是需要实现的函数的声明
int ListLocate_L(LinkList L, ElemType x);int main()
{LinkList L;int n;int x,k;   scanf("%d",&n);  //输入链表中元素个数if(ListCreate_L(L,n)!= OK) {printf("表创建失败!!!\n");return -1;}scanf("%d",&x); //输入待查找元素k=ListLocate_L(L,x);printf("%d\n",k);return 0;
}/* 请在这里填写答案 */

输入样例:

4
1 2 3 4
1

输出样例:

1
//代码如下
 
      
int ListLocate_L(LinkList L, ElemType x) {  //创建一个指向当前节点的指针  LNode* curPtr = L->next;  //创建计数器counter,遍历,若当前节点数据域值=x,返回位置  int counter = 1;  //若当前指针next为空,循环结束  while(curPtr->next != NULL) {  if(curPtr->data == x)  return counter;  //否则,返回0 (为什么呢?) else {  curPtr = curPtr->next;  counter++;  }  }  
}