数据结构1-3章学习笔记

简介: 数据结构1-3章学习遇到的问题即解决办法主要包含链表,队列等问题需要有一定的C语言基础,整个伪代码是C和C++混写的,所以一开始学会有点觉得难理解

数据结构1-3章学习遇到的问题即解决办法

主要包含链表,队列等问题

需要有一定的C语言基础,整个伪代码是C和C++混写的,所以一开始学会有点觉得难理解

算法2.3

#define LIST_INIT_SIZE 100//线性表存储空间的初始分配量
#define LISTINCREMENT 10//线性表存储空间的分配增量
typedef struct{
  ElemType * elem; //存储空间基址
  int length; //当前长度
  int listsize;//当前分配的存储容量(以sizeof(ElemType)为单位)
}SqList;
Status InitList_Sq(SqList &L){
  //构造一个空的线性表L。
  L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
  //ElemType即element type代表所有可能的数据类型,一般默认为int型
  //分配了一个大小为100个ElemType类型的连续内存空间,并用指针L.elem指向这段空间的第一个ElemType
  if(! L.elem)exit(OVERFLOW);
  L.length = 0;
  L.listsize = LIST_INIT_SIZE;
  return OK;
}//InitList_Sq

malloc是用于分配指定size的内存的库函数

malloc语法:指针名:(数据类型*)malloc(长度)

思维出错:

L.elem不是已经分配了一个空间吗?为什么后面还要

L.listsize = LIST_INIT_SIZE;

这段代码来分配空间?

?:理解出错,L.elem只是个指针名,可以理解为从这个指针(即地址)开始分配了一个空间。就类似数组名的值是一个指针常量,也就是数组第一个元素的地址。

算法2.22

typedef struct{ //项的表示,多项式的项作为LinkList的数据元素
  float coef; //系数 
  int   expn; //指数
}//term,ElemType; //两个类型名:term用于本ADT,ElemType为LinkList的数据对象名
typedef LinkList polynomial; // 用带表头结点的有序链表表示多项式
int cmp(term a,term b);
//依a的指数值<(或=)(或>)b的指数值,分别返回-1、0和+1
void AddPolyn(polynomial &Pa,polynomial &Pb){
//多项式加法:Pa = Pa + Pb,利用两个多项式的结点构成“和多项式”
  ha = GetHead(Pa); hb = GetHead(Pb);//ha和hb分别指向Pa和Pb的头结点
  qa = NextPos(Pa,ha); qb = NextHead(Pb,hb);//qa和qb分别指向Pa和Pb中当前结点
  while(qa&&qb){ //qa和qb均非空
    a = GetCurElem(qa); b = GetCurElem(qb);//a和b为两表中当前比较元素
    switch( * cmp(a,b)){
      case -1: //多项式PA中当前结点的指数值小
        ha = qa; qa = NextPos(Pa,qa);break;
      case 0: //两者的指数值相等
      sum = a.coef + b.ceof;
      if(sum!=0.0){ //修改多项式PA中当前结点的系数值
          SetCurElem(qa,sum); ha = qa; }
        else { //删除多项式PA当前结点
            DelFirst(ha,qa); FreeNode(qa); }
        Delfirst(hb,qa); FreeNode(qb); qb = NextPos(pb, hb);
        qa = NextPos(Pa, ha); break;
      case 1: //多项式PB中当前结点的指数值小
         DelFirst(hb,qb); InsFirst(ha, qb);
         qb = NextPos(Pb, hb); ha=NextPos(Pa,ha);break;
      }//switch
    }//while
    if(!ListEmpty(Pb)) Append(Pa,qb); //链接Pb中剩余结点
    FreeNode(hb): //释放Pb的头结点
}//AddPolyn

思维误区:在思考的时候,一直都想着头指针就一定指向头结点,然后就在下面的这两段卡住了

case -1: 
ha = qa; qa = NextPos(Pa,qa); //我是这样想,为什么qa赋值给ha了,ha不是头指针吗,不是固定指向头结点吗?
或者
case 1:
ha=NextPos(Pa,ha); //为什么把ha的下一个地址赋给ha?ha不是不变的吗?

解决问题:ha在上述代码中只是作为一个常量,比如case -1中,因为Pa中的结点指数小,所以只需要把当前的结点变为头结点,然后qa指向下一个结点,再进行下一次的比较。

image.jpeg

如图可以看到,每一轮的比较,ha都是在变化的。

同理,当qb插进ha和qa中间后,ha下一个位置变成了新的ha。

一个单链表的题

20210616114834372.png

思维误区:为什么不是选选A,A和D有什么区别?

问题原因:对代码的赋值理解出错了,如果选A的话,head=p->next,p的后面是null,怎么可能把一个null赋值给头结点呢?D:将新结点插入成为头结点,head这个指针变成了p->next,如下图:

20210616123541669.png

后面看这题真的是很简单,不知道当时在想什么0.0

销毁队列算法

Status DestoryQueue (LinkQueue &Q){
//销毁队列
  while(Q.front){
    Q.rear =![在这里插入图片描述](https://ucc.alicdn.com/images/user-upload-01/20210616132019840.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAwMTIyMg==,size_16,color_FFFFFF,t_70)
 Q.front->next;
    free(Q.front);
    Q.front = Q.rear;
    }
    return OK;
}

遇到的问题和上面的算法2.22差不多

思维固化了,以为头指针和尾指针就一定是固定的指向头结点和最后一个元素

其实这个算法还是蛮好理解的,就是把

①头指针的下一个元素的地址赋给尾指针,然后头指针把指向的元素销毁掉

②把尾指针的位置赋给头指针

③头指针有把这一刻指向的元素给销毁掉,再把下一个元素的位置赋给尾指针

④循环如此,直到全部销毁完,头指针指向null


20210616132034755.jpg

完。

相关文章
|
4月前
|
存储 JSON NoSQL
redis基本数据结构(String,Hash,Set,List,SortedSet)【学习笔记】
这篇文章是关于Redis基本数据结构的学习笔记,包括了String、Hash、Set、List和SortedSet的介绍和常用命令。文章解释了每种数据结构的特点和使用场景,并通过命令示例演示了如何在Redis中操作这些数据结构。此外,还提供了一些练习示例,帮助读者更好地理解和应用这些数据结构。
redis基本数据结构(String,Hash,Set,List,SortedSet)【学习笔记】
2022 数据结构与算法《王道》学习笔记 (十一)KMP算法 详细归纳总结 改进的模式匹配算法
2022 数据结构与算法《王道》学习笔记 (十一)KMP算法 详细归纳总结 改进的模式匹配算法
2022 数据结构与算法《王道》学习笔记 (十一)KMP算法 详细归纳总结 改进的模式匹配算法
|
机器学习/深度学习 存储 算法
|
算法 前端开发
数据结构和算法的学习笔记(第四部分)
自学的数据结构和算法的学习笔记
数据结构和算法的学习笔记(第四部分)
|
存储 机器学习/深度学习 算法

热门文章

最新文章