数据结构经典算法总复习（上卷）

第一章：数据结构导论

无重要考点，仅需了解时间复杂度。

第二章：线性表

1.获得线性表第i个元素

void GetElem_sq(SqList L, int i, ElemType &e) {
  if (i<1 || i>L.length) ErrorMsg("Invalid i value");
//注意错误监测
  e = L.elem[i-1];//特别注意：C语言数组下标从0开始，与线性表的位序差1
}

2.求两个顺序表的并集

void Union_sq(SqList &La, SqList &Lb) {
  Increment(La, Lb.length);
  for (int i=0; i<Lb.length; ++i) {
    ElemType e = Lb.elem[i];
    int j = 0;
    while(j<La.length && La.elem[j]!=e) ++j;
    if (j==La.length) {
      La.elem[La.length++] = e;
    }
  }
  delete []Lb.elem;
  Lb.length = Lb.listsize = 0;
}

3.求两个单链表的并集

void Union_L(LinkList &La, LinkList &Lb) {
  LNode *pa = La;
  while (Lb) {
    LNode *s = Lb; Lb = Lb->next;//从Lb中依次抽取出s结点
    LNode *p = pa;
    while (p && p->data != s->data) {//与La中结点p依次比对
      p = p->next;
    }
    if (p) delete s;
    else {s->next = La; La = s;}//如果没有，则在La表头添加s
  }
}

4.实现顺序表的就地逆置，即在原表的存储空间将线性表（a1, a2, ..., an−1, an）逆
置为（an, an−1, ..., a2, a1）

void Element_Invert(SqList &L)
{
    int len=L.length;
    Elemtype tmp;
    int i;
    for(i=0;i<len/2;i++)//简单的前后互换
    {
        tmp=L.elem[i];
        L.elem[i]=L.elem[len-i-1];
        L.elem[len-i-1]=tmp;
    }
}

5.循环链表的查找元素

LNode* LocateElem_L3(LinkList L, ElemType e) {
  LNode *p = L->next;
  while (p != L && p->data != e) p = p->next;
  return p == L ? NULL : p;//转了一圈回头了，说明没找到
}

6.双向链表插入元素

void ListInsert_DL(DLinkList &L, DLNode *p, DLNode *s) {//s插入到链表中p的前面
  s->prior = p->prior;
  s->next = p;//先把s插好
  p->prior->next = s;
  p->prior = s;//再去动p结点
}

已知线性表用顺序存储结构表示，表中数据元素为 n 个正整数，试写一个算法，分离该表中的奇数和偶数，使得所有奇数集中放在左侧，偶数集中放在右侧，要求不借用辅助数组且时间复杂度为 $O(n)$

7.第一个顺序表实现，较为简单

void Element_EvenOdd(SqList &L)//哨兵思想，左右相合，有点快速排序那味了
{
    int left=0,right=L.length -1,tmp;
    while(left<right)
    {
        while(L.elem[left]%2==1) //为 奇 数
        {
            left++;
        }
        while(L.elem[right]%2==0) //为 偶 数
        {
            right --;
        }
        tmp=L.elem[left];
        L.elem[left]=L.elem[right];
        L.elem[right]=tmp;
    }
}

8.第二个链表实现，如果存在头指针，则无需考虑第一个插入的特殊情况。

void oddEvenList(Linklist& L) {//没有头指针的情况
    if (!L ||!L->next) return;
    LNode *oddHead=NULL;
    LNode *oddTail=NULL;
    LNode *evenHead=NULL;
    LNode *evenTail=NULL;
    LNode *curr=L;
    while (curr) {
        if (curr->val % 2 == 1) {
            if (!oddHead) {//此时需要考虑第一个奇的情况
                oddHead=curr;
                oddTail=curr;
            } else {
                oddTail ->next=curr;
                oddTail=oddTail ->next;//更新odd链表的尾指针
            }
        } else {
            if (!evenHead) {//需要考虑第一个偶的情况
                evenHead=curr;
                evenTail=curr;
            } else {
                evenTail ->next=curr;
                evenTail=evenTail ->next;//更新even链表的尾指针
            }
        }
        curr=curr->next;
    }
    if (oddHead) {
        oddTail ->next=evenHead;//存在奇数的话，奇数表尾连接偶数表头
            if (evenTail) {
                evenTail ->next=NULL;//如果存在偶数的话，偶数表尾置空；如果不存在，本身就是空表尾
            }
        L=oddHead;
    } else {
        L=evenHead;//如果不存在奇数，则链表头为even链表的表头
    }
}

第三章：栈和队列

1.判断以为结束符的字符序列是否为形如”xyz@zyx” 模式的逆序字符序列

bool judgechar(Sqstack &s,char *p) {
    char e;
    while(*p!='@'&& *p!='#'){//将@前内容入栈
        push(s,*p);
        p++;
    }
    if(*p=='#') return FALSE;//若没有@则报False
    p++;
    while(*p!='#'){
        if(pop(s,e)&&e==*p) p++;//依次比较且出栈，即@前的和@后的依次抵消
        else return FALSE;
    }
    if(Stackempty(s)) return TRUE;//都抵消了，则对了
    else return FALSE;
}

2.数制转换问题，从N进制转为d进制。

void conversion(int N, int d) {
  if (N<=0 || d<=0) ErrorMsg("Input error");
  Stack S; InitStack(S);
  while (N) { Push(S, N%d); N = N/d; }//先除的余数，先入栈
  int e;
  while (Pop(S, e)) { cout << e; }//后出栈
  cout << endl;
}

3.设中缀表达式由单字母变量，双目运算符和圆括号组成，试写一个算法，将一个书写正确的中缀表达式转为后缀表达式。

