1. Обзор

Язык C позволяет пользователям задавать структуру данных, состоящую из данных разных типов, объединённых в одно целое для обращения к ним. Данные, объединённые в это целое, взаимосвязаны. Такая структура данных называется структурой; она эквивалентна записи в других языках высокого уровня.

Общий вид объявления типа структуры следующий:

struct 结构体名
{成员列表};

Имя структуры используется как обозначение типа структуры, также называемое тегом структуры. Внутри фигурных скобок находятся члены структуры, которые вместе образуют структуру. Каждый член должен иметь объявление типа, например:

Type name member name;

Список членов также можно называть списком полей, а первый член также называется полем в структуре. Правила именования членов такие же, как правила именования переменных.

struct student
{
    int num;
    char name[20];
    char sex;
    int age;
    float score;
    char addr[30];
};

2. Способы определения переменных типа структуры

Ранее был указан лишь тип структуры, который подобен модели, но не содержит конкретных данных, и система не выделяет для него реальные единицы памяти. Чтобы использовать в программе данные типа структуры, следует определить переменные типа структуры и сохранить в них конкретные данные. Для определения переменных типа структуры можно использовать следующие три способа.

(1) Сначала объявить тип структуры, затем определить имена переменных

Как указано выше, уже определён тип структуры struct student, и его можно использовать для определения переменных. Например:

struct student{  //结构体类型名
    ...
    ...
    ...
}student1, student2 //结构体变量名

student1 и student2 определены как переменные типа struct student.

После определения переменных структуры система выделяет для них единицы памяти. Например, student1 и student2 занимают по 59 байт в памяти.

Обратите внимание, что разница между определением переменной как стандартного типа (базового типа данных) и как структурного типа состоит в том, что в последнем случае требуется не только указать, что переменная имеет структурный тип, но и указать конкретный структурный тип (например, тип struct student), поскольку можно определить много конкретных структурных типов. При определении переменной как целого числа достаточно указать её как int.

(2) Определение переменных при объявлении типа

Например:

struct student
{
    int num;
    char name[20];
    char sex;
    int age;
    float score;
    char addr[30];
}student1, student2;

Его эффект такой же, как у первого способа, то есть определяются две переменные student1 и student2 типа struct student. Общая форма этого определения такова:

struct 结构体名
{
    成员表列
}变量名表列;

(3) Непосредственное определение переменных структурного типа

Его общая форма такова:

struct
{
    成员表列
}变量名表列;

То есть имя структуры не указывается.

Относительно структурных типов следует пояснить несколько моментов:

  • a. Тип и переменная — разные понятия, и их не следует путать. Присваивать значения, обращаться к чему-либо или выполнять операции можно только с переменными, но не с типом. Во время компиляции для типов память не выделяется; память выделяется только для переменных.
  • b. Члены (то есть поля) структуры можно использовать независимо, и их роль и статус эквивалентны обычным переменным.

  • c. Член также может быть переменной структурного типа. Например:

    struct date // 声明一个结构体类型
{
    int month;
    int day;
    int year;
}

struct student
{
    int num;
    char name[20];
    char sex;
    int age;
    struct date birthday;
    char addr[30];
}student1, student2;

    Сначала объявите тип struct date, который представляет «дату» и включает три члена: month, day, year. Затем при объявлении типа struct student укажите член birthday как тип struct date.

  • d. Имена членов могут совпадать с именами переменных в программе, но они не представляют один и тот же объект.

3. Обращение к структурным переменным

(1) Структурную переменную нельзя вводить или выводить целиком.

Вводить или выводить можно только каждый элемент структурной переменной по отдельности. Способ обращения к элементу структурной переменной таков:

Struct variable name.member name

Например, student1.num обозначает элемент num в переменной student1, то есть элемент num переменной student1. Можно присвоить значение элементу переменной. Например: student1.num = 10010;

