数据结构——表之特殊的线性表

程序员文章站 2022-06-01 20:46:32

...

栈

只允许在一端进行插入或删除操作的线性表

顺序栈

初始化

#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];
    int top;
}SqStack;

void InitStack(SqStack &S){
    S.top=-1; //初始化栈顶指针
}

void testStack() {
    SqStack S;
    InitStack(S);
}

//判断栈空
bool StackEmpty(SqStack S){
    if(S.top==-1)
    return true;
    else
    return false;
}

//新元素进栈
bool Push(SqStack &S,ElemType x){
    if(S.top==MaxSize-1)
    return false;
    S.data[++S.top] = x;
    return true;
}

//出栈
bool Pop(SqStack &S,ElemType &x){
    if(S.top==-1)
    return false;
    x=S.data[S.top--];
    return true;
}

//读取栈顶元素
bool GetTop(SqStack S,ElemType &x){
    if(S.top==-1)
    return false;
    x=S.data[S.top];
    return true;
}

共享栈

#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];
    int top0;
    int top1;
}ShStack;

//初始化栈
void InitStack(ShStack &S){
    S.top0=-1;
    S.top1=MaxSize;
}

链栈

typedef struct Linknode{
    ElemType data;
    struct Linknode *next;
}*LiStack;

栈的应用

括号匹配

#define MaxSize 10
typedef struct{
    char data[MaxSize];
    int top;
} SqStack;

bool bracketCheck(char str[],int length) {
    SqStack S;
    InitStack(S);//初始化栈
    for(int i=0;i<length;i++) {
        if(str[i]=='(' || str[i]=='[' || str[i]=='{'){
            Push(S,str[i]);
        } else {
            if(StackEmpty(S)) //扫描到右括号，且当前栈空
            return false; //匹配失败
            char topElem;
            Pop(S,topElem);
            if(str[i]==')' && topElem!='(')
            return false;
            if(str[i]==']' && topElem!='[')
            return false;
            if(str[i]=='}' && topElem!='{')
            return false;
        }
    }
    return StackEmpty(S);
}

栈在递归中的应用

函数调用的特点：最后被调用的函数最先执行结束（LIFO）

队列

只允许在一段进行插入，在另一端删除的线性表

顺序实现

#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];
    int front,rear;
}SqQueue;

void InitQueue(SqQueue &Q){
    Q.rear=Q.fron=0;
}

void testQueue(){
    SqQueue Q;
    InitQueue(Q);
}

bool QueueEmpty(SqQueue Q){
    if(Q.rear==Q.front)
    return true;
    else
    return false;
}

//入队
bool EnQueue(SqQueue &Q,ElemType x) {
    if((Q.rear+1)5MaxSize==Q.front)
    return false;
    QQ.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MaxSize;
    return true;
}
//出队
bool DeQueue(SqQueue &Q,ElemType &x){
    if(Q.rear==Q.front)
    return false;
    x=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    return true;
}
bool GetHead(SqQueue Q,ElemType &x){
    if(Q.rear==Q.front)
    return false;
    x=Q.data[Q.front];
    return true;
}

判断队列已满/已空

方案一：
#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];
    int front,rear;
}SqQueue;

队满：(Q.rear+1)%MaxSize==Q.front（队尾指针的再下一个位置是队头）

队空：Q.rear == Q.front


队列元素个数：(rear+MaxSize-front)%MaxSize

方案二：
#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];
    int front,rear;
    int size;
}SqQueue;

插入成功size++

删除成功size--

队满：size==MaxSize
队空：size==0

方案三：
#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];
    int tag;
}SqQueue;

每次删除成功令tag=0；
每次插入成功令tag=1；

队空：front==rear&&tag==0
队满：front==rear&&tag==1

链式实现

初始化（带头结点）

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct{
    LinkNode *front,*rear;
}LinkQueue;

void InitQueue(LinkQueue &Q){
    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}

void testLinkQueue(){
    LinkQueue Q;
    InitQueue(Q);
}

