数据结构

2021-09-05
作者 ZXY39
~6.12K 字

数据结构

线性结构

堆栈

引入:后缀表达式,从左往右扫描，逐个处理运算数和运算符号。

特点：只在一端（栈顶Top）做插入删除，先入后出（Last In First Out）
入栈（Push）：插入数据
出栈（Pop）：删除数据

使用例

1.一个数组实现两个堆栈

#define MaxSize
struct DStack{
Elementtype Data[MaxSize];
int Top1;
int Top2;
}S;
S.Top1=-1;
S.Top2=MaxSize;//分别表示两个数组空的位置
void Push(struct DStack *PtrS,ElementType item, int Tag)//入栈
{	
    if(PtrS->Top2-Ptrs->Top1==1)printf("堆栈满");//两堆栈挨在一起
    根据tag写入不同堆栈PtrS->Data[++(Ptrs->Top1)或--(Ptrs->Top1)]=item;
}

2.中缀表达式转换为后缀表达式

从头到尾读取中缀表达式的每个对象，对不同对象按不同的情况处理。

运算数：直接输出；
左括号：压入堆栈；
右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）；
运算符：
• 若优先级大于栈顶运算符时，则把它压栈；
• 若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出；再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈；
若各对象处理完毕，则把堆栈中存留的运算符一并输出。

3.堆栈的其他应用：

函数调用及递归实现
深度优先搜索
回溯算法
。。。

队列

队列(Queue)：：具有一定操作约束的线性表
插入和删除操作：只能在一端插入，而在另一端删除

数据插入：入队列（AddQ）
数据删除：出队列（DeleteQ）
先来先服务
先进先出：FIFO

队列的顺序存储实现

队列的顺序存储结构通常由一个一维数组和一个记录队列头元
素位置的变量front以及一个记录队列尾元素位置的变量rear组成。

#define MaxSize < 储存数据元素的最大个数>
struct QNode {
ElementType Data[ MaxSize ];
int rear;
int front;
};
typedef struct QNode *Queue;

特性：front=rear时堆栈空或满。

顺环序列：

数组最后一位连接第一位。

区分堆栈空或满所使用的方法：

引入变量标记：Size（记录录入数据总数）或Tag（记录最后一次的操作是录入还是删除）。
让数组空一个出来：仅堆栈满时满足rear+1=front，仅堆栈空时满足front=rear。

在顺环序列中的具体实现：堆栈满：

1.入队列

void AddQ( Queue PtrQ, ElementType item)
{
if ( (PtrQ->rear+1) % MaxSize == PtrQ->front ) {
printf(“ 队列满”);
return;
}
PtrQ->rear = (PtrQ->rear+1)% MaxSize;
PtrQ->Data[PtrQ->rear] = item;
}

2.出队列

ElementType DeleteQ ( Queue PtrQ )
{
if ( PtrQ->front == PtrQ->rear ) {
printf(“ 队列空”);
return ERROR;
} else {
PtrQ->front = (PtrQ->front+1)% MaxSize;
return PtrQ->Data[PtrQ->front];
}
}

队列的链式存储实现

struct Node{
ElementType Data;
struct Node *Next;
};
struct QNode{ /*  链队列结构 */
struct Node *rear; /*  指向队尾结点 */
struct Node *front; /*  指向队头结点 */
};
typedef struct QNode *Queue;
Queue PtrQ;

不带头结点的链式队列出队操作的一个示例：

ElementType DeleteQ ( Queue PtrQ )
{ 
struct Node *FrontCell;
ElementType FrontElem;
if ( PtrQ->front == NULL) {
printf(“ 队列空”); return ERROR;
}
FrontCell = PtrQ->front;
if ( PtrQ->front == PtrQ->rear) /*  若队列只有一个元素 */
PtrQ->front = PtrQ->rear = NULL; /*  删除后队列置为空 */
else
PtrQ->front = PtrQ->front->Next;
FrontElem = FrontCell->Data;
free( FrontCell ); /*  释放被删除结点空间 */
return FrontElem;
}