.Точка — это оператор доступа к элементу (компоненту). Он имеет наивысший приоритет среди всех операторов, поэтому student1.num можно рассматривать как единое целое. Результат приведенного выше оператора присваивания состоит в присваивании целого числа 10010 элементу num переменной student1.

(2) Если элемент сам имеет структурный тип, для последовательного перехода к элементу самого нижнего уровня нужно несколько операторов доступа к элементам. Только элементу самого нижнего уровня можно присваивать значение, к нему можно обращаться или выполнять над ним операции.

Например: к элементам структурной переменной student1 можно обращаться так:

student1.num
student1.birthday.month

Заметьте, что student1.birthday нельзя использовать для доступа к элементу birthday в переменной student1, потому что сам birthday является структурной переменной.

（(3) Над элементами структурной переменной можно выполнять различные операции, как над обычными переменными (допустимые операции определяются их типом).

student2.score = student1.score;
sum = student1.score + student2.score;
student1.age ++;
++ student1.age;

Поскольку.Оператор . имеет наивысший приоритет, поэтому student1.age++ выполняет операцию инкремента для student1.age, а не сначала выполняет инкремент для age.

(4) Можно брать адрес элемента структурной переменной. Можно также брать адрес структурной переменной. Например:

scanf("%d", &student1.num);// 输入 student1.num 的值
printf("%o", &student1);// 输出 student1 的首地址

Но нельзя использовать следующий оператор для чтения всей структурной переменной, например:

scanf("%d,%s,%c,%d,%f,%s", &student1);

Адрес переменной структуры в основном используется как параметр функции для передачи адреса структуры.

4. Инициализация переменных структуры

Как и переменные других типов, переменные структур могут получать начальные значения во время определения.

Пример

#include <stdio.h> struct student { long int num; char name[20]; char sex; char addr[30]; }a = {89031, "Li Lin", 'M', "123 Beijing Road"}; void main() { printf("NO. : %ld\nname: %s\nsex: %c\naddress: %s\n", a.num, a.name, a.sex, a.addr); }

5. Массивы структур

Переменная структуры может хранить набор данных (например, номер студента, имя, оценки и т. д.). Если в вычислениях нужно обработать данные 10 студентов, очевидно, следует использовать массив, то есть массив структур. Отличие массива структур от числовых массивов, рассмотренных ранее, состоит в том, что каждый элемент массива является данными структурного типа, и каждый из них включает различные элементы-члены (компоненты).

5.1 Определение массивов структур

Аналогично определению переменных структуры, нужно лишь указать, что это массив.

struct student
{
    int num;
    char name[20];
    char sex;
    int age;
    float score;
    char addr[30];
};
struct student stu[3];

Выше определён массив stu, элементы которого имеют тип struct student, и массив содержит 3 элемента. Можно также непосредственно определить массив структур. Например:

struct student
{
    int num;
    ....

}stu[3];

или 

struct

{
    int num;
    　...
}stu[3];

5.2 Инициализация массивов структур

Как и массивы других типов, массивы структур можно инициализировать, например:

struct student
{
    int mum;
    char name[20];
    char sex;
    int age;
    float score;
    char addr[30];
}stu[3] = {{10101,"Li Lin", 'M', 18, 87.5, "103 Beijing Road"},
            {10101,"Li Lin", 'M', 18, 87.5, "103 Beijing Road"},
            {10101,"Li Lin", 'M', 18, 87.5, "103 Beijing Road"}};

При определении массива stu количество элементов можно опустить, то есть записать в следующей форме:

stu[] = {{...},{...},{...}};

Во время компиляции система определяет количество элементов массива по числу структурных констант, заданных в качестве начальных значений.

Конечно, для инициализации массива можно также использовать следующую форму:

struct student
{
    int num;
    ...
};
struct student stu[] = {{...},{...},{...}};

То есть сначала объявить тип структуры, затем определить массив как этот тип структуры и инициализировать его при определении массива.

Из вышесказанного видно, что общая форма инициализации массива структур состоит в том, чтобы добавить после определения массива:

5.3 Пример применения массивов структур

