s2.cpp

包含图的遍历和线性链表两个内容

//---------------------------------------------------------------------------

#include <stdio.h>
#include <malloc.h>
#include <process.h>
#include<iostream.h>
static int length=0;//length为链表长度
struct Node
 {
   int data;
   Node *next;
 };
Node *LinkList;//指向Noe结点类型的指针
Node *set()       //  初始化链表
{
     Node *p,*head;
     p=new Node ; //建立头结点
     head=p;
     p->data=0;
     p->next=0;
     return (head);//返回头结点
}
Node *Get(Node *L1,int m)//链表尾添加新结点
{
          Node *p=L1,*q;
	  q=new Node;//建立新结点
	  q->data=m;
	  q->next=0;
	  while(p->next!=0)
	     p=p->next;
	  p->next=q;//将结点链接在表尾
	  return (L1);
}
Node *insert(Node *L1,int m,int n)//在第n个位置之前插入新结点m
{
    int i=1;
    Node *p=L1,*q,*r;
    q=new Node;//建立新结点
    q->data=m;
    q->next=0;
    while(i<n) { p=p->next;i++;}//寻找插入位置 n
    r=p->next;
    p->next=q;
    q->next=r;//进行插入
    return L1;
}
Node *Det(Node *L1,int m)//删除结点
{
       Node *p=L1,*q;
       while(p->next&&p->next->data!=m)
	   p=p->next;//寻找所要删除的结点
       if(p->next==0) { printf("找不到此数\n"); return(L1);}
	  else if(p->next->next==0)
	  {
             q=p->next;
	     p->next=0;//删除的结点在表尾
	  }
	   else { q=p->next;
	           p->next=q->next;
	   }
       free(q);//释放空间
	   return(L1);
}
int Lookfor( Node *L1,int m)//查找结点
{
     Node *p=L1;
    int i=1;
       while(p->next&&p->next->data!=m)
	   { p=p->next; i++;}

        if(p->next==0) { printf("找不到此数\n"); return 0;}
        printf("此元素在链表中的位置为%d\n",i);
		return 1;
}

void out( Node *L1)//输出链表各结点元素
{
   Node *p=L1->next;//排除头结点
    while(p)              //非空，输出结点
       {
          printf("%d ",p->data);
          p=p->next;
       }
   printf("\n");
}
Node *Sort(Node *L1)//插入排序
{
    Node *L=L1,*q=L1->next->next,*r,*s,*p;
    L->next->next=0;//按序的新链表
    while(q) 
    {
        p=L;
	while(p->next&&p->next->data<=q->data)//寻找插入位置
        p=p->next;
        r=q->next;
       	if(p->next==0) { p->next=q; q->next=0;}//直接插在表尾
         else
               {
                 s=p->next;
                 p->next=q;
	         q->next=s;
               }
        q=r;
     }
   return L;
}
void main()   //主函数
{
         Node * p;
         int m=0,n,i;
         p=set();    //建立头结点
         cout<<"欲输入的结点个数:";
	 cin>>n;
	 cout<<"输入所有结点:";
	 while(m<n)
	 {
         cin>>i;

	 p=Get(p,i); //链表尾添加新结点
	 m++;
	 length++;//长度加1
	 }
	 cout<<"所建链表为：\n";
         out(p);  //输出链表

	 cout<<"新插入的元素及插入位置:";
         scanf("%d%d",&i,&m);
	 p=insert(p,i,m); //插入
	 length++;//长度加1
	 cout<<"插入新元素后链表为：\n";
         out(p) ;   //输出链表

         cout<<"输入删除的结点元素位置:";
         scanf("%d",&i);
         p=Det(p,i);length--;//长度减1
	 cout<<"删除元素后链表为：\n";
	 out(p);  //输出链表

        cout<<"输入查找的结点元素:";
	scanf("%d",&i);
	Lookfor(p,i);
	p=Sort(p);   //排序
	cout<<"排序后链表为：\n";
        out(p); //输出链表
}

//---------------------------------------------------------------------------