用C語言描述數據結構

2019-11-17 05:28:37

字體：大中小

來源：轉載

供稿：網友

　　學好計算機，主要要從三個方面做起，其中，第一步就是要學好各種語言，這是第一步，對各種語言有一個大體的了解;然后就是數據結構了，它是計算機中的一門核心的課程，也是一門信息計算;在最后本人認為就是算法了，它也是這三部中最難得一步了，要學好計算機，做一名優秀的程序元，這三步是最基本的，然后再是在他們的基礎上層層深入。

　　在過去的一年之中，我對計算機的語言有了一個大體的了解，在前一段時間，我自學了數據結構，下面，談談我自學的數據結構的看法，在接下來一段有人指點的時間里，再來糾正以前對數據結構的錯誤看法。

　　數據結構是一個比較抽象的東西，他的任務是從各種實際的問題中歸納，抽象出個對象的特征，對象之間的相互關系，在選擇合適的數據結構來組織，、儲存和選擇相應的算法。其中，最重要的還是一種抽象思維的轉換，需要有一種歸納的思維，在初學的時候，我選擇了在理解的基礎上背一些比較典型的數據結構，比如:線性表，隊，餞的儲存方法等，最后發現一些其他的東西也可以類似。

　　用C語言描述數據結構可以分為以下幾部分:線性表，隊，餞，廣義表，然后是樹，圖，最后還有遞歸，串，查找，排序。其中較為典型的例子有走迷宮，漢諾塔，出入隊列哈夫曼編碼等。

　　現行表示具有相同特征的數據元素的一個有限序列，儲存方式有兩種:順序儲存——順序表，鏈式儲存——鏈表。

　　(一)順序表儲存結構，用C語言來運行各個基本運算的分類:

Typedef char ElemType /*將字符性重新用ElemType來定義*/
#define MaxSize 99 /*用宏定義來定義MaxSize*/

Typedef strUCt
{
　ElemType elem[MaxSize]; /*定義一種為SqList的結構體類型*/
　Int length;
}SqList;
　　(1) 初始化線性表

Void InitList(SqList *&L) /*將L定義為SqList類型*/
{
　L=(Sqlist *)malloc(sizeof(SqList)); /*在內存的動態區分配一個長度為n個
　L->length=0; 長為sizeof的連續空間*/
}
　　(2) 銷毀線性表

Void DestroyList(SqList *&L)
{
　Free(L); /*釋放L的儲存空間*/
}
　　(3) 判定線性表是否為空

Int ListEmpty(SqList *L)
{
　Return(L->length==0);
}
　　(4) 求線性表的長度

Int ListLength(SqList *L)
{
　Return(L->length);
}
　　(5) 輸出線性表

Void Displist(SqList *L)
{
　int i;
　if(ListEmpty(L))
　　return;
　for(i=0;i＜L-LENGTH;I++;)
　　PRintf(“%c,”L-elem[i]);
　　printf(“/n”);
}
　　(6) 求線性表中某個數據元素得值

　　比如求線性表的第i個元素的值e

