用C语言描述数据结构

　　学好计算机，主要要从三个方面做起，其中，第一步就是要学好各种语言，这是第一步，对各种语言有一个大体的了解;然后就是数据结构了，它是计算机中的一门核心的课程，也是一门信息计算;在最后本人认为就是算法了，它也是这三部中最难得一步了，要学好计算机，做一名优秀的程序元，这三步是最基本的，然后再是在他们的基础上层层深入。

　　在过去的一年之中，我对计算机的语言有了一个大体的了解，在前一段时间，我自学了数据结构，下面，谈谈我自学的数据结构的看法，在接下来一段有人指点的时间里，再来纠正以前对数据结构的错误看法。

　　数据结构是一个比较抽象的东西，他的任务是从各种实际的问题中归纳，抽象出个对象的特征，对象之间的相互关系，在选择合适的数据结构来组织，、储存和选择相应的算法。其中，最重要的还是一种抽象思维的转换，需要有一种归纳的思维，在初学的时候，我选择了在理解的基础上背一些比较典型的数据结构，比如:线性表，队，饯的储存方法等，最后发现一些其他的东西也可以类似。

　　用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(“

”);

　　}

　　(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("

");

　　}

　　(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

　　　}

　　}