Следующий пример иллюстрирует определение и обращение к массивам структур.

Пример

#include <stdio.h> #include <string.h> #include <stdlib.h> struct person { char name[20]; int count; }leader[3] = {{"Li", 0}, 　{"Zhang", 0}, 　{"Fun", 0}}; void main() { int i, j; char leader_name[20]; for(i = 1; i<= 10;i++) { scanf("%s", leader_name); for(j=0;j<3;j++) if(strcmp(leader_name, leader[j].name) == 0) leader[j].count ++; } printf("\n"); for(i=0;i<3;i++) printf("%5s: %d\n", leader[i].name, leader[i].count); system("pause"); }

Результат выполнения выглядит следующим образом:

LI
Li
Fun
Zhang
Zhang
Fun
Li
Fun
Zhang
Li

   Li: 3
Zhang: 3
  Fun: 3

6. Указатели на данные структурного типа

Указатель на структурную переменную — это начальный адрес сегмента памяти, занимаемого этой переменной. Переменную-указатель можно настроить так, чтобы она указывала на структурную переменную; в этом случае значением переменной-указателя является начальный адрес структурной переменной. Переменную-указатель также можно использовать для указания на элемент в массиве структур.

6.1 Указатель на структурную переменную

Применение указателя на структурную переменную:

Пример

#include <string.h> #include <stdio.h> #include <stdlib.b> struct student { long num; char name[20]; char sex; float score; }; void main() { struct student stu_1; struct student *p; p = &stu_1; stu_1.num = 89101; strcpy(stu_1.name, "Ли Линь"); stu_1.sex = 'M'; stu_1.score = 89.5; printf("№ :%ld\nимя: %s\nпол:%c\nоценка:%f\n", stu_1.num, stu_1.name, stu_1.sex, stu_1.score); printf("№ :%ld\nимя: %s\nпол:%c\nоценка:%f\n", (*p).num, (*p).name, (*p).sex, (*p).score); system("pause"); }

.num или stu

.name в качестве фактического аргумента функции для передачи значения фактического аргумента формальному параметру. Использование такое же, как при использовании обычной переменной в качестве фактического аргумента, и относится к методу передачи по значению. Следует отметить, что типы фактического и формального параметров должны быть согласованы.

NO. :89101
name: Li Lin
sex:M
score:89.500000
NO. :89101
name: Li Lin
sex:M
score:89.500000

Видно, что вывод двух операторов printf одинаков.

В языке C для удобства и наглядности (*p).num можно заменить на p->num. Он представляет член num в переменной структуры *p (т.е. в переменной структуры, на которую указывает p). Аналогично, (*p).name эквивалентно p->name.

То есть следующие три формы эквивалентны:

  • a. переменная структуры.имя члена
  • b. (*p).имя члена
  • c. p-> имя члена

Элементы вывода последней функции printf выше можно переписать следующим образом:

printf("NO. :%ld\nname: %s\nsex:%c\nscore:%f\n",p->num, p->name, p->sex, p->score);

где->называется оператором стрелки.

Проанализируйте следующие операторы:

  • p -> n получает значение поля n в структурной переменной, на которую указывает p.
  • p -> n ++ получает значение поля n в структурной переменной, на которую указывает p, и после использования значения увеличивает его на 1.
  • ++p -> n получает значение поля n в структурной переменной, на которую указывает p, и увеличивает его на 1 (сначала инкремент).

6.2 Указатель на массив структур

Как было представлено ранее, указатели и переменные-указатели могут использоваться для указания на массивы или элементы массивов. Аналогично, переменные-указатели также могут использоваться для указания на массивы структур и их элементы.

Применение указателя на массив структур.

Пример

#include <stdio.h> #inlcude <stdlib.h> struct student { int num; char name[20]; char sex; int age; }; struct student stu[3] = {{10101, "Li Lin", 'M', 18}, 　{10102, "Чжан Фунь", 'M', 19}, 　{10103, "Ван Минь", 'F', 20}}; int main() { struct student *p; printf("№ имя пол возраст\n"); for(p=stu; p<stu+3;p++) printf("%5d %-20s %2c %4d\n", p->num, p->name, p->sex, p->age); system("pause"); }

