实验二_单链表_头歌实验2单链表

引言

1. 文章结构：每题是由题目、解析与注意事项和代码三部分组成。在文章的结尾，记录了我的一些做题心得。
2. 建议第一次写这些题目的同学可以自己先敲一下代码，然后再参考文章中的代码。

---

第一题

题目

题目描述
链表是数据结构中一种最基本的数据结构，它是用链式存储结构实现的线性表。它较顺序表而言在插入和删除时不必移动其后的元素。现在给你一些整数，然后会频繁地插入和删除其中的某些元素，会在其中某些时候让你查找某个元素或者输出当前链表中所有的元素。

输入
输入数据只有一组，第一行有n+1个整数，第一个整数是这行余下的整数数目n，后面是n个整数。这一行整数是用来初始化列表的，并且输入的顺序与列表中的顺序相反，也就是说如果列表中是1、2、3那么输入的顺序是3、2、1。
第二行有一个整数m，代表下面还有m行。每行有一个字符串，字符串是“get”，“insert”，“delete”，“show”中的一种。如果是“get”或者“delete”，则其后跟着一个整数a，代表获得或者删除第a个元素；如果是“insert”，则其后跟着两个整数a和e，代表在第a个位置前面插入e；“show”之后没有整数。

输出
如果获取成功，则输出该元素；如果删除成功则输出“delete OK”；如果获取失败或者删除失败，则输出“get fail”以及“delete fail”。如果插入成功则输出“insert OK”，否则输出“insert fail”。如果是“show”则输出列表中的所有元素，如果列表是空的，则输出“link list is empty”。注：所有的双引号均不输出。

样例输入
3 3 2 1
21
show
delete 1
show
delete 2
show
delete 1
show
delete 2
insert 2 5
show
insert 1 5
show
insert 1 7
show
insert 2 5
show
insert 3 6
show
insert 1 8
show
get 2

样例输出
1 2 3
delete OK
2 3
delete OK
2
delete OK
Link list is empty
delete fail
insert fail
Link list is empty
insert OK
5
insert OK
7 5
insert OK
7 5 5
insert OK
7 5 6 5
insert OK
8 7 5 6 5
7

解析与注意事项

1. 查找中的循环条件要判断指针 p 是否为空。这样如果不在表长范围内查找，p 就会指向NULL，循环结束。从而保证在表长范围内查找。
2. 查找中判断未找到的条件：指针 p 为空（注意要写成 !p ）或计数元素 m 大于要查找元素的序数 i。这样一来，要是查找超出表长，此时 m<i，但p为空，返回错误；如果输入的 i 值小于1，那就进不了第一个循环。此时 m>i ，返回错误。这样确保了输入的 i 值不小于1（如0，-1等非法输入）
3. 插入操作中，不能把链表 L 的 next 赋给指针 p 。不然在空表插入元素时，insert 1 5（在第一个位置处插入元素5） 插入不了。因为表为空时，执行 p = L->next 后 p 指向NULL，返回错误。
4. 插入操作中，要对指针 q 分配存储空间。因为一开始声明指针变量时，系统其实并未给指针分配存储空间（系统不会单独为指针变量分配存储空间）。其实对指针 q 分配存储空间后，指针q 本身还是不占存储空间，只是在系统中分配了一块内存，然后让指针 q 指向了这块内存。
5. 删除操作用于查找的循环结束后，指针p指向的是要删除结点的前一个结点。
6. 删除操作中，释放存储空间前，要先调整结点关系。
7. 在显示操作的 printf 中，一定别忘了加空格。注意格式！

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int ElemType;   // 定义元素的类型为整型
typedef int Status;     // 定义状态类型
#define ERROR 0
#define OK 1

typedef struct LNode {
    ///===============补充代码======================== 
    ElemType data;
    struct LNode* next;
}LNode, * LinkList;      // 定义节点类型以及链表类型（链表类型实际上是一个节点指针类型）

Status GetElem_L(LinkList& L, int i, ElemType& e) { // 算法2.8
    // L为带头结点的单链表的头指针。
    // 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
   ///===============补充代码======================== 
    int m;
    LinkList p;
    p = L->next;
    for (m=1; m < i && p; m++)//注意判断是否为空p
        p = p->next;
    if (!p || m > i)//表示未找到
        return ERROR;
    e = p->data;
    return OK;
} // GetElem_L

