# 数据结构与算法实验报告

## |顺序表|顺序表的查找操作

### 1. 实训题目

本题要求实现一个函数，要求从顺序表中查找指定元素，并返回第一个查找成功的元素在表中的位置序号，若查找失败，则返回0；

函数接口定义：

```c++
int LocateElem(SqList L,ElemType e);
```

其中SqList结构定义如下：

```c++
typedef struct{
    ElemType *elem;
    int length;
 }SqList;
```

裁判测试程序样例：

```c++
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 5
typedef int ElemType;
typedef struct{
    ElemType *elem;
    int length;
}SqList;
void InitList(SqList &L);/*细节在此不表*/
int LocateElem(SqList L,ElemType e);
int main(){
    SqList L;
    InitList(L);
    ElemType e;
    int p;
    scanf("%d",&e);
    p=LocateElem(L,e);
    printf("The position of %d in SequenceList L is %d.",e,p);
    return 0;
}
/* 请在这里填写答案 */
```

### 2. 算法思想

顺序表的遍历

### 3. 算法步骤

- 因为是顺序表，所以，第一个指针指向0就可以。（也可以说指到表头）
- 设置一个计数器`i`,初始化为`0`
- 从第一个节点开始访问，访问到`L.length-1`的点。
- 如果找到与元素`e`相同的元素，返回`i+1`,因为存储单位是从0开始的。

### 4. 源代码

```cpp
int LocateElem(SqList L,ElemType e){
  for(int i=0;i<L.length;++i){
    if(L.elem[i]==e)return i+1;
  }
  return 0;
}
```

## |顺序表|顺序表的插入操作

### 1.实训题目

本题要求实现一个函数，在顺序表的第i个位置插入一个新的数据元素e，插入成功后顺序表的长度加1，函数返回值为1；插入失败函数返回值为0；

函数接口定义：

```cpp
int ListInsert(SqList &L,int i,ElemType e);
```

其中SqList结构定义如下：

```cpp
typedef struct{
    ElemType *elem;
    int length;
}SqList;
```

裁判测试程序样例：

```cpp
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 5
typedef int ElemType;
typedef struct {
  ElemType *elem;
  int length;
} SqList;
void InitList(SqList &L); /*细节在此不表*/
int ListInsert(SqList &L, int i, ElemType e);
int main() {
  SqList L;
  InitList(L);
  ElemType e;
  int i;
  scanf("%d%d", &i, &e);
  int result = ListInsert(L, i, e);
  if (result == 0) {
    printf("Insertion Error.The value of i is unlawful or the storage space is "
           "full!");
  } else if (result == 1) {
    printf("Insertion Success.The elements of the SequenceList L are:");
    for (int j = 0; j < L.length; j++) {
      printf(" %d", L.elem[j]);
    }
  }
  return 0;
}
/* 请在这里填写答案 */

```

### 2.算法思想

顺序表的插入操作。

先将i后面的元素整体后移，然后插入元素和维护长度。

### 3.算法步骤

- 存储的时候是以0开始存储的，所以开始的时候让`i--`，这样可以更加方便的写代码
- 判断非法条件，`i>=L.length` `i`大于L的长度，`i`小于`0`，`L`的长度已经到达最大值，都返回`0`
- 设置计数器`ii`,初始化为`L的长度-1`
- `ii`从`L的长度-1`递减到`ii`,每次减1
- 赋值:让`L`的第ii+1元素的值为第ii元素的值
- 插入元素:修改第i个元素的值为e
- 维护表长:L的长度+1
- 返回状态

### 4.源代码

```cpp
int ListInsert(SqList &L,int i,ElemType e){
  i=i-1;
  if(i>L.length||i<0)return 0;//大于长度
  if(L.length==MAXSIZE)return 0;
  for(int ii=L.length-1;ii>=i;--ii){//后移元素
      L.elem[ii+1]=L.elem[ii];
    }
  L.elem[i]=e;//修改元素
  L.length++;//修改表长
  return 1;
}
```

## |顺序表|顺序表的删除操作

### 1.实训题目

本题要求实现一个函数，要求将顺序表的第i个元素删掉，成功删除返回1，否则返回0；

函数接口定义：

```cpp
int ListDelete(SqList &L,int i);
```

其中SqList结构定义如下：

```cpp
typedef struct{
    ElemType *elem;
    int length;
 }SqList;
```

裁判测试程序样例：

```cpp
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 5
typedef int ElemType;
typedef struct {
  ElemType *elem;
  int length;
} SqList;
void InitList(SqList &L); /*细节在此不表*/
int ListDelete(SqList &L, int i);
int main() {
  SqList L;
  InitList(L);
  int i;
  scanf("%d", &i);
  int result = ListDelete(L, i);
  if (result == 0) {
    printf("Delete Error.The value of i is illegal!");
  } else if (result == 1) {
    printf("Delete Success.The elements of the SequenceList L are:");
    for (int j = 0; j < L.length; j++) {
      printf(" %d", L.elem[j]);
    }
  }
  return 0;
}
/* 请在这里填写答案 */

```

### 2.算法思想

顺序表的删除操作。

将i后面的元素整体后移，然后维护长度。

### 3.算法步骤

- 判断非法条件： 都返回`0`
  - `i`大于L的长度，
  - `i`小于等于`0`，
  - `L`的长度已经到达最大值。
  - `L`的长度小于1
- 设置计数器`j`,初始化为`i-1`
- `j`从`i-1`递增到`L.elem-2`,每+1
- 赋值:让`L`的第j个元素的值为`L`的第j+1的元素的值
- 维护表长:`L.length` -1
- 返回状态值

### 4. 源代码

```cpp
int ListDelete(SqList &L,int i){
  if(L.length<1||i>L.length||i<=0)return 0;
  for(int j=i-1;j<L.length-1;++j){//从i-1到L.elem-2 进行操作
    L.elem[j]=L.elem[j+1];
  }
  L.length-=1;//修改长度
  return 1;
}
```

## |顺序表|求顺序表最大值

### 1.实训题目

本题要求实现一个函数，要求返回顺序表的最大值，空表返回0。题目保证顺序表中所有元素都为正整数。

函数接口定义：

```cpp
int GetMax(SqList L);
```

其中`SqList`结构定义如下：

```cpp
typedef struct{
    ElemType *elem;
    int length;
}SqList;
```

裁判测试程序样例：

```cpp
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 5
typedef int ElemType;
typedef struct{
    ElemType *elem;
    int length;
 }SqList;
void InitList(SqList &L);/*细节在此不表*/
int GetMax(SqList L);

int main()
{
    SqList L;
    InitList(L);
    int p;
    p=GetMax(L);
    if(p) printf("The max of SequenceList L is %d.\n",p);
    else printf("The SequenceList is null.\n");
    return 0;
}

/* 请在这里填写答案 */

```

### 2.算法思想

枚举顺序表中的每一个元素。

然后进行判断是否为当前的最大值

### 3.算法步骤

- 判断非法条件： 都返回`0`
  - `L`的长度为`0`
- 定义一个无限大的数`cmax`为`0x3f3f3f3f` (`7f7f7f7f`容易爆int)
- `i`从`0`递增到`L.length-1`,每+1
- 赋值:让`cmax`为`cmax`和`L的第i个的元素`的最大值
- 返回`cmax`

### 4. 源代码

```cpp
int max(int a,int b){return a>b?a:b;}
int GetMax(SqList L){
  if(L.length==0)return 0;
  int cmax=-0x3f3f3f3f;
  for(int i=0;i<L.length;++i){
    cmax=max(cmax,L.elem[i]);
  }
  return cmax;
}
```

## |顺序表|后记

过程中用了这个调试代码来初始化和调试

```cpp
void InitList(SqList &L){
  L.elem=new ElemType[MAXSIZE];//线性表标记到数组
  L.length = 0;//设置当前的长度为0
  for(int i=0;;++i){//读入
    ElemType e;
    scanf("%d",&e);
    if(e==-1)break;//如果是-1 break掉
    L.elem[L.length++]=e;//插入
  }
}
```

## |链表|求单链表的表长

### 1.实训题目

本题要求实现一个函数，求带头结点的单链表的表长。

