C通用范例源代码之数据结构之链表

1、C 通用范例源代码之数据结构之链表范例 1-32 头插法建立单链表工相关函数：createlist函数#include typedef char datatype;typedef struct nodedatatype data;struct node *next; listnode;typedef listnode *linklist;listnode *p;linklist createlist(void)char ch;linklist head;listnode *p;head=NULL;/* 初始化为空 */ch=getchar( );while (ch!=n) p=(listnod

2、e*)malloc(sizeof(listnode);/* 分配空间 */ p-data=ch;/* 数据域赋值 */ p-next=head;/* 指定后继指针 */ head=p;/*head 指针指定到新插入的结点上 */ ch=getchar( );return (head);main()linklist newlist=createlist();doprintf(%cn,newlist-data);newlist=newlist-next;while(newlist!=NULL);printf(n);范例 1-33 限制链表长度建立长单链表工相关函数：createlist函数#inc

3、lude #define N 4typedef char datatype;typedef struct node datatype data;structnode *next; listnode;typedeflistnode *linklistnode*p;linklistcreatelist(int n)int i;linklist head; listnode *p; head=NULL;for(i=n;iO;-i)/*指定长度为n,插入次数受限制*/ p=(listnode*)malloc(sizeof(listnode); scanf(%c,&p-data); p-next=hea

4、d;head=p; return(head);main()linklist newlist=createlist(N);do printf(%c,newlist-data); newlist=newlist-next;while(newlist!=NULL); printf(n);范例 1-34 尾插法建立单链表工相关函数：createlist函数#include #define N 4 typedef char datatype;typedef struct node datatype data;structnode *next; listnode;typedeflistnode *link

5、listlistnode*p;linklistcreater()charch;linklist head;listnode *p,*r;head=NULL;r=NULL;/*r 为尾指针 */ while(ch=getchar()!=n) p=(listnode *)malloc(sizeof(listnode); p-data=ch;if(head=NULL)head=p;/*head 指向第一个插入结点 */ elser-next=p;/* 插入到链表尾部 */ r=p;/*r 指向最新结点，即最后结点 */ if (r!=NULL)r-next=NULL;/* 链表尾部结点的后继指针指定

6、为空 */ return(head); main()linklist newlist=creater();do printf(%c,newlist-data); newlist=newlist-next;while(newlist!=NULL); printf(n);范例 1-35 按序号查找单链表 工相关函数：get node函数#include typedef char datatype;typedef struct nodedatatype data;struct node *next; listnode;typedef listnode *linklist; listnode *p;l

7、inklist createlist(void)char ch;linklist head; listnode *p;head=NULL;/* 初始化为空 */ ch=getchar( );while (ch!=n) p=(listnode*)malloc(sizeof(listnode);/* 分配空间 */ p-data=ch;/* 数据域赋值 */p-next=head;/* 指定后继指针 */ head=p;/*head 指针指定到新插入的结点上 */ ch=getchar( ); return (head);listnode * getnode(linklist head,int i

8、)int j; listnode * p; p=head;j=0;while(p-next & jnext; j+; if (i=j) printf(%cn,p-data); return p; else return NULL;main()linklist list; listnode * node;int i=0;list=createlist(); node=getnode(list,i);范例 1-36 按值查找单链表工相关函数：locate node函数#include typedef char datatype;typedef struct node datatype data;

9、struct node *next; listnode;typedef listnode *linklist;listnode *p;linklist createlist(void)char ch;linklist head;listnode *p;head=NULL;/* 初始化为空 */ch=getchar( );while (ch!=n) p=(listnode*)malloc(sizeof(listnode);/* 分配空间 */ p-data=ch;/* 数据域赋值 */ p-next=head;/* 指定后继指针 */ head=p;/*head 指针指定到新插入的结点上 */

10、ch=getchar( );return (head);listnode * locatenode(linklist head,char key)listnode * p=head;while( p-next& p-data!=key)p=p-next;if(p!=NULL)printf(%cn,p-data);return p;main()linklist list;listnode * node;char key=c;list=createlist();node=locatenode(list,key);范例 1-37 链表的插入工相关函数：insertnode函数#include typ

11、edef char datatype;typedef struct nodedatatype data;struct node *next; listnode;typedef listnode *linklist;listnode *p;linklist createlist(void)char ch;linklist head;listnode *p;head=NULL;/* 初始化为空 */ch=getchar( );while (ch!=n) p=(listnode*)malloc(sizeof(listnode);/* 分配空间 */ p-data=ch;/* 数据域赋值 */ p-n

12、ext=head;/* 指定后继指针 */ head=p;/*head 指针指定到新插入的结点上 */ ch=getchar( );return (head);void insertnode(linklist head,char x,int i)int j=0;listnode * p,*s;p=head;while(p&jnext;+j;if(!p|ji-1)exit(1);s=(linklist)malloc(sizeof(listnode);s-data=x;s-next=p-next;p-next=s;main()linklist list;int i=1;char x=c;list=

13、createlist();insertnode(list,x,i);doprintf(%c,list-data);list=list-next;while(list!=NULL);printf(n);范例 1-38 链表的删除工相关函数：deletelist函数#include typedef char datatype;typedef struct nodedatatype data;struct node *next; listnode;typedef listnode *linklist;listnode *p;linklist createlist(void)char ch;linkl

14、ist head;listnode *p;head=NULL;/* 初始化为空 */ch=getchar( );while (ch!=n) p=(listnode*)malloc(sizeof(listnode);/* 分配空间 */ p-data=ch;/* 数据域赋值 */ p-next=head;/* 指定后继指针 */ head=p;/*head 指针指定到新插入的结点上 */ ch=getchar( );return (head);void deletelist(linklist head,int i)int j=0;listnode * p,*r;p=head;while(p&jn

15、ext;+j;if(!p-next|ji-1)exit(1);r=p-next;p-next=r-next;free(r) ;main()linklist list;int i=1;list=createlist();deletelist(list,i);doprintf(%c,list-data);list=list-next;while(list!=NULL);printf(n);范例 1-39 归并两个单链表工相关函数：con cate nate函数#include typedef char datatype;typedef struct nodedatatype data;struct

16、 node *next; listnode;typedef listnode *linklist;listnode *p;linklist createlist(void)char ch;linklist head;listnode *p;head=NULL;/* 初始化为空 */ch=getchar( );while (ch!=n) p=(listnode*)malloc(sizeof(listnode);/* 分配空间 */ p-data=ch;/* 数据域赋值 */ p-next=head;/* 指定后继指针 */ head=p;/*head 指针指定到新插入的结点上 */ ch=get

17、char( );return (head);linklist concatenate(linklist list1,linklist list2)listnode *temp;if (list1=NULL)return list2;else if (list2!=NULL) for ( temp =list1; temp-next; temp = temp-next ); /* 遍历到 list1 的末尾 */ temp-next=list2;/* 将 list2 链接到 list1 末尾 */return list1;main()linklist list1,list2,list3;list

18、1=createlist();list2=createlist(); list3=concatenate(list1,list2);doprintf(%c,list3-data);list3=list3-next;while(list3!=NULL);printf(n);范例 1-40 动态堆栈工相关函数：push函数Pop函数#include stdio.htypedefchar datatype;typedefstruct nodedatatype data;struct node *next; stack;stack * creat(void)char ch;stack * head;s

19、tack *p;head=NULL;/* 初始化为空 */ch=getchar( );while (ch!=n) p=(stack*)malloc(sizeof(stack);/* 分配空间 */ p-data=ch;/* 数据域赋值 */ p-next=head;/* 指定后继指针 */ head=p;/*head 指针指定到新插入的结点上 */ ch=getchar( );return (head);void MakeNull(stack *s)/* 使栈 s 为空 */stack *p=s;while(s!=NULL)s=s-next;free(p);/* 释放空间 */p=s;data

20、type Top(stack *s)if(Empty(s)/*s 为空栈，直接跳出，提示出错信息 */ printf(The stack is empty.);elsereturn s-data;void Pop(stack *s)stack *p;if(Empty(s) /*s 为空栈，直接跳出，提示出错信息 */ printf(The stack is empty.);elsep=s;s=s-next;free(p);/* 释放栈顶空间 */void Push(stack *s,datatype x)stack *p;p=(stack*)malloc(sizeof(stack);p-dat

21、a=x;p-next=s;s=p;int Empty(stack *s)return(s=NULL);void main()stack* m_stack=creat();char m_top;if(!Empty(m_stack)m_top=Top(m_stack);Pop(m_stack);elsePush(m_stack,a);MakeNull(m_stack);范例 1-41 动态队列工 相关函数： Enqueue函数#include stdio.htypedef char datatype;typedef struct nodedatatype data;struct node *nex

22、t; position;typedef struct queueposition *front;position *rear;queuetype;/* 使队列为空： */void MakeNull(queuetype * q)q-rear=q-front;while(q-front!=NULL) q-front=q-front-next; free(q-rear);/* 释放空间 */ q-rear=q-front;q-front=(position*)malloc(sizeof(position);q-front-next=NULL;q-rear=q-front;/* 取队列的队头元素： *

23、/datatype Front(queuetype *q)if(Empty(q)printf(The queue is empty!);else return(q-front-next-data);/* 删除队列头元素： */void dequeue(queuetype * q)position* p;if(Empty(q)printf(The queue is empty!);elsep=q-front; q-front=q-front-next; free(p);/* 在队列中加入新元素： */void Enqueue(datatype x,queuetype * q)position*

24、p; p=(position*)malloc(sizeof(position); p-data=x;p-next=NULL; q-rear-next=p; q-rear=p;/* 判断是否为空队列： */int Empty(queuetype * q)return (q-front=q-rear);void main()queuetype * m_q;char m_top;m_q=(queuetype *)malloc(sizeof(queuetype); m_q-front=m_q-rear=(position*)malloc(sizeof(position); m_q-rear-next=

25、NULL;if(!Empty(m_q)m_top=Front(m_q); dequeue(m_q);elseEnqueue(c,m_q);MakeNull(m_q);范例 1-42 初始化单循环链表工相关函数：ListLe ngth_CL 函数#include /* EOF(=AZ 或 F6),NULL */#include /* floor(),ceil(),abs() */#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0OK 等 */typedef int Status; /* Status 是函数的类型 ,其值是函数结果状态

26、代码，如 typedef int ElemType;/* c2-2.h 线性表的单链表存储结构 */struct LNodeElemType data;struct LNode *next;typedef struct LNode *LinkList; /* 另一种定义 LinkList 的方法 */Status InitList_CL(LinkList *L) /* 操作结果：构造一个空的线性表 L */*L=(LinkList)malloc(sizeof(struct LNode); /* 产生头结点 ,并使 L 指向此头结点 */ if(!*L) /* 存储分配失败 */exit(OVE

27、RFLOW);(*L)-next=*L; /* 指针域指向头结点 */return OK;Status ListEmpty_CL(LinkList L)FALSE */ /* 初始条件：线性表 L 已存在。操作结果：若 L 为空表，则返回 TRUE ，否则返回 if(L-next=L) /* 空 */return TRUE;elsereturn FALSE;int ListLength_CL(LinkList L) /* 初始条件： L 已存在。操作结果：返回 L 中数据元素个数 */int i=0;LinkList p=L-next; /* p 指向头结点 */while(p!=L) /*

28、没到表尾 */i+;p=p-next;return i;Status GetElem_CL(LinkList L,int i,ElemType *e) /*当第i个元素存在时，其值赋给e并返回0K,否则返回ERROR */int j=1; /* 初始化 ,j 为计数器 */LinkList p=L-next-next; /* p 指向第一个结点 */ if(iListLength_CL(L) /* 第 i 个元素不存在 */return ERROR;while(jnext;j+;*e=p-data; /* 取第 i 个元素 */return OK;Status ListInsert_CL(Li

29、nkList *L,int i,ElemType e) /* 改变 L */ /* 在 L 的第 i 个位置之前插入元素 e */LinkList p=(*L)-next,s; /* p 指向头结点 */int j=0;if(iListLength_CL(*L)+1)/* 无法在第 i 个元素之前插入*/return ERROR;while(jnext;j+;s=(LinkList)malloc(sizeof(struct LNode); /* 生成新结点 */s-data=e; /* 插入 L 中 */s-next=p-next;p-next=s;if(p=*L) /* 改变尾结点 */*L

30、=s;return OK;Status ListTraverse_CL(LinkList L,void(*vi)(ElemType) /* 初始条件 :L 已存在。操作结果 :依次对 L 的每个数据元素调用函数 vi() 。一旦 vi() 失败 ,则操作失败 */ LinkList p=L-next-next;while(p!=L-next)vi(p-data);p=p-next;printf(n);return OK;void visit(ElemType c)printf(%d ,c);void main()LinkList L;ElemType e;int j;Status i;i=In

31、itList_CL(&L); /* 初始化单循环链表 L */printf( 初始化单循环链表 L i=%d (1: 初始化成功 )n,i);i=ListEmpty_CL(L);printf(L 是否空 i=%d(1: 空 0:否 )n,i);ListInsert_CL(&L,1,3); /* 在 L 中依次插入 3,5 */ListInsert_CL(&L,2,5);i=GetElem_CL(L,1,&e);j=ListLength_CL(L);printf(L中数据元素个数=%d,第1个元素的值为d。n,j,e);printf(L 中的数据元素依次为： );ListTraverse_CL(

32、L,visit);范例 1-43 查询元素的前驱和后继工相关函数：PriorElem_CL 函数 NextElem_CL函数#include /* EOF(=AZ 或 F6),NULL */#include /* floor(),ceil(),abs() */#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0typedef int Status; /* Status 是函数的类型 ,其值是函数结果状态代码，如 OK 等 */ typedef int ElemType;struct LNodeElemType data;struct

33、LNode *next;typedef struct LNode *LinkList; /* 另一种定义 LinkList 的方法 */Status InitList_CL(LinkList *L) /* 操作结果：构造一个空的线性表 L */*L=(LinkList)malloc(sizeof(struct LNode); /* 产生头结点 ,并使 L 指向此头结点 */ if(!*L) /* 存储分配失败 */exit(OVERFLOW);(*L)-next=*L; /* 指针域指向头结点 */return OK;Status ListEmpty_CL(LinkList L)FALSE *

34、/ /* 初始条件：线性表 L 已存在。操作结果：若 L 为空表，则返回 TRUE ，否则返回 if(L-next=L) /* 空 */return TRUE;elsereturn FALSE;int ListLength_CL(LinkList L) /* 初始条件： L 已存在。操作结果：返回 L 中数据元素个数 */int i=0;LinkList p=L-next; /* p 指向头结点 */while(p!=L) /* 没到表尾 */i+;p=p-next;return i;Status GetElem_CL(LinkList L,int i,ElemType *e) /*当第i个元

35、素存在时，其值赋给e并返回0K,否则返回ERROR */int j=1; /* 初始化 ,j 为计数器 */LinkList p=L-next-next; /* p 指向第一个结点 */ if(iListLength_CL(L) /* 第 i 个元素不存在 */ return ERROR;while(jnext;j+;*e=p-data; /* 取第 i 个元素 */return OK;Status ListInsert_CL(LinkList *L,int i,ElemType e) /*改变 L */ /* 在 L 的第 i 个位置之前插入元素 e */LinkList p=(*L)-ne

36、xt,s; /* p 指向头结点 */int j=0;if(iListLength_CL(*L)+1) /* 无法在第 i 个元素之前插入 */ return ERROR;while(jnext;j+;s=(LinkList)malloc(sizeof(struct LNode); /*生成新结点 */s-data=e; /* 插入 L 中 */s-next=p-next;p-next=s;if(p=*L) /* 改变尾结点 */*L=s;return OK;Status PriorElem_CL(LinkList L,ElemType cur_e,ElemType *pre_e) /* 初始

37、条件：线性表 L 已存在 */* 操作结果：若 cur_e 是 L 的数据元素，且不是第一个，则用 pre_e 返回它的前驱， */ /* 否则操作失败， pre_e 无定义 */LinkList q,p=L-next-next; /* p 指向第一个结点 */q=p-next;while(q!=L-next) /* p 没到表尾 */ if(q-data=cur_e) *pre_e=p-data;return TRUE;p=q;q=q-next;return FALSE;Status NextElem_CL(LinkList L,ElemType cur_e,ElemType *next_e

38、) /* 初始条件：线性表 L 已存在 */* 操作结果：若 cur_e 是 L 的数据元素 ,且不是最后一个 ,则用 next_e 返回它的后继， */* 否则操作失败， next_e 无定义 */LinkList p=L-next-next; /* p 指向第一个结点 */while(p!=L) /* p 没到表尾 */if(p-data=cur_e)*next_e=p-next-data;return TRUE;p=p-next;return FALSE;void visit(ElemType c)printf(%d ,c);void main()LinkList L;ElemType

39、e;int j;Status i;i=InitList_CL(&L); /* 初始化单循环链表 L */printf( 初始化单循环链表 L i=%d (1: 初始化成功 )n,i);i=ListEmpty_CL(L);printf(L 是否空 i=%d(1: 空 0:否 )n,i);ListInsert_CL(&L,1,3); /* 在 L 中依次插入 3,5 */ListInsert_CL(&L,2,5);printf( 依次插入元素 3 和 5n);PriorElem_CL(L,5,&e); /* 求元素 5 的前驱 */printf(5 前面的元素的值为 %d。 n,e);NextEl

40、em_CL(L,3,&e); /* 求元素 3 的后继 */printf(3 后面的元素的值为 %d。 n,e);范例 1-44 单循环链表中元素的删除工相关函数：ListDelete_CL函数#include /* EOF(=AZ 或 F6),NULL */#include /* floor(),ceil(),abs() */* 函数结果状态代码 */#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0/* #define OVERFLOW -2 因为在 math.h 中已定义 OVERFLOW 的值为 3,故去掉此行 */ typ

41、edef int Status; /* Status 是函数的类型 ,其值是函数结果状态代码，如OK 等 */typedef int Boolean; /* Boolean 是布尔类型 ,其值是 TRUE 或 FALSE */typedef int ElemType;struct LNodeElemType data;struct LNode *next;typedef struct LNode *LinkList; /* 另一种定义 LinkList 的方法 */Status InitList_CL(LinkList *L) /* 操作结果：构造一个空的线性表 L */*L=(LinkLis

42、t)malloc(sizeof(struct LNode); /* 产生头结点 ,并使 L 指向此头结点 */ if(!*L) /* 存储分配失败 */exit(OVERFLOW);(*L)-next=*L; /* 指针域指向头结点 */return OK;int ListLength_CL(LinkList L) /* 初始条件： L 已存在。操作结果：返回 L 中数据元素个数 */int i=0;LinkList p=L-next; /* p 指向头结点 */while(p!=L) /* 没到表尾 */i+;p=p-next;return i;int LocateElem_CL(LinkL

43、ist L,ElemType e,Status(*compare)(ElemType,ElemType) /* 初始条件：线性表 L 已存在， compare() 是数据元素判定函数*/*操作结果：返回L中第1个与e满足关系compare。的数据元素的位序。*/*若这样的数据元素不存在，则返回值为 0 */int i=0;LinkList p=L-next-next; /* p 指向第一个结点 */ while(p!=L-next)i+;if(compare(p-data,e) /* 满足关系 */return i; p=p-next; return 0;Status ListInsert_C

44、L(LinkList *L,int i,ElemType e) /*改变 L */ /* 在 L 的第 i 个位置之前插入元素 e */LinkList p=(*L)-next,s; /* p 指向头结点 */int j=0;if(iListLength_CL(*L)+1) /* 无法在第 i 个元素之前插入 */ return ERROR;while(jnext;j+;s=(LinkList)malloc(sizeof(struct LNode); /*生成新结点 */s-data=e; /* 插入 L 中 */s-next=p-next;p-next=s;if(p=*L) /* 改变尾结点

45、 */*L=s;return OK;Status ListDelete_CL(LinkList *L,int i,ElemType *e) /*改变 L */ /* 删除 L 的第 i 个元素 ,并由 e 返回其值 */LinkList p=(*L)-next,q; /* p 指向头结点 */int j=0;if(iListLength_CL(*L) /* 第 i 个元素不存在 */ return ERROR;while(jnext;j+;q=p-next; /* q 指向待删除结点 */p-next=q-next;*e=q-data;if(*L=q) /* 删除的是表尾元素 */*L=p;f

46、ree(q); /* 释放待删除结点 */return OK;Status ListTraverse_CL(LinkList L,void(*vi)(ElemType) /* 初始条件 :L 已存在。操作结果 :依次对 L 的每个数据元素调用函数 vi() 。一旦 vi() 失败 ,则操作失败 */ LinkList p=L-next-next;while(p!=L-next)vi(p-data);p=p-next;printf(n);return OK;Status compare(ElemType c1,ElemType c2)if(c1=c2)return TRUE;elsereturn

47、 FALSE;void visit(ElemType c)printf(%d ,c);void main()LinkList L;ElemType e;int j;Status i;i=InitList_CL(&L); /* 初始化单循环链表 L */printf( 依次在单循环链表中插入 3,5n);ListInsert_CL(&L,1,3); /* 在 L 中依次插入 3,5 */ListInsert_CL(&L,2,5); j=LocateElem_CL(L,5,compare); if(j) printf(L 的第 %d 个元素为 5。 n,j);elseprintf( 不存在值为 5

48、 的元素 n); i=ListDelete_CL(&L,2,&e);printf( 删除 L 的第 2 个元素： n);if(i),e);printf(”删除的元素值为d,现在L中的数据元素依次为: ListTraverse_CL(L,visit);elseprintf( 删除不成功！ n);范例 1-45 单循环链表的清除和销毁工相关函数：DestroyList函数#include /* EOF(=AZ 或 F6),NULL */#include /* floor(),ceil(),abs() */* 函数结果状态代码 */#define TRUE 1#define FALSE 0#defi

49、ne OK 1#define ERROR 0typedef int Status; /* Status 是函数的类型 ,其值是函数结果状态代码，如 OK 等 */ typedef int ElemType;struct LNodeElemType data;struct LNode *next;typedef struct LNode *LinkList; /* 另一种定义 LinkList 的方法 */Status InitList_CL(LinkList *L) /* 操作结果：构造一个空的线性表 L */*L=(LinkList)malloc(sizeof(struct LNode);

50、/* 产生头结点 ,并使 L 指向此头结点 */ if(!*L) /* 存储分配失败 */exit(OVERFLOW);(*L)-next=*L; /* 指针域指向头结点 */return OK;Status DestroyList_CL(LinkList *L) /* 操作结果：销毁线性表 L */LinkList q,p=(*L)-next; /* p 指向头结点 */while(p!=*L) /* 没到表尾 */q=p-next;free(p);p=q;free(*L);*L=NULL;return OK;Status ClearList_CL(LinkList *L) /* 改变 L */ /* 初始条件：线性表 L 已存在。操作结果：将 L 重置为空表 */LinkList p,q;*L=(*L)-next; /* L 指向头结点 */ p=(*L)-next; /* p 指向第一个结点 */ while(p!=*L) /* 没到表尾 */q=p-next;free(p);p=q;(*L)-next=*L; /* 头结点指针域指向自身 */return OK;Status ListEmpty_CL(LinkList L)FALSE */ /* 初始条件：线性表 L 已