1樓
wangxinxin 發(fā)表于：2010-12-10 11:44:16
學(xué)好計算機，主要要從三個方面做起，其中，第一步就是要學(xué)好各種語言，這是第一步，對各種語言有一個大體的了解；然后就是數(shù)據(jù)結(jié)構(gòu)了，它是計算機中的一門核心的課程，也是一門信息計算；在最后本人認為就是算法了，它也是這三部中最難得一步 了，要學(xué)好計算機，做一名優(yōu)秀的程序元，這三步是最基本的，然后再是在他們的基礎(chǔ)上層層深入。
- t8 D2 T/ B6 g6 |在過去的一年之中，我對計算機的語言有了一個大體的了解，在前一段時間，我自學(xué)了數(shù)據(jù)結(jié)構(gòu)，下面，談?wù)勎易詫W(xué)的數(shù)據(jù)結(jié)構(gòu)的看法，在接下來一段有人指點的時間里，再來糾正以前對數(shù)據(jù)結(jié)構(gòu)的錯誤看法。
; j0 G/ l! I! H9 g' D數(shù)據(jù)結(jié)構(gòu)是一個比較抽象的東西，他的任務(wù)是從各種實際的問題中歸納，抽象出個對象的特征，對象之間的相互關(guān)系，在選擇合適的數(shù)據(jù)結(jié)構(gòu)來組織，、儲存和選擇相應(yīng)的算法。其中，最重要的還是一種抽象思維的轉(zhuǎn)換，需要有一種歸納的思維，在初學(xué)的 時候，我選擇了在理解的基礎(chǔ)上背一些比較典型的數(shù)據(jù)結(jié)構(gòu)，比如：線性表，隊，餞的儲存方法等，最后發(fā)現(xiàn)一些其他的東西也可以類似。
* c5 ?! A2 R+ y8 z: }3 r$ y用C語言描述數(shù)據(jù)結(jié)構(gòu)可以分為以下幾部分：線性表，隊，餞，廣義表，然后是樹，圖，最后還有遞歸，串，查找，排序。其中較為典型的例子有走迷宮，漢諾塔，出入隊列哈夫曼編碼等。
. q8 y1 h( Q7 M0 w/ B現(xiàn)行表示具有相同特征的數(shù)據(jù)元素的一個有限序列，儲存方式有兩種：順序儲存——順序表，鏈式儲存——鏈表。
" _3 V) M4 |3 ^6 X(一)順序表儲存結(jié)構(gòu)，用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 cTypedef struct
8 ?# \+ s+ T$ {{
2 r8 r! j& A7 f! X. W8 XElemType elem[MaxSize]; /*定義一種為SqList的結(jié)構(gòu)體類型*/
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( WVoid InitList(SqList *&L) /*將L定義為SqList類型*/
9 ]! x, g% q5 d! ?: r{
4 Q2 e! a9 l* V2 `; J+ xL=(Sqlist *)malloc(sizeof(SqList)); /*在內(nèi)存的動態(tài)區(qū)分配一個長度為n個
1 @1 R. {, Z0 \# [) @/ ~1 nL->length=0; 長為sizeof的連續(xù)空間*/
, 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 QInt 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$ wVoid Displist(SqList *L)
" ]- ~: P7 ~( z: _3 {. j{
) q$ J" K. E* Nint i;
* @; Z4 r$ ?5 n* R8 Yif(ListEmpty(L))
: _: l6 H4 U4 `+ [ return;
" J) _5 i; C( }* X# |) Y8 nfor(i=0;i
$ \0 U5 ^0 R- Q. n: aprintf(“%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) 求線性表中某個數(shù)據(jù)元素得值: 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) 插入數(shù)據(jù)元素
' 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）刪除數(shù)據(jù)元素
+ 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]; /*與插入數(shù)據(jù)元素基本相似*/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以上是數(shù)據(jù)結(jié)構(gòu)關(guān)于順序表的各種有關(guān)的儲存方式，與順序表對應(yīng)的是鏈表，它也是一種非常重要的儲存方式。 B) G% L; Q- P1 d
在初次接觸到c語言的時候已經(jīng)對鏈表有了大體的了解，它主要是由結(jié)點和指針域組成，指針指向下一個結(jié)點。3 l/ ~& [$ u. s# ^0 L
（二）單鏈表的運算的實現(xiàn)
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)); /*創(chuàng)建頭結(jié)點*/
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位頭結(jié)點，q為p的后繼結(jié)點*// 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