c++8.dat

程序字典 经典的东西 里面有C、汇编、JAVA的字典

};
void main (void)
{
　Person_Info* p1;
　p1 = new Person_Info; // 申请内存
　p1->age = 32; // 给age成员赋值
　strcpy(p1->name,"Bobbie"); // 给name成员赋值 
　// 打印p1指向的内容
　cout << "Name: " << p1->name << endl; // 打印name成员
　cout << "Age: " << p1->age << endl; // 打印age成员
　delete p1; // 释放申请的内存
}  
　　该程序的运行结果为:
　　Name：Bobbie
　　Age：32 


第五节 链表

我们已经知道：数组是一种数据结构,用来保存线性数据.它并不象数组那样,需要一个连续的内存块.使用链表时,每一个数组元素动态地分配内存单元,并通过指针把他们联系在一起,链表元素我们也称之为链表结点.
　　每一个结点包含两个域：数据域和指针域.数据域保存数据,指针域连接该结点到下一个结点.每一个结点用new在堆中申请内存,所以在用delete释放申请的内存以前,结点的内存一直存在.链表的前端有一个指向第一个结点的指针,最后一个结点的指针域不指向别的结点.

 　　在某一类数据集合中,依据数据成员之间的关系的不同,可把数据结构分为两大类：线性结构和非线性结构.线性结构中各个数据成员一次排列在一个线性序列中,如数组和链表等；非线性结构中,每个数据成员可能与零个或多个其它数据成员之间发生关系,如树和图.
　　用数组来存放数据的时候,需要事先确定数组的长度,并分配连续的内存空间.因而不能动态地分配内存,不能改变数组的大小.而链表是一种非连续存放的重要的线性数据结构,它可以对存储空间进行动态的分配.比如我们要对一个公司员工数据进行记录,由于公司的人事可能会经常地变动,涉及到员工人数的增减.如果用数组来存放员工的记录,当员工人数发生变化的时候,数组的大小很难做到相应的变化.如果人数减少,数组会有剩余空间,但人数增加,原来的数组大小可能不够,就必须重新开数组.这样就会产生浪费空间或增加维护负担等问题.如果改用链表来存放员工的数据,就不会产生这些问题,因为链表对存储空间的分配是动态的.
　　链表是由一些列的结点组成,每一个结点包含数据和指向下一结点的指针.每一个结点占用一块存储单元,当要在链表中增加一个结点时,可动态地为该结点分配一个存储单元；当要在链表中删除一个结点时,也可释放该结点的存储单元.下图是一个简单的链表示意图：
               1356           1475            1021
               -----          -----           -----
        head-->  A     |----->  B     |------>  C
               -----   |      -----   |       -----
               1475  --|      1021  --|       NULL 
               -----          -----           ----- 
 
　　该链表由3个结点组成,其中每个结点都分为两个域,一个是数据域(即图中的大写字母A、B、C),存放各种实际的数据,如学号num、姓名name、性别sex和成绩score等.另一个域为指针域,存放下一结点的首地址.比如第一个结点的指针域存放的地址是1475,就是第二个结点的首地址.链表中的每一个结点都是同一种结构类型.
　　另外,每个链表都有一个头指针head,它存放的是链表头结点的首地址.我们就可以通过链表的head指针找到链表的头结点,然后通过该结点的指针域找到一个结点的首地址,从而可以找到该链表的所有结点.需要注意的是：最后一个结点的指针域为NULL,据此,我们可以判断一个链表是否结束.下面是一个学生结构的实例：
　　struct stu
　　{ 
　　　int num;
　　　int score;
　　　stu *next;
　　}
　　前两个成员组成数据域,后一个成员next是指针域,它是一个指向stu类型结构的指针变量.
　　对链表的主要操作有以下几种：
　　1. 建立链表；
　　2. 结构的查找与输出；
　　3. 插入一个结点；
　　4. 删除一个结点；
　　下面对每一种操作具体进行讲解.
 
 5.1 链表的创建
　　为了创建图8-3所示链表,我们需要定义下面的结构：
　　struct node {
　　　int data;
　　　node* next;
　　};

 5.2 链表的遍历和查找