Результат выполнения выглядит следующим образом:

No.    name        sex        age
10101 Li Lin                M       18
10102 Zhang Fun        M       19
10103 Wang Min          F        20

Обратите внимание на следующие два момента:

（

1) Если начальное значение p равно stu, т. е. оно указывает на первый элемент, то после p + 1 оно указывает на начальный адрес следующего элемента. Например:

(++p) -> num сначала увеличивает p на 1, затем получает значение члена num в элементе, на который он указывает (т. е. 10102).

(p++) ->num сначала получает значение p->num (т. е. 10101), затем увеличивает p на 1, указывая на stu

Обратите внимание на разницу между двумя вышеприведенными.

(2) В программе указатель p определён как переменная, указывающая на данные типа struct student. Он может указывать только на данные типа struct student (значение p — начальный адрес элемента массива stu) и не может указывать на член внутри элемента массива stu (т. е. адрес p не может быть адресом члена). Например, следующее неверно:

p = &stu[1].name

При компиляции возникнет ошибка. Никогда не думайте, что, поскольку p хранит адрес, ему можно присвоить любой адрес. Если типы адресов различаются, можно использовать принудительное преобразование типа. Например:

p = (struct student *)&stu[1].name;

В этот момент начальный адрес члена name элемента stu

6.3 Использование структурных переменных и указателей на структуры в качестве параметров функций

Существуют три способа передачи значения структурной переменной в другую функцию:

  • (1) Использовать член структурной переменной в качестве аргумента. Например, использовать stu
  • (2) Использовать структурную переменную в качестве параметра. В старых версиях системы C не разрешалось использовать структурную переменную как фактический аргумент; ANSI C снял это ограничение. Однако при использовании структурной переменной в качестве фактического аргумента применяется передача по значению, и все ячейки памяти, занимаемые структурной переменной, последовательно передаются формальному параметру. Формальный параметр также должен быть структурной переменной того же типа. Во время вызова функции формальный параметр также занимает ячейки памяти. Этот способ передачи требует больших накладных расходов как по памяти, так и по времени. Если структура очень большая, накладные расходы значительны. Кроме того, поскольку используется передача по значению, если значение формального параметра (также структурной переменной) изменяется во время выполнения вызываемой функции, это значение не может быть возвращено в вызывающую функцию, что часто создаёт неудобства. Поэтому этот способ обычно используется реже.
  • (3) Использовать указатель на структурную переменную (или массив) в качестве фактического аргумента и передать адрес структурной переменной (или массива) формальному параметру.

Использование структурной переменной в качестве параметра функции.

Пример

#include <stdio.h> #define FORMAT "%d\n%s\n%f\n%f\n%f\n" struct student { int num; char name[20]; float score[3]; }; void print(struct student stu) { printf(FORMAT, stu.num, stu.score[0], stu.score[1], stu.score[2]); printf("\n"); } void main() { struct student stu; stu.num = 12345; strcpy(stu.name, "Li Li"); stu.score[0] = 67.5; stu.score[1] = 89; stu.score[2] = 78.6; printf(stu); }

Измените вышеприведённое, чтобы использовать указатель на переменную структуры в качестве фактического аргумента.

Пример

#include <stdio.h> #define FORMAT "%d\n%s\n%f\n%f\n%f\n" struct student { int num; char name[20]; float score[3]; }stu = {12345, "Li Li", 67.5, 89, 78.6}; void print(struct student *p) { printf(FORMAT, p->num, p->name, p->score[0], p->оценка[1], p->score[2]); printf("\n"); } void main() { print(&stu); }

7. Работа со связными списками с помощью указателей

7.1 Обзор связного списка

Связный список — это распространённая и важная структура данных. Это структура, которая выполняет динамическое распределение памяти.

