第3章 数据结构
3.1 结构体
C语言中包括了一些基本数据类型，例如整型、字符型、浮点型、枚举类型、构造数据类型（数组型）、指针类型等。这些数据类型在程序开发中起着重要的作用，但是在开发复杂应用程序的时候只有这些数据类型是不够的，有时需要将不同类型的数据组合成一个有机的整体，以便引用。这就应用到了结构体类型。
实例073 找最高分
本实例是一个提高基础技能的程序
实例位置：光盘\mingrisoft\03\073
实例说明
本实例通过结构体变量记录学生成绩，比较得到记录中的最高成绩，输出该学生的信息。程序运行效果如图3.1所示。
图3.1 显示最高分学生信息
技术要点
本实例应用了结构体数组实现存储学生信息记录，下面介绍结构体数组的相关知识。
一个结构体变量中可以存放一组数据（如一个学生的学号、姓名、年龄等数据）。如果要记录的学生数量很多，定义多个结构体变量显然很麻烦，这时就要应用数组。数据元素为结构体类型的数组称为结构体数组。与一般数组不同的是，结构体数组元素都是一个结构体类型的数据，它们各自还包含成员。
结构体数组的定义与一般结构体变量定义类似，只需说明其为数组即可，例如：
struct student stu[5]；
表示定义了一个名为stu的数组，数组有5个元素，它的每个元素都是一个struct student类型数据。
与定义结构体变量一样，也可以直接定义结构体数组，例如：
struct student
{
int num;
char name[20];
float score;
} stu[5] ;
或者：
struct
{
int num;
char name[20];
float score;
} stu[5] ;
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include "stdio.h"
（3）声明struct student类型：
struct student
{
/*结构体成员*/
int num;
char name[20];
float score;
};
（4）创建main（）函数作为程序的入口程序，在main（）函数中定义struct student类型的数组。查找数组中各学生记录的最高分，并显示在窗体上。实现代码如下：
void main（）
{
int i, m;
float maxscore;
struct student stu[5] =
{
{101, "liming", 89} ,
{102, "zhanghong", 95},
{103, "lili", 89},
{104, "weichen", 85},
{105, "yangfan", 75}
}; /*声明结构体类型数组*/
m = 0;
maxscore=stu[0].score; /*初始化最大成绩*/
for（i = 1; i < 5; i++）
{
if（stu[i].score > maxscore）
{
maxscore=stu[i].score; /*记录最大成绩*/
m=i; /*记录最大成绩下标*/
}
}
printf（"The maxmum score is:%5.1f\n",maxscore）; /*输出最大成绩*/
printf（"The student number is:%d\n",stu[m].num）; /*最大成绩的学号*/
printf（"The student name is:%s\n",stu[m].name）; /*最大成绩的姓名*/
getch（）;
}
举一反三
根据本实例，读者可以：
输出成绩大于90分的学生信息。
查找指定学生的成绩。
实例074 平均成绩
这是一个可以提高基础技能的实例
实例位置：光盘\mingrisoft\03\074
实例说明
利用结构体，编程实现输入一个学生期中和期末成绩求出其平均成绩。运行结果如图3.2所示。
图3.2 平均成绩
技术要点
本实例是一个简单的结构体应用，没有太多难点，定义的结构体成员变量包括期中、期末及平均成绩。从键盘中输入期中、期末成绩存到定义的结构体score中，计算出平均成绩即可。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include<stdio.h>
（3）输入期中、期末成绩存到定义的结构体score中，将两个成绩求和再除以2便可求出平均成绩。
（4）主函数程序代码如下：
main（）
{
struct student_score /*定义结构体，用来存储期中、期末及平均成绩*/
{
int mid;
int end;
int ave;
} score;
printf（"please input score（midterm and end of term）:"）;
scanf（"%d,%d", &score.mid, &score.end）; /*输入期中、期末成绩*/
score.ave =（score.mid + score.end）/ 2; /*计算出平均成绩*/
printf（"average=%d\n", score.ave）; /*将平均成绩输出*/
}
举一反三
根据本实例，读者可以：
输入职工信息，按职工工资由高到低输出。
输入学生期中成绩、期末成绩、平时考核成绩，按30%、50%、20%计算学生的综合成绩。
实例075 比较计数
这是一个可以提高基础技能的实例
实例位置：光盘\mingrisoft\03\075
实例说明
用“比较计数”法对结构数组a按字段num进行升序排序，num的值从键盘中输入。运行结果如图3.3所示。
图3.3 比较计数
技术要点
本实例的算法思想如下：定义结构体用来存储输入的数据及其最后排序，对数组中的元素逐个比较，并用结构体中成员变量con记录该元素大于其他元素的次数，次数越大证明该数据越大。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件，进行宏定义：
#include<stdio.h>
#define N 5
（3）定义结构体order用来存储数据及其排序，并定义结构体数组a，代码如下：
struct order /*定义结构体用来存储数据及它的排序*/
{
int num;
int con;
}a[20]; /*定义结构体数组a*/
（4）主函数程序代码如下：
main（）
{
int i, j;
for（i = 0; i < N; i++）
{
scanf（"%d",&a[i].num）; /*输入要进行排序的5个数字*/
a[i].con = 0;
}
for（i = N -1; i >= 1; i--）
for（j = i -1; j >= 0; j--）
if（a[i].num<a[j].num） /*对数组中的每个元素和其他元素比较*/
a[j].con++; /*记录排序号*/
else
a[i].con++;
printf（"the order is:\n"）for（i = 0; i < N; i++）
printf（"%3d%3d\n",a[i].num,a[i].con）; /*将数据及其排序输出*/
}
举一反三
根据本实例，读者可以编程实现：
5名选手参加选举，找出选票数最多的前3名。
编写结构体存放12个月信息。
实例076 信息查询
本实例可以方便操作、提高效率
实例位置：光盘\mingrisoft\03\076
实例说明
从键盘中输入姓名和电话号码，以#结束，编程实现输入姓名，查询电话号码的功能。运行结果如图3.4所示。
图3.4 信息查询
技术要点
本实例的主要思路如下：首先定义一个结构体用来存储姓名及电话号码，再分别定义两个函数，一个函数的作用是将输出的姓名及电话号码存储到结构体数组中，另一个函数的功能是根据输入的姓名查找电话号码，最后在主函数中分别调用这两个函数就能实现题中要求的功能。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件并进行宏定义：
#include <stdio.h>
#include <string.h>
#define MAX 101
（3）定义结构体aa，用来储存电话号码和姓名：
struct aa /*定义结构体aa存储姓名和电话号码*/
{
char name[15];
char tel[15];
};
（4）自定义函数readin（），用来实现电话号码和姓名存储的过程，代码如下：
int readin（struct aa*a） /*自定义函数readin，用来存储姓名及电话号码*/
{
int i = 0, n = 0;
while（1）
{
scanf（"%s",a[i].name）; /*输入姓名*/
if（!strcmp（a[i].name, "#"））
break;
scanf（"%s",a[i].tel）; /*输入电话号码*/
i++;
n++; /*记录的条数*/
}
return n; /*返回条数*/
}
（5）自定义函数search（），用来查询输入的姓名所对应的电话号码，代码如下：
void search（struct aa*b,char*x,int n） /*自定义函数search，查找姓名所对应的电话号码*/
{
int i;
i = 0;
while（1）
{
if（!strcmp（b[i].name,x）） /*查找与输入姓名相匹配的记录*/
{
printf（"name:%s tel:%s\n",b[i].name,b[i].tel）;/*输出查找到的姓名所对应的电话号码*/
break;
}
else
i++;
n--;
if（n = = 0）
{
printf（"No found!"）; /*若没查找到记录输出提示信息*/
break;
}
}
}
（6）主函数程序代码如下：
main（）
{
struct aa s[MAX]; /*定义结构体数组s*/
int num;
char name[15];
num=readin（s）; /*调用函数readin*/
printf（"input the name:"）;
scanf（"%s",name）; /*输入要查找的姓名*/
search（s,name,num）; /*调用函数search*/
}
举一反三
根据本实例，读者可以：
建一个结构体，结构体中包括名字、年龄及月薪，要求在输出信息时将出生日期输出。
编程实现统计每个文件中单词的个数及行数。
实例077 计算开机时间
这是一个自娱自乐的实例
实例位置：光盘\mingrisoft\03\077
实例说明
编程实现计算开机时间，要求在每次开始计算开机时间时都能接着上次记录的结果接着向下记录。运行结果如图3.5所示。
图3.5 计算开机时间
技术要点
实例中按秒为单位读取系统时间，将读取的时间存到指定磁盘文件中，每次开始计时的时候就从该磁盘文件中读取上次记录的时间接着计时，当秒数达到60，则分钟数加1，如果分钟数达到60，则小时数加1。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
（3）定义结构体time，用来存储时间信息，代码如下：
struct time /*定义结构体time，存储时间信息*/
{
int hour;
int minute;
int second;
} t;
（4）主函数程序代码如下：
main（）
{
FILE*fp; /*定义文件类型指针fp*/
fp=fopen（"Time","r"）; /*以只读方式打开文件Time*/
fread（&t,sizeof（struct time）,1,fp）; /*读取文件中信息*/
while（!kbhit（）） /*当无按键时执行循环体语句*/
{
rewind（fp）; /*将文件指针设置到文件起点*/
sleep（1）; /*程序停止1秒钟*/
fread（&t,sizeof（struct time）,1,fp）; /*读取文件中的内容*/
if（t.second==59） /*如果到60秒*/
{
t.minute=t.minute+1; /*如果到60秒分钟数加1*/
if（t.minute==60） /*判断是否到60分钟*/
{
t.hour=t.hour+1; /*到60分钟小时数加1*/
t.minute=0; /*分数置0*/
}t.second=0; /*秒数置0*/
}
else
t.second=t.second+1; /*秒数加1*/
printf（"%d:%d:%d\n",t.hour,t.minute,t.second）; /*输出累积开机时间*/
fp=fopen（"Time","w"）; /*以可写方式打开Time文件*/
fwrite（&t,sizeof（struct time）,1,fp）; /*定义结构体time，存储时间信息*/
fclose（fp）; /*关闭文件指针*/
}
}
举一反三
根据本实例，读者可以：
在本实例的基础上，增加开机天数记录。
用自定义延迟时间函数来记录开机时间。
3.2 链表
链表是一种常见的数据结构。用于动态进行存储。它避免了使用数组存放数据浪费空间的缺点，可以根据存放的数据大小开辟内存单元。线性表的数据存储在任意的存储单元，这组存储单元可以是连续的，也可以是不连续的，这种存储特性，增加了数据操作的灵活性。因此，链表还是一种重要的数据结构。
实例078 创建单向链表
本实例是一个提高基础技能的程序
实例位置：光盘\mingrisoft\03\078
实例说明
本实例实现创建一个简单的链表，并将这个链表中数据输出到窗体上。程序运行效果如图3.6所示。
图3.6 创建并显示链表
技术要点
链表是动态分配存储空间的链式存储结构，其包括一个“头指针”变量，头指针中存放一个地址，该地址指向一个元素。链表中每一个元素称为“节点”，每个节点都由两部分组成：存储数据元素的数据域和存储直接后继存储位置的指针域。指针域中存储的即是链表的下一个节点的存储位置，是一个指针。多个节点结成一个链表。链表的结构示意图如图3.7所示。
图3.7 链表结构示意图
其中第0个节点称为整个链表的头节点，它一般不存放具体数据，只是存放第一个节点的地址，也称为“头指针”。最后一个节点的指针域设置为空（NULL），作为链表的结束标志，表示它没有后继节点。
说明：从图3.7中可以看出，链表并不一定是连续存放的存储节点，并且只要获得链表的头节点，就可以通过指针变量整条链表。
使用结构体变量作为链表中的节点，因为结构体变量成员可以是数值类型、字符类型、数组类型，也可以是指针类型，这样就可以使用指针类型成员来存放下一个节点的地址，使用其他类型成员存放数据信息。例如，可以一个结构体类型如下：
struct LNode
{
int data;
struct LNode *next;
};
上面的结构体类型中成员data用来存放节点中的数据，相当于图3.7 中的a、b、c。next是指针类型的成员，它指向struct LNode类型数据，就是本结构体类型的数据。 注意：上面只是定义了一个结构体类型，并未实际分配存储空间，只有定义了变量才分配存储空间。
在创建链表时要动态为链表分配空间，C语言的库函数提供了几种函数实现动态开辟存储单元。这里使用malloc（）函数实现动态开辟存储单元，下面进行介绍。
malloc函数原型为：
void *malloc（unsigned int size）;
其作用是在内存的动态存储区中分配一个长度为size的连续空间。函数返回值是一个指向分配域起始地址的指针（类型为void）。如果分配空间失败（如内存空间不足），则返回空指针（NULL）。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include "stdio.h"
#include <malloc.h>
（3）声明struct LNode类型：
struct LNode
{
int data;
struct LNode *next;
};
（4）创建create（）自定义函数，实现创建一个链表，将此函数定义为指针类型，使其返回值为指针值，返回值指向一个struct LNode类型数据，实际上是返回链表的头指针。代码如下：
struct LNode *create（int n）
{
int i;
struct LNode*head, *p1, *p2;
int a;
head = NULL;
printf（"Input the integers:\n"）;
for（i = n; i > 0; --i）
{
p1=（struct LNode*）malloc（sizeof（struct LNode））;/*分配空间*/
scanf（"%d",&a）; /*输入数据*/
p1->data=a; /*数据域赋值*/
if（head==NULL） /*指定头节点*/
{
head = p1;
p2 = p1;
}
else
{
p2->next=p1; /*指定后继指针*/
p2 = p1;
}
}
p2->next = NULL;
return head;
}
（5）创建main（）函数作为程序的入口程序，在main（）函数中调用create（）自定义函数，实现创建一个链表，并将链表中的数据输出。实现代码如下：
void main（）
{
int n;
struct LNode *q;
printf（"Input the count of the nodes you want to creat:"）;
scanf（"%d",&n）; /*输入链表节点个数*/
q = create（n）;
printf（"The result is:\n"）;
while（q）
{
printf（"%d ",q->data）; /*输出链表*/
q = q->next;
} getch（）;
}
举一反三
根据本实例，读者可以：
使用学生信息动态创建一个单链表。
创建固定长度单链表。
实例079 创建双向链表
本实例是一个提高基础技能的程序
实例位置：光盘\mingrisoft\03\079
实例说明
本实例实现创建一个双向链表，并将这个链表中数据输出到窗体上，输入要查找的学生姓名，将查找的姓名从链表中删除，并显示删除后的链表。程序运行效果如图3.8所示。
图3.8 创建双向链表
技术要点
单向链表节点的存储结构只有一个指向直接后继的指针域，所以，从单链表的某个节点出发只能顺指针查找其他节点。使用双向链表可以避免单链表这种单向性的缺点。
顾名思义，双向链表的节点有两个指针域，一个指向其直接后继，另一个指向其直接前驱，在C语言中可描述如下：
typedef struct DulNode
{
char name[20];
struct node*prior; /*直接前驱指针*/
struct node*next; /*直接后继指针*/
}DNode;
其结构如图3.9所示。
图3.9 双向链表示意图
如图3.9（a）所示，双向链表包括3个域，两个指针域一个数据域。如图3.9（b）所示，可以看出双向链表节点间的关系。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
（3）声明struct LNode类型：
typedef struct node
{
char name[20];
struct node*prior, *next;
}stud; /*双链表的结构定义*/
（4）创建create（）自定义函数，实现创建一个双向链表，将此函数定义为指针类型，使其返回值为指针值，返回值指向一个struct node类型数据，实际上是返回链表的头指针。代码如下：
stud *creat（int n）
{
stud*p, *h, *s;
int i;
h=（stud*）malloc（sizeof（stud））; /*申请节点空间*/
h->name[0] = '\0';
h->prior = NULL;
h->next = NULL;
p = h;
for（i = 0; i < n; i++）
{
s =（stud*）malloc（sizeof（stud））;
p->next=s; /*指定后继节点*/
printf（"Input the %d student's name: ", i + 1）;
scanf（"%s", s->name）;
s->prior=p; /*指定前驱节点*/
s->next = NULL;
p = s;
}
p->next = NULL;
return（h）;
}
（5）创建serch（）自定义函数，实现查找要删除的节点，如果找到则返回该节点地址。代码如下：
/*查找*/
stud *search（stud *h, char *x）
{
stud*p; /*指向结构体类型的指针*/
char *y;
p = h->next;
while（p）
{
y = p->name;
if（strcmp（y,x）==0） /*如果是要删除的节点，则返回地址*/
return（p）;
else
p = p->next;
}
printf（"cannot find data!\n"）;
}
（6）创建del（）自定义函数，实现删除链表中指定的节点。代码如下：
/*删除*/
void del（stud *p）
{
p->next->prior=p->prior; /*p的下一个节点的前驱指针指向p的前驱节点*/
p->prior->next=p->next; /*p的前驱节点的后继指针指向p的后继节点*/
free（p）;
}
（7）创建main（）函数作为程序的入口程序，在main（）函数中调用create（）自定义函数，实现创建一个链表，并将链表中的数据输出。调用serch（）自定义函数和del（）自定义函数实现查找指定节点并从链表中将该节点删除。实现代码如下：
/*主函数*/
main（）
{
int number;
char sname[20];
stud*head, *sp;
puts（"Please input the size of the list:"）;
scanf（"%d",&number）; /*输入链表节点数*/
head=creat（number）; /*创建链表*/
sp = head->next;
printf（"\nNow the double list is:\n"）;
while（sp） /*输出链表中数据*/
{
printf（"%s ", &*（sp->name））;
sp = sp->next;
}
printf（"\nPlease input the name which you want to find:\n"）;
scanf（"%s", sname）;
sp=search（head,sname）; /*查找指定节点*/
printf（"the name you want to find is:%s\n", *&sp->name）;
del（sp）; /*删除节点*/
sp = head->next;
printf（"\nNow the double list is:\n"）;
while（sp）
{
printf（"%s",&*（sp->name））; /*输出当前链表中数据*/
sp = sp->next;
}
printf（"\n"）;
puts（"\n Press any key to quit..."）;
getch（）;
}
举一反三
根据本实例，读者可以：
使用学生信息动态创建一个双链表。
创建带固定长度双链表。
实例080 创建循环链表
本实例是一个提高基础技能的程序
实例位置：光盘\mingrisoft\03\080
实例说明
本实例实现创建一个循环链表。这里只创建一个简单的循环链表来演示循环链表的创建和输出方法。程序运行效果如图3.10所示。
图3.10 创建循环链表
技术要点
循环链表是另一种形式的链式存储结构。只是链表中最后一个节点的指针域指向头节点，使链表形成一个环。从表中任一节点出发均可找到表中其他节点，如图3.11所示，为单链表的循环链表结构示意图，也可以有双链表的循环链表。
图3.11 循环链表示意图
循环链表与普通链表的操作基本一致，只是在算法中循环遍历链表节点时判断条件不再是p->next是否为空，而是是否等于链表的头指针。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
（3）声明struct student类型：
typedef struct student
{
int num;
struct student *next;
}LNode, *LinkList;
（4）创建create（）自定义函数，实现创建一个循环链表，其返回值为指针值，返回值指向一个struct node类型数据，实际上是返回链表的头指针。代码如下：
LinkList create（void）
{
LinkList head;
LNode*p1, *p2;
char a;
head = NULL;
a = getchar（）;
while（a != '\n'）
{
p1=（LNode*）malloc（sizeof（LNode））;/*分配空间*/
p1->num=a; /*数据域赋值*/
if（head = = NULL）
else
head = p1;
p2->next = p1;
p2 = p1;
a = getchar（）;
}
p2->next=head; /*尾节点指向头节点*/
return head;
}
（5）创建main（）函数作为程序的入口函数，实现调用create（）自定义函数创建一个循环链表，并输出。代码如下：
void main（）
{
LinkList L1, head;
printf（"Please input the linklist:\n"）;
L1=create（）; /*创建循环链表*/
head = L1;
printf（"The resultant linklist is:\n"）;
printf（"%c ", L1->num）;
L1=L1->next; /*指向下一个节点*/
while（L1 != head）
{
/*判断条件为循环到头节点结束*/
printf（"%c ", L1->num）;
L1 = L1->next;
}
getch（）;
}
举一反三
根据本实例，读者可以：
查询元素的前驱和后继。
单循环链表中元素的删除。
实例081 双链表逆置
本实例是一个提高基础技能的程序
实例位置：光盘\mingrisoft\03\081
实例说明
本实例实现创建一个双向链表，将双向链表的节点逆置，即将尾节点放到第一个节点的位置，倒数第二个节点放到第二个节点的位置，依此类推，并将逆置后的双链表输出显示在窗体上。程序运行效果如图3.12所示。
图3.12 双链表逆置
技术要点
在实例088中已经介绍了双链表的结构特点，双链表的逆置即是将双链表数据列中元素逆置。根据双链表的特点，依次将双链表节点的每个后继节点按照头插入法插入到新建链表的首位，即可实现双链表元素逆置。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件，定义宏：
#include <stdio.h>
#define N 10
（3）声明双链表结构：
typedef struct node
{
char name[20];
struct node*prior, *next;
} stud; /*双链表的结构定义*/
（4）创建create（）自定义函数，实现创建一个双链表链表，其返回值为指针值，返回值指向一个struct node类型数据，实际上是返回链表的头指针。代码如下：
/*双链表的创建*/
stud *creat（int n）
{
stud*p, *h, *s; /*声明双链表结构类型的指针*/
int i;
h=（stud*）malloc（sizeof（stud））; /*创建头节点*/
/*初始化头节点*/
h->name[0] = '\0';
h->prior = NULL;
h->next = NULL;
p=h; /*p指向头节点*/
printf（"Input the records:\n "）;
for（i = 0; i < n; i++）
{
s=（stud*）malloc（sizeof（stud））;/*申请节点空间*/
p->next = s;
scanf（"%s",s->name）; /*输入数据*/
s->prior=p; /*指定前驱节点*/
s->next=NULL; /*指定后继节点*/
p = s;
}
p->next = NULL;
return（h）; /*返回头节点*/
}
（5）创建reverse（）自定义函数，实现将给定的双链表逆置，返回一个新的双链表。程序代码如下：
stud *reverse（stud *head）
{
stud*p, *r, *h;
h = head->next;
/*实现逆置*/
if（h && h->next）
{
p = h;
r = p->next;
p->next = NULL;
while（r）
{
p = r;
r = r->next;
p->next = h;
h->prior = p;
h = p;
}
head->next=h; /*指定后继节点*/
h->prior=head; /*指定前驱节点*/
return head; /*返回头节点*/
}
}
（6）创建main（）函数作为程序的入口函数，在函数中调用自定义函数实现创建一个双链表并将双链表逆置。代码如下：
void main（）
{
int n, i;
int x;
stud *q;
printf（"Input the count of the nodes you want to creat:"）;
scanf（"%d", &n）;
q=creat（n）; /*创建双链表*/
q=reverse（q）; /*双链表逆置*/
printf（"The result linklist:\n"）;
while（q） /*输出逆置后的双链表*/
{
printf（"%s ", &*（q->name））;
q = q->next;
}
getch（）;
}
举一反三
根据本实例，读者可以：
删除双链表中节点。
向双链表中插入节点。
实例082 双链表逆序输出
这是一个可以启发思维的实例
实例位置：光盘\mingrisoft\03\082
实例说明
本实例实现创建一个指定节点数的双向链表，并将双链表中的节点数据逆序输出。程序运行效果如图3.13所示。
图3.13 双链表逆序输出
技术要点
双链表节点数据逆序输出的实现算法很简单，因为双向链表有两条指针链，一条可以看成是从头节点出发直到尾节点的指针链，另一条可以看成是从尾节点出发直到指向头节点的指针链。双链表节点数据的逆序输出就是根据双链表的这个特性实现的，从尾节点到头节点使用指针依次遍历该链表的节点，即可实现逆序查找双链表节点，并将节点数据域的数据信息输出。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件，定义宏：
#include <stdio.h>
#define N 10
（3）声明双链表结构：
typedef struct node
{
char name[20];
struct node*prior, *next;
} stud; /*双链表的结构定义*/
（4）创建create（）自定义函数，实现创建一个双链表，其返回值为指针值，返回值指向一个struct node类型数据，实际上是返回链表的头指针。代码如下：
/*双链表的创建*/
stud *creat（int n）
{
stud*p, *h, *s; /*声明双链表结构类型的指针*/
int i;
h=（stud*）malloc（sizeof（stud））; /*创建头节点*/
/*初始化头节点*/
h->name[0] = '\0';
h->prior = NULL;
h->next = NULL;
p=h; /*p指向头节点*/
printf（"Input the records:\n "）;
for（i = 0; i < n; i++）
{
s=（stud*）malloc（sizeof（stud））; /*申请节点空间*/
p->next = s;
scanf（"%s",s->name）; /*输入数据*/
s->prior=p; /*指定前驱节点*/
s->next=NULL; /*指定后继节点*/
p = s;
}
p->next = NULL;
return（h）; /*返回头节点*/
}
（5）创建自定义函数gettp（），实现获取一个指向双链表尾节点的指针。程序代码如下：
stud *gettp（stud *head）
{
stud*p, *r;
while（p->next != NULL）
{
p = p->next;
}
return p; /*返回尾节点指针*/
}
（6）创建main（）函数，作为程序的入口函数。在主函数中调用creat（）自定义函数和gettp（）自定义函数，实现创建并找到双向链表的尾节点。使用双链表节点中的指向直接前驱的指针遍历双链表，并将节点的数据依次输出到窗体上。代码如下：
void main（）
{
int n, i;
int x;
stud *q;
printf（"Input the count of the nodes you want to creat:"）;
scanf（"%d",&n）; /*输入要创建链表的节点数*/
q=creat（n）; /*创建双链表*/
q=gettp（q）; /*找到双链表的尾节点*/
printf（"The result: "）;
while（q）
{
printf（" %s",&*（q->name））; /*逆序输出*/
q=q->prior; /*从尾节点开始向前遍历链表节点*/
}
getch（）;
}
举一反三
根据本实例，读者可以：
获取双链表节点个数。
判断双链表是否为空。
实例083 约瑟夫环
这是一个可以启发思维的实例
实例位置：光盘\mingrisoft\03\083
实例说明
本实例使用循环链表实现约瑟夫环。给定一组编号分别是：4，7，5，9，3，2，6，1，8。初始值由用户输入，这里输入4，如图3.14所示。按照约瑟夫环原理打印输出队列。
程序运行效果如图3.14所示。
图3.14 使用循环链表实现约瑟夫环
技术要点
约瑟夫环算法是：n个人围成一圈，每个人都有一个互不相同的密码，该密码是一个整数值，选择一个人作为起点，然后顺时针从1到k（k为起点人手中的密码值）数数。数到k的人退出圈子，然后从下一个人开始继续从1到j（刚退出圈子的人的密码）数数，数到j的人退出圈子。重复上面的过程。直到剩下最后一个人。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件，声明结构体，声明自定义函数等：
#include "stdio.h"
#define N 9
#define OVERFLOW 0
#define OK 1
int KeyW[N]={4,7,5,9,3,2,6,1,8};
void Joseph（LinkList p,int m, int x）;
（3）声明struct LNode类型：
typedef struct LNode{
int keyword;
struct LNode *next;
}LNode,*LinkList;
（4）创建Joseph（）自定义函数，实现使用循环链表实现约瑟夫环算法，根据给定数获得一个数列。代码如下：
void Joseph（LinkList p,int m,int x）{
LinkList q; /*声明变量*/
int i;
if（x= =0）return;
q=p;
m%=x;
if（m= =0）m=x;
for（i=1;i<=m;i++）{ /*找到下一个节点*/
p=q;
q=p->next;
}
p->next=q->next;
i=q->keyword;
printf（"%d ",q->keyword）;
free（q）;
Joseph（p,i,x-1）; /*递归调用*/
}
（5）创建main（）函数作为程序的入口函数，调用Joseph（）自定义函数实现约瑟夫环算法，并将得到的数列输出。代码如下：
int main（）
{
int i,m;
LinkList Lhead,p,q;
Lhead=（LinkList）malloc（sizeof（LNode））; /*申请节点空间*/
if（!Lhead）return OVERFLOW;
Lhead->keyword=KeyW[0]; /*数据域赋值*/
Lhead->next=NULL;
p=Lhead;
for（i=1;i<9;i++）{ /*创建循环链表*/
if（!（q=（LinkList）malloc（sizeof（LNode））））return OVERFLOW;
q->keyword=KeyW[i];
p->next=q;
p=q;
}
p->next=Lhead;
printf（"Please input the first record m: \n"）;
scanf（"%d",&m）;
printf（"The output alignment is:\n"）;
Joseph（p,m,N）;
getch（）;
return OK;
}
举一反三
根据本实例，读者可以编程实现：
循环链表的合并。
查找循环链表中元素值。
实例084 创建顺序表并插入元素
这是一个可以启发思维的实例
实例位置：光盘\mingrisoft\03\084
实例说明
本实例实现创建一个顺序表，在顺表中插入元素，并输出到窗体上。程序运行效果如图3.15所示。
图3.15 创建顺序表
技术要点
顺序表是用一组地址连续的存储单元依次存储线性表的数据元素。线性表是最常用且最简单的一种数据结构，一个线性表是n个数据元素的有限序列。
假设顺序表的每个元素需要占用L个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则顺序表中第i+1个数据元素的存储位置Loci+1和第i个数据元素的存储位置Loci之间的关系如下：
Loci+1=Loci+L
顺序表的第i个数据元素的存储位置为：
Loci+1=Loc1+（i-1）*L
上面的式子中，Loc1是顺序表的第一个元素的存储位置，通常称为顺序表的起始位置或是基地址。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
#define Listsize 100
（3）声明struct sqlist类型：
struct sqlist
{
int data[Listsize];
int length;
};
（4）创建InsertList（）自定义函数，在顺序表中插入元素，代码如下：
void InsertList（struct sqlist *l, int t, int i）
{
int j;
if（i < 0 || i > l->length）
{
printf（"position error"）;
exit（1）;
}
if（l->length>=Listsize） /*如果超出顺序表范围，则溢出*/
{
printf（"overflow"）;
exit（1）;
}
for（j=l->length-1;j>=i;j--） /*插入元素*/
l->data[j + 1] = l->data[j];
l->data[i] = t;
l->length++;
}
（5）创建main（）函数作为程序的入口函数。代码如下：
void main（）
{
struct sqlist *sq;
int i, n, t;
sq=（struct sqlist*）malloc（sizeof（struct sqlist））;/*分配空间*/
sq->length = 0;
printf（"Please input the size of the list :"）;
scanf（"%d", &n）;
printf（"Please input the elements of the list:\n"）;
for（i = 0; i < n; i++）
{
scanf（"%d", &t）;
InsertList（sq,t,i）; /*插入元素*/
} printf（"Now the list is:\n"）;
for（i = 0; i < sq->length; i++）
{
printf（"%d ", sq->data[i]）;
}
getch（）;
}
举一反三
根据本实例，读者可以：
创建指定长度顺序表。
向顺序表中插入数据。
实例085 向链表中插入节点
这是一个可以启发思维的实例
实例位置：光盘\mingrisoft\03\085
实例说明
本实例实现创建一个指定节点数的链表，并在链表中插入一个新的节点。程序运行效果如图3.16所示。
图3.16 向链表中插入节点
技术要点
在链表中插入节点需要解决两个问题：怎样找到插入的位置，怎样实现插入操作。
这里实现的是在事先指定的位置插入一个指定数据元素的节点。因为链表是链式结构的，要想插入一个节点，就先要断开链表，才能将新节点插入。就像是一群小学生手拉手，要将一个新的小学生加入其中，就需要在要插入的位置先使两名小学生的手脱开，让前面的同学拉新同学的手，新同学拉后面同学的手。这样就完成了插入，形成一个新的队列。
按照上面的思路，如果在第i个位置前插入一个节点，就先要找到插入的位置，使用指针p指向该节点，本实例使用下面的循环语句从头节点移动指针，找到要插入位置的前一个节点。插入前的链表如图3.17（a）所示。程序代码如下：
p = head;
while（p && j < i -1）
{
p = p->next;
++j;
}
将要插入节点（即s指向的节点）指向链表中插入位置的下一个节点。代码如下：
s->next = p->next;
将指针p指向的节点（即插入位置的前一个节点）指向要插入的节点，代码如下：
p->next = s;
插入节点后的链表如图3.17（b）所示。
图3.17 单链表插入节点示意图
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
（3）声明struct student类型：
struct student
{
int num;
struct student *next;
};
（4）创建insertnode（）自定义函数，实现在已知链表中插入一个节点。程序代码如下：
struct student *insertnode（struct student *head, char x, int i）
{
int j = 0;
struct student*p, *s;
p = head;
while（p&&j<i-1） /*找到要插入的位置*/
{
p = p->next;
++j;
}
if（!p || j > i -1）
exit（1）;
s=（struct student*）malloc（sizeof（struct student））;/*申请节点空间*/
s->num=x; /*为数据域赋值*/
s->next = p->next;
p->next = s;
}
（5）创建main（）函数作为程序的入口函数，调用create（）和insertnode（）自定义函数实现创建链表并在链表中插入一个节点。程序代码如下：
void main（）
{
int n, i;
int x;
struct student*q; /*声明节点类型的指针变量*/
printf（"Input the count of the nodes you want to creat:"）;
scanf（"%d", &n）;
q=create（n）; /*创建链表*/
i = 2;
x = 123;
insertnode（q,x,i）; /*插入节点*/
printf（"The result is:\n"）;
while（q） /*输出插入节点后的链表*/
{
printf（"%d ",q->num）;
q = q->next;
}
}
举一反三
根据本实例，读者可以：
由用户输入插入节点位置并将节点插入。
向链表中插入多个节点。
实例086 从链表中删除节点
这是一个可以提高分析能力的实例
实例位置：光盘\mingrisoft\03\086
实例说明
本实例实现创建一个链表，并在链表中删除一个节点，将删除节点后的链表显示在窗体上。程序运行效果如图3.18所示。
图3.18 从链表中删除节点
技术要点
在链表中删除节点就是将节点从链表中分离出来，撤销原来的链接关系，而不是将节点从内存中抹掉。就像是有编号为1、2、3、4、5的5个小学生手拉手，现在要将编号为3的小学生从这个队列中分离出来。只要将编号为3的小学生的手从两边脱开，使编号为1和编号为2的两个小学生拉手，形成一个新的队列。如图3.19（a）所示为原来队列，如图3.19（b）所示为分离一个学生后的队列。
图3.19 从队列中删除元素
从链表中删除一个节点与上面相仿，只是需要改变要删除节点的前一个节点的指针域，使其指向要删除节点的下一个节点即可。其示意图如图3.20所示。
图3.20 从链表中删除节点示意图
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
（3）声明struct student类型：
typedef struct student
{
int num;
struct student *next;
}LNode, *LinkList;
（4）创建create（）自定义函数实现创建链表，代码如下：
struct student *create（int n）
{
int i;
struct student*head, *p1, *p2;
int a;
char b;
head=NULL; /*初始化头节点地址*/
printf（"The record:\n"）;
for（i = n; i > 0; --i）
{
p1=（struct student*）malloc（sizeof（struct student））;/*分配空间*/
scanf（"%d", &a）;
p1->num=a; /*数据域赋值*/
if（head = = NULL）
{
head = p1;
p2 = p1;
}
else
{
p2->next=p1; /*指定后继指针*/
p2 = p1;
}
}
p2->next=NULL; /*后继指针为空，链表结束*/
return head; /*返回头节点*/
}
（5）创建delnode（）自定义函数，实现删除已知链表中的指定节点，并释放删除节点空间。程序代码如下：
struct student *delnode（struct student *head, int i）
{
int j = 0;
struct student*p, *r;
p = head;
while（p&&j<i-1） /*找到要删除的位置*/
{
p = p->next;
++j;
}
if（!p->next || j > i -1）
exit（1）;
r = p->next;
p->next=r->next; /*删除节点*/
free（r）;
}
（6）创建main（）函数作为程序的入口函数，调用create（）自定义函数实现创建链表，调用delnode（）自定义函数实现删除链表中第3个节点。程序代码如下：
void main（）
{
int n, i;
int x;
struct student *q;
printf（"Input the count of the nodes you want to creat:"）;
scanf（"%d",&n）; /*输入要创建的链表节点数*/
q=create（n）; /*创建链表*/
i = 2;
delnode（q,i）; /*删除第3个节点*/
printf（"The third record is deleted!\nThe result is:\n"）;
while（q） /*输出删除节点后的链表*/
{
printf（"%d ",q->num）;
q = q->next;
} getch（）;
}
举一反三
根据本实例，读者可以：
删除指定位置的节点。
使用新元素替换一个节点。
实例087 合并两个链表
这是一个可以提高分析能力的实例
实例位置：光盘\mingrisoft\03\087
实例说明
本实例实现将两个链表合并，合并后的链表为原来两个链表的连接，即将第二个链表直接连接到第一个链表的尾部，合成为一个链表。程序运行效果如图3.21所示。
图3.21 合并两个链表
技术要点
本实例是将两个链表合并，即将两个链表连接起来。主要的思想是先找到第一个链表的尾节点，使其指针域指向下一个链表的头节点。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
（3）声明struct student类型：
typedef struct student
{
int num;
struct student *next;
}LNode, *LinkList;
（4）创建create（）自定义函数，实现创建一个链表，其返回值为指针值，返回值指向一个struct node类型数据，实际上是返回链表的头指针。代码如下：
LinkList create（void）
{
LinkList head;
LNode*p1, *p2;
char a;
head = NULL;
a = getchar（）;
while（a != '\n'）
{
p1=（LNode*）malloc（sizeof（LNode））;/*分配空间*/
p1->num=a; /*数据域赋值*/
if（head = = NULL）
head = p1;
else
p2->next = p1;
p2 = p1;
a = getchar（）;
}
p2->next = NULL;
return head;
}
（5）创建coalition（）自定义函数，实现将创建的两个链表合并，程序代码如下：
LinkList coalition（LinkList L1, LinkList L2）
{
LNode *temp;
if（L1 = = NULL）
return L2;
else
{
if（L2 != NULL）
{
for（temp = L1; temp->next != NULL; temp = temp->next）;
temp->next=L2; /*遍历L1中节点直到尾节点*/
}
}
return L1;
}
（6）创建main（）函数作为程序的入口函数，调用create（）自定义函数实现创建两个链表，调用coalition（）自定义函数实现将两个链表合并，并将合并后的链表输出。程序代码如下：
void main（）
{
LinkList L1, L2, L3;
printf（"Please input two linklist:\n"）;
printf（"The first linklist:\n"）;
L1=create（）; /*创建一个链表*/
printf（"The second linklist:\n"）;
L2=create（）; /*创建第二个链表*/
coalition（L1,L2）; /*连接两个链表*/
printf（"The resultant linklist is:\n"）;
while（L1） /*输出合并后的链表*/
{
printf（"%c", L1->num）;
L1 = L1->next;
}
getch（）;
}
举一反三
根据本实例，读者可以：
按序号查找单链表。
按值查找单链表。
实例088 单链表就地逆置
这是一个可以启发思维的实例
实例位置：光盘\mingrisoft\03\088
实例说明
本实例实现创建一个单链表，并将链表中的节点逆置，将逆置后的链表输出在窗体上。程序运行效果如图3.22所示。
图3.22 单链表逆置
技术要点
本实例实现单链表的逆置，主要算法思想是：将单链表的节点按照从前往后的顺序依次取出，并依次插入到头节点的位置。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
（3）声明struct student类型：
struct student
{
int num;
struct student *next;
};
（4）创建create（）自定义函数，实现创建一个循环链表，其返回值为指针值，返回值指向一个struct node类型数据，实际上是返回链表的头指针。代码如下：
struct student *create（int n）
{
int i;
struct student*head, *p1, *p2;
int a;
head = NULL;
printf（"The record:\n"）;
for（i = n; i > 0; --i）
{
p1=（struct student*）malloc（sizeof（struct student））;/*分配空间*/
scanf（"%d", &a）;
p1->num=a; /*数据域赋值*/
if（head = = NULL）
{
head = p1;
p2 = p1;
}
else
{
p2->next=p1; /*指定后继指针*/
p2 = p1;
}
}
p2->next = NULL;
return head; /*返回头节点指针*/
}
（5）创建reverse（）自定义函数，实现将单链表逆置，程序代码如下：
struct student *reverse（struct student *head）
{
struct student*p, *r;
if（head->next && head->next->next）
{
p=head; /*获取头节点地址*/
r = p->next;
p->next = NULL;
while（r）
{
p = r;
r = r->next;
p->next = head;
head = p;
} return head;
}
return head; /*返回头节点*/
}
（6）创建main（）函数，作为程序的入口函数，调用create（）自定义函数实现创建单链表，调用reverse（）自定义函数实现将单链表逆置。程序代码如下：
void main（）
{
int n, i;
int x;
struct student *q;
printf（"Input the count of the nodes you want to creat:"）;
scanf（"%d", &n）;
q=create（n）; /*创建单链表*/
q=reverse（q）; /*单链表逆置*/
printf（"The reserve linklist is:\n"）;
while（q） /*输出逆置后的单链表*/
{
printf（"%d ", q->num）;
q = q->next;
} getch（）;
}
举一反三
根据本实例，读者可以：
使用链表统计运动会分数。
使用链表统计学生成绩。
实例089 头插入法建立单链表
本实例是一个提高基础技能的程序
实例位置：光盘\mingrisoft\03\089
实例说明
本实例实现使用头插入法创建一个单链表，并将单链表输出在窗体上。程序运行效果如图3.23所示。
图3.23 头插入法创建链表
技术要点
头插入法创建单链表算法的思想是：先创建一个空表，生成一个新节点，将新节点插入到当前链表的表头节点之后，直到插入完成。
头插入法创建的链表的逻辑顺序与在屏幕上输入数据的顺序相反，所以头插入法也可以说成是逆序建表法。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
（3）声明struct student类型：
typedef struct student
{
char num;
struct student *next;
}LNode, *LinkList;
（4）创建create（）自定义函数，实现创建一个链表，返回创建的链表的头节点地址。代码如下：
LinkList create（void）
{
LinkList head;
LNode *p1;
char a;
head = NULL;
printf（"Please input the linklist's records:\n"）;
a = getchar（）;
while（a != '\n'）
{
p1=（LinkList）malloc（sizeof（LNode））; /*分配空间*/
p1->num=a; /*数据域赋值*/
p1->next = head;
head = p1;
a = getchar（）;
}
return head; /*返回头节点*/
}
（5）创建main（）函数作为程序的入口函数，调用create（）自定义函数实现创建链表。程序代码如下：
main（）
{
LinkList L1;
L1 = create（）;
printf（"The linklist is:\n"）;
while（L1）
{
printf（"%c ", L1->num）;
L1 = L1->next;
}
getch（）;
}
举一反三
根据本实例，读者可以：
查找学生成绩。
按学号对学生进行排序。