/*========帶頭節點的線性鏈表類型=========*/
typedef char ElemType//結點類型
typedef struct LNode
{char data;struct LNode *next;
}*Link,*Position;//鏈表類型
typedef struct
{Link head,tail;int len;
}LinkList;/*======================================================*/
/*=======一些在其他函數定義中會調用的函數===============*/
/*======================================================*//*---compare---比較兩個元素的大小關系*/
int Compare(char a,char b)
{  return a-b;
}/*---visit---*/
int Visit(Link p)
{if(...)return 1;elsereturn 0;}/*---length---求鏈的長度*/
int Length(Link s)
{ int i=0;Link p=NULL;p=s;while(p->next!=NULL){p=p->next;i++;}return i;
}/*---print---在屏幕上輸出鏈表的所有元素*/
void Print(LinkList L)
{     Link p=NULL;p=L.head;if(!p->next){printf("\nThe LinkList is empty.\n\n");return ;}printf("The List:");while(p){printf("%c-",p->data);p=p->next;}
}/*======================================================*/
/*==========對帶頭結點的單鏈線性表進行操作的函數的定義==*/
/*======================================================*//*---分配由p指向的結點并賦值為e---*/
Position MakeNode(ElemType e)
{       Link p=NULL;p=(Link)malloc(sizeof(struct LNode));if(p){p->data=e;p->next=NULL;}else return;return p;
}/*---釋放p所指向的結點-*/
void FreeNode(Link p)
{          free(p);
}/*---構造一個由L指向的空的線性表-*/
void InitList(LinkList *L)
{      L->head=MakeNode('L');//生成頭結點L->head->next=NULL;/*不是l->head=NULL*/L->tail=L->head;L->len=0;
}/*----------銷毀由L指向的線性表---------*/
void DestroyList(LinkList *L)
{   Link p;p=(*L).tail;while(p!=(*L).head){p=PriorPos(*L,p);FreeNode(p->next);}FreeNode((*L).head);
}/*將線性表L置為空表，并釋放原鏈表的頭結點*/
void ClearList(LinkList *L)
{     Link p;p=(*L).tail;while(p!=(*L).head){p=PriorPos(*L,p);FreeNode(p->next);}FreeNode((*L).head);
}/*---將s指向的結點插入線性鏈表的第一個結點之前-*/
void InsFirst(LinkList *L,Link s)
{    s->next=L->head->next;if(!L->head->next) L->tail=s;       /*當向一個空的線性表執行該操作時*/L->head->next=s;L->len++;
}/*---刪除表中第一個結點并以q返回-*/
void DelFirst(LinkList *L,Link q)
{    if(!L->head->next){printf("\nThe LinkList is empty,can not delete..\n");return 0;}q=L->head->next;L->head->next=L->head->next->next;
}/*---將指針s所的一串結點鏈接在線性表L的最后一個結點-*/
void Append(LinkList *L,Link s)
{  Link q;q=L->head;if(!L->tail){/*考慮到鏈表為空的情況*/L->head->next=s;while(q->next) q=q->next;/*尾結點的處理*/L->tail=q;}L->tail->next=q=s;while(q->next) q=q->next;/*不能忘了對尾結點的處理*/L->tail=q;L->len+=Length(s);
}/*---刪除線性表l中的尾結點-*/
void Remove(LinkList *L,Link q)
{   if(!L->tail){printf("\nthe LinkList is empty,can not remonde..\n");return 0;}q=L->tail;                      L->tail=PriorPos(*L,q);L->tail->next=NULL;
}/*---將s所指向結點插入在p所指結點之前-*/
void InsBefore(LinkList *L,Link p,Link s)
{   Link q;q=PriorPos(*L,p);s->next=p;q->next=s;
}/*---將s所指向結點插入在p所指結點之后-*/
void InsAfter(LinkList *L,Link p,Link s)
{    s->next=p->next;p->next=s;
}/*---用e更新p所指向的當前結點-*/
void SetCurElem(Link p,ElemType e)
{         p->data=e;
}/*---返回p所指結點中元素的值-*/
ElemType GetCurElem(Link p)
{        return p->data;
}int Listempty(LinkList L)
{         /*---若線性表為空表則返回1，否則返回0-*/if(L.head==L.tail) return 1;return 0;
}int Listlength(LinkList L)
{      /*---返回線性表中元素個數-*/return L.len;
}Position GetHead(LinkList L)
{     /*---返回線性表l中頭結點的位置-*/return L.head;
}Position GetLast(LinkList L)
{      /*-----返回線性表l中最后一個結點的位置-------*/return L.tail;
}/*---返回p所指結點的直接前驅的位置-*/
Position PriorPos(LinkList L,Link p)
{    Link q;q=L.head;if(q->next==p) return 0;while(q->next!=p)   q=q->next;return q;
}/*-----返回p所指結點的直接后繼的位置-------*/
Position NextPos(Link p)
{     Link q;q=p->next;return q;
}/*-----用p返回線性表l中第i個結點的位置，并返回ok-------*/
void LocatePos(LinkList L,int i,Link p)
{    p=L.head;if(i<=0||i>Listlength(L))   return 0;while(i){p=p->next;i--;}
}/*----返回表中第一個與e滿足一定函數關系的結點次序位置----*/
int LocatElem(LinkList L,ElemType e)
{     int i=0;Link p;p=L.head->next;while(compare(p->data,e)&&p){p=p->next;++i;}if(!p){/*考慮到查找不到指定元素的情況*/printf("\nthere's no '%c' in this LinkList.",e);return 0;}return i;
}/*----用一個函數遍歷表中所有結點-------*/
void ListTraverse(LinkList L)
{         Link p;p=L.head;while(!visit(p))  p=p->next;   
}

將單鏈線性表La和Lb的元素按值非遞減排列

Status MergeList_L(NLinkList &La, NLinkList &Lb, NLinkList &Lc, int (*compare)(ElemType, ElemType)) 
{  // 算法2.21// 已知單鏈線性表La和Lb的元素按值非遞減排列。// 歸并La和Lb得到新的單鏈線性表Lc，Lc的元素也按值非遞減排列。NLink ha, hb;Position pa, pb, q;ElemType a, b;if (!InitList(Lc)) return ERROR;  // 存儲空間分配失敗ha = GetHead(La);      // ha和hb分別指向La和Lb的頭結點hb = GetHead(Lb);pa = NextPos(La, ha);  // pa和pb分別指向La和Lb中當前結點pb = NextPos(Lb, hb);while (pa && pb) {     // La和Lb均非空a = GetCurElem(pa);  // a和b為兩表中當前比較元素b = GetCurElem(pb);if ((*compare)(a, b)<=0) {  // a≤bDelFirst(ha, q);  Append(Lc, q);  pa = NextPos(La, pa);  } else{   // a＞bDelFirst(hb, q);  Append(Lc, q);  pb = NextPos(Lb, pb);  }} // whileif (pa) Append(Lc, pa);        // 鏈接La中剩余結點elseAppend(Lc, pb);        // 鏈接Lb中剩余結點FreeNode(ha);   FreeNode(hb);              // 釋放La和Lb的頭結點return OK;
} // MergeList_L