博文
线性表(2006-04-09 01:16:00)
摘要: 现在数据结构学到了第6章了,现在对以前的各种基本的数据结构做下总结:首先是线性表,线性表是n个数据元素的有限序列,它又包括顺序表和链表。线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素,其动态分配存储结构可如下表示:
#define LIST_INIT_SIZE 100 //存储空间的初始分配量
#define LISTINCERMENT 10//存储空间的分配增量
typedef struct
{
ElemType *elem;
int length;
int listsize;
}
顺序表的构造不太难,只要给elem一个指向存储空间的值即可,其他的操作不用多说大家应该都知道。
以下主要浅谈下链表,最开始其实链表应该是在大一就学的,由于某些原因而错过了,寒假在家自己看了下C中的这一章,所以今年开始学这个时感觉不是太费力,但这也给自己带来了不小麻烦,以至课程讲到第四章时自己又重新回到前面去看线性表。开始学时只是想到这个东西是怎么样的,没有去深入研究它为什么是这样的,当时也是仗着自己先看过的,幸亏现在发现得早自己的错误。
链表与线性表相比最大的特点就是它是用一组任意的存储单元来储存线性表的数据元素,储存单元可以连续也可以不连续。因此为了表示没个数据元素与其后继元素之间的逻辑关系,对每一个数据元素来说除了存储其本身的信息外,还需要一个存储一个指向其直接后继的信息。这两部分信息组成了数据元素的存储映象,即结点(Node)。它包括数据域和指针域。单链表的存储结构可表示如下:
typedef struct
{
ElemType data;
struct LNode *next;
}LNode......