链表知识.doc

一、链表的建立
　　　链表的建立比较简单，可以建立一个包含数据域和指向本身结构的指针域的结构
体，然后将当前结点的指针指向下一个结点，以此类推就可以创建链表，最后一个结点
的指针域赋空指针。下面通过一个具体例子进行介绍。
　　　【例11-1】创建一个包含表头结点和10个结点的链表，假设这个链表表征学生
的数据，包含学生的学号、考试成绩。
　　　(为讲解方便，将下面的代码加上行号，大家在上机调试时不能加行号)
　　　　　1: #include "stdlib.h"
　　　　　2: #include "stdio.h"
　　　　　3: struct stu
　　　　　4: {
　　　　　5: int num;
　　　　　6： float score;
　　　　　7： struct stu *next;
　　　　　8：};
　　　　　9：struct stu *create(int n)
　　　　　10：{
　　　　　11： struct stu *mylist,*tempnode,*cursor;
　　　　　12： mylist = (struct stu *)malloc(sizeof(struct stu));//分配表头结点的存储空间
　　　　　13： if ( mylist == NULL ) // 判断表头结点的内存分配是否成功,不成功,则结束程序
　　　　　14： {
　　　　　15： printf("\n错误：内存分配失败! 程序结束") ;
　　　　　16： exit( 1 ) ;
　　　　　17： }
　　　　　18： mylist->next = NULL ; // 现在的状态为空链表
　　　　　19： cursor = mylist ;
　　　　　20： for( int i = 0 ; i < n ; i ++ )
　　　　　21： {
　　　　　22： tempnode=(struct stu *)malloc(sizeof(struct stu)) ;//开辟结点存储空间
　　　　　23： if (!tempnode) //如果开辟存储空间失败，下面的语句就做出报告
　　　　　24： {
　　　　　25： printf("\n错误：内存分配失败! 程序结束") ;
　　　　　26： exit( 1 ) ;
　　　　　27： }
　　　　　28： tempnode->next = NULL ; //防止不定指针。
　　　　　29： tempnode->num = 10*i ;
　　　　　30： tempnode->score = 20.5*i+10;
　　　　　31： cursor->next = tempnode ; //将结点连接到链表上
　　　　　32： cursor = cursor->next ; //将链表的光标移动到下一个结点上
　　　　　33： printf("num=%d, 　　score=%f\n",tempnode->num,tempnode->score);
　　　　　34：}
　　　　　35： printf("\n");
　　　　　36： return(mylist);
　　　　　37: }
　　　链表的建立通过create()函数来完成。代码的3~8行定义一个链表结构，第
9~37行是创建链表的函数，其中，第12行分配了表头结点的存储空间，第20~34行的循
环体创建了表的结点并对结点进行初始化。大家可能会发现，该例题的代码中对结点值
是通过循环进行非常有规律的赋值，实际上，读者完全可以根据实际情况改成从键盘输
入数据(而且做法很简单)，例题中这样做只是为了调试程序的方便，不用一次次的输入
数据。接下来就可以对链表进行各种操作了，需要注意的是在程序结束前，一定要将链
表的内存空间释放掉，以免占用内存。
　　　下面是调用create()函数的主函数及链表输出函数print()的代码。
　　　　　print( struct stu *list)
　　　　　{
　　　　　struct stu *cursor ;
　　　　　cursor = list;
　　　　　if( list != NULL)
　　　　　do
　　　　　{
　　　　　cursor = cursor->next ; // 依次遍历链表
　　　　　printf("num=%d score=%f\n",cursor->num,cursor->score);
　　　　　}while(cursor->next!=NULL);
　　　　　}
　　　　　void main()
　　　　　{ int n; //链表结点数
　　　　　struct stu *my_list;
　　　　　printf("Input the number of node\n");
　　　　　scanf("%d",&n); //输入链表结点数
　　　　　my_list=create(n); //返回所创建的链表
　　　　　print(my_list);
　　　　　}