### 函数接口定义：

```c++
int Length ( LinkList L );
```

其中LinkList结构定义如下：

```c++
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
```

L是带头结点的单链表的头指针，函数Length返回单链表的长度。

### 裁判测试程序样例：

```c++
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode {
  ElemType data;
  struct LNode *next;
} LNode, *LinkList;
LinkList Create(); /* 细节在此不表 */
int Length(LinkList L);
int main() {
  LinkList L = Create();
  printf("%d\n", Length(L));
  return 0;
}
/* 你的代码将被嵌在这里 */
```

### 输入样例：

```in
2 1 4 5 3 -1
```

### 输出样例：

```out
5
```

### 2. 算法思想

枚举每个节点，然后计数器自增。

### 3. 算法步骤

- 申请一个临时变量`siz`作为计数器，并且初始化为0
- 让`i`从`L-next`开始，每次赋值为`i->next`
- 每次循环进行加`1`
- 返回`siz`

### 4. 源代码

```cpp
int Length ( LinkList L ){
  int siz=0;
  for(LinkList i=L->next;i!=NULL;i=i->next){
    siz++;
  }
  return siz;
}
```

## **|链表|带头结点的单链表插入操作**

### 1. 实训题目

**6-2 带头结点的单链表插入操作**

本题要求实现带头结点的单链表插入操作，插入成功返回1，否则返回0。

### 函数接口定义：

```c
int insert_link ( LinkList L,int i,ElemType e);
```

L是单链表的头指针，i为插入位置，e是插入的数据元素，插入成功返回1，否则返回0。

### 裁判测试程序样例：

```c
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode {
  ElemType data;
  struct LNode *next;
} LNode, *LinkList;
LinkList Create(); /* 细节在此不表 */
void print(LinkList L);
int insert_link(LinkList L, int i, ElemType e);
int main() {
  int position, insert_data;
  int flag;
  LinkList L = Create();
  scanf("%d", &position);
  scanf("%d", &insert_data);
  flag = insert_link(L, position, insert_data);
  if (flag) {
    print(L);
  } else {
    printf("Wrong Position for Insertion");
  }
  return 0;
}
void print(LinkList L) {
  LinkList p;
  p = L->next;
  while (p) {
    printf("%d ", p->data);
    p = p->next;
  }
}
/* 请在这里填写答案 */
```

### 输入格式：

输入数据为三行，第一行是若干正整数，最后以-1表示结尾（-1不算在序列内，不要处理）。所有数据之间用空格分隔。
第二行数据是插入位置，第三行数据是被插入元素值。

### 输入样例：

```in
1 2 3 4 5 6 -1
2 
100
```

### 输出样例：

```out
1 100 2 3 4 5 6 
```

### 2.算法思想

判断非法条件之后，找到需要插入位置`i`的**前一个**节点，新建节点进行插入，同时维护链表。

### 3.算法步骤

- 先计算大小，方法如同`求单链表的表长`,申请变量`siz`，从`j=L`开始，每次赋值`j=j->next`：，每次循环`siz`自增。
- 如果插入的坐标`i`**小于**`0`或者**大于** `链表的长度`，则不是合法插入，返回`0`
- 申请新的内存。
- 初始化新的节点`ovo`
- 设置循环变量`j`，初始化为`j=L`，终止条件`j!=NULL`，循环赋值`j=j->next`
- 如果`++cnt`的值为`i`，也就是`j`的后继为待插入位置
  - 新建节点的后继设置为当前节点`j`的后继。 也就是执行`ovo->next=j->next`
  - 当前节点`j`的后继设置为申请的新的节点`ovo`

### 4.源代码

```cpp
int insert_link(LinkList L, int i, ElemType e){
  int siz=0;
  for(LinkList j = L;j!=NULL;j=j->next){++siz;}//计算大小
  if(i<=0 || i>siz)return 0;//错误判断
  LNode *ovo = (LNode*)malloc(sizeof(LNode));//新建节点
  ovo->data=e;//赋值
  int cnt= 0;//计数器
  for(LinkList j = L;j!=NULL;j=j->next){
    if(++cnt == i){
      ovo->next=j->next;
      j->next=ovo;
    }
  }
  return 1;
}
```

## |链表|**带头结点的单链表删除操作**

### 1. 实训题目

本题要求实现删除单链表的第i个元素结点，删除成功返回1，否则返回0。

### 函数接口定义：

```c++
int delete_link ( LinkList L,int i);
```

L为单链表的头指针，i为删除结点的序号。

### 裁判测试程序样例：

```cpp
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode {
  ElemType data;
  struct LNode *next;
} LNode, *LinkList;
LinkList Create(); /* 细节在此不表 */
void print(LinkList L);
int delete_link(LinkList L, int i);
int main() {
  LinkList L = Create();
  int position;
  int flag;
  scanf("%d", &position);
  flag = delete_link(L, position);
  if (flag) {
    print(L);
  } else {
    printf("Wrong Position for Deletion");
  }
  return 0;
}
void print(LinkList L) {
  LinkList p;
  p = L->next;
  while (p) {
    printf("%d ", p->data);
    p = p->next;
  }
}
/* 请在这里填写答案 */
```

### 输入格式：

输入数据为两行，第一行是若干正整数，最后以-1表示结尾（-1不算在序列内，不要处理）。所有数据之间用空格分隔。
第二行数据是删除位置。

### 输入样例：

```in
1 2 3 4 5 6 -1
3
```

### 输出样例：

```out
1 2 4 5 6 
```

### 2.算法思想

先判断非法条件。

枚举链表，找到该节点时，删除节点，维护链表结构。

### 3.算法步骤

- 判断非法条件:如果插入位置大于链表长度，或者小于等于0则为非法
- 设置计数器`cnt`，初始化为`0`
- 设置循环变量`j`，初始化为`j=L`，终止条件`j!=NULL`，循环赋值`j=j->next`
- 当`cnt+1`等于`i`的时候，即当元素，则开始插入
  - 建立临时变脸`nx`
  - 判断当前的j的下一个，是否是链表最后一个元素，如果是`nx=NULL`，否则让`nx`等于`j`的下一个的下一个，即要删除元素的后继。
  - 删除(`j->next`)，释放内存空间，维护链表。
  - 只需要让`j`（待删除节点的**前驱**）指向待删除节点的**后继**，即为`j->next=nx`
- 返回插入成功状态值。

### 4.源代码

```cpp
int delete_link ( LinkList L,int i){
  int siz=0;
  for(LinkList j = L;j!=NULL;j=j->next){++siz;}//计算大小
  siz-=1;
  
  if(i>siz||i<=0)return 0;
  int cnt= 0;
  for(LinkList j = L;j!=NULL;j=j->next){
    if(++cnt==i){
      LinkList nx;
      if(j->next==NULL)nx=NULL;
      else nx=j->next->next;
      free(j->next);
      j->next=nx;
      break;
    }
  }
  return 1;
}
```



## |链表|**求单链表元素序号**

### 1. 实训题目

#### **求单链表元素序号**

本题要求实现一个函数，求带头结点的单链表中元素序号。

### 函数接口定义：

```c++
int Locate ( LinkList L, ElemType e);
```

L是带头结点的单链表的头指针，e是要查找的元素值。如果e在单链表中存在，函数Locate返回其序号（序号从1开始）；否则，返回0。

### 裁判测试程序样例：

```c++
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
LinkList Create();/* 细节在此不表 */
int Locate ( LinkList L, ElemType e);
int main(){
    ElemType e;
    LinkList L = Create();
    scanf("%d",&e);
    printf("%d\n", Locate(L,e));
    return 0;
}
/* 你的代码将被嵌在这里 */
```

### 输入样例：

```in
2 1 4 5 3 -1
5
```

### 输出样例：

```out
4
```

### 2.算法思想

枚举结点，同时计数。

### 3.算法步骤

- 设置变量`cnt` 初始化为`0`，用于计数

- 设置循环变量`i`，初始化为`i=L-next`，终止条件`i!=NULL`，循环赋值`i=i->next`

  - 循环内 `cnt` 自增

  - 循环内进行判断，当前节点的`data`值是否为`e`
    - 如果为`e` 则返回`cnt`的值

