算法 1：
void invert( ElemType R[]，int s， int t )
/* 本算法将数组 R 中下标自 s 到 t 的元素逆置， 即将（Rs, Rs+1, …, Rt-1, Rt ） 改变为（Rt, Rt-1, …, Rs+1, Rs ）*/
void exchange ( SqList A; int m ) {
/*本算法实现顺序表中前 m 个元素和后 n 个元素的互换*/ n = A.length – m;
invert( A.elem, 0, A.length ); invert( A.elem, 0, n-1 ); invert( A.elem, n, m+n-1 ); } 算法 2:
void exchange( SqList A, int m ) {
/* 实现顺序表 A 中前 m 个元素和后 n 个元素互换*/ for ( i=0; j = m; ji; k-- ) A.elem[j] = A.elem[j-1]; A.elem[i] = x; }
算法的时间复杂度:为: O(m?n) 算法设计:
将 (b1, b2, …, bn )从链表的当前位置上删除之后再插入 a1 到之前，并将 am设为表尾。
ta L a1 a2 hb tb b2 … am ∧ b1 … 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 算法处理后，线性表发生了逆置。处理后的线性表为： 8 7 6 5 4 3 2 1 … 3．试比较顺序存储结构和链式存储结构的优缺点。 答： 顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，，要求内存中存储单元的地址必须是连续的。 优点：一般情况下，存储密度大，存储空间利用率高。 缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难以扩充。 链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。 优点：插入和删除元素时很方便，使用灵活。 缺点：存储密度小，存储空间利用率低。 4．试写出一个计算链表中结点个数的算法，其中指针ｐ指向该链表的第一个结点。 答：int linklist_num(linklist L,Lnode *p) { int n=0; While(p){n++;p=p->next;} Return n: } 5．试设计实现在单链表中删去值相同的多余结点的算法。 (a)为删除前，(b)为删除后。 10 H 10 ∧18 15 15 (a) 删除前 10 H 15 18 ∧ (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) {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;} }