算法2-1 在顺序表 list 中查找元素 x

分数 10

作者 陈越

单位 浙江大学

请编写程序，将 n 个整数存入顺序表，对任一给定整数 x，查找其在顺序表中的位置。

输入格式：

输入首先在第一行给出正整数 n（≤104）；随后一行给出 n 个 int 范围内的不重复的整数，数字间以空格分隔；最后一行给出待查找的元素 x，也是 int 范围内的整数。

输出格式：

在一行中输出 x 在顺序表中的位置，即数组下标。如果没找到，则输出 -1。注意数组下标从 0 开始。

输入样例 1：

5
1 2 3 4 5
4

输出样例 1：

3

输入样例 2：

5
4 3 6 8 0
1

输出样例 2：

-1

解析（按课本）

#include <iostream>
#include <cstdlib>
using namespace std;
#define MAXSIZE 10000
typedef int ElemType;
typedef ElemType * list;
typedef struct 
{
    ElemType * elem;    
    int length;
    int listsize;
}SqList;

int main()
{
    int n;
    cin >> n;
    SqList L;
    L.elem = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));
    L.length = n;
    L.listsize = MAXSIZE;
    for(int i = 0; i < n; i++)
        cin >> L.elem[i];
    int k;
    cin >> k;
    for(int i = 0; i < L.length; i++)
    {
        if(L.elem[i] == k)
        {
            cout << i << endl;
            return 0;
        }
    }
    cout << -1;
    return 0;
}

算法2-2 在顺序表 list 的第 i 个位置上插入元素 x

分数 15

作者 陈越

单位 浙江大学

请编写程序，将 n 个整数存入顺序表，对任一给定整数 x，将其插入顺序表中指定的第 i 个位置。注意：i 代表位序，从 1 开始，不是数组下标。

输入格式：

输入首先在第一行给出正整数 n（≤104）；随后一行给出 n 个 int 范围内的整数，数字间以空格分隔；最后一行给出插入位置 i 和待插入的元素 x，均为 int 范围内的整数。

输出格式：

分以下几种情况输出：

  • 如果顺序表中已经有 104 个元素了，则不能插入，在一行中输出句子 错误：表满不能插入。。
  • 如果插入的位置不合法，则不能插入，在一行中输出句子 错误：插入位置不合法。。
  • 无论是否插入成功，都在一行中顺序输出表中的元素，每个元素后面跟一个空格。

输入样例 1：

5
1 2 3 4 5
3 8

输出样例 1：

1 2 8 3 4 5

输入样例 2：

5
4 3 6 8 0
0 1

输出样例 2：

错误：插入位置不合法。
4 3 6 8 0

解析（按课本）

#include <iostream>
#include <cstdlib>
using namespace std;
#define MAXSIZE 10000
typedef int ElemType;
typedef ElemType * list;
typedef struct
{
    ElemType * elem;
    int length;
    int listsize;
}SqList;
int main()
{
    SqList L;
    L.elem = (ElemType *)malloc(MAXSIZE * sizeof(ElemType)); 
    int n;
    cin >> n;
    L.length = n;
    L.listsize = MAXSIZE;
    for(int i = 0; i < n; i++)
        cin >> L.elem[i];
    int a, b;
    cin >> a >> b;
    if(a < 1 || a > L.length + 1)
    {
        cout << "错误：插入位置不合法。" << endl;
    }
    else if(L.length >= L.listsize)
    {
        cout << "错误：表满不能插入。" << endl;
    }
    else
    { 
        for(int i = L.length - 1; i >= a - 1; i--)
            L.elem[i + 1] = L.elem[i];
        L.elem[a - 1] = b;
        L.length++;
    }
    for(int i = 0; i < L.length; i++)
        cout << L.elem[i] << " ";
    return 0;
}

算法2-3 从顺序表 list 中删除第 i 个元素

分数 15

作者 陈越

单位 浙江大学

请编写程序，将 n 个整数存入顺序表，对任一指定的第 i 个位置，将这个位置上的元素从顺序表中删除。注意：i 代表位序，从 1 开始，不是数组下标。

输入格式：

输入首先在第一行给出正整数 n（≤104）；随后一行给出 n 个 int 范围内的整数，数字间以空格分隔；最后一行给出删除位序 i，为 int 范围内的整数。

输出格式：

如果删除的位置不合法，则不能删除，在一行中输出句子 错误：不存在这个元素。。无论是否删除成功，都在一行中顺序输出表中的元素，每个元素后面跟一个空格。

输入样例 1：

5
1 2 3 4 5
3

输出样例 1：

1 2 4 5

输入样例 2：

5
4 3 6 8 0
0

输出样例 2：

错误：不存在这个元素。
4 3 6 8 0

解析（按课本）

#include <iostream>
using namespace std;
#define MAXSIZE 10000
typedef int ElemType;
typedef ElemType * list;
typedef struct
{
    ElemType * elem;
    int length;
    int listsize;
}SqList;
int main()
{ 
    SqList L;
    L.elem = (ElemType *)malloc(MAXSIZE * sizeof(ElemType)); 
    int n;
    cin >> n;
    L.length = n;
    L.listsize = MAXSIZE;
    for(int i = 0; i < n; i++)
        cin >> L.elem[i];
    int k;
    cin >> k;
    if(k < 1 || k > L.length)
        cout << "错误：不存在这个元素。" << endl;
    else
    {
        for(int i = k; i < L.length; i++)
            L.elem[i - 1] = L.elem[i];
        L.length--;
    }
    for(int i = 0; i < L.length; i++)
        cout << L.elem[i] << " ";
    return 0;
}

算法2-4 求单链表list中的元素个数，即表长

分数 15

作者 陈越

单位 浙江大学

请编写程序，将 n 个整数顺次插入一个初始为空的单链表的表头。最后输出单链表的表长。
本题旨在训练学习者熟悉单链表的基本操作，不建议直接输出 n。

输入格式：

输入首先在第一行给出非负整数 n（≤15）；随后一行给出 n 个 int 范围内的整数，数字间以空格分隔。

输出格式：

在一行中输出单链表的表长。

输入样例：

5
1 2 3 4 5

输出样例：

5

解析

#include <iostream>
#include <cstdlib>
using namespace std;
typedef int ElemType;
typedef struct LNode
{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

int main()
{
    LinkList head = (LinkList)malloc(sizeof(LNode));
    head->next = NULL;

    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        LinkList p = (LinkList)malloc(sizeof(LNode));
        cin >> p->data;
        p->next = head->next;
        head->next = p;
    }

    int count = 0;
    LinkList p = head->next;
    while (p)
    {
        count++;
        p = p->next;
    }
    cout << count << endl;
    return 0;
}

注意

创建了一个头节点，避免了插入时判断 “链表是否为空” 的麻烦（无论链表是否有有效节点，插入逻辑都一致），是单链表的常用优化写法