浙大878考研备考代码整理

中国大学MOOC浙大数据结构——1.3 分治法求最大公共子序列和问题.cpp

int Max3( int A, int B, int C )
{ /* 返回3个整数中的最大值 */
    return A > B ? A > C ? A : C : B > C ? B : C;
}
 
int DivideAndConquer( int List[], int left, int right )
{ /* 分治法求List[left]到List[right]的最大子列和 */
    int MaxLeftSum, MaxRightSum; /* 存放左右子问题的解 */
    int MaxLeftBorderSum, MaxRightBorderSum; /*存放跨分界线的结果*/
 
    int LeftBorderSum, RightBorderSum;
    int center, i;
 
    if( left == right )  { /* 递归的终止条件，子列只有1个数字 */
        if( List[left] > 0 )  return List[left];
        else return 0;
    }
 
    /* 下面是"分"的过程 */
    center = ( left + right ) / 2; /* 找到中分点 */
    /* 递归求得两边子列的最大和 */
    MaxLeftSum = DivideAndConquer( List, left, center );
    MaxRightSum = DivideAndConquer( List, center+1, right );
 
    /* 下面求跨分界线的最大子列和 */
    MaxLeftBorderSum = 0; LeftBorderSum = 0;
    for( i=center; i>=left; i-- ) { /* 从中线向左扫描 */
        LeftBorderSum += List[i];
        if( LeftBorderSum > MaxLeftBorderSum )
            MaxLeftBorderSum = LeftBorderSum;
    } /* 左边扫描结束 */
 
    MaxRightBorderSum = 0; RightBorderSum = 0;
    for( i=center+1; i<=right; i++ ) { /* 从中线向右扫描 */
        RightBorderSum += List[i];
        if( RightBorderSum > MaxRightBorderSum )
            MaxRightBorderSum = RightBorderSum;
    } /* 右边扫描结束 */
 
    /* 下面返回"治"的结果 */
    return Max3( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum );
}
 
int MaxSubseqSum3( int List[], int N )
{ /* 保持与前2种算法相同的函数接口 */
    return DivideAndConquer( List, 0, N-1 );
}

中国大学MOOC浙大数据结构——2.1线性表操作（基于数组）.cpp

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last;
};
 
/* 初始化 */
List MakeEmpty()
{
    List L;
 
    L = (List)malloc(sizeof(struct LNode));
    L->Last = -1;
 
    return L;
}
 
/* 查找 */
#define ERROR -1
 
Position Find( List L, ElementType X )
{
    Position i = 0;
 
    while( i <= L->Last && L->Data[i]!= X )
        i++;
    if ( i > L->Last )  return ERROR; /* 如果没找到，返回错误信息 */
    else  return i;  /* 找到后返回的是存储位置 */
}
 
/* 插入 */
/*注意:在插入位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是存储下标位置（从0开始），两者差1*/
bool Insert( List L, ElementType X, Position P ) 
{ /* 在L的指定位置P前插入一个新元素X */
    Position i;
 
    if ( L->Last == MAXSIZE-1) {
        /* 表空间已满，不能插入 */
        printf("表满"); 
        return false; 
    }  
    if ( P<0 || P>L->Last+1 ) { /* 检查插入位置的合法性 */
        printf("位置不合法");
        return false; 
    } 
    for( i=L->Last; i>=P; i-- )
        L->Data[i+1] = L->Data[i]; /* 将位置P及以后的元素顺序向后移动 */
    L->Data[P] = X;  /* 新元素插入 */
    L->Last++;       /* Last仍指向最后元素 */
    return true; 
} 
 
/* 删除 */
/*注意:在删除位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是存储下标位置（从0开始），两者差1*/
bool Delete( List L, Position P )
{ /* 从L中删除指定位置P的元素 */
    Position i;
 
    if( P<0 || P>L->Last ) { /* 检查空表及删除位置的合法性 */
        printf("位置%d不存在元素", P ); 
        return false; 
    }
    for( i=P+1; i<=L->Last; i++ )
        L->Data[i-1] = L->Data[i]; /* 将位置P+1及以后的元素顺序向前移动 */
    L->Last--; /* Last仍指向最后元素 */
    return true;   
}

中国大学MOOC浙大数据结构——2.1线性表操作（基于链表）.cpp

