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

第一章：数据结构导论

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

第二章：线性表

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;//若没有@则报Falsep++;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);//随手输一个10Push_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移到Zelse {hanoi(n-1, x, z, y);//将n-1个盘子由X移到Ymove(x,n,z);//将盘子n由X移到Zhanoi(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-1for (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矩阵转置为Tint 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;}
}

理解示意图如下：