算法学习：算法C语言实现 第三章 基本数据结构

前言

第三章介绍了各种各样的数据结构以及基于其上的操作。书中对数据类型给出定义：数据类型是值的集合和在这些值上的操作集。从这个角度来理解，每个C程序在某种意义上都是一种数据类型。

基本数据结构

书中介绍了一些C语言的语法，例如函数、数字类型、结构体等，这里直接略过这些基本内容，直奔后面的稍微高级一点的数据结构与算法。

数组

数组是最基本的数据结构，它是一组相同类型数据的集合，可以通过索引直接访问。埃拉托色尼筛法是一个使用数组的简单例子。

埃拉托色尼筛法（sieve of Eratosthenes）

用一个含有N个数字的数组isPrime的下标代表N个自然数，若自然数i为素数则令isPrime[i]为1，否则设为零。初始状态下，数组中全为1，表示没有任何数被证明为是合数。然后把已经证明是合数（已知素数的倍数）的元素设为0，如果所有更小素数的倍数都已经设为0而isPrime[i]为1，则可知i是素数。

//sieve of Eratosthenes 埃拉托色尼筛法筛选素数
#include <stdio.h>
#define N 10000

int main(void)
{
    int i,j;
    int isPrime[N];
    for(i=0;i<N;i++)
    {
        isPrime[i]=1;
    }
    isPrime[0]=0;
    isPrime[1]=0;//先判断0和1为合数
    for(i=0;i<N;i++)
    {
        if(isPrime[i]==1)
        {
            for(j=i;i*j<N;j++)
            {
                isPrime[i*j]=0;//遇到质数后，判断该质数的倍数为合数
            }
        }
    }
    for(i=0;i<N;i++)
    {
        if(isPrime[i]==1)
        {
            printf("%d ",i);
        }
    }
    printf("\n");
}

这个算法的效率在于快速访问任何位置的能力

数组的动态存储分配

上一个程序在代码里面规定了筛选数字个数N为10000，如果要改变筛选数字的个数，需要修改代码重新编译程序。如果要在运行程序时决定要筛选的数字个数，则可以使用malloc进行动态内存分配。

//根据输入动态分配内存
#include<stdlib.h>
int main(int argc,char *argv[])
{
    long int N=atol(argv[1]);//atol()函数把字符串转换成长整型整数
    int *nums=malloc(N*sizeof(int));
    if(nums==NULL)
    {
        printf("内存不可用\n");
        return 1;
    }

    //这里放算法代码

    free(nums);
    return 0;
}

链表

链表的优势在于，它可以提供高效地重排数据项的能力。这种灵活性的代价是不能快速访问表中任意数据项。

链表处理接口

链表处理接口声明放在list.h中，具体实现放在list.c中，使用时根据需要修改itemType。把链表封装为高级数据结构可以提高开发效率，但是额外的抽象层次有时会掩盖一些只有底层操作被涉及的事实。

typedef struct node * link;
struct node{
    itemType item;
    link next;
}
typedef link Node;
void initNodes(int);
link newNode(itemType);
void freeNode(link);
void insertNext(link,link);
link deleteNext(link);
link getNext(link);
itemType getItem(link);
//函数的具体实现代码懒得写了

使链表末尾节点指向首节点可以形成循环链表，在结构体添加更多链接可以实现双向链表。

约瑟夫问题

假设有N个人觉得选出一个领导人，方法如下：所有人排成一个圆圈，按顺序数数，间隔M个人出局一个人，此时他两边的人重新靠拢形成圆圈。问题是要找出哪个人是最后剩下的人。

//使用循环链表的范例
#include<stdio.h>
#include<stdlib.h>
#include"list.h"
int main(int argc,char *argv[])
{
    int index;
    int N = atol(argv[1]);
    int M = atol(argv[2]);
    Node temp;
    Node member;
    initNodes(N);
    for(index=2,x = newNode(1);index<=N;index++)
    {
        temp=newNode(index);
        insertNext(member,temp);
        member=temp;
    }
    while(member!=Next(member))
    {
        for(index=1;index<M;index++)
            member=Next(member);
            freeNode(deleteNext(member));
    }
    printf("%d\n",Item(member));·
}

这个算法的效率在于快速删除元素的能力。

反转链表

把链表顺序反转，然后返回指向反转后首节点的指针并把反转前的首节点设为NULL。

link reverse(link first)
{
    link temp;
    link node1=first;
    link node2=NULL;
    while(node1!=NULL)
    {
        temp=node1->next;
        node1->next=node2;
        node2=node1;
        node1=temp;
    }
    
    return node2;
}

用自然语言描述算法真是很麻烦，还是画图方便。联创团队web后端笔试就考了反转链表。

链表插入排序

将一个乱序链表变成一个有序链表，在每次循环中从输入链表取出一个节点然后插入到输出链表的适当位置。为了简化代码，在链表的开始保留一个头节点，头结点指向链表的首节点。

//没有具体的情景，懒得写了

字符串

字符串与数组的区别在于，数组长度确定而字符串长度会改变。这里介绍的算法有字符串查找和字符串排序。书上这章介绍了暴力查找法，复杂度O(N^2)，代码是正确的但是不能高效运行，称为性能错误。字符串排序算法使用strcmp()函数解决。

//没啥价值，懒得写了

复合数据结构

使用二维数组表示图。

二维数组分配

用malloc()动态分配内存，在这里定义一个malloc2d()函数更方便使用。

int **malloc2d(int row,int line)
{
    int index;
    int **temp=malloc(row*sizeof(int *));
    for(index=0;index<row;index++)
    {
        temp[index]=malloc(c*sizeof(int));
    }
    return temp;
}
int **nums=malloc2d(M,N);

图的邻接矩阵表示

假设图有V个顶点和E条边，并用范围在0到V-1之间的E对整数集合定义这个图，边由顶点对指定。用i-j定义i和j的连接，此时j-i和i-j的意义相同，这种图称为无向图。使用二维数组（也称为邻接矩阵）可以表示图：如果第i行第j列为非零值，则判断i和j存在一条边。由对称性可知如果第i行第j列非零则第j行第i列非零。
下面这个程序读入定义无向图的一组边，然后生成邻接矩阵表示。如果i和j存在边则将map[i][j]和map[j][i]设为1，如果不存在则设为0，程序假设顶点数V已经确定。

#include<stdio.h>
#include<stdlib.h>
int main(void)
{
    int i;
    int j;
    int map[V][V];
    for(i=0;i<V;i++)
    {
        for(j=0;j<V;j++)
        {
            map[i][j]=0;
        }
    }
    for(i=0;i<V;i++)
    {
        map[i][i]=1;//每个顶点都和自身连接
    }
    while(scanf("%d %d\n",&i,&j)==2)
    {
        map[i][j]=1;
        map[j][i]=1;
    }
}

总结

使用基本的抽象结构用于构建复杂结构并没有止境，在下一步，将要使用链表和数组建立一些作为基本工具的重要数据结构。