singlelink.txt

单链表的实现的程序 VC++编写 保存为TXT格式

/*实验一：单链表的操作*/
#include<iostream.h>
struct node{
      int data;
      node *next;
};

/*逆序生成单链表*/
node *creat()
{
    node *head,*p,*q;
    head=0;  //首节点指针初始值为0
    //cout<<"以数字1-10为例，逆序生成单链表!\n";
    int n=0;  //节点个数计数器
    int num[100];
    cout<<"请按先后顺序输入所有要存入单链表的数据(以-1结束):\n";
    for(int k=0;k<100;k++)
    {
      cin>>num[k];
      if(num[k]==-1) break;
    } //此时k为单链表长度 
    k--;
    for(int j=k;j>=0;j--)
    {   
        n++;
        p=new node;
        p->data=num[j];
        if(head==NULL)
        {  
          p->next=NULL;
          head=p;
        }
        else
        {
           p->next=head;
           head=p;
        }
    }
    q=new node;
    q->data=n;  //存储该单链表的长度
    q->next=head;
    head=q;    //形成头节点
    return head;
}  

/*在第i个节点之后插入节点数据为x的新节点,i>=0,若i=0,则在头节点之后插入*/
node *insert(node *head,int xx,int i)
{
    if(i<0||i>head->data)
      cout<<"位置超出了范围!\n";
    else
    {
        node *p;//建立一个新节点，用于存储新数据
		p=new node;
        p->data=xx;
		p->next=NULL;
        if(i==0)  //新节点作为首节点
        {
            p->next=head->next;
            head->next=p;
            head->data=head->data+1; //链表长度加1
        }
        else
        {
             node *q=head->next; //q指向首节点
             int j=1; //指示应插入新节点的位置
             while(q->next && j<i)
             {
                  q=q->next;
                  j++;
             }
             if(!q->next)
                 cout<<"未找到"<<i<<"节点!\n";
             else
             {
                  p->next=q->next;
                  q->next=p;
                  head->data=head->data+1; //链表长度加1
             }
         }
     } 
	return head;
}

/*删除链表中内容为x的节点*/
node *delnode(node *head,int x)
{
    if(head==NULL)
      cout<<"链表下溢!\n";
    else
    {
        node *p,*q;
        p=head->next;
        q=head;         //q始终指向p的前一个节点
        while(p!=NULL && p->data!=x)
        {
            p=p->next;
            q=q->next;  //q始终指向p的前一个节点
        }
        if(p==NULL)
           cout<<"未找到内容为"<<x<<"的节点!\n";
        else  /*p是内容为x的节点*/
        {
            if(!p->next) //若p是最后一个节点
            {
                q->next=NULL; //节点q为最后一个节点
                delete(p);
            }
            else
            {
                q->next=p->next;//置q指向p的下一个节点
                delete(p);  //删除节点p
            }
            cout<<"删除内容为"<<x<<"的节点"<<"成功!\n";
            head->data--;//链表长度减1
        }  
	}
	return head;//返回当前新链表的头节点
}

void output(node *head)
{
	if(head==NULL)
		cout<<"链表内容为空!\n";
	else
	{ 
		cout<<"链表内容为:\n";
		node *pp=head->next;
        for(int h=0;h<head->data;h++)
		{
		cout<<pp->data<<'\t';
	 	pp=pp->next;
		}
        cout<<'\n';
	}
}


void main(void)
{
    node *head;
    head=creat();
    cout<<"链表长度为:"<<head->data<<'\n';
	output(head);
    char ope,ch='Y';
    while(ch=='Y'||ch=='y')
    { 
        cout<<"请输入操作名称(S—插入，D—删除节点):";
        cin>>ope;
        if(ope=='S'||ope=='s')
        {    
            int x,i;
            cout<<"执行插入操作!\n";
            cout<<"例如：输入 2 3，则在第3个节点后插入一个内容为2的新节点。\n";
            cout<<"若输入2 0，则在头节点之后插入内容为2的新节点。\n";
            cout<<"请输入要插入的数据内容以及插入位置：\n";
            cin>>x>>i;
            head=insert(head,x,i);
            cout<<"此时链表的长度为:"<<head->data<<'\n'; 
			output(head);
        }
        else if(ope=='D'||ope=='d')
        {
            cout<<"执行删除操作!\n";
            int x;
            cout<<"请输入要删除的节点内容:";
            cin>>x;
            head=delnode(head,x);
            cout<<"此时链表的长度为:"<<head->data<<'\n';
        }
        else
            cout<<"无效的操作命令!\n";
        cout<<"继续(Y/N)?\n";
        cin>>ch;
    }
}