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

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载============== --------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载--------------------- ~ 1 ~

《数据结构与算法》课后答案 课后习题解答 判断题 1．线性表的逻辑顺序与存储顺序总是一致的。 2．顺序存储的线性表可以按序号随机存取。 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 7．线性表的链式存储结构优于顺序存储结构。 8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。 9．线性表的链式存储结构是用一组任意的存储单元来================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载============== --------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载--------------------- ~ 2 ~

存储线性表中数据元素的。 10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。 11．静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。 12．线性表的特点是每个元素都有一个前驱和一个后继。 算法设计题 1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。 【提示】直接用题目中所给定的数据结构，因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，然后插入x ，最后修改表示表长的变量。 int insert (datatype A,int *elenum,datatype x) elenum为表的最大下标*/ {if ================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载============== --------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载--------------------- ~ 3 ~

(*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) 与其值相同的元素删除*/ {k=i+1; while(klast&&A->data[i]==A->data[k]) k++; /*使k指向第一个与A[i] /*将第i个元素以后 /*插入成功*/ 不同的元素*/ n=k-i-1; /*n表示要删除元 素的个数*/ ================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载============== --------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载--------------------- ~ 4 ~

for(j=k;jlast;j++) A->data[j-n]=A->data[j]; /*删除多余元素 */ A->last= A->last -n; i++; } 3．写一个算法，从一个给定的顺序表A中删除值在x~y(x 【提示】对顺序表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]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中的字符按字母字符、数字字符和其它字符的================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载============== --------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载--------------------- ~ 5 ~

顺序排列。要求利用原来的存储空间，元素移动次数最小。 【提示】对线性表进行两次扫描，第一次将所有的字母放在前面，第二次将所有的数字放在字母之后，其它字符之前。 int fch(char c) {if(c>=‘a’&&c=‘A’&&c int fnum(char c) 否数字*/ {if(c>=‘0’&&c else return (0); } void process(char R[n]) {low=0; high=n-1; while(low /*将字母放在前面*/ /*判断c是 /*判断c是否字母*/ return (1); {while(low while(low {k=R[low]; R[low]=R[high]; R[high]=k; } } low=low+1; high=n-1; while(low {while(low R[low]=R[high]; R[high]=k; } } 5．线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前m个元素和后n个元素进行整体互换。即将线性表： 改变为： 。 } /*将数字放在字母后 【提示】比较m和n的大小，若m {if(m for(i=1;i ================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载============== --------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载--------------------- ~ 6 ~

{x=L->data[0]; for(k=1;klast;k++) L->data[k-1]=L->data[k]; L->data[L->last]=x; } else for(i=1;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而不改变其排序================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载============== --------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载--------------------- ~ 7 ~

性。 LinkList Combine(LinkList A, LinkList B) {C=A; rc=C; pa=A->next; pb=B->next; free(B); 头结点*/ while (pa && pb) /*将pa、pb所指向结点中，值 /*pa指向表A的第一个结点*/ /*pb指向表B的第一个结点*/ /*释放B的 较小的一个插入到链表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; /*将链表A或B中剩余的部分链接到 else rc->next=pb; 链表C的表尾*/ return(C); } 8．假设长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链表中某一结点的指针，编写算法删除该结点的前驱结点。 【提示】利用循环单链表的特点，通过s指针可循环找到其前驱结点p及p的前驱结点q，然后可删除结点*p。 viod delepre(LNode *s) {LNode *p, *q; p=s;