数据结构题集-第二章-线性表-算法设计题一

说明

• 本文参照严蔚敏《数据结构(C语言版)题集》一书中包含的问答题和算法设计题目，提供解答，后续文章还有算法的解决方案。
• 请读者在自己已经解决了某个题目或进行了充分的思考之后，再参考本解答，以保证复习效果。
• 由于作者水平所限，本解答中一定存在不少这样或者那样的错误和不足，希望读者们在阅读中多动脑、勤思考，争取发现和纠正这些错误，写出更好的算法来。

2.10 指出以下算法中的错误和低效之处

并将它改写为一个既正确又高效的算法。

Status DeleteK(SqList &a,int i,int k)
{
	//本过程从顺序存储结构的线性表 a 中删除第 i 个元素起的 k 个元素
	if(i<1||k<0||i+k>a.length) return INFEASIBLE;//参数不合法
	else {
		for(count=1;count<k;count++){
			//删除一个元素
			for(j=a.length;j>=i+1;j--) a.elem[j-1]=a.elem[j];
			a.length--;
		}
	}
	return OK;
} // DeleteK

解：
以上算法每次将超出表范围的一个未知数不断代替前面的元素，
无法删除串长为1的字串，产生了过多的重复移动，删除结束后，将第i个元素之后所有元素的值都丢失。
重新分析后，改进的算法可以把删除字串后的新后缀整个移动到它们的新位置。
这里实现该算法时，完全遵照原书中的类型和数据结构，并提供随机初始化，便于测试。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

#define MAX_TEST_LENGTH 123
#define MAX_TEST_ELEM 1000
typedef int ElemType;
typedef struct{
	ElemType *elem; // 存储空间基址
	int length; // 当前长度
	int listsize; // 当前分配的存储容量
} SqList; // 顺序表类型
typedef struct LNode{
	ElemType data;
	struct LNode *next;
} LNode, *LinkList; // 线性链表类型

Status InitList_Sq(SqList *pL){
	// 构造一个空的线性表
	(*pL).elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
	if(!(*pL).elem) exit(OVERFLOW); // 存储分配失败
	(*pL).length = 0; // 空表长度为0
	(*pL).listsize = LIST_INIT_SIZE; // 初始存储容量
	return OK;
}// InitList_Sq

Status ListInsert_Sq(SqList *pL, int i, ElemType e){
	// 在顺序线性表L中第i个位置之前插入新的元素e
	// i的合法值范围：[1,ListLength_Sq(L)+1]
	if(i<1 || i>((*pL).length+1)) return ERROR; // i值不合法
	if((*pL).length>=(*pL).listsize){ // 当前存储空间已满，增加分配
		ElemType *newbase = (ElemType *)realloc((*pL).elem,((*pL).listsize+LISTINCREMENT)*sizeof(ElemType));
		if(!newbase) exit(OVERFLOW); // 存储分配失败
		(*pL).elem = newbase; // 新基址
		(*pL).listsize += LISTINCREMENT; // 增加存储容量
	}
	ElemType *p = NULL;
	ElemType *q = &((*pL).elem[i-1]); // q为插入位置
	for(p=&((*pL).elem[(*pL).length-1]);p>=q;--p) *(p+1) = *p; // 插入位置及之后的元素右移
	*q = e; // 插入e
	++((*pL).length); // 表长增1
	return OK;
}// ListInsert_Sq

Status FreeList_Sq(SqList *pL){
	// 释放线性表
	if(NULL!=(*pL).elem){
		free((*pL).elem);
		return OK;
	}else{
		return ERROR;
	}
}// FreeList_Sq

Status rand_init_list(SqList *pL){
	int pos;
	time_t t;
	int count = MAX_TEST_LENGTH;
	if(OK!=InitList_Sq(pL)) return ERROR;
	srand((unsigned)time(&t)); //初始化随机数发生器
	while(count--){
		if(OK!=ListInsert_Sq(pL,1+rand()%((*pL).length+1),(rand()%MAX_TEST_ELEM)))
			return ERROR; // 随机找一个合法位置插入新随机元素
	}
	return OK;
}

void display_list(SqList L){
	int i;
	for(i=1;i<=L.length;i++){
		printf("%3d.%d\t",i-1,L.elem[i-1]);
		if(i%7==0) putchar('\n');
	}
}

Status DeleteK(SqList *pa,int i,int k) // 低效的算法
{
	int count,j;
	//本过程从顺序存储结构的线性表 中删除第 i 个元素起的 k 个元素
	if(i<1||k<0||i+k>(*pa).length) return INFEASIBLE;//参数不合法
	else {
		for(count=1;count<k;count++){
			//删除一个元素
			for(j=(*pa).length;j>=i+1;j--) (*pa).elem[j-1]=(*pa).elem[j];
			(*pa).length--;
		}
	}
	return OK;
} // DeleteK

Status DeleteKNew(SqList *pL,int i,int k){ // 删除线性表中第i个元素起的k个元素
	int count;
	if(i<1||k<0||i+k-1>(*pL).length) return INFEASIBLE;
	for(count=1;i+count-1<=(*pL).length-k;count++) // 注意循环结束的条件
		(*pL).elem[i+count-1]=(*pL).elem[i+count+k-1];
	(*pL).length-=k;
	return OK;
}//DeleteKNew

int main(){
	SqList L;
	if(OK==rand_init_list(&L)){
		display_list(L);
		if(OK!=DeleteKNew(&L,100,1))
			printf("\nDelete error\n");
		printf("\nAfter delete:\n");
		display_list(L);
		if(OK==FreeList_Sq(&L))
			printf("Free List success!\n");
	}
	return 0;
}