Skip to content

Latest commit

 

History

History
422 lines (316 loc) · 10.3 KB

从零开始学习数据结构_矩阵+串.md

File metadata and controls

422 lines (316 loc) · 10.3 KB

数组 + 矩阵 + 串是常见的数据结构，需要深入掌握与学习。

对于数组：根据指定下标定位相关元素的地址是最为关键的操作，玩数组就是玩下标。

矩阵：M * N 的二维数组，是逻辑线性结构。

一、稀疏矩阵

1.1 基础概念

模型如下：

稀疏矩阵：矩阵中绝大多数元素为零，只有少量非零元素；稀疏因子 = 非零元素数量/矩阵总元素数量。

存储空间利用率：有效元素所申请空间/该矩阵所申请的空间。

定位：当给出下标i、j，且i、j在有效下标取值范围内，需要定位其所对应的元素在压缩存储方式中的位置。

1.2 代码实现

为提升空间利用率（只存储有效元素，避免空间过度浪费），矩阵的存储一般采用三元组法/十字交叉链。

1.2.1 三元组

1.2.1.1 结构体
typedef struct TRIAD{
    int value;
    int row;
    int col;
}TRIAD;

typedef struct TRIPLE{
    TRIAD *element;
    int rowCount;
    int colCount;
    int elementCount;
}TRIPLE;
1.2.1.2 具体代码
#include <stdio.h>
#include <malloc.h>

typedef struct TRIAD{
    int value;
    int row;
    int col;
}TRIAD;

typedef struct TRIPLE{
    TRIAD *element;
    int rowCount;
    int colCount;
    int elementCount;
}TRIPLE;

TRIPLE *inputTriple(void);
void destoryTriple(TRIPLE *);
void showMatrix(TRIPLE triple);
TRIPLE *revangeMatrix(TRIPLE triple);
TRIPLE *initTriple(int rowCount, int colCount, int elementCount);

TRIPLE *initTriple(int rowCount, int colCount, int elementCount){
    TRIPLE *triple;

    triple = (TRIPLE *)malloc(sizeof(TRIPLE));
    triple->rowCount = rowCount;
    triple->colCount = colCount;
    triple->elementCount = elementCount;

    triple->element = (TRIAD *)malloc(sizeof(TRIAD) * elementCount);

    return triple;
}

TRIPLE *revangeMatrix(TRIPLE triple){
    TRIPLE *revTriple;
    int *ec;
    int i;
    int index;

    revTriple = initTriple(triple.rowCount, triple.colCount, triple.elementCount);
    revTriple->rowCount = triple.colCount;
    revTriple->colCount = triple.rowCount;
    revTriple->elementCount = triple.elementCount;

    ec = (int *)calloc(triple.colCount+1, sizeof(int));
    for(i = 0; i < triple.elementCount; i++){
        ec[triple.element[i].col + 1]++;    
    }
    for(i = 1; i < triple.colCount+1; i++){
        ec[i] += ec[i-1];
    }
    for(i = 0; i < triple.elementCount; i++){
        index = ec[triple.element[i].col];
        revTriple->element[index].col = triple.element[i].row; 
        revTriple->element[index].row = triple.element[i].col;
        revTriple->element[index].value = triple.element[i].value;
        ec[index+1]++;
    }

    free(ec);

    return revTriple;
}

void showMatrix(TRIPLE triple){
    int i;
    int j;
    int t = 0;

    for(i = 0; i < triple.rowCount; i++){
        for(j = 0; j < triple.colCount; j++){
            if(i == triple.element[t].row && j == triple.element[t].col)
                printf("%d\t", triple.element[t++].value);
            else 
                printf("0\t");
        }
        printf("\n");
    }

}

void destoryTriple(TRIPLE *triple){
    free(triple->element);
    free(triple);
}

TRIPLE *inputTriple(void){
    TRIPLE *triple;
    int rowCount;
    int colCount;
    int elementCount;
    int i;

    scanf("%d%d%d", &rowCount, &colCount, &elementCount);   

    triple = initTriple(rowCount, colCount, elementCount);

    for(i = 0; i < elementCount; i++){
        int value;
        int row;
        int col;

        scanf("%d%d%d", &row, &col, &value);
        triple->element[i].row = row;
        triple->element[i].col = col;
        triple->element[i].value = value;
    }

    return triple;
}

void main(void){
    TRIPLE *tr;
    TRIPLE *revTr;

    tr = inputTriple();

    revTr = revangeMatrix(*tr);

    showMatrix(*tr);
    showMatrix(*revTr);

    destoryTriple(tr);
    destoryTriple(revTr);
}

1.2.2 十字交叉链

1.2.2.1 数据模型
1.2.2.2 结构体
// 1、稀疏矩阵中的每一个元素的数据类型是 USER_TYPE，用户自定义数据类型
typedef int USER_TYPE;

// 2、十字交叉链中每一个节点的数据类型
typedef struct NODE{
    USER_TYPE data;
    struct NODE *nextCol;
    struct NODE *nextRow;
}NODE;

