将 (b1, b2, …, bn )从链表的当前位置上删除之后再插入 a1 到之前，并将 am设为表尾。
ta L a1 a2 hb tb … am ∧ b1 b2 … bn ∧ ta->next=NULL; tb->next = L->next; L->next = hb;
void exchange( SLink &L, int m ) { // 互换链表中前 m 个和后 n 个结点 ta = L; i = 0;
while ( ta && i ta = ta->next; i++; }// while if ( ta && ta->next ) { // m < 表长 hb = ta->next; tb = hb; while (tb->next) tb = tb->next; // 查询表尾 bn修改指针 } 算法的时间复杂度:为:O(ListLength(L)) 4．讨论线性表的逻辑结构和存储结构的关系，以及不同存储结构的比较。 【答案】存储结构分为： ⑴顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系 链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系 ⑵数据的逻辑结构—只抽象反映数据元素的逻辑关系 数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现 ⑶数据的逻辑结构与存储结构密切相关： 算法设计 → 逻辑结构 算法实现 → 存储结构 ⑷顺序表： 可以实现随机存取：?(1) 插入和删除时需要移动元素：?(n) 需要预分配存储空间; 适用于―不常进行修改操作、表中元素相对稳定‖的场合。 链表： 只能进行顺序存取：?(n) 插入和删除时只需修改指针：?(1) 不需要预分配存储空间; 适用于―修改操作频繁、事先无法估计最大表长‖的场合。 —— 应用问题的算法时间复杂度的比较 例如，以线性表表示集合进行运算的时间复杂度为?(n2), 而以有序表表示集合进行运算的时间复杂度为?(n) 习 题 2 1．判断下列概念的正确性 (1) 线性表在物理存储空间中也一定是连续的。 (2) 链表的物理存储结构具有同链表一样的顺序。 (3) 链表的删除算法很简单，因为当删去链表中某个结点后，计算机会自动地将后继的各个单元向前移动。 答：（1）（2）（3）都不正确。 2. 有如下图所示线性表，经过daorder 算法处理后，线性表发生了什么变化？画出处理后的线性表。 void daorder() { int i, j, n ; ElemType x; n=length/2; for( i=0 ; i { j=length-i-1; x=elem[i]; elem[i]=elem[j]; elem[j]=x; } } elem[0] ?? elem[7] 假设length=8 1 2 3 4 5 6 7 8 … 答：经过daorder 算法处理后，线性表发生了逆置。处理后的线性表为： 3．试比较顺序存储结构和链式存储结构的优缺点。 答： 顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，，要求内存中存储单元的地址必须是连续的。 优点：一般情况下，存储密度大，存储空间利用率高。 缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难以扩充。 链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。 优点：插入和删除元素时很方便，使用灵活。 缺点：存储密度小，存储空间利用率低。 4．试写出一个计算链表中结点个数的算法，其中指针ｐ指向该链表的第一个结点。 答：int linklist_num(linklist L,Lnode *p) { int n=0; While(p){n++;p=p->next;} Return n: 8 7 6 5 4 3 2 1 … } 5．试设计实现在单链表中删去值相同的多余结点的算法。 (a)为删除前，(b)为删除后。 答：void Deletaz(Linklist L) { Lnode *p,*q,*r,*s; P=l->next; while (p) {q=p;r=q->next; while(r){if(r->data!=p->data){q=r;r=r->next}; else{s=r->next;q->next=s;free(r);r=s;} } P=p->next; } } 6. 有一个线性表(a1,a2,...,an)，它存储在有附加表头结点的单链表中，写一个算法，求出该线性表中值为x的元素的序号。如果x不存在，则输出序号为零。 答：int linklist_x(linklist L,datatype x) H 10 15 18 15 10 ∧(a) 删除前 H 10 15 18 ∧(b) 删除后 {int i=0;Lnode *p; P=L->next; While(p&&p->dada!=x){i++;p=p->next;} If(!p)return 0; Else return I; } 7．写一个算法将一单链表逆置。要求操作在原链表上进行。 答：void reverse (LinkList L) { p=L->next; L->next=NULL; while (p) { q=p->next; p->next=L->next; L->next=p; p=q; } } 8．在一个非递减有序线性表中，插入一个值为X的元素，使插入后的线性表仍为非递减有序。分别用向量和单链表编写算法。 答：void insert_x(Linklist L,Datatype x) /*在递增有序的单链表L中插入值为x的元素，使得插入后L仍然有序*/ {Lnode *p,*q,*r; P=L;q=p->next; While(q&&q->dada<=x) {p=q;q=q->next;} R=(Lnode *)malloc(Lnode); r->dada=x; r->next=q; p->next=r; } 9．写一算法将值为B的结点插在链表中值为a的结点之后。如果值为a的结点不存在，则插在表尾。 答: void Insert_LinkList( LinkList L, DataType a, DataType B) { /* 在值为a 的结点后插入值为B的结点，表中若无a则B接在表尾 */ LinkList p,q,s ; s=( LinkList)malloc(sizeof(struct node)); s->data=B; s->next=NULL; q=L; p=L->next; while( p!=NULL && p->data!=a ) { q=p; p=p->next; } if(p){s->next=p->next;p->next=s;} } else{ s->next=q->next;q->next=s;} 10．试用循环链表为存储结构，写一个约瑟夫(Josephu)问题的算法。约瑟夫问题是：有N个人围成一圈，从第i个人开始从1报数，数到m时，此人就出列。下一个人重新从1开始报数，再数到m时，以一个人出列。直到所有的人全部出列。按出列的先后得到一个新的序列。例如，N=5， i=1, m=3 时新的序列应为：3, 1, 5, 2, 4。 答： typedef struct node /* 结点的结构定义 */ { int num; /* 编号子域 */ struct node *next; /* 指针域 */ }JOS; void outs(JOS *h, int m) { int i; JOS *q=h, *p; printf(―\\n ―); while (q->next!=q) { for(i=1;i printf(―m \\n‖,q->num); /* 输出最后一个结点的编号值 */ free(q); } /* outs */ 11. 设有两个单链表A、B，其中元素递增有序，编写算法将A、B归并成一个按元素值递减（允许有相同值）有序的链表C，要求用A、B中的原结点形成，不能重新申请结点。 答：void unit(Linklist A,Linklist B,Linklist C) {Lnode *p,*q,*r,*s; P=A->next;q=>next;C=A;r=C; While(p&&q) {if(p->dada<=q->dada){r=p;p=p->next;} Else{s=q;q=q->next;s->next=r->next;r->next=s;r=s;} } If(!p)r->next=q;free(B) } 讨论小课堂 3 【参考内容】 1. 如果输入序列为1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列:4 3 5 6 1 2和1 3 5 4 2 6;请说明为什么不能实现或如何才能得到。 2. 设输入序列为2，3，4，5，6，利用一个栈能得到序列2，5，3，4，6吗？栈可以用单链表实现吗？