当前位置: 首页 > article >正文

数据结构经典算法总复习(上卷)

第一章:数据结构导论

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

第二章:线性表

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

理解示意图如下:

由【0 1 12】的“1”(列),找到rpos中的col=1,次序值为2,则插入到T中第二个位置(从上到下数第三个),转置后即【1 0 12】。

其他同理。


这一节就差不多,一篇文章无需很长,在这里留个空,下篇文章明天。

重头戏名单:树,图,查找表,排序


http://www.kler.cn/a/450622.html

相关文章:

  • C++版循环安全队列DequeBuffer
  • Android自定义吐司三
  • 面向未来的教育技术:智能成绩管理系统的开发
  • window安装TradingView
  • Day1 苍穹外卖前端 Vue基础、Vue基本使用方式、Vue-router、Vuex、TypeScript
  • MySQL 数据库优化详解【Java数据库调优】
  • redis延迟队列
  • 云边端一体化架构
  • pyinstaller打包资源文件和ini配置文件怎么放
  • 油漆面积(2017年蓝桥杯)
  • 在瑞芯微RK3588平台上使用RKNN部署YOLOv8Pose模型的C++实战指南
  • ABP vNext框架之EntityVersion
  • 绩效考核试题
  • 技术文档的语言表达:简洁、准确与易懂的平衡艺术
  • 嵌入式科普(24)从SPI和CAN通信重新理解“全双工”
  • 智能脂肪秤方案pcba设计研发步骤解析
  • 开发场景中Java 集合的最佳选择
  • 华为浏览器(HuaweiBrowser),简约高效上网更轻松
  • uniapp Native.js原生arr插件服务发送广播到uniapp页面中
  • leetcode 面试经典 150 题:螺旋矩阵
  • Spring基础分析13-Spring Security框架
  • Python中zip
  • H3C MPLS跨域optionB
  • MacOS M3源代码编译Qt6.8.1
  • Linux系统文件
  • 前端Python应用指南(二)深入Flask:理解Flask的应用结构与模块化设计