lksource.cpp

数据结构的链表使用

#include<malloc.h>
#include<stdlib.h>
#include<iostream.h>
  #define TRUE 1
  #define FALSE 0
  #define OK 1
  #define OVERFLOW -2
 
  #define ERROR 0
  #define INFEASIBLE -1

  #define LIST_INIT_SIZE 100
  #define LISTINCREMENT 10

  typedef int ElemType;
  typedef int Status;



  typedef struct LNode{
	  ElemType data;
	  struct LNode *next;
  }LNode,*LinkList;


  Status visit(ElemType p)
   {
	   cout<<p;
	   return OK;
   }


 Status   compare(ElemType x,ElemType y)
   { 
	   if (x==y) return OK;
	   else return FALSE;
   }



  Status  InitList_Lk(LinkList &L,int n)
  {
	  int i;
	  LNode *p;

	  L=(LinkList)malloc(sizeof(LNode));
	  if(!L) exit(OVERFLOW);
	  L->next=NULL;
	  cout<<"输入"<<n<<"个字符";
	  for(i=0;i<n;i++)
	  {
		  p=(LinkList)malloc(sizeof(LNode));
		  if(!p)  exit(OVERFLOW);
		  
		  cin>>p->data;//scanf(p->data);
		  p->next=L->next;
		  L->next=p;
	  }
	  return OK;
  }//(1)建立有n个节点的链表， n为0时只有一个空表头


  Status DestroyList_Lk(LinkList &L)
  {
	  LNode *p;
	  while(L->next)
	  {
		  p=L->next;
		  L->next=p->next;
		  free(p);
	  }
	  free(L);
	  return OK;
  }//(2)头指针也没了



  Status ClearList_Lk(LinkList &L)//???????
  {
	  LNode *p;
	  p=L->next;
	  if(p)
	  {
		  do
		  {
			  p->data=L->data;
			  p=p->next;
		  }while(p);
	  }
	  return OK;
  }//(3)节点数据皆为空表头数据,不好用


  Status ListEmpty_Lk(LinkList &L)
  {
	  LNode *p;
	  p=L->next;
	  while(p)
	  {
		  if(p->data!=L->data) break;//!!!!!
		  else p=p->next;
	  }
	  if(!p) return TRUE;
	  else return FALSE;
  }//(4)链表仍然存在


  int Listlength_Lk(LinkList L)
  {
	  int length;
	  LNode *p;

	  length=0;
	  p=L->next;
	  while(p){length++; p=p->next;}
	  return length;
  }//(5)反映链表总长；包括无意义数据的节点


  Status GetElem_Lk(LinkList L,int i,ElemType &e)
  {
	  LinkList p;
	  int j;
	  p=L->next;
	  j=1;

	  while(p&&j<i)
	  {p=p->next; j++;}
	  if(!p||j>i) return ERROR;
	  else{e=p->data; return OK;}
  }//(6)??????取第i个节点的数据——用e取


  int LocateElem_Lk(LinkList L,ElemType e)
  {
	  LNode *p;
	  int Location;
	  Location=1;
	  p=L->next;
	  while(p)
	  {
		  if(compare(p->data,e)) break;
		  else{Location++;   p=p->next;}
	  }
	  if(!p) return 0;
	  else return Location;
  }//(7)确定数据e的第一个位置 


  Status PriorElem_Lk(LinkList L,ElemType cur_e,ElemType &pre_e)
  {
	  LNode *p,*q;
	  q=L->next;
	  if(!q) exit(OVERFLOW);
	  else p=q->next;
	  while(p)
	  {
		  if(compare(p->data,cur_e)) break;
		  else{q=p;p=q->next;}
	  }
	  if(!p)return ERROR;
	  else{pre_e=q->data;  return OK;}
  }//(8)  



 Status NextElem_Lk(LinkList L,ElemType cur_e,ElemType &next_e)
  {
	  LNode *p;
	  p=L->next;
	 
	  while(p->next)
	  {
		  if(compare(p->data,cur_e)) break;
		  else{p=p->next;}
	  }
	  if(!p->next)return ERROR;
	  else{next_e=(p->next)->data;  return OK;}
  }//(9)


  Status ListInsert_Lk(LinkList &L,int i,ElemType e)
  {
	  LNode *p,*s;
	  int j;
	  p=L;

	  for(j=1;j<i&&p;j++)
		 p=p->next;
	  if(i==0||!p) return ERROR;
	  else
	  {
		  s=(LNode*)malloc(sizeof(LNode));
		  s->data=e;
		  s->next=p->next;
		  p->next=s;
		  return OK;
	  }
  }//(10)??????WRONG


  Status ListDelete_Lk(LinkList &L,int i, ElemType &e)
  {
	  LNode *p,*q;
	  int j;
	  q=L;
	  p=L->next;
	  for(j=1;j<i&&p;j++)
	  {q=p; p=p->next;}
	  if(i==0||!p) return ERROR;
	  else{q->next=p->next;  e=p->data;  free(p); return OK;}
  }//(11)?????


  Status ListTravers_Lk(LinkList L)
  {
	  LNode *p;
	  p=L->next;
	  while(p)
	  {
		  visit(p->data);  p=p->next;
	  }
		  return OK;
	  
  }


  void differ_Lk(LinkList A,LinkList B,LinkList C)
  {
	  LNode *p,*q,*s,*r;
	  p=A->next;
	  r=A;
	  q=B->next;
	  s=C->next;

	  while(p!=NULL&&q!=NULL&&s!=NULL)
	  {
		  if(q->data<s->data) q=q->next;
		  if(s->data<q->data) s=s->next;
		  if(q->data==s->data)
		  {
			  while(p->data<q->data&&p!=NULL){r=p;p=p->next;}
			  while(p->data==q->data&&p!=NULL){r->next=p->next; free(p); p=r->next;}
			  q=q->next;
		  }
	  }
  }






void main()
{
//	ElemType e;
//	ElemType cur_e,next_e,pre_e;
	LinkList List;
	InitList_Lk(List,0);
//	cout<<ListEmpty_Lk(List);
	ListInsert_Lk(List,1,1);
    ListInsert_Lk(List,1,2);
	ListInsert_Lk(List,3,3);
    ListInsert_Lk(List,4,4);
	ListInsert_Lk(List,5,5);
    ListInsert_Lk(List,6,6);
	ListInsert_Lk(List,7,7);
    ListInsert_Lk(List,8,8);
	ListTravers_Lk(List);
	cout<<endl;
	cout<<LocateElem_Lk(List, 0);

  
}
//INSERT DELETE CLEAT DESTROY