1.概述：

C语言中的单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。
链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。
如下图所示：

一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接

一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。

链表最基本的结构是在每个节点保存数据和到下一个节点的地址，在最后一个节点保存一个特殊的结束标记，另外在一个固定的位置保存指向第一个节点的指针，有的时候也会同时储存指向最后一个节点的指针。一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。但是也可以提前把一个节点的位置另外保存起来，然后直接访问。当然如果只是访问数据就没必要了，不如在链表上储存指向实际数据的指针。这样一般是为了访问链表中的下一个或者前一个节点。
相对于双向链表，这种普通的，每个节点只有一个指针的链表也叫单向链表，或者单链表，通常用在每次都只会按顺序遍历这个链表的时候（例如图的邻接表，通常都是按固定顺序访问的）。

2.程序实现：

struct LNode { ElemType data; struct LNode *next; }; typedef struct LNode *LinkList; Status InitList(LinkList *L) { *L=(LinkList)malloc(sizeof(struct LNode)); if(!*L) exit(OVERFLOW); (*L)->next=NULL; return OK; } Status DestroyList(LinkList *L) { LinkList q; while(*L) { q=(*L)->next; free(*L); *L=q; } return OK; } Status ClearList(LinkList L) { LinkList p,q; p=L->next; while(p) { q=p->next; free(p); p=q; } L->next=NULL; return OK; } Status ListEmpty(LinkList L) { if(L->next) return FALSE; else return TRUE; } int ListLength(LinkList L) { int i=0; LinkList p=L->next; while(p) { i++; p=p->next; } return i; } Status GetElem(LinkList L,int i,ElemType *e) { int j=1; LinkList p=L->next; while(p&&j<i) { p=p->next; j++; } if(!p||j>i) return ERROR; *e=p->data; return OK; } int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType)) { 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) { LinkList q,p=L->next; while(p->next) { q=p->next; 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) { LinkList p=L->next; while(p->next) { if(p->data==cur_e) { *next_e=p->next->data; return OK; } p=p->next; } return INFEASIBLE; } Status ListInsert(LinkList L,int i,ElemType e) { int j=0; LinkList p=L,s; while(p&&j<i-1) { p=p->next; j++; } if(!p||j>i-1) return ERROR; s=(LinkList)malloc(sizeof(struct LNode)); s->data=e; s->next=p->next; p->next=s; return OK; } Status ListDelete(LinkList L,int i,ElemType *e) { int j=0; LinkList p=L,q; while(p->next&&j<i-1) { 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 ListTraverse(LinkList L,void(*vi)(ElemType)) { LinkList p=L->next; while(p) { vi(p->data); p=p->next; } printf("\n"); return OK; } #include"c1.h" typedef int ElemType; #include"c2-2.h" #include"bo2-2.c" void CreateList(LinkList *L,int n) { int i; LinkList p; *L=(LinkList)malloc(sizeof(struct LNode)); (*L)->next=NULL; printf("请输入%d个数据\n",n); for(i=n;i>0;--i) { p=(LinkList)malloc(sizeof(struct LNode)); scanf("%d",&p->data); p->next=(*L)->next; (*L)->next=p; } } void CreateList2(LinkList *L,int n) { int i; LinkList p,q; *L=(LinkList)malloc(sizeof(struct LNode)); (*L)->next=NULL; q=*L; printf("请输入%d个数据\n",n); for(i=1;i<=n;i++) { p=(LinkList)malloc(sizeof(struct LNode)); scanf("%d",&p->data); q->next=p; q=q->next; } p->next=NULL; } void MergeList(LinkList La,LinkList *Lb,LinkList *Lc) { LinkList pa=La->next,pb=(*Lb)->next,pc; *Lc=pc=La; while(pa&&pb) if(pa->data<=pb->data) { pc->next=pa; pc=pa; pa=pa->next; } else { pc->next=pb; pc=pb; pb=pb->next; } pc->next=pa?pa:pb; free(*Lb); Lb=NULL; } void visit(ElemType c) { printf("%d ",c); } void main() { int n=5; LinkList La,Lb,Lc; printf("按非递减顺序, "); CreateList2(&La,n); printf("La="); ListTraverse(La,visit); printf("按非递增顺序, "); CreateList(&Lb,n); printf("Lb="); ListTraverse(Lb,visit); MergeList(La,&Lb,&Lc); printf("Lc="); ListTraverse(Lc,visit); }