以文本方式查看主题

-  曙海教育集团论坛  (http://sun4.cn/bbs/index.asp)
--  C语言开发  (http://sun4.cn/bbs/list.asp?boardid=62)
----  用C语言描述数据结构  (http://sun4.cn/bbs/dispbbs.asp?boardid=62&id=2410)

--  作者:wangxinxin
--  发布时间:2010-12-10 11:44:16
--  用C语言描述数据结构
学好计算机,主要要从三个方面做起,其中,第一步就是要学好各种语言,这是第一步,对各种语言有一个大体的了解;然后就是数据结构了,它是计算机中的一门核心的课程,也是一门信息计算;在最后本人认为就是算法了,它也是这三部中最难得一步 了,要学好计算机,做一名优秀的程序元,这三步是最基本的,然后再是在他们的基础上层层深入。- t8 D2 T/ B6 g6 |
在过去的一年之中,我对计算机的语言有了一个大体的了解,在前一段时间,我自学了数据结构,下面,谈谈我自学的数据结构的看法,在接下来一段有人指点的时间里,再来纠正以前对数据结构的错误看法。; j0 G/ l! I! H9 g\' D
数据结构是一个比较抽象的东西,他的任务是从各种实际的问题中归纳,抽象出个对象的特征,对象之间的相互关系,在选择合适的数据结构来组织,、储存和选择相应的算法。其中,最重要的还是一种抽象思维的转换,需要有一种归纳的思维,在初学的 时候,我选择了在理解的基础上背一些比较典型的数据结构,比如:线性表,队,饯的储存方法等,最后发现一些其他的东西也可以类似。* c5 ?! A2 R+ y8 z: }3 r$ y
用C语言描述数据结构可以分为以下几部分:线性表,队,饯,广义表,然后是树,图,最后还有递归,串,查找,排序。其中较为典型的例子有走迷宫,汉诺塔,出入队列哈夫曼编码等。
. q8 y1 h( Q7 M0 w/ B现行表示具有相同特征的数据元素的一个有限序列,储存方式有两种:顺序储存——顺序表,链式储存——链表。" _3 V) M4 |3 ^6 X
(一)顺序表储存结构,用C语言来运行各个基本运算的分类:
+ I5 m  C# h; ?- C4 iTypedef char ElemType          /*将字符性重新用ElemType来定义*/
\' L  A, L9 e7 ^) ~: C( c#define MaxSize  99           /*用宏定义来定义MaxSize*/) n- t9 ~2 X7 S  c
Typedef struct8 ?# \\+ s+ T$ {
{
2 r8 r! j& A7 f! X. W8 XElemType elem[MaxSize];      /*定义一种为SqList的结构体类型*/
9 _, c6 o, `& P& E) Z, cInt length;
9 t- _8 C2 O$ E6 t0 E; `}SqList;" {  s- |( E* s9 ?- A" Q
(1)    初始化线性表0 D& d  J, ^  ]7 D: Q* e( W
Void InitList(SqList *&L)     /*将L定义为SqList类型*/
9 ]! x, g% q5 d! ?: r{4 Q2 e! a9 l* V2 `; J+ x
L=(Sqlist *)malloc(sizeof(SqList));   /*在内存的动态区分配一个长度为n个
1 @1 R. {, Z0 \\# [) @/ ~1 nL->length=0;                          长为sizeof的连续空间*/
, t7 \\% o3 u* J- B$ S6 l\' V}! `( l, D+ O\' b; I9 Q1 S9 M9 s  {
(2)    销毁线性表
8 B( }2 G, [2 A2 j$ P        Void DestroyList(SqList *&L). g\' ]; ?7 ~+ L4 J" Q# p5 U
{+ V) j+ O; a( V" }1 s  R9 m% a" D% [
Free(L);                          /*释放L的储存空间*/
0 w! b% l/ W0 }4 V9 X1 W}( @9 E4 `/ {* P1 H5 i0 v
(3)    判断线性表是否为空3 W* _" k0 a  t* @4 f) w6 Q
Int ListEmpty(SqList *L)2 F  ~2 l# x% ^$ |, \\9 v7 A/ o
{
: l1 M+ d! Q1 V) C3 n2 KReturn(L->length==0);( }8 m) _0 \\\' x! l( J6 x
}  S9 ?# U; z# I& r& n& s: H* ?- E
(4)    求线性表的长度- Y: j3 O/ m4 w4 X\' Q! q5 X3 v) e/ {
Int ListLength(SqList *L)\' ^! z6 x. O) \\$ h- ?0 N\' \\# U) n
{
1 t# y4 K0 R$ E  d2 c4 b: ?Return(L->length);! l7 P/ S# I+ ?) t" u  H. b/ s
}
\' d2 Z0 l3 a& |\' g2 S! m1 E. b# P(5)    输出线性表5 O" _- U# S4 S, q1 J; i$ w
Void Displist(SqList *L)" ]- ~: P7 ~( z: _3 {. j
{) q$ J" K. E* N
int i;
* @; Z4 r$ ?5 n* R8 Yif(ListEmpty(L))
: _: l6 H4 U4 `+ [   return;" J) _5 i; C( }* X# |) Y8 n
for(i=0;i$ \\0 U5 ^0 R- Q. n: a
printf(“%c,”L-elem);3 [; X0 n/ T7 i$ }% Y7 F6 B* l
printf(“\\n”);
. U+ R$ c9 g, S1 l# {, f2 v! P}
3 g$ n& T0 G) r& b6 \\9 |; c(6)    求线性表中某个数据元素得值: N0 Z7 K; ~9 w- F( N9 g/ c
比如求线性表的第i个元素的值e. r1 P  r1 ~2 D
int GetElem(SqList *L,int i,Elemtype e)     /*线性表L的第i个元素的值e*/
  _/ p+ \\. T9 |  R{. d& P- X& H) n6 x
If(iL-length)
( B& t0 t/ z7 ~1 Y& eReturn 0;2 d5 ~; t; H2 L
else
3 ~, v( L* G, x      {( p8 H4 z5 a0 _4 b; X
       e=L->elem[i-1];
& J: {, C. v2 {, x( k8 L       return 1;* Q. G/ p+ l7 @0 @4 F
}                                                                                                        0 U. I\' W- q0 f# ~2 q
(7)    按元素值查找(查找第一个与元素值相同的元素的位置)
3 b2 @$ b3 f\' i4 E+ Cint Locateelem(SqList *L,Elemtype e)2 u2 A9 g, k& y7 \\3 Y& ?+ u
{" M9 B1 a; a/ \\+ P% o% w$ D. c
        int i=0;
\' w- E\' U" }* Q; e        while(ilength&&L->elem!=e)      /*i的值存在的范围*/
9 i9 K7 f7 s! _! h  y. n. b- I               i++;$ z, p# B3 I- O# _" h# z
        if(i>=L-length)
: x. m5 ?0 F5 y2 h! x8 x- |9 y               return 0;4 n7 g5 \\7 W4 v\' o; `
        else
! h* M! B, R: t               return i+1;
3 B" b( ^  i. ^0 W6 R0 W}
# E+ c# L- P8 a2 T(8)    插入数据元素
\' t, |3 o  C/ O: M; k% ~int ListInsert(SqList *L,int i,ElemType e)
) A1 x) Y/ O( ?- F; U{6 H" W3 j* W- L2 v+ V2 Y& G% s
       int j;
; l4 _( V. _# w       if(iL->length+1)
( X% P3 O  K9 @9 h              return 0;
: F1 o! a! m4 e: ]. Q       i--;4 I% c. w8 }9 N
       for(j=L->length;j>1;j--)
+ h, a- V, n3 V" N6 T5 R              L->elem[j]=L->elem[j-1];         /*首先出一个空的位子,然后前面的值依次4 M) J: T( V6 K5 V! @
       L->elem[e];                       覆盖后面的值,即将前面的支附给后面的值*/
& n6 C, `. F+ n, z) `1 X       L->length++;
5 E* @6 t. t* T8 \\5 S+ i       return 1;& p$ W\' i) L+ z4 k
}
8 w& I% P\' w$ u3 j7 U/ s6 m! f(9)删除数据元素
+ H( i. ]9 F& I* iint ListDelete(SqList *L,int i,ElemType &e)\' k. J9 [0 {  l  x; [
{1 |. M7 T* G* L6 Z# Y- I
       int j;
" `" I; D+ D* T6 L1 F       if(iL->length+1)
1 \\, M9 K) x+ e8 n              return 0;
: o+ y6 d\' G" r       i--;# @! Q) i, {6 [
       e=L->elem;# |( \\/ P% I1 |; H6 u
       for(j=i;jlength-1;j++)
* s$ e\' L* Q% v, p              L->elem[j]=L->elem[j+1];        /*与插入数据元素基本相似*/2 L\' p+ k5 k, p
       L->length--;
  {7 n( T0 ?7 s% E6 @6 W# x       return 1;
# ?: l2 N\' u0 K% B& m  @! g}
2 D: t# d$ n# l. ?; l5 A* l以上是数据结构关于顺序表的各种有关的储存方式,与顺序表对应的是链表,它也是一种非常重要的储存方式。  B) G% L; Q- P1 d
在初次接触到c语言的时候已经对链表有了大体的了解,它主要是由结点和指针域组成,指针指向下一个结点。3 l/ ~& [$ u. s# ^0 L
(二)单链表的运算的实现
3 V% H! |; p2 H1 ^Typedef char ElemType
3 X7 q: Y& a( q; [  [: Q#define MaxSize 99+ {6 ^4 j- W  c) _! K) t. _* I" k9 a1 Y
Typedef struct LNode1 L* R; i4 Q0 o
{, ]8 W5 R; L- w4 g0 @  G\' j
ElemType data;8 t5 F, v0 Z" I! t, K
struct LNode *next;
; A\' R: B% j& ]9 o; s, `, p}LinkList;
  j" i2 ~* B% x(1)初始化线性表
7 P& R( L) ~- Y, Kvoid InitList(LinkList *&L)
$ p& W, [8 x* p$ [: R" v9 ?( P/ h8 j{+ F$ y* a6 x( i* ^  Z
       L=(Linklist *)malloc(sizeof(Linklist));     /*创建头结点*/
7 Z4 t% S; e1 S* D" @7 x       L->next=NULL;
* e0 ?/ Z/ v4 b! G- J( j4 H8 q}
" C3 e7 ^* h) U1 o0 K3 k(2)销毁线性表1 f0 y$ t" J9 m% W2 T5 }) q
Void DestroyList(LinkList *&L)1 P, G" ~3 G( G$ e# G
{, h3 l) f1 c\' d3 A# p1 F8 t
       LinkList *p=L,q=L->next;           /*p位头结点,q为p的后继结点*// O\' {5 e\' t3 \\3 v; _5 y, g
       while(q!=NULL)
& X7 R! J\' c2 u3 y; d% W. I) [& Z" Q- R       {0 a5 d3 K0 \\\' N\' A& E5 s. d+ L
              free(p);  U6 z$ H: f3 X- I2 F6 ?# R
              p=q;                       /*p逐渐向后释放*/; r3 Q0 d7 c9 u! q
              q=p-next;
7 d: U3 Y; k9 h# Vfree(p);                         /*释放最后一个p*/8 b, ^0 f0 U4 Y+ s
}
# f7 n: L) q* ](3)判断线性表是否为空?1 k! k6 v% d/ b! i\' y1 u
int ListEmpty(LinkList *L)
# z  T" Q3 E& m9 z0 T2 Q9 h{
4 E2 F8 k( Q2 r/ E# O5 L: j       return(L->next==NULL)6 l# h9 o+ s5 w4 {/ I3 l
}" x* V* r& t9 T$ c0 x. f  M