《数据结构与算法》课后习题答案

2、3 课后习题解答

2、3、2 判断题

1．线性表得逻辑顺序与存储顺序总就是一致得。（×） 2．顺序存储得线性表可以按序号随机存取。（√）

3．顺序表得插入与删除操作不需要付出很大得时间代价，因为每次操作平均只有近一半得元素需要移动。（×）

4．线性表中得元素可以就是各种各样得，但同一线性表中得数据元素具有相同得特性，因此属于同一数据对象。（√）萦窪櫪碛职詢盏。 5．在线性表得顺序存储结构中，逻辑上相邻得两个元素在物理位置上并不一定相邻。（×）

6．在线性表得链式存储结构中，逻辑上相邻得元素在物理位置上不一定相邻。（√） 7．线性表得链式存储结构优于顺序存储结构。（×）

8．在线性表得顺序存储结构中，插入与删除时移动元素得个数与该元素得位置有关。（√）

9．线性表得链式存储结构就是用一组任意得存储单元来存储线性表中数据元素得。（√） 10．在单链表中，要取得某个元素，只要知道该元素得指针即可，因此，单链表就是随机存取得存储结构。（×）

11．静态链表既有顺序存储得优点，又有动态链表得优点。所以它存取表中第i个元素得时间与i无关。（×）

12．线性表得特点就是每个元素都有一个前驱与一个后继。（×）

2、3、3 算法设计题

1．设线性表存放在向量A[arrsize]得前elenum个分量中，且递增有序。试写一算法，将x 插入到线性表得适当位置上，以保持线性表得有序性，并且分析算法得时间复杂度。恋罚鹪镐籜穢鷙。 【提示】直接用题目中所给定得数据结构（顺序存储得思想就是用物理上得相邻表示逻辑上得相邻，不一定将向量与表示线性表长度得变量封装成一个结构体），因为就是顺序存储，分配得存储空间就是固定大小得，所以首先确定就是否还有存储空间，若有，则根据原线性表中元素得有序性，来确定插入元素得插入位置，后面得元素为它让出位置，（也可以从高下标端开始一边比较，一边移位）然后插入x ，最后修改表示表长得变量。韜学烧纯锉伦烩。 int insert (datatype A[],int *elenum,datatype x) /*设elenum为表得最大下标*/惲餿構啬彌祷猎。 {if (*elenum==arrsize-1) return 0; else {i=*elenum;

while (i>=0 && A[i]>x)

{A[i+1]=A[i]; i--; }

A[i+1]=x; (*elenum)++;

return 1; }

/*表已满，无法插入*/發鉗鹩汹阖鳌櫨。 /*边找位置边移动*/

/*找到得位置就是插入位得下一位*/ /*插入成功*/

}

时间复杂度为O(n)。

2．已知一顺序表A，其元素值非递减有序排列，编写一个算法删除顺序表中多余得值相同得元素。

【提示】对顺序表A，从第一个元素开始，查找其后与之值相同得所有元素，将它们删除；再对第二个元素做同样处理，依此类推。钉覽圹馬双冲褻。 void delete(Seqlist *A) {i=0;

while(ilast) /*将第i个元素以后与其值相同得元素删除

*/

{k=i+1;

while(k<=A->last&&A->data[i]==A->data[k]) k++; /*使k指向第一个与A[i]不同得元素*/ n=k-i-1; /*n表示要删除元素得个数*/ for(j=k;j<=A->last;j++) A->data[j-n]=A->data[j]; /*删除多余元素*/

A->last= A->last -n; i++; }

}

3．写一个算法，从一个给定得顺序表A中删除值在x~y(x<=y)之间得所有元素，要求以较高得效率来实现。靓筚释帮滚陇讵。 【提示】对顺序表A，从前向后依次判断当前元素A->data[i]就是否介于x与y之间，若就是，并不立即删除，而就是用n记录删除时应前移元素得位移量；若不就是，则将A->data[i]向前移动n位。n用来记录当前已删除元素得个数。谬郓塵奋来鸟濼。 void delete(Seqlist *A,int x,int y) {i=0; n=0;

while (ilast) {if (A->data[i]>=x && A->data[i]<=y) n++; /*若A->data[i] 介于x与y之间，n自增*/

賃虑銥錐嫱繆謫。

轶。 else A->data[i-n]=A->data[i];

/*否则向前移动A->data[i]*/慟辽犷鳶诈憒

i++; }

A->last-=n; }

4．线性表中有n个元素，每个元素就是一个字符，现存于向量R[n]中，试写一算法，使R中得字符按字母字符、数字字符与其它字符得顺序排列。要求利用原来得存储空间，元素移动次数最小。弥瘡鵝錟袄骓沥。 【提示】对线性表进行两次扫描，第一次将所有得字母放在前面，第二次将所有得数字放在字母之后，其它字符之前。綣凿贐镱歷绒浃。 int fch(char c) /*判断c就是否字母*/ {if(c>='a'&&c<='z'||c>='A'&&c<='Z') return (1);

else return (0); }

int fnum(char c)

{if(c>='0'&&c<='9') return (1); else return (0);

}

void process(char R[n]) {low=0; high=n-1;

while(low

/*判断c就是否数字*/

/*将字母放在前面*/

{while(low

R[low]=R[high]; R[high]=k; }

}

low=low+1; high=n-1;

while(low

{k=R[low];

R[low]=R[high]; R[high]=k; }

}

}

5．线性表用顺序存储，设计一个算法，用尽可能少得辅助存储空间将顺序表中前m个元素与后n个元素进行整体互换。即将线性表：貳饽兹总詐蠷辩。 （a1, a2, … , am, b1, b2, … , bn）改变为： （b1, b2, … , bn , a1, a2, … , am）。

【提示】比较m与n得大小，若m

void process(Seqlist *L,int m,int n)

{if(m<=n)

for(i=1;i<=m;i++) {x=L->data[0];

for(k=1;k<=L->last;k++) L->data[k-1]=L->data[k]; L->data[L->last]=x; }

else for(i=1;i<=n;i++) {x=L->data[L->last]; for(k=L->last-1;k>=0;k- -) L->data[k+1]=L->data[k]; L->data[0]=x; }

}

6．已知带头结点得单链表L中得结点就是按整数值递增排列得，试写一算法，将值为x 得结点插入到表L中，使得L仍然递增有序，并且分析算法得时间复杂度。悭鎵岂帅鳥师獰。 LinkList insert(LinkList L, int x) {p=L; while(p->next && x>p->next->data) p=p->next; /*寻找插入位置*/ s=(LNode *)malloc(sizeof(LNode)); /*申请结点空间*/ s->data=x; /*填装结点*/ s->next=p->next; p->next=s; /*将结点插入到链表中*/

return(L);

}

7．假设有两个已排序（递增）得单链表A与B，编写算法将它们合并成一个链表C而不改变其排序性。

LinkList Combine(LinkList A, LinkList B)

{C=A; rc=C;

pa=A->next; /*pa指向表A得第一个结点*/ pb=B->next; /*pb指向表B得第一个结点*/ free(B); /*释放B得头结点*/

while (pa && pb) /*将pa、pb所指向结点中，值较小得一个插入到链表C得表尾*/

貴济鱉黷館鷓铜。

if(pa->datadata)

{rc->next=pa; rc=pa;

pa=pa->next; } else

{rc->next=pb; rc=pb;

pb=pb->next; }

if(pa) rc->next=pa; else rc->next=pb; /*将链表A或B中剩余得部分链接到链表C得表尾*/ return(C); }

8．假设长度大于1得循环单链表中，既无头结点也无头指针，p为指向该链表中某一