- 如果循环结束没有进行返回，则说明`cnt`不存在，返回`0`。

### 4.源代码

```cpp
int Locate(LinkList L, ElemType e){
  int cnt=0;
  for(LinkList i=L->next;i!=NULL;i=i->next){
    ++cnt;
    if(i->data==e){
      return cnt;
    }
  }
  return 0;
}
```



## |链表|**带头结点的单链表就地逆置**

### 1. 实训题目

**带头结点的单链表就地逆置**

本题要求编写函数实现带头结点的单链线性表的就地逆置操作函数。L是一个带头结点的单链表，函数ListReverse_L(LinkList &L)要求在不新开辟节点的前提下将单链表中的元素进行逆置，如原单链表元素依次为1,2,3,4，则逆置后为4,3,2,1。

### 函数接口定义：

```c++
void ListReverse_L(LinkList &L);
```

其中 `L` 是一个带头结点的单链表。

### 裁判测试程序样例：

```c++
//库函数头文件包含
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

//函数状态码定义
#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE -1
#define OVERFLOW   -2

typedef int  Status;
typedef int  ElemType; //假设线性表中的元素均为整型

typedef struct LNode
{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

Status ListCreate_L(LinkList &L,int n)
{
    LNode *rearPtr,*curPtr;   //一个尾指针，一个指向新节点的指针
    L=(LNode*)malloc(sizeof (LNode));
    if(!L)exit(OVERFLOW);
    L->next=NULL;               //先建立一个带头结点的单链表
    rearPtr=L;  //初始时头结点为尾节点,rearPtr指向尾巴节点
    for (int i=1;i<=n;i++){  //每次循环都开辟一个新节点，并把新节点拼到尾节点后
        curPtr=(LNode*)malloc(sizeof(LNode));//生成新结点
        if(!curPtr)exit(OVERFLOW);
        scanf("%d",&curPtr->data);//输入元素值
        curPtr->next=NULL;  //最后一个节点的next赋空
        rearPtr->next=curPtr;
        rearPtr=curPtr;
    }
    return OK;
}
void ListReverse_L(LinkList &L);
void ListPrint_L(LinkList &L){
//输出单链表
    LNode *p=L->next;  //p指向第一个元素结点
    while(p!=NULL)
    {
          if(p->next!=NULL)
               printf("%d ",p->data);
          else
               printf("%d",p->data);
          p=p->next;
    }
}
int main()
{
    LinkList L;
    int n;
    scanf("%d",&n);
    if(ListCreate_L(L,n)!= OK) {
          printf("表创建失败！！！\n");
          return -1;
    }
    ListReverse_L(L);
    ListPrint_L(L);
    return 0;
}
/* 请在这里填写答案 */
```

**输入格式**：

第一行输入一个整数n，表示单链表中元素个数，接下来一行共n个整数，中间用空格隔开。

**输出格式**：

输出逆置后顺序表的各个元素，两个元素之间用空格隔开，最后一个元素后面没有空格。

### 输入样例：

```in
4
1 2 3 4
```

### 输出样例：

```out
4 3 2 1
```

### 2.算法思想

新建一个链表，枚举旧链表的同时使用头插法进行插入新的链表。

### 3.算法步骤

- 新建一个链表`ls`，申请内存空间
- 初始化链表`ls: ls->next =NULL; ls->data=0`;
- 设置循环变量`i`，初始化为`i=L-next`，终止条件`i!=NULL`，循环赋值`i=i->next`
  - 循环内：新建节点`tmp`，申请内存空间。
  	- 循环内：`tmp`进行赋值，`tmp`的`data=i`的`data`。
  	- 头插法：`tmp`的下一个等于ls的下一个。
  	- 头插法：`ls`的下一个节点为`tmp`
- L 赋值为新建的列表。
- 此处可以把旧的链表的内存空间清空。

### 4.源代码

```cpp
void ListReverse_L(LinkList &L) {
  LNode *ls = (LNode*)malloc(sizeof(LNode));
  ls->next=NULL;
  ls->data=0;
  for(LinkList i = L->next;i!=NULL;i=i->next){
    LNode *tmp = (LNode*)malloc(sizeof(LNode));
    tmp->data=i->data;
    tmp->next=ls->next;
    ls->next=tmp;
  }
  L=ls;
}
```



## |链表|**带头结点的链式表操作集**

### 1. 实训题目

** 带头结点的链式表操作集**

本题要求实现带头结点的链式表操作集。

### 函数接口定义：

```c++
List MakeEmpty(); 
Position Find( List L, ElementType X );
bool Insert( List L, ElementType X, Position P );
bool Delete( List L, Position P );
```

其中`List`结构定义如下：

```c++
typedef struct LNode *PtrToLNode;
struct LNode {
    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;
```

各个操作函数的定义为：

`List MakeEmpty()`：创建并返回一个空的线性表；

`Position Find( List L, ElementType X )`：返回线性表中X的位置。若找不到则返回ERROR；

`bool Insert( List L, ElementType X, Position P )`：将X插入在位置P指向的结点之前，返回true。如果参数P指向非法位置，则打印“Wrong Position for Insertion”，返回false；

`bool Delete( List L, Position P )`：将位置P的元素删除并返回true。若参数P指向非法位置，则打印“Wrong Position for Deletion”并返回false。

### 裁判测试程序样例：

```c++
#include <stdio.h>
#include <stdlib.h>

#define ERROR NULL
typedef enum {false, true} bool;
typedef int ElementType;
typedef struct LNode *PtrToLNode;
struct LNode {
    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;

List MakeEmpty(); 
Position Find( List L, ElementType X );
bool Insert( List L, ElementType X, Position P );
bool Delete( List L, Position P );

int main()
{
    List L;
    ElementType X;
    Position P;
    int N;
    bool flag;

    L = MakeEmpty();
    scanf("%d", &N);
    while ( N-- ) {
        scanf("%d", &X);
        flag = Insert(L, X, L->Next);
        if ( flag==false ) printf("Wrong Answer\n");
    }
    scanf("%d", &N);
    while ( N-- ) {
        scanf("%d", &X);
        P = Find(L, X);
        if ( P == ERROR )
            printf("Finding Error: %d is not in.\n", X);
        else {
            flag = Delete(L, P);
            printf("%d is found and deleted.\n", X);
            if ( flag==false )
                printf("Wrong Answer.\n");
        }
    }
    flag = Insert(L, X, NULL);
    if ( flag==false ) printf("Wrong Answer\n");
    else
        printf("%d is inserted as the last element.\n", X);
    P = (Position)malloc(sizeof(struct LNode));
    flag = Insert(L, X, P);
    if ( flag==true ) printf("Wrong Answer\n");
    flag = Delete(L, P);
    if ( flag==true ) printf("Wrong Answer\n");
    for ( P=L->Next; P; P = P->Next ) printf("%d ", P->Data);
    return 0;
}
/* 你的代码将被嵌在这里 */
```

### 输入样例：

```in
6
12 2 4 87 10 2
4
2 12 87 5
```

### 输出样例：

```out
2 is found and deleted.
12 is found and deleted.
87 is found and deleted.
Finding Error: 5 is not in.
5 is inserted as the last element.
Wrong Position for Insertion
Wrong Position for Deletion
10 4 2 5 
```

### 2.算法思想

- 函数`MakeEmpty`
  - 生成节点，生成指针，指针指向节点。
- 函数` Find`
  - 枚举节点，找到相同数据则返回
- 函数 `Insert`
  - 枚举节点，找到位置的时候，新建节点，维护链表
- 函数 `Delete`
  - 枚举节点，找到节点并且删除，维护链表。

### 3.算法步骤

#### MakeEmpty 函数

- 新建一个节点`nd`
- 初始化节点`nd`，`nd`的下一节点指向空，数值初始化为`0`
- 新建指针`ptn`，指向`nd`
- 新建`List ls`，`List `也是**指针**，所以直接等于`ptn`即可。
- 返回列表`ls`

#### Find 函数

