数据结构代码整理(1)
调试环境:Turbo C 2.0
教材：《数据结构C语言版》清华大学出版社
指导老师：张志良
由于时间较长了，有一个文件找不到了，所以不是很全。希望大家谅解。
Define.h
1) /*define.h*/
2) /*书中定义的最有用的一些常量 */
3) #define TRUE 1
4) #define FALSE 0
5) #define OK 1
6) #define ERROR 0
7) #define INFEASIBLE -1
8) #define OVERFLOW -2
9) typedef int Status;
10) typedef int ElemType;
线性链表的头文件
1) /*******************************************************************
2) * Stlinear.h *
3) * 本文件的函数应用于算法2.1至2.6 *
4) ********************************************************************/
5) #include "define.h"
6) #define LISTINCREMENT 10 /* 数组的增加值 */
7) #define LIST_INIT_SIZE 100 /* 数组的开始值 */
8) /* 这里定义的两个数组被看作是代替键盘的输入 */
9) int a[22]={7 , 2, 1, 5, 6, 8, 9,10, 3, 4,-1};
10) int b[11]={7,2,11,15,16,18,19,20,13,14,-1};
11) typedef struct /*定义一个数组的元素结构*/
12) {ElemType *elem;
13) int length;
14) int listsize;
15) }SqList;
16) ElemType LocateElem(ElemType La[ ],ElemType e)
17) /* 如果你要找的元素在这个线性表里面，则返回它的值否则返回0 */
18) {int *p=La;
19) while(*p!=-1)
20) if(e = =*p++) return e;
21) return 0;
22) }
23) void ListInsert (ElemType La[ ],int la_len,ElemType e ) /*插入一个元素*/
24) {ElemType *p=La;
25) *(p+la_len)=e;
26) *(p+la_len+1)=-1;
27) }
28) ElemType ListLength(int list[ ]) /*计算线性表的长度*/
29) {int *p=list;
30) int count=0;
31) while(*p++!=-1) count++;
32) return count;
33) }
34) ElemType GetElem(ElemType Lb[ ],ElemType i , ElemType e)
35) /* 在线性表中查找一个要寻找的元素并返回它的值 */
36) {ElemType *p=Lb;
37) e=*(p+i);
38) return e;
39) }
40) void combine(ElemType La[ ],ElemType Lb[ ]) /* 把两个线性表连接起来 */
41) {ElemType la_len;
42) ElemType lb_len;
43) int i;
44) la_len=ListLength(La)-1;
45) lb_len=ListLength(Lb)-1;
46) for(i=0;i<=lb_len;i++)
47) {GetElem(Lb,i,*(Lb+i));
48) if(!LocateElem(La,*(Lb+i))) ListInsert(La,++la_len,*(Lb+i));
49) }
50) }
51) char *mergelist(char *la,char *lb) /* 合并两个线性表 */
52) {int i,j,k,lena,lenb;
53) char *lc;
54) i=j=k=0;
55) lena=strlen(la);
56) lenb=strlen(lb);
57) lc=(char *)malloc((lena+lenb)*sizeof(char)+1);
58) if(!lc) exit(OVERFLOW);
59) while(la[i]!=''&&lb[j]!='')
60) if(la[i]<=lb[j])
61) {*(lc+k)=la[i];k++;i++;}
62) else
63) {*(lc+k)=lb[j];k++;j++;}
64) if(la[i]=='')
65) for(;lb[j]!='';k++,j++) *(lc+k)=lb[j];
66) if(lb[j]=='')
67) for(;la[i]!='';k++,i++) *(lc+k)=la[i];
68) *(lc+k)='';
69) return lc;
70) }
71) Status InitList_Sq(SqList *L) /* 构造一个线性表 */
72) {L->elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
73) if(!L->elem) exit(OVERFLOW);
74) L->length=0;
75) L->listsize=LIST_INIT_SIZE ;
76) return OK;
77) } /* InitList_Sq */
78) Status ListInsert_Sq(SqList *L,int i , ElemType e) /* 在线性表中插入一个元素 */
79) {ElemType *p,*q;
80) ElemType *newbase;
81) ElemType *d; /*d用于给链表加结尾(-1) */
82) L->listsize=ListLength(a)+LISTINCREMENT;
83) L->length=ListLength(a); /*在链表L的第I个元素之前插入元素e */
84) if (i<1||i>(L->length)+1) return ERROR; /* 若找不到I,则返回出错信息*/
85) if ((L->length)>=(L->listsize)) /*若空间已满则申请新的空间 */
86) {newbase= (ElemType *)malloc ((L->listsize)*sizeof(ElemType));
87) if(!newbase) exit(OVERFLOW);
88) L->elem=newbase;
89) L->listsize+=LISTINCREMENT;
90) }
91) q=&(L->elem[i-1]);
92) for(p=& (L->elem[L->length-1]);p>=q;--p) *(p+1)=*p;
93) *q=e;
94) ++L->length;
95) d=&(L->elem[L->length]);
96) *d=-1;
97) return OK;
98) } /*ListInsert_Sq*/
99) ElemType ListDelete_Sq(SqList *L,int i ) /* 删除一个元素，并返回它的值 */
100) {ElemType *p,*q;
101) ElemType e;
102) int Length,number;
103) L->length=ListLength(a);
104) if ((i<1)||(i>L->length)) return ERROR; /*若找不到I,则返回出错信息 */
105) p=&(L->elem[i-1]); /*p为要删除的元素的地址 */
106) e= *p; /*返回元素的值*/
107) q=L->elem+L->length-1; /*链表表尾的地址*/
108) for(++p;p<=q;++p) *(p-1)=*p; /*链接剩余的元素*/
109) --L->length; /*减少链表的长度 */
110) Length=L->length;
111) Length++;Length--; /*仅仅为了防止警告*/
112) return e;
113) } /*ListDelete_Sq*/
114) int LocateElem_Sq(SqList L,ElemType e)
115) /*找到线性表中符合要求的第一个元素，并返回它的值，如果找不到，就返回 0 */
116) {int i;
117) ElemType *p;
118) int compare;
119) i=0;
120) p=L.elem;
121) L.length=ListLength(a);
122) compare=0;
123) while(i++<=L.length && (!compare) )
124) {if ((*p++)= =e)
125) {compare=1;
126) break;
127) }
128) }
129) if (i<=L.length) return i ;
130) else return 0;
131) } /*LocateElem_Sq*/
132) void MergeList_Sq (SqList La,SqList Lb, SqList *Lc) /* 合并两个线性表 */
133) {int number=0;
134) ElemType *pa,*pb,*pc;
135) ElemType *pa_last,*pb_last;
136) La.elem=a; Lb.elem=b;
137) La.length=La.listsize=ListLength(a);
138) Lb.length=Lb.listsize=ListLength(b);
139) pa=La.elem; pb=Lb.elem;
140) Lc->listsize=Lc->length=La.length+Lb.length;
141) pc=Lc->elem= (ElemType *)malloc(Lc->listsize*sizeof (ElemType));
142) if(!Lc->elem) exit(OVERFLOW);
143) pa_last=La.elem+La.length-1;
144) pb_last=Lb.elem+Lb.length-1;
145) while (pa<=pa_last && pb<=pb_last)
146) {if (*pa<=*pb) *pc++=*pa++;
147) else *pc++=*pb++;
148) number++;
149) }
150) while (pa<=pa_last) { *pc++=*pa++; number++; }
151) while (pb<=pb_last) { *pc++=*pb++; number++; }
152) } /*Mergelist_Sq*/
算法 2.1(书20页)
1) /*************************************************************************
2) * DS2_1_1.cpp *
3) * 算法2.1 *
4) * 把所有在线性表Lb中但不在La中的元素插入到La中 *
5) **************************************************************************/
6) # include<stdio.h>
7) # include "stlinear.h"
8) void main()
9) {int *q=a;
10) combine(a,b);
11) do
12) { printf("%4d",*q);
13) }while( *++q!=-1);
14) }
算法 2.2 （书21页）
1) /************************************************************************
2) * DS2_2.c *
3) * 已知线性表La和Lb中的数据元素按值非递减排列 *
4) * 归并Lb和La得到新的线性表Lc,Lc的数据元素也按非递减排列 *
5) ************************************************************************/
6) # include<stdio.h>
7) # include<string.h>
8) # include<alloc.h>
9) # include<stdlib.h>
10) # include "stlinear.h"
11) void main()
12) {char a[ ]="abcdh",
13} b[ ]="abefg",
14} *lcp;
15} lcp= mergelist (a,b);
16} printf("%s",lcp);
17} }
算法2.3 （书23页）
1) /*****************************************************************
2) * DS2_3.cpp *
3) * 算法2。3 *
4) * 初始化一个线性表 *
5) ******************************************************************/
6) # include<stdio.h>
7) # include<stdlib.h>
8) # include "stlinear.h"
9) void main()
10) {Status result;
11} SqList L;
12} result=InitList_Sq (&L);
13} if(result==OK) printf ("OK");
14} }
Algorism 2.4 （书24页）
1) /*********************************************************
2) * DS2_4.c *
3) * 算法 2.4 *
4) * 在数组中插入一个元素 *
5) **********************************************************/
6) # include<alloc.h>
7) # include<conio.h>
8) # include<stdio.h>
9) # include<process.h>
10) # include "stlinear.h"
11) void main()
12) {SqList L;
13) ElemType e;
14) int i,j;
15) L.elem=a;
16) printf ("Please input the number you want to insert:");
17) scanf ("%d",&e);
18) printf ("Please input the place for the number you want to insert:");
19) scanf("%d",&i);
20) if (ListInsert_Sq (&L,i,e)= =OK)
21) {for(j=0;j<ListLength (a);j++) printf ("%-4d",a[j]);
22) printf (" ");
23) printf ("Successfully done !!! ");
24) }
25) else printf ("OverFlow");
26) }
算法 2.5 （书25页）
1) /******************************************************************
2) * DS2_5.c *
3) * 算法2.5 *
4) * 在线性表中删除一个元素 *
5) ******************************************************************/
6) # define NULL 0
7) # define LISTINCREMENT 10
8) # include"stlinear.h"
9) # include<stdio.h>
10) ElemType e; /*显示要被删除的元素*/
11) int Length;
12) Status ListDelete (SqList *L,int i ) /*删除第i个元素,并返回这个元素的值 */
13) {ElemType *p,*q;
14) L->length=ListLength (a);
15) if ((i<1) || (i>L->length)) return ERROR; /*如果输入值无效*/
16) p= &(L->elem[i-1]); /*元素要被删除的位置 */
17) e=*p; /*返回e的值*/
18) q= L->elem+L->length-1; /*最后一个元素的位置 */
19) for (++p;p<=q;++p) *(p-1)=*p; /*所有的元素都要向左移动一位*/
20) --L->length; /*线性表的长度要减少一位*/
21) Length=L->length;
22) return OK;
23) } /*ListDelete_Sq*/
24) void main()
25) {SqList A;
26) int i,j;
27) elem=a;
28) printf ("Please input the place where you want to delete the element:");
29) scanf ("%d",&i);
30) if (ListDelete(&A,i)= =OK)
31) {printf ("The element you deleted is %d ",e);
32) for (j=0;j<Length;j++)
33) printf ("%-4d",a[j]);
34) printf (" ");
35) printf ("Element deleted successfully!!! ");
36) }
37) else printf ("Invalidate input!!! ");
38) }
算法 2.6（书26页）
39) /*********************************************************************
40) * DS2_6.c *
41) * 算法 2.6 *
42) * 找到第一个符合要求的元素 *
43) **********************************************************************/
44) # include "stlinear.h"
45) # include<stdio.h>
46) void main()
47) {SqList L;
48) int j;
49) ElemType e;
50) L.elem=a;
51) printf ("Please input the element you want to find:");
52) scanf ("%d",&e);
53) printf (" ");
54) if (( j=LocateElem_Sq (L,e))= =0)
55) printf("Can not found!!! ");
56) else
57) printf ("The element you've input is the %d' th one in the list. ",j);
58) }
算法2.7 （书26页）
1) /********************************************************************
2) * DS2_7.c * * 算法 2.7 *
3) * 另一中合并两个线性表的方法 *
4) *********************************************************************/
5) /*定义两个按照递减排序的数组仅仅为了调试方便.*/
6) int a[11]={1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10 ,-1};
7) int b[11]={2,3,4,5,6,7,8,9,10,11,-1};
8) # include "define.h"
9) # include<alloc.h>
10) # include<process.h>
11) # include<stdio.h>
12) int number=0;
13) typedef struct {
14) ElemType *elem;
15) int length;
16) int listsize;
17) }SqList;
18) int ListLength(int list[ ])
19) {int *p=list;
20) int count=0;
21) while (*p++!=-1) count++;
22) return count;
23) }
24) void MergeList_Sq (SqList La,SqList Lb, SqList *Lc)
25) {ElemType *pa,*pb,*pc;
26) ElemType *pa_last,*pb_last;
27) La.elem=a; Lb.elem=b;
28) La.length=La.listsize=ListLength(a);
29) Lb.length=Lb.listsize=ListLength(b);
30) pa=La.elem; pb=Lb.elem;
31) Lc->listsize=Lc->length=La.length+Lb.length;
32) pc=Lc->elem=(ElemType *)malloc(Lc->listsize*sizeof(ElemType));
33) if(!Lc->elem) exit(OVERFLOW);
34) pa_last=La.elem+La.length-1;
35) pb_last=Lb.elem+Lb.length-1;
36) while(pa<=pa_last&& pb<=pb_last)
37) { if(*pa<=*pb) *pc++=*pa++;
38) else *pc++=*pb++;
39) number++;
40) }
41) while (pa<=pa_last) { *pc++=*pa++; number++; }
42) while (pb<=pb_last) { *pc++=*pb++; number++; }
43) } /*Mergelist_Sq*/
44) void main()
45) {int i=0;
46) SqList A,B,C;
47) elem=a;
48) elem=b;
49) MergeList_Sq(A,B,&C);
50) while(i++<number)
51) printf("%d ",*C.elem++);
52) }
算 法2.8(书29页)
1) /******************************************************
2) * DS2_8.c *
3) * 算法2.8 *
4) * 在线性表中找到第i个元素 *
5) *******************************************************/
6) # include "define.h"
7) # include<stdio.h>
8) # include<alloc.h>
9) int a[11]={7 , 2, 1, 5, 6, 8, 9,10, 3, 4,-1};
10) typedef struct L_Node
11) {ElemType data;
12) struct L_Node *next;
13) } LNode,*LinkList;
14) Status GetElem_L (LinkList L, int i )
15) /*L为带头接点的单链表的头指针，当第i个元素存在的时候，其值赋给e并返回OK,否则返回ERROR */
16) {int j;
17) LinkList p=L;
18) LinkList temp;
19) if(i==1)
20) {printf("%d ",p->data);
21) return OK;
22) }
23) p= p->next; j=1; /*初始化，p指向第一个接点，j是记数器 */
24) while (p && j<i) /*顺指针向后查找，直到p指向第i个元素或p为空*/
25) {temp=p;
26) p=p->next; ++j;
27) }
28) if( !p || j<i) return ERROR; /*第i个元素不存在*/
29) printf ("%d ",temp->data); /*打印该元素*/
30) return OK;
31) } /*GetElem_L*/
32) void main()
33) {int i;
34) int j;
35) LinkList L,p;
36) L=(LNode *)malloc (sizeof (LNode));
37) p=L;
38) L->next=NULL;
39) L->data=-2;
40) j=0;
41) while (L->data!=-1)
42) {L->data=a[j++];
43) L->next= (LNode *)malloc(sizeof (LNode));
44) L=L->next;
45) }
46) L->next=NULL;
47) L=p;
48) printf ("Please input the number to the place for the element:");
49) scanf ("%d",&i);
50) if (GetElem_L (L,i)= =OK) printf("Well Dond!!! ");
51) else printf ("The requirement you've done haven't been sucessfully done !!! ");
52} }
算法 2.9，2.11（书30，31页）
1) /********************************************************************
2) * DS2_9.c *
3) * 算法 2.9 *
4) * 在地i个元素插入一个元素 *
5) ********************************************************************/
6) # include "define.h"
7) # include<stdio.h>
8) # include<alloc.h>
9) int a[11]={7 , 2, 1, 5, 6, 8, 9,10, 3, 4,-1};
10) typedef struct L_Node
11) {ElemType data;
12) struct L_Node *next;
13) }LNode,*LinkList;
14) int ListLength (int list[ ])
15) {int *p=list;
16) int count=0;
17) while (*p++!=-1) count++;
18) return count;
19) }
20) Status ListInsert_L(LinkList L,int i , ElemType e)
21) /*在带头接点的单链线性表的第i个元素前插入元素e*/
22) {LinkList p,s;
23) int j=0;
24) p=L;
25) while (p && j<i-1)
26) {p=p->next;
27) ++j;
28) } /* 寻找第i-1 个节点 */
29) if(!p || j>i-1) return ERROR;
30) s= (LNode *)malloc (sizeof (LNode));
31) s->data=e;
32) s->next=p->next;
33) p->next=s;
34) return OK;
35) } /* ListInsert */
36) LinkList CreateList_L (LinkList L,int n )
37) /* 逆位序输入n个元素的值，建立带表头接点的单链线性表L */
38) {int i;
39) LinkList p;
40) L= (LinkList)malloc(sizeof (LNode));
41) L->next=NULL; /* 先建立一个带头接点的单链线性表 */
42) for ( i=n;i>=0;--i)
43) {p= (LinkList) malloc(sizeof (LNode));
44) p->data=a[i];
45) p->next=L->next;L->next=p;
46) }
47) return L;
48) } /* CreateList_L */
49) void OutPutList (LinkList L,int n)
{LinkList p=L;
50) int i;
51) printf (" ");
52) for(i=0;i<n;i++)
53) {p=p->next;
54) printf("%4d",p->data);
55) }
56) printf(" ");
57) } /* Output the linear table */
58) void main()
59) {int i;
60) ElemType e;
61) LinkList L=NULL;
62) L=CreateList_L (L,ListLength (a));
63) OutPutList (L,ListLength (a));
64) printf ("Please input the place you want to add an element in :");
65) scanf ("%d",&i);
66) if(i<1||i>ListLength(a))
67) {printf ("OVERFLOW ");
68) exit(OVERFLOW);
69) }
70) printf(" Please input the element that you want to insert:");
71) scanf("%d",&e);
72) printf(" ");
73) if(ListInsert_L(L,i,e)==OK)
74) {OutPutList (L,ListLength(a)+1);
75) printf(" Well Done!! ");
76) }
77) else
78) printf("OverFlow");
79) }
算法 2.10（书30页）
1) /********************************************************************
2) *程序DS2_10.c *
3) *算法2.10 (p.30) *
4) *实现:删除第 i 个元素; *
5) *操作:建立一个头接点为空的链表,找到第i个元素并删除它,而后输出新的链 *
6) * 表及第i个元素的值; *
7) *********************************************************************/
8) # include "define.h"
9) # include<stdio.h>
10) # include<alloc.h>
11) int a[11]={7 , 2, 1, 5, 6, 8, 9,10, 3, 4,-1};
12) typedef struct L_Node
13) {ElemType data;
14) struct L_Node *next;
15) }LNode,*LinkList;
16) int ListLength(int list[ ]) /*求出数组的长度*/
17) {int *p=list;
18) int count=0;
19) while(*p++!=-1) count++;
20) return count;
21) }
22) LinkList CreateList_L(LinkList L,int n )
23) /* 从底部开始输入由n个元素组成的数组,其头接点为空*/
24) {int i;
25) LinkList p;
26) L=(LinkList)malloc(sizeof (LNode));
27) L->next=NULL; /*最初建立一个只有头接点的空链表*/
28) for(i=n;i>=0;--i)
29) {p=(LinkList)malloc(sizeof(LNode));
30) p->data=a[i];
31) p->next=L->next; L->next=p;
32) }
33) return L;
34) }
35) ElemType ListDelete_L(LinkList L , int i ) /*删除第i个元素,将其值赋予e*/
36) {ElemType e;
37) LinkList p,q;
38) int j;
39) p=L;
40) j=0;
41) while(p->next&&j<i-1)
42) /*找到第i个元素所在的位置并将指针p指向它的前一个元素*/
43) {p=p->next; ++j;
44) }
45) if(!(p->next)||j>i-1) return ERROR; /*没有找到其地址*/
46) q=p->next; p->next=q->next; /*删除元素*/
47) e=q->data; free(q); /*释放接点*/
48) return(e);
49) }
50) void OutPutList(LinkList L,int n) /*输出新的链表*/
51) {LinkList p=L;
52) int i;
53) printf(" ");
54) for(i=0;i<n;i++)
55) {p=p->next;
56) printf("%4d",p->data);
57) }
58) printf(" ");
59) }
60) void main()
61) {int i;
62) LinkList L=NULL;
63) L=CreateList_L(L,ListLength(a));
64) OutPutList(L,ListLength(a));
65) printf ("Please input the place you want to delete an element :");
66) scanf ("%d",&i);
67) if(i<1||i>ListLength(a)) /*若不存在i则返回出错信息*/
68) {printf ("OVERFLOW ");
69) exit(OVERFLOW);
70) }
71) printf (" The element you deleted in the %d place is %d. ",i,ListDelete_L(L,i));
72) OutPutList(L,ListLength(a)-1);
73) }
算法2.12(书31页)
/*******************************************************************
* DS2_12.c *
* 算法2.12 *
* 合并两个线性链表 *
********************************************************************/
# include "define.h"
# include<stdio.h>
# include<alloc.h>
# include<process.h>
/* 这里定义的两个数组被看作是代替键盘的输入 */
int a[11]={1 ,2 ,3 ,4 ,5 ,6 ,7 ,8,9,10 ,-1};
int b[11]={2,3,4,5,15,18,19,20,24,31,-1};
/* 定义一个在线性表中要用到的结构 */
typedef struct L_Node
{ElemType data;
struct L_Node *next;
}LNode,*LinkList;
LinkList A_CreateList(LinkList L,int n )
{int i;
LinkList p;
L= (LinkList)malloc(sizeof(LNode));
L->next=NULL;
for(i=n;i>=0;--i)
{p=(LinkList)malloc(sizeof(LNode));
p->data=a[i];
p->next=L->next; L->next=p;
}
return L;
} /* CreateList_L */
LinkList B_CreateList(LinkList L,int n )
{int i;
LinkList p;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
for(i=n;i>=0;--i)
{p=(LinkList)malloc(sizeof(LNode));
p->data=b[i];
p->next=L->next; L->next=p;
}
return L;
} /* CreateList_L */
int ListLength(int list[ ])
{int *p=list;
int count=0;
while(*p++!=-1) count++;
return count;
}
void OutPutList(LinkList L,int n)
{LinkList p=L;
int i;
printf(" ");
for(i=0;i<n;i++)
{p=p->next;
printf("%4d",p->data);
}
printf(" ");
} /* Output the linear table */
void MergeList_L(LinkList La, LinkList Lb, LinkList Lc)
/* 我们已经有了两个按照非递减顺序排列的线性表，现在我们要把它们合并*/
{LinkList pa=NULL,pb=NULL,pc=NULL;
La=pa=A_CreateList(pa,ListLength(a)-1);
Lb=pb=B_CreateList(pb,ListLength(b));
pa=pa->next; pb=pb->next;
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);
OutPutList(Lc,(ListLength(a)+ListLength(b)));
} /* MergeList_L */
void main()
{LinkList La=NULL,Lb=NULL,Lc=NULL;
MergeList_L(La,Lb,Lc);
}
算法2.13~2.17（书32，34页）
1) /**************************************************************************
2) *程序DS2_17.c *
3) *算法2.17 (其中包含算法2.14~~2.16) (p.33) *
4) *实现: (A-B)U(B-A); *
5) *操作:建立表示集合A的静态链表S,而后再输入集合B的元素的同时查找S表, 若存*
6) * 在和B相同的元素,则从S表中删除之,否则将其插入S中 *
7) **************************************************************************/
8) # define MAXSIZE 1000
9) typedef char Elemtype;
10) typedef struct
11) {Elemtype data;
12) int cur;
13) }component,SLinkList[MAXSIZE];
14) void InitSpace_SL(SLinkList space)
15) /*将一维数组space中各个分量链接成一个备用链表，space[0].cur为头指针*/
16) {int i;
17) for(i=0;i<MAXSIZE-1;++i) space[i].cur=i+1;
18) space[MAXSIZE-1].cur=0;
19) }
20) int Malloc_SL(SLinkList space)
21) /*若备用空间链表非空，则返回分配的节点下标，否则返回0*/
22) {int i;
23) i=space[0].cur;
24) if(space[0].cur) space[0].cur=space[i].cur;
25) return i;
26) }
27) void Free_SL(SLinkList space,int k) /*将下标为k的空间结点回收到备用链表*/
28) {space[k].cur=space[0].cur;
29) space[0].cur=k;
30) }
31) void difference(SLinkList space,int S)
32) /*依次输入集合A和B的元素，在一维数组space中建立表示集合（A-B）∪(B-A)的静态链表，S为其头指针。假设备用空间足够大，space[0].cur为其头指针 */
33) {int i,j,r,m,n,k,p;
34) SLinkList b;
35) InitSpace_SL(space);
36) InitSpace_SL(b);
37) S=Malloc_SL(space);
38) r=S;
39) printf("input m,n:");
40) scanf("%d%d",&m,&n);
41) for(j=1;j<=m;++j)
42) {i=Malloc_SL(space);
43) printf(" input a:");
44) scanf("%s",&space[i].data);
45) space[r].cur=i;
46) r=i++;
47) }
48) space[r].cur=0;
49) for(j=1;j<=n;++j)
50) {printf(" input b:");
51) scanf("%s",&b[j].data);
52) p=S;
53) k=space[S].cur;
54) while(k!=space[r].cur && space[k].data!=b[j].data)
55) {p=k;
56) k=space[k].cur;
57) }
58) if (k==space[r].cur)
59) {i=Malloc_SL(space);
60) space[i].data=b[j].data;
61) space[i].cur=space[r].cur;
62) space[r].cur=i;
63) }
64) else
65) {space[p].cur=space[k].cur;
66) Free_SL(space,k);
67) if(r==k) r=p;
68) }
69) }
70) }
71) int LocateElem_SL(SLinkList *S,int e)
72) /*在静态链表中找到第一个值为e的元素，并返回它的下标 */
73) {int i;
74) i=S[0]->cur;
75) while(i&&S[i]->data!=e) i=S[i]->cur;
76) return i;
77) } /* LocateElem_SL */
78) main( )
79) {SLinkList a;
80) int s=0,i=1;
81) difference(a,s);
82) if(a[1].cur!=0)
83) do
84) {i=a[i].cur;
85) printf(" %c,%d",a[i].data,a[i].cur);
86) }while(a[i].cur!=0);
87) else printf(" (A-B)U(B-A)=Null ");
88) getch();
89) }
算法2.18(书36页)
1) /***************************************************************************程序DS2_18 .c *
2) *算法2.18 (p.36) * *实现: 建立双向链表,并在指定的位置之前插入元素; *
3) **************************************************************************/
4) # define ok 1
5) # define NULL 0
6) # define error -1
7) typedef int ElemType;
8) typedef int status;
9) typedef struct Dulnode
10) {Elemtype data;
11) struct DuLnode *prior; /*前驱指针*/
12) struct DuLnode *next; /*后续指针*/
13) }node,*Dulink;
14) status Greatedulink(Dulink L,ElemType m) /*建立双向链表,其长度为m*/
15) {Dulink p,q;
16) ElemType j;
17) p=L;
18) for(j=1;j<=m;j++)
19) {q=(Dulink)malloc(sizeof(node));
20) if(!q) return error;
21) scanf("%d",&q->data);
22) q->prior=p;
23) p->next=q;
24) p=q;
25) q->next=NULL;
26) }
27) return ok;
28) }
29) Dulink GetElemp_dul(Dulink L,ElemType i,ElemType m)
30) /*在链表中取出第i个元素,赋值于m*/
31) {ElemType j;
32) Dulink q;
33) q=L;
34) if(!(i>=1&&i<=(m+1))) return NULL;
35) for(j=1;j<=i;j++) q=q->next;
36) return q;
37) }
38) status IistInsert_dul(Dulink L,ElemType i,ElemType e)
39) /*在带头结点的双链循环链表中第i个位置之前插入元素e(1<=i<=表长+1)*/
40) {Dulink p,s;
41) p=GetElemp_dul(L,i,e); /*在L中确定第i个元素的位置指针p*/
42) if(!p) return error; /*p=NULL 则返回不存在信息*/
43) s=(Dulink)malloc(sizeof(node));
44) if(!s) return error;
45) s->data=e;
46) s->prior=p->prior; p->prior->next=s;
47) s->next=p; p->prior=s;
48) return ok;
49) }
50) main()
51) {Dulink L,p;
52) ElemType i,e,m;
53) int j=1;
54) L=(Dulink)malloc(sizeof(node));
55) printf(" please put in the length of link: ");
56) scanf("%d",&m);
57) Greatedulink(L,m);
58) printf("Please input the position that you want to insert the element in :");
59) scanf("%d",&i);
60) if(i<=0||i>m) /*若不存在i,则返回出错信息*/
61) {printf("Invalidate input !!!");
62) exit(1);
63) }
64) p=GetElemp_dul(L,i,m);
65) printf(" please put in the insert e: ");
66) scanf("%d",&e);
67) IistInsert_dul(L,i,e);
68) p=L->next;
69) while(j<=m+1) /*输出新的链表*/
70) {printf("%d:%d ",j,p->data);
71) p=p->next;
72) j++;
73) }
74) }
算法2.19（书37页）
1) /**************************************************************************
2) *程序DS2_19.c *
3) *算法2.19 (p.37) *
4) *实现:删除一个带头结点的双链循环表的第 i 个元素 *
5) ***************************************************************************
6) # define ok 1
7) # define NULL 0
8) # define error -1
9) typedef int elemtype;
10) typedef int status;
11) typedef struct dulnode
12) {elemtype data;
13) struct dulnode *prior;
14) struct dulnode *next;
15) }node,*dulink;
16) status greatedulink(dulink L,elemtype m) /*建立一个双链循环表(长度为m)*/
17) {dulink p,q;
18) elemtype j;
19) p=L;
20) for(j=1;j<=m;j++)
21) {q=(dulink)malloc(sizeof(node));
22) if(!q) return error;
23) scanf("%d",&q->data);
24) q->prior=p; p->next=q; p=q;
25) q->next=NULL;
26) }
27) return ok;
28) }
29) dulink getelemp_dul(dulink L,elemtype i,elemtype m)
30) /*找到第i个元素的位置(m为表长) (1<=i<=表长)*/
31) {int j;
32) dulink q;
33) q=L;
34) if(!(i>=1&&i<=(m+1))) return NULL;
35) for(j=1;j<=i;j++) q=q->next;
36) return q;
37) }
38) elemtype listdelete_dul(dulink L,int i,elemtype m) /*删除第i个元素*/
39) {dulink p;
40} elemtype *e=&m;
41} p=getelemp_dul(L,i,m); /*在L中确定第i个元素的位置指针p*/
42} if(!p) return error; /*p=NULL 则返回不存在信息*/
43} L=p;
44} *e=p->data;
45} p->prior->next=p->next;
46} p->next->prior=p->prior;
47} free(p);
48} return m;
49} }
50) main()
51) {dulink L,*L1,p,q;
52} elemtype i,m,result;
53} int j=1;
54} L=(dulink)malloc(sizeof(node));
55} q=L;
56} printf(" please put in the length of link: ");
57} scanf("%d",&m);
58} greatedulink(L,m);
59} printf("Please input the position that you want to delete the element in :");
60} scanf("%d",&i);
61} if(i<=0||i>m) /*若不存在i则返回出错信息*/
62} {printf("Invalidate input !!!");
63} exit(1);
64} }
65} result=listdelete_dul(L,i,m);
66} printf("The value of the element that you want to delete is %d ",result);
67} p=q;
68} while(j<=m-1) /*输出新的链表*/
69} {printf("%d ",p->next->data);
70} p=p->next;
71} j++;
72} }
73} }
算法2.20（书39页）
1) /*************************************************************************
2) *程序DS2_20,c *
3) *算法2.20 (p.38) *
4) *实现: 建立带头结点的单向链表,并在第i个元素之前插入元素 *
5) ************************************************************************/
6) # define NULL 0
7) # define OK 1
8) # define ERROR -1
9) typedef int status;
10) typedef int elemtype;
11) typedef struct Lnode
12) {elemtype data;
13) struct Lnode *next;
14) }*Link,*Position;
15) typedef struct
16) {Link head,tail;
17) int len;
18) }LinkList;
19) status InitLinkList(LinkList *L) /*建立空链表*/
20) {(L->head)=(Link)malloc(sizeof(struct Lnode));
21) (L->head)->next=NULL;
22) L->len=0;
23) return OK;
24) }
25) status CreateLinkList(LinkList *L,elemtype m) /*给链表赋值,共m个元素*/
26) {Link p,q;
27) elemtype j;
28) p=L->head;
29) for(j=1;j<=m;j++)
30) {q=(Link)malloc(sizeof(struct Lnode));
31) if(!q) return ERROR;
32) {p->next=q;
33) p=q;
34) q->next=NULL;
35) scanf("%d",&(q->data));
36) }
37) }
38) return OK;
39) }
40) Link LocatePos(LinkList *L,elemtype b,elemtype m,Link q)
41) /*在链表中找到第b个元素并返回指针*/
42) {elemtype j;
43) if(!(b>=1&&b<=m)) return NULL;
44) q=L->head;
45) for(j=1;j<=b;j++) q=q->next;
46) return q;
47) }
48) Link MakeNode(Link p,elemtype e) /*建立新的分配空间*/
49) {p=(Link)malloc(sizeof(struct Lnode));
50) p->data=e;
51) return p;
52) }
53) status InsFirst(Link h,Link s) /*插入元素*/
54) {s->next=h->next;
55) h->next=s;
56) }
57) main( )
58) {elemtype m,i,b,e;
59) LinkList *L;
60) Link h,s,p,q,t;
61) int j=1;
62) p=q=(Link)malloc(sizeof(struct Lnode));
63) L=(LinkList *)malloc(sizeof(LinkList));
64) InitLinkList(L);
65) printf(" Please put in m(the length of linklist): ");
66) scanf("%d",&m);
67) CreateLinkList(L,m);
68) printf(" Pleas put in the insert position i: ");
69) scanf("%d",&i);
70) if(i<=0||i>m) /*i不存在,则返回出错信息*/
71) {printf("Invalidate input!");
72) exit(1);
73) }
74) b=i-1;
75) h=LocatePos(L,b,m,q);
76) printf(" Please put in the insert node's data e: ");
77) scanf("%d",&e);
78) s=MakeNode(p,e);
79) InsFirst(h,s);
80) t=L->head->next;
81) while(j<=m+1)
82) {printf("%d:%d ",j,t->data);
83) t=t->next;
84) j++;
85) }
86) }
算法2.21（书39页）
1) /*************************************************************************
2) *程序DS2_21.c *
3) *算法2.21 (p.39) *
4) *实现:将单链线性表La和lb的元素按非递减排列于Lc中 *
5) *操作:建立链表;按非递减顺序进行新的排列; *
6) *************************************************************************/
7) # define NULL 0
8) # define Len sizeof(Lnode)
9) # define LEN sizeof(Linklist)
10) typedef int ElemType;
11) typedef struct Lnode
12) {ElemType data;
13) struct Lnode *next;
14) }Lnode,*Link,*Position;
15) typedef struct
16) {Link head,tail;
17) int len;
18) }Linklist;
19) Position Initlist() /*建立单向链表(头结点为空)并赋值*/
20) {Link head,p1,p2;
21) head=(Link)malloc(Len);
22) p1=p2=(Link)malloc(Len);
23) head->data=NULL;
24) printf("Please write the data:");
25) scanf("%d",&p1->data);
26) head->next=p1;
27) while(p1->data!=0)
28) {p1=(Link)malloc(Len);
29) scanf("%d",&p1->data);
30) p2->next=p1; p2=p1;}
31) p2->next=NULL;
32) return(head);
33) }
34) Position NextPos(Link ha) /*找到当前元素的下一个元素的地址并返回指针*/
35) {Link pa;
36) if(ha->next!=NULL)
37) { pa=ha->next;
38) return(pa);
39) }
40) }
41) Position MergeList_L(Linklist *la,Linklist *lb) /*将La和Lb进行重新排列*/
42) { Link ha,hb,hc,h;Link pa,pb,q;
43) ElemType a,b;
44) ha=la->head; /*ha指向头结点*/
45) hb=lb->head; /*hb指向头结点/
46) hc=(Link)malloc(Len); /*重新建立头结点*/
47) h=hc;
48) pa=NextPos(ha);
49) pb=NextPos(hb);
50) while (pa->data!=0 && pb->data!=0) /*pa 和pb非空*/
51) { a=pa->data;
52) b=pb->data;
53) if(a<=b) /*比较当前元素*/
54) { q=pa;
55) pa=NextPos(pa);
56) hc->next=q; hc=q;
57) }
58) else {q=pb;
59) pb=NextPos(pb);
60) hc->next=q; hc=q;
61) }
62) }
63) if(pa->data!=0) hc->next=pa; /*链接剩余结点*/
64) else hc->next=pb;
65) free(ha); free(hb);
66) return(h);
67) }
68) void print(Linklist *lc) /*输出最后的新链表*/
69) { Link p;
70) p=lc->head;
71) p=p->next;
72) printf("The result is:");
73) while(p!=NULL)
74) { printf("%3d",p->data);
75) p=p->next;
76) }
77) }
78) main()
79) {Linklist *la,*lb,*lc;
80) la=(Linklist *)malloc(LEN);
81) lb=(Linklist *)malloc(LEN);
82) lc=(Linklist *)malloc(LEN); /*Lc只是一个空的头结点*/
83) printf(" Please write the length of la:");
84) scanf("%d",&la->len);
85) printf(" Please write the length of lb:");
86) scanf("%d",&lb->len);
87) la->head=Initlist();
88) lb->head=Initlist();
89) lc->head=MergeList_L(la,lb);
90) printf(" *** *** *** *** *** *** ");
91) print(lc);
92) printf(" *** *** *** *** *** *** ");
93) getch();
94) }
算法2.22~2.23 （书43页）
1) /************************************************************************
2) *程序DS2_23.c *
3) *算法2.23 (p.23)(包含算法 2.22) *
4) *实现:一元多次式的表示和相加 *
5) *操作:以链表的形式表示系数和指数;进行加法运算; *
6) **************************************************************************/
7) # include "define.h"
8) # include<stdio.h>
9) # define LEN sizeof(Linklist)
10) # define Len sizeof(Lnode)
11) typedef struct Lnode
12) {int coef;
13) int expn;
14) struct Lnode *next;
15) }Lnode,*Link,*Position;
16) typedef struct
17) {Link head,tail;
18) int len;
19) }Linklist;
20) typedef Linklist polynomial;
21) Position CreatPolyn(int m)
22) /*建立单向线性表并赋值填入相应的系数和指数(其长度为m),头指针为空(0,-1)*/
23) {Link head,p1,p2; int i;
24) head=(Link)malloc(Len);
25) p1=p2=(Link)malloc(Len);
26) head->coef=0; head->expn=-1; /*设置头结点的数据元素*/
27) printf(" Please writer the struct: coef expn: ");
28) scanf("%d%d",&p1->coef,&p1->expn);
29) head->next=p1;
30) for(i=1;i<m;++i) /*依次输入非零项*/
31) {p1=(Link)malloc(Len);
32) scanf("%d%d",&p1->coef,&p1->expn);
33) p2->next=p1;p2=p1;
34) }
35) p2->next=NULL;
36) return(head);
37) }
38) Position NextPos(Link ha) /*找到当前位置的下一个位置的地址并返回指针*/
39) {Link pa;
40) if(ha!=NULL) pa=ha->next;
41) return(pa);
42) }
43) ElemType cmp(int a,int b) /*比较指针的系数*/
44) {if(a==b) return 0;
45) if(a<b) return -1;
46) if(a>b) return 1;
47) }
48) Position Before(Link ha,Link qa) /*找出当前位置的前一个位置并返回指针*/
49) {Link p;
50) p=ha->next;
51) while(p->next!=qa)
52) { p=p->next;}
53) return(p);
54) }
55) Position AddPolyn( polynomial *la, polynomial *lb) /*对二个多项式进行加法运算*/
56) {Link qa,qb,ha,hb,q,pb,pa;
57) ElemType a,b,c,d,sum;
58) ha=la->head; hb=lb->head; /*指向头结点*/
59) q=ha;
60) qa=NextPos(ha); qb=NextPos(hb); /*指向当前结点*/
61) while (qa!=NULL && qb!=NULL)
62) {a=qa->expn; b=qb->expn;
63) switch(cmp(a,b)) /*进行指数的比较及加法的运算*/
64) {case -1: /*pa中的指数值小*/
65) qa=NextPos(qa); break;
66) case 0: /*两者的指数值相等*/
67) c=qa->coef;d=qb->coef;
68) sum=c+d;
69) if(sum!=0) /*不为零,则修改当前结点的系数值*/
70) {qa->coef=sum;
71) qa=NextPos(qa);qb=NextPos(qb);break;}
72) else /*删除当前结点*/
73) { pa=Before(ha,qa);
74) pa->next=qa->next;
75) qb=NextPos(qb);
76) qa=NextPos(qa); break;}
77) case 1: /*pa中的指数值大
78) pb=(Link)malloc(Len);
79) pb->coef=qb->coef;pb->expn=qb->expn; /*插入当前结点*/
80) pb->next=(qa->next);
81) qa->next=pb;
82) qb=NextPos(qb);break;
83) }
84) }
85) if(qb!=NULL) qa->next=qb; /*链接剩余结点*/
86) return(q);
87) }
88) void print(Linklist *la) /*输出结果*/
89) {Link p;
90) p=la->head;
91) p=p->next;
92) while(p!=NULL)
93) {printf("coef:%3d,expn:%3d ",p->coef,p->expn);
94) p=p->next;}
95) }
96) main()
97) {Linklist *la,*lb,*lc;
98) int m,n;
99) la=(Linklist *)malloc(LEN);
100) lb=(Linklist *)malloc(LEN);
101) lc=(Linklist *)malloc(LEN);
102) printf(" Please writer the number of the struct la:");
103) scanf("%d",&m);
104) printf(" Please writer the number of the struct lb:");
105) scanf("%d",&n);
106) la->head=CreatPolyn(m);
107) lb->head=CreatPolyn(n);
108) lc->head=AddPolyn(la,lb);
109) printf(" *** *** *** *** *** *** *** ");
110) print(lc);
111) printf(" *** *** *** *** *** *** *** ");
112) getch();
113) }
合上手头的案卷，终于把第二章的算法全部整理出来了，好艰难啊，看着外面的天空，漆黑一片，11：20分，Walkman 中又响起了一首熟悉又伤感的歌曲。寂寞的夜里，忽然又变得心潮澎湃起来。于是打开编译器，写出了一个伤感的程序
