博客

数据结构与算法题目集（中文）——函数题（一）

  • Post author:
  • Post category:其他




数据结构与算法题目集（中文）——函数题（一）

文章目录



6-1 单链表逆转

函数接口定义： 

List Reverse( List L );

其中

List

结构定义如下： 

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */


L

是给定单链表，函数

Reverse

要返回被逆转后的链表。


裁判测试程序样例：
 

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

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;

List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表 */

List Reverse( List L );

int main()
{
    List L1, L2;
    L1 = Read();
    L2 = Reverse(L1);
    Print(L1);
    Print(L2);
    return 0;
}

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


输入样例：
 

5
1 3 4 5 2


输出样例：
 

1
2 5 4 3 1



代码


参考博客
 

List Reverse( List L )
{
 	List Temp, Prev;
 	Prev = NULL;
 	while(L)
 	{
 		Temp = L->Next;
 		L->Next = Prev;
 		Prev = L;
 		L = Temp;
 	}
 	return Prev;
}



思考

1.超清晰的解读！

img

2.对于输入和输出样例的分析

​ 5个元素，分别是…

​ 1 (print(L1) 的结果)

​ 2 5 4 3 1（print(L2) 的结果）


还是不太明白为什么print(L1)可以输出1，在reverse()执行完后L1不是指向NULL了么？

大佬的调试代码 

#include<stdio.h>  
#include<stdlib.h>  
typedef int ElementType;  
typedef struct Node *PtrToNode;  
struct Node {  
    ElementType Data;  
    PtrToNode Next;  
};  
typedef PtrToNode List;  
List Read();  
void Print(List L);  
List Reverse(List L);  
  
int main()  
{  
    List L1, L2;  
    L1 = Read();  
    L2 = Reverse(L1);  
    Print(L1);  
    Print(L2);  
  
    return 0;  
}  
  
/* 建立链表 */  
List Read()  
{  
    List head = NULL;  
    List current;  
    List prev = NULL;  
    int len = 0;  
    scanf("%d", &len);  
    if (len == 0)   return NULL;  
    
    while (len--)   
    {  
        current = (List)malloc(sizeof(struct Node));  
        if (head == NULL)  
            head = current;  
        else  
        prev->Next = current;  
        current->Next = NULL;  
        scanf("%d", &current->Data);  
        prev = current; 
    }  
    return head;  
}  
  
void Print(List L)  
{  
    List p = L;  
    List s = L;  
    List temp;  
    if (p == NULL)  
        printf("NULL");  
    else  
        printf("\n");  
    while (p!=NULL) {  
        printf("%d ", p->Data);  
        p = p->Next;  
    }  
}  
  
List Reverse( List L )  
{  
    List Temp, Prev;  
    Prev = NULL;  
    while(L->Next)  
    {  
        Temp = L->Next;  
        L->Next = Prev;  
        Prev = L;  
        L = Temp;  
    }  
    return Prev;  
}



6-2 顺序表操作集

函数接口定义： 

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

其中

List

结构定义如下： 

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素的位置 */
};

各个操作函数的定义为：


List MakeEmpty()

：创建并返回一个空的线性表；


Position Find( List L, ElementType X )

：返回线性表中X的位置。若找不到则返回ERROR；


bool Insert( List L, ElementType X, Position P )

：将X插入在位置P并返回true。若空间已满，则打印“FULL”并返回false；如果参数P指向非法位置，则打印“ILLEGAL POSITION”并返回false；


bool Delete( List L, Position P )

：将位置P的元素删除并返回true。若参数P指向非法位置，则打印“POSITION P EMPTY”（其中P是参数值）并返回false。


裁判测试程序样例：
 

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

#define MAXSIZE 5
#define ERROR -1
typedef enum {false, true} bool;
typedef int ElementType;
typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素的位置 */
};

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;

    L = MakeEmpty();
    scanf("%d", &N);
    while ( N-- ) {
        scanf("%d", &X);
        if ( Insert(L, X, 0)==false )
            printf(" Insertion Error: %d is not in.\n", X);
    }
    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
            printf("%d is at position %d.\n", X, P);
    }
    scanf("%d", &N);
    while ( N-- ) {
        scanf("%d", &P);
        if ( Delete(L, P)==false )
            printf(" Deletion Error.\n");
        if ( Insert(L, 0, P)==false )
            printf(" Insertion Error: 0 is not in.\n");
    }
    return 0;
}

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


输入样例：
 

6
1 2 3 4 5 6
3
6 5 1
2
-1 6


