东北大学：《数据结构》课程教学资源（学习资料）第二章 参考答案

第二章参考答案 、名词解释(略) 、填空题 1、结点起始终端序号位置前趋后趋 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)xk 10, L. datal]=L. data[j-1 ll、nO(n)n/2O(n) 12, Ldata[j-2=l data[j-1 14、i=1 ≡L.last 15、O(n)O 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)&&l<D) 26,(p->next!=NULL)&&(p->data!=x) 27,(p!=NULL)&&(p->next!=NULL)p->next 28, maillot(size)p->next 29, insert lklist(head, x, 1)I++ n(n-1)/2 O(n) 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 第二章 参考答案 一、名词解释 （略） 二、填空题 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 i datatype data [maxsize I sqlist qlist L 数据域data是一个一维数组,线性表的第1,2…,n个元素分别存放在此数组的 第0,1 ,1ast-1个分量中,数据域last表示线性表当前的长度,而last-1是线性 表的终端结点在顺序表中的位置。常数 maxsize称为顺序表的容量,从last到 maxsize-1 为顺序表当前的空闲区(或称备用区)。 Sqlist类型完整地描述了顺序表的组织。L被说明为 sqlist类型的变量,即为一顺 序表,其表长应写为L.1ast,而它的终端结点则必须写为 L data[L.1ast-1]。 2、假设数据元素的类型为 datatype。单链表的类型定义如下: typedef struct node *pointer struct node Datatype data pointer next typedef pointer lklist 其中,① poster是指向 struct node类型变量的指针类型;② struct node是结构体 类型规定一个结点是由两个域data和next组成的记录,其中data的结点的数据域,next 是结点的链域:③ krist与 pointer相同类型,用来说明头指针变量的类型,因而 krist 也就被用来作为单链表的类型 3 typedef struct dnode *pointer struct dnode pointer prior, next typedaf pinter dlklist 链域 prior和next分别指向本结点数据域data所含数据元素的直接前趋和直接后继所 在的结点。所有结点通过前趋和后继指针链接在一起,再加上起标识作用的头指针,就得到 双向循环链表。 4、顺序串的类型定义与顺序表类似,可描述如下: const maxlen=串的最大长度 typedef struct Ichar ch[maxlen string 5、链串的类型定义为 const nodesize=用户定义的结点大小 typedef struct node * pointer 2

2 四、简答及应用 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 Ichar ch[ oqeslze polnernext 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 “ myoldmt (dSUBSTR(B, 3, 2) “le (g)LENGTH(D) (h)INDEX(B, D) 0 (i) DINDEX(C,”"d”) 3 OINSERT(D, 2, C) “ mold (k)INSERT(B, 1, A) mule” (DELETE(B, 2, 2) (m)DELETE(B, 2,0) 10、 REPLACE(S, SUBSTR(T,7,1) SUBSTR(T,3,1), CONCAT(S,”y”) 五、算法设计 1、分析:(1)当A、B表都不为空时,比较A,B表中各元素对应位置的内容的大小, 进而判断A,B的大小 (2)当A,B表都不为空时,且A,B表中各各元素对应位置的内容相同时, 比较A,B的长度,进而判断A,B的大小或是否相等

3 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、 分析：(1)当 A、B 表都不为空时，比较 A，B 表中各元素对应位置的内容的大小， 进而判断 A，B 的大小。 (2)当 A，B 表都不为空时，且 A，B 表中各各元素对应位置的内容相同时， 比较 A，B 的长度，进而判断 A，B 的大小或是否相等

const maxsize=顺序表的容量; fint data maxsize i sqlist; int CMP sqlist(sqlist A sqlist B) i for (i=0; (i<A last )&&(I<B last)): i++) i if(A data[[]<B data[i)return(-1); if(A data[i]>B data[i]return(1); (A last==B last)return(O) else if(A last>. last)return(1); 2、(1)定位 LOCATE(L,X 在带头结点类单链表上实现的算法为 int locate lklist(lklist head, datatype x) *求表head中第一个值等于x的的序号,不存在这种结点时结果为0*/ /*置初值 while((p!=NULL)&&(p->datal=x)) {p=p-> next:J++}/*未达表结点又未找到值等于Ⅹ的结点时经,继续扫描 if(p->data==x) return(; eturn(0) 在无头结点的单链表上实现的算法为: int Locate(lklist head, datatype X) 求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/ ip=head; j=l /*置初值* while((p!=NULL)&&(p->datal=x)) {p=p->next计++}/未达表结点又未找到值等于X的结点时经,继续扫描* if( p->data==X) return( return(O) (2)按序号查找find(L,i) 在带头结点的单链表上实现的算法为: pointer find Iklist(Iklist head, int i) (=l; p=head->next; while((<l)&&(pl=NULL)(p=p->next; j++) if(i==j return(p) else return(NULL) 在无头结点的单链表上实现的算法为: pointer find lklist(lklist head, int i)

4 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);

while((<1)&&(p!=NULL))p=p->next; j ++ else return(NULL) (3)、插入 INSERT(L,X,i) 在带头结点单链表上实现的算法为: void insert Iklist(Iklist head, datatype x, int I) /*在表haed的第i个位置上插入一人以x为值的新结点* {p= find lklist(head,i-1),/*先找第i-1个结点* ifp== NULLreeor((“不存在第i个位置”)*若第i-1个结点不存在,退出* =x/否则生成新结点* s>next=p->next/*结点*p在链域值传给结点*s的链域* t=s;/*修改*p的链域* 在无头结点的单链表上实现的算法为: void Insert( Iklist head, dataytpe X, int 1) /*在表haed的第i个位置上插入一人以x为值的新结点* if(ix=0)eror(i<=0”) else{s=mloc(size);s->data=X,/*否则生成新结点 if(i==1)(s->next=head; head=s; i else! p=wfind Iklist(lklist head, i-1) if(p==NULL) error("i>n+1) (4)删除 DELDTE(Li) 在带头结点的单链表上实现的算法为: void delete lklist(( krist head. int i)/删除表head的第i个结点* {p= find lklist(head,i-1)/*先找待删结点的直接前驱* if(p!=NULL)&&(p->next!=NUL)/*若直接前趋存在且待结点存在* (qFp->next/*q指向待删结点* p>next=q>next摘除待结点* fre(q)/*释放已摘除结点q* else erro(“不存在第i个结点”)/否则给出相关信息* 在无头结点的单链表上实现的算法为: oid delete(lklist head, int 1) /*删除表head的第i个结点,若该链表仅有一个结点时,赋该结点指针NUL* fif(i<=0)error("I<=0 else(if(i==0)(q=head; head=head->next; free(@) else{p= wind Iklist(head,i-l)/*找链表head中第i-1结点指针*/

5 { 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 结点指针*/