bool IsEmpty(LinkQueue Q){
    if(Q.front==Q.rear)
    return true;
    else
    return false;
}

入队

//带头结点
void EnQueue(LinkQueue &Q,ElemType x){
    LinkNoder *s=(LinkNode *)malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    Q.rear->next=s;
    Q.rear=s;
}

//不带头结点
void EnQueue(LinkQueue &Q,ElemType x){
    LinkNoder *s=(LinkNode *)malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    if(Q.front == NULL){
        Q.front = s;
        Q.rear = s;
    }else{
        Q.rear->next=s;
        Q.rear=s;   
    }
}

出队

//带头结点
bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.front==Q.rear)
    return false;
    LinkNode *p=Q.front->next;
    x=p->data;
    Q.front->next=p->next;
    if(Q.rear==p)
    Q.rear=Q.front;
    free(p);
    return true;
}
//不带头结点
bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.front==NULL)
    return false;
    LinkNode *p=Q.front;
    x=p->data;
    Q.front=p->next;
    if(Q.rear==p){
        Q.front = NULL;
        Q.rear=NULL;
    }
    free(p);
    return true;
}

双端队列

只允许从两端插入、两端删除的线性表

队列应用–树的层次遍历

树的层次遍历
图的广度优先遍历

定义

由零个或多个字符组成的优先序列。

特殊的线性表

串的存储结构

串的顺序存储

#define MAXLEN 255 {
    char ch[MAXLEN];//每个分量存储一个字符
    int length;  //串的实际长度
}SString;

typedef struct{
    char *ch;
    int length;
}HString;

HString S;
S.ch = (char *) malloc(MAXLEN * sizeof(char));
S.length = 0;

串的链式存储

typedef struct StringNode{
    char ch[4];
    struct StringNode * next;
}StringNode, * String;

模式匹配

朴素模式匹配算法

int Index(SString S,SString T){
    int i = 1.j = 1;
    while(i<=S.length && j<=T.length) {
        if(S.ch[i]==T.ch[j]){
            ++i;++j;
        }else{
            i=i-j+2;
            j=1;
        }
    }
    if(j<T.length)
    return i-T.length;
    else
    return 0;
}

KMP算法

//KMP算法
int Index_KMP(SString S,SString T) {
    int i = 1,j = 1;
    int next[T.length+1];
    get_next(T,next);
    while(i<=S.length&&j<=T.length) {
        if(j==0||S.ch[i]==T.ch[j]){
            ++i;
            ++j;  //继续比较后继字符
        }else
        j=next[j]; //模式串向右移动
    }
    if(j>T.length)
    return i-T.length; //匹配成功
    else
    return 0;
}

//求模式串的next数组
void get_next(SString T,int next[]){
    int i = 1,j = 0;
    next[1] = 0;
    while(i<T.length){
        if(j==0||T.ch[i]==T.ch[j]){
            ++i;++j;
            //若pi=pj，则next[j+1]=next[j]+1;
            next[i]=j;
        }
        else
        //否则令j=next[j],循环继续
        j=next[j];
    }
}

KMP算法优化

nextval数组的求法：
先算出next数组
先令nextval[1]=0
for(int j=2;j<=T.length;j++){
    if(T.ch[next[j]]==T.ch[j])
        nextval[j]=nextval[next[j]];
    else
        nextval[j]=next[j];
}

当字串和模式串不匹配时j=nextval[j];

什么是哈希表

将一个字符串转化为数组长度范围内的下标值的过程就称作为哈希化

而实现哈希化的代码一般会封装在一个函数里，这个函数就叫做哈希函数

秦九韶算法（霍纳算法）

能在很大程度上保证每个元素的下标值不重复

哈希表的优缺点

优点

无论数据有多少，处理起来都特别快
能够快速地进行插入修改元素、删除元素、查找元素等操作
代码简单

缺点

哈希表中的数据是没有顺序的
数据不允许重复