二、
我们知道，数组式计算机根据事先定义好的数组类型与长度自动为其分配一连续的存储单元，相同数组的位置和距离都是固定的，也就是说，任何一个数组元素的地址都可一个简单的公式计算出来，因此这种结构可以有效的对数组元素进行随机访问。但若对数组元素进行插入和删除操作，则会引起大量数据的移动，从而使简单的数据处理变得非常复杂，低效。
为了能有效地解决这些问题，一种称为“链表”的数据结构得到了广泛应用。
1． 链表概述
链表是一种动态数据结构，他的特点是用一组任意的存储单元（可以是连续的，也可以是不连续的）存放数据元素。
链表中每一个元素成为“结点”，每一个结点都是由数据域和指针域组成的，每个结点中的指针域指向下一个结点。Head是“头指针”，表示链表的开始，用来指向第一个结点，而最后一个指针的指针域为NULL(空地址)，表示链表的结束。
可以看出链表结构必须利用指针才能实现，即一个结点中必须包含一个指针变量，用来存放下一个结点的地址。
实际上，链表中的每个结点可以用若干个数据和若干个指针。结点中只有一个指针的链表称为单链表，这是最简单的链表结构。
再c++中实现一个单链表结构比较简单。例如，可定义单链表结构的最简单形式如下
struct Node
{
int Data;
Node*next;
};
这里用到了结构体类型。其中，*next是指针域，用来指向该结点的下一个结点；Data是一个整形变量，用来存放结点中的数据。当然，Data可以是任何数据类型，包括结构体类型或类类型。
在此基础上，我们在定义一个链表类list，其中包含链表结点的插入，删除，输出等功能的成员函数。

class list
{
Node*head;
public:
list(){head=NULL;}
void insertlist(int aDate,int bDate);//链表结点的插入
void Deletelist(int aDate);//链表结点的删除
void Outputlist();//链表结点的输出
Node*Gethead(){return head;}
};
2． 链表结点的访问
由于链表中的各个结点是由指针链接在一起的，其存储单元文笔是连续的，因此，对其中任意结点的地址无法向数组一样，用一个简单的公式计算出来，进行随机访问。只能从链表的头指针（即head）开始，用一个指针p先指向第一个结点，然后根据结点p找到下一个结点。以此类推，直至找到所要访问的结点或到最后一个结点（指针为空）为止。
下面我们给出上述链表的输出函数；
void list::outputlist()
{
Node*current=head;
while(current!=NULL)
{
cout<<current->Data<<" ";
current=current->next;
}
cout<<endl;
}
3． 链表结点的插入
如果要在链表中的结点a之前插入结点b，则需要考虑下面几点情况。
（1） 插入前链表是一个空表，这时插入新结点b后。
（2） 若a是链表的第一个结点，则插入后，结点b为第一个结点。
（3） 若链表中存在a,且不是第一个结点，则首先要找出a的上一个结点a_k，然后使a_k的指针域指向b，在令b的指针域指向a，即可完成插入。
（4） 如链表中不存在a，则插在最后。先找到链表的最后一个结点a_n，然后使a_n的指针域指向结点b，而b指针的指针为空。
以下是链表类的结点插入函数，显然其也具有建立链表的功能。
void list::insertlist(int aDate,int bDate) //设aDate是结点a中的数据，bDate是结点b中的数据
{
       Node*p,*q,*s; //p指向结点a，q指向结点a_k，s指向结点b
       s=(Node*)new(Node); //动态分配一个新结点
       s->Data=bDate; //设b为此结点 
       p=head;
      if(head==NULL) //若是空表，使b作为第一个结点
        {
            head=s;
            s->next=NULL; 
         }
       else
            if(p->Data==aDate) //若a是第一个结点
               {
                  s->next=p;
                  head=s; 
               }
            else
              {
                  while(p->Data!=aDate&&p->next!=NULL)//查找结点a
                    {
                            q=p;
                             p=p->next;
                     }
                   if(p->Data==aDate) ///若有结点a
                    {
                          q->next=s;
                           s->next=p; 
                     } 
                     else //若没有结点a；
                   {
                          p->next=s;
                           s->next=NULL; 
                    }
             }
}
4． 链表结点的删除
如果要在链表中删除结点a并释放被删除的结点所占的存储空间，则需要考虑下列几种情况。
（1） 若要删除的结点a是第一个结点，则把head指向a的下一个结点。
（2） 若要删除的结点a存在于链表中，但不是第一个结点，则应使a得上一个结点a_k-1的指针域指向a的下一个结点a_k+1。
（3） 空表或要删除的结点a不存在，则不做任何改变。
以下是链表类的结点删除函数。
void list::deletelist(int aDate) //设aDate是要删除的结点a中的数据成员
{
Node*p,*q; //p用于指向结点a,q用于指向结a的前一个结点
p=head;
if(p==NULL) //若是空表
return;
if(p->Data==aDate) //若a是第一个结点
{
head=p->next;
delete p;
}
else
{
while(p->Data!=aDate&&p->next!=NULL) //查找结点a
{
q=p;
p=p->next;
}
if(p->Data==aDate) //若有结点a
{
q->next=p->next;
delete p;
}
}
}
例题；利用以上三个链表操作成员函数insertlist,deletelist.outputlist,可形成以下的简单链表操作程序。
#include"iostream.h"
struct Node
{
int Data;
Node*next;
};
class list
{
Node*head;
public:
list(){head=NULL;}
void insertlist(int aData,int bData);
void deletelist(int aData);
void outputlist();
Node*gethead(){return head;}
};

