单链表操作集(不带有空头结点)本题要求实现不带有空头结点(dummy head node)的单链表操作集(PTA)

2024-01-03 11:36:40

单链表操作集(不带有空头结点)本题要求实现不带有空头结点(dummy head node)的单链表操作集。

函数接口定义:

struct Node* findByIndex(struct Node *head, int index);
int insertByIndex(struct Node **phead, int index, int item);
int deleteByIndex(struct Node **phead, int index, int *pitem);

其中链表结构定义如下:

struct Node{
    int data;
    struct Node *next;
};

裁判测试程序样例:

/* 测试程序仅为示例,实际的测试程序可能不同 */
#include <stdio.h>
#include <stdlib.h>
struct Node{
    int data;
    struct Node *next;
};
struct Node* initList() { return NULL; }
void printList(struct Node* head){
    /* 细节省略 */
}
struct Node* createNode(int data){
    struct Node *p;
    p = (struct Node*)malloc(sizeof(struct Node));
    if(!p) return NULL;
    p->data = data;
    p->next = NULL;
    return p;
};

struct Node* findByIndex(struct Node *head, int index);
int insertByIndex(struct Node **phead, int index, int item);
int deleteByIndex(struct Node **phead, int index, int *pitem);

int main(){
    struct Node *head;
    head = initList();
    int op, r, index, item;
    struct Node *p;
    scanf("%d", &op);
    while(op){  //1:查找   2:插入 3:删除     其它:退出
        switch(op){
        case 1:
            scanf("%d", &index);
            p = findByIndex(head, index);
            printf("%d\n", p ? p->data : 99999);
            break;
        case 2:
            scanf("%d%d", &index, &item);
            r = insertByIndex(&head, index, item);
            printf("%d : ", r);
            printList(head);
            break;
        case 3:
            scanf("%d", &index);
            item = 99999;
            r = deleteByIndex(&head, index, &item);
            printf("%d %d : ",r,item);
            printList(head);
            break;
        default:
            return 0;
        }
        scanf("%d", &op);
    }
    return 0;
}

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

输入样例 :

2 1 10
2 1 20
2 2 30
2 4 5
2 6 6
1 2
1 5
3 1
3 2
0

输出样例:

1 : 10, 
1 : 20, 10, 
1 : 20, 30, 10, 
1 : 20, 30, 10, 5, 
0 : 20, 30, 10, 5, 
30
99999
1 20 : 30, 10, 5, 
1 10 : 30, 5, 

?题解:

注意传入下标时判断是否合法


// Function to find a node by its index
struct Node* findByIndex(struct Node* head, int index) {
    struct Node* current = head;
    if(index<=0)
        return NULL;
    int i = 1;
    while (current != NULL && i <index) {
        current = current->next;
        i++;
    }
    return current;
}

// Function to insert a new node with the given item at the specified index
int insertByIndex(struct Node** phead, int index, int item) {
    if (index < 1) return 0;

    struct Node* newNode = createNode(item);
    if (newNode == NULL) return 0;

    if (index == 1) {
        newNode->next = *phead;
        *phead = newNode;
    } else {
        struct Node* prev = findByIndex(*phead, index - 1);
        if (prev == NULL) {
            free(newNode);
            return 0;
        }
        newNode->next = prev->next;
        prev->next = newNode;
    }
    return 1;
}

// Function to delete the node at the specified index and store its value in pitem
int deleteByIndex(struct Node** phead, int index, int* pitem) {
    if (index < 1 || *phead == NULL) return 0;

    struct Node* current = *phead;
    if (index == 1) {
        *pitem = current->data;
        *phead = current->next;
        free(current);
    } else {
        struct Node* prev = findByIndex(*phead, index - 1);
        if (prev == NULL || prev->next == NULL) return 0;

        current = prev->next;
        *pitem = current->data;
        prev->next = current->next;
        free(current);
    }
    return 1;
}

文章来源:https://blog.csdn.net/weixin_73728113/article/details/135337665
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。