松鼠小筑 - 学习笔记

单链表

发表于 2020-03-07 更新于 2022-01-15 分类于数据结构与算法 Disqus：本文字数： 1.7k 阅读时长 ≈ 3 分钟

2-3 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用什么存储方式最节省运算时间？ (2分)b

单链表
仅有尾指针的单循环链表
仅有头指针的单循环链表
双链表

c虽然可以直接获得第一个元素，但是想要获得最后一个元素却需要遍历整个链表。而b给出的是带有尾结点的单循环链表，这样就可以直接得到最后一个元素，想要得到第一个元素只需要再遍历一个元素就可以，所以选择b

1-22下列函数试图求链式存储的线性表的表长，是否正确？

int  Length ( List  *PtrL )
{    List  *p = PtrL;      
     int  j = 0;
     while ( p ) { 
           p++; 
           j++;                 
     }   
     return  j;
}

F p++不能指向后一个元素

2-4

若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用哪种存储方式最节省运算时间？ (2分)

单链表
双链表
单循环链表
带头结点的双循环链表

D 头结点上一个就是最后一个节点

这道题的逻辑，简单来说，就是地址存放你当前元素的地址，链接地址是指向当前元素的下一个元素的地址。因此，我们来看没插入f之前时，链表的顺序，由于头元素是c（地址1008H），由C开始，C的链接地址是1000H，也就是指向元素a（地址1000H），之后a的链接地址是1010H，也就是指向元素e。。。按照上面这个思路遍历，我们可以得到链表的遍历顺序c（1008H）->a（1000H）->e（1010H）->b（1004H）->d（100CH）->null。由于f逻辑上位于a和e之间，因此也就是说将f插入到ae之间，因此只需要修改a的链接地址（也就是指向下一个元素的地址）为f的地址（1014H），然后将f的链接地址修改为e的地址。
链表插入不影响其他元素，所以其他元素链接地址不变。

不带表头结点，头指针直接指向数据

在m之后

在一个长度为 n （ n>1 ）的单链表上，设有头和尾两个指针，执行操作与链表的长度有关。

删除单链表中的第一个元素
删除单链表中的最后一个元素
在单链表第一个元素前插入一个新元素
在单链表最后一个元素后插入一个新元素

A
头指针是指向第一个元素（结点）的指针。当删除单链表中的第一个元素时只需要将头指针指向第二个元素，然后释放第一个元素储存空间申请的内存。与链表长度无关。

123

ListNode *temp = head->next;``head->next = temp->next;``free``(temp);

B
尾指针是指向最后一个元素（结点）的指针，与头指针类似。当删除单链表中的最后一个元素时由于不是双向链表，所以要从头指针开始，一直遍历直到倒数第二个元素，将倒数第二个元素（结点）指向NULL，释放原末端元素（结点）空间后，将尾指针等于新的末端元素（结点）。所以与链表长度有关。

12345

ListNode *p = head;``while``(p->next != rear) p = p->next;``p->next = NULL;``free``(r);``r = p;

C 在单链表第一个元素前插入一个新元素时，只需要把新的元素（结点）指向原来的第一个元素（结点），然后使头指针指向新的元素（结点）。与链表长度无关。

12

new_point->next = head->next;``head->next = new_point;

D 在单链表最后一个元素后插入一个新元素时，只需先将新结点指向NULL，然后将尾指针指向的原末端结点指向新的元素（结点），最后将尾指针指向新的元素（结点）。与链表长度无关。

123

new_point->next = NULL;``rear->next = new_point;``rear = new_point;

静态链表:数组的每一个下标都对应一个data和一个cur。数据域data用来存放数据元素，；而游标cur相当于单链表中的next指针，

存放该元素的后继在数组中的下标。

clion的安装和配置

发表于 2020-03-05 更新于 2022-01-15 分类于 C/C++ Disqus：本文字数： 762 阅读时长 ≈ 1 分钟

写代码时一个易用的编译器是很重要的，若想写c/c++我推荐jetbrain家的clion，真的很方便

首先去官网下载官网页面并安装

在这不提供破解方法，建议支持正版，破解方法可以在百度上搜索到

之后需要下载一个c/c++的译码器，我在这用的是MingW.不建议去官网下载，因为即使科学上网速度也还是很慢而且容易出错

在这提供我的百度网盘收藏链接，直接下载安装即可

链接：https://pan.baidu.com/s/1xYOb-eYFKSfJgwFxG9fZWw
提取码：kiec

（2）配置CLion
打开CLion，左上角File-Settings-Build-Toolchains，然后点击 + 号

settings

toolchains

Environment选择MinGW，然后填入刚刚解压的MinGW64的路径（这是我的路径）：

1	C:\Users\71022\Documents\mingw64

image.png

然后CLion会自动帮你填上所有你该填的东西，点击OK，等调试的小虫子变绿就可以了。

image.png

当然，也会出现无法检测成功的情况，这时候就需要手动填写啦。
CMake一般会自动选择。
Make填入路径：

1	C:\Users\71022\Documents\mingw64\bin\mingw32-make.exe

C Compiler填入路径：

1	C:\Users\71022\Documents\mingw64\bin\gcc.exe

