数据结构与算法实验报告

|顺序表|顺序表的查找操作

1. 实训题目

本题要求实现一个函数，要求从顺序表中查找指定元素，并返回第一个查找成功的元素在表中的位置序号，若查找失败，则返回0；

函数接口定义：

int LocateElem(SqList L,ElemType e);

其中SqList结构定义如下：

typedef struct{
    ElemType *elem;
    int length;
 }SqList;

裁判测试程序样例：

#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. 源代码

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；

函数接口定义：

int ListInsert(SqList &L,int i,ElemType e);

其中SqList结构定义如下：

typedef struct{
    ElemType *elem;
    int length;
}SqList;

裁判测试程序样例：

#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.源代码

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；

函数接口定义：

int ListDelete(SqList &L,int i);

其中SqList结构定义如下：

typedef struct{
    ElemType *elem;
    int length;
 }SqList;

裁判测试程序样例：

#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. 源代码

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。题目保证顺序表中所有元素都为正整数。

函数接口定义：

int GetMax(SqList L);

其中SqList结构定义如下：

typedef struct{
    ElemType *elem;
    int length;
}SqList;

裁判测试程序样例：

#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. 源代码

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;
}

|顺序表|后记

过程中用了这个调试代码来初始化和调试

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.实训题目

本题要求实现一个函数，求带头结点的单链表的表长。

函数接口定义：

int Length ( LinkList L );

其中LinkList结构定义如下：

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

L是带头结点的单链表的头指针，函数Length返回单链表的长度。

裁判测试程序样例：

#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;
}
/* 你的代码将被嵌在这里 */

输入样例：

2 1 4 5 3 -1

输出样例：

5

2. 算法思想

枚举每个节点，然后计数器自增。

3. 算法步骤

  • 申请一个临时变量siz作为计数器，并且初始化为0
  • 让i从L-next开始，每次赋值为i->next
  • 每次循环进行加1
  • 返回siz

4. 源代码

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。

函数接口定义：

int insert_link ( LinkList L,int i,ElemType e);

L是单链表的头指针，i为插入位置，e是插入的数据元素，插入成功返回1，否则返回0。

裁判测试程序样例：

#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不算在序列内，不要处理）。所有数据之间用空格分隔。
第二行数据是插入位置，第三行数据是被插入元素值。

输入样例：

1 2 3 4 5 6 -1
2 
100

输出样例：

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.源代码

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。

函数接口定义：

int delete_link ( LinkList L,int i);

L为单链表的头指针，i为删除结点的序号。

裁判测试程序样例：

#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不算在序列内，不要处理）。所有数据之间用空格分隔。
第二行数据是删除位置。

输入样例：

1 2 3 4 5 6 -1
3

输出样例：

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.源代码

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. 实训题目

求单链表元素序号

本题要求实现一个函数，求带头结点的单链表中元素序号。

函数接口定义：

int Locate ( LinkList L, ElemType e);

L是带头结点的单链表的头指针，e是要查找的元素值。如果e在单链表中存在，函数Locate返回其序号（序号从1开始）；否则，返回0。

裁判测试程序样例：

#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;
}
/* 你的代码将被嵌在这里 */

输入样例：

2 1 4 5 3 -1
5

输出样例：

4

2.算法思想

枚举结点，同时计数。

3.算法步骤

  • 设置变量cnt 初始化为0，用于计数

  • 设置循环变量i，初始化为i=L-next，终止条件i!=NULL，循环赋值i=i->next

    • 循环内 cnt 自增

    • 循环内进行判断，当前节点的data值是否为e

      • 如果为e 则返回cnt的值
  • 如果循环结束没有进行返回，则说明cnt不存在，返回0。

4.源代码

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。

函数接口定义：

void ListReverse_L(LinkList &L);

其中 L 是一个带头结点的单链表。

裁判测试程序样例：

//库函数头文件包含
#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个整数，中间用空格隔开。

输出格式：

