用一组地址任意的存储单元存放线性表中的数据元素。

以元素(数据元素的映象)  +指针(指示后继元素存储位置)  =  结点 (表示数据元素  或  数据元素的映象)

以“结点的序列”表示线性表 称作链表

结点和单链表的 C 语言描述：

 单链表的存储结构定义 ：

 

typedef struct LNode {

ElemType data;// 数据域         struct LNode *next; // 指针域    } LNode, *LinkList;

        LinkList  L；  // L 为单链表的头指针

 

 单链表的基本操作:

       

创建并初始化为空表 Status InitList(LinkList &L){    // TODO (#1#): 创建空表   L=(LinkList )malloc(sizeof(LNode));   if(!L) return ERROR;   L->next=NULL;   return OK;    //-------------------------------------}

将表L置空 Status ClearList(LinkList &L){    // TODO (#1#): 清空表	LinkList p;	while(L->next)	{		p=L->next;		L->next=p->next;		free(p);	}    return OK;    //-------------------------------------}

 

求表L的长度 int ListLength(LinkList L){    // TODO (#1#): 链表求长度	LinkList p = L->next;	int j=0;	while(p)	{		p=p->next;		++j;	}    return j;    //-------------------------------------}

 

取表L中的第i个元素,并用e返回. 操作成功返回OK,失败时返回ERROR Status GetElem(LinkList L, int i, ElemType &e){    // TODO (#1#): 实现取元素GetElem(L,i,&e)    LinkList p;	p=L->next;	int j=0;	while(p&&j
    
     next;		++j;	}	if(!p || j>i)		return ERROR;	e=p->data;    return OK;      //-------------------------------------}
    

在表L中定位元素e首次出现的位置. 操作成功返回位序,失败时返回0 compare(a,b) 为比较函数,匹配时返回true,否则返回false int LocateElem(LinkList L, ElemType e, bool (*compare)(ElemType,ElemType)){    // TODO (#1#): 在表中定位元素e,用compare(a,b)匹配元素    LinkList p; 	int j;    p = L->next; j = 1;    while(p!=NULL) {        if( compare(p->data,e) )  return j;        p=p->next;    }    return 0;    //-------------------------------------}

 

在表L中插入第i个元素e. 操作成功返回OK,失败时返回ERRORStatus ListInsert(LinkList &L, int i, ElemType e){    // TODO (#1#): 在链表中插入元素    LinkList p;	int j=0;    LinkList s;	p=L;	while(p && j
    
     next;		++j;	}	if(!p || j>i-1)      return ERROR;	s=(LinkList)malloc(sizeof(LNode));    s->data=e;	s->next=p->next;	p->next=s;	return OK;    //-------------------------------------}
    

 

删除表L中第i个元素,结果用e返回. 操作成功返回OK,失败时返回ERROR Status ListDelete(LinkList &L, int i, ElemType &e){    // TODO (#1#): 在链表中删除元素   LinkList p,q;	int j=0;	p=L;	while(p->next&&j
    
     next;		++j;	}	if(!(p->next)||j>i-1) return ERROR;	q=p->next;	p->next=q->next;	e=q->data;	free(q);	return OK;    //-------------------------------------}
    

如有需要可下载完整代码：