C++ Compiler填入路径：

1	C:\Users\71022\Documents\mingw64\bin\g++.exe

Debugger一般会自己填入，如果没有可以手动填：

1	C:\Users\71022\Documents\mingw64\bin\gdb.exe

然后OK，等一段时间就可以了。

7-3 学生顺序表的建立 (10分)

发表于 2020-03-05 更新于 2022-01-15 分类于数据结构与算法 Disqus：本文字数： 862 阅读时长 ≈ 2 分钟

完成对一个顺序表的建立，表中的每个元素是同学们的学号、姓名和三门课程的成绩，输入5个同学的信息，然后显示在屏幕上。（要求利用顺序表的基本操作）

输入格式:

首先收入学生人数5，然后依次输入5个学生的学号、姓名和三门课的成绩

输出格式:

输入5个学生的学号、姓名和三门课的成绩

输入样例:

5 01 张三 89 89 89 02 李四 90 90 90 03 王五 89 89 89 04 钱六 97 97 97 05 赵倩 90 90 90

输出样例:

1 张三 89.0 89.0 89.0 2 李四 90.0 90.0 90.0 3 王五 89.0 89.0 89.0 4 钱六 97.0 97.0 97.0 5 赵倩 90.0 90.0 90.0

#include <stdio.h>
struct STU
{
    int id;
    char name[20];
    float score1;
    float score2;
    float score3;
}stu[20];
int main()
{
    int m;
    scanf("%d",&m);
    for (int i = 0; i <m ; ++i) {
        scanf("%d%s%f%f%f",&stu[i].id,&stu[i].name,&stu[i].score1,&stu[i].score2,&stu[i].score3);
    }
    for (int j = 0; j < m-1; ++j) {
        printf("%d %s %.1f %.1f %.1f\n",j+1,stu[j].name,stu[j].score1,stu[j].score2,stu[j].score3);
    }
    int j=m-1;
    printf("%d %s %.1f %.1f %.1f",j+1,stu[j].name,stu[j].score1,stu[j].score2,stu[j].score3);
        

}

7-4 顺序表的建立及遍历 (30分)

发表于 2020-02-28 更新于 2022-01-15 分类于数据结构与算法 Disqus：本文字数： 1.2k 阅读时长 ≈ 2 分钟

读入n值及n个整数，建立顺序表并遍历输出。

输入格式:

读入n及n个整数

输出格式:

输出n个整数，以空格分隔（最后一个数的后面没有空格）。

输入样例:

在这里给出一组输入。例如：

1 2	4 -3 10 20 78

输出样例:

在这里给出相应的输出。例如：

1	-3 10 20 78

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
#define list 10
#define max 10
 
typedef int Elemtype;
typedef struct sqlist *List;
struct sqlist{
Elemtype *elem;
int length;
int listsize;
};
 
void initlist(List L){
L->elem=(Elemtype *)malloc(list*sizeof(Elemtype));
L->length=0;
L->listsize=max;
}
 
void creat(List L){
initlist(L);
int i,n;
scanf("%d",&n);
for(i=0;i<n;i++) {
   scanf("%d",&L->elem[i]);
   L->length++;
   if(L->length==L->listsize) {
int *new_elem = (Elemtype *)malloc((L->listsize+list)*sizeof(Elemtype));
memcpy(new_elem,L->elem,L->length);
L->elem = new_elem;
L->listsize+=list;
   }
} 
}
 
void print(List L) {
for(int i=0; i<L->length;i++) {
if(i==L->length-1)
printf("%d",L->elem[i]);
else
printf("%d ",L->elem[i]);
}
}
 
int main(){
List L = (List)malloc(sizeof(struct sqlist));
initlist(L);
creat(L);
print(L);
return 0;
}

7-5 求集合交集 (20分)

发表于 2020-02-28 更新于 2022-01-15 分类于数据结构与算法 Disqus：本文字数： 795 阅读时长 ≈ 1 分钟

求整数集合A与整数集合B的交集。

输入格式:

输入有三行：第一行是A和B的元素个数m和n；第二行是集合A的m个元素；第三行是集合A的n个元素。

输出格式:

输出交集的所有元素（按照在A集合出现的顺序输出，最后一个输出后面没有空格）。

输入样例:

在这里给出一组输入。例如：

1
2
3

3 4
10 9 2
9 10 8 0

输出样例:

在这里给出相应的输出。例如：

10 9

#include<stdio.h>
int main()
{
    int a,b,alist[999],blist[999];
    scanf("%d%d",&a,&b);
    for(int i=0;i<a;i++){
        scanf("%d",&alist[i]);
    }
    for(int j=0;j<b;j++){
        scanf("%d",&blist[j]);
    }
    int clist[999]={0};
    int q=0;
    for(int k=0;k<a;k++){
        int temp=alist[k];
        for(int p=0;p<b;p++){
            if(temp==blist[p]){
                clist[q]=temp;
                q++;
            }
        }
    }
    if (q>0){
    for(int u=0;u<q-1;u++){
        printf("%d ",clist[u]);
    }
    printf("%d",clist[q-1]);
    return 0;} else{
        return 0;
    }
}