数据结构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指向下一个结点,再进行下一次的比较。
如图可以看到,每一轮的比较,ha都是在变化的。
同理,当qb插进ha和qa中间后,ha下一个位置变成了新的ha。
一个单链表的题
思维误区:为什么不是选选A,A和D有什么区别?
问题原因:对代码的赋值理解出错了,如果选A的话,head=p->next,p的后面是null,怎么可能把一个null赋值给头结点呢?D:将新结点插入成为头结点,head这个指针变成了p->next,如下图:
后面看这题真的是很简单,不知道当时在想什么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
完。