第二章线性表习题(答案)
1.描述以下三个概念的区别：头指针，头结点，首元素结点。
首元结点是指链表中存储线性表中第一个数据元素a1的结点。
为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。
头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。
若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。
否则表示空表的链表的头指针为空。
2.填空：
（1）在顺序表中插入或删除一个元素，需要平均移动一半元素，具体移动的元素个数与插入或删除的位置有关。
（2）在顺序表中，逻辑上相邻的元素，其物理位置也相邻。
在单链表中，逻辑上相邻的元素，其物理位置不一定相邻。
（3）在带头结点的非空单链表中，头结点的存储位置由头指针指示，首元素结点的存储位置由头结点的next域指示，除首元素结点外，其它任一元素结点的存储位置由其直接前趋的next域指示。
3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。
按要求从下列语句中选择合适的语句序列。
a. 在P结点后插入S结点的语句序列是：（4）、（1）。
b. 在P结点前插入S结点的语句序列是：（7）、（11）、（8）、（4）、（1）。
c. 在表首插入S结点的语句序列是：（5）、（12）。
d. 在表尾插入S结点的语句序列是：（11）、（9）、（1）、（6）。
供选择的语句有：
（1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next;（4）S->next= P->next; （5）S->next= L; （6）S->next= NULL;（7）Q= P; （8）while(P->next!=Q) P=P->next;
（9）while(P->next!=NULL) P=P->next; （10）P= Q;
（11）P= L; （12）L= S; （13）L= P;
4.设线性表存于a[n]中且递增有序。
试写一算法，将X插入到线性表的适当位置上，以保
持线性表的有序性。
void insertData(int a[],int data)
{
int i,location=0;
for(i=0;i<lenth&&a[i]<data;i++); /*定位到查入点*/
location=i;
for(i=lenth-1;i>=location;i--) /*把查入点及查入点之后的数据以次后移一位*/
{
a[i+1]=a[i];
}
a[location]=data; /*把查新数据*/
lenth++;
}
5.写一算法，从顺序表中删除自第i个元素开始的k个元素。
int DeleteData(int a[],int i,int k)
{
int j;
if(i<1||i>lenth||k<0||k>lenth-k+1)return 0;
for(j=i-1;j<i+k-1;j++)
{
a[j]=a[j+k];
}
lenth=lenth-k;
}
6. 试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。
void delete（Linklist &L）
LinkedList Delete（LinkedList L）
∥L是带头结点的单链表，本算法删除其最小值结点。
{p=L->next；∥p为工作指针。
指向待处理的结点。
假定链表非空。
pre=L；∥pre指向最小值结点的前驱。
q=p；∥q指向最小值结点，初始假定第一元素结点是最小值结点。
while（p->next!=null）
{if（p->next->data<q->data）{pre=p；q=p->next；} ∥查最小值结点
p=p->next；∥指针后移。
}
pre->next=q->next；∥从链表上删除最小值结点
free（q）；∥释放最小值结点空间
}∥结束算法delete。
7.试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表
（a1, a2..., a n）逆置为（a n, a n-1,..., a1）。
（1）以一维数组作存储结构，设线性表存于a[n]中。
void invert(int a[])
{
for(k=0; k<=(n-1)/2; k++ )
{
w = a[k];
a[k] = a[n-k-1];
a[n-k-1] = w;
} // for
} // invert
（2）以单链表作存储结构。
LinkedList invert2（LinkedList la）
∥la是带头结点且数据项递减有序的单链表，本算法将其排列成数据项递增有序的单链表。
{p=la->next；/*p为工作指针*/
la->next=null；
while（p!=null）
{r=p->next；/*暂存p的后继。
*/
p->next=la->next；/*将p结点前插入头结点后。
*/
la->next=p；p=r；
}
}∥结束算法
8.已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它
字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。
int CharSqlist(LNode *L)
{
LNode *Lc,*Ln,*Lo,*p,*pc,*pn,*po;
Lc=L;
Ln=(LNode *) malloc (sizeof (LNode)); if(!Ln)return 0;
Lo=(LNode *) malloc (sizeof (LNode)); if(!Lo)return 0;
pc=Lc,pn=Ln,po=Lo,p=L->next;
while(p!=NULL)
{
if(p->data>'a'&&p->data<'z'||p->data>'A'&&p->data<'Z') {pc->next=p;pc=p;}
else if(p->data>'0'&&p->data<'9')
{pn->next=p;pn=p;}
else
{po->next=p;po=p;}
p=p->next;
}
pc-next=Lc;pn-next=Ln;po-next=Lo;
return 1;
}。