| 以文本方式查看主題 - 曙海教育集團論壇 (http://www.scb-ycwb.com/bbs/index.asp) -- C語言開發 (http://www.scb-ycwb.com/bbs/list.asp?boardid=62) ---- 用C語言描述數據結構 (http://www.scb-ycwb.com/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語言描述數據結構可以分為以下幾部分：線性表，隊，餞，廣義表，然后是樹，圖，最后還有遞歸，串，查找，排序。其中較為典型的例子有走迷宮，漢諾塔，出入隊列哈夫曼編碼等。 現行表示具有相同特征的數據元素的一個有限序列，儲存方式有兩種：順序儲存——順序表，鏈式儲存——鏈表。" _3 V) M4 |3 ^6 X (一)順序表儲存結構，用C語言來運行各個基本運算的分類： Typedef char ElemType /*將字符性重新用ElemType來定義*/ #define MaxSize 99 /*用宏定義來定義MaxSize*/) n- t9 ~2 X7 S c Typedef struct8 ?# \\+ s+ T$ { { ElemType elem[MaxSize]; /*定義一種為SqList的結構體類型*/ Int length; }SqList;" { s- |( E* s9 ?- A" Q (1) 初始化線性表0 D& d J, ^ ]7 D: Q* e( W Void InitList(SqList *&L) /*將L定義為SqList類型*/ {4 Q2 e! a9 l* V2 `; J+ x L=(Sqlist *)malloc(sizeof(SqList)); /*在內存的動態區分配一個長度為n個 L->length=0; 長為sizeof的連續空間*/ }! `( l, D+ O\' b; I9 Q1 S9 M9 s { (2) 銷毀線性表 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的儲存空間*/ }( @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 { Return(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 { Return(L->length);! l7 P/ S# I+ ?) t" u H. b/ s } (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; if(ListEmpty(L)) 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”); } (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*/ {. d& P- X& H) n6 x If(iL-length) Return 0;2 d5 ~; t; H2 L else {( p8 H4 z5 a0 _4 b; X e=L->elem[i-1]; return 1;* Q. G/ p+ l7 @0 @4 F } 0 U. I\' W- q0 f# ~2 q (7) 按元素值查找（查找第一個與元素值相同的元素的位置） int 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; while(ilength&&L->elem!=e) /*i的值存在的范圍*/ i++;$ z, p# B3 I- O# _" h# z if(i>=L-length) return 0;4 n7 g5 \\7 W4 v\' o; ` else return i+1; } (8) 插入數據元素 int ListInsert(SqList *L,int i,ElemType e) {6 H" W3 j* W- L2 v+ V2 Y& G% s int j; if(iL->length+1) return 0; i--;4 I% c. w8 }9 N for(j=L->length;j>1;j--) L->elem[j]=L->elem[j-1]; /*首先出一個空的位子，然后前面的值依次4 M) J: T( V6 K5 V! @ L->elem[e]; 覆蓋后面的值，即將前面的支附給后面的值*/ L->length++; return 1;& p$ W\' i) L+ z4 k } （9）刪除數據元素 int ListDelete(SqList *L,int i,ElemType &e)\' k. J9 [0 { l x; [ {1 |. M7 T* G* L6 Z# Y- I int j; if(iL->length+1) return 0; i--;# @! Q) i, {6 [ e=L->elem;# |( \\/ P% I1 |; H6 u for(j=i;jlength-1;j++) L->elem[j]=L->elem[j+1]; /*與插入數據元素基本相似*/2 L\' p+ k5 k, p L->length--; return 1; } 以上是數據結構關于順序表的各種有關的儲存方式，與順序表對應的是鏈表，它也是一種非常重要的儲存方式。 B) G% L; Q- P1 d 在初次接觸到c語言的時候已經對鏈表有了大體的了解，它主要是由結點和指針域組成，指針指向下一個結點。3 l/ ~& [$ u. s# ^0 L （二）單鏈表的運算的實現 Typedef char ElemType #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; }LinkList; (1)初始化線性表 void InitList(LinkList *&L) {+ F$ y* a6 x( i* ^ Z L=(Linklist *)malloc(sizeof(Linklist)); /*創建頭結點*/ L->next=NULL; } （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) {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; free(p); /*釋放最后一個p*/8 b, ^0 f0 U4 Y+ s } (3)判斷線性表是否為空？1 k! k6 v% d/ b! i\' y1 u int ListEmpty(LinkList *L) { return(L->next==NULL)6 l# h9 o+ s5 w4 {/ I3 l }" x* V* r& t9 T$ c0 x. f M |