答：int DeleteAndInsertSub(LinkList &la,LinkList &lb,int i,int j,int len)
{
int k;
LinkList p,q,prev,s; if(i<0||j<0||len<0)
return -1; p=la;
k=1;
prev=NULL; while(p&&k<i)
{
prev=p; p=p-
>next; k++;
}
 
if(!p)
return -1; q=p;k=1; while(q&&k<len)
{
q=q->next; k++;
}
if(!q)
return -1; if(!prev)
la=q->next; else
prev->next=q->next;
if(j==1)
{
 


}
else
{
 
q->next=lb; lb=q;



s=lb;k=1; while(s&&k<j-1)
{
 
s=s->next; k++;
}
if(!s)
return -1; q->next=s->next; s->next=p; return 1;
}
}

4．写一算法，将一带有头结点的单链表就地逆置，即要求逆置在原链表上进行，不允许 重新构造新链表。

(a)

           

(b)

           

图    单链表的倒置
 
函数原型如下：
void LinkList_reverse(LinkList &L)；

答：void LinkList_reverse(LinkList &L)
{
LinkList p,q,s;
p=L->next;q=p->next;s=q->next;p->next=NULL; while(s->next)
{
q->next=p;p=q; q=s;s=s-
>next;
}
q->next=p;s->next=q;L->next=s;
}

5．写一算法，将带有头结点的非空单链表中数据域值最小的那个结点移到链表的最前面。 要求：不得额外申请新的链结点。函数原型如下：
void delinsert(LinkList &L)；

答：void delinsert(LinkList &L)
{
p=L->next;    //p 是链表的工作指针
pre=L;    //pre 指向链表中数据域最小值结点的前驱
q=p;    //q 指向数据域最小值结点，初始假定是第一结点
while(p->next!=NULL)
{
if(p->next->data<q->data)    //找到新的最小值结点
{    pre=p;    q=p->next; } p=p->next;
}
if(q!=L->next)    //若最小值是第一元素结点，则不需再操作
{
pre->next=q->next;    //将最小值结点从链表上摘下
q->next=L->next;    //将 q 结点插到链表最前面
L->next=q;
}
}

6．编写一个算法来交换单链表中指针 P 所指结点与其后继结点，HEAD 是该链表的头指针， P 指向该链表中某一结点。 答：单链表中查找任何结点，都必须从头指针开始。本题要求将 指针 p 所指结点与其后继结 点交换，这不仅要求知道 p 结点，还应知道 p 的前驱结点。这样 才能在 p 与其后继结点交换 后，由原 p 结点的前驱来指向原 p 结点的后继结点。
LinkedList Exchange（LinkedList HEAD，p）
 
∥HEAD 是单链表头结点的指针，p 是链表中的一个结点。本算法将 p 所指结点与其后继结
点交换。
{q=head->next；    ∥q 是工作指针，指向链表中当前待处理结点。
pre=head；    ∥pre 是前驱结点指针，指向 q 的前驱。
while（q!=null && q!=p）{pre=q；q=q->next；}    ∥未找到 p 结点，后移指针。 if（ p->next==null）printf（“p 无后继结点\n”）;    ∥p 是链表中最后一个结点，无后 继。
Else    ∥处理 p 和后继结点交换
{q=p->next；    ∥暂存 p 的后继。
pre->next=q；    ∥p 前驱结点的后继指向 p 的后继。
p    ->next=q->next；∥p 的后继指向原 p 后继的后继。
q    ->next=p    ；∥原 p 后继的后继指针指向 p。
}
}∥算法结束。

7．已知线性链表第一个链结点指针为 list，请写一算法，将该链表分解为两个带有头结 点的循环链表，并将两个循环链表的长度分别存放在各自头结点的数据域中。其中,线性表 中序号为偶数的元素分解到第一个循环链表中,序号为奇数的元素分解到第二个循环链表 中。
答：算法如下：
void split(ListNode *List, ListNode *&list1, ListNode *&list2)
{
list1=(ListNode *)malloc(sizeof(ListNode ))； list2=(ListNode *)malloc(sizeof(ListNode ))； p=list;；
q=list1； r=list2； len1=0； len2=0
； mark=1； while (p!=null)
{
if(mark=1)
{
q->next=p; q=q->next; len1++; mark=2;
}
else
{
r->next=p; r=r->next; len2++;
 
mark=1;
}
}
list1->data=len1; list2->data=len2; q->next=list1;
r->next=list2;
}