　　下面我们看一个简单的链表操作函数Length(),该函数计算链表中结点的个数.
　　//给定链表的头指针,计算并返回链表结点的个数
　　int Length(node* head)
　　{
　　　node* current = head;
　　　int count = 0;
　　　while (current != NULL) {
　　　count++;
　　　current = current->next;
　　}
　　return count;
　　} 
　　计算链表结点个数时,该函数使用了循环语句,这也是对链表操作中常用的方法.上面的函数是用while循环语句,也可以用下面的for循环语句替代：
　　for (current = head; current != NULL; current = current->next)
　　{ … }
　　Length()函数有下面几个特点：
　　(1) current是一个局部指针变量,它最初与head指向相同的结点.当函数返回后,它被自动释放,但链表结点依然在堆内存中.
　　(2) 能够适应空链表的情形,此时current=head=NULL,循环体中的语句不会执行.
　　(3) 循环体中的语句"current = current->next;",使局部指针current移向链表的下一个结点.当到达最后一个结点时,执行 "current = current->next; "语句后,current为NULL.
　　下面的程序是调用Length()函数的实例,先调用BuildOneTwoThree()函数创建链表,然后调用Length()函数计算链表结点的个数：
　void LengthTest() 
　{
　　node* myList = BuildOneTwoThree();
　　int len = Length(myList);
　　　　　　// len的结果为3
　}
　　我们可以用与Length()函数类似的方法查找链表中的某一个结点.
　　//给定链表的头指针和待查结点数据,返回查到的结点的指针
　　node* Find(node* head,int data)
　　{
　　　node* current = head;
　　　while (current!=NULL)
　　　if(current->data == data) break;
　　　else current = current->next; 
　　　return current;
　　}
　　Find()函数的功能是：输入链表头结点head和待查结点数据data,如果某一个结点的数据与data相等,则返回该结点的指针；如果查完每一个结点也没有找到数据与data相等的结点,则返回空指针.
　　需要注意的是：Find函数也可以写成下面的形式.
　　//给定链表的头指针和待查结点数据,返回查到的结点的指针
　　node* Find(node* head,int data)
　　{
　　　node* current = head;
　　　while (current!=NULL&& current->data == data)
　　　current = current->next; 
　　　return current;
　　}
　　但把while的条件"current!=NULL&& current->data == data"写成" current->data == data &&current!=NULL"的形式,则Find函数可能会出现运行错误.这是因为：如果链表的最后一个结点,仍然不是要找的结点,则到下一次循环时current为NULL,再进行条件判断时,前者current!=NULL为真,而不再作current->data == data的判断,循环便结束；而后者在作current->data == data判断时就会导致程序崩溃.

   由于链表具有的特殊结构,我们在对链表中的结点进行访问和查找的时候,必须从链表的头结点开始,按照链表结点指针域所指的顺序逐个查找结点,直到找到为止.
　　首先,我们来看看计算链表结点个数的函数Length()是如何实现的：
　　int Length(node* head) //以指向链表头结点的指针作为参数
　　{　
　　　node* current = head; //定义一个结点指针,并使之指向链表头结点
　　　int count = 0; //计数器变量,初值为0
　　　while (current != NULL) { //如果未到链表尾,继续循环
　　　count++; //计数器加1
　　　current = current->next; //指针current指向下一个结点
　　}
　　return count; //返回计数值,即链表长度
　　} 
　　该函数就利用了链表结点的特点,即各结点通过指针依次链接起来,从头结点开始,使一个结点的指针依次指向下一个结点,同时计数器加1.这样,就实现了对链表结点个数的统计.Length( )函数对链表结点依次访问的过程,实际上就是对链表的一次遍历,得到所需要的信息.针对链表的这种访问方式,可以打个简单的比方：比如有一队小朋友手拉手站着,现在我们要对小朋友的人数进行统计.首先设定人数值为0,这时,我们只需要找出站在队首的小朋友,通过他们互相拉着的手找到下一个小朋友,同时每找到下一个小朋友就对计数器加1,直到找到最后一个小朋友为止,也就得到了该队小朋友的总人数.
　　为了对链表的一个结点数据进行修改或者需要读取某个结点的一些数据,就要用到链表的查找.我们可以参考链表遍历的方法,对链表的结点逐个访问,判断该结点的数据是否是我们要找的数据值.若是,则查找成功,返回指向该结点的指针；若不是,则继续判断下一个结点,直到到达链表尾为止.若查找失败,则返回NULL：
　　node* Find(node* head,int data) //以链表头指针和待插数据为参数
　　{
　　　node* current = head; //定义指针变量,指向头指针
　　　while (current!=NULL) //如果没有到达链表尾,则继续查找
　　　if(current->data == data) break; 
　　　//如果该结点数据等于待查数据,则查找成功,跳出循环
　　　else current = current->next; //否则继续指向下一个结点
　　　return current; //返回当前指针
　　}

 5.3 链表的插入和删除
　　链表和数组都是保存线性数据,前者的优点在于能够方便地进行数据元素的插入和删除,链表结点的插入和删除操作是链表很常用的操作.在一个链表中插入一个结点或删除一个结点,需要知道待插入结点位置及前一个结点位置的指针,然后改变链表中结点的链接关系.
　　链表的两个指针可以根据实际情况确定,例如,假定有一个链表,其头指针为head,结点数据是由小到大排序的.现要在该链表中插入一个结点position,继续保持链表的排序关系,两个指针就可以通过搜索原链表结点得到,其代码如下：
void Insert(node* &head,node* position)
{
　node * before, *current;
　before = current = head;
　//搜索链表,确定指针before和current
　while (current!=NULL)
　　if(current->data >= position ->data) break;
　　else{
　　　before = current;
　　　current = current->next;
　　}
　//插入结点position
　　if(current == head){ //插在链表头
　　　position ->next = head;
　　　head = position;
　　}
　　else{ //插在链表中间
　　　before ->next = position;
　　　position ->next = current;
　　}
}