3.1 链存储结构的定义

　　线性表的链式存储结构中，逻辑上相邻的元素其存储位置不一定相邻，元素间的逻辑次序是由结点的指针域来指示的，结点的存储空间是动态申请和动态释放的，所以不需要预先按最大的存储要求分配连续空间。线性表链式存储时，只要知道该线性表的起始地址，表中的各个元素就可通过其间的链接关系逐步查找到。描述如下：

　　typedef struct Lnode

　　{ ElemType data;

　　struct Lnode *next;

　　}Lnode,*LinkList;

　　LinkList L;

　　3.2链式存储结构基本运算的实现

　　3.2.1 插入运算(后插)

　　首先在表中寻找插入位置i;若没有找到给出错误提示信息;若找到则申请、填装新结点;然后将新结点插入在i结点的后面。算法描述如下：

　　int Insert_LinkList(LinkList &L, int i, int x)

　　{ Lnode *p,*s;

　　p=Get_LinkList(L,i);

　　if(p==NULL)

　　{ printf("参数i输入有误!\n");

　　return 0; }

　　else

　　{ s=(Lnode *)malloc(sizeof(Lnode));

　　s->data=x;

　　s->next=p->next;

　　p->next=s;

　　return 1; }

　　}

　　3.2.2删除运算(按序号)

　　首先在表中查找删除位置i;若没有找到给出提示信息;若找到则删除该结点，只要将其直接前驱结点的指针域修改为指向被删除结点的直接后继结点即可。算法描述如下：

　　int Delete_LinkList(LinkList L,int i)

　　{ LinkList p,s;

　　p=Get_LinkList(L,i-1);

　　if(p==NULL)

　　{ printf("待删结点前结点不存在!\n");

　　return -1; }

　　else

　　if(p->next==NULL)

　　{ printf("该结点不存在\n");

　　return 0; }

　　else

　　{ s=p->next;

　　p->next=s->next;

　　free(s);

　　return 1; }

　　}

　　3.2.3查找运算(按值查找)

　　从表的头结点出发，顺链逐个将结点的值和给定值x作比较;若相等返回首次找到的和给定值相等的结点的存储位置;否则返回提示信息。算法描述如下：

　　int Locate_LinkList(LinkList L,int x)

　　{ LinkList p;

　　int j=1;

　　p=L->next;

　　while(p!=NULL&&p->data!=x)

　　{ p=p->next;

　　j++; }

　　if(p)

　　{ printf("%d在链表中，是第%d个元素\n",p->data,j);

　　return j; }

　　else

　　{ printf("该数值不在链表里。\n");

　　return 0; }

　　}

　　四、线性表顺序实现及链式实现的比较

　　线性表顺序存储结构利用了内存地址空间的一维、线性、连续性等特点，具有存储空间连续，存储密度大;存储结构简单，容易实现;可随机存取线性表中所有的数据元素;访问效率高等优点。适用于数据相对稳定的线性表，如职工工资、人事管理表，学生学籍、成绩表等。但是由基本运算分析可知，在进行插入或删除运算时效率不高。平均起来，每插入或删除一个元素需要移动表中一半的元素，最坏的情况更要移动表中全部的元素。顺序存储结构也不利于存储空间的分配。

　　线性表采用链式存储结构时，插入和删除等运算只需要修改相关指针域，不需要移动数据元素，提高了运算的效率，弥补了线性表顺序存储结构带来的各种不足。但是链式存储结构实现过程中数据结点中的指针域需要占用存储空间、存储密度不高、不能实现随机存取。

　　总的来说线性数据结构的顺序存储实现和链式存储实现各有优缺点，实际应用过程中，应该对所碰到的问题做具体分析，研究问题中所涉及数据的数据特征，从而选择不同的物理实现方式。

　　【参考文献】

　　[1] 严蔚敏,吴伟民.数据结构(C语言版) [M].北京:清华大学出版社,2007.

　　[2] 张晓莉,王苗.数据结构与算法(第2版) [M].北京:机械工业出版社,2008.

　　[3] 李春葆,尹为民.数据结构教程(第3版) [M].北京: 清华大学出版社,2008.

　　[4] 欧建圣.线性表在《数据结构》中重要性分析 [J].武钢职工大学学报.2001,(13).

 2/2   首页 上一页 1 2