输出逆置后顺序表的各个元素，两个元素之间用空格隔开，最后一个元素后面没有空格。

输入样例：

4
1 2 3 4

输出样例：

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.源代码

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. 实训题目

带头结点的链式表操作集

本题要求实现带头结点的链式表操作集。

函数接口定义：

List MakeEmpty(); 
Position Find( List L, ElementType X );
bool Insert( List L, ElementType X, Position P );
bool Delete( List L, Position P );

其中List结构定义如下：

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。

裁判测试程序样例：

#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;
}
/* 你的代码将被嵌在这里 */

输入样例：

6
12 2 4 87 10 2
4
2 12 87 5

输出样例：

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.源代码

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.实训题目

统计二叉树叶子结点个数

本题要求实现一个函数，可统计二叉树的叶子结点个数。

函数接口定义：

int LeafCount ( BiTree T);

T是二叉树树根指针，函数LeafCount返回二叉树中叶子结点个数，若树为空，则返回0。

裁判测试程序样例：

#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;
}
/* 你的代码将被嵌在这里 */

输入样例：

输入为由字母和'#'组成的字符串，代表二叉树的扩展先序序列。例如对于如下二叉树，输入数据：

AB#DF##G##C##

输出样例（对于图中给出的树）：

二叉树.png

3

2. 算法思想

递归遍历树，如果是叶子结点，返回1，每层递归统计，返回和。

3. 算法步骤

  • 如果遍历到空结点NULL，则返回0
  • 当前层的计数器初始化为0。
  • 如果当前节点的左子树和右子树的值都为空，则返回1
  • 其他情况：递归到左子树，然后递归到右子树。
  • 返回当前节点的计数器ans给上层节点。

4. 源代码

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.实训题目

本题要求实现给定的二叉树的三种遍历。

函数接口定义：

void Preorder(BiTree T);
void Inorder(BiTree T);
void Postorder(BiTree T);

T是二叉树树根指针，Preorder、Inorder和Postorder分别输出给定二叉树的先序、中序和后序遍历序列，格式为一个空格跟着一个字符。

其中BinTree结构定义如下：

typedef char ElemType;
typedef struct BiTNode
{
   ElemType data;
   struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

裁判测试程序样例：

#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;
}
/* 你的代码将被嵌在这里 */

输入样例：

输入为由字母和'#'组成的字符串，代表二叉树的扩展先序序列。例如对于如下二叉树，输入数据：

AB#DF##G##C##

输出样例（对于图中给出的树）：

二叉树.png

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. 源代码

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.实训题目

求二叉树的深度

本题要求实现一个函数，可返回二叉树的深度。

函数接口定义：

int Depth(BiTree T);

T是二叉树树根指针，函数Depth返回二叉树的深度，若树为空，返回0。

裁判测试程序样例：

#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;
}
/* 你的代码将被嵌在这里 */

输入样例：

输入为由字母和'#'组成的字符串，代表二叉树的扩展先序序列。例如对于如下二叉树，输入数据：

AB#DF##G##C##

输出样例（对于图中给出的树）：

二叉树.png

4

2. 算法思想

遍历二叉树，每层向上返回：当前层找到的最大深度+1，进而求出深度。

3. 算法步骤

  • 如果当前节点为空：NULL 返回 0

  • 当前节点可获得的最大深度为：

    • 左子树获得的最大深度+1
    • 右子树获得的最大深度+1
    • 两者取最大值，即位当前节点的最大深度。
    • 取Depth(T->lchild)+1 和 Depth(T->rchild)+1 的最大值
  • 返回当前节点的深度。

4. 源代码

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的结点。

函数接口定义：

void InorderPrintNodes( BiTree T);

T是二叉树树根指针，InorderPrintNodes按照中序遍历的顺序输出给定二叉树T中度为1的结点，格式为一个空格跟着一个字符。

其中BiTree结构定义如下：

typedef struct BiTNode
{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

裁判测试程序样例：

#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;
}
/* 你的代码将被嵌在这里 */

