线性表的链式实现

这学期开了数据结构这门课。对于学软件工程的学生来讲，认真、切实的学好它是非常必要的。LUPA开源社区gO2?sl [IdqN#h
最近一次上机时，我把线性表的链式形式实现了，但还存在很多问题，希望大家能给我指点一二。
}2{3}#G/xk d!I)Z0$cat include.h
,rhC-vb%S2A(].~0#include <stdio.h>
(t(Vn#sn!D[#yZ
?0#include <stdlib.h>
Vtj1N%vd/o0#include <malloc.h>
vBd)]7X0#include <string.h>
yv t7Y(_x@{0
JL6P#Ur0$cat Status.h
6|&k,FGf9AI#J0#define TRUE 1
A;}#b]0G~hO0#define FALSE 0LUPA开源社区'H#fm+m*is
#define OK 1LUPA开源社区De\8Z
t9T}6gL
#define ERROR 0
3_e%S ],^/t6f j0#define INFESIBLE -1LUPA开源社区1wlRmwf4b
#define OVERFLOW -2

typedef int Status;
3q%e;Q Y3Nj E2g/r0
F{6D e{3h0$cat struct.hLUPA开源社区z${Sq0f:kE4INB
#include "include.h"
5EqFhpO)t0#include "Status.h"

typedef struct Node{LUPA开源社区b;FY@P
 int data;
\7](V!F+F9Xb%sv0 struct Node *next;LUPA开源社区@x2u-MR mk
}LNode,*LinkList;LUPA开源社区*OP1C2H}-M8KqC
LUPA开源社区
g
n4N]-L;x7wY
$cat Linearlist.c
+ZNJ3RqU P0LUPA开源社区m$}n'mM
LinkList InitList();
s8I_RC'J#J"s\0void DestroyList(LinkList L);
3kz2f B Bz0LinkList Clearlist(LinkList L);
p{%b"h$g0Status ListEmpty(LinkList L);
1B/r|iu;MNJ-mIk0int ListLength(LinkList L);LUPA开源社区9ZbP[\3R
LNode GetElem(LinkList L,int i);LUPA开源社区(xfx9GCW$h
Status Compare(LinkList p,LNode e);LUPA开源社区$i[,l`
g)[&L.L
int LocatElem(LinkList L,LNode e);
+X%L,p1G8R7_0LinkList PriorElem(LinkList L,LNode e);LUPA开源社区NG|c'AO;r1I;cT5u
LinkList NextElem(LinkList L,LNode e);LUPA开源社区3Jy6}I+X,N~7l,X
LinkList ListInsert(LinkList L,int locate,LNode e);LUPA开源社区3^)n
d%b M L
LinkList InsertHead(LinkList L,LNode e);LUPA开源社区G:k2Onv
LinkList InsertTail(LinkList L,LNode e);LUPA开源社区*DoY%y`:] d
J
void Vist(LinkList p);LUPA开源社区D7Z;o6oTj6e6k
void ListTraverse(LinkList L);

LinkList InitList()LUPA开源社区!k9O+_ T.{zj M
{
Up}S^0 LinkList L;
d"F^}FW} a&p0 L=(LinkList)malloc(sizeof(LNode));
Z3C)}N^/e:{0 if(L==NULL)

z/U-l*A]bD,Fwh0 {
_:Tte9K{#M$HP0  printf("Creat L point fail!\n");LUPA开源社区:?'J|o(h
  exit(1);
+Z;i? Z!n}z0 }
]
?k'?P&A QuzM0 L->data=0;LUPA开源社区A!{"@ M(s|
 L->next=NULL;

?`qO~
H&q#I*T0 return L;LUPA开源社区+ym6zxz5O%{4z B.r
}
\3Y l{}L$BL],R0void DestroyList(LinkList L)LUPA开源社区#D"T-EmHwZ'zs
{
c },mB"?-~}0 LinkList p;LUPA开源社区2~0c5Pc`@
 for(p=L->next;p!=NULL;p=p->next)
5a/w8b V4O3z
~0 {
$`.v2M F)y0  L->next=NULL;LUPA开源社区Kmj-b`c
  free(L);
!TK`S p0  L=p;
B7mAQg)r0 }
XF0`7ztzl1B8F0}LUPA开源社区v:u
I3bMn"~:? I&n t8_
LinkList Clearlist(LinkList L)LUPA开源社区"M] e#V2kP
{LUPA开源社区"x?pd~8|3C
 LinkList p;LUPA开源社区%k5CT+?D7_
 for(p=L->next;p!=NULL;p=p->next)
3g7xvl*\YN eY7lP0  p->data=0;
!@ jZy
\*Q4x0 return L;LUPA开源社区HNrdIYxwA!C
}
5n!HQ%h(X;N3dF9g0Status ListEmpty(LinkList L)LUPA开源社区tX0p(}7ws0R[
{
8~CW3H?b5?0 Status status;LUPA开源社区,xX4xN&i3w*b0W
 if(L->data==0)
SYJ&Az l2rz0  status=TRUE;
Zy
F%L`3rer E,^0 else LUPA开源社区FNJ:w ^\x/T
  status=FALSE;LUPA开源社区@8q,lxmO
 return status;
[1T}q({0} LUPA开源社区/W6X#Yd*X'^5gpdV
int ListLength(LinkList L)LUPA开源社区 a9Z:p&y l/Vd1q
{
#~v$wh.rx0k0 return L->data;LUPA开源社区&r}'A.D;wq5{
}
)y,H,p8v(N0LNode GetElem(LinkList L,int i)
*[!CE k a^S0{
Osk[P8j:Z/C*R0 LNode s;
0kp aIb,Z3j Dx0 LinkList p;LUPA开源社区mD-U&f9z;y4F/Y
 int j;
2J!R[Q;xM-^5t0 if(i<1||i>ListLength(L))
@9McG'SCs!p0 {
MT;V#C"y)L^0  printf("%d don't exit in the lenght.\n",i);LUPA开源社区
r4F&dq$?(H5E9t Yj
  exit(1);LUPA开源社区X2P4d9\.vX/B6c
 }LUPA开源社区&Ya?F~zL(L
 else LUPA开源社区,D5XT#X[U?*Vh
 {
t E0G%ydv~0  for(j=1,p=L->next;j<i;p=p->next,j++)
H1T u$nnJ0   ;
,sM#{Z8h.J0  s.data=p->data;
B7jT3Bbx0 }
K7Na A[0 return s;LUPA开源社区? K#verK"` u
}LUPA开源社区ljR(J_7{!k(]
Status Compare(LinkList p,LNode e)LUPA开源社区x \kvh mh
{LUPA开源社区.n4B(I [{5FSr
 Status status;
Vmz5V"C]`0 if(p->data==e.data)LUPA开源社区'x5]T,E7Xex+n
  status=TRUE;LUPA开源社区5D;N j$WC1Zt%L
 else
AU#qB}-Y0  status=FALSE; LUPA开源社区S:W^qW,w;gD_ x
 return status;
E~Du2_p-mLf0}
U;Rk1TeAC7w0int LocatElem(LinkList L,LNode e)
-`Br].tN0{LUPA开源社区 n9g AP.?_N!|%V
 Status s;
-F%S5p0|4I\&D0 LinkList p;LUPA开源社区:ziRI{/V
 int locate;
FP$P W2Dc1c0 int i;
lD*I|!\0 for(i=0,p=L;i<ListLength(L);i++,p=p->next)LUPA开源社区 ynFvG5D
 {
BOJO\
u&W&D0  if((s=Compare(p,e))==FALSE)
4T2}zIhed2J-a0   continue;LUPA开源社区-c7u/GOb/cD
  else
Bh @$ktK.f0  {
[4r%a3J#w*k]0   locate=i;LUPA开源社区fzL.J d Z\O l
   break;
;R-Fk2@ H+W0S0  }LUPA开源社区.|!t/\Ud6f
 }LUPA开源社区'qSEi` _nC
 if(i>=ListLength(L))LUPA开源社区(v5lTV5|d t[
 {LUPA开源社区i)IQ$@"Sq L
  printf("%d don't exit in the LinkList.\n",e.data);
?@-u5x"QH
qz
D*Q0  exit(1);
_Z#J[3DS0 }  
!{y6R~?0Kgz}R-P h'[0 return locate;LUPA开源社区-Rk-n1`5[L5j)K3RQ
}LUPA开源社区 e[7|Tv
LinkList PriorElem(LinkList L,LNode e)
*L}E?u E+N)nb0{LUPA开源社区rln"V2GdA
 LinkList p=NULL;LUPA开源社区n4@1D9Z|dt\ }
 int locate;
~^G.Qo0 int i;LUPA开源社区%|/L7^+|AU/b
 locate=LocatElem(L,e);LUPA开源社区;Lgp H+WP$m U
 if(locate==0||locate==1)LUPA开源社区:O&g el.lj+Y
 {LUPA开源社区Z&~E2_V?gi}
  /*printf("PriorElem:locate=%d",locate);*/
,u4v)s5p5L+x|0  p=L->next;LUPA开源社区F%M2i(Y v
 }
bw|/Z"ds.ni2q0 else LUPA开源社区 v/xk
J H]k @`
 {
6ry:aJH#]3tc4W0  for(i=1,p=L->next;i<locate-1;p=p->next,i++)
VN:QB"{e W~0   ;
0}:O#f!l@g0 }
Q.r&Cd
D,z{+D1I"e0 return p;  
3^Q+q@gf` p6b*`0}
XXgAYl`4y0LinkList NextElem(LinkList L,LNode e)
$O"Sd F*N `+Ou2{0{
"E0c(@ };k"L0 LinkList p=NULL;LUPA开源社区hG._9U h2YigC-b%gJ
 int locate;LUPA开源社区t@*e[.OE7z*s j
 int i;
m,g-J6Fg:S3S} F
h0 locate=LocatElem(L,e);
O&Re.q*P0 if(locate>=ListLength(L))LUPA开源社区0E#[ n)?-q%^
 {LUPA开源社区xv1e-t;HC:T
  /*p=NULL;
:w+R.w N$NT)xz0  exit(1);*/
@9b({5hc$LV8KP8C0  for(i=1,p=L->next;i<ListLength(L);p=p->next,i++)
4i(jsRVs@0   ;LUPA开源社区(f6|!}wch BGW%~R
 }LUPA开源社区#HrS,t)?@+f!x4odo
 else LUPA开源社区v$Z;a9Kp*gS)u5J
 {LUPA开源社区p^T4eyG1L,hb
  for(i=1,p=L->next;i<locate;p=p->next,i++)LUPA开源社区{,c BKV
]ef `
   ;LUPA开源社区
Q@x"_#F!n*U5V?*N
  p=p->next;
4`:qVxZ$bSG0 }LUPA开源社区Y[m
M:v
 return p;LUPA开源社区 e+]R'd2k*z-VL
}
v"^o;Z.A jL0LinkList ListInsert(LinkList L,int locate,LNode e)LUPA开源社区)px-fj\!s7F:i
{
FCrC
~;Fz0 LinkList p,pre;

H{S QtBZ B,}0 p=(LinkList)malloc(sizeof(LNode));
d*|3e-{HCi sh0 if(p==NULL)LUPA开源社区7y^[)Yt%cf
 {
"F#B`'Z7G&{Y.O0  printf("Creat p Node fail!\n");LUPA开源社区7Am ^j0nmEd\
  exit(1);
/pl oJ)RDk0 }/*printf("GetElem(L,locate)=%d",GetElem(L,locate).data);*/
0aa4d0uB6^2^M0 pre=PriorElem(L,GetElem(L,locate));
*w(`X:Ndu3v0 printf("%d",pre->data);LUPA开源社区g-\f(y:G
 if(pre==NULL)LUPA开源社区 qEDgEP z X
 {LUPA开源社区1d(L"z.xQ2J'y:R
  printf("pre return Error!");LUPA开源社区7ib @S%x7\T`%q7Yo
  exit(1);
_O#k;xy \9W0e]3R0 }
@j%W8O)H0 p->data=e.data;
%B @DO%{&M-WN
A0 p->next=pre->next;
hoOA$mQ2PY'n0 pre->next=p;
(r?J\DB0 L->data+=1;
R
y!eH@6X!\m*A0 return L;LUPA开源社区%L*V$h1_ aD
}
"H+E hX {ANpP v0LinkList InsertHead(LinkList L,LNode e)LUPA开源社区w;F"cw!rX
{LUPA开源社区;@6p%X}uJ@)H
 LinkList p;
&Ab1nHh.VC.P6i9w0 p=(LinkList)malloc(sizeof(LNode));LUPA开源社区!w(y.[.r;`ZwZ5y
 if(p==NULL)
tg'we`9w%[G[0 {
7TU,g*t2MR?0  printf("Creat Node fail!\n");LUPA开源社区s*p[#Hl0H6``W/{+t
  exit(1);
TA}6{.K/f"|0 }
~8q!A UM|%w Y!K{0 p->data=e.data;
f0x!Ky/o1e0 p->next=L->next;LUPA开源社区s+U2s`(_ k] YL
 L->next=p;
u G0PF;A5_/Y"j,`\b?b0 p=NULL;
Xcoz(o#[R,C0 L->data+=1;
:b$q {(cm|1j0 return L;LUPA开源社区 cSX8B/@
} LUPA开源社区cX6LU }%~
LinkList InsertTail(LinkList L,LNode e)
,k{+@ HIQDYn W;T(|0{LUPA开源社区
b$c,A%\4~[{"ncE
 LinkList p,tail;LUPA开源社区O+|%F
s)kKsei!n
 p=(LinkList)malloc(sizeof(LNode));LUPA开源社区2Nz*u(K[5o'pj8Q*G,s3K?h
 if(p==NULL)
s
Wmn:~2q{0jr0 {LUPA开源社区,y5ZP-F:|!bUm
  printf("Creat Node fail!\n");LUPA开源社区bHkb7t{V@hHe
  exit(1);
H~1?$e%j1g-x0 }
,k|fq wZ0 p->data=e.data;
L5\h$\
]l~0 p->next=NULL;
OA Em%kBf7fN\0 for(tail=L;tail->next;tail=tail->next)
z
T"y)[s
`&lLQ0  ;LUPA开源社区-yX5o"a0D%m
 tail->next=p;LUPA开源社区6^1Jr'G0M4V
 L->data+=1;LUPA开源社区&g Iv}8C9x
 return L;LUPA开源社区1vdH3w)^1I'y V;]
}
Q&g!c9g&bRCMV:i0LinkList ListDelete(LinkList L,int locate,LNode e)
"|*Z4P!b
S/s0{
8]h\3IO2|Y0 LinkList p,pre;LUPA开源社区3`Pt'Ep@:@
 pre=PriorElem(L,GetElem(L,locate));
%o#g?8tS9F{H0 if(pre==NULL)
;Sl9rs|2_o/N5t,b9{M}0 {
-o.t S:A?'|?:Q;H0  printf("ListDelete:pre==NULL\n");LUPA开源社区"U)^^"L R2od8XW9og
  exit(1);
,?3y%D
E#IDb0 }LUPA开源社区%_h[C/V:Bu
 p=pre->next;LUPA开源社区$?M:YII-y'D,@7Q(n Un
 pre->next=p->next;LUPA开源社区KA `AY+V(lW'd)Csb
 e.data=p->data;
~$g+q#x3W;r0 printf("%d has been delete\n",e.data);
3qaudWh0 free(p);
"nSEU ^
^:Bc;OJG0 L->data-=1;LUPA开源社区Zt{!ty,j"|4W
 return L;LUPA开源社区r[9l'}};V ~-{4`*g7kE
}
1I Om2hyt/Wqa|1f0void Vist(LinkList p)
N
rAy8KL0{LUPA开源社区SH!u \`
DP
 printf("The Elem is %d\n",p->data);
3V\#q[:rDwTB0}
eBh^-aG0void ListTraverse(LinkList L)
*t4X!y'}
ta6I s1zB@,J+K0{
0a$NqJI bRY0 LinkList p;
Z,{H(c0J6{u0 int i;LUPA开源社区u a#m*Y`
 for(i=1,p=L->next;i<=ListLength(L);i++,p=p->next)LUPA开源社区^+fMC1m KgP7r2b
  Vist(p);LUPA开源社区[c2O_+jW&]u
}
-l$@%Y"}*Ir)]0$cat test.c
m&G;C(A(B5T"k0#include "include.h"LUPA开源社区FK;DWJ)P9U
#include "Status.h"
:Mr/E,?d%F!yxq0#include "struct.h"LUPA开源社区2T`lbf)C;d0o
#include "LinearList.c"

int main()
\H_%D9fw/t)m:T$z0{LUPA开源社区
r*Ja x0o5Yy?3BK3D
 LinkList head/*,tail*/;
sh0k8f)y0 LinkList p/*,pre,pTemp*/;
Fz2SmH$[*zO
r0 /*LinkList headOld;*/
W2c1AG7z\9`ge0 LNode e,test;
(Tj1zxEH/L0 char ch;
Gi)bI(?0 int flag=1,i;LUPA开源社区t*k
v pa#vvo
 head=InitList();LUPA开源社区_bd"`3nOO4oH8k/d]
 printf("Input data(quit for 'q'):");LUPA开源社区%xt5~#u A.og
_(ff
 scanf("%d",&e.data);LUPA开源社区yMDg)got~
 {
Yvk"I:a0 while(flag==1)
,jpL aKZ `0  if((ch=getchar())=='q')
&qV \Ij/s B0   flag=0;LUPA开源社区)j CoC6R8WhK`B3Qg
  elseLUPA开源社区%Ba+j!{i.jz
  {
8`.yT] T~+C0   head=InsertTail(head,e);LUPA开源社区 {(^/c+N*m9A2[J
   puts("save successful");LUPA开源社区5c {/v&Zk|5R
  }LUPA开源社区#q%g h(_+\j
  if(flag!=0)
VM*}M'?0  {
d"Tw2M8NA.~:[0   printf("Input data:");
&y/L_/h%Y0   scanf("%d",&e.data);
Ure:\U3_0  }LUPA开源社区z:?1L Y;e N1Ic;R
  elseLUPA开源社区#r@0fxE:}`
   break;LUPA开源社区2j?1^~'Xe,tP
 }LUPA开源社区6q{#f;X_8['g
 puts("the List is:");
wXy-p
]n0 ListTraverse(head);
C;LgK6`0 printf("List length is%d\n",ListLength(head));
Z|:Io)av_'Y0 printf("input i=");
BC`"C2U1y k0 scanf("%d",&i);
*A5M8V9OT@$^)v0 printf("%d",GetElem(head,i).data);LUPA开源社区m4KB1n}UJ
 printf("\ntest.data=");LUPA开源社区$b%cC~cdvhE
 scanf("%d",&test.data);LUPA开源社区9zv]3h)HhG R
 printf("locate=%d",LocatElem(head,test));LUPA开源社区;U }*p
|8q%KN
 /*printf("delete i=");LUPA开源社区a.A&g-e5RDj"v0?+t
 scanf("%d",&i);
"j U_R&]Jn8kJ4o{0 head=ListDelete(head,i,test);
9M
ZDJ/DNG0 ListTraverse(head);*/LUPA开源社区|7QW/sto
 printf("List length is%d\n",ListLength(head));LUPA开源社区"Q^3G#Maq
 printf("input insert data:");LUPA开源社区P3wL%m Rk D
 scanf("%d",&test.data);LUPA开源社区0qZH3Q"Y$s!C
 head=ListInsert(head,5,test);LUPA开源社区5}RNSo2?.y
 ListTraverse(head);LUPA开源社区5R"v2\4zp0Q5S?
 p=PriorElem(head,test);LUPA开源社区UAl2eB#tokb
 printf("\npriodata is:%d",p->data);LUPA开源社区a2~!`4]h Kjr
 p=NextElem(head,test);LUPA开源社区O^-QLm3k)H/Q
 printf("\nnextdata is:%d",p->data);
;`/?'L wY0|y.DM q0 DestroyList(head);LUPA开源社区0{JO-pe l$W%n
 return 0;
3f@4Zd6lr0}LUPA开源社区/xr-VGIae)?)hK
参见《数据结构（C语言版）》严蔚敏 吴伟民 第19页LUPA开源社区g+cqN3I