- 新建循环变量`i`，`i`初始化为`L`，循环终止条件：`i!=NULL`，每次循环`i = i->Next`
- 如果发现`Data`的值为`X`，返回当前节点，即为`i`，返回`i`
- 如果循环结束仍然没有找到，返回`ERROR`

#### Insert 函数

- 设置循环变量`i`，初始化为`i=L`，终止条件`i!=NULL`，循环赋值`i=i->next`

  - 如果`i`的下一个节点为`P`，则进行
    - 新建节点`nd`
    - `nd`的数值初始化为`X`
    - `i`的后继设置为`nd`
    - `nd`的后继设置为`P`
    - 返回 `true` 状态值
  
- 如果没有找到节点：

  - "Wrong Position for Insertion\n"

  - 返回false状态值

#### Delete 函数

- 设置循环变量`i`，初始化为`i=L`，终止条件`i!=NULL`，循环赋值`i=i->next`

- 如果`i`的后继为`P`：

  - `i`的后继设置为`P`的后继
  - 把`P`免费了（`free(P)` 释放内存空间)。
  - 返回`true`状态值

- 如果没有找到`P`：

  - 输出"Wrong Position for Deletion\n“
  - 返回`false`状态值
  

### 4.源代码

```cpp
List MakeEmpty(){
  //struct LNode nd;
  struct LNode ovo;
  struct LNode *nd = (struct LNode*)malloc(sizeof(struct LNode));
  nd->Next=NULL;
  nd->Data=0;
  PtrToLNode ptn = (PtrToLNode)malloc(sizeof(PtrToLNode));
  ptn = nd;
  List ls = (List)malloc(sizeof(List));
  ls=ptn;
  ls->Next=NULL;
  return ls;
}
Position Find(List L, ElementType X){
  for(PtrToLNode i = L;i!=NULL;i=i->Next){
    if(i->Data==X){
      return i;
    }
  }
  return ERROR;
}

bool Insert(List L, ElementType X, Position P){
  for(PtrToLNode i=L;i!=NULL;i=i->Next){
    if(i->Next == P){
      struct LNode *nd = (struct LNode*)malloc(sizeof(struct LNode));
      nd->Data=X;
      i->Next=nd;//i -> nd
      nd->Next=P;// nd ->p
      return true;
    }
  }
  printf("Wrong Position for Insertion\n");
  return false;
}

bool Delete(List L, Position P){
  for(PtrToLNode i=L;i!=NULL;i=i->Next){
    if(i->Next==P){
      i->Next=P->Next;
      free(P);
      return true;
    }
  }
  printf("Wrong Position for Deletion\n");
  return false;
}
```
## |树与二叉树|统计二叉树叶子结点

### 1.实训题目

**统计二叉树叶子结点个数**

本题要求实现一个函数，可统计二叉树的叶子结点个数。

### 函数接口定义：

```c++
int LeafCount ( BiTree T);
```

T是二叉树树根指针，函数`LeafCount`返回二叉树中叶子结点个数，若树为空，则返回0。

### 裁判测试程序样例：

```c++
#include <stdio.h>
#include <stdlib.h>
typedef char ElemType;
typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree Create();/* 细节在此不表 */
int LeafCount ( BiTree T);
int main(){
    BiTree T = Create();
    printf("%d\n", LeafCount(T));
    return 0;
}
/* 你的代码将被嵌在这里 */
```

### 输入样例：

输入为由字母和'#'组成的字符串，代表二叉树的扩展先序序列。例如对于如下二叉树，输入数据：

```in
AB#DF##G##C##
```

### 输出样例（对于图中给出的树）：

