第二章习题及答案: 1.描述以下概念:数据,数据元素,数据结构 答:数据:数据是指所有能被输入到计算机并被加工处理的信息的集合。它可以是用于运算 的一组数据,也可以是一些文字、符号,或者一幅图、一张表、一组声音等等 数据元素:数据元素是数据处理的基本单位。数据是由若干个数据元素组成的,每个数 据元素可包含若干个数据项,数据项是数据处理的最小单位 数据结构:数据结构是指数据元素及其相互关系。作为一门学科,数据结构研究的主要 方面包括:数据的逻辑结构、存储结构和基本运算 2.设线性表存于整型数组a的前几个分量中,且递增有序。试写一算法,将元素x插入到 线性表适当的位置,以保持线性表的有序性。 参考程序见“上机练习\参考答案”文件夹中的“ex2-1.cpp” 3.设有两个线性表分别存放在数组al和a2的前几个分量中,且递增有序。试写一算法, 将这两个数组合并为一个数组,且递增有序。(提示:参考题目2,可将数组2中的元 素一个一个地插到数组1中) 参考程序见“上机练习参考谷案”文件夹中的“ex2-2epp” 4.设有一头为head的带头结点的单链表,其数据域为整型数据且递增有序,试写一算法, 将元素x插入到链表适当的位置,以保持链表的有序性 参考程序见“上机练习参考答案”文件夹中的“ex3-1cpp 5.试写出不带头的单链表的插入、删除算法。(注意:对不带头的单链表,其插入、删除 运算有可能改变链表的头) 插入算法(前插) int insert(node*head, datatype x, datatype elm) /*将元素ⅹ插入到以head为头指针的链表中的元素em之前,若不存在元素elm,则插入到 表尾* node*p, *q, *s; if(s=(node+) malloc(sizeof(node))= NULL)return0;/*申请新结点* s->data=x,/给新结点数据域赋值* if (head==NULL) head=s, head ->next=NULL; /*查找元素em的前驱元素,q为前驱元素的指针* while(q-> data!=elm&&q=NULL)/*未找到且表未找完,q指针后移* q=q->next; p=q>next;s>next=p, q->next=s;/插入新元素* if(q==head) head=s return 1 删除算法如下
第二章习题及答案： 1. 描述以下概念：数据，数据元素，数据结构 答：数据．．：数据是指所有能被输入到计算机并被加工处理的信息的集合。它可以是用于运算 的一组数据，也可以是一些文字、符号，或者一幅图、一张表、一组声音等等。 数据元素 ．．．．：数据元素是数据处理的基本单位。数据是由若干个数据元素组成的，每个数 据元素可包含若干个数据项 ．．．，数据项是数据处理的最小单位。 数据结构 ．．．．：数据结构是指数据元素及其相互关系。作为一门学科，数据结构研究的主要 方面包括：数据的逻辑结构、存储结构和基本运算。 2. 设线性表存于整型数组 a 的前几个分量中，且递增有序。试写一算法，将元素 x 插入到 线性表适当的位置，以保持线性表的有序性。 参考程序见“上机练习\参考答案”文件夹中的“ex2-1.cpp” 3. 设有两个线性表分别存放在数组 a1 和 a2 的前几个分量中，且递增有序。试写一算法， 将这两个数组合并为一个数组，且递增有序。（提示：参考题目 2，可将数组 2 中的元 素一个一个地插到数组 1 中） 参考程序见“上机练习\参考答案”文件夹中的“ex2-2.cpp” 4. 设有一头为 head 的带头结点的单链表，其数据域为整型数据且递增有序，试写一算法， 将元素 x 插入到链表适当的位置，以保持链表的有序性。 参考程序见“上机练习\参考答案”文件夹中的“ex3-1.cpp” 5. 试写出不带头的单链表的插入、删除算法。（注意：对不带头的单链表，其插入、删除 运算有可能改变链表的头） 插入算法（前插）： int insertL (node* head,datatype x,datatype elm) /*将元素 x 插入到以 head 为头指针的链表中的元素 elm 之前，若不存在元素 elm，则插入到 表尾*/ { node * p,*q,*s; if ((s=(node*)malloc(sizeof(node)))==NULL) return 0; /*申请新结点*/ s->data=x; /*给新结点数据域赋值*/ if (head==NULL) head=s;head->next=NULL; q=head; /*查找元素 elm 的前驱元素，q 为前驱元素的指针*/ while (q->data!=elm && q!=NULL) /*未找到且表未找完，q 指针后移*/ q=q->next; p=q->next；s->next=p;q->next=s; /*插入新元素*/ if (q==head) head=s; return 1; } 删除算法如下：
int deleteL(node* head, datatype x) /*删除单链表head中的数据元素x*/ node *p,*q/*q为x所在结点的指针,p为其前一个结点的指针* p=head; q=p->next; while(ql=nULL & strcmp(p->data. no, x no)) *注意两个关系表达式的顺序不能颠倒* (p=q: q=q->next; i if (q==NULL) printf("n no this element") return o if(p==head) head=head->next return 1 6.假设以数组seq[0.m-1]存放循环队列,同时设变量rear和 quelen分别指示队尾元素的 位置和队列中元素的存放个数。试给出队空队满的条件,并写出相应的入队出队算法。 队空条件: quelen=0 队满条件: quelen=m1 #define m 10 typedef struct Int rear, quelen; 1 Queue *循环队列的出队算法 int DelQueue( Queue *sq) fint front if(sq-quelen==0) i printf("stack is empty! n"); i sq->quelen= sq->quelen-1 front=(sq->rear+m-sq->quelen+ 1)%m return(sq->seqlfrontD)
int deleteL (node* head,datatype x) /*删除单链表 head 中的数据元素 x*/ { node *p,*q;/*q 为 x 所在结点的指针，p 为其前一个结点的指针*/ p=head;q=p->next; while (q!=NULL && strcmp(p->data.no,x.no)) /*注意两个关系表达式的顺序不能颠倒*/ {p=q;q=q->next;} if (q==NULL) { printf("/n no this element"); return 0; } if (p==head) head=head->next; p->next=q->next; free(q); return 1; } 6. 假设以数组 seq[0..m-1]存放循环队列，同时设变量 rear 和 quelen 分别指示队尾元素的 位置和队列中元素的存放个数。试给出队空队满的条件，并写出相应的入队出队算法。 队空条件：quelen=0 队满条件：quelen=m-1 #define m 10 typedef struct queue_type {int seq[m]; int rear,quelen; }Queue; /*循环队列的出队算法*/ int DelQueue(Queue *sq) {int front; if (sq->quelen==0) {printf("stack is empty!\n"); exit(1);} else { sq->quelen= sq->quelen-1; front=(sq->rear+m-sq->quelen+1)%m; return(sq->seq[front]); } }
*循环队列的入队算法* void En Queue( Queue* sq, int x) if((sq->quelen==m-1) i printf("queue is full! \n") exit(1); i isq-rear=(sq->rear+1)%MAXLEN sq->quelen- sq->quelen+
/*循环队列的入队算法*/ void EnQueue(Queue* sq,int x) { if((sq->quelen==m-1) { printf("queue is full!\n"); exit(1);} else {sq->rear=(sq->rear+1)%MAXLEN; sq->seq[sq->rear]=x; sq->quelen= sq->quelen+1; } }