应用: 多项式加法运算

采用不带头结点的单向链表，按照指数递减的顺序排列各项

struct PolyNode {
int coef; //  系数
int expon; //  指数
struct PolyNode *link; //  指向下一个节点的指针
};
typedef struct PolyNode *Polynomial;
Polynomial P1, P2;

算法思路：两个指针P1 和P2 分别指向这两个多项式第一个结点，不断循环,赋值给结果多项式：

P1->expon==P2->expon: 系数相加，若结果不为0，则作为结果多项式对应项的系数。同时，P1和P2都分别指向下一项；
P1->expon>P2->expon: 将P1的当前项存入结果多项式，并使P1指向下一项；
P1->exponexpon: 将P2的当前项存入结果多项式，并使P2指向下一项；
当某一多项式处理完时，将另一个多项式的所有结点依次复制到结果多项式中去。

Polynomial PolyAdd (Polynomial P1, Polynomial P2)
{
Polynomial front, rear, temp;
int sum;
rear = (Polynomial) malloc(sizeof(struct PolyNode));
front = rear; /*  由front  记录结果多项式链表头结点 */
while ( P1 && P2 ) /*  当两个多项式都有非零项待处理时 */
switch ( Compare(P1->expon, P2->expon) ) {
case 1:
Attach( P1->coef, P1->expon, &rear);
P1 = P1->link;
break;
case -1:
Attach(P2->coef, P2->expon, &rear);
P2 = P2->link;
break;
case 0:
sum = P1->coef + P2->coef;
if ( sum ) Attach(sum, P1->expon, &rear);
P1 = P1->link;
P2 = P2->link;
break;
}
/*  将未处理完的另一个多项式的所有节点依次复制到结果多项式中去 */
for ( ; P1; P1 = P1->link ) Attach(P1->coef, P1->expon, &rear);
for ( ; P2; P2 = P2->link ) Attach(P2->coef, P2->expon, &rear);
rear->link = NULL;
temp = front;
front = front->link; /* 令front 指向结果多项式第一个非零项 */
free(temp); /*  释放临时空表头结点 */
return front;
}
void Attach( int c, int e, Polynomial *pRear )
{ /*  由于在本函数中需要改变当前结果表达式尾项指针的值， */
/*  所以函数传递进来的是结点指针的地址，*pRear 指向尾项*/
Polynomial P;
P =(Polynomial)malloc(sizeof(struct PolyNode)); /*  申请新结点 */
P->coef = c; /*  对新结点赋值 */
P->expon = e;
P->link=NULL;
/*  将P 指向的新结点插入到当前结果表达式尾项的后面 */
(*pRear)->link = P;
*pRear = P; /*  修改pRear 值 */
}

树

查找 (Searching)

静态查找：集合中记录是固定的

没有插入和删除操作，只有查找

动态查找：集合中记录是动态变化的

除查找，还可能发生插入和删除

静态查找

方法1:顺序查找（低效率）

顺序查找算法的时间复杂度为O(n)。

方法2 ：二分查找（Binary Search)

假设n 个数据元素的关键字满足有序（比如：小到大））
并且是连续存放（数组），那么可以进行二分查找

int BinarySearch ( StaticTable * Tbl, ElementType K)
{ /* 在表Tbl 中查找关键字为K 的数据元素*/
int left, right, mid, NoFound=-1;
left = 1; /* 初始左边界*/
right = Tbl->Length; /* 初始右边界*/
while ( left <= right )
{
mid = (left+right)/2; /* 计算中间元素坐标*/
if( K < Tbl->Element[mid]) right = mid-1; /* 调整右边界*/
else if( K > Tbl->Element[mid]) left = mid+1; /* 调整左边界*/
else return mid; /* 查找成功，返回数据元素的下标*/
}
return NotFound; /* 查找不成功，返回-1*/
}