输出样例：
 

FULL Insertion Error: 6 is not in.
Finding Error: 6 is not in.
5 is at position 0.
1 is at position 4.
POSITION -1 EMPTY Deletion Error.
FULL Insertion Error: 0 is not in.
POSITION 6 EMPTY Deletion Error.
FULL Insertion Error: 0 is not in.



代码

List MakeEmpty(){
    List p;
    p = (List)malloc(sizeof(struct LNode));
    p->Last = -1;//题干要求保存线性表中最后一个元素的位置，则空表初始化为-1
    return p;
}

Position Find( List L, ElementType X ){
    for(int i = 0; i <= L->Last; i++){
        if(X==L->Data[i]){//遍历搜索查找
            return i;
        }
    }
    return ERROR; //-1
}

bool Insert( List L, ElementType X, Position P ){
    if(L->Last==MAXSIZE-1){//已满
        printf("FULL");
        return false;
    }
    
    if(P<0||P>L->Last+1){//非法
        printf("ILLEGAL POSITION");
        return false;
    }
    
    //正常情况
    int i;
    for(i = L->Last+1; i > P; i--){
        L->Data[i] = L->Data[i-1];//向右平移
    }
    
    L->Data[i] = X;//插入
    L->Last++;//个数增加
    return true;
}

bool Delete( List L, Position P ){
    //if(L->Last==-1)return false;//无需判断是否为空，否则有些情况无法输出下句
    
    if(P<0||P>L->Last){//删除的位置不在已有位置内
        printf("POSITION %d EMPTY",P);
        return false;
    }
    for(int i = P; i < L->Last; i++){//删除后向左平移
        L->Data[i] = L->Data[i+1];
    }
    L->Last--;//减少一个
    return true;
}



知识

1.线性表存储结构有顺序结构和链式存储结构。前者是顺序表，后者为链表。

2.

线性表考研数据结构笔记，感谢！



6-3 求链式表的表长

函数接口定义： 

int Length( List L );

其中

List

结构定义如下： 

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


L

是给定单链表，函数

Length

要返回链式表的长度。


裁判测试程序样例：
 

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

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

List Read(); /* 细节在此不表 */

int Length( List L );

int main()
{
    List L = Read();
    printf("%d\n", Length(L));
    return 0;
}

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


输入样例：
 

1 3 4 5 2 -1


输出样例：
 

5



代码

int Length( List L ){
    int len=0;
    while(L){
        len++;
        L=L->Next;
    }
    return len;
}

把空表的情况也考虑在内了



6-4 链式表的按序号查找

函数接口定义： 

ElementType FindKth( List L, int K );

其中

List

结构定义如下： 

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


L

是给定单链表，函数

FindKth

要返回链式表的第

K

个元素。如果该元素不存在，则返回

ERROR

。


裁判测试程序样例：
 

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

#define ERROR -1
typedef int ElementType;
typedef struct LNode *PtrToLNode;
struct LNode {
    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode List;

List Read(); /* 细节在此不表 */

ElementType FindKth( List L, int K );

int main()
{
    int N, K;
    ElementType X;
    List L = Read();
    scanf("%d", &N);
    while ( N-- ) {
        scanf("%d", &K);
        X = FindKth(L, K);
        if ( X!= ERROR )
            printf("%d ", X);
        else
            printf("NA ");
    }
    return 0;
}

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


输入样例：
 

1 3 4 5 2 -1
6
3 6 1 5 4 2


输出样例：
 

4 NA 1 2 5 3



代码

ElementType FindKth( List L, int K ){
	List L1=L; 
 	int cnt=1; //注意题干要求“第K个”元素，需要从1开始
  	while(L1){
  		if(cnt==K) return L1->Data;
  		L1=L1->Next; 
        cnt++;
 	}
  	return ERROR;
}

d”, &N);

while ( N– ) {


scanf(“%d”, &K);

X = FindKth(L, K);

if ( X!= ERROR )

printf(“%d “, X);

else

printf(“NA “);

}

return 0;

}

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




**输入样例：**

```in
1 3 4 5 2 -1
6
3 6 1 5 4 2


输出样例：
 

4 NA 1 2 5 3



代码

ElementType FindKth( List L, int K ){
	List L1=L; 
 	int cnt=1; //注意题干要求“第K个”元素，需要从1开始
  	while(L1){
  		if(cnt==K) return L1->Data;
  		L1=L1->Next; 
        cnt++;
 	}
  	return ERROR;
}


版权声明：本文为lmyouxiu原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。