数据结构（C语言版，严蔚敏 编著） 考前巩固

四、算法题

1.线性链表 Create

• 逆序建立（头插法）：先建立头节点，再从后往前添加元素。

void List_Create(LinkList &L,int n){
//逆位序输入 n 个元素的值，建立单链表L。
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;//先建立 头节点
	for( i = n; i > 0; --i ){//循环生成其他结点
		p = (LinkList)malloc(sizeof(LNode));
		scanf(&p->data);
		p->next = L->next;
		L->next = p;
	}
}

• 顺序建立（尾插法）：

void CreateList2(LinkList& L,int n){	
	L = (LinkList)malloc(sizeof(LNode)); 
	L->next = NULL;
	q = L;
	for( i = 1; i <= n; i++ ){
		p = (LinkList)malloc(sizeof(LNode));
		scanf(&p->data);
		q->next = p;
		q = q->next;
	}
	p->next = NULL;//next域置空。
}

2.线性链表 Delete

Status List_Delete(LinkList &L,int i,ElemType &e){
//在单链表L中，删除第 i 个元素，并由 e 返回其值。
	p = L;
	j = 0;
	while( p->next && j < i-1 ){//让 p 指向待删除结点的前驱，即 i-1
		p = p->next;
		++j;
	}
	if( !( p->next ) || j > i-1 ){//p 指向了最后一个元素 || j 超出 待删除的位置i （在数组中的位置i-1）
		return ERROR;
	}
	q = p->next;
	p->next = q->next;
	e = q->data;
	free(q);
	return OK;
}

free(q);：由系统回收一个 LNode 型的结点，回收后的空间可以备作再次生成结点时使用。

3.线性链表 Insert

Status List_insert(LinkList &L,int i,ElemType e){
//在单链表L中，插入元素 e 到第 i 个位置。原第 i 个元素的位置变为 i+1。 
	p = L;
	j = 0;
	while( p && j < i-1 ){//查找第 i-1 个值
		p = p->next;
		++j; 
	}
	if( !p || j > i-1 ){//指针 p 为空 || j 超出 目的插入位置i （在数组中的下标i-1）
		return ERROR;
	}
	s = (LinkList)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return OK;
}

s = (LinkList)malloc(sizeof(LNode));：由系统生成一个 LNode 型的结点，同时将该结点的起始位置赋给指针变量 s。

4.

5. 折半查找算法 p220

int Search_Bin(SSTable ST, KeyType key){
	low = 1;
	high = ST.length;
	while(low <= high){
		mid = (low + high) / 2;
		if( EQ( key,ST.elem[mid].key ) ){//找到带查找元素
			return mid;
		}else if( LT( key,ST.elem[mid].key ) ){
			high = mid -1;
		}else{
			low = mid +1;
		}
	}
	return 0;
}

6.

7.循环队列的入队算法 p65

Status EnQueue(SqQueue &Q, QElemType e){
// 插入新的队尾元素 e
	if( ( Q.rear+1 ) % MAXQSIZE == Q.front ){
		return ERROR;
	}
	Q.base[Q.rear] = e;
	Q.rear = (Q.rear + 1) % MAXQSIZE;
	return OK;
}

出队(不在老师给考试的范围内)：

Status DeQueue(SqQueue &Q, QElemType &e){
//
	if( Q.rear == Q.front ){
		return ERROR;
	}
	e = Q.base[Q.front];
	Q.front = (Q.front + 1) % MAXQSIZE;
	return OK;
}

8.顺序栈的出栈算法 p47

Status Pop(SqStack &S, SElemType &e){
//栈不为空，则删除 S 的栈顶元素
	if(S.top == S.base){
		return ERROR;
	}
	e = * --S.top;
	return OK;
}

知识点

衡量一个算法好坏的量度：

• 时间复杂度：衡量算法执行的时间量级。
• 空间复杂度：衡量算法的数据结构所占存储以及大量的附加存储。
• 算法的其他性能：

chap 3 栈

stack 是限定仅在表尾进行插入或删除操作的线性表。表尾为栈顶(top)，表头为栈底(bottom)。
遵循后进先出原则。可类比铁路调度站。

• base栈底指针：
• top栈顶指针：
  top = base;可以作为栈空的标记。非空栈的栈顶指针始终在栈顶元素的下一个位置上。
• stacksize已分配的存储空间

条件：

• 栈满条件：S.top - S.base >= S.stacksize
• 栈空条件：S.top == S.base

chap 3 队列

循环队列：

• front队列头指针：删除头元素时，头指针 +1，头指针始终指向队头元素。
• rear队列尾指针：插入尾元素时，尾指针 +1，尾指针始终指向队尾元素的下一个位置。

只凭 Q.front == Q.rear 无法判断队列空间是“空”还是“满”。
处理方法：少用一个元素空间，约定以 “front 在 rear 的下一位置上” 作为队列呈“满”状态的标志。

• 队满条件：(Q.rear + 1) % MAXQSIZE == Q.front
• 队空条件：Q.front == Q.rear

chap 9 静态查找

通常以“其关键字和给定值进行过比较的记录个数的平均值”作为衡量查找算法好坏的依据。
等概率下顺序查找的平均查找长度：ASL = (n+1)/2

顺序表的查找：

• 优点：算法简单，适应面广。对表的结构无任何要求，无论记录是否按关键字有序均可应用。
• 缺点：平均查找长度较大，特别是当n很大时，查找效率较低。

有序表的查找：（折半查找）

• low
• mid = (low + high) / 2
• high

1. 折半查找过程：以处于区间中间位置记录的关键字和给定值比较，若相等，则查找成功，若不等，则缩小范围。
2. 性能分析：
   折半查找过程可以用二叉树叙述，也叫判定树。
   ∵ 折半查找在查找成功时，进行比较的关键字个数最多不超过树的深度h。
   ∵ 而具有n个结点的判定树的深度为 h=(log₂n)+1。
   ∴ 折半查找法在查找成功时，和给定值进行比较的关键字个数至多为 h=(log₂n)+1。
3. 折半查找的平均查找长度：
   ASL_bs = log₂(n+1) - 1
4. 优缺点分析：
   优点：折半查找的效率比顺序查找高。
   缺点：只适用于有序表，且限于顺序存储结构。对线性链表无法有效的进行折半查找。