#3900. 【模板】单链表

【模板】单链表

题目描述

实现单链表的基本操作:头插法、尾插法、按序号查找结点值、按值查找表结点、插入结点、删除结点、求表长。

注意:操作的是带头结点的单链表。

输入格式

第一行输入一个正整数 tt,表示接下来有 tt 个操作。题目保证链表内的值不会重复,保证查找和删除操作都合法。

接下来 tt 行,每行一个操作,为以下几种之一,具体请查看样例:

  • 11 nn 以空格分隔的 nn 个数,表示用头插法将 nn 个数插入到链表中,输出链表,数之间以空格分隔
  • 22 nn 以空格分隔的 nn 个数,表示用尾插法将 nn 个数插入到链表中,输出链表,数之间以空格分隔
  • 33 ii 查找序号为 ii 的结点值并输出
  • 44 ee 查找值为 ee 的结点的序号并输出
  • 55 xx yy 插入结点 xx 到链表的第 yy 个位置上,输出链表,数之间以空格分隔
  • 66 jj 将链表的第 jj 个结点删除,输出链表,数之间以空格分隔
  • 77 输出链表中数据结点的长度(不含头结点)

输出格式

每个操作需要换行,具体请查看样例。

样例

9
1 5 6 9 18 60 301
2 8 3 16 53 67 25 45 101 2
7
4 45
5 900 4
5 238 7
3 12
6 15
7
301 60 18 9 6
301 60 18 9 6 3 16 53 67 25 45 101 2
13
11
301 60 18 900 9 6 3 16 53 67 25 45 101 2
301 60 18 900 9 6 238 3 16 53 67 25 45 101 2
25
301 60 18 900 9 6 238 3 16 53 67 25 45 101
14

示例代码

  1. Python3Python3
# Author: guke

class Node(object):

    def __init__(self, elem):
        self.elem = elem
        self.next = None

class LinkList(object):

    def __init__(self):
        node = Node(None)
        self.__head = node
    
    def length(self):
        cur = self.__head.next
        count = 0
        while cur is not None:
            count += 1
            cur = cur.next
        return count
    
    def head_insert(self, item):
        node = Node(item)
        node.next = self.__head.next
        self.__head.next = node
    
    def end_insert(self, item):
        node = Node(item)
        if self.__head.next is None:
            self.__head.next = node
        else:
            cur = self.__head.next
            while cur.next is not None:
                cur = cur.next
            cur.next = node
    
    def insert(self, x, y):
        if y == 1:
            self.head_insert(x)
        elif y > self.length():
            self.end_insert(x)
        else:
            pre = self.__head
            current = 0
            while current < y - 1:
                current += 1
                pre = pre.next
            node = Node(x)
            node.next = pre.next
            pre.next = node
    
    def search_i(self, i):
        cur = self.__head.next
        record = 1
        while record < i:
            cur = cur.next
            record += 1
        return cur.elem
    
    def search_e(self, e):
        cur = self.__head.next
        record = 1
        while cur is not None:
            if cur.elem == e:
                return record
            else:
                cur = cur.next
                record += 1
    
    def delete(self, j):
        cur = self.__head.next
        pre = None
        record = 1
        while record < j:
            pre = cur
            cur = cur.next
            record += 1
        pre.next = cur.next

    def output(self):
        cur = self.__head.next
        while cur is not None:
            print(cur.elem, end=" ")
            cur = cur.next
        print()


if __name__ == "__main__":
    ll = LinkList()
    t = int(input())
    for _ in range(t):
        ali = [int(__) for __ in input().split()]
        if ali[0] == 1:
            for ___ in range(ali[1]):
                ll.head_insert(ali[2 + ___])
            ll.output()
        elif ali[0] == 2:
            for ___ in range(ali[1]):
                ll.end_insert(ali[2 + ___])
            ll.output()
        elif ali[0] == 3:
            print(ll.search_i(ali[1]))
        elif ali[0] == 4:
            print(ll.search_e(ali[1]))
        elif ali[0] == 5:
            ll.insert(ali[1], ali[2])
            ll.output()
        elif ali[0] == 6:
            ll.delete(ali[1])
            ll.output()
        else:
            print(ll.length())
  1. C++C++
// Author: guke

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

typedef int ElemType;

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

LinkList HeadCreate(LinkList &L, int x)
{
    LNode *q;
    q = (LNode *)malloc(sizeof(LNode));
    q->data = x;
    q->next = L->next;
    L->next = q;
    return L;
}

LinkList EndCreate(LinkList &L, int x)
{
    LNode *q, *p = L;
    q = (LNode *)malloc(sizeof(LNode));
    while (p->next != NULL)
        p = p->next;
    q->data = x;
    p->next = q;
    p = q;
    p->next = NULL;
    return L;
}

LNode *GetItem(LinkList L, int target)
{
    int j = 1;
    LNode *p = L->next;
    if (target == 0)
        return L;
    if (target < 1)
        return NULL;
    while (p && j < target)
    {
        p = p->next;
        j++;
    }
    return p;
}

int GetElem(LinkList L, int elem)
{
    int j = 1;
    LNode *p = L->next;
    while (p)
    {
        if (p->data == elem)
            break;
        p = p->next;
        j++;
    }
    return j;
}

bool Insert(LinkList L, int target, ElemType e)
{
    LNode *p = GetItem(L, target - 1);
    if (p == NULL)
        return false;
    LNode *q = (LNode *)malloc(sizeof(LNode));
    q->data = e;
    q->next = p->next;
    p->next = q;
    return true;
}

bool Delete(LinkList L, int target)
{
    LNode *p = GetItem(L, target - 1);
    if (p == NULL)
        return false;
    LNode *q = p->next;
    p->next = q->next;
    free(q);
    q = NULL;
    return true;
}

int Len(LinkList L)
{
    L = L->next;
    int len = 0;
    while (L != NULL)
    {
        L = L->next;
        len++;
    }
    return len;
}

void PrinList(LinkList L)
{
    L = L->next;
    while (L != NULL)
    {
        printf("%d ", L->data);
        L = L->next;
    }
    printf("\n");
}

int main()
{
    LinkList L;
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    int t, n, a;
    scanf("%d", &t);
    for (int i = 0; i < t; i++)
    {
        int op;
        scanf("%d", &op);
        if (op == 1)
        {
            scanf("%d", &n);
            for (int j = 0; j < n; j++)
            {
                scanf("%d", &a);
                HeadCreate(L, a);
            }
            PrinList(L);
        }
        else if (op == 2)
        {
            scanf("%d", &n);
            for (int j = 0; j < n; j++)
            {
                scanf("%d", &a);
                EndCreate(L, a);
            }
            PrinList(L);
        }
        else if (op == 3)
        {
            int target;
            scanf("%d", &target);
            LNode *p = GetItem(L, target);
            printf("%d\n", p->data);
        }
        else if (op == 4)
        {
            int elem;
            scanf("%d", &elem);
            int res = GetElem(L, elem);
            printf("%d\n", res);
        }
        else if (op == 5)
        {
            int x, y;
            scanf("%d %d", &x, &y);
            Insert(L, y, x);
            PrinList(L);
        }
        else if (op == 6)
        {
            int target;
            scanf("%d", &target);
            Delete(L, target);
            PrinList(L);
        }
        else if (op == 7)
        {
            int len = Len(L);
            printf("%d\n", len);
        }
    }
    return 0;
}