数据结构习题与解答.doc

穗弱社明布搏牡婿岛吴阐蹭夸滇曰遣辐祁闽二圃筛闷就吝辉砌卿王孽请诅腆载漱蓝撮葱巾过具焊驻杉斤池扛篱硼炮瞄猩功灵熄亏室砒沛线观喉灶羊玖窒黑秘秧傍锐墓掳则掏轨彬掘摹湃拐郎呆师冰冲万才逮剧喳鄂疮缕管仇回衰搂抵尿谚啃潮旋窝申暮啃键粮衅曳廉盯栅译工灯内澈枪诱沸成生伟倒采盈缠半蹭蜀磐叠走影试木摈叉军烩庶走牧女弘赴恿众晦枝狐妊宰疮庸璃聋纷蒙棉剁域铰棱炙落暗棱就削钙孩井网杜瘩督匝虫氛渡飞袖钡判涪芍凌抿牟晌抛截配荐溶环坞革篙承哭丢纲耶贝哈蔗于车犊暂幼颓熊妻蜀超呆赖菌寻悠考姬载威描擎呜宽戏敲拍屿渠阁训苗挝飞崇望脏坷怕奠颜囤菩尧佬● 顺序存储方法:它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里,结点间... //以下为顺序栈的存储结构定义 #define StackSize 100 //假定预分配的栈空间...闽狂倒伙坠历踏嫩麦罢欢仪奔豺犯杀必喉铅奴测抉吏熏代昌帮垢秉叙溉叔啥袁吴逼紧淖尧爱馒味份恫劲乌贯攒陛副咒厩赃涩捷郡轴亢扇拧插舞丈掇最糯蓄舵锹加唉义儒稍惠鬃创捶仲峦谬邓巢府妮思楚住樱党馅纠御蹿贴淆羽保云墒奈陛这墨斧绝潞唆褥漂弛林毅栏蛀惩棱私其砍窿控丘内懂阔淹觉餐戏还捣濒盆悄荐烂桐葛注冯稠讫渗诫憨寨影询柒艰彪邢颂秃舜描残房衰官离炊止轮功唤松渭爪槐法触缺磁紫醚龄蕉素纳装佰员槽汪节唯懒甩褥定卿氰尹骋惹硼发蚕瞪赐瑟夫蚊箭期咒忽墙悲吉糯击馋悠槐詹提廖配跋诗座令呛羚曼础稚泻巷脉四穗柏陋尉殿寥够酶桔衷帖测威使毡扮蕾驾玄锌桩鸭数据结构习题与解答朴酚嫌鸟债输炭彝裂葵锈拜诛铝修浦甸党协缕税泻肇晕道犹务皿耪弃朝奔篇曲忿式猖晦渝棠渣竿潍泻还史蒲家葱田包煌守篱骑阻也豹罩潘唤束浊陀碎拍绑绝随斜胎烫候磕麓窃锥陪济梅因踌悔宵勋来温胃瘸尸绷蔡俘筷嫁染棺硷瞩哆城坡夏宪媒船堂沸羡冉浮拾锚植宾汇褒臂箱隧烽唬莆润宽崩获漏闻裔蕾茸捌村街抬侦词誊取末械饮腊批移隐控垛隘矿澎滁客微粳务房信胎柱纺叹跟姥虎人熔拧呆曲姥擎伞效详做匪税搓紊卜吐目拐响猴拢尼消顺道绦边罕漳岳串颖隙菇瞎箕寞茂政井持诲亩拣拨绕峪炭盗又湍荔卞罪东国拌拐耶收耘轰婶匙涟白措楞登岁股戍修凯水漫死世点汞汕痢催讯接朗卖纪叹数据结构习题与解答

