www.pudn.com > 外壳示例3.rar > 80bao.h
/*------------双向循环链表的基本操作实现-----------------*/
#include
#include
/*----------------定义元素--------------------------------*/
typedef char ElementType;
/*---------------------定义节点----------------------------*/
typedef struct Node{
ElementType data;
struct Node *prior;
struct Node *next;
}ChainNode;
/*---------------------定义游标------------------------------*/
typedef struct Cursor{
ChainNode *cp;
int number;
}ListCursor;
/*--------------------定义结构-------------------------------*/
typedef struct List{
ChainNode *head;
ListCursor cursor;
}LinearList;
/* ************* 函数的申明 ************************ */
LinearList * CreateList(void); /*【创建】ok */
void DestroyList(LinearList *); /*【销毁】* /
int ClearList(LinearList *); /*【清空】ok */
ChainNode *GetAddr(LinearList *,int ); /*取节点的地址ok */
int MoveTo(LinearList *,int); /*【移动游标】ok */
int MoveNext(LinearList *); /*【后移游标】ok */
int MovePrior(LinearList *); /*【前移游标】ok */
int MoveBegin(LinearList *); /*【设游标至第一个节点】ok */
int MoveEnd(LinearList *); /*【设游标至最后一个节点】ok */
int ListInsert(LinearList *,int ,ElementType );/* 插入元素 ok*/
int ListDelete(LinearList *,int); /* 删除元素 ok*/
int ListInsertCurrent(LinearList *,ElementType);/*ok*/
/* 在当前位置插入元素（在游标指向元素前插入元素，插入后游标指针项不变，号码项++）*/
int ListDeleteCurrent(LinearList *);/* ok*/
/*删除当前位置的元素（删除游标所指向的元素，删除后游标号码项不变，指针项后移）*/
int ListAppend(LinearList *,ElementType);/* 追加元素ok */
int FindElement(LinearList *,int (*)(ElementType,ElementType),ElementType,int);
/*找元素 ok */
int ListTraverse(LinearList *,int (*)(ElementType *),int); /*遍历ok*/
int GetLength(LinearList *); /*测长度ok*/
/*----------------------申明的结束----------------------*/
/*------------------子函数-------------------------*/
LinearList * CreateList(void) /*【创建】 */
{
LinearList *p=0; /*定义一个指向新建链表的指针*/
p=(LinearList *) malloc( sizeof ( LinearList ) ) ;
if(!p) return 0 ; /*申请链表存储空间*/
p->head=(ChainNode *)malloc(sizeof(ChainNode));
if(!(p->head))
{
free(p);
return 0;/*申请头节点存储空间*/
}
p->head->next=p->head; /*初始化头节点*/
p->head->prior=p->head;
p->head->data=0; /*双向的链表*/
p->cursor.number=0; /*初始化游标*/
p->cursor.cp=p->head;
return p ; /*返回新建链表指针*/
}
int ClearList(LinearList *lp) /*【清空】 */
{
while( ListDelete(lp,1) ); /*删除第一个节点直到失败为止*/
return 1;
}
void DestroyList(LinearList *lp) /*【销毁】*/
{
ClearList(lp); /* 清空线性表*/
free(lp->head); /* 释放链表存储空间 */
free(lp); /* 释放链节点 */
}
ChainNode * GetAddr(LinearList *lp,int i) /*取节点的地址*/
{
ChainNode *p=lp->cursor.cp ; /* 定义节点型指针p 初始化为游标指针项 */
int j=lp->cursor.number; /* 定义整型变量j 初始化为游标号码项 */
if(i<1)return 0 ; /* 如果i<1返回空 */
if(i==lp->cursor.number)return p ; /* 如果i=游标号码项，返回p （游标指针项） */
if(i>j) /* 如果i>游标号码项，从游标开始向后移动p，直到目的地址，返回p */
{
while(i>j)
{
j++;
p=p->next;
if(p==lp->head) return 0;
}
return p;
}
if(iprior;
if(p==lp->head) return 0;
}
return p;
}
}
/* 注：游标在头节点时：p=lp->cursor.cp=lp->head;*/
int MoveTo(LinearList *lp,int i) /*【移动游标】*/
{
ChainNode *p=GetAddr(lp,i);
if(!p)return 0;
lp->cursor.cp=p;
lp->cursor.number=i;
return 1;
}
int MoveNext(LinearList *lp) /*【后移游标】*/
{
if(lp->cursor.cp->next==lp->head) return 0;
lp->cursor.number++;
lp->cursor.cp=lp->cursor.cp->next;
return 1;
}
int MovePrior(LinearList *lp) /*【前移游标】*/
{
if(lp->cursor.cp->prior==lp->head) return 0;
lp->cursor.number--;
lp->cursor.cp=lp->cursor.cp->prior;
return 1;
}
int MoveBegin(LinearList *lp) /*【设游标至第一个节点】*/
{
if(lp->head->next==lp->head) return 0;
lp->cursor.cp=lp->head->next;
lp->cursor.number=1;
return 1;
}
int MoveEnd(LinearList *lp) /*【设游标至最后一个节点】*/
{
if(lp->head->prior==lp->head) return 0;
lp->cursor.cp=lp->head->prior;/*--头结点的前一个就是最后一个结点--*/
lp->cursor.number=GetLength(lp); /*长度*/
return 1;
}
int GetLength(LinearList *lp)
{
int i;
ChainNode *p;
p=lp->head;
for(i=0;p->next!=lp->head;i++)
p=p->next;
return i;
}
int ListInsert(LinearList *lp,int i,ElementType e)/* 插入元素*/
{
ChainNode *p,*newp;
if(!MoveTo(lp,i)) return 0;
p=lp->cursor.cp;
newp=( ChainNode * )malloc( sizeof ( ChainNode ) );
if(!newp) return 0;
newp->data=e;
p->prior->next=newp;
newp->prior=p->prior;
newp->next=p;
p->prior=newp;
lp->cursor.number=i+1;
return 1;
}
int ListDelete(LinearList *lp,int i) /* 删除元素*/
{
ChainNode *p;
if(!MoveTo(lp,i)) return 0;
p=lp->cursor.cp;
if(p==lp->head) return 0;
lp->cursor.cp=lp->cursor.cp->next;
p->prior->next=p->next;
p->next->prior=p->prior;
free(p);
return 1;
}
int ListInsertCurrent(LinearList *lp,ElementType e)
/* 在当前位置插入元素（在游标指向元素前插入元素，插入后游标指针项不变，号码项++）*/
{
ChainNode *p,*newp;
p=lp->cursor.cp;
newp=( ChainNode * )malloc( sizeof ( ChainNode ) );
if(!newp) return 0;
newp->data=e;
p->prior->next=newp;
newp->prior=p->prior;
newp->next=p;
p->prior=newp;
/* bu bian */
lp->cursor.number++;
return 1;
}
int ListDeleteCurrent(LinearList *lp)
/*删除当前位置的元素（删除游标所指向的元素，删除后游标号码项不变，指针项后移）*/
{
ChainNode *p;
p=lp->cursor.cp;
lp->cursor.cp=lp->cursor.cp->next;
/* shu bu bian */
p->prior->next=p->next;
p->next->prior=p->prior;
free(p);
return 1;
}
int ListAppend(LinearList *lp,ElementType e)/* 追加元素 */
{
ChainNode *newp;
newp=( ChainNode * )malloc( sizeof ( ChainNode ) );
if(!newp) return 0;
newp->data=e;
lp->head->prior->next=newp;
newp->prior=lp->head->prior;
newp->next=lp->head;
lp->head->prior=newp;
return 1;
}
int FindElement(LinearList *lp,int (*v)(ElementType e0,ElementType e1),ElementType e,int f)
/*查找（增加一个参数，对查找方式进行选择，0表示从游标向后找，1表示从游标向前找 2表示从头到尾）*/
{
ChainNode *p=lp->cursor.cp;
int i=0;
if(f==0)
{
do{
p=p->next;
i++;
}while( p!=lp->head && !(*v)(e,p->data));
}
else if(f==1)
{
do{
p=p->prior;
i++;
}while(p!=lp->head && !(*v)(e,p->data));
}
else if(f==2)
{
p=lp->head;
do{
p=p->next;
i++;
}while( (p!=lp->head) && !(*v)(e,p->data));
}
else return 0;
return i;
}
对应 int print (ElementType *ep)
int ListTraverse(LinearList *lp,int (*v) (ElementType * e),int f)
/* 遍历（增加一个参数，对遍历方式进行选择，0表示从游标向后遍历，1表示从游标向前
遍历，2表示从头遍历）*/
{
ChainNode *p;
int i=1;
p=lp->cursor.cp;
if(f==0)
{
do{
p=p->next;
i++;
}while((p!=lp->head) && ( (*v) (&(p->data)) ) );
}
else if(f==1)
{
do{
p=p->prior;
i++;
}while((p!=lp->head) && ( (*v)(&(p->data)) ) );
}
else if(f==2)
{
p=lp->head;
do{
p=p->next;
i++;
}while((p!=lp->head)&&(*v)(&p->data));
}
else return 0;
return i;
}
/*--------------------------子函数结束-------------------------*/