链表

#include //malloc( ) #include // INT ,MAX #include //EOF,NULL #include //atoi( ) #include //eof( )

#include //floor( ),ceil( ),abs( ) #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0

#define INFEASIBLE -1 typedef int Status; typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LNode,*LinkList;

Status InitList(LinkList &L)//建立链表 {

L=(LinkList)malloc(sizeof(LNode)); if (!L) {

printf(\"Init error\\n\"); return ERROR; }

L->next=NULL; return OK; }

Status GetElem(LinkList L,int i,ElemType &e)//当第i个元素存在时，其值赋给e并返回ok，否则返回error {LinkList p;

p = L->next;int j=1; while(p&&jnext;++j; }

if(!p||j>i)return ERROR; e = p->data; return OK; }

int ListLength(LinkList L)//返回链表中元素个数

{LinkList p=L; int i=0;

while(p->next) {i++;

p = p->next; }

return i; }

void output(LinkList L)//输出链表 {LinkList p; p=L->next; while(p)

{printf(\"%d\\p = p->next; } }

Status ListInsert(LinkList &L,int i,ElemType e)//在第i个位置之前插入元素e {

LinkList p=L; int j=0;

while(p&&(jp=p->next; ++j; }

if (!p||j>i-1)return ERROR;

LinkList q=(LinkList)malloc(sizeof(LNode));//生成新结点 q->data=e;//插入链表中 q->next=p->next; p->next=q; return OK; }

Status ListDelete(LinkList &L,int i,ElemType &e)//删除第i个元素，并由e返回值 {

LinkList p=L; int j=0;

while(p->next&&jp=p->next; ++j; }

if(!(p->next)||j>i-1)return ERROR;//删除位置不合理，返回error LinkList q=p->next;//删除并释放结点 e=p->next->data;

p->next=p->next->next; free(q);

return OK; }

Status ListEmpty(LinkList L)//判断链表是否为空 {if(L->next) {

return FALSE; } else {

return TRUE; } }

Status compare(ElemType e1,ElemType e2)//比较e1和e2值 {if(e1==e2)return TRUE; else return FALSE; }

int LocateElem(LinkList L,ElemType e,Status(*compare) (ElemType,ElemType))//返回链表中第一个与e满足compare函数判定关系的元素的位置 {

int i=0;

LinkList p = L->next; while(p) {

i++;

if(compare(p->data,e)) return i; p = p->next; }

return 0; }

int main() {

LinkList L; ElemType e; int i,n;

printf(\"构建空表\\n\"); InitList(L);

printf(\"输入元素-1，21，13，24，8\\n\");

ListInsert(L,1,8); ListInsert(L,1,24); ListInsert(L,1,13); ListInsert(L,1,21); ListInsert(L,1,-1); printf(\"输出链表:\"); output(L);

i=ListLength(L);

printf(\"\\n该链表的长度为:%d\\n\i=ListEmpty(L);

printf(\"该表是否为空表(空表为1，非空为0):%d\\n\ GetElem(L,3,e);

printf(\"链表第三个元素为:%d\\n\LocateElem(L,24,(*compare));

printf(\"元素24的位置为:%d\\n\

printf(\"将0插入链表第四个元素之前\\n\"); ListInsert(L,4,0);

printf(\"输出链表:\"); output(L);

printf(\"\\n删除链表的第五个元素\\n\"); ListDelete(L,5,e) ; printf(\"输出链表:\"); output(L); printf(\"\\n\"); return 0; }