算法结构之单链表的建立

一、实验目的

1．掌握单链表的基本运算：建立、插入和删除

2．掌握运用C语言上机调试单链表的基本方法。

二、实验环境

Windows和vc6.0

三、实验内容

设计算法，实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求：（1）从键盘输入n个整数，以0作为结束标记，产生不带表头的单链表，并输入结点值。（2）从键盘输入1个整数，在单链表中查找该结点的位置。若找到，则显示“找到了”；否则显示“找不到”。（2）从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出单链表所有结点值，观察输出结果。（4）从键盘输入1个整数，表示欲删除结点的位置，输出单链表所有结点值，观察输出结果。

   算法程序：

   #include

using namespace std;

struct node         //定义节点类型 

{

       int data;    //数据域 

       node *p;    //指针域 

};

class list           //链表类定义 

{

      public:

             list()

             { 

               head=NULL;

               n=0;

             }

             void creat(int end=0);  //创建链表函数声明 

             void find();           //查找节点函数声明 

             void inset();     //插入节点函数声明 

            void delet();      //删除节点函数声明 

             void print();       //输出链表函数声明 

      private:

              node *loca(int l);   //定位函数 

              node *head;        //链表头指针 

              int n;    //链表长度 

};

void list::creat(int end)   //创建链表函数

{

     int x;            //数据缓冲变量 

     node *a;          //临时指针变量                           

cout<<"新建链表，请输入n个整数,以0作为结束标志"<     while(1)

     {  

cin>>x; //输入进入缓冲X 

        if(x==end) break;  //如果存x放的结束符，跳出录入循环

        n++;            //表长增加1 

        if(n==1) 

         {a=new node;head=a;} //初始化头结点指针 

        else 

{a->p=new node;a=a->p;} //建立新节点并指向 

a->data=x; //数据域初始化 

a->p=NULL; //指针域初始化 

     } 

}

void list::find()     //查找节点函数 

{

     int x,i=0,m=0;

     node *a;      //临时指针变量 

     a=head;

cout<<"请输入要查找的节点值"< cin>>x;

     while(a!=NULL)

     { 

       i++;

if(a->data==x)

       {

cout<<"找到了！该值对应第"<< i<<"节点"<        m=1;

       }

a=a->p;

     }

if(m==0) cout<<"找不到!"<}

void list::inset()

{

     int i,x;

     node *b; 

     b=new node;               //临时指针变量 

cout<<"请输入欲插入的位置和数值"< cin>>i>>x;

b->data=x;

if(i==1) {b->p=head;head=b;n++;}

     else

     {

if(i>n) {loca(n)->p=b;b->p=NULL;n++;}

     else

{b->p=loca(i-1)->p;

loca(i-1)->p=b;

        n++;

        }

     }

}

void list::print()               //打印输出链表 

{    

cout<<"链表输出如下："<if(head==NULL) cout<<"链表为空!"<     node *a;                    //临时指针变量 

     a=head;                     //a指向头结点        

     while(a!=NULL)              //输出链表 

     {

cout<data<<" ";

a=a->p;

     }

cout<}

void list::delet()

{

     int i;

     node *a;

cout<<"你想删除第几个节点?"< cin>>i;

     a=loca(i);

if(i==1) {head=a->p;delete a;n--;}

     else

     {

if(i==n){loca(i-1)->p=NULL;delete a;n--;}

         else

         {

if(i>n) {cout<<"超出表长!"<         else

{loca(i-1)->p=a->p;

            delete a;

            n--;

            }

         }

     }     

}

node * list::loca(int l)

{    int i;

     i=l-1;

     node *a;                    //临时指针变量 

     a=head;

     while(i--)

     {

a=a->p;

     }

     return a;

}

int main()

{

 list zz;

    char a;

    zz.creat();

    while(1)

    {

cout<<"功能选择：c-建立 f-查找 i-插入 d-删除 p-输出 "< cin>>a;

        switch(a)

        {

          case 'c':{zz.creat();break;}

          case 'f':{zz.find();break;}

          case 'i':{zz.inset();break;}

          case 'd':{zz.delet();break;}

          case 'p':{zz.print();break;}

          default:break;         

        }

    }

}

运行结果：

思考题

如果生成带头结点的单链表，程序应如何修改？

四、实验报告要求

具体内容包含以下几项：实验题目、实验目的、实验环境、实验内容与完成情况（要求附上自主设计的源程序）、实验中出现的问题、对问题的解决方案、完成思考题、实验总结等。