习题二和上机答案.doc

习 题 二⒉１描述以下四个概念的区别：头指针变量，头指针，头结点，首结点（第一个结点） 解：头指针变量和头指针是指向链表中第一个结点（头结点或首结点）的指针；在首结点之前附设一个结点称为头结点；首结点是指链表中存储线性表中第一个数据元素的结点若单链表中附设头结点，则不管线性表是否为空，头指针均不为空，否则表示空表的链表的头指针为空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 || xdata) /*若单链表为空或 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]B.elem[j]) j++;else if(A.elem[i]!=A.elem[k]){A.elem[++k]=A.elem[i]; //当发现了一个在 A,B 中都存在的元素i++;j++; //且 C 中没有,就添加到 C 中}}//whilewhile(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；r=heada；r->next=NULL；while (p!=NULL){q=headb；while (q!=NULL && q->data!=p->data) q=q->next；if (q!=NULL){s=p->next；free(p)；p=s；}else{r->next=p；s=p->next；r=p；r->next=NULL；p=s；}}s=heada；heada=heada->next；free(s)；return heada；}2.8 设有线性表 A=(a1 ,a2 ,...,am )，B=(b 1 ,b2 ,...,bn )。

试写一合并 A、B 为线性表C 的算法，使得(a1 ,b1 ,...,am ,bm ,bm+1 ,...,bn ) 当 m≤n 时C＝｛ (a1 ,b1 ,...,an ,bn ,an+1 ,...,am ) 当 m＞n 时A、B 和 C 均以单链表作存储结构，且 C 表利用 A 和 B 中结点空间解：假设 A，B 和 C 链表分别具有头结点的指针 a，b 和 c实现本题功能的函数如下： node *link(a，b) node *a，*b; { node *r，*s，*p，*q，*c; c=(node *)malloc(sizeof(node)); /*建立一个头结点*/ r=c;p=a;q=b; while (p!=NULL || q!=NULL) {if (p!=NULL) /*如果 A 链表还存在可取的结点，则复制一个同样的结点链接到 C 中*/ { s=(node *)malloc(sizeof(node)); s->data=p->data; r->next=s; r=s; p=p->next; }if (q!=NULL) /*如果 B 链表还存在可取的结点，则复制一个同样的结点链接到 C 中*/ { s=(node *)malloc(sizeof(node)); s->data=q->data; r->next=s; r=s; q=q->next; } }r->next=NULL; s=c; c=c->next; /*删除头结点*/ free(s); return(c); }2.9 试用两种线性表的存储结构来解决约瑟夫问题。

设有 n 个人围坐在圆桌周围，现从第s 个人开始报数，数到第 m 个人出列，然后从出列的下一个人重新开始报数，数到第 m 个人又出列，…，如此重复直到所有的人全部出列为止例如当 n=8,m=4,s=1,得到的新序列为：4，8，5，2，1，3，7，6写出相应的求解算法解：先构造一个循环链表nodetype *crea(int n){ nodetype *s,*r,*h;int I;for (i=1;idata=I;s->next=NULL;if(i==1) h=s;else r->next=s;r=s;}r->next=h;return h;}void jese (nodetype *h,int m){ nodetype *p=h,*q;int I;while (p->next!=p){for (i=1;inext;if (p->next!=p){ q=p->next;printf(“%d”,q->data);p->next=q->next;free(q);}p=p->next;}printf(“%d”,p->data);}2.10 已知单链表中的数据元素含有三类字符（即：字母字符、数字字符和其它字符） ，试编写算法构造三个环形链表，使每个环形链表中只含同一类的字符，且利用。