第二章 参考答案名词解释 （略）
填空题
1、结点 起始 终端 序号 位置 前趋 后趋
2、（） ф
3、前趋 前趋 后趋 后趋
4、线性 5、线性 长度 表长 6、空表
7、初始化INITLATE（L） 求表长LENGTH（L） 读表长GET（L，i） 定位LOCATE
（L，X） 插入INSERT（L，X，i） 删除DELETE（L，i）
8、逻辑结构中相邻的结点在存储结构中仍相邻
9、b+（i-1）x k
10、L．data[j]=L．data[j-1]
11、n O(n) n/2 O(n)
12、L.data[j-2]=l.data[j-1]
13、n-1 o(n) (n-1)/2 O(n)
14、i=1 i≦L.last
15、O(n) O(1)
16、L.last L.data[i-1]
17、单链表 循环链表 双链表
18、指针 19，单链表
20、头结点 表结点
21、首结点 尾结点 任何信息、特殊标志 表长
22、头结点 头结点
23、t=malloc(size) t->next=NULL
24、p=haed p=p->next
25、(p->next!=NULL)&&(j<I)
26、(p->next!=NULL)&&(p->data!=x)
27、(p!=NULL)&&(p->next!=NULL) p->next
28、mailloc(size) p->next
29、insert_lklist(head,x,I) I++ n(n-1)/2 O(n2)
30、p=q p->next=NULL O(n)
31、单向循环链表（简称循环链表） 双向循环链表（简称双链表）
32、NULL 头结点 33、双链表
34、字符数组 赋值 35、空 ф 非空 字符
36、长度 相同 子 主 37、非紧缩 紧缩
38、结点大小 不属于字符集的特殊符号单项选择题
1、②2、①3、①4、②5、①6、②7、③8、③9、④
10、②11、④12、③13、⑤14、④15、③16、①17、②18、③
19、④20、④21、④22、223、②24、③25、④26、②27、③
28、④29、①30、④31、②32、②33、④34、④35、③36、③
37、②38、③39、②40、①41、④
简答及应用
1、线性表的数据元素的类型为datatype，则在语言上可用下述类型定义来描述顺序表：
const maxsize=顺序表的容量；
typedef struct
{ datatype data[maxsize]
int last;
}sqlist;
sqlist L;
数据域data是一个一维数组，线性表的第1，2……，n个元素分别存放在此数组的第0，1，……，last-1个分量中，数据域last表示线性表当前的长度，而last-1是线性表的终端结点在顺序表中的位置。常数maxsize称为顺序表的容量，从last到maxsize-1为顺序表当前的空闲区（或称备用区）。
Sqlist类型完整地描述了顺序表的组织。L被说明为sqlist类型的变量，即为一顺序表，其表长应写为L.last，而它的终端结点则必须写为 L.data[L.last-1]。
2、假设数据元素的类型为datatype。单链表的类型定义如下：
typedef struct node *pointer
struct node
{datatype data;
pointer next;
};
typedef pointer lklist;
其中，①ponter是指向struct node类型变量的指针类型;②struct node是结构体类型规定一个结点是由两个域data和next组成的记录，其中data的结点的数据域,next是结点的链域；③lklist与pointer相同类型，用来说明头指针变量的类型，因而lklist也就被用来作为单链表的类型。
3、typedef struct dnode *dpointer;
struct dnode
{datatype data;
dpointer prior,next;
}
typedaf dpinter dlklist;
链域prior和next分别指向本结点数据域data所含数据元素的直接前趋和直接后继所在的结点。所有结点通过前趋和后继指针链接在一起，再加上起标识作用的头指针，就得到双向循环链表。
4、顺序串的类型定义与顺序表类似，可描述如下：
const maxlen=串的最大长度
typedef struct
{char ch[maxlen]
int curlen;
}string
5、链串的类型定义为：
const nodesize=用户定义的结点大小;
typedef struct node *pointer;
struct node
{char ch[nodesize]
poinernext;
}
typedef pointer strlist;
当结点大小为1时，可将ch域简单地定义为：char ch
6、head称为头指针变量，该变量的值是指向链表的第一个结点的指针，称为头指针。头指针变量是用于存放头指针的变量。
为了便于实现各种运算，通常在单链表的第一个结点之前增设一个类型相同的结点，称为头结点。其它结点称为表结点。表结点中和第一个和最后一个分别称为首结点和尾结点。
头指针变量的作用：对单链表中任一结点的访问，必须首先根据头指针变量中存放的头指针找到第一个结点，再依次按各结点链域存放的指针顺序往下找，直到找到或找不到。头指针变量具有标识单链表的作用，故常用头指针变量为命名单链表。
头结点的作用：头结点的数据域可以不存储任何信息，也可以存放一个特殊标志或表长。其作用是为了对链表进行操作时，将对第一个结点煌处理和对其它结点的处理统一起来。
7、循环单链表、循环双链表。
8、空串和空格串：含0个字符的串称为空串，其长度为0。空格串是含有一个或多处空格字符组成的串，其长度不为0。
串变量和串常量：串常量在程序的执行过程中只能引用不能改变而串变量的值在程序执行过程中是可以改变和重新赋值的。
主串和子串：一个串中任意个连续字符组成的子序列称为该串的子串，该串称为它的所以子串的主串。
串变量的名字与串变量的值：串变量的名字表示串的标识符；串变量的值表示串变量的字符序列。
9、(a)A+B,mule”
(b)B+A,mule,
(c)D+C+B,myoldmule”
(d)SUBSTR(B,3,2),le”
(e)SUBSTR(C,1,0) ,,
(f)LENGTH(A) 2
(g)LENGTH(D) 2
(h)INDEX(B,D) 0
(i)INDEX(C,”d”) 3
(j)INSERT(D,2,C),myold”
(k)INSERT(B,1,A),m ule”
(l)DELETE(B,2,2),me”
(m)DELETE(B,2,0),mule”
10、REPLACE(S,SUBSTR(T,7,1),SUBSTR(T,3,1));CONCAT(S,”y”);
算法设计分析：(1)当A、B表都不为空时，比较A，B表中各元素对应位置的内容的大小，进而判断A，B的大小。
(2)当A，B表都不为空时，且A，B表中各各元素对应位置的内容相同时，比较A，B的长度，进而判断A，B的大小或是否相等。
const maxsize=顺序表的容量;
typedef struct
{int data[maxsize]
int last;
}sqlist;
int CMP_sqlist(sqlist A,sqlist B)
{ for (i=0;(i<A.last)&&(I<B.last));i++}
{ if(A.data[i]<B.data[i])return(-1);
if(A.data[i]>B.data[i])return(1);
}
if(A.last= =B.last) return(0);
else if(A.last>B.last) return(1);
else return(-1);
}
2、(1)定位LOCATE(L，X)
在带头结点类单链表上实现的算法为：
int locate_lklist(lklist head,datatype x)
/*求表head中第一个值等于x的的序号，不存在这种结点时结果为0*/
{p=head->next;j=1; /*置初值*/
while((p!=NULL)&&(p->data!=x))
{p=p->next;j++}/*未达表结点又未找到值等于X的结点时经，继续扫描*/
if (p->data = =x) return(j);
else return(0);
}
在无头结点的单链表上实现的算法为：
int Wlocate(lklist head,datatype X)
/*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/
{p=head; j=1; /*置初值*/
while((p!=NULL)&&(p->data!=x))
{p=p->next;j++}/*未达表结点又未找到值等于X的结点时经，继续扫描*/
if( p->data = =X) return(j);
else return(0);
}
(2)按序号查找find(L,i)
在带头结点的单链表上实现的算法为：
pointer find_lklist(lklist head,int i);
{ j=1; p=head->next;
while((j<1)&&(p!=NULL)){p=p->next; j++}
if(i= = j) return(p);
else return(NULL);
}
在无头结点的单链表上实现的算法为：
pointer find_lklist(lklist head,int i);
{ j=1; p=head;
while((j<1)&&(p!=NULL)){p=p->next; j++}
if(i= = j) return(p);
else return(NULL);
}
(3)、插入INSERT(L，X，i)
在带头结点单链表上实现的算法为：
void insert_lklist(lklist head,datatype x,int I)
/*在表haed的第i个位置上插入一人以x为值的新结点*/
{p=find_lklist(head,i-1); /*先找第i-1个结点*/
if(p= =NULL)reeor(“不存在第i个位置”)/*若第i-1个结点不存在，退出*/
else{s=malloc(size);s->data=x /*否则生成新结点*/
s->next=p->next /*结点*p在链域值传给结点*s的链域*/
p->next=s; /*修改*p的链域*/
}
}
在无头结点的单链表上实现的算法为：
void Winsert(lklist head,dataytpe X,int i)
/*在表haed的第i个位置上插入一人以x为值的新结点*/
{if(i<=0) error(“i<=0”);
else{ s=malloc(size);s->data=X; /*否则生成新结点*/
if(i= =1){s->next=head;head=s;}
else{ p=wfind_lklist(lklist head,i-1);
if(p= =NULL) error(“i>n+1”);
else{s->next=p->next;p->next=s;}
}
}
(4)删除DELDTE(L,i)
在带头结点的单链表上实现的算法为：
void delete_lklist(lklist head,int i) /*删除表head的第i个结点*/
{p=find_lklist(head,i-1) /*先找待删结点的直接前驱*/
if((p!==NULL)&&(p->next!=NULL))/*若直接前趋存在且待结点存在*/
(q=p->next; /*q指向待删结点*/
p->next=q->next/*摘除待结点*/;
free(q);/*释放已摘除结点q*/
}
else error(“不存在第i个结点”)/*否则给出相关信息*/
}
在无头结点的单链表上实现的算法为：
void Wdelete(lklist head,int i)
/* 删除表head的第i个结点，若该链表仅有一个结点时，赋该结点指针NULL*/
{if(i<=0) error(“I＜＝0”
else{if(i= =0){q=head;head=head->next;free(q);}
else{p=wfind_lklist(head,i-1);/*找链表head中第i-1结点指针*/
if(p!=NULL)&&(p->next!=NULL)
｛q=p->next; p->next=q->next; free(q);｝
else error(“不存在第I个结点”)；
｝
｝
｝
分析：从第一个结点开始访问，只要是非空计数一次。
Int wlength_lklist(lklist head) /*求表head的长度*/
{p=head;j=0;
while(p!=NULL){p=p->next;j++;}
return(j); /*回传表长*/
｝
设A,B,C均为无头结点单链表分析：（1）当有序表A，B均非空时，找出两表中元素最小的一个元素，然后将此结点插入到C表中，重复上述步骤。
（2）当A，B两表有一个为空表时，将另一表中元素顺序地插入到C表中。
（3）由于C按递减排序，因此在C表中插入元素时，应始终插入到C表表头。
Lklist Wlink_lklist(lklist A,lklist B)
{ while((A!=NULL)&&(B!=NULL))
if(A->data<b->data){p=A;A=A->next;}
else
p->next=C;C=p;
}
if(A= =NULL) A=B;
while(A!=NULL)
{p=A;A=A->next;
p->next=C;C=p;}
return(C);
}
分析：（1）当有序表A、B均非空时，依次分别从A、B表头部取下结点，插入C表中。
（2）当A、B两表有一个为空表时，将非空表插入到C表尾部。
设A，B，C均为带头结点的单链表
lklist HB_lklist(lklist A,lklist B)
{ C=A;
A=A->next;B=B->next; //去除头结点
While((A!=NULL)&&(B!=NULL))
{p->next=A;p=p->next;A=A->next;
p->next=B;p=p->next;B=B->next;
}
if((B= =NULL)&&(A!=NULL)) p->next=A;
else if((A= =NULL)&&(B!=NULL)) p->next=B;
Return(c);
}
分析：从有序表的尾部开始依次取元素与插入元素比较，若大于插入元素，此元素后移一位，再取它前面一个元素重复上述步骤；则将待插入元素插入。
Void CR(datatype A[],datatype X,int elenum)
{ i=elenum-1;
while((i>=0)&&X<A[i]){A[i+1]=A[i];I--}
A[i+1]=X;
Elenum=elenum+1;
}
算法的时间复杂度为O（n）。
分析首先从表头开始查找待插入位置的直接前趋，找到后插入待插结点。
/*设L表带头结点*/
Void CR_lklist(lklist L,datatype x)
{q=L;p=q->next;
while((p!=NULL)&&(p->data<x)){q=p;p=p->next;}/*查X插入位置q*/
s=malloc(size);s->data=s;
}
(1)顺序表分析：将顺序表的第一个元素与最后一个元素互换，第二个元素与倒数第二个元素互换。
Void NZ_sqlist(sqlist A)
{for{i=0;i<((A.last-1)/2);i++}
{x=A.data[i];
A.data[i]=A.data[A.last-i-1];
A.data[A.last-i-1]=x;
}
}
(2)单链表分析：将原单链表的元素依次取出，再插入另一个单链表的头部。
设该单链表为无头结点，s为指向表的第一个结点的指针。
Void NZ_lklist(lklist s)
{p=NULL; /*p指向当前结点的前趋结点*/
while(s!=NULL)
{ q=s;s=s->next; /*将原单链表的元素依次取出到q*/
q->next=p;p=q; /*再插入另一个单链表p的头部*/
}
s=p; /*s指向新单链表的第一个结点*/
}
分析：A与B的交是指A与B的相同部分元素，即那些在A中出现又在B中出现的元素。由于A、B是有序表，故从表头开始依次比较当前指针所指元素的值是否相同，若相同，在C表中插入该元素，然后将两个表的指针后移，否则指向较小元素的指针后移。重复上述步骤，直到A，B表中有一个表到表尾。
(1)顺序表
sqlist HDZ_sqlist(sqlist A,sqlist B)
{ t=0;j=0;k=0;
while((t<=A.last-1)&&(j<=B.last-1))
switch{ case A.data[i]<B.data[j];i++;break;
case A.data[i]>B.data[j];j++;break;
case A.data[i]= =B.data[j];C.data[k]=A.data[i];k++;i++;j++;break;
}
C.last=k;
Return(c );
}
(2)单链表（设带头结点）
lklist HDZ_lklist(lklist A,lklist B)
{ C=initiate_lklist();
r=C;p=A->next;q=B->next:;
While ((p!=null)&&(q!=null))
Switch
{ case p->data <q->data,p=p->next;break;
case p->data <q->data,q=q->next;break;
case p->data==q->data;
s=malloc(size);s->data=p->data;
s->next=r->next; r->next=s;
r=s; p=p->next;q=q->next;
}
return(c);
}
10.分析：①在有序表B、C中找出相同元素X；
②若X在表A中出现则删除，否则转①；
③重复①②直到B、C表有一个表查找完毕。
顺序表
void ASBC_sqlist(sqlist A,sqlist B,sqlist C)
{I=0;j=0;k=0;
while ((j<B.last)&&(k<C.last))
switch
{case B.data[j]<C.data[k]:j++;break;
case B.data[j]<C.data[k]:k++;break;
case B.data[j]==C.data[k]:/*B、C中找到相同元素*/
{while((I<A.last)&&( A.data[I]<B.data[j]))I++;/*在A中查找B、C表共有元素*/
if (I>= A.last) return;
if (A.data[I]==B.data[j])/*在A中存在B、C表共有元素，删除*/
{for(t=I+1;t< A.last;t++) A.data[t-1]= A.data[t] A.last--;}
j++;k++;
}
}
}
单链表（设含头结点）
void ASBC_lklist(lklist A,lklist B,lklist C)
{pa= A ->next;q= A;
pb= B ->next;pc= C ->next;
while ((pb!=null)&&(pc!=null))
switch
{
case pb->data<pc->data,pb=pb->next;break;
case pb->data<pc->data,pc=pc->next;break;
case pb->data= =pc->data:/* B、C中找到相同元素*/
if(pa= =null)return;
if (pa->data= =pb->data)/*在 A中存在 B、C 表共有元素，删除*/
{q->next=pa->next; free(pa);pa=q->next;}
pb=pb->next;pc=pc->next;
}
}
}
11．分析设置两个指针，分别指向*S及其后继，然后按循环链表特性，顺序往下查找*s的直接前趋，找到后删除；
void DELETE_Xlklist(lklist S)
{p=s; q=p->next;
while (q->nest!=s)
{ p=q; q=q->next;}
p->next=s; free(q);
}
12．分析：在链表L中依次取元素，若取出的元素是字母，把它插入到字母B中，然后在L中删除该元素；若取出的元素是数字，把它插入到数字链D中，然后在L中删除该元素。继续取下一个元素，直到链表的尾部。最后B、D、L中分别存放的是字母字符、数字字符和其它字符。
设原表有头结点、头指针L，新建数字字符链D，字母字符链B，其它字符链R。
void DISM_lklist(lklist L,lklist D,lklist B,lklist R)
{ D =malloc(size of(int)); D ->next= D; /*建D循环链表头结点*/
B =malloc(sizeof(char)); B ->next= B; /*建B循环链表头结点*/
p= L;q=p->next;
while(q!=null)
{if((q->data<=’9’)&&(q->data>=’0’))
{p->next=q->next; /*在表L 中摘除q结点*/
q->next= D ->next; D ->next=q; /*将q结点插入D中*/
q=p->next; /*移动q指针*/
}
else if (q->data<=’z’)&&(q->data>=’a’)||(q->data<=’z’)&&(q->data>=’a’))
{p->next=q->next; /*在表L中删除q 结点*/
q->next= B ->next; B ->next=q; /*将q结点插入B中*/
q=p->next; /*移动q指针*/
}else {p=q;q=p->next;} /*移动q指针*/
}
p->next=L;R=L; /*使R为循环表*/
}
13．分析：使用一维数组，数组下标表示元素的序号，数组值为1表示元素存在，数组值为0表示此元素不存在。若累加数组的下标大于N，再从1开始继续累加数组值，直到所有元素都输出。
Void JSP( int n,k,a[n])
{for(I=0;I<n;I++) a[I ]=1;
j=0;
for(I=0;I<n;I++)
{s=0;
while (s<l){j=(j%n) +1;
s=s+a[j-1];
printf(“%d”,j);a[j-1]=0;
}
}
14．（1）始化
dlklist initiate_dlklist()
{t=malloc(size);
t->next =null;
t->prior=null;
return(t);
}
(2)定位（设含头结点）
int locate_dlklist (dlklist head,datatype x)
/*求表head中第一个值等于x 的结点的序号。不存在这种结点时结果为0 */
{p=head->next;j=1; /*置初值*/
while((p!=null)&&(p->data!=x))
{p=p->next;j++;} /*未达尾结点又未找到值等于x的结点时继续扫描*/
if (p->data = = x) return (j);
else return (0);
}
插入（设含头结点）
void insert_dlklist (dlklist head,datatype x,int I)
/*在表head的第I 个位置上插入一个以x为值的新结点*/
{p=head->next; j=1; /*先找第I-1个结点*/
while ((p!=null) &&(j<I-1))
if ((I-1)!=j) error(“不存在第I个位置”)/*若第I-1个结点不存在，退出*/
else {s=malloc(size);s->data=x;/*否则生成新结点*/
s->prior=p;
s->next=p->next;
p->next->prior=s;
p->next=s;
}
}
删除（设含头结点）
void deldtd_dlklist(dlklist head,int I) /*删除表head的第i个结点*/
{p=head->next;j=1; /*先找第i个结点*/
while((p!=null)&&(j<I)) {p=p->next;j++;}
if(I!=j) error(“不存在第I个位置”)/*若第i个结点不存在，退出*/
if(p!=null) /*若直接前趋存在且待删结点存在*/
{p->prior->next=p->next;
p->next->prior=p->prior;
free(p);/*释放已摘除结点p*/
}
else error(“不在存在第I 结点”) /*否则给出相关信息*/
}
15．分析：首先在链表中查找元素值为X的结点，若找到则让freq域的值增1；然后依次和它的前趋的freq域值比较，若比前freq域值大，和前趋结点位置交换，直到比前趋结点的freq域值小为止。
Typedef struct dfnode *dfpointer;
Struct dfnode
{datatype data;
int freq;
dfpointer prior,next;
}
typedef dfpointer dflklist;
设该双链表含头结点。
Int LOCATE_dflklist(dflklist L,datatype X)
{/*定位值等于X的结点*/
p=L->next; I=1;
while ((p!=null)&&(p->data!=X))
{o=p->next; I++;}
if ((p->data!=X||(p= = null)) error(“不存在值为X的结点,);
else { p->freq++; /*令元素值为X的结点中freq域的值增1*/
q=p->prior;
while((q!= L)&&(q->freq<p->freq))
{I=I-1;
p->prior->next=p->next; /*摘除p*/
p->next->prior=p->prior;
q->prior-<next=p /*在q前插入p*/
p->prior=q->prior;
p->next=q;
q->prior=p;
q=p->prior; /*q重新指向p的前趋*/
}
return(i);
}
16．分析：将X串的结点依次与Y串中的结点值比较，若找到第一个不在Y中出现的结点，则查找成功，返回该值。
设单链表无头结点
char CZC_lklist (lklist X,lklist Y)
{p=x;
while (p!=null)
{q=Y;
while (q!=null)&&(q->data!=p->data) q=q->next;
if (q!=null) return(p->data);
else p=p->next;
}
return(‘＄’);
/*若X中的字符都在Y中出现，则返回’＄’*/
}
17.const maxlen=串的最大长度;
typedef struct
{char ch [maxlen];
int curlen;
} string;
int EQUAL_string(string s,string t )
{ if (s.curlen!=t.curlen) return(0);
for (t=0; t<s.curlen; t++)
if (s.ch[t]!=t.ch[t] ) return(0);
return(1);
}
18.设单链表无头结点
const nodesize =用户定义的结点大小；
typedef struct node *pointer;
struct node
{char ch;
pointer next;
}
typedef pointer strlist;
int EQULA_strlist(strlist s,strlist t )
{ while ((s!= null )&&(t!=null)&&(s->ch==t->ch))
{s=s->next;t=t->next;}
return((t= = null)&&(s= =null));
}
19．分析：首先判断串T是否为串S的子串，若串T是串S的子串对S中该子串逆置。
Int NZ_strlist (strlist s,strlist t)
{p=s->next;t=t->next;q=s;
while(p!=null)
{pp =p ; tt =t; /*判断串T是否为串S的子串*/
while ((tt!=null)&&(pp!=null)&&(pp->ch= =tt->ch))
{pp=pp->next;tt=tt->next;}
if (tt==null) /*串T是串S的子串对S中的该子串的位置*/
{qq=q->next; /* q是子串的第一个结点前趋pp是子串最后一个结点后继*/
while(qq!=pp)
{g=qq; qq= qq->next;
q->next =pp; pp=g;
}
q->next=pp; /*将该子串的前趋与逆置后的子串的相连*/
return(1);/*找到并逆置返1 */
}else {q=p;p=p->next;}
}
return(0);/*找不到匹配的串返0*/
}
20．Int index(char *s,char *t)
{l=LENGTH(s);k=LENGTH(t);
for (j=1;j<=l;j++)
{if (( l-j+1)>=k)
{ASSIGN(m,SUBSTR(s,j,k));
if (EQUAL(m,t )) return(j);
}else return(0);
}
}
填空题
1、结点 起始 终端 序号 位置 前趋 后趋
2、（） ф
3、前趋 前趋 后趋 后趋
4、线性 5、线性 长度 表长 6、空表
7、初始化INITLATE（L） 求表长LENGTH（L） 读表长GET（L，i） 定位LOCATE
（L，X） 插入INSERT（L，X，i） 删除DELETE（L，i）
8、逻辑结构中相邻的结点在存储结构中仍相邻
9、b+（i-1）x k
10、L．data[j]=L．data[j-1]
11、n O(n) n/2 O(n)
12、L.data[j-2]=l.data[j-1]
13、n-1 o(n) (n-1)/2 O(n)
14、i=1 i≦L.last
15、O(n) O(1)
16、L.last L.data[i-1]
17、单链表 循环链表 双链表
18、指针 19，单链表
20、头结点 表结点
21、首结点 尾结点 任何信息、特殊标志 表长
22、头结点 头结点
23、t=malloc(size) t->next=NULL
24、p=haed p=p->next
25、(p->next!=NULL)&&(j<I)
26、(p->next!=NULL)&&(p->data!=x)
27、(p!=NULL)&&(p->next!=NULL) p->next
28、mailloc(size) p->next
29、insert_lklist(head,x,I) I++ n(n-1)/2 O(n2)
30、p=q p->next=NULL O(n)
31、单向循环链表（简称循环链表） 双向循环链表（简称双链表）
32、NULL 头结点 33、双链表
34、字符数组 赋值 35、空 ф 非空 字符
36、长度 相同 子 主 37、非紧缩 紧缩
38、结点大小 不属于字符集的特殊符号单项选择题
1、②2、①3、①4、②5、①6、②7、③8、③9、④
10、②11、④12、③13、⑤14、④15、③16、①17、②18、③
19、④20、④21、④22、223、②24、③25、④26、②27、③
28、④29、①30、④31、②32、②33、④34、④35、③36、③
37、②38、③39、②40、①41、④
简答及应用
1、线性表的数据元素的类型为datatype，则在语言上可用下述类型定义来描述顺序表：
const maxsize=顺序表的容量；
typedef struct
{ datatype data[maxsize]
int last;
}sqlist;
sqlist L;
数据域data是一个一维数组，线性表的第1，2……，n个元素分别存放在此数组的第0，1，……，last-1个分量中，数据域last表示线性表当前的长度，而last-1是线性表的终端结点在顺序表中的位置。常数maxsize称为顺序表的容量，从last到maxsize-1为顺序表当前的空闲区（或称备用区）。
Sqlist类型完整地描述了顺序表的组织。L被说明为sqlist类型的变量，即为一顺序表，其表长应写为L.last，而它的终端结点则必须写为 L.data[L.last-1]。
2、假设数据元素的类型为datatype。单链表的类型定义如下：
typedef struct node *pointer
struct node
{datatype data;
pointer next;
};
typedef pointer lklist;
其中，①ponter是指向struct node类型变量的指针类型;②struct node是结构体类型规定一个结点是由两个域data和next组成的记录，其中data的结点的数据域,next是结点的链域；③lklist与pointer相同类型，用来说明头指针变量的类型，因而lklist也就被用来作为单链表的类型。
3、typedef struct dnode *dpointer;
struct dnode
{datatype data;
dpointer prior,next;
}
typedaf dpinter dlklist;
链域prior和next分别指向本结点数据域data所含数据元素的直接前趋和直接后继所在的结点。所有结点通过前趋和后继指针链接在一起，再加上起标识作用的头指针，就得到双向循环链表。
4、顺序串的类型定义与顺序表类似，可描述如下：
const maxlen=串的最大长度
typedef struct
{char ch[maxlen]
int curlen;
}string
5、链串的类型定义为：
const nodesize=用户定义的结点大小;
typedef struct node *pointer;
struct node
{char ch[nodesize]
poinernext;
}
typedef pointer strlist;
当结点大小为1时，可将ch域简单地定义为：char ch
6、head称为头指针变量，该变量的值是指向链表的第一个结点的指针，称为头指针。头指针变量是用于存放头指针的变量。
为了便于实现各种运算，通常在单链表的第一个结点之前增设一个类型相同的结点，称为头结点。其它结点称为表结点。表结点中和第一个和最后一个分别称为首结点和尾结点。
头指针变量的作用：对单链表中任一结点的访问，必须首先根据头指针变量中存放的头指针找到第一个结点，再依次按各结点链域存放的指针顺序往下找，直到找到或找不到。头指针变量具有标识单链表的作用，故常用头指针变量为命名单链表。
头结点的作用：头结点的数据域可以不存储任何信息，也可以存放一个特殊标志或表长。其作用是为了对链表进行操作时，将对第一个结点煌处理和对其它结点的处理统一起来。
7、循环单链表、循环双链表。
8、空串和空格串：含0个字符的串称为空串，其长度为0。空格串是含有一个或多处空格字符组成的串，其长度不为0。
串变量和串常量：串常量在程序的执行过程中只能引用不能改变而串变量的值在程序执行过程中是可以改变和重新赋值的。
主串和子串：一个串中任意个连续字符组成的子序列称为该串的子串，该串称为它的所以子串的主串。
串变量的名字与串变量的值：串变量的名字表示串的标识符；串变量的值表示串变量的字符序列。
9、(a)A+B,mule”
(b)B+A,mule,
(c)D+C+B,myoldmule”
(d)SUBSTR(B,3,2),le”
(e)SUBSTR(C,1,0) ,,
(f)LENGTH(A) 2
(g)LENGTH(D) 2
(h)INDEX(B,D) 0
(i)INDEX(C,”d”) 3
(j)INSERT(D,2,C),myold”
(k)INSERT(B,1,A),m ule”
(l)DELETE(B,2,2),me”
(m)DELETE(B,2,0),mule”
10、REPLACE(S,SUBSTR(T,7,1),SUBSTR(T,3,1));CONCAT(S,”y”);
算法设计分析：(1)当A、B表都不为空时，比较A，B表中各元素对应位置的内容的大小，进而判断A，B的大小。
(2)当A，B表都不为空时，且A，B表中各各元素对应位置的内容相同时，比较A，B的长度，进而判断A，B的大小或是否相等。
const maxsize=顺序表的容量;
typedef struct
{int data[maxsize]
int last;
}sqlist;
int CMP_sqlist(sqlist A,sqlist B)
{ for (i=0;(i<A.last)&&(I<B.last));i++}
{ if(A.data[i]<B.data[i])return(-1);
if(A.data[i]>B.data[i])return(1);
}
if(A.last= =B.last) return(0);
else if(A.last>B.last) return(1);
else return(-1);
}
2、(1)定位LOCATE(L，X)
在带头结点类单链表上实现的算法为：
int locate_lklist(lklist head,datatype x)
/*求表head中第一个值等于x的的序号，不存在这种结点时结果为0*/
{p=head->next;j=1; /*置初值*/
while((p!=NULL)&&(p->data!=x))
{p=p->next;j++}/*未达表结点又未找到值等于X的结点时经，继续扫描*/
if (p->data = =x) return(j);
else return(0);
}
在无头结点的单链表上实现的算法为：
int Wlocate(lklist head,datatype X)
/*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/
{p=head; j=1; /*置初值*/
while((p!=NULL)&&(p->data!=x))
{p=p->next;j++}/*未达表结点又未找到值等于X的结点时经，继续扫描*/
if( p->data = =X) return(j);
else return(0);
}
(2)按序号查找find(L,i)
在带头结点的单链表上实现的算法为：
pointer find_lklist(lklist head,int i);
{ j=1; p=head->next;
while((j<1)&&(p!=NULL)){p=p->next; j++}
if(i= = j) return(p);
else return(NULL);
}
在无头结点的单链表上实现的算法为：
pointer find_lklist(lklist head,int i);
{ j=1; p=head;
while((j<1)&&(p!=NULL)){p=p->next; j++}
if(i= = j) return(p);
else return(NULL);
}
(3)、插入INSERT(L，X，i)
在带头结点单链表上实现的算法为：
void insert_lklist(lklist head,datatype x,int I)
/*在表haed的第i个位置上插入一人以x为值的新结点*/
{p=find_lklist(head,i-1); /*先找第i-1个结点*/
if(p= =NULL)reeor(“不存在第i个位置”)/*若第i-1个结点不存在，退出*/
else{s=malloc(size);s->data=x /*否则生成新结点*/
s->next=p->next /*结点*p在链域值传给结点*s的链域*/
p->next=s; /*修改*p的链域*/
}
}
在无头结点的单链表上实现的算法为：
void Winsert(lklist head,dataytpe X,int i)
/*在表haed的第i个位置上插入一人以x为值的新结点*/
{if(i<=0) error(“i<=0”);
else{ s=malloc(size);s->data=X; /*否则生成新结点*/
if(i= =1){s->next=head;head=s;}
else{ p=wfind_lklist(lklist head,i-1);
if(p= =NULL) error(“i>n+1”);
else{s->next=p->next;p->next=s;}
}
}
(4)删除DELDTE(L,i)
在带头结点的单链表上实现的算法为：
void delete_lklist(lklist head,int i) /*删除表head的第i个结点*/
{p=find_lklist(head,i-1) /*先找待删结点的直接前驱*/
if((p!==NULL)&&(p->next!=NULL))/*若直接前趋存在且待结点存在*/
(q=p->next; /*q指向待删结点*/
p->next=q->next/*摘除待结点*/;
free(q);/*释放已摘除结点q*/
}
else error(“不存在第i个结点”)/*否则给出相关信息*/
}
在无头结点的单链表上实现的算法为：
void Wdelete(lklist head,int i)
/* 删除表head的第i个结点，若该链表仅有一个结点时，赋该结点指针NULL*/
{if(i<=0) error(“I＜＝0”
else{if(i= =0){q=head;head=head->next;free(q);}
else{p=wfind_lklist(head,i-1);/*找链表head中第i-1结点指针*/
if(p!=NULL)&&(p->next!=NULL)
｛q=p->next; p->next=q->next; free(q);｝
else error(“不存在第I个结点”)；
｝
｝
｝
分析：从第一个结点开始访问，只要是非空计数一次。
Int wlength_lklist(lklist head) /*求表head的长度*/
{p=head;j=0;
while(p!=NULL){p=p->next;j++;}
return(j); /*回传表长*/
｝
设A,B,C均为无头结点单链表分析：（1）当有序表A，B均非空时，找出两表中元素最小的一个元素，然后将此结点插入到C表中，重复上述步骤。
（2）当A，B两表有一个为空表时，将另一表中元素顺序地插入到C表中。
（3）由于C按递减排序，因此在C表中插入元素时，应始终插入到C表表头。
Lklist Wlink_lklist(lklist A,lklist B)
{ while((A!=NULL)&&(B!=NULL))
if(A->data<b->data){p=A;A=A->next;}
else
p->next=C;C=p;
}
if(A= =NULL) A=B;
while(A!=NULL)
{p=A;A=A->next;
p->next=C;C=p;}
return(C);
}
分析：（1）当有序表A、B均非空时，依次分别从A、B表头部取下结点，插入C表中。
（2）当A、B两表有一个为空表时，将非空表插入到C表尾部。
设A，B，C均为带头结点的单链表
lklist HB_lklist(lklist A,lklist B)
{ C=A;
A=A->next;B=B->next; //去除头结点
While((A!=NULL)&&(B!=NULL))
{p->next=A;p=p->next;A=A->next;
p->next=B;p=p->next;B=B->next;
}
if((B= =NULL)&&(A!=NULL)) p->next=A;
else if((A= =NULL)&&(B!=NULL)) p->next=B;
Return(c);
}
分析：从有序表的尾部开始依次取元素与插入元素比较，若大于插入元素，此元素后移一位，再取它前面一个元素重复上述步骤；则将待插入元素插入。
Void CR(datatype A[],datatype X,int elenum)
{ i=elenum-1;
while((i>=0)&&X<A[i]){A[i+1]=A[i];I--}
A[i+1]=X;
Elenum=elenum+1;
}
算法的时间复杂度为O（n）。
分析首先从表头开始查找待插入位置的直接前趋，找到后插入待插结点。
/*设L表带头结点*/
Void CR_lklist(lklist L,datatype x)
{q=L;p=q->next;
while((p!=NULL)&&(p->data<x)){q=p;p=p->next;}/*查X插入位置q*/
s=malloc(size);s->data=s;
}
(1)顺序表分析：将顺序表的第一个元素与最后一个元素互换，第二个元素与倒数第二个元素互换。
Void NZ_sqlist(sqlist A)
{for{i=0;i<((A.last-1)/2);i++}
{x=A.data[i];
A.data[i]=A.data[A.last-i-1];
A.data[A.last-i-1]=x;
}
}
(2)单链表分析：将原单链表的元素依次取出，再插入另一个单链表的头部。
设该单链表为无头结点，s为指向表的第一个结点的指针。
Void NZ_lklist(lklist s)
{p=NULL; /*p指向当前结点的前趋结点*/
while(s!=NULL)
{ q=s;s=s->next; /*将原单链表的元素依次取出到q*/
q->next=p;p=q; /*再插入另一个单链表p的头部*/
}
s=p; /*s指向新单链表的第一个结点*/
}
分析：A与B的交是指A与B的相同部分元素，即那些在A中出现又在B中出现的元素。由于A、B是有序表，故从表头开始依次比较当前指针所指元素的值是否相同，若相同，在C表中插入该元素，然后将两个表的指针后移，否则指向较小元素的指针后移。重复上述步骤，直到A，B表中有一个表到表尾。
(1)顺序表
sqlist HDZ_sqlist(sqlist A,sqlist B)
{ t=0;j=0;k=0;
while((t<=A.last-1)&&(j<=B.last-1))
switch{ case A.data[i]<B.data[j];i++;break;
case A.data[i]>B.data[j];j++;break;
case A.data[i]= =B.data[j];C.data[k]=A.data[i];k++;i++;j++;break;
}
C.last=k;
Return(c );
}
(2)单链表（设带头结点）
lklist HDZ_lklist(lklist A,lklist B)
{ C=initiate_lklist();
r=C;p=A->next;q=B->next:;
While ((p!=null)&&(q!=null))
Switch
{ case p->data <q->data,p=p->next;break;
case p->data <q->data,q=q->next;break;
case p->data==q->data;
s=malloc(size);s->data=p->data;
s->next=r->next; r->next=s;
r=s; p=p->next;q=q->next;
}
return(c);
}
10.分析：①在有序表B、C中找出相同元素X；
②若X在表A中出现则删除，否则转①；
③重复①②直到B、C表有一个表查找完毕。
顺序表
void ASBC_sqlist(sqlist A,sqlist B,sqlist C)
{I=0;j=0;k=0;
while ((j<B.last)&&(k<C.last))
switch
{case B.data[j]<C.data[k]:j++;break;
case B.data[j]<C.data[k]:k++;break;
case B.data[j]==C.data[k]:/*B、C中找到相同元素*/
{while((I<A.last)&&( A.data[I]<B.data[j]))I++;/*在A中查找B、C表共有元素*/
if (I>= A.last) return;
if (A.data[I]==B.data[j])/*在A中存在B、C表共有元素，删除*/
{for(t=I+1;t< A.last;t++) A.data[t-1]= A.data[t] A.last--;}
j++;k++;
}
}
}
单链表（设含头结点）
void ASBC_lklist(lklist A,lklist B,lklist C)
{pa= A ->next;q= A;
pb= B ->next;pc= C ->next;
while ((pb!=null)&&(pc!=null))
switch
{
case pb->data<pc->data,pb=pb->next;break;
case pb->data<pc->data,pc=pc->next;break;
case pb->data= =pc->data:/* B、C中找到相同元素*/
if(pa= =null)return;
if (pa->data= =pb->data)/*在 A中存在 B、C 表共有元素，删除*/
{q->next=pa->next; free(pa);pa=q->next;}
pb=pb->next;pc=pc->next;
}
}
}
11．分析设置两个指针，分别指向*S及其后继，然后按循环链表特性，顺序往下查找*s的直接前趋，找到后删除；
void DELETE_Xlklist(lklist S)
{p=s; q=p->next;
while (q->nest!=s)
{ p=q; q=q->next;}
p->next=s; free(q);
}
12．分析：在链表L中依次取元素，若取出的元素是字母，把它插入到字母B中，然后在L中删除该元素；若取出的元素是数字，把它插入到数字链D中，然后在L中删除该元素。继续取下一个元素，直到链表的尾部。最后B、D、L中分别存放的是字母字符、数字字符和其它字符。
设原表有头结点、头指针L，新建数字字符链D，字母字符链B，其它字符链R。
void DISM_lklist(lklist L,lklist D,lklist B,lklist R)
{ D =malloc(size of(int)); D ->next= D; /*建D循环链表头结点*/
B =malloc(sizeof(char)); B ->next= B; /*建B循环链表头结点*/
p= L;q=p->next;
while(q!=null)
{if((q->data<=’9’)&&(q->data>=’0’))
{p->next=q->next; /*在表L 中摘除q结点*/
q->next= D ->next; D ->next=q; /*将q结点插入D中*/
q=p->next; /*移动q指针*/
}
else if (q->data<=’z’)&&(q->data>=’a’)||(q->data<=’z’)&&(q->data>=’a’))
{p->next=q->next; /*在表L中删除q 结点*/
q->next= B ->next; B ->next=q; /*将q结点插入B中*/
q=p->next; /*移动q指针*/
}else {p=q;q=p->next;} /*移动q指针*/
}
p->next=L;R=L; /*使R为循环表*/
}
13．分析：使用一维数组，数组下标表示元素的序号，数组值为1表示元素存在，数组值为0表示此元素不存在。若累加数组的下标大于N，再从1开始继续累加数组值，直到所有元素都输出。
Void JSP( int n,k,a[n])
{for(I=0;I<n;I++) a[I ]=1;
j=0;
for(I=0;I<n;I++)
{s=0;
while (s<l){j=(j%n) +1;
s=s+a[j-1];
printf(“%d”,j);a[j-1]=0;
}
}
14．（1）始化
dlklist initiate_dlklist()
{t=malloc(size);
t->next =null;
t->prior=null;
return(t);
}
(2)定位（设含头结点）
int locate_dlklist (dlklist head,datatype x)
/*求表head中第一个值等于x 的结点的序号。不存在这种结点时结果为0 */
{p=head->next;j=1; /*置初值*/
while((p!=null)&&(p->data!=x))
{p=p->next;j++;} /*未达尾结点又未找到值等于x的结点时继续扫描*/
if (p->data = = x) return (j);
else return (0);
}
插入（设含头结点）
void insert_dlklist (dlklist head,datatype x,int I)
/*在表head的第I 个位置上插入一个以x为值的新结点*/
{p=head->next; j=1; /*先找第I-1个结点*/
while ((p!=null) &&(j<I-1))
if ((I-1)!=j) error(“不存在第I个位置”)/*若第I-1个结点不存在，退出*/
else {s=malloc(size);s->data=x;/*否则生成新结点*/
s->prior=p;
s->next=p->next;
p->next->prior=s;
p->next=s;
}
}
删除（设含头结点）
void deldtd_dlklist(dlklist head,int I) /*删除表head的第i个结点*/
{p=head->next;j=1; /*先找第i个结点*/
while((p!=null)&&(j<I)) {p=p->next;j++;}
if(I!=j) error(“不存在第I个位置”)/*若第i个结点不存在，退出*/
if(p!=null) /*若直接前趋存在且待删结点存在*/
{p->prior->next=p->next;
p->next->prior=p->prior;
free(p);/*释放已摘除结点p*/
}
else error(“不在存在第I 结点”) /*否则给出相关信息*/
}
15．分析：首先在链表中查找元素值为X的结点，若找到则让freq域的值增1；然后依次和它的前趋的freq域值比较，若比前freq域值大，和前趋结点位置交换，直到比前趋结点的freq域值小为止。
Typedef struct dfnode *dfpointer;
Struct dfnode
{datatype data;
int freq;
dfpointer prior,next;
}
typedef dfpointer dflklist;
设该双链表含头结点。
Int LOCATE_dflklist(dflklist L,datatype X)
{/*定位值等于X的结点*/
p=L->next; I=1;
while ((p!=null)&&(p->data!=X))
{o=p->next; I++;}
if ((p->data!=X||(p= = null)) error(“不存在值为X的结点,);
else { p->freq++; /*令元素值为X的结点中freq域的值增1*/
q=p->prior;
while((q!= L)&&(q->freq<p->freq))
{I=I-1;
p->prior->next=p->next; /*摘除p*/
p->next->prior=p->prior;
q->prior-<next=p /*在q前插入p*/
p->prior=q->prior;
p->next=q;
q->prior=p;
q=p->prior; /*q重新指向p的前趋*/
}
return(i);
}
16．分析：将X串的结点依次与Y串中的结点值比较，若找到第一个不在Y中出现的结点，则查找成功，返回该值。
设单链表无头结点
char CZC_lklist (lklist X,lklist Y)
{p=x;
while (p!=null)
{q=Y;
while (q!=null)&&(q->data!=p->data) q=q->next;
if (q!=null) return(p->data);
else p=p->next;
}
return(‘＄’);
/*若X中的字符都在Y中出现，则返回’＄’*/
}
17.const maxlen=串的最大长度;
typedef struct
{char ch [maxlen];
int curlen;
} string;
int EQUAL_string(string s,string t )
{ if (s.curlen!=t.curlen) return(0);
for (t=0; t<s.curlen; t++)
if (s.ch[t]!=t.ch[t] ) return(0);
return(1);
}
18.设单链表无头结点
const nodesize =用户定义的结点大小；
typedef struct node *pointer;
struct node
{char ch;
pointer next;
}
typedef pointer strlist;
int EQULA_strlist(strlist s,strlist t )
{ while ((s!= null )&&(t!=null)&&(s->ch==t->ch))
{s=s->next;t=t->next;}
return((t= = null)&&(s= =null));
}
19．分析：首先判断串T是否为串S的子串，若串T是串S的子串对S中该子串逆置。
Int NZ_strlist (strlist s,strlist t)
{p=s->next;t=t->next;q=s;
while(p!=null)
{pp =p ; tt =t; /*判断串T是否为串S的子串*/
while ((tt!=null)&&(pp!=null)&&(pp->ch= =tt->ch))
{pp=pp->next;tt=tt->next;}
if (tt==null) /*串T是串S的子串对S中的该子串的位置*/
{qq=q->next; /* q是子串的第一个结点前趋pp是子串最后一个结点后继*/
while(qq!=pp)
{g=qq; qq= qq->next;
q->next =pp; pp=g;
}
q->next=pp; /*将该子串的前趋与逆置后的子串的相连*/
return(1);/*找到并逆置返1 */
}else {q=p;p=p->next;}
}
return(0);/*找不到匹配的串返0*/
}
20．Int index(char *s,char *t)
{l=LENGTH(s);k=LENGTH(t);
for (j=1;j<=l;j++)
{if (( l-j+1)>=k)
{ASSIGN(m,SUBSTR(s,j,k));
if (EQUAL(m,t )) return(j);
}else return(0);
}
}