void getsuffix(char exp[],char suffix[]) {
    SqStack S;
    InitStack_sq(S,10);//随手输一个10
    Push_sq(S,'#');//开头的符号
    char *p=exp;
    char c,ch;
    int k=0;
    while(!StackEmpty(S){
        ch=p++;
        if(!isoperator(ch)){//判断是否为符号
            suffix[k++]=ch;//不为符号，直接写入表达式
            continue;
        }
        switch(ch){//若为符号
            case '(':Push_sq(S,ch);break;
            case ')'://若为反括号，则一直取出，直到出现正括号
                while(Pop_sq(S,c)&&c!='(') suffix[k++]=c;
                break;
            default:
                while(GetTop_sq(S,c) && preop(c,ch)) 
//判断c(前)和ch(后)优先级，c>=ch则为true
                    {suffix[k++]=c;Pop_sq(S,c);}
                if(ch!='#') push(S,ch);
                break;
        }
    }
    suffix[k]='\0';
    DestoryStack_sq(S);
}

4.求顺序队列的长度

int QueueLength_sq(SqQueue Q) {
//当Q.rear=Q.front时为空队列
//当Q.front-Q.rear=1时为满队列
  return (Q.rear - Q.front + Q.queuesize) % Q.queuesize;
}

5.顺序队列的入队和出队

void EnQueue_sq(SqQueue &Q, ElemType e) {
  if ((Q.rear+1) % Q.queuesize == Q.front) Increment(Q);//已为满
  Q.elem[Q.rear] = e; Q.rear = (Q.rear+1) % Q.queuesize;
}

bool DeQueue_sq(SqQueue &Q, ElemType &e) {
  if (Q.front == Q.rear) return false;//已为空
  e = Q.elem[Q.front]; Q.front = (Q.front+1) % Q.queuesize;
  return true;
}

6.汉诺塔问题

void hanoi(int n, char x, char y, char z) {
  if (n==1) move(x,1,z);//跳出递归条件,即最简问题，将1个盘子由X移到Z
  else {
    hanoi(n-1, x, z, y);//将n-1个盘子由X移到Y
    move(x,n,z);//将盘子n由X移到Z
    hanoi(n-1, y, x, z);//将n-1个盘子由Y移到Z
  }
}

void move(char u, int i, char v) {
  printf("move %d from %c to %c", i, u, v);
}

7.八皇后问题

#define N 8 //8*8的国际象棋棋盘
int X[N];
int B[2*N-1],C[2*N-1];
int A[N];
void mark(int i,int j,int flag) {//标志横线，左斜线，右斜线能否再次放置
	A[j]=B[i+j]=C[i-j+7]=flag;
}
bool AbleSet(int i,int j) {//判断这个横线，左斜线，右斜线能否放置
	return (A[i]==0&&B[i+j]==0&&C[i-j+7]==0);
}
void eightQueen(int k) {//从第0列开始尝试，一直到N-1
	for (int i = 0; i < N; i++) {
		if(AbleSet(k,i)) {
			X[k]=i;
			mark(k,i,1);
			if(k==N-1){for (k=0;k<N;k++)cout << X[k] << endl;}
			else eightQueen(k+1);//如果暂时合适，则进入下一列开始尝试
			mark(k,i,0);//没有合适情况，则回溯，取消这里的放置，重新尝试另一种
		}
	}//若运行到这里，则说明这一列已经放不了皇后了，前面的列有些问题，该工作栈弹出，回溯上一级。
}

8.写一个递归算法，对不带头结点的单链表进行逆序，要求输入参数是单链表的头指针，返回逆序之后的头指针。

Link_node inverse(Link_node ∗head){
    Link_node ∗new_head;
    if(head−>next == NULL) return head;//最简单情况，递归终止条件
    else{//将长度为n的链表拆分为1+(n-1)两部分，对后面部分进行逆序，再将这两部分交换位置即可
        new_head = inverse(head−>next);
        head−>next−>next = head;
        head−>next = NULL;
        return new_head;
    }
}

第四章：数组

1.快速转置稀疏矩阵，要求时间复杂度等于nu+tu（列+非零元个数）

ps：普通的行列转换要两个for，时间复杂度为nu*mu（行*列），远大于快速转置。

void FastTranspose(TSMatrix M, TSMatrix &T) {//M矩阵转置为T
  int p, q, col;
  T.mu = M.nu; T.nu = M.mu; T.tu = M.tu;//mu、nu、tu代表矩阵行、列、非零元个数，构造T矩阵
  if (T.tu) {
    T.data = new Triple[T.tu]; rpos = new int[T.mu];
    int *num = new int[M.nu];
    for (col=0; col<M.nu; ++col) num[col] = 0;
//初始化num数组，num存储矩阵M的col列的非零元个数
    for (p=0; p<M.tu; ++p) ++num[M.data[p].j];
//num数组的下标表示M的第p个元素的列（j），制造num完成
    rpos[0] = 0;                //rpos数组代表M中转置后元素应插入位置
    for (col=1; col<M.nu; ++col) rpos[col] = rpos[col-1] + num[col-1];
//制造rpos数组，非首项则按此规律计算在T中位置
    for (p=0; p<M.tu; ++p) {
      col = M.data[p].j; q=rpos[col];//找原M的列，和应该插入T中该列值的位置
      T.data[q].i = M.data[p].j; T.data[q].j = M.data[p].i;
      T.data[q].e = M.data[p].e; ++rpos[col];//转置操作，俩矩阵行（i）与列（j）互换，操作数不变，次序同时递加。
    }
  }
  else {//如果没有非零元
    T.data = NULL; rpos = NULL;
  }
}

理解示意图如下：