数据结构作业课数据结构作业课11

《数据结构作业课数据结构作业课11》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构作业课数据结构作业课112002.10.18Chuhua1主要内容主要内容ò第1至3次书面作业（从第1章到第5章）ò上机作业1、2、3Chuhua2书面作业中存在的问题书面作业中存在的问题ò概念问题–在带头结点的单链表中，表头与首元素的区别；–循环链表（单向/双向）中判断链表为空的条件；–逻辑结构与物理结构。Chuhua3带头结点的单链表带头结点的单链表^ab……d^表头结点首元素/首结点P142.7d：删除首元结点的语句序列P=L;Q=P->next;P->next=P->next->next;free(Q);Chuhua4带头结点的单向循环链表带头结点的单向循环

2、链表^ab……dls^（空链表）判断链表为空的条件：ls==ls->next;Chuhua5不带头结点的单向循环链表不带头结点的单向循环链表lsabc……dlsa（表中只有一个结点）判断链表为空的条件:ls==NULL;Chuhua6逻辑结构与物理结构逻辑结构与物理结构ò逻辑结构：描述数据元素之间的逻辑关系。课本上采用ADT（抽象数据类型）来表示逻辑结构。ò物理结构：数据结构在计算机中的表示（顺序映象和非顺序映象）。ò在设计算法时，首先要确定采用哪种数据结构；这里所说的数据结构指的是物理结构。Chuhua7第一次作业第一次作业òC语言中，数组的下标是从0开始的。ò在用类C语

3、言编写算法时，应尽量符合语法要求。ò具体问题：–P16,2.10：“将它改为一个既正确又高效的算法”，怎样说明这一点？–P17,2.16：如何选择新的链头Chuhua8第二次作业第二次作业ò物理结构和逻辑结构的区别ò对所设计的算法不给出数据结构说明Chuhua9例例11对单链表进行就地逆置对单链表进行就地逆置/*单链表的类型定义*/typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;^a……b^Chuhua10例例11对单链表进行就地逆置对单链表进行就地逆置intReverseList(LinkListl

4、a){LinkListp,q,t;q=la->next;p=q->next;q->next=NULL;//表头变成表尾while(p->next!=NULL){t=p;p=p->next;t->next=q;q=t;}p->next=q;la->next=p;//头指针指向新的表头元素return0;}Chuhua11例例22队列队列P253.28用带头结点的循环链表表示队列typedefstructdLNode{intdata;structdLNode*next;}DLinkNode,*DLinkList;DLinkListddnalloc(void){return((D

5、LinkList)malloc(sizeof(DLinkNode)));}Chuhua12例例22队列队列/*初始化队列*/DLinkListInitialQueue(){DLinkListl;l=ddnalloc();l->data=-32766;l->next=l;returnl;/*返回尾指针*/}Chuhua13例例22队列队列/*入队列*/voidInQueue(DLinkList&l){DLinkListu;intnum;scanf(“%d”,&num);u=ddnalloc();u->data=num;u->next=l->next;l->next=u;l=u

6、;/*更新尾指针*/}Chuhua14例例22队列队列/*出队列*/intOutQueue(DLinkList&l){DLinkListhead,v;intnum;if(l->next==l)return–1;head=l->next;/*头结点*/if(head->next==1)/*队列中只有一个结点*/{num=l->data;v=l;l=l->next;l->next=l;}else{v=head->next;head->next=v->next;num=v->data;}free(v);returnnum;}Chuhua15例例22队列队列òP263.30利用队尾

7、元素的位置和队列中元素的个数，推算出队头元素的位置，再判断循环队列为空或已满。Chuhua16数组与广义表数组与广义表ò计算数组元素的存储位置（P31,5.1）–数组按行存储、按列存储–元素的第一个字节的地址ò广义表：–函数GetTail(T)的结果是一个列表L=((apple,pear),(banana,orange))GetTail(L)=((banana,orange))GetHead(GetTail(L))=(banana,orange)GetHead(GetHead(GetTail(L)))=banana