冲突

哈希化以后有几个元素的下标值相同，这就叫做冲突

拉链法

把下标值相同的元素存入到一个单独的数组中，然后将该数组存放在他们原本所在数组的下标位置，再对这个位置的数组进行遍历即可。

开放地址法

当元素下标值发生冲突时，寻找空白的位置插入数据。

寻找空白位置三大方法：

线性探测
二次探测
再哈希法

线性探测

顾名思义，线性探测的意思就是，当某两个元素发生冲突时，将当前索引+1，查看该位置是否为空，是的话就插入数据，否则就继续将索引+1，以此类推……直到插入数据位置。

二次探测

在线性探测的基础上，将每次探测的步长改为了当前下标值 index + 1² 、index + 2² 、 index + 3² …… 直到找到空白位置插入元素为止。

再哈希法

再将我们传入的值进行一次 哈希化，获得一个新的探测步数 step，然后按照这个步数进行探测，找到第一个空着的位置插入数据。这在很大的程度上解决了聚集的问题。

这个哈希化的处理过程一定要跟第一次哈希化的处理过程不一样，这样才能确认一个合适的搜索步长，提高查找效率。

公认的比较好的哈希函数

step = constant - (key % constant)

++constant++是一个自己定的质数常量且小于数组的容量

++key++就是第一次哈希化得到的值

哈希表的扩容和减容

填充因子表示哈希表中的数据个数与哈希表长度的比值。其决定哈希表的存取数据所需的时间大小。

用代码实现哈希表

前提

采用链地址法解决冲突问题
涉及到常量的地方，都选用质数。因为在数论上，使用质数可以尽可能地使数据在哈希表中均匀分布。

创建一个构造函数

创建一个大地构造函数，用于存放哈希表地一些属性和方法

function HashTable() {
    //属性
    
    //用于存储数据
    this.storage = [];
    
    //统计哈希表内数据个数
    this.count = 0;
    
    //设定哈希表初始长度
    this.length = 7;
}

封装哈希函数

霍纳算法讲解了哈希化的过程，因此我们在封装哈希函数时，就也通过霍纳算法的最终化简结构来实现

function HashTable() {
	// 属性
	
	// 用于存储数据
    this.storage = []
    
    // 统计哈希表内数据个数
    this.count = 0
    
    // 设定哈希表初始长度
    this.length = 7

	//封装哈希函数
    HashTable.prototype.hashFunc = function (str, size) {
        let hashCode = 0

        //取一个很大的数
        for (let i = 0; i < str.length; i ++) {
            hashCode = 37 * hashCode + str.charCodeAt(i)
        }
        
        //取余
        return hashCode % size
    }
}

数据结构——表之特殊的线性表

目录

栈

顺序栈

初始化

共享栈

链栈

栈的应用

括号匹配

栈在递归中的应用

队列

顺序实现

链式实现

初始化（带头结点）

入队

出队

双端队列

队列应用–树的层次遍历

定义

串的存储结构

串的顺序存储

串的链式存储

模式匹配

朴素模式匹配算法

KMP算法

KMP算法优化

什么是哈希表

秦九韶算法（霍纳算法）

哈希表的优缺点

优点

缺点

冲突

拉链法

开放地址法

线性探测

二次探测

再哈希法

哈希表的扩容和减容

用代码实现哈希表

创建一个构造函数

封装哈希函数

SQL SERVER函数之深入表值函数的处理分析

C#数据结构之循环链表的实例代码

mysql学习笔记之表的基本操作

数据结构简明备忘录 线性表

python数据结构之图的实现方法

oracle分区表之hash分区表的使用及扩展

Python数据结构之顺序表的实现代码示例

线性表之单向链表(动图解析)

SQL优化之针对count、表的连接顺序、条件顺序、in及exist的优化

ORACLE 修改表结构 之ALTER CONSTAINTS的使用

数据结构简明备忘录线性表

ORACLE 修改表结构之ALTER CONSTAINTS的使用