선형 표 의 단일 체인 표 저장 구조

//2.112.h
/* c1.h (   ) */
#include<string.h>
#include<ctype.h>
#include<malloc.h> /* malloc()  */
#include<limits.h> /* INT_MAX  */
#include<stdio.h> /* EOF(=^Z F6),NULL */
#include<stdlib.h> /* atoi() */
#include<io.h> /* eof() */
#include<math.h> /* floor(),ceil(),abs() */
#include<process.h> /* exit() */
/*          */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
/* #define OVERFLOW -2    math.h    OVERFLOW   3,      */
typedef int Status; /* Status      ,           ， OK  */
typedef int Boolean; /* Boolean     ,   TRUE FALSE */

//2.113.h
/* c2-2.h             */
struct LNode
{
	ElemType data;
	struct LNode *next;
};
typedef struct LNode *LinkList; /*      LinkList    */

//2.114.h
/* bo2-2.c       (     c2-2.h  )     (12 ) */
#include"2.112.h"
typedef int ElemType;
#include"2.113.h"

Status InitList(LinkList *L)
{ /*     ：         L */
	*L = (LinkList)malloc(sizeof(struct LNode)); /*      ,  L       */
	if (!*L) /*        */
		exit(OVERFLOW);
	(*L)->next = NULL; /*       */
	return OK;
}

Status DestroyList(LinkList *L)
{ /*     ：   L   。    ：     L */
	LinkList q;
	while (*L)
	{
		q = (*L)->next;
		free(*L);
		*L = q;
	}
	return OK;
}

Status ClearList(LinkList L) /*    L */
{ /*     ：   L   。    ： L      */
	LinkList p, q;
	p = L->next; /* p        */
	while (p) /*      */
	{
		q = p->next;
		free(p);
		p = q;
	}
	L->next = NULL; /*          */
	return OK;
}

Status ListEmpty(LinkList L)
{ /*     ：   L   。    ： L   ，   TRUE，    FALSE */
	if (L->next) /*    */
		return FALSE;
	else
		return TRUE;
}

int ListLength(LinkList L)
{ /*     ：   L   。    ：  L        */
	int i = 0;
	LinkList p = L->next; /* p        */
	while (p) /*      */
	{
		i++;
		p = p->next;
	}
	return i;
}

Status GetElem(LinkList L, int i, ElemType *e) /*   2.8 */
{ /* L             。  i      ,    e   OK,    ERROR */
	int j = 1; /* j     */
	LinkList p = L->next; /* p        */
	while (p&&j<i) /*        ,  p   i    p   */
	{
		p = p->next;
		j++;
	}
	if (!p || j>i) /*  i       */
		return ERROR;
	*e = p->data; /*   i    */
	return OK;
}

int LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType))
{ /*     :    L   ,compare()         (   1,   0) */
	/*     :   L  1  e    compare()        。 */
	/*                      ,     0 */
	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)
{ /*     :    L    */
	/*     :  cur_e L     ,      ,  pre_e      , */
	/*             OK;      ,pre_e   ,  INFEASIBLE */
	LinkList q, p = L->next; /* p        */
	while (p->next) /* p        */
	{
		q = p->next; /* q p    */
		if (q->data == cur_e)
		{
			*pre_e = p->data;
			return OK;
		}
		p = q; /* p    */
	}
	return INFEASIBLE;
}

Status NextElem(LinkList L, ElemType cur_e, ElemType *next_e)
{ /*     ：   L    */
	/*     ： cur_e L     ，       ，  next_e      ， */
	/*             OK;      ，next_e   ，  INFEASIBLE */
	LinkList p = L->next; /* p        */
	while (p->next) /* p        */
	{
		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) /*   2.9。   L */
{ /*            L  i         e */
	int j = 0;
	LinkList p = L, s;
	while (p&&j<i - 1) /*    i-1    */
	{
		p = p->next;
		j++;
	}
	if (!p || j>i - 1) /* i  1       */
		return ERROR;
	s = (LinkList)malloc(sizeof(struct LNode)); /*       */
	s->data = e; /*   L  */
	s->next = p->next;
	p->next = s;
	return OK;
}

Status ListDelete(LinkList L, int i, ElemType *e) /*   2.10。   L */
{ /*            L ，   i   ,  e     */
	int j = 0;
	LinkList p = L, q;
	while (p->next&&j<i - 1) /*    i   ,  p      */
	{
		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))
/* vi      ElemType， bo2-1.c          ElemType&   */
{ /*     ：   L    */
	/*     :   L           vi()。  vi()  ,      */
	LinkList p = L->next;
	while (p)
	{
		vi(p->data);
		p = p->next;
	}
	printf("
");
	return OK;
}

//2.111
/* algo2-5.c     2.11、2.12    */
#include"2.114.h"

void CreateList(LinkList *L, int n) /*   2.11 */
{ /*    (    )  n     ，             L */
	int i;
	LinkList p;
	*L = (LinkList)malloc(sizeof(struct LNode));
	(*L)->next = NULL; /*               */
	printf("   %d   
", n);
	for (i = n; i>0; --i)
	{
		p = (LinkList)malloc(sizeof(struct LNode)); /*       */
		scanf_s("%d", &p->data); /*       */
		p->next = (*L)->next; /*       */
		(*L)->next = p;
	}
}

void CreateList2(LinkList *L, int n)
{ /*    (    )  n     ，              */
	int i;
	LinkList p, q;
	*L = (LinkList)malloc(sizeof(struct LNode)); /*       */
	(*L)->next = NULL;
	q = *L;
	printf("   %d   
", n);
	for (i = 1; i <= n; i++)
	{
		p = (LinkList)malloc(sizeof(struct LNode));
		scanf_s("%d", &p->data);
		q->next = p;
		q = q->next;
	}
//	p->next = NULL;
}


void MergeList(LinkList La, LinkList *Lb, LinkList *Lc)/*   2.12 */
{ /*        La Lb          。 */
	/*   La Lb         Lc，Lc            */
	LinkList pa = La->next, pb = (*Lb)->next, pc;
	*Lc = pc = La; /*  La      Lc     */
	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     */
	Lb = NULL;
}

void visit(ElemType c) /* ListTraverse()     (     ) */
{
	printf("%d ", c);
}

void main()
{
	int n = 5;
	LinkList La, Lb, Lc;
	printf("      , ");
	CreateList2(&La, n); /*      n      */
	printf("La="); /*     La    */
	ListTraverse(La, visit);
	printf("      , ");
	CreateList(&Lb, n); /*      n      */
	printf("Lb="); /*     Lb    */
	ListTraverse(Lb, visit);
	MergeList(La, &Lb, &Lc); /*         La Lb,    Lc */
	printf("Lc="); /*     Lc    */
	ListTraverse(Lc, visit);
}