データ構造シングルチェーン表実現
29734 ワード
「データ構造」におけるシングルチェーンの実現Cコード
回転:
http://blog.chinaunix.net/uid-22750250-id-1769905.html
include.h
/******************************************************************
******************************************************************/
#include<string.h>
#include<ctype.h>
#include<malloc.h> // malloc()
#include<limits.h> // INT_MAX
#include<stdio.h> // EOF(=^Z F6),NULL
#include<stdlib.h> // atoi()
#include<io.h> // eof()
#include<math.h> // floor(),ceil(),abs()
#include<process.h> // exit()
#include<iostream.h> // cout,cin
/******************************************************************
******************************************************************/
#include "status.h"
list.h
#include "status.h"
//-------------- -------------------------
typedef int ElemType;
struct LNode
{
ElemType data;
struct LNode *next;
}LNode;
typedef struct LNode *LinkList;
//-------------- -------------------------
/***********************************************************
* *
************************************************************/
Status InitList(LinkList *L);//
Status ListInsert(LinkList *L,int i,ElemType e);//
Status ListDelete(LinkList *L,int i,ElemType *e);// L i ， e
Status ListEmpty(LinkList L);//
Status ClearList(LinkList *L);//
int ListLength(LinkList L);// L
Status GetElem(LinkList L,int i, ElemType *e);// L i
int LocateElem(LinkList L,ElemType e,Status (*compare)(ElemType , ElemType));//LocateElem
Status PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e);//
Status NextElem(LinkList L,ElemType cur_e,ElemType *next_e);//
Status ListTraverse(LinkList L,void(*vi)(ElemType));//Traverse L Vi L
Status DestroyList(LinkList *L);status.h/******************************************************************
******************************************************************/
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
// #define OVERFLOW -2 math.h OVERFLOW 3,
typedef int Status; // Status , ， OK
typedef int Boolean;list./******************************************************************************
list.h
12
******************************************************************************/
#include "include.h"
#include "list.h"
//----------------------- ------------------------------------------
Status InitList(LinkList *L)
{// ：
(*L)=(LinkList)malloc(sizeof(LNode));// L
if(!(*L)) //
exit(OVERFLOW);
(*L)->next=NULL;
return OK;
}
//----------------------- --------------------------------------------
Status ListInsert(LinkList *L,int i,ElemType e)
{// i e
LinkList p=*L,s;
int j=0;
while(p&&j<i-1)
{ // i-1
p=p->next;
j++;
}
if(!p||j>i-1) //i 1
return ERROR;
s=(LinkList)malloc(sizeof(LNode));//
s->data=e; // L
s->next=p->next;
p->next=s;
return OK;
}
//----------------------- -------------------------------------------
Status ListDelete(LinkList *L,int i,ElemType *e)
{// L i ， e
LinkList p=*L,q;
int j=0;
while(p->next&&j<(i-1)) // i ， p
{
p=p->next;
++j;
}
if(!(p->next)||j>(i-1)) //
return ERROR;
q=p->next;
p->next=q->next; //
*e=q->data;
free(q);
return OK;
}
//----------------------- -------------------------------------------
Status ListEmpty(LinkList L)
{// ：L 。 ： L TRUE, FALSE
if(L->next)
return FALSE;
else
return TRUE;
}
//----------------------- -------------------------------------------
Status ClearList(LinkList *L)
{// ：L 。 ： L 。
LinkList p,q;
p=(*L)->next; //
while(p) //
{
q=p->next;
free(p);
p=q;
}
(*L)->next=NULL;//
return OK;
}
//----------------------- L -----------------------------------
int ListLength(LinkList L)
{// ：L 。 ： L
LinkList p;
int i=0;
p=L->next; //p
while(p)
{
p=p->next;
++i;
}
return i;
}
//----------------------- L i -----------------------------------
Status GetElem(LinkList L,int i, ElemType *e)
{//L 。
// i e， OK， FALSE
LinkList p;
int j=0;
p=L->next; //
j=1;
while(p&&j<i) // ， p p i
{
p=p->next;
++j;
}
if(!p||j>i) // i
return ERROR;
*e=p->data; // i
return OK;
}
//-----------------------LocateElem -----------------------------
int LocateElem(LinkList L,ElemType e,Status (*compare)(ElemType , ElemType))
{// ： ，compare() （ 1， 0）
// ： L e compare()
int i=0;
LinkList p=L->next; //
while(p)
{
++i;
if(compare(p->data,e)) //
return i;
p=p->next;
}
return 0;
}
//----------------------- -----------------------------
Status PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e)
{// ：L
// ：cur_e L ， pre_e ，
// OK; ,pre_e , INFEASIBLE
LinkList q,p=L->next; //p
while(p->next) //
{
q=p->next; //q p
if(q->data==cur_e)
{
*pre_e=p->data;
return OK;
}
p=q; //
}
return INFEASIBLE;
}
//----------------------- -----------------------------
Status NextElem(LinkList L,ElemType cur_e,ElemType *next_e)
{// ：L
// ：cur_e L ， next_e ，
// OK; ,next_e , INFEASIBLE
LinkList p=L->next;//p
while(p->next) //
{
if(p->data==cur_e)
{
*next_e=p->next->data;
return OK;
}
p=p->next;
}
return INFEASIBLE;
}
//-----------------------visit ----------------------------------
Status ListTraverse(LinkList L,void(*vi)(ElemType))
{// ： L
// : L vi()。 vi() ,
LinkList p=L->next;//
while(p)
{
vi(p->data);
p=p->next;
}
printf("
");
return OK;
}
//----------------------- ----------------------------------
Status DestroyList(LinkList *L)
{ // ： L 。 ： L
LinkList q;
while(*L)
{
q=(*L)->next;
free(*L);
*L=q;
}
return OK;
}メール.#include "include.h"
#include "list.h"
Status compare(ElemType c1,ElemType c2)
{//
if(c1==c2)
return TRUE;
else
return FALSE;
}
void visit(ElemType c)
{
printf("%d ",c);
}
void main()
{
LinkList L,p;
Status result;
ElemType e;
int i=0;
//------------------------ -------------------------------
result=InitList(&L);
printf(" L ：L=%u
",L);
//---------------------------------------------------------------------
//----------------------- ----------------------------------
result=ListEmpty(L);
if(result)
printf("L
");
else
printf("L
");
//---------------------------------------------------------------------
//------------------------- --------------------------------
for(i=1;i<=5;i++)
ListInsert(&L,1,i);
printf(" L ：
");
p=L; //p
while(p->next)
{
printf(" %d ",p->next->data);
p=p->next;
}
printf("
");
//---------------------------------------------------------------------
//----------------------- ----------------------------------
printf(" 4
");
ListDelete(&L,4,&e);
printf(" L :
");
p=L; //p
while(p->next)
{
printf(" %d ",p->next->data);
p=p->next;
}
printf("
");
//---------------------------------------------------------------------
//----------------------- ----------------------------------
result=ListEmpty(L);
if(result)
printf("L
");
else
printf("L
");
//---------------------------------------------------------------------
//----------------------- ----------------------------------
printf(" L
");
result=ClearList(&L);
printf(" L：
");
result=ListEmpty(L);
if(result)
printf("L
");
else
printf("L
");
//---------------------------------------------------------------------
//------------------------- 10 --------------------------------
for(i=1;i<=10;i++)
ListInsert(&L,1,i);
printf(" L ：
");
p=L; //p
while(p->next)
{
printf(" %d ",p->next->data);
p=p->next;
}
printf("
");
//---------------------------------------------------------------------
//------------------------- L ---------------------
i=ListLength(L);
printf("L ：%d
",i);
//---------------------------------------------------------------------
//------------------------- L i ---------------------
result=GetElem(L,6,&e);
printf(" 6 ：%d
",e);
//---------------------------------------------------------------------
//-------------------------LocateElem ---------------------
printf(" L 4
");
if(i=LocateElem(L,4,compare))
printf(" %d 4
",i);
else
printf(" 4
");
//---------------------------------------------------------------------
//------------------------- ----------------------------
printf(" 4
");
//result=PriorElem(L,42,&e); //
result=PriorElem(L,4,&e);
if(result==OK)
printf(" 4 :%d
",e);
else
printf("
");
//---------------------------------------------------------------------
//------------------------- ----------------------------
printf(" 4
");
result=PriorElem(L,42,&e); //
//result=NextElem(L,4,&e);
if(result==OK)
printf(" 4 :%d
",e);
else
printf("
");
//---------------------------------------------------------------------
//-------------------------ListTraverse ------------------------
printf("ListTraverse , L 。
");
result= ListTraverse(L,visit);
printf("
");
//---------------------------------------------------------------------
//------------------------- --------------------------------
printf(" L ：L=%u
",L);
printf(" L...
");
DestroyList(&L);
printf(" L ：L=%u
",L);
//---------------------------------------------------------------------
}