int GetElem(SqList *L,int i,Elemtype e) /*線性表L的第i個元素的值e*/
{
　If(i<1i>L-length)
　　Return 0;
　else
　{
　　e=L->elem[i-1];
　　return 1;
　}
　　(7) 按元素值查找(查找第一個與元素值相同的元素的位置)

int Locateelem(SqList *L,Elemtype e)
{
　int i=0;
　while(ilength&&L->elem[i]!=e) /*i的值存在的范圍*/
　　i++;
　if(i>=L-length)
　　return 0;
　else
　　return i+1;
}
　　(8) 插入數據元素

int ListInsert(SqList *L,int i,ElemType e)
{
　int j;
　if(i<1i>L->length+1)
　　return 0;
　i--;
　for(j=L->length;j>1;j--)
　　L->elem[j]=L->elem[j-1]; /*首先出一個空的位子，然后前面的值依次
　　L->elem[e]; 覆蓋后面的值，即將前面的支附給后面的值*/
　　L->length++;
　　return 1;
}
　　(9)刪除數據元素

int ListDelete(SqList *L,int i,ElemType &e)
{
　int j;
　if(i<1i>L->length+1)
　　return 0;
　i--;
　e=L->elem[i];
　for(j=i;jlength-1;j++)
　　L->elem[j]=L->elem[j+1]; /*與插入數據元素基本相似*/
　L->length--;
　return 1;
}
　　以上是數據結構關于順序表的各種有關的儲存方式，與順序表對應的是鏈表，它也是一種非常重要的儲存方式。

　　在初次接觸到c語言的時候已經對鏈表有了大體的了解，它主要是由結點和指針域組成，指針指向下一個結點。

　　(二)單鏈表的運算的實現

Typedef char ElemType
#define MaxSize 99
Typedef struct LNode
{
　ElemType data;
　struct LNode *next;
}LinkList;
　　(1)初始化線性表

void InitList(LinkList *&L)
{
　L=(Linklist *)malloc(sizeof(Linklist)); /*創建頭結點*/
　L->next=NULL;
}
　　(2)銷毀線性表

Void DestroyList(LinkList *&L)
{
　LinkList *p=L,q=L->next; /*p位頭結點，q為p的后繼結點*/
　while(q!=NULL)
　{
　　free(p);
　　p=q; /*p逐漸向后釋放*/
　　q=p-next;
　　free(p); /*釋放最后一個p*/
　}
　　(3)判定線性表是否為空?

int ListEmpty(LinkList *L)
{
　return(L->next==NULL)
}
　　(4)求線性表的長度

int ListLength(LinkList *L)
{
　LinkList *p=L; /*將L的頭結點重新定義為P*/
　int i=0;
　while(p->next!=NULL)
　{
　　i++;
　　p=p->next; /*逐漸指向后面的指針*/
　}
　return i;
}
　　(5)輸出線性表

void DispList(LinkList *L)
{
　LinkList *P=L->next;
　while(p!=NULL)
　{
　　printf("%c",p->data); /*打印出那個數據元素*/
　　p=p->next;
　}
　printf("/n");
}
　　(6)求線性表中的夢數據元素的值

int GetList(LinkList *L,int i,ElemType &e)
{
　int j;
　LinkList *P=L;
　while(p!=NULL&&j＜I) p *直到找到與給出的數相等的項*>
　{
　　j++;
　　p=p->next;
　}
　if(p==NULl)
　　return 0;
　else
　{
　　e=p->date;
　　return 1;
　}
}
　　(7)按元素值查找(在單鏈表中從頭開始查找第一個值與e相同的結點)

int LocateElem(LinkList *L,ElemType e)
{
　LinkList *p=L->next;
　int n=1;
　while(p!=NULL&&p->data!=e)
　{
　　p=p->next;
　　n++;
　}
　if(p=NULL)
　　return 0;
　else
　　return n;
}
　　(8)插入數據元素

int InsertElem(LinkList *&L,int i,ElemType e)
{
　LinkList *p=L,*s;
　int j=0;
　while(p!=NULL&&j＜I)
　{
　　p=p->next;
　　j++;
　}
　if(p=NULL)
　　return 0;
　else
　{
　　s=(LinkList *)malloc(sizeof(LinkList)); /*新建一個結點*/
　　s->data=e;
　　s->next=p->next; /*將s插入*/
　　p->next=s;
　　return 1
　}
}
　　(9)刪除數據元素

int DeleteElem(LinkList *&L,int i,ElemType e)
{
　LinkList *p=L,*s;
　int j=0;
　while(p!=NULL&&j＜I)
　{
　　p=p->next;
　　j++;
　}
　if(p=NULL)
　　return 0;
　else
　{
　　s=p->next;
　　if(s==NULL)
　　return 0;
　　free(s);
　　return 1
　}
}

上一篇：C++中的EXIT與析構函數

下一篇：保衛C++：安全STL編程中的受檢迭代子