线性表定义及实现

线性表是最常用的数据结构，抽象上讲表是存储具有先后顺序元素数据的结构，实现上分为顺序表和链式表。
顺序表一般采用C语言中数组实现，数组中存储数据，依靠数据索引确定先后顺序信息，物理上存储连续。根据C中数组的定义，移动，动态申请空间，复制等操作，可以想象顺序表在处理动态变化线性表上的缺点。
链式表一般采用C语言中结构体struct实现，每个结构体节点除了存储数据，还存储元素先后顺序信息，物理上存储不连续；根据是否存储前置元素可分为单链表双链表等。插入，删除，移动等动态操作较为方便。

编程实例

问题及解决思路

projecteuler的Problem10求2000000以内所有素数的和，首先要找到2000000所有素数。判断一个是是否素数，如果采用比之小的数去除，则除法运行次数太多。所以建立一个素数链表，用该链表里的素数去除，判断是否素数；一旦是素数，插入或追加到该链表中，为判断后续数字做嫁衣。
详细介绍：https://segmentfault.com/a/11...

代码实现

结构定义

struct intNode;typedef struct intNode sIntNode;typedef sIntNode *pIntNode;struct intNode{    long long int data;    pIntNode next;    pIntNode prv;};

操作方法

//初始化pIntNode elrInitListInt(long long int data){    pIntNode tmp = NULL;    tmp = (pIntNode)malloc(sizeof(sIntNode));    tmp->data = data;    tmp->prv = tmp->next = tmp;        return tmp;}//释放void elrPushListInt(pIntNode pList, long long int data){    pIntNode tmp = NULL;        tmp = (pIntNode)malloc(sizeof(sIntNode));    tmp->data = data;    tmp->next = pList;    tmp->prv = pList->prv;    pList->prv->next = tmp;    pList->prv = tmp;}//追加元素void elrFreeListInt(pIntNode pList){    pIntNode tmp;    while (pList->prv != pList){        tmp = pList->prv;        pList->prv = tmp->prv;        tmp->prv->next = pList;        free(tmp);    }    free(pList);    pList = NULL;}

素数全局变量初始化方法

pIntNode globalPrime;int globalPrimeCount;long long int globalPrimeNum;void initGlobalPrime(){    globalPrime = elrInitListInt(2);    elrPushListInt(globalPrime, 3);    elrPushListInt(globalPrime, 5);    globalPrimeNum = 0;    globalPrimeCount = 3;}void freeGlobalPrime(){    elrFreeListInt(globalPrime);    globalPrimeNum = 0;    globalPrimeCount = 0;    }

判断是否素数

//优化：
//1.用链表的素数去除，减少除法运行次数,本质上应该就是Eratosthenes埃拉托斯特尼筛选法
//2.采用6n+1,6n+5才可能是素数，减少运行次数

int isPrime(const long int num){    pIntNode tmpPrimeNode;    long int tmpNum;        if (num <= globalPrimeNum * 6){        tmpPrimeNode = globalPrime;        do{            if (num < tmpPrimeNode->data) break;            if (tmpPrimeNode->data == num) return 1;            tmpPrimeNode = tmpPrimeNode->next;        }while(tmpPrimeNode != globalPrime);        return 0;    }    else{        for (tmpNum = globalPrimeNum + 1; tmpNum * 6 <= num + 6; tmpNum += 1){            globalPrimeNum = tmpNum;            long int test;            int isDiv;            test = tmpNum * 6 + 1;            isDiv = 1;            tmpPrimeNode = globalPrime;            do{                if ((tmpPrimeNode->data * tmpPrimeNode->data) > test) break;                if (! (test % tmpPrimeNode->data)){                    isDiv = 0;                    break;                }                tmpPrimeNode = tmpPrimeNode->next;            }while (tmpPrimeNode != globalPrime);            if (isDiv){                elrPushListInt(globalPrime, test);                globalPrimeCount++;            }            test = tmpNum * 6 + 5;            isDiv = 1;            tmpPrimeNode = globalPrime;            do{                if ((tmpPrimeNode->data * tmpPrimeNode->data) > test) break;                if (! (test % tmpPrimeNode->data)){                    isDiv = 0;                    break;                }                tmpPrimeNode = tmpPrimeNode->next;            }while (tmpPrimeNode != globalPrime);            if (isDiv){                elrPushListInt(globalPrime, test);                globalPrimeCount++;            }        }        return isPrime(num);        // if ((num == globalPrime->prv->data) || (num == globalPrime->prv->prv->data))         //     return 1;        // else        //     return 0;    }}

找第n个素数

long long int findPrimeSumByNum(const long int num){    long int iSum= 0;    pIntNode tmpPrimeNode;    if (num > globalPrimeNum){        isPrime(num);    }        tmpPrimeNode = globalPrime;    do{        iSum += tmpPrimeNode->data;        tmpPrimeNode = tmpPrimeNode->next;    }while ((globalPrime != tmpPrimeNode) && (num >= tmpPrimeNode->data));    return iSum;}