Связный список имеет переменную-указатель head, которая хранит адрес, указывающий на элемент. Каждый элемент связного списка называется узлом. Каждый узел должен включать две части: одна — это фактические данные, необходимые пользователю, а другая — адрес следующего узла. Видно, что головной указатель head указывает на первый элемент, первый элемент указывает на второй элемент, ... до последнего элемента. Этот элемент больше не указывает на другие элементы; он называется хвостом списка, а его адресная часть содержит NULL (означающий пустой адрес), и на этом связный список заканчивается.

Видно, что элементы связного списка не обязательно должны храниться в памяти непрерывно. Чтобы найти определённый элемент, нужно сначала найти предыдущий элемент, и только затем можно найти следующий элемент по адресу следующего элемента, который тот предоставляет. Без указателя head невозможно получить доступ ко всему связному списку.

Видно, что такую структуру данных, как связный список, необходимо реализовывать с помощью переменных-указателей. То есть узел должен содержать переменную-указатель для хранения адреса следующего узла.

Ранее мы познакомились с переменными структурного типа. Использовать их в качестве узлов связного списка — наиболее подходящий вариант. Переменная структурного типа содержит несколько членов; эти члены могут иметь числовой тип, символьный тип, тип массива или тип указателя. Мы используем этот член типа указателя для хранения адреса следующего узла. Например, мы можем спроектировать такой структурный тип:

struct student
{
    int num;
    float score;
    struct student *next;
};

Среди них члены num и score используются для хранения полезных данных в узле (данных, необходимых пользователю). next — это член типа указателя, который указывает на данные типа struct student (это тип структуры, содержащий next). Член типа указателя может указывать на данные структур других типов, а также может указывать на данные того типа структуры, в котором он находится. Теперь next является членом типа struct student и указывает на данные типа struct student. Таким образом, можно создать связанный список.

Обратите внимание: само по себе определение типа struct student не выделяет память; ячейки памяти выделяются только при определении переменных.

7.2 Простой связанный список

Следующий пример показывает, как создать и вывести простой связанный список:

Пример

#include <stdio.h> #include <stdlib.h> #define NULL 0 struct student { long num; float score; struct student *next; }; void main() { struct student a, b, c, *head, *p; a.num = 99101; a.score = 89.5; b.num = 99103; b.score = 90; c.num = 99107; c.score = 85;// присвоить значения членам num и score узла head = &a;// присвоить начальный адрес узла a указателю head a.next = &b;// присвоить начальный адрес узла b члену next узла a b.next = &c; c.next = NULL;// член next узла c не хранит адрес никакого другого узла p = head;// сделать так, чтобы указатель p указывал на узел a do { printf("%ld %5.1f\n", p->num, p->score);// вывести данные узла, на который указывает p p = p->next;// сделать так, чтобы p указывал на следующий узел }while(p != NULL);// после вывода узла c значение p равно NULL system("pause"); }

Результат выполнения:

99101  89.5
99103  90.0
99107  85.0

7.3 Функции, необходимые для обработки динамических связных списков

(1) функция malloc

void *malloc(unsigned int size);

Её функция — выделить непрерывный участок памяти длиной size в динамической области памяти. Значением этой функции (то есть возвращаемым значением) является указатель на начальный адрес выделенного участка (базовый тип void). Если функция не может успешно выполниться (например, недостаточно памяти), она возвращает нулевой указатель NULL.

(2) функция calloc

void *calloc(unsigned n, unsigned size);

Её функция — выделить n непрерывных участков длиной size в динамической области памяти. Функция возвращает указатель на начальный адрес выделенного участка; если выделение не удалось, она возвращает NULL. Функцию calloc можно использовать для выделения динамической памяти для одномерного массива, где n — количество элементов массива, а каждый элемент имеет длину size.

(3) функция free

void free(void *p);