8. 设 A 和 B 是两个单链表，其表中元素递增有序。
试写一算法将 A 和 B 归并成一个按元素值递减有序的单链表 C，并要求辅助空间为 O(1)。 答
：Linklist merge(Linklist A,Linklist B)
{
Linklist C; Listnode *p; C=null; while (A&&B)
if(A->data<=B->data)
{p=A->next;A->next=C;C=A;A=p;} else
{p=B->next;B->next=C;C=B;B=p;} if (A)
while(A) { p=A->next;A->next=C;C=A;A=p;} else
while(B) {p=B->next;B->next=C;C=B;B=p;} return C;
}

二、栈、队列和数组

大纲要求：

（一） 栈和队列的基本概念
（二） 栈和队列的顺序存储结构
（三） 栈和队列的链式存储结构
（四） 栈和队列的应用
（五） 特殊矩阵的压缩存储 知识点：
1．栈、队列的定义及其相关数据结构的概念，包括：顺序栈、链栈、循环队列、链队列等。 栈与队列存取数据（请注意包括：存和取两部分）的特点。
2． 掌握顺序栈和链栈上的进栈和退栈的算法，并弄清栈空和栈满的条件。注意因栈在一端
 
操作，故通常链栈不设头结点。
3． 如何将中缀表达式转换成前缀、后缀表达式，了解对两种表达式求值的方法。
4．栈与递归的关系。用递归解决的几类问题：问题的定义是递归的，数据结构是递归的， 以及问题的解法是递归的。掌握典型问题的算法以及将递归算法转换为非递归算法，如 n!阶乘问题，fib数列问题，hanoi问题。了解在数值表达式的求解、括号的配对等问题 中应用栈的工作原理。
5． 掌握在链队列上实现入队和出队的算法。注意对仅剩一个元素的链队列删除元素时的处 理
（令队尾指针指向队头）。还需特别注意仅设尾指针的循环链队列的各种操作的实现
6．循环队列队空及队满的条件。队空定义为队头指针等于队尾指针，队满则可用牺牲一 个单元或是设标记的方法，这里特别注意取模运算。掌握循环队列中入队与出队算法。
7． 在后续章节中多处有栈和队列的应用，如二叉树遍历的递归和非递归算法、图的深度优
先遍历等都用到栈，而树的层次遍历、图的广度优先遍历等则用到队列。这些方面的应 用应重点掌握。
8． 数组在机器（内存）级上采用顺序存储结构。掌握数组（主要是二维）在以行序为主和 列序为主的存储中的地址计算方法。
9． 特殊矩阵（对称矩阵、对角矩阵、三角矩阵）在压缩存储是的下标变换公式。




练习题：

（一）选择题：

1.    一个栈的输入序列为 1 2 3 4，则（ D    ）不可能是其出栈序列。
A. 1 2 4 3    B. 2 1 3 4    C. 1 4 3 2    D. 4 3 1 2
2.    一个递归算法必须包括（    B    ）。
A. 递归部分    B. 终止条件和递归部分
C. 迭代部分    D.终止条件和迭代部分
3.        一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来 看，通常递归过程比非递归过程（B）。





5.    二维数组 N 的元素是 4 个字符（每个字符占一个存储单元）组成的串，行下标 i 的范 围从 0 到 4，列下标 j 的范围从 0 到 5，N 按行存储时元素 N[3][5]的起始地址与 N 按列
存储时元素（    B    ）的起始地址相同。
A. N[2][4]        B. N[3][4]
C. N[3][5]        D. N[4][4]
6.    设有数组 A[i,j]，数组的每个元素长度为 3 字节，i 的值为 1 到 8，j 的值为 1 到 10，
数组从内存首地址 BA 开始顺序存放，当以列为主序存放时，元素 A[5,8]的存储首地
 

址是（    B    ）
A. BA+141    B. BA+180
C. BA+222    D. BA+225
7.  递归过程或函数调用时，处理参数及返回地址，要用一种称为（ C ）的数据结构。
A．队列    B．多维数组
C．栈    D. 线性表
8.    对于单链表形式的队列，队空的条件是（ A ）
A．F＝R＝nil    B．F＝R
C．F≠nil 且 R＝nil    D．R－F＝1
9. 若循环队列以数组 Q[0..m-1]作为其存储结构，变量 rear 表示循环队列中的队尾元素 的实际位置，其移动按 rear=(rear+1) Mod m 进行，变量 length 表示当前循环队列 中的元素个数，则循环队列的队首元素的实际位置是（ C ）
A．rear-length B．(rear- length+m) Mod m
C．(1+rear+m-length) Mod m D．M- length





（二）应用题

1、（10 分）假设一个准对角矩阵
 
a11
a21









 
a12 a22
 


a33 a43
 


a34 a44
 





.....
 






ai, j
 








....
 








a2m1, 2m1
 











a2m1,2m 
