线性表定义及实现
线性表是最常用的数据结构,抽象上讲表是存储具有先后顺序元素数据的结构,实现上分为顺序表和链式表。
顺序表一般采用 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;
}