习 题 二
⒉１描述以下四个概念的区别：头指针变量，头指针，头结点，首结点（第一个结点）。 解：头指针变量和头指针是指向链表中第一个结点（头结点或首结点）的指针；在首结点之前附设一个结点称为头结点；首结点是指链表中存储线性表中第一个数据元素的结点。若单链表中附设头结点，则不管线性表是否为空，头指针均不为空，否则表示空表的链表的头指针为空。
2.2简述线性表的两种存储结构有哪些主要优缺点及各自使用的场合。
解：顺序存储是按索引直接存储数据元素，方便灵活，效率高，但插入、删除操作将引起元素移动，降低了效率；而链式存储的元素存储采用动态分配，利用率高，但须增设表示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入和删除十分简单。顺序存储适用于线性表中元素数量基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素的情况；而链式存储适用于频繁进行元素动态插入或删除操作的场合。
2.3 在头结点为h的单链表中，把值为b的结点s插入到值为a的结点之前，若不存在a，就把结点s插入到表尾。
Void insert(Lnode *h,int a,int b) {Lnode *p,*q,*s;
s=(Lnode*)malloc(sizeof(Lnode)); s->data=b; p=h->next;
while(p->data!=a&&p->next!=NULL) {q=p; p=p->next; }
if (p->data==a) {q->next=s; s->next=p;} else
{p->next=s; s->next=NULL;
} }
2.4 设计一个算法将一个带头结点的单链表A分解成两个带头结点的单链表A和B，使A中含有原链表中序号为奇数的元素，而B中含有原链表中序号为偶数的元素，并且保持元素原有的相对顺序。 Lnode *cf(Lnode *ha) {Lnode *p,*q,*s,*hb; int t; p=ha->next; q=ha; t=0;
hb=(Lnode*)malloc(sizeof(Lnode)); s=hb;
while(p->next!=NULL) {if (t==0)
{q=p;p=p->next;t=1;} else
{q->next=p->next;
p->next=s->next; s->next=p; s=p; p=p->next; t=0; } }
s->next=NULL; return (hb); }
2.5设线性表中的数据元素是按值非递减有序排列的，试以不同的存储结构，编写一算法，将x插入到线性表的适当位置上，以保持线性表的有序性。 ⑴顺序表；
解：本题的算法思想是：先找到适当的位置，然后后移元素空出一个位置，再将 x 插入，
并返回向量的新长度。实现本题功能的函数如下：
int insert(vector A，int n，ElemType x) /*向量 A 的长度为 n*/ { int i，j； if (x>=A[n-1]) A[n]=x /*若 x 大于最后的元素，则将其插入到最后*/ else
{ i=0；
while (x>=A[i]) i++； /*查找插入位置 i*/
for (j=n-1；j>=i；j--) A[j+1]=A[j]； /*移出插入 x 的位置*/
A[i]=x；
n++； /*将 x 插入，向量长度增 1*/ } return n; }
⑵单链表。
解：本题算法的思想是先建立一个待插入的结点，然后依次与链表中的各结点的数据域比较大小，找到插入该结点的位置，最后插入该结点。实现本题功能的函数如下： node *insertorder(head，x)
node *head; ElemType x; {
node *s，*p，*q;
s=(node *)malloc(sizeof(node)); /*建立一个待插入的结点*/ s->data=x; s->next=NULL;
if (head==NULL || x
date 域*/
{
s->next=head; /*则把 s 结点插入到表头后面*/ head=s; }
else { q=head; /*为 s 结点寻找插入位置，p 指向待比较的结点，q 指向 p 的
前驱结点*/
p=q->next;
while (p!=NULL && x>p->data) /*若 x 小于 p 所指结点的 data 域值
*/
if (x>p->data) /*则退出 while 循环*/
{
q=p; p=p->next;
}
s->next=p; /*将 s 结点插入到 q 和 p 之间*/ q->next=s; }
return(head);
}
2.6假设有A和B分别表示两个递增有序排列的线性表集合（即同一表中元素值各不相同）， 求A和B的交集C， 表C中也依值递增有序排列。试以不同的存储结构编写求得C的算法。 ⑴顺序表；
void SqList_Intersect_True(SqList &A,SqList B)//求元素递增排列的线性表A和B的元素的交集并存回A中 {
i=1;j=1;k=0;
while(A.elem[i]&&B.elem[j]) {
if(A.elem[i] else if(A.elem[i]>B.elem[j]) j++; else if(A.elem[i]!=A.elem[k]) { A.elem[++k]=A.elem[i]; //当发现了一个在A,B中都存在的元素 i++;j++; //且C中没有,就添加到C中 } }//while while(A.elem[k]) A.elem[k++]=0; }//SqList_Intersect_True ⑵单链表。 单链表 chnode *or(chnode *head1,chnode *head2) { chnode *p1,*p2,*q2,*h,*p; h=p=malloc(sizeof(chnode)); p->next=NULL; p1=head1->next; while(p1) { p2=head2; q2=p2->next; while((q2->data!=p1->data)&&q2) { p2=q2; q2=q2->next; } if(p1->data==q2->data) p2->next=q2->next; if(q2) { while(p->next) p=p->next; p->next=q2; p=q2; q2->next=NULL; } p1=p1->next; } return(h); } 2.7设计一个算法求两个递增有序排列的线性表A和B 的差集。（每个单链表中不存在重复的元素） 提示：即在A中而不在B中的结点的集合。 typedef int elemtype； typedef struct linknode { elemtype data； struct linknode *next； } nodetype； nodetype *subs(nodetype *heada, nodetype *headb) { nodetype *p, *q, *r, *s； s=(nodetype *)malloc(sizeof(nodetype))； s->next=heada； heada=s； p=heada->next；