![二叉树.png](https://images.ptausercontent.com/aa12f6f6-eb01-4b1e-b103-793c992bdc0b.png#vwid=211&vhei=194)

```out
3
```

### 2. 算法思想

递归遍历树，如果是叶子结点，返回1，每层递归统计，返回和。

### 3. 算法步骤

- 如果遍历到空结点`NULL`，则返回`0`
- 当前层的**计数器**初始化为`0`。
- 如果当前节点的**左子树**和右子树的值都为空，则返回`1`
- 其他情况：递归到**左子树**，然后递归到右子树。
- 返回当前节点的计数器`ans`给上层节点。

### 4. 源代码

```cpp
int LeafCount(BiTree T) {
  if(T==NULL){return 0;}
  int ans = 0 ;
  if(T->lchild==NULL&&T->rchild==NULL){return 1;}
  ans+=LeafCount(T->lchild);
  ans+=LeafCount(T->rchild);
  return ans;
}
```

## |**树与二叉树|二叉树的三种遍历（先序、中序和后序）**

### 1.实训题目

本题要求实现给定的二叉树的三种遍历。

### 函数接口定义：

```c++
void Preorder(BiTree T);
void Inorder(BiTree T);
void Postorder(BiTree T);
```

T是二叉树树根指针，Preorder、Inorder和Postorder分别输出给定二叉树的先序、中序和后序遍历序列，格式为一个空格跟着一个字符。

其中BinTree结构定义如下：

```cpp
typedef char ElemType;
typedef struct BiTNode
{
   ElemType data;
   struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
```

### 裁判测试程序样例：

```c++
#include <stdio.h>
#include <stdlib.h>
typedef char ElemType;
typedef struct BiTNode
{
   ElemType data;
   struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

BiTree Create();/* 细节在此不表 */
void Preorder(BiTree T);
void Inorder(BiTree T);
void Postorder(BiTree T);
int main()
{
   BiTree T = Create();
   printf("Preorder:");   Preorder(T);   printf("\n");
   printf("Inorder:");    Inorder(T);    printf("\n");
   printf("Postorder:");  Postorder(T);  printf("\n");
   return 0;
}
/* 你的代码将被嵌在这里 */
```

### 输入样例：

输入为由字母和'#'组成的字符串，代表二叉树的扩展先序序列。例如对于如下二叉树，输入数据：

```in
AB#DF##G##C##
```

### 输出样例（对于图中给出的树）：

![二叉树.png](https://images.ptausercontent.com/41545570-23e0-4971-b240-dcd21f8986dd.png#vwid=211&vhei=194)

```out
Preorder: A B D F G C
Inorder: B F D G A C
Postorder: F G D B C A
```

### 2. 算法思想

按照不同顺序遍历二叉树。

前序遍历：根 左 右

中序遍历：左 右 根

后序遍历：左 右 根

### 3. 算法步骤

- 如果当前节点是**NULL**节点，则返回
- 对于先序遍历
  - 输出当前节点（也就是根）**T->data**
  - 遍历左子树
  - 遍历右子树
- 对于中序遍历
  - 遍历左子树` T->lchild`
  - 输出当前节点（根节点） `T->data`
  - 遍历右子树 `T->rchild`
- 对于后序遍历
  - 遍历左子树 `T->lchild`
  - 遍历右子树 `T->rchild`
  - 输出当前节点（根节点） `T->data`

### 4. 源代码

```cpp
void Preorder(BiTree T){
  if(T==NULL)return;
  printf(" %c",T->data);
  Preorder(T->lchild);
  Preorder(T->rchild);
}
void Inorder(BiTree T){
  if(T==NULL)return;
  Inorder(T->lchild);
  printf(" %c",T->data);
  Inorder(T->rchild);
}
void Postorder(BiTree T){
  if(T==NULL)return;
  Postorder(T->lchild);
  Postorder(T->rchild);
  printf(" %c",T->data);
}
```



## |**树与二叉树|求二叉树的深度**

### 1.实训题目

** 求二叉树的深度**

本题要求实现一个函数，可返回二叉树的深度。

### 函数接口定义：

```c++
int Depth(BiTree T);
```

T是二叉树树根指针，函数Depth返回二叉树的深度，若树为空，返回0。

### 裁判测试程序样例：

```c++
#include <stdio.h>
#include <stdlib.h>
typedef char ElemType;
typedef struct BiTNode {
  ElemType data;
  struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
BiTree Create(); /* 细节在此不表 */
int Depth(BiTree T);
int main() {
  BiTree T = Create();
  printf("%d\n", Depth(T));
  return 0;
}
/* 你的代码将被嵌在这里 */
```

### 输入样例：

输入为由字母和'#'组成的字符串，代表二叉树的扩展先序序列。例如对于如下二叉树，输入数据：

```in
AB#DF##G##C##
```

### 输出样例（对于图中给出的树）：

![二叉树.png](https://images.ptausercontent.com/f54d8207-3e83-4495-a0da-6042c1ffc677.png#vwid=211&vhei=194)

```out
4
```

### 2. 算法思想

遍历二叉树，每层向上返回：当前层找到的最大深度+1，进而求出深度。

### 3. 算法步骤

- 如果当前节点为空：`NULL` 返回 `0`
- 当前节点可获得的最大深度为：
  - 左子树获得的最大深度+1
  - 右子树获得的最大深度+1
  - 两者取最大值，即位当前节点的最大深度。
  - 取`Depth(T->lchild)+1 `和 `Depth(T->rchild)+1` 的最大值
- 返回当前节点的深度。

### 4. 源代码

```cpp
int max(int x,int y){return x>y?x:y;}
int Depth(BiTree T){
  if(T==NULL)return 0;
  int dep = max(Depth(T->lchild)+1,Depth(T->rchild)+1);
  return dep;
}
```





## **|树与二叉树| 中序输出度为1的结点**

### 1.实训题目

本题要求实现一个函数，按照中序遍历的顺序输出给定二叉树中度为1的结点。

### 函数接口定义：

```c++
void InorderPrintNodes( BiTree T);
```

T是二叉树树根指针，InorderPrintNodes按照中序遍历的顺序输出给定二叉树T中度为1的结点，格式为一个空格跟着一个字符。

其中BiTree结构定义如下：

```cpp
typedef struct BiTNode
{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
```

### 裁判测试程序样例：

```c++
#include <stdio.h>
#include <stdlib.h>
typedef char ElemType;
typedef struct BiTNode
{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

BiTree Create();/* 细节在此不表 */
void InorderPrintNodes( BiTree T);
int main()
{
    BiTree T = Create();
    printf("Nodes are:");
    InorderPrintNodes(T);
    return 0;
}
/* 你的代码将被嵌在这里 */
```

### 输入样例：

输入为由字母和'#'组成的字符串，代表二叉树的扩展先序序列。例如对于如下二叉树，输入数据：

```in
ACG#H###BEF###D##
```

### 输出样例（对于图中给出的树）：

![二叉树.PNG](https://images.ptausercontent.com/4c75f496-356e-4e4a-8c13-020cbcfd7647.PNG#vwid=220&vhei=153)

```out
Nodes are: G C E
```

### 2. 算法思想

按照题目要求，先序遍历二叉树，如果当前节点的出度为1，则输出当前节点。

### 3. 算法步骤

- 如果当前节点为**空**:`NULL` 则返回
- 根据**先序**遍历，遍历**左子树**
- 如果当前节点的出度之和是1，则输出：
  - T的左子树不等于空，结果是0或者1
  - T的右子树不等于空，结果是0或者1
  - 取两者的和
  - 当且仅当：左子树为空右子树不为空，或者，右子树为空左子树不为空  。此时的和为1
  - 则进行输出

### 4. 源代码

```cpp
void InorderPrintNodes( BiTree T){
  if(T==NULL)return ;
  InorderPrintNodes(T->lchild);
  if((T->lchild!=NULL) +  (T->rchild!=NULL) == 1){
    printf(" %c",T->data);
  }
  InorderPrintNodes(T->rchild);
}
```



## |树与二叉树|后记|调试代码与建树

因为OI的习惯，实在习惯不了在PTA在线打代码和这样子调试，运行超级慢，效率超级低。

还是希望可以在本地运行和调试代码。

于是题目虽然是函数题，但是其实也可以补全。

于是按照要求，建了棵树。

能用递归写的，其实用循环写也没问题，就是得多个状态栈，所以还是直接用递归建树啦。

有一个稍微坑点的地方是：读入根节点data的问题，如果读入了一次，递归到子树再读一遍，读入流指针就可能不对劲啦。

想了想跟回退读入流指针相比，还是递归的时候传一个上一次读到的节点。

```cpp
void build_tree(BiTree T,char last){
  T->data=last;
  T->lchild=NULL;
  T->rchild=NULL;
  char l_data,r_data;
  scanf("%c",&l_data);
  if(l_data!='#'){
    BiTree tmp = (BiTree)malloc(sizeof(BiTNode));
    tmp->data=l_data;
    tmp->lchild=NULL;
    tmp->rchild=NULL;
    T->lchild=tmp;
    build_tree(T->lchild,l_data);
  }
  scanf("%c",&r_data);
  if(r_data!='#'){
    BiTree tmp=(BiTree)malloc(sizeof(BiTNode));
    tmp->data=r_data;
    tmp->lchild=NULL;
    tmp->rchild=NULL;
    T->rchild=tmp;
    build_tree(T->rchild,r_data);
  }
}
BiTree Create(){
  BiTree tree = (BiTree)malloc(sizeof(BiTNode));
  char root;
  scanf("%c",&root);//读入根节点
  tree->data = root;
  build_tree(tree,root);
  return tree;
}
```

写完这两行字，我就意识到，不需要传这个last变量，只需要在开始的时候读一下根节点，其他的都不需要特殊处理。

这样就是下面的代码啦

```cpp
void build_tree(BiTree T){
  // T->data=last;
  T->lchild=NULL;
  T->rchild=NULL;
  char l_data,r_data;
  scanf("%c",&l_data);
  if(l_data!='#'){
    BiTree tmp = (BiTree)malloc(sizeof(BiTNode));
    tmp->data=l_data;
    tmp->lchild=NULL;
    tmp->rchild=NULL;
    T->lchild=tmp;
    build_tree(T->lchild);
  }
  scanf("%c",&r_data);
  if(r_data!='#'){
    BiTree tmp=(BiTree)malloc(sizeof(BiTNode));
    tmp->data=r_data;
    tmp->lchild=NULL;
    tmp->rchild=NULL;
    T->rchild=tmp;
    build_tree(T->rchild);
  }
}

BiTree Create(){
  BiTree tree = (BiTree)malloc(sizeof(BiTNode));
  char root;
  scanf("%c",&root);//读入根节点
  tree->data = root;
  build_tree(tree);
  return tree;
}
```

## |栈、队列、串、数组、广义表|手写栈

### 1.实训题目

手写一个栈

### 2.算法思想

使用数组来表示栈，定义一个数表示指针。

### 3.算法步骤

- `sz`数组存储栈元素
- `top`存储栈顶位置在哪
- `get_top()`函数
  - 返回栈顶元素，由于`top`表示栈顶，也就是`sz[top]`
- `pop()`函数
  - 弹出元素，实际上就是直接让`top-1`即可。
- `empty()`函数
  - 判断栈是否为空。
  - 如果`top`小于等于`0`，则说明已经弹出完成或者过度弹出，返回`0`
  - `top`大于等于`1`，说明栈中还有元素
- `push(int x)`函数
  - `top`指针自增
  - 然后元素赋值到`sz[top]`中

### 4.源代码

```cpp
#include<stdio.h>

#define maxn 12345

struct stack{
  int sz[maxn];
  int top;
  stack(){//结构体构造函数，初始化。
    top=0;
  }
  int get_top(){return sz[top];}//返回栈顶元素
  bool pop(){//弹出栈顶元素。
    if(top<=0){
      return false;
    }
    top--;
    return true; 
  }
  int empty(){//栈是否为空
    if(top>=1)return 0;
    return 1;
  }
  void push(int x){//向栈添加元素
    sz[++top]=x;
  }
}st;

int main(){
  for(int i=1;i<=5;++i){
    st.push(i);
  }
  for(;!st.empty();){
    printf("%d ",st.get_top());
    st.pop();
  }
  for(int i=6;i<=10;++i){
    st.push(i);
  }
  for(;!st.empty();){
    printf("%d ",st.get_top());
    st.pop();
  }
}
```

### 5. 代码输出

```cpp
5 4 3 2 1 10 9 8 7 6
```



## |栈、队列、串、数组、广义表|手写队列

### 1.实训题目

手写非循环队列

### 2.算法思想

设置一个头指针，设置一个尾指针。

分别为指向队列的头和尾。

### 3.算法步骤

- `sz` 数组保存数据
- `head `表示队列头
- `tail `表示队列的尾

- 函数 `queue()` 构造函数
  - `head = 1`
  - `tail  = 1`
  - 让两者都指向第一个元素。
- 函数 `front() `返回队列的头
  - `head`指向队列的头，所以直接返回`sz[head]`即可
- 函数 `pop()` 弹出元素
  - 让`head `自增即可。
  - 但这样的缺点是，之前的空间被浪费了，无法再次利用。
  - 解决这个问题可以直接队列和链表相结合，这样就可以释放不需要的空间。也可以使用循环队列。
- 函数 `empty()` 判断是否为空
  - 只需要判断头（`head`）是否大于尾巴（`tail`）即可。
    - 如果头大于等于尾巴则说明已经为空
    - 不然不为空
- 函数 `push(int x) `向队列添加元素
  - 尾巴自增（`tail++`)
  - 向尾巴指向的数组的位置修改为`x`

### 4.源代码

```cpp
#include<stdio.h>
#define maxn 23333
struct queue{//手写非循环队列
  int sz[maxn<<1];
  int tail;
  int head;
  queue(){
    head = 1;
    tail = 1;
  }
  int front(){
    return sz[head];
  }
  void pop(){
    head++;
    return; 
  }
  int empty(){
    if(head>=tail)return 1;
    return 0;
  }
  void push(int x){
    sz[tail++]=x;
  }
};

int main(){
  struct queue q;
  for(int i=1;i<=10;++i)q.push(i);
  for(;!q.empty();){
    printf("%d ",q.front());
    q.pop();
  }
}
```

### 5.代码输出

```cpp
1 2 3 4 5 6 7 8 9 10
```





## |栈、队列、串、数组、广义表|KMP

### 1.实训题目

![pic](/media/6e/6e09d8d78a82d31685b7347590e3a4b2c6cd2b6523dab31c37e94cf71a2d8c00.png#vwid=1275&vhei=844)

### 2.算法思想

KMP数组记录模式串匹配失败之后的模式串的**前缀**和**后缀**的**最大的相同的位置**。

而在匹配过程中，避免多余的重复匹配，匹配失败后，直接跳到最大的按位相等的地方即可。

### 3.算法步骤

- `kmp`数组的求解：

  - `kmp[i]`记录的是，当模式串匹配到第`i`位的时候失败了，进行自我跳转。
  - 从第二个字符开始自我匹配（此处数组从下标1开始存储），如果自我匹配失败，则进行自我跳回。直到跳回到开始的位置或者再次相等的地方。
  - 如果自我匹配成功，则可以让j指针自增，同时`kmp`数组的第`i`位，即当前位置，设置为`j`

- KMP匹配

  - 求出模式串和主串的长度分别为`len`和`len_p`
  - 匹配主串，如果匹配失败，直接通过j指针的跳转到`kmp[j]`，回退。
  - 如果相等则j指针自增，直到发现j指针的大小与模式串的长度相同，则此处匹配成功。

- 复杂度分析：

  - 观察`kmp`数组的求出过程后，可以发现，while语句几乎是在几跳中就彻底完成，时间基本上不会占用，因此实现基本上是O（N+与M一次方相关的数）
  - 具体的分析大概如下：

  - 来自山东OI选手`rqy`：每次位置指针`i++`，匹配失败的指针j最多增加一次，所以j最多增加`len`次，所以是O(N的长度+M的长度)=O(N+M)

### 4.源代码

```cpp
#include<bits/stdc++.h>
const int maxn=1e6+8;

char s1[maxn];
char s2[maxn];

int kmp[maxn];

void getnext(){
  int j=0;
  //kmp[0]=kmp[1]=0;
  int len = strlen(s2+1);
  for(int i=2;i<=len;++i){
    while(j!=0 && s2[i]!=s2[j+1])j=kmp[j];
    if(s2[i]==s2[j+1])j++;
    kmp[i]=j;//赋值
  }
}
void KMP(){
  int j =0;
  int len=strlen(s1+1);
  int len_p=strlen(s2+1);
  for(int i=1;i<=len;++i){
    while(j&&s1[i]!=s2[j+1])j=kmp[j];
    if(s1[i]==s2[j+1])j++;
    if(j==len_p){
      printf("%d\n",i-len_p+1);
    }
  }
}

int main(){
  using namespace std;
  cin>>s1+1;
  cin>>s2+1;
  getnext();
  KMP();
  int len=strlen(s2+1);
  for(int i=1;i<=len;++i)printf("%d ",kmp[i]);
}
//洛谷通过
//第一次写KMP（之前manacher懂了KMP也没能会写，多少有些参考）
```

### 5.代码输出

![pic](/media/80/8032d3069975270d0325f195629de58dfb435bb5cf4a40fba809f0b400f30c3f.png#vwid=1222&vhei=666)





## |栈、队列、串、数组、广义表|递归广义表

### 1.实训题目

E = (a,E)

### 2.算法思想

元素。自己指向自己

### 3.算法步骤

- 申请个内存
- 自己指向自己。（`ovo->ptr=ovo`)
- data赋值(` ovo->data=233`)
- 枚举元素`i`作为指针：初始化为:`ovo`,终止条件`i!=NULL`，循环赋值`i=i->ptr`
  - 输出信息

### 4.源代码

```cpp
#include<stdlib.h>
#include<stdio.h>
typedef struct Node{
  int data;
  struct Node *ptr;
}nd,*point;
int main(){
  point ovo = (point)malloc(sizeof(Node));
  ovo->ptr=ovo;
  ovo->data=233;
  for(point i = ovo;i!=NULL;i=i->ptr){
    printf("[data:%d ptr:%x]->",i->data,i->ptr);
  }
}
```

### 5.代码输出

```cpp
[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]->[data:233 ptr:781400]....
```

##  **|图论|图的基本概念与表示**

### 1.实训题目

请根据下图给出：

（1）每个顶点的度

（2）邻接矩阵

（3）邻接表

![图片1.png](https://images.ptausercontent.com/82746318-d63a-410d-aad8-d5893a8e6e73.png#vwid=200&vhei=219)

### 2. 算法思想

邻接表，建表，然后统计每个点的出度。

图可表示为

```bash
8
a b 15
a c 2
a d 12
b e 6
c e 8 
c f 4
d g 3
e g 9
f g 10
f d 5
g b 4
```



通过网站可以再次二次确认一下图是否正确：

<https://csacademy.com/app/graph_editor/>

![image-20221201184359220](/media/0d/0d17f23aafee6af3e6d517c0934b105a9355daa6eb6023538ac1b64d4c774dde.png#vwid=1647&vhei=817)



如果进行数字字母映射，可以得到这个表

`t1.in`

```bash
7 11
1 2 15
1 3 2
1 4 12
2 5 6
3 5 8
3 6 4
4 7 3
5 7 9
6 7 10
6 4 5
7 2 4
```

### 3. 算法步骤

先建立一个邻接表，`fst`数组存链表头，`Edge`结构体存链表。

`Edge`结构体内包含：`u,v,w,nxt`  分别是边的起点`u`，终点`v`，权值`w`，和链表的下一条边。

`cnt`作为`edge`的指针，表示边的序号。

因为是有向图，所以开的边最好是两倍。

`N` 为 点的数量

`M` 为 边的数量



#### `inline x map_fun(x)`函数

```cpp
inline char map_fun(int x){return 'a'+x-1;}//这俩好用
inline int map_fun(char x){return x-'a'+1;}//这俩好用
```

两个函数，分别实现了，将数字映射到字符 和 将字符映射到数字两个功能。

具体实现做法: 

- 数字 -> 字符 :
  - **'a'的值**（65） **减**一，然后加上**偏移量x**
- 字符->数字:
  - **偏移量**减去**基础偏移'a'(65)**，**加**一

#### `addedge(int u,int v,int w)`函数

也是链表的实现方法。

使用的是头插法进行。

这部分因为OI时期写习惯了，就用int作为指针啦。

传入的参数有，u，v，w

- 首先让cnt自增。

- 然后分别进行赋值edge[cnt].u =u，edge[cnt].v= v edge[cnt].w= w
- 当前节点的后继指针设置为 u 点的链表头，也就是fst[u]
- 让u点的链表头指针，指向当前节点，也就是cnt。

这样就完成了边的添加。

#### `inline void addedge_mat(int u,int v,int w) `函数

邻接矩阵。传入的参数有`u`,`v`,`w`。

只需要`matrix[u][v]=w;`

建立边即可。

#### `inline int get_in_deg(int u)`函数

求入度，这里用了最暴力的方式来计算，也就是枚举所有的边。

然后进行统计。

先枚举所有的节点

- 计数器`ans`初始化为`0`

- `i`为循环变量，`i`从`1->N`，每次`i`进行自增。
  - j为循环变量初始化为`fst[i]`，循环条件：`j`（`j!=0`)，每次循环进行赋值`j = edge[j].nxt`即为：从链表头开始，每次赋值为后继，直到无法找到下一个后继为止
    - 过程中，`uu` 设置为当前边的 u 即为`edge[j].u`，`vv`设置为当前边的`v`即为`edge[j].v`，`ww`则为`edge[j].w`也就是当前边的权值。
    - 如果发现当前边指向`u` 也就是 `vv`=`u`，则计算边权和。
- 最后输出边权和`ans`



其实入度和出度可以在邻接表建立的时候进行维护，没必要在这里求。

#### `inline int get_out_deg(int u)` 函数

- 跟上一个基本上是同理滴。u为要计算出度的节点。
- 初始化计数器变量`ans` 设置为0
- `i`为循环变量初始化为`fst[u]`，循环条件：`i`（`i!=0`)，每次循环进行赋值`i = edge[i].nxt`即为：从链表头开始，每次赋值为后继，直到无法找到下一个后继为止
  - 统计当前边的边权，加到`ans`变量内。
- 返回`ans`变量作为答案



#### 在`addedge`函数内记录出入度

在维护邻接表之后，添加下面两行即可。

```cpp
in_deg[v]+=w;
out_deg[u]+=w;
```

分别让v的入度加w

让u的出度加w

添加这两个函数即可，这样就可以`O(1)`的时间复杂度求出入度和出度。

```cpp
inline int get_ind_o1(int u){return in_deg[u];}
inline int get_outd_o1(int u){return out_deg[u];}
```

### 4. 源代码

```cpp
#include<iostream>
#include<cstdio>

char map[]={-1,'a','b','c','d','e','f','g','h'};//用于查对应关系
//1号节点对应着a；2号节点对应着b
inline char map_fun(int x){return 'a'+x-1;}
inline int map_fun(char x){return x-'a'+1;}
int M;
int N;
const int maxn=1234;
struct Edge{
  int u,v,w;
  int nxt;
}edge[maxn<<1];
int cnt =0;
int fst[maxn];
int in_deg[maxn];
int out_deg[maxn];

inline void addedge(int u,int v, int w){//感觉是默写出来的
  edge[++cnt].u=u,edge[cnt].v=v,edge[cnt].w=w;
  edge[cnt].nxt=fst[u];
  fst[u]=cnt;
  //下面两行维护入度和出度
  in_deg[v]+=w;
  out_deg[u]+=w;
}


inline int get_out_deg(int u){//暴力求出度
  int ans = 0;
  for(int i=fst[u];i;i=edge[i].nxt){
    ans+=edge[i].w;
  }
  return ans;
}
inline int get_in_deg(int u){//暴力求入度
  int ans= 0;
  for(int i=1;i<=N;++i){
    for(int j=fst[i];j;j=edge[j].nxt){
      int uu = edge[j].u;
      int vv = edge[j].v;
      int ww = edge[j].w;
      if(vv==u)ans+=ww;
    }
  }
  return ans;
}

inline int get_ind_o1(int u){return in_deg[u];}//O1求出度和入度
inline int get_outd_o1(int u){return out_deg[u];}

int matrix[11][11];
inline void addedge_mat(int u,int v,int w){//邻接矩阵
  matrix[u][v]=w;
}
inline void show_mat(){//打印邻接矩阵，并且好看一点
  printf("-------------mat-------------\n");
  for(int j=0;j<=N;++j){
    printf("%5c ",map_fun(j));
  }
  printf("\n");
  for(int i=1;i<=N;++i){
    printf("%5c ",map_fun(i));
    for(int j=1;j<=N;++j){
      printf("%5d ",matrix[i][j]);
    }
    printf("\n");
  }
  printf("-------------mat-------------\n\n");
}

inline void show_edge(){//打印邻接表，并且好看一点
  for(int i=1;i<=N;++i){
    printf("%c:",map_fun(i));
    for(int u = fst[i];u;u=edge[u].nxt){
      // if(u==fst[i])printf("[first]")
      int uu=edge[u].u;
      int vv=edge[u].v;
      int ww=edge[u].w;
      int nxt=edge[u].nxt;
      printf("->[u:%d v:%d w:%d nxt:%d]",uu,vv,ww,nxt);
    }
    printf("\n");
  }
}

int main(){
  using namespace std;
  freopen("t1.in","r",stdin);//读入文件
  
  cin>>N>>M;
  for(int i=1;i<=M;++i){
    int u,v,w;
    cin>>u>>v>>w;//读入边
    addedge(u,v,w);//邻接表
    addedge_mat(u,v,w);//邻接矩阵
  }
  show_mat();//显示邻接矩阵

  //计算入度，出度
  int sum_in_deg=0;
  int sum_out_deg=0;
  for(int i=1;i<=N;++i){//计算出度和入度和和，并且打印。用两种方法计算，答案一样。
    sum_in_deg+=get_in_deg(i);
    sum_out_deg+=get_out_deg(i);
    printf("%c out_deg: %d in_deg:%d deg:%d\n",map_fun(i),get_out_deg(i),get_in_deg(i),get_ind_o1(i)+get_outd_o1(i));
  }
  printf("sum_in_deg:%d sum_out_deg:%d\n",sum_in_deg,sum_out_deg);
  //
  printf("\n-------------edge-------------\n");
  show_edge();//打印邻接矩阵
  printf("-------------edge-------------\n");
}
```



### 5. 代码输出

```cpp
-------------mat-------------
    `     a     b     c     d     e     f     g
    a     0    15     2    12     0     0     0
    b     0     0     0     0     6     0     0
    c     0     0     0     0     8     4     0
    d     0     0     0     0     0     0     3
    e     0     0     0     0     0     0     9
    f     0     0     0     5     0     0    10
    g     0     4     0     0     0     0     0
-------------mat-------------

a out_deg: 29 in_deg:0 deg:29
b out_deg: 6 in_deg:19 deg:25
c out_deg: 12 in_deg:2 deg:14
d out_deg: 3 in_deg:17 deg:20
e out_deg: 9 in_deg:14 deg:23
f out_deg: 15 in_deg:4 deg:19
g out_deg: 4 in_deg:22 deg:26
sum_in_deg:78 sum_out_deg:78

-------------edge-------------
a:->[u:1 v:4 w:12 nxt:2]->[u:1 v:3 w:2 nxt:1]->[u:1 v:2 w:15 nxt:0]
b:->[u:2 v:5 w:6 nxt:0]
c:->[u:3 v:6 w:4 nxt:5]->[u:3 v:5 w:8 nxt:0]
d:->[u:4 v:7 w:3 nxt:0]
e:->[u:5 v:7 w:9 nxt:0]
f:->[u:6 v:4 w:5 nxt:9]->[u:6 v:7 w:10 nxt:0]
g:->[u:7 v:2 w:4 nxt:0]
-------------edge-------------
```

应该不用手画图了吧，代码都是自己写的。



## **|图论|图的存储结构+遍历序列**

### 1.实训题目

**8-2 图的存储结构+遍历序列**

设有下列无向图：
（1）画出该图的邻接矩阵。（3分）
（2）画出该图的邻接表。（3分）
（3）从V1出发，按照（1）中存储结构，写出深度优先遍历序列（3分）；
（4）从V1出发，按照（1）中存储结构，写出广度优先遍历序列（3分）；

![t4.png](/media/d0/d073439442e24b1e96ca325d136bbf1c151f1d9f04291d2943999cb5c136c81f.png#vwid=221&vhei=159)

### 2. 算法思想

邻接表邻接矩阵跟上一个题目一样啦。

分别进行深度优先和广度优先遍历就好啦。

深度的话dfs到头就好。

广度的话用一个队列作为辅助即可。

题目转换

`t2.in`

```bash
6 10
1 2
1 3 
1 4
2 3
2 5
3 4
3 5
3 6
4 6
5 6
```

![pic](/media/e6/e69726a1ba73d57e104d9d508ef9b99211eff83850b1b7ef46bbe5f336f84871.png#vwid=1477&vhei=736)



### 3. 算法步骤

- 邻接矩阵和邻接表的遍历和输出同上面一样啦。
  - 邻接矩阵 打印二维数组
  - 邻接表 遍历每个点，然后遍历链表的每个节点就可以啦
- DFS 遍历
  - vis 数组记录的是当前节点是否已经遍历过，避免循环遍历。
  - 遍历当前节点的所有边，如果指向的边没有被遍历过，则进行遍历。
    - 起始条件：`i = fst[u]`，当`i==0`的时候终止，每次循环：`i=edge[i].nxt`
    - 如果目标点没有被遍历过，则标记该节点已经遍历了，递归遍历目标节点`dfs(vv)`
- BFS 遍历（代码中遍历了两次，一次用了STL的队列，一次用的手写的简单的队列）
  - 定义一个队列`q`
  - 函数传参`u`，将`u`加入到队列中。
  - 循环：直到队列为空
    - 从队列中取出元素`now_u`
    - 输出当前节点。
    - 遍历`now_u`的所有边，如果指向的节点没有被访问到，则加入到队列中。
    - 不断循环此过程，直到队列为空为止。

###  4. 源代码

```cpp
#include<bits/stdc++.h>
int M;
int N;
const int maxn=1234;
struct Edge{
  int u,v,w;
  int nxt;
}edge[maxn<<1];
int cnt =0;
int fst[maxn];
int in_deg[maxn];
int out_deg[maxn];
inline void addedge(int u,int v, int w){//感觉是默写出来的
  edge[++cnt].u=u,edge[cnt].v=v,edge[cnt].w=w;
  edge[cnt].nxt=fst[u];
  fst[u]=cnt;
}

int matrix[11][11];
inline void addedge_mat(int u,int v,int w){//邻接矩阵
  matrix[u][v]=w;
  matrix[v][u]=w;
}


inline void show_mat(){//打印邻接矩阵，并且好看一点
  printf("-------------mat_start-------------\n");
  for(int j=0;j<=N;++j){//打印横着的坐标
    printf("v%d    ",j);
  }
  printf("\n");//换行
  for(int i=1;i<=N;++i){
    printf("v%d %5",i);//竖着的坐标
    for(int j=1;j<=N;++j){
      printf("%5d ",matrix[i][j]);//矩阵数据
    }
    printf("\n");
  }
  printf("-------------mat_end-------------\n\n");
}

inline void show_edge(){//打印邻接表，并且好看一点
  printf("-------------edge_start-------------\n");
  for(int i=1;i<=N;++i){
    printf("v%d:",i);
    for(int u = fst[i];u;u=edge[u].nxt){
      int uu=edge[u].u;
      int vv=edge[u].v;
      int ww=edge[u].w;
      int nxt=edge[u].nxt;
      printf("->[u:%d v:%d w:%d nxt:%d]",uu,vv,ww,nxt);
    }
    printf("\n");
  }
  printf("-------------edge_end-------------\n");
}

struct queue2{//非循环队列
  int sz[maxn<<1];
  int tail;
  int head;
  queue2(){
    head = 1;
    tail = 1;
  }
  int front(){
    return sz[head];
  }
  void pop(){
    head++;
    return; 
  }
  int empty(){
    if(head>=tail)return 1;
    return 0;
  }
  void push(int x){
    sz[tail++]=x;
  }
};

int vis[maxn];
void dfs(int u){
  if(!vis[u]){
    printf("[v%d]",u);
    vis[u]=1;
  }else{
    printf("->[v%d]",u);
  }
  

  for(int i=fst[u];i;i=edge[i].nxt){
    int uu = edge[i].u;
    int vv = edge[i].v;
    if(!vis[vv]){
      vis[vv]=1;
      dfs(vv);
    }
  }
}


void bfs(int u){
  std::queue <int> q;
  q.push(u);
  for(;!q.empty();){
    int now_u = q.front();
    q.pop();
    vis[now_u]=1;
    printf("[v%d]",now_u);
    for(int i = fst[now_u];i;i=edge[i].nxt){
      int uu = edge[i].u;
      int vv = edge[i].v;
      // printf("de:%d->%d\n",uu,vv);
      if(!vis[vv]){
        vis[vv]=1;
        q.push(vv);
      }
    }
  }
}



void bfs2(int u){
  queue2 q;
  q.push(u);
  for(;!q.empty();){
    int now_u = q.front();
    q.pop();
    vis[now_u]=1;
    printf("[v%d]",now_u);
    for(int i = fst[now_u];i;i=edge[i].nxt){
      int uu = edge[i].u;
      int vv = edge[i].v;
      // printf("de:%d->%d\n",uu,vv);
      if(!vis[vv]){
        vis[vv]=1;
        q.push(vv);
      }
    }
  }
}


int main(){
  freopen("t2.in","r",stdin);
  using namespace std;
  cin>>N>>M;//读入节点和边
  for(int i=1;i<=M;++i){//读入边
    int u,v,w;
    cin>>u>>v;
    addedge(u,v,1);//无向图两次加边
    addedge(v,u,1);
    addedge_mat(u,v,1);
  }

  show_mat();
  show_edge();

  printf("\n------------dfs_start-------------\n");
  for(int i=1;i<=N;++i)vis[i]=0;//清空数组。
  dfs(1);
  printf("\n-------------dfs_end-------------\n");

  printf("\n------------bfs_start-------------\n");
  for(int i=1;i<=N;++i)vis[i]=0;//清空数组。
  bfs(1);//STL 队列
  printf("\n------------bfs_end-------------\n");


  printf("\n------------bfs_start-------------\n");
  for(int i=1;i<=N;++i)vis[i]=0;//清空数组。
  bfs2(1);//手写队列 非循环队列
  printf("\n------------bfs_end-------------\n");

}
```

### 程序输出

```cpp
-------------mat_start-------------
v0    v1    v2    v3    v4    v5    v6
v1     0     1     1     1     0     0
v2     1     0     1     0     1     0
v3     1     1     0     1     1     1
v4     1     0     1     0     0     1
v5     0     1     1     0     0     1
v6     0     0     1     1     1     0
-------------mat_end-------------

-------------edge_start-------------
v1:->[u:1 v:4 w:1 nxt:3]->[u:1 v:3 w:1 nxt:1]->[u:1 v:2 w:1 nxt:0]
v2:->[u:2 v:5 w:1 nxt:7]->[u:2 v:3 w:1 nxt:2]->[u:2 v:1 w:1 nxt:0]
v3:->[u:3 v:6 w:1 nxt:13]->[u:3 v:5 w:1 nxt:11]->[u:3 v:4 w:1 nxt:8]->[u:3 v:2 w:1 nxt:4]->[u:3 v:1 w:1 nxt:0]
v4:->[u:4 v:6 w:1 nxt:12]->[u:4 v:3 w:1 nxt:6]->[u:4 v:1 w:1 nxt:0]
v5:->[u:5 v:6 w:1 nxt:14]->[u:5 v:3 w:1 nxt:10]->[u:5 v:2 w:1 nxt:0]
v6:->[u:6 v:5 w:1 nxt:18]->[u:6 v:4 w:1 nxt:16]->[u:6 v:3 w:1 nxt:0]
-------------edge_end-------------

------------dfs_start-------------
[v1]->[v4]->[v6]->[v5]->[v3]->[v2]
-------------dfs_end-------------

------------bfs_start-------------
[v1][v4][v3][v2][v6][v5]
------------bfs_end-------------

------------bfs_start-------------
[v1][v4][v3][v2][v6][v5]
------------bfs_end-------------
```