Status ListInsert_L(LinkList& L, int i, ElemType e) { // 算法2.9
    // 在带头结点的单链线性表L的第i个元素之前插入元素e   
  ///===============补充代码========================   
    int m;
    LinkList p,q;
    p = L;
    for (m = 1; m < i && p; m++)// p = L->next;m < i-1，这么写空表时insert 1 5 插入不了
        p = p->next;
    if (!p || m > i)
        return ERROR;
    q= (LinkList)malloc(sizeof(LNode));//要分配存储空间
    q->data = e;
    q->next = p->next;
    p->next = q;
    return OK;
} // LinstInsert_L

Status ListDelete_L(LinkList& L, int i, ElemType& e) { // 算法2.10
    // 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
   ///===============补充代码======================== 
    int m;
    LinkList p,q;
    p = L;
    for (m = 1; m < i && p->next; m++)
        p = p->next;//此时p指向的是要删除结点的前一个结点
    if (!(p->next) || m > i)
        return ERROR;
    e = p->next->data;
    q = p->next;
    p->next = q->next;
    free(q);//先调整结点关系，再释放存储空间
    return OK;
} // ListDelete_L

void CreateList_L(LinkList& L, int n) { // 算法2.11
    // 逆位序输入n个元素的值，建立带表头结点的单链线性表L
   ///===============补充代码======================== 
    LinkList p;
    int i;
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;

    for (i = 0; i < n; i++)
    {
        p = (LinkList)malloc(sizeof(LNode));
        scanf("%d", &(p->data));//%d
        p->next = L->next;
        L->next = p;
    }
} // CreateList_L

int ShowList_L(LinkList L) {
    // 显示链表中的元素，返回值为链表元素的数目
    ///===============补充代码======================== 
    int m, n = 0;
    LinkList p;
    p = L->next;
    if (!p)
        return ERROR;
    for (m = 0; p; m++)
    {
        printf("%d ", (p->data));//空格！！！
        p = p->next;
        n++;
    }
    return n;
}

int main() {

    int n;                  // 初始时元素的数目
    int m;                  // 指令的数目
    char strInst[30];       // 存储指令:instruction
    int a;                  // 存储位置数据
    LinkList L;             // 链表
    int e;                  // 定义节点，用来存储获取的节点或者删除的节点
    scanf("%d", &n);        // 读入元素的数目
    CreateList_L(L, n);     // 创建链表
    scanf("%d", &m);        // 读取指令的数目
    while (m--) {             // 做 m 次循环
        scanf("%s", strInst);                   // 读取指令
        if (strcmp(strInst, "get") == 0) {        // 如果是需要获取某个元素
            scanf("%d", &a);                    // 读取元素的位置
            if (GetElem_L(L, a, e) == OK) {       // 如果获取元素成功
                printf("%d\n", e);              // 输出元素的值
            }
            else {                              // 如果获取元素失败
                puts("get fail");               // 输出获取元素的出错信息
            }
        }
        else if (strcmp(strInst, "insert") == 0) {// 如果是插入某个元素
            scanf("%d%d", &a, &e);              // 获取待插入的位置以及待插入的值
            if (ListInsert_L(L, a, e) == OK) {    // 如果插入元素成功
                puts("insert OK");              // 输出插入成功的信息
            }
            else {
                puts("insert fail");            // 否则输出插入失败的信息
            }
        }
        else if (strcmp(strInst, "delete") == 0) {// 如果是删除某个元素
            scanf("%d", &a);                     // 获得待删除元素的位置
            if (ListDelete_L(L, a, e) == OK) {    // 如果删除成功
                puts("delete OK");              // 输出删除成功的信息
            }
            else {
                puts("delete fail");            // 否则输出删除失败的信息
            }
        }
        else if (strcmp(strInst, "show") == 0) { // 如果是显示链表
            if (ShowList_L(L) == 0) {             // 如果链表为空
                puts("Link list is empty");     //显示量表为空的信息
            }
        }
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

---

做题心得

1. 对指针分配存储空间，指针本身是不占存储空间的，只是在系统中分配了一块内存，然后让指针指向了这块内存。
2. 在C语言的输入输出语句中，如「 scanf(“%d”, &(p->data)); 」由于 p->data 的数据类型是 Elemtype ,而 Elemtype 可以通过修改定义中的数据类型来修改 Elemtype 的数据类型，（即修改「 typedef int ElemType; 」中的 int ）。这时 scanf 与 printf 中的 %d 就要一个一个修改了。但要是使用的是 C++ ，由于没有格式转换说明，就不需要一个一个修改。