输入样例：

输入为由字母和'#'组成的字符串，代表二叉树的扩展先序序列。例如对于如下二叉树，输入数据：

ACG#H###BEF###D##

输出样例（对于图中给出的树）：

二叉树.PNG

Nodes are: G C E

2. 算法思想

按照题目要求，先序遍历二叉树，如果当前节点的出度为1，则输出当前节点。

3. 算法步骤

  • 如果当前节点为空:NULL 则返回
  • 根据先序遍历，遍历左子树

  • 如果当前节点的出度之和是1，则输出：

    • T的左子树不等于空，结果是0或者1
    • T的右子树不等于空，结果是0或者1
    • 取两者的和
    • 当且仅当：左子树为空右子树不为空，或者，右子树为空左子树不为空 。此时的和为1
    • 则进行输出

4. 源代码

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的问题，如果读入了一次，递归到子树再读一遍，读入流指针就可能不对劲啦。

想了想跟回退读入流指针相比，还是递归的时候传一个上一次读到的节点。

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变量，只需要在开始的时候读一下根节点，其他的都不需要特殊处理。

这样就是下面的代码啦

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.源代码

#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. 代码输出

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.源代码

#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.代码输出

1 2 3 4 5 6 7 8 9 10

|栈、队列、串、数组、广义表|KMP

1.实训题目

pic

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.源代码

#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

|栈、队列、串、数组、广义表|递归广义表

1.实训题目

E = (a,E)

2.算法思想

元素。自己指向自己

3.算法步骤

  • 申请个内存
  • 自己指向自己。（ovo->ptr=ovo)
  • data赋值( ovo->data=233)

  • 枚举元素i作为指针：初始化为:ovo,终止条件i!=NULL，循环赋值i=i->ptr

    • 输出信息

4.源代码

#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.代码输出

[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

2. 算法思想

邻接表，建表，然后统计每个点的出度。

图可表示为

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

如果进行数字字母映射，可以得到这个表

t1.in

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)函数

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函数内记录出入度

在维护邻接表之后，添加下面两行即可。

in_deg[v]+=w;
out_deg[u]+=w;

分别让v的入度加w

让u的出度加w

添加这两个函数即可，这样就可以O(1)的时间复杂度求出入度和出度。

inline int get_ind_o1(int u){return in_deg[u];}
inline int get_outd_o1(int u){return out_deg[u];}

4. 源代码

#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. 代码输出

-------------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

2. 算法思想

邻接表邻接矩阵跟上一个题目一样啦。

分别进行深度优先和广度优先遍历就好啦。

深度的话dfs到头就好。

广度的话用一个队列作为辅助即可。

题目转换

t2.in

6 10
1 2
1 3 
1 4
2 3
2 5
3 4
3 5
3 6
4 6
5 6

pic

3. 算法步骤

  • 邻接矩阵和邻接表的遍历和输出同上面一样啦。

    • 邻接矩阵 打印二维数组
    • 邻接表 遍历每个点，然后遍历链表的每个节点就可以啦

  • DFS 遍历

    • vis 数组记录的是当前节点是否已经遍历过，避免循环遍历。

    • 遍历当前节点的所有边，如果指向的边没有被遍历过，则进行遍历。

      • 起始条件：i = fst[u]，当i==0的时候终止，每次循环：i=edge[i].nxt
      • 如果目标点没有被遍历过，则标记该节点已经遍历了，递归遍历目标节点dfs(vv)

  • BFS 遍历（代码中遍历了两次，一次用了STL的队列，一次用的手写的简单的队列）

    • 定义一个队列q
    • 函数传参u，将u加入到队列中。

    • 循环：直到队列为空

      • 从队列中取出元素now_u
      • 输出当前节点。
      • 遍历now_u的所有边，如果指向的节点没有被访问到，则加入到队列中。
      • 不断循环此过程，直到队列为空为止。

4. 源代码

#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");

}

程序输出

-------------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-------------
最后修改：2022 年 12 月 07 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