数据结构实用教 程第二章课后习题答案.doc

数据结构实用教程（C语言版） DJ友情提醒：兔崽子们别老是抄答案，抄了也多想想为什么这么做 2 线性表2.1 回答下列概念：线性结构，线性表，顺序表，单链表，静态链表 线性结构：设Data_Structure =（D，S），rS，相对r，D中有且仅有一个开始结点和一个终端结点，其余的内部结点都有且仅有一个前趋和一个后继，则称Data_Structure是相对r的线性结构。线性表：是具有相同属性的n（n0）个数据元素的有限序列。顺序表：顺序表（Sequential List）是采用顺序存储结构的线性表。单链表：每个结点只附加一个指向后继的指针域，这样的链表称为单链表（Single Linked List）静态链表：用数组实现的链表，指针就变换为数组的下标，结点即为数组中的下标变量，由于需要预先分配一个较大的数组空间，因此这种链表称之为静态链表。2.2 比较顺序表和链表这两种线性表不同存储结构的特点。逻辑关系的表示：顺序表隐含表示关系，链表显示表示关系。2存储密度：顺序表的存储密度大，而链表的存储密度小。3存储分配方式：顺序表的存储空间是预先静态分配的一块连续存储空间，在程序执行之前必须明确规定它的存储规模。链表不用事先估计存储规模，动态分配和释放存储空间，存储空间可连续也可不连续。4存取方法：顺序表可以随机存取，链表必须顺序存取。5插入、删除操作：在顺序表中做插入、删除时平均移动表中一半的元素；在链表中作插入、删除时，只要修改指针域，而不需要移动元素。所以顺序表的插入、删除效率低，链表的插入、删除效率高。6实现语言：顺序表容易实现，任何高级语言中都有数组类型。而链表的操作是基于指针的，对于没有提供指针类型的高级语言，必须采用静态链表。总之，两种存储结构各有长短，选择那一种由实际问题中的主要因素决定。通常“较稳定”的线性表选择顺序存储，而频繁做插入、删除的线性表，即动态性较强的线性表宜选择链接存储。2.3 已知长度为n的线性表A中的元素是整数，写算法求线性表中值大于item的元素个数。分两种情况编写函数：（1）线性表采用顺序存储；（2）线性表采用单链表存储。（1）线性表采用顺序存储#define MAX 1024typedef int DataType;typedef struct DataType dataMAX;int last; SeqList;int LocateElem (SeqList *L, DataType item)int i,j=0; for(i=0;ilast ;i+) if( L-datai item ) j+; return j;（2）线性表采用单链表存储typedef int DataType;typedef struct Node DataType data; struct Node *next; LinkList;LinkList *locateElem(LinkList *L, DataType item ) LinkList *p=L-next; int i=0; while ( p ) if( p-data item) i+; p=p-next; return i ;2.4 已知长度为n的线性表A中的元素是整数，写算法删除线性表中所有值为item的数据元素。分两种情况编写函数：（1）线性表采用顺序存储；（2）线性表采用单链表存储。（1）线性表采用顺序存储#define MAX 1024typedef int DataType;typedef struct DataType dataMAX;int last; SeqList; int LocateElem (SeqList *L, DataType item)int i=0; While(ilast) if( L-datai =item ) for(j=i+1;jlast;j+) L-dataj-1=L-dataj; L-last -; Else i+; （2）线性表采用单链表存储typedef int DataType;typedef struct Node DataType data; struct Node *next; LinkList;int deleteDupNode(LinkList *L, DataType item) LinkList *p,*q,*r; q= L; p=L-next; while (p) if (p-data=item) q-next=p-next; free(p); p=q-next;else q=p; p=p-next; 2.5 设长度为Max的顺序表L中包含n个整数且递增有序。试写一算法，将x 插入到顺序表的适当位置上，以保持表的有序性，并且分析算法的时间复杂度。#define MAX 1024typedef int DataType;typedef struct DataType dataMAX;int last; SeqList;int inserts(SeqList *L, DataType x) int i; if (L-last =Max-1) printf(“full”); return 0; i= L-last;while(i=0& L-datai x) L-data i+1= L-data i-;L-data i+1=x; L-last +; return 1;2.6 设带头结点的单链表L中的数据元素是整型数且递增有序。试写一算法，将x 插入到单链表的适当位置上，以保持表的有序性，并且分析算法的时间复杂度。typedef int DataType;typedef struct Node DataType data; struct Node *next; LinkList;void InsertList(LinkList *L,datetype x)LinkList *p,*s;s=(LinkList *)malloc(sizeof(Linklist);s-data=x;p=L;while(p-next)&(p-next-datanext;s-next=p-next; p-next=s;2.7 试写一算法实现对不带头结点的单链表H进行就地逆置。typedef int DataType;typedef struct Node DataType data; struct Node *next; LinkList;LinkList * Reverse(LinkList *H)LinkList *p,*q;if (!H) return;p=H-next; q=H-next; H-next=NULL;While(q)q=q-next; p-next= H; H =p; p=q; return H;2.8 若带头结点的单链表L中的数据元素是整型数，编写算法对单链表L进行排序。typedef int DataType;typedef struct Node DataType data; struct Node *next; LinkList;void InsertList(LinkList *L)LinkList *p,*q,*s;if (!L-next |！L-next-next) return;q= L-next-next; L-next-next= NULL;while(q)s=q; q=q-next;p=L;while(p-next)&(p-next-datadata ) p=p-next;s-next=p-next; p-next=s; 2.9 设单链表X和单链表Y分别存储了两个字符串，设计算法找出X中第一个不在Y中出现的字符。typedef char DataType;typedef struct Node DataType data; struct Node *next; LinkList;linklist *search(linklist *x, linklist *y) linklist *p,*q; p=x; q=y; while(p&q) if(p-data!=q-data) q=q-next;else p=p-next; q=y; return p; 2.10 已知递增有序的两个单链表A和B各存储了一个集合。设计算法实现求两个集合的交集运算C=AB。typedef int DataType;typedef struct Node DataType data; struct Node *next; LinkList;LinkList *union(LinkList *A,LinkList *B) LinkList *C, *p,*q,*s*r; p=A-next;q=B-next; C=A; r=C; while (p&q) if (p-data=q-data) r-next=p; r=p; p=p-next;q=q-next;else if (p-datadata) p=p-next; else q=q-next; r-next= NULL ; free(B); return C;2.11 已知递增有序的两个单链表A和B，编写算法将A、B归并成一个递增有序的单链表C。typedef int DataType;typedef struct Node DataType data; struct Node *next; LinkList;LinkList *union(