void list::insertlist(int aData,int bData) //设aData是结点a中的数据，bData是结点b中的数据
{
Node*p,*q,*s; //p指向结点a，q指向结点a_k，s指向结点b
s=(Node*)new(Node); //动态分配一个新结点
s->Data=bData; //设b为此结点
p=head;
if(head==NULL) //若是空表，使b作为第一个结点
{
head=s;
s->next=NULL;
}
else
if(p->Data==aData) //若a是第一个结点
{
s->next=p;
head=s;
}
else
{
while(p->Data!=aData && p->next!=NULL)//查找结点a
{
q=p;
p=p->next;
}
if(p->Data==aData) ///若有结点a
{
q->next=s;
s->next=p;
}
else //若没有结点a；
{
p->next=s;
s->next=NULL;
}
}
}
void list::deletelist(int aData) //设aData是要删除的结点a中的数据成员
{
Node*p,*q; //p用于指向结点a,q用于指向结a的前一个结点
p=head;
if(p==NULL) //若是空表
return;
if(p->Data==aData) //若a是第一个结点
{
head=p->next;
delete p;
}
else
{
while(p->Data!=aData&&p->next!=NULL) //查找结点a
{
q=p;
p=p->next;
}
if(p->Data==aData) //若有结点a
{
q->next=p->next;
delete p;
}
}
}
void list::outputlist()
{
Node*current=head;
while(current!=NULL)
{
cout<<current->Data<<" ";
current=current->next;
}
cout<<endl;
}
void main()
{
list A,B;
int Data[10]={25,41,16,98,5,67,9,55,1,121};
A.insertlist(0,Data[0]); //建立链表A首结点
for(int i=1;i<10;i++)
A.insertlist(0,Data[i]); //顺序向后插入
cout<<"\n链表A:";
A.outputlist();
A.deletelist(Data[7]);
cout<<"删除元素Data[7]后";
A.outputlist();
B.insertlist(0,Data[0]); //建立链表B首结点
for(i=0;i<10;i++)
B.insertlist(B.gethead()->Data,Data[i]); //在首结点处顺序向后插入
cout<<"\n链表B:";
B.outputlist();
B.deletelist(67);
cout<<"删除元素67后";
B.outputlist();
}
程序运行结果为
链表A；25，41，16，98，5，67，9，55，1，121
删除元素Data[7]后；
25，41，16，98，5，67，9，1，121
链表B；121，1，55，9，67，5，98，16，41，25，
删除元素67后；
121，1，55，9，5，98，16，41，25，

下面是杨辉三角的代码：
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
const int n=11;
int i,j,a[n][n];
for(i=1;i<n;i++)
{
a[i][i]=1;
a[i][1]=1;
}
for(i=3;i<n;i++)
{
for(j=2;j<=i-1;j++)
a[i][j]=a[i-1][j-1]+a[i-1][j];
}
for(i=1;i<n;i++)
{
for(j=1;j<=i;j++)
cout<<setw(5)<<a[i][j]<<" ";
cout<<endl;
}
cout<<endl;
return 0;
}