typedef struct LNode *PtrToLNode;
struct LNode {
    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;
 
/* 查找 */
#define ERROR NULL
 
Position Find( List L, ElementType X )
{
    Position p = L; /* p指向L的第1个结点 */
 
    while ( p && p->Data!=X )
        p = p->Next;
 
    /* 下列语句可以用 return p; 替换 */
    if ( p )
        return p;
    else
        return ERROR;
}
 
/* 带头结点的插入 */
/*注意:在插入位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是链表结点指针，在P之前插入新结点 */
bool Insert( List L, ElementType X, Position P )
{ /* 这里默认L有头结点 */
    Position tmp, pre;
 
    /* 查找P的前一个结点 */        
    for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ;            
    if ( pre==NULL ) { /* P所指的结点不在L中 */
        printf("插入位置参数错误\n");
        return false;
    }
    else { /* 找到了P的前一个结点pre */
        /* 在P前插入新结点 */
        tmp = (Position)malloc(sizeof(struct LNode)); /* 申请、填装结点 */
        tmp->Data = X; 
        tmp->Next = P;
        pre->Next = tmp;
        return true;
    }
}
 
/* 带头结点的删除 */
/*注意:在删除位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是拟删除结点指针 */
bool Delete( List L, Position P )
{ /* 这里默认L有头结点 */
    Position tmp, pre;
 
    /* 查找P的前一个结点 */        
    for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ;            
    if ( pre==NULL || P==NULL) { /* P所指的结点不在L中 */
        printf("删除位置参数错误\n");
        return false;
    }
    else { /* 找到了P的前一个结点pre */
        /* 将P位置的结点删除 */
        pre->Next = P->Next;
        free(P);
        return true;
    }
}

中国大学MOOC浙大数据结构——2.2堆栈的操作（基于数组）.cpp

typedef int Position;
struct SNode {
    ElementType *Data; /* 存储元素的数组 */
    Position Top;      /* 栈顶指针 */
    int MaxSize;       /* 堆栈最大容量 */
};
typedef struct SNode *Stack;
 
Stack CreateStack( int MaxSize )
{
    Stack S = (Stack)malloc(sizeof(struct SNode));
    S->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    S->Top = -1;
    S->MaxSize = MaxSize;
    return S;
}
 
bool IsFull( Stack S )
{
    return (S->Top == S->MaxSize-1);
}
 
bool Push( Stack S, ElementType X )
{
    if ( IsFull(S) ) {
        printf("堆栈满");
        return false;
    }
    else {
        S->Data[++(S->Top)] = X;
        return true;
    }
}
 
bool IsEmpty( Stack S )
{
    return (S->Top == -1);
}
 
ElementType Pop( Stack S )
{
    if ( IsEmpty(S) ) {
        printf("堆栈空");
        return ERROR; /* ERROR是ElementType的特殊值，标志错误 */
    }
    else 
        return ( S->Data[(S->Top)--] );
}

中国大学MOOC浙大数据结构——2.2堆栈的操作（基于链表）.cpp

typedef struct SNode *PtrToSNode;
struct SNode {
    ElementType Data;
    PtrToSNode Next;
};
typedef PtrToSNode Stack;
 
Stack CreateStack( ) 
{ /* 构建一个堆栈的头结点，返回该结点指针 */
    Stack S;
 
    S = (Stack)malloc(sizeof(struct SNode));
    S->Next = NULL;
    return S;
}
 
bool IsEmpty ( Stack S )
{ /* 判断堆栈S是否为空，若是返回true；否则返回false */
    return ( S->Next == NULL );
}
 
bool Push( Stack S, ElementType X )
{ /* 将元素X压入堆栈S */
    PtrToSNode TmpCell;
 
    TmpCell = (PtrToSNode)malloc(sizeof(struct SNode));
    TmpCell->Data = X;
    TmpCell->Next = S->Next;
    S->Next = TmpCell;
    return true;
}
 
ElementType Pop( Stack S )  
{ /* 删除并返回堆栈S的栈顶元素 */
    PtrToSNode FirstCell;
    ElementType TopElem;
 
    if( IsEmpty(S) ) {
        printf("堆栈空"); 
        return ERROR;
    }
    else {
        FirstCell = S->Next; 
        TopElem = FirstCell->Data;
        S->Next = FirstCell->Next;
        free(FirstCell);
        return TopElem;
    }
}

中国大学MOOC浙大数据结构——2.3队列的操作（基于数组）.cpp

typedef int Position;
struct QNode {
    ElementType *Data;     /* 存储元素的数组 */
    Position Front, Rear;  /* 队列的头、尾指针 */
    int MaxSize;           /* 队列最大容量 */
};
typedef struct QNode *Queue;
 
Queue CreateQueue( int MaxSize )
{
    Queue Q = (Queue)malloc(sizeof(struct QNode));
    Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    Q->Front = Q->Rear = 0;
    Q->MaxSize = MaxSize;
    return Q;
}
 
bool IsFull( Queue Q )
{
    return ((Q->Rear+1)%Q->MaxSize == Q->Front);
}
 
bool AddQ( Queue Q, ElementType X )
{
    if ( IsFull(Q) ) {
        printf("队列满");
        return false;
    }
    else {
        Q->Rear = (Q->Rear+1)%Q->MaxSize;
        Q->Data[Q->Rear] = X;
        return true;
    }
}
 
bool IsEmpty( Queue Q )
{
    return (Q->Front == Q->Rear);
}
 
ElementType DeleteQ( Queue Q )
{
    if ( IsEmpty(Q) ) { 
        printf("队列空");
        return ERROR;
    }
    else  {
        Q->Front =(Q->Front+1)%Q->MaxSize;
        return  Q->Data[Q->Front];
    }
}

中国大学MOOC浙大数据结构——2.3队列的操作（基于链表）.cpp

typedef struct Node *PtrToNode;
struct Node { /* 队列中的结点 */
    ElementType Data;
    PtrToNode Next;
};
typedef PtrToNode Position;
 
struct QNode {
    Position Front, Rear;  /* 队列的头、尾指针 */
    int MaxSize;           /* 队列最大容量 */
};
typedef struct QNode *Queue;
 
bool IsEmpty( Queue Q )
{
    return ( Q->Front == NULL);
}
 
ElementType DeleteQ( Queue Q )
{
    Position FrontCell; 
    ElementType FrontElem;
     
    if  ( IsEmpty(Q) ) {
        printf("队列空");
        return ERROR;
    }
    else {
        FrontCell = Q->Front;
        if ( Q->Front == Q->Rear ) /* 若队列只有一个元素 */
            Q->Front = Q->Rear = NULL; /* 删除后队列置为空 */
        else                     
            Q->Front = Q->Front->Next;
        FrontElem = FrontCell->Data;
 
        free( FrontCell );  /* 释放被删除结点空间  */
        return  FrontElem;
    }
}

中国大学MOOC浙大数据结构——2.4一元多项式的加法乘法操作（基于不带头结点的单链表）.cpp

struct PolyNode {
	int coef; // 系数
	int expon; // 指数
	struct PolyNode *link; // 指向下一个节点的指针
};
typedef struct PolyNode *Polynomial;
Polynomial P1, P2;

Polynomial PolyAdd (Polynomial P1, Polynomial P2)
{
	Polynomial front, rear, temp;
	int sum;
	rear = (Polynomial) malloc(sizeof(struct PolyNode));
	front = rear; /* 由front 记录结果多项式链表头结点 */
	while ( P1 && P2 ) /* 当两个多项式都有非零项待处理时 */
		switch ( Compare(P1->expon, P2->expon) ) {
			case 1:
				Attach( P1->coef, P1->expon, &rear);
				P1 = P1->link;
				break;
			case -1:
				Attach(P2->coef, P2->expon, &rear);
				P2 = P2->link;
				break;
			case 0:
				sum = P1->coef + P2->coef;
				if ( sum ) Attach(sum, P1->expon, &rear);
				P1 = P1->link;
				P2 = P2->link;
				break;
		}
	/* 将未处理完的另一个多项式的所有节点依次复制到结果多项式中去 */
	for ( ; P1; P1 = P1->link ) Attach(P1->coef, P1->expon, &rear);
	for ( ; P2; P2 = P2->link ) Attach(P2->coef, P2->expon, &rear);
	rear->link = NULL;
	temp = front;
	front = front->link; /*令front指向结果多项式第一个非零项 */
	free(temp); /* 释放临时空表头结点 */
	return front;
}

void Attach( int c, int e, Polynomial *pRear )
{ 	/* 由于在本函数中需要改变当前结果表达式尾项指针的值， */
	/* 所以函数传递进来的是结点指针的地址，*pRear指向尾项*/
	Polynomial P;
	P =(Polynomial)malloc(sizeof(struct PolyNode)); /* 申请新结点 */
	P->coef = c; /* 对新结点赋值 */
	P->expon = e;
	P->link=NULL;
	/* 将P指向的新结点插入到当前结果表达式尾项的后面 */
	(*pRear)->link = P;
	*pRear = P; /* 修改pRear值 */
}

Polynomial ReadPoly()
{
  Polynomial P, Rear, t;
  int c, e, N;
  scanf("%d", &N);
  P = (Polynomial)malloc(sizeof(struct PolyNode)); /* 链表头空结点 */
  P->link = NULL;
  Rear = P;
  while ( N-- ) {
    scanf("%d %d", &c, &e);
    Attach(c, e, &Rear); /* 将当前项插入多项式尾部 */
  }
  t = P; P = P->link; free(t); /* 删除临时生成的头结点 */
  return P;
}

Polynomial Mult( Polynomial P1, Polynomial P2 )
{
  Polynomial P, Rear, t1, t2, t;
  int c, e;
  if (!P1 || !P2) return NULL;
  t1 = P1; t2 = P2;
  P = (Polynomial)malloc(sizeof(struct PolyNode)); P->link = NULL;
  Rear = P;
  while (t2) { /* 先用P1的第1项乘以P2，得到P */
    Attach(t1->coef*t2->coef, t1->expon+t2->expon, &Rear);
    t2 = t2->link;
  }
  t1 = t1->link;
  while (t1) {
    t2 = P2; Rear = P;
    while (t2) {
      e = t1->expon + t2->expon;
      c = t1->coef * t2->coef;
      while (Rear->link && Rear->link->expon > e)
        Rear = Rear->link;
      if (Rear->link && Rear->link->expon == e) {
        if (Rear->link->coef + c)
          Rear->link->coef += c;
        else { // 如果系数相加为0，删除这一项
          t = Rear->link;
          Rear->link = t->link;
          free(t);
        }
      }
      else {
        t = (Polynomial)malloc(sizeof(struct PolyNode));
        t->coef = c; t->expon = e;
        t->link = Rear->link;
        Rear->link = t; Rear = Rear->link;
      }
    t2 = t2->link;
    }
  t1 = t1->link;
  }
  t2 = P; P = P->link; free(t2);
  return P;
}

void PrintPoly( Polynomial P )
{ /* 输出多项式 */
  int flag = 0; /* 辅助调整输出格式用 */
  if (!P) {printf("0 0\n"); return;}
  while ( P ) {
    if (!flag)
    flag = 1;
    else
    printf(" ");
    printf("%d %d", P->coef, P->expon);
    P = P->link;
  }
  printf("\n");
}

int main()
{
  Polynomial P1, P2, PP, PS;
  P1 = ReadPoly();
  P2 = ReadPoly();
  PP = Mult( P1, P2 );
  PrintPoly( PP );
  PS = Add( P1, P2 );
  PrintPoly( PS );
  return 0;
}

二叉排序树操作.cpp

/**
代码实现参考自王道考研数据结构书籍
*/
typedef int ElemType;


//二叉树链式存储结构描述
typedef struct BiTNode{
    ElemType data;                               //数据域
    struct BiTNode *lchild, *rchild;             //左、右孩子结点
}BiTNode, BSTNode, *BiTree;

//二叉排序树的查找
BSTNode *BST_Search(BiTree T, ElemType key, BSTNode *&p) {
//查找函数返回指向关键字值为key的结点指针，若不存在，返回NULL
    p = NULL;
    while(T != NULL && T->data != key) {
        p=T;
        if(key < T->data) T = T->lchild;
        else T = T->rchild;
    }
    return p;
}

//二叉排序树的插入
int BST_Insert(BiTree &T, ElemType k) {
//在二叉排序树T中插入一个关键字为k的结点
    if(T==NULL) {
        T = (BiTree)malloc(sizeof(BSTNode));
        T->data = k;
        T->lchild = T->rchild = NULL;
        return 1;                                //返回1，表示成功
    }
    if(k == T->data) return 0;                   //二叉排序树中存在相同关键字的结点，不再插入
    if(k < T->data) 
        return BST_Insert(T->lchild, k);         //插入到左子树中
    else
        return BST_Insert(T->rchild, k);         //插入到右子树中
}

//二叉排序树的创建
void Creat_BST(BiTree &T, ElemType str[], int n) {
//用关键字数组str[]建立一个二叉排序树
    T = NULL;                                    //初始时bt为空
    int i = 0;
    while(i<n) {
        BST_Insert(T, str[i]);
        i++;
    }
}

//二叉排序树删除
//最简单的是通过线索二叉树寻找到被删除结点的前驱后后继

平衡二叉树操作.cpp

/**
代码实现参考自算法笔记
*/
typedef int ElemType;

栈的应用——括号匹配.cpp

bool BracketsCheck(char *str) {
    InitStack(S);                           //初始化栈
    int i = 0;
    while(str[i]!='\0') {
        switch(str[i]) {
            //左括号入栈
            case '(' : Push(S,'('); break;
            
        }
    }
}