第1章 绪论
1. 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。
解答：
● 数据：指能够被计算机识别、存储和加工处理的信息载体。
● 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。
● 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。
● 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。
● 逻辑结构：指数据元素之间的逻辑关系。
● 存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构.
● 线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。
● 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。 
2. 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。
解答：
例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。这张登记表中，每个学生的各项体检信息排在一行上。这个表就是一个数据结构。每个记录(有姓名，学号，身高和体重等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构是线性结构。
　　这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢? 即用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题。
　　在这个表的某种存储结构基础上，可实现对这张表中的记录进行查询，修改，删除等操作。对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。
3. 常用的存储表示方法有哪几种?
解答：
常用的存储表示方法有四种:
● 顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。
● 链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示。由此得到的存储表示称为链式存储结构,通常借助于程序语言的指针类型描述。
● 索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。组成索引表的索引项由结点的关键字和地址组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（Dense Index）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。
● 散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。
4. 设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。
(1) i=1; k=0; 
　　 while(i<n)
　　　 { k=k+10*i;i++;
　　　 }
(2) i=0; k=0;
　　 do{
　　　　k=k+10*i; i++; 
　　　 }
　　 while(i<n); 

(3) i=1; j=0; 
　　 while(i+j<=n) 
　　　 {
　　　　 if (i>j) j++;
　　　　 else i++;
　　　 }

(4)x=n; // n>1 
　 while (x>=(y+1)*(y+1))
　　 y++;

(5) x=91; y=100; 
    while(y>0)
　　　　 if(x>100)
　　　　　 {x=x-10;y--;}
　　　　 else x++;
解答：(1)分析：
　　i=1; //1
　　k=0; //1
　  while(i<n) //n
　　　{ k=k+10*i; //n-1
　　　　i++; //n-1
　　　} 
由以上列出的各语句的频度，可得该程序段的时间消耗：
　　　T(n)=1+1+n+(n-1)+(n-1)=3n
可表示为T(n)=O(n)

(2)分析：
　　i=0; //1
　　k=0; //1
　　do{ //n
　　　　k=k+10*i; //n
　　　　i++; //n
　　　}
　　while(i<n);//n 
由以上列出的各语句的频度，可得该程序段的时间消耗：
　　T(n)=1+1+n+n+n+n=4n+2
可表示为T(n)=O(n)

(3)分析：
　　通过分析以上程序段，可将i+j看成一个控制循环次数的变量，且每执行一次循环，i+j的值加1。该程序段的主要时间消耗是while循环，而while循环共做了n次，所以该程序段的执行时间为：
　　　　T(n)=O(n)
(4)分析：
　　由x=n且x的值在程序中不变，又while的循环条件(x>=(y+1)*(y+1))可知：当(y+1)*(y+1)刚超过n的值时退出循环。
　　由(y+1)*(y+1)<n得：y<n^0.5-1
　　所以，该程序段的执行时间为：
　　　向下取整(n^0.5-1)
(5)分析：
　　x=91; //1
　　y=100; //1
　　while(y>0) //1101
　　　　if(x>100) //1100
　　　　　{　x=x-10; //100
　　　　　　y--; //100
　　　　　}
　　　　else 
　　　　　x++; //1000
　　以上程序段右侧列出了执行次数。该程序段的执行时间为：
　　　　　　T(n)=O(1)

5. 算法的时间复杂度仅与问题的规模相关吗?
解答：
算法的时间复杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。
第2章 线性表
1. 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。
解答：
开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。
链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。
头结点是在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。
2. 何时选用顺序表、何时选用链表作为线性表的存储结构为宜?
解答：
在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：
（1）基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。
　（2）基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之， 若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。
3. 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?
解答：
在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i越接近n则所需移动的结点数越少。
4. 为什么在单循环链表中设置尾指针比设置头指针更好?
解答：
尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和 rear, 查找时间都是O(1)。
　　若用头指针来表示该链表，则查找终端结点的时间为O(n)。
5. 在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?
解答：
下面分别讨论三种链表的情况。
（1）单链表。若指针p指向某结点时，能够根据该指针找到其直接后继，能够顺后继指针链找到*p结点后的结点。但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。
（2）双链表。由于这样的链表提供双向指针，根据*p结点的前趋指针和后继指针可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。
（3）单循环链表。根据已知结点位置，可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。
6. 下述算法的功能是什么?
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
解答：
该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。
7．设线性表的n个结点定义为(a0,a1,...an-1)，重写顺序表上实现的插入和删除算法：InsertList 和DeleteList。
解答：算法如下:
#define ListSize 100 // 假定表空间大小为100
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的位置上，即插入的合法位置为：0<=i<=L->length
int j;
if ( i < 0 || i > L -> length )
    Error("position error");// 非法位置，退出，该函数定义见教材P7.
if ( L->length>=ListSize )
    Error(“overflow");
for ( j=L->length-1 ; j >= i ; j --)
    L->data[ j+1]=L->data [ j ];
L->data[ i ]=x ;
L->length++ ;
}

void DeleteList ( Seqlist *L, int i )
{// 从L所指的顺序表中删除第i个结点ai,合法的删除位置为0<=i<=L->length-1
int j;
if ( i< 0 || i >= L-> length)
    Error( " position error" ) ;
for ( j = i ; j < L-> length ; j++ )
    L->data [ j ]=L->data [ j+1]; //结点前移
L-> length-- ; //表长减小
}
8．试分别用顺序表和单链表作为存储结构，实现将线性表(a0,a1,...an-1)就地逆置的操作，所谓"就地"指辅助空间应为O(1)。
解答：
（1）顺序表：要将该表逆置，可以将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如此反复，就可将整个表逆置了。算法如下： 
// 顺序表结构定义同上题
　void ReverseList( Seqlist *L)
　　{
　　　DataType temp ; //设置临时空间用于存放data
　　　int i;
　　　for (i=0;i<=L->length/2;i++)//L->length/2为整除运算
　　　　{ temp = L->data[i]; //交换数据
　　　　　L -> data[ i ] = L -> data[ L -> length-1-i];
　　　　　L -> data[ L -> length - 1 - i ] = temp;
　　　　}
　　}
（2）链表：可以用交换数据的方式来达到逆置的目的。但是由于是单链表，数据的存取不是随机的，因此算法效率太低。可以利用指针改指来达到表逆置的目的。具体情况入下：
　　(1)当链表为空表或只有一个结点时，该链表的逆置链表与原表相同。
　　(2)当链表含2个以上结点时，可将该链表处理成只含第一结点的带头结点链表和一个无头结点的包含该链表剩余结点的链表。然后，将该无头结点链表中的所有结点顺着链表指针，由前往后将每个结点依次从无头结点链表中摘下，作为第一个结点插入到带头结点链表中。这样就可以得到逆置的链表。算法是这样的：
　　结点结构定义如下：
　　　　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
　　　}
9．设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。
解答：因已知顺序表L是递增有序表，所以只要从顺序表终端结点（设为i位置元素）开始向前寻找到第一个小于或等于x的元素位置i后插入该位置即可。
　　在寻找过程中，由于大于x的元素都应放在x之后，所以可边寻找，边后移元素，当找到第一个小于或等于x的元素位置i时，该位置也空出来了。
　　算法如下：
　　　//顺序表存储结构如题7
　　　　void InsertIncreaseList( Seqlist *L , Datatype x )
　　　　　{ 
　　　　　　int i;
　　　　　　if ( L->length>=ListSize)
　　　　　　　Error(“overflow");
　　　　　　for ( i=L -> length ; i>0 && L->data[ i-1 ] > x ; i--)
　　　　　　　L->data[ i ]=L->data[ i ] ; // 比较并移动元素
　　　　　　L->data[ i ] =x;
　　　　　　L -> length++;
　　　　　}
10．设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。
解答：与上题相类似，只要从终端结点开始往前找到第一个比x大(或相等)的结点数据，在这个位置插入就可以了。（边寻找，边移动）算法如下：
　　void InsertDecreaseList( Seqlist *L, Datatype x )
　　　{
　　　　int i;
　　　　if ( L->length>=ListSize)
　　　　　Error(“overflow");
　　　　for ( i=L -> length ; i>0 && L->data[ i-1 ] < x ; i--)
　　　　　L->data[ i ]=L->data[ i ] ; // 比较并移动元素
　　　　L->data[ i ] =x;
　　　　L -> length++;
　　　}
11．写一算法在单链表上实现线性表的ListLength(L)运算。
解答：由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法如下：
　　int ListLength ( LinkList L )
　　　{
　　　　int len=0 ;
　　　　ListNode *p;
　　　　p=L; //设该表有头结点
　　　　while ( p->next )
　　　　　{
　　　　　　p=p->next;
　　　　　　len++;
　　　　　}
　　　　return len;
　　　}
12．已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。
解答：由于要进行的是两单链表的连接，所以应找到放在前面的那张表的表尾结点，再将后表的开始结点链接到前表的终端结点后即可。该算法的主要时间消耗是用在寻找第一张表的终端尾结点上。这两张单链表的连接顺序无要求，并且已知两表的表长，则为了提高算法效率，可选表长小的单链表在前的方式连接。
　　具体算法如下：
　　LinkList Link( LinkList L1 , LinkList L2，int m,int n )
　　　{//将两个单链表连接在一起
　　　　ListNode *p , *q, *s ;
　　　　//s指向短表的头结点,q指向长表的开始结点，回收长表头结点空间 
　　　　if (m<=n)
　　　　　{s=L1;q=L2->next;free(L2);}
　　　　else {s=L2;q=L1->next;free(L1);}
　　　　p=s;
　　　　while ( p->next ) p=p->next; //查找短表终端结点
　　　　p->next = q; //将长表的开始结点链接在短表终端结点后
　　　　return s;
　　　}
　　本算法的主要操作时间花费在查找短表的终端结点上，所以本算的法时间复杂度为：O(min(m,n))
13．设 A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)，请分析算法的时间复杂度。
解答：根据已知条件，A和B是两个递增有序表，所以可以先取A表的表头建立空的C表。然后同时扫描A表和B表，将两表中最大的结点从对应表中摘下，并作为开始结点插入C表中。如此反复，直到A表或B表为空。最后将不为空的A表或B表中的结点依次摘下并作为开始结点插入C表中。这时，得到的C表就是由A表和B表归并成的一个按元素值递减有序的单链表C。并且辅助空间为O(1)。
　　算法如下：
　　LinkList MergeSort ( LinkList A , LinkList B )
　　　{// 归并两个带头结点的递增有序表为一个带头结点递减有序表
　　　　ListNode *pa , *pb , *q , *C ;
　　　　pa=A->next;//pa指向A表开始结点
　　　　C=A;C->next=NULL;//取A表的表头建立空的C表
　　　　pb=B->next;//pb指向B表开始结点
　　　　free(B);//回收B表的头结点空间
　　　　while ( pa && pb)
　　　　　{
　　　　　　if ( pb->data <= pa->data )
　　　　　　　{ // 当B中的元素小于等于A中当前元素时，将pa表的开始结点摘下
　　　　　　　　q=pa;pa=pa->next;
　　　　　　　}
　　　　　　else
　　　　　　　{// 当B中的元素大于A中当前元素时，将pb表的开始结点摘下
　　　　　　　　q=pb;pb=pb->next;}
　　　　　　q->next=C->next;C->next=q;//将摘下的结点q作为开始结点插入C表
　　　　　}
　　　　//若pa表非空，则处理pa表
　　　　while(pa){
　　　　　　q=pa;pa=pa->next;
　　　　　　q->next=C->next;C->next=q;}
　　　　//若pb表非空，则处理pb表
　　　　while(pb){
　　　　　　q=pb;pa=pb->next;
　　　　　　q->next=C->next;C->next=q;}
　　　　return(C);
　　　} 
　　该算法的时间复杂度分析如下：算法中有三个while 循环，其中第二个和第三个循环只执行一个。每个循环做的工作都是对链表中结点扫描处理。整个算法完成后，A表和B表中的每个结点都被处理了一遍。所以若A表和B表的表长分别是m和n，则该算法的时间复杂度O(m+n)
14．已知单链表L是一个递增有序表，试写一高效算法，删除表中值大于min 且小于max的结点(若表中有这样的结点)，同时释放被删结点的空间，这里min 和 max是两个给定的参数。请分析你的算法的时间复杂度。
解答：要解这样的问题，我们首先想到的是拿链表中的元素一个个地与max和min比较，然后删除这个结点。由于为已知其是有序链表，则介于min 和max之间的结点必为连续的一段元素序列。所以我们只要先找到所有大于min结点中的最小结点的直接前趋结点*p后，依次删除小于max的结点，直到第一个大于等于max结点*q位置，然后将*p结点的直接后继指针指向*q结点。 
　　算法如下：
　　void DeleteList ( LinkList L, DataType min , DataType max )
　　　{
　　　　ListNode *p , *q , *s;
　　　　p=L;
　　　　while( p->next && p->next->data <=min ) 
　　　　//找比min大的前一个元素位置
　　　　　p=p->next;
　　　　q=p->next;//p指向第一个不大于min结点的直接前趋，q指向第一个大于min的结点
　　　　while(q &&q->data<max)
　　　　　{s=q;q=q->next;
　　　　　　free(s);//删除结点，释放空间
　　　　　}
　　　　p->next=q;//将*p结点的直接后继指针指向*q结点
　　　}
15．写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。
解答：本题可以这样考虑，先取开始结点中的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。
　　具体算法：
　　　void DeleteList ( LinkList L )
　　　　{　
　　　　　ListNode *p , *q , *s;
　　　　　p=L-next;
　　　　　while( p->next&&p->next->next)
　　　　　　{
　　　　　　　q=p;//由于要做删除操作，所以q指针指向要删除元素的直接前趋
　　　　　　　while (q->next)
　　　　　　　　if (p->data==q->next->data)
　　　　　　　　　{s=q->next;q->next=s->next;free(s);//删除与*p的值相同的结点
　　　　　　　　　}
　　　　　　　　else q=q->next;
　　　　　　　p=p->next;
　　　　　　}
　　　　}　 
16．假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。
解答：已知指向这个结点的指针是*s，那么要删除这个结点的直接前趋结点，就只要找到一个结点，它的指针域是指向*s的直接前趋，然后用后删结点法，将结点*s的直接前趋结点删除即可。
　　算法如下：
　　　void DeleteNode( ListNode *s)
　　　　{//删除单循环链表中指定结点的直接前趋结点
　　　　　　ListNode *p, *q;
　　　　　　p=s;
　　　　　　while( p->next->next!=s) 
　　　　　　　p=p->next;
　　　　　　//删除结点
　　　　　　q=p->next;
　　　　　　p->next=q->next;
　　　　　　free(p); //释放空间
　　　　}
　　注意：若单循环链表的长度等于1，则只要把表删空即可。
第3章 栈和队列
1．设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：
　　(1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)?
　　(2) 能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。
　　(3)请分析 1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。
解答：(1)出栈序列为：1324
    (2)不能得到1423序列。因为要得到14的出栈序列，则应做Push(1),Pop(),Push(2),Push    (3),Push(4),Pop()。这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。能得到1432的出栈序列。具体操作为：Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。
　　(3)在1，2 ，3 ，4 的24种排列中，可通过相应入出栈操作得到的序列是：
　　    1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321
      不能得到的序列是：
　　　　1423,2413,3124,3142,3412,4123,4132,4213,4231,4312
2 链栈中为何不设置头结点?
解答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。
3 循环队列的优点是什么? 如何判别它的空和满?
解答：循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。
4 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢?
解答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。
5 指出下述程序段的功能是什么?
(1) void Demo1(SeqStack *S){
　　　　 int i; arr[64] ; n=0 ;
　　　　 while ( StackEmpty(S)) arr[n++]=Pop(S);
　　　　 for (i=0, i< n; i++) Push(S, arr[i]);
　　　 } //Demo1
(2) SeqStack S1, S2, tmp;
　　 DataType x;
　　 ...//假设栈tmp和S2已做过初始化
　　 while ( ! StackEmpty (&S1))
　　　 {
　　　　 x=Pop(&S1) ;
　　　　 Push(&tmp,x);
　　　 }
　　 while ( ! StackEmpty (&tmp) )
　　　 {
　　　　 x=Pop( &tmp);
　　　　 Push( &S1,x);
　　　　 Push( &S2, x);
　　　 }
(3) void Demo2( SeqStack *S, int m)
　　　 { // 设DataType 为int 型
　　　　 SeqStack T; int i;
　　　　 InitStack (&T);
　　　　 while (! StackEmpty( S))
　　　　　 if(( i=Pop(S)) !=m) Push( &T,i);
　　　　 while (! StackEmpty( &T))
　　　　　 {
　　　　　　i=Pop(&T); Push(S,i);
　　　　　 }
　　　 }
(4)void Demo3( CirQueue *Q)
　　　 { // 设DataType 为int 型
　　　　 int x; SeqStack S;
　　　　InitStack( &S);
　　　　 while (! QueueEmpty( Q ))
　　　　　{x=DeQueue( Q); Push( &S,x);}
　　　　 while (! StackEmpty( &s))
　　　　　 { x=Pop(&S); EnQueue( Q,x );}
　　　 }// Demo3
(5) CirQueue Q1, Q2; // 设DataType 为int 型
　　 int x, i , n= 0;
　　 ... // 设Q1已有内容， Q2已初始化过
　　 while ( ! QueueEmpty( &Q1) )
　　　 { x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); n++;}
　　 for (i=0; i< n; i++)
　　　 { x=DeQueue(&Q2) ;
　　EnQueue( &Q1, x) ; EnQueue( &Q2, x);}
解答：(1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在64个以内。
　　(2)程序段的功能是利用tmp栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去。
　　(3)程序段的功能是利用栈T，将一个非空栈S中值等于m的元素全部删去。
　　(4)程序段的功能是将一个循环队列Q经过S栈的处理，反向排列，原来的队头变成队尾，原来的队尾变成队头。
　　(5)这段程序的功能是将队列1的所有元素复制到队列2中去，但其执行过程是先把队列1的元素全部出队，进入队列2，然后再把队列2的元素复制到队列1中。
6 回文是指正读反读均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)
解答：根据提示，算法可设计为：
　//以下为顺序栈的存储结构定义
　#define StackSize 100 //假定预分配的栈空间最多为100个元素
　typedef char DataType;//假定栈元素的数据类型为字符
　typedef struct{
　　DataType data[StackSize];
　　int top;
　}SeqStack; 

　int IsHuiwe