// 3、无论是行链表、列链表，都应该是多个链表，且用头指针作为起点
typedef struct CROSS_LINK{
    int rowCount;
    int colCount;
    NODE **rowHead;
    NODE **colHead;
}CROSS_LINK;

CROSS_LINK *crossHead =    NULL; //通过头结点指针实现逻辑

具体代码实现较为复杂，暂时还没时间去实现这块具体的逻辑，有兴趣的读者，可以自行实现代码细节。

二、串

2.1 基础概念

串：数组 + 链表的结合是其基本组成结构。

涉及到经典算法：串匹配基础算法 --> KMP 串匹配算法（后续会写这个算法）

使用数组表达串的缺陷：

  1. 长度不能够灵活变化；
  2. 对于串中字符的插入、删除操作存在着大量的移动操作。

随机访问与顺序访问：

  1. 随机访问是无需遍历直接定位的访问方式，通常指下标访问；
  2. 顺序访问是必须重头开始逐一遍历的访问方式，通常指链表节点访问。

串的常见操作有：初始化串、销毁串、指定下标插入、删除、查找、替换、复制、连接、分割等等操作。

2.2 代码实现

2.2.1 数据模型

2.2.2 结构体

#define UNIT_LEN    16

// 1、每一个节点的数据类型
typedef struct STRING_UNIT{
    char string[UNIT_LEN];
    struct STRING_UNIT *next;
    char len;
}STRING_UNIT;

// 2、头指针进行控制
typedef struct STRING{
    STRING_UNIT *stringHead;
    int length;
}STRING;

2.2.3 具体代码（实现 .h 文件）

#ifndef _MEC_STRING_H_
#define _MEC_STRING_H_

#include<stdio.h>
#include<malloc.h>
#include<string.h>

#define UNIT_LEN    16

typedef struct STRING_UNIT{
    char string[UNIT_LEN];
    struct STRING_UNIT *next;
    char len;
}STRING_UNIT;

typedef struct STRING{
    STRING_UNIT *stringHead;
    int length;
}STRING;

boolean initString(STRING **string);
STRING_UNIT *creatStringUnit();
void destoryString(STRING **string);
void removeStringUintAt(STRING_UNIT *curUnit);
void setStringUnitContent(STRING_UNIT *target, const char *source, int len);
void stringCopy(STRING *string, const char *source);
void showString(STRING string);

void showString(STRING string){
    int count = 0;
    int index = 0;
    STRING_UNIT *cur;
    register char ch;

    cur = string.stringHead;
    while(cur && count < string.length){
        ch = cur->string[index];
        if(ch){
            putchar(ch);
            count++;
            if(++index >= UNIT_LEN){
                index = 0;
                cur = cur->next;
            }
        }
    }
}

void stringCopy(STRING *string, const char *source){
    STRING_UNIT *cur;
    int sourceLen;
    int dealedCount = 0;

    sourceLen = strlen(source);
    string->length = sourceLen;
    cur = string->stringHead;

    while(sourceLen > 0){       
        setStringUnitContent(cur, source + dealedCount++ * UNIT_LEN,
            sourceLen > UNIT_LEN ? UNIT_LEN : sourceLen);
        sourceLen -= UNIT_LEN;

        if(sourceLen > 0){
            if(cur->next == NULL){
                cur->next = creatStringUnit();
            }
            cur = cur->next;
        }
    }

    while(cur->next){
        removeStringUintAt(cur);
    }

}

void setStringUnitContent(STRING_UNIT *target, const char *source, int len){
    int index;

    for(index = 0; index < len; index++){
        target->string[index] = source[index];
    }

    while(index < UNIT_LEN){
        target->string[index++] = 0;
    }

    target->len = len;
}

void removeStringUintAt(STRING_UNIT *curUnit){
    STRING_UNIT *p;

    if(curUnit->next){
        p = curUnit->next;
        curUnit->next = p->next;
        free(p);
    }
}

void destoryString(STRING **string){
    STRING_UNIT *head;

    if(!*string){
        return; 
    }

    head = (*string)->stringHead;
    while(head){
        STRING_UNIT *p;

        p = head;
        head = head->next;
        free(p);
    }

    free(*string);
    *string = NULL;
}

STRING_UNIT *creatStringUnit(){
    STRING_UNIT *head;

    head = (STRING_UNIT *)calloc(sizeof(STRING_UNIT), 1);

    head->len = 0;
    head->next = NULL;

    return head;
}

boolean initString(STRING **string){
    if(*string){
        return FALSE;
    }

    *string = (STRING *)malloc(sizeof(STRING));

    (*string)->stringHead = creatStringUnit();
    (*string)->length = 0;

    return TRUE;
}

#endif

三元组、十字交叉链、KMP 算法、串（数组+链表）实现方式是数据结构中最基础部分，这部分需要消化吃透。

三、说明

原创文章链接：从零开始学习数据结构-->矩阵+串