Её функция — освободить область памяти, на которую указывает p, чтобы эта часть области памяти могла использоваться другими переменными. p — значение, возвращённое последним вызовом функции calloc или malloc. Функция free не имеет возвращаемого значения. Обратите внимание: функции malloc и calloc, предоставляемые более ранними версиями C, возвращали указатели на символьные данные. Функции malloc и calloc, предоставляемые ANSI C, определены как тип void *.

7.4 Создание динамического связного списка

Так называемое создание динамического связного списка означает построение связного списка с нуля во время выполнения программы, то есть создание узлов по одному, ввод данных для каждого узла и установление связи между предыдущим и следующим.

Пример

#include <stdio.h> #include <stdlib.h> #define NULL 0 #define LEN sizeof(struct student) struct student { long num; float score; struct student *next; }; struct student *create() { struct student *p1, *p2, *head; int num; float score; int n = 0; head = NULL; p1 = p2 = (struct student *)malloc(LEN); printf("пожалуйста, введите num и score.\n"); scanf("%d,%f", &p1->num, &p1->score); while(p1->num != 0) { n ++; if(n == 1) head = p1; else p2->next = p1; p2 = p1; p1 = (struct student *)malloc(sizeof(struct student)); printf("пожалуйста, введите число и оценку.\n"); scanf("%d,%f", &p1->num, &p1->score); } p2->next = NULL; return head; } void printlist(struct student *head) { struct student *p; p = head; if(head != NULL) { do { printf("число=%d оценка=%f\n", p->num, p->score); p = p->next; }while(p != NULL); } } void main() { struct student *head; head = create(); printlist(head); system("pause"); }

Ниже представлены различные операции над связным списком

Вывести связный список:

void printlist(struct student *head)
{
    struct student *p;
    p = head;

    if(head != NULL)
    {
        do 
        {
            printf("num=%d score=%5.2f\n", p->num, p->score);
            p = p->next;
        } while (p != NULL);
    }
    /* while(p -> next != NULL)
    {
        printf("num=%d score=%f\n", p->num, p->score);
        p = p->next;
    }*/
}
Удалить узел:
struct student *delNode(struct student *head, int num)
{
    printf("delNode.\n");
    struct student *p1, *p2;
    if(head == NULL)
    {
        printf("The List is NULL.\n");
    }
    else
    {
        p1 = head;
        while(p1->next != NULL && p1->num != num)
        {
            p2 = p1;
            p1 = p1->next;
        }
        if(p1->num == num)
        {
            if(p1 == head)
                head = p1->next;
            else
                p2->next = p1->next;
        }
        else
            printf("Can not find list num.\n");
    }
    return head;
}

Обновить узел:

struct student *update(struct student *head, int index, int num, float score)
{
    printf("update.\n");
    struct student *p;
    if(head == NULL)
    {
        printf("The List is NULL.\n");
    }
    else
    {
        p = head;
        while(p->next != NULL && p->num != index)
        {
            p = p->next;
        }
        if(p->num == index)
        {
            p->num = num;
            p->score = score;
        }
        else
            printf("Can not find list index.\n");
    }
    return head;
}

Добавить узел:

struct student *add(struct student *head, int index, int num, float score)
{
    printf("add.\n");
    struct student *p1, *p2, *p3;
    if(head == NULL)
    {
        printf("The List is NULL.\n");
    }
    else
    {
        p1 = p2 = head;
        while(p1->next != NULL && p1->num != index)
        {
            p1 = p1->next;
            p2 = p1;
        }
        if(p1->num == index)
        {
            p3 = (struct student *)malloc(LEN);
            p3->num = num;
            p3->score = score;

            if(p2->next == NULL)
            {
                p2->next = p3;
                p3->next = NULL;
            }
            else
            {
                p3->next = p2->next;
                p2->next = p3;   
            }
        }
        else
            printf("Can not find list index.\n");
    }
    return head;
}

Исходная ссылка: http://www.cnblogs.com/qkhhxkj/archive/2011/06/28/2091818.html

Справочная книга: глава о структурных типах в книге г-на Тан Хаоцяна *C Programming*.