Код С++ структуры
Как поменять вместо массива, динамический список ( однонаправленный или двунаправленный ) ? Вот код :
#include
#include
using namespace std;
struct subject {//структура оценок
int math;//математика
int ru;//русский
int inf;//информатика
};
struct learner {//структура ученика
string surname;//фамилия
string name;//имя
string patronymic;//отчество
int klass;//класс
string phone;//номер телефона
subject score;//оценки
float avg_score;
};
void print(learner a) {//функция вывода полной информации ученика
cout << a.surname << " " << a.name << " " << a.patronymic << ":\n";
cout << "\tномер: " << a.phone << endl;
cout << "\tоценки: \n";
cout << "\t\tматематика: " << a.score.math << endl;
cout << "\t\tрусский: " << a.score.ru << endl;
cout << "\t\tинформатика: " << a.score.inf << endl;
cout << "\tсредняя оценка: " << a.avg_score << endl;
}
int main() {
int n;//количество учеников
cout << "Введите количество учеников: ";
cin >> n;
learner *a = new learner[n];//объявление структуры типа learner
cout << "Введите фамилию, имя, отчество, класс, номер, оценки (математика, русский язык, информатика): \n";
for (int i = 0; i < n; i++)
{
cout << i + 1 << ". ";
//чтение информации i-го ученика
cin >> a[i].surname >> a[i].name >> a[i].patronymic >> a[i].klass >> a[i].phone >> a[i].score.math >> a[i].score.ru >> a[i].score.inf;
a[i].avg_score = (a[i].score.math + a[i].score.ru + a[i].score.inf) / 3.0;
//вычисление средней оценки
}
for (int i = 0; i < n; i++)//вывод информации об ученике
print(a[i]);
return 0;
}
Вот решение с емакса, там правда никого надо допилить проталкивание:
SqrtTreeItem op(const SqrtTreeItem &a, const SqrtTreeItem &b);
inline int log2Up(int n) {
int res = 0;
while ((1 << res) < n) {
res++;
}
return res;
}
class SqrtTree {
private:
int n, lg, indexSz;
vector v;
vector clz, layers, onLayer;
vector< vector > pref, suf, between;
inline void buildBlock(int layer, int l, int r) {
pref[layer][l] = v[l];
for (int i = l+1; i < r; i++) {
pref[layer][i] = op(pref[layer][i-1], v[i]);
}
suf[layer][r-1] = v[r-1];
for (int i = r-2; i >= l; i--) {
suf[layer][i] = op(v[i], suf[layer][i+1]);
}
}
inline void buildBetween(int layer, int lBound, int rBound, int betweenOffs) {
int bSzLog = (layers[layer]+1) >> 1;
int bCntLog = layers[layer] >> 1;
int bSz = 1 << bSzLog;
int bCnt = (rBound - lBound + bSz - 1) >> bSzLog;
for (int i = 0; i < bCnt; i++) {
SqrtTreeItem ans;
for (int j = i; j < bCnt; j++) {
SqrtTreeItem add = suf[layer][lBound + (j << bSzLog)];
ans = (i == j) ? add : op(ans, add);
between[layer-1][betweenOffs + lBound + (i << bCntLog) + j] = ans;
}
}
}
inline void buildBetweenZero() {
int bSzLog = (lg+1) >> 1;
for (int i = 0; i < indexSz; i++) {
v[n+i] = suf[0][i << bSzLog];
}
build(1, n, n + indexSz, (1 << lg) - n);
}
inline void updateBetweenZero(int bid) {
int bSzLog = (lg+1) >> 1;
v[n+bid] = suf[0][bid << bSzLog];
update(1, n, n + indexSz, (1 << lg) - n, n+bid);
}
void build(int layer, int lBound, int rBound, int betweenOffs) {
if (layer >= (int)layers.size()) {
return;
}
int bSz = 1 << ((layers[layer]+1) >> 1);
for (int l = lBound; l < rBound; l += bSz) {
int r = min(l + bSz, rBound);
buildBlock(layer, l, r);
build(layer+1, l, r, betweenOffs);
}
if (layer == 0) {
buildBetweenZero();
} else {
buildBetween(layer, lBound, rBound, betweenOffs);
}
}
void update(int layer, int lBound, int rBound, int betweenOffs, int x) {
if (layer >= (int)layers.size()) {
return;
}
int bSzLog = (layers[layer]+1) >> 1;
int bSz = 1 << bSzLog;
int blockIdx = (x - lBound) >> bSzLog;
int l = lBound + (blockIdx << bSzLog);
int r = min(l + bSz, rBound);
buildBlock(layer, l, r);
if (layer == 0) {
updateBetweenZero(blockIdx);
} else {
buildBetween(layer, lBound, rBound, betweenOffs);
}
update(layer+1, l, r, betweenOffs, x);
}
inline SqrtTreeItem query(int l, int r, int betweenOffs, int base) {
if (l == r) {
return v[l];
}
if (l + 1 == r) {
return op(v[l], v[r]);
}
int layer = onLayer[clz[(l - base) ^ (r - base)]];
int bSzLog = (layers[layer]+1) >> 1;
int bCntLog = layers[layer] >> 1;
int lBound = (((l - base) >> layers[layer]) << layers[layer]) + base;
int lBlock = ((l - lBound) >> bSzLog) + 1;
int rBlock = ((r - lBound) >> bSzLog) - 1;
SqrtTreeItem ans = suf[layer][l];
if (lBlock <= rBlock) {
SqrtTreeItem add = (layer == 0) ? (
query(n +
public:
inline SqrtTreeItem query(int l, int r) {
return query(l, r, 0, 0);
}
inline void update(int x, const SqrtTreeItem &item) {
v[x] = item;
update(0, 0, n, 0, x
}
};
Вроде на emaxx есть решение и инфа на эту тему (попа)
