第二章习题及答案：
描述以下概念：数据，数据元素，数据结构答：数据：数据是指所有能被输入到计算机并被加工处理的信息的集合。它可以是用于运算的一组数据，也可以是一些文字、符号，或者一幅图、一张表、一组声音等等。
数据元素：数据元素是数据处理的基本单位。数据是由若干个数据元素组成的，每个数据元素可包含若干个数据项，数据项是数据处理的最小单位。
数据结构：数据结构是指数据元素及其相互关系。作为一门学科，数据结构研究的主要方面包括：数据的逻辑结构、存储结构和基本运算。
设线性表存于整型数组a的前几个分量中，且递增有序。试写一算法，将元素x插入到线性表适当的位置，以保持线性表的有序性。
参考程序见“上机练习\参考答案”文件夹中的“ex2-1.cpp”
设有两个线性表分别存放在数组a1和a2的前几个分量中，且递增有序。试写一算法，将这两个数组合并为一个数组，且递增有序。（提示：参考题目2，可将数组2中的元素一个一个地插到数组1中）
参考程序见“上机练习\参考答案”文件夹中的“ex2-2.cpp”
设有一头为head的带头结点的单链表，其数据域为整型数据且递增有序，试写一算法，将元素x插入到链表适当的位置，以保持链表的有序性。
参考程序见“上机练习\参考答案”文件夹中的“ex3-1.cpp”
试写出不带头的单链表的插入、删除算法。（注意：对不带头的单链表，其插入、删除运算有可能改变链表的头）
插入算法（前插）：
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 (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;
}
假设以数组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 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;
}
}
