|
|
|
《数据结构》自学方法指导 |
|
|
来源： 发布时间：2006-5-29 16:56:48 点击： |
带头结点的单链表如图所示，图中阴影部分表示头结点的数据域不存储信息，但是在有的应用中，可利用该域来存放表的长度等附加信息。
引入头结点后，尾插法建立单链表的算法可简化为：
LinkList CreateListR1(void)
{//用尾插法建立带头结点的单链表
char ch;
LinkList head=(LinkList)malloc(sizeof(ListNode));
//生成头结点
ListNode *s,*r;
r=head;//尾插法初值亦指向头结点
while((ch=getchar())!='\n'){
s=(ListNode *)malloc(sizeof(ListNode));
s->data=ch;
r->next=s;
r=s;
}
r->next=NULL;//终端结点的指针域置空，或空表的头结点指针域置空
return head;
}
10.单链表上实现的查找、插入和删除算法
⑴查找运算
①按序号查找
ListNode * GetNode(LinkList head,int i)
{//带头结点的单链表head中查找第i个结点，若找到(0≤i≤n)，则返回该结点的存储
//位置，否则返回NULL。
Int j;
ListNode *p;
p=head;j=0; //从头结点开始扫描
while(p->next && j<i){//顺指针向后扫描，直到p->next为NULL，或j=i为止
p=p->next;
j++;
}
if(i==j)
return p; //找到了第i个结点
else
return NULL;//当i<0或i>n时，找不到第i个结点
}
②按值查找
ListNode * LocateNode (LinkList head, DataType key)
{//在带头结点的单链表head中查找其值为key的结点
ListNode *p=head->next;//从开始结点比较，表非空时，p初始值指向开始结点。
While(p&&p->data!=key)//直到p为NULL或p->data为key止
p=p->next;//扫描下一结点
return p; //若p=NULL，则查找失败，否则p指向找到的值为key的结点
}
⑵插入运算
void InsertList(LinkList head, DataType x,int i){ //将值为x的新结点插入到带头结点的单链表head的第i个结点的位置上
ListNode *p;
p=GetNode(head,i-1);//寻找第i-1个结点
if(p==NULL)//i<1或i>n+1时插入位置i有错
Error("position error");
s=(ListNode *)malloc(sizeof(ListNode));
s->data=x;
s->next=p->next;
p->next=s;
}
⑶删除运算
void DeleteList(LinkList head,int i)
{//删去带头结点的单链表head上的第i个结点
ListNode *p,*r;
p=GetNode(head,i-1); //找第i-1个结点if(p==NULL||p->next==NULL)//i<1或i>n时删除位置有错
Error("position error");//退出程序运行
r=p->next; //令r指向被删结点ai
p->next=r->next; //释放结点ai，将所有占用的空间归还给存储池
free(r);
}
11.其他链表
接下来，我们简要介绍一下几种衍生的链式存储结构：循环链表和双向链表。
循环链表的特点是将链表中尾结点的指针域指向头结点，使整张链表形成一个环。因此从链表中的任意一个结点出发都可以找到表中其他结点。循环链表的操作与简单链表的操作基本一致，其唯一差别在于判断链表尾的标准是看 p->next 是否等于头指针，而不是看其是否为空。
另一种链式存储结构称为双向链表。在这种结构中，每个结点都有两个指针域，一个指向前驱，一个指向后继。因此在这种链表中求结点的前驱和后继都很方便。这样的设计弥补了简单链表的单向性的缺陷(简单链表的 NEXT 操作的时间复杂度是 O(1)，PRIOR 操作的时间复杂度是 O(n))。 在双向链表中进行插入、删除操作，与在简单链表中操作稍有不同：在简单链表中插入删除只要修改单方向的指针，而双向链表操作则要同时修改两个方向的指针。
12.栈的定义和基本运算
那么栈是一种怎么样的线性表呢? 让我们来看一看栈的定义吧：栈(STACK)是限定仅在表尾进行插入删除的线性表。 因此，对栈来说，表尾端有其特殊含义，我们给它一个名称：栈顶；相应地，表头就称为栈底。当线性表为空时，我们同样也称其为空栈。
假设栈S=(a1，a2，…，an)，则称ai为栈底元素，an为栈顶元素。栈中元素按a1，a2，…，an的 次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此， 栈又称为后进先出(Last in First Out)的线性表(简称LIFO结构)，它的这个特点可用铁路调度站形象地表示。
作为一种特殊的线性表，栈还是与线性表有着诸多联系的，例如和线性表有顺序和链式两种存储结构，类似地，栈也有两种存储结构分别与其对应。
顺序栈即栈的顺序存储结构是，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设指针top指示栈顶元素的当前位置。空栈的栈顶指针值为零。假设用一维数组S[arrmax]表示栈，则对非空栈，S[0]为最早进入栈的元素，S[top]为最迟进入栈的元素，即栈顶元素。当top==arrmax-1时意为栈满，此时若有元素入栈则将产生"数组越界"的错误，称为栈上溢，反之，top==-1意为栈空，在应用中通常作为控制程序转移的条件。下图展示了顺序栈中数据元素和栈顶指针之间的对应关系。进栈操作相当于在顺序表尾部插入结点的操作，出栈操作相当于在单链表的头部插入结点的操作。
与顺序栈相对应的另一种栈称作链栈, 顾名思义它就是以链表为基本存储结构的栈。参照链表的定义，很容易得出链栈的实现方法，同学们可以自己尝试一下。我们着重研究的则是链栈有那些特殊的性质。在学习链表的过程中，我们对链表的性质有了如下的总结：
(1)链表的插入删除操作都很方便；
(2)链表的随机访问性能很差；
(3)链表因为要保存指针域，消耗的空间较大；
(4)链表的结点动态分配释放机制使得空间实际利用率大大提高。
我们再针对栈的特点结合上述性质来看看链栈有那些利弊：因为栈的出入的限制上述第一点的优势在链栈中表现不出来，而又因为栈的访问仅限于栈顶元素，上述第二点的缺点也不明显。倒是后两点尤其是第四点成为了链栈的主要特点。链栈因为能够进行结点的动态分配，因此一个应用程序中的多个链栈能够很容易的实现空间共享。由此可见，对栈这一种元素多变的数据结构来说，链式存储结构似乎更适宜些。对于链栈，进栈操作相当于在单链表的头部插入结点的操作，出栈操作相当于在单链表的头部删除结点的操作。
13.队列的定义及基本运算
和栈相反，队列{Queue)是一种先进先出(First in First Out，缩写为FIFO)的线性表。它只允许在表的一端进行插入，而在另一端删除元素。这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端叫做队尾(rear)，允许删除的一端则称为队头(front)。假设队列为q=(a1，a2，…，an)，那么，a1就是队头元素，an则是队尾元素。队列中的元素是按照a1，a2，…，an的顺序进入的，退出队列也只能按照这个次序依次退出，也就是说，只有在a1，a2，…，an-1都离开队列之后，an才能退出队列。
由于顺序队列中还存在"假上溢"现象。所以为了克服这种现象的方法就是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界(QueueSize-1)时，其加1操作的结果是指向向量的下界0。
If(i+1==QueueSize)//i表示front或rear
i=0;
else
i++;
利用"模运算"可将上述操作简化为：
i=(i+1)&Queusize
然而，在循环队列中又出现了一个新问题：如何判定队满和队空？本新闻共 6页,当前在第 3页 1 2 3 4 5 6 |
|
|
|
