|
试描述头指针头结点开始结点的区别并说明头指针和头结点的作用 答 开始结点是指链表中的第一个结点也就是没有直接前趋的那个结点 链表的头指针是一指向链表开始结点的指针(没有头结点时)单链表由头指针唯一确定因此单链表可以用头指针的名字来命名 头结点是在链表的开始结点之前附加的一个结点有了头结点之后头指针指向头结点不论链表否为空头指针总是非空而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后) 何时选用顺序表何时选用链表作为线性表的存储结构为宜? 答 在实际应用中应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构通常有以下几方面的考虑 基于空间的考虑当要求存储的线性表长度变化不大易于事先确定其大小时为了节约存储空间宜采用顺序表反之当线性表长度变化大难以估计其存储规模时采用动态链表作为存储结构为好 基于时间的考虑若线性表的操作主要是进行查找很少做插入和删除操作时采用顺序表做存储结构为宜反之 若需要对线性表进行频繁地插入或删除等的操作时宜采用链表做存储结构并且若链表的插入和删除主要发生在表的首尾两端则采用尾指针表示的单循环链表为宜 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素? 答 在等概率情况下顺序表中插入一个结点需平均移动n/个结点删除一个结点需平均移动(n)/个结点具体的移动次数取决于顺序表的长度n以及需插入或删除的位置ii越接近n则所需移动的结点数越少 为什么在单循环链表中设置尾指针比设置头指针更好? 答 尾指针是指向终端结点的指针用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便设一带头结点的单循环链表其尾指针为rear则开始结点和终端结点的位置分别是rear>next>next 和 rear 查找时间都是O() 若用头指针来表示该链表则查找终端结点的时间为O(n) 在单链表双链表和单循环链表中若仅知道指针p指向某结点不知道头指针能否将结点*p从相应的链表中删去?若可以其时间复杂度各为多少? 答 下面分别讨论三种链表的情况 单链表若指针p指向某结点时能够根据该指针找到其直接后继能够顺后继指针链找到*p结点后的结点但是由于不知道其头指针所以无法访问到p指针指向的结点的直接前趋因此无法删去该结点 双链表由于这样的链表提供双向指针根据*p结点的前趋指针和后继指针可以查找到其直接前趋和直接后继从而可以删除该结点其时间复杂度为O() 单循环链表根据已知结点位置可以直接得到其后相邻的结点位置(直接后继)又因为是循环链表所以我们可以通过查找得到p结点的直接前趋因此可以删去p所指结点其时间复杂度应为O(n) 下述算法的功能是什么? LinkList Demo(LinkList L){ // L 是无头结点单链表 ListNode *Q*P; if(L&&L>next){ Q=L;L=L>next;P=L; while (P>next) P=P>next; P>next=Q; Q>next=NULL; } return L; }// Demo 答 该算法的功能是将开始结点摘下链接到终端结点之后成为新的终端结点而原来的第二个结点成为新的开始结点返回新链表的头指针 设线性表的n个结点定义为(aaan)重写顺序表上实现的插入和删除算法InsertList 和DeleteList解算法如下: #define ListSize // 假定表空间大小为 typedef int DataType;//假定DataType的类型为int型 typedef struct{ DataType data[ListSize];// 向量data用于存放表结点 int length; // 当前的表长度 } Seqlist; //以上为定义表结构 void InsertList ( Seqlist *L Datatype x int i) { //将新结点x插入L所指的顺序表的第i个结点ai的位置上即插入的合法位置为<=i<=L>length int j; if ( i < || i > L > length ) Error(position error);// 非法位置退出该函数定义见教材P if ( L>length>=ListSize ) Error(overflow); for ( j=L>length ; j >= i ; j ) L>data[ j+]=L>data [ j ]; L>data[ i ]=x ; L>length++ ; } void DeleteList ( Seqlist *L int i ) {// 从L所指的顺序表中删除第i个结点ai合法的删除位置为<=i<=L>length int j; if ( i< || i >= L> length) Error( position error ) ; for ( j = i ; j < L> length ; j++ ) L>data [ j ]=L>data [ j+]; //结点前移 L> length ; //表长减小 } 试分别用顺序表和单链表作为存储结构实现将线性表(aaan)就地逆置的操作所谓就地指辅助空间应为O() 答 顺序表 要将该表逆置可以将表中的开始结点与终端结点互换第二个结点与倒数第二个结点互换如此反复就可将整个表逆置了算法如下 // 顺序表结构定义同上题 void ReverseList( Seqlist *L) { DataType temp ; //设置临时空间用于存放data int i; for (i=;i<=L>length/;i++)//L>length/为整除运算 { temp = L>data[i]; //交换数据 L > data[ i ] = L > data[ L > lengthi]; L > data[ L > length i ] = temp; } } 链表 分析 可以用交换数据的方式来达到逆置的目的但是由于是单链表数据的存取不是随机的因此算法效率太低可以利用指针改指来达到表逆置的目的具体情况入下 ()当链表为空表或只有一个结点时该链表的逆置链表与原表相同 ()当链表含个以上结点时可将该链表处理成只含第一结点的带头结点链表和一个无头结点的包含该链表剩余结点的链表然后将该无头结点链表中的所有结点顺着链表指针由前往后将每个结点依次从无头结点链表中摘下作为第一个结点插入到带头结点链表中这样就可以得到逆置的链表算法是这样的 结点结构定义如下 typedef char DataType; //假设结点的数据域类型的字符 typedef struct node{ //结点类型定义 DataType data; //结点的数据域 struct node *next;//结点的指针域 }ListNode; typedef ListNode *LinkList; ListNode *p; LinkList head; LinkList ReverseList( LinkList head ) {// 将head 所指的单链表(带头结点)逆置 ListNode *p *q ;//设置两个临时指针变量 if( head>next && head>next>next) {//当链表不是空表或单结点时 p=head>next; q=p>next; p > next=NULL; //将开始结点变成终端结点 while (q) { //每次循环将后一个结点变成开始结点 p=q; q=q>next ; p>next = head> next ; head>next = p; } return head; } return head; //如是空表或单结点表直接返回head } 设顺序表L是一个递增有序表试写一算法将x插入L中并使L仍是一个有序表 答 因已知顺序表L是递增有序表所以只要从顺序表终端结点（设为i位置元素）开始向前寻找到第一个小于或等于x的元素位置i后插入该位置即可 在寻找过程中由于大于x的元素都应放在x之后所以可边寻找边后移元素当找到第一个小于或等于x的元素位置i时该位置也空出来了 算法如下 //顺序表存储结构如题 void InsertIncreaseList( Seqlist *L Datatype x ) { int i; if ( L>length>=ListSize) Error(overflow); for ( i=L > length ; i> && L>data[ i ] > x ; i) L>data[ i ]=L>data[ i ] ; // 比较并移动元素 L>data[ i ] =x; < |
