数据结构中之单向循环链表的使用

女爷i 2022-08-14 00:54 151阅读 0赞

在单向链表中，每个节点的指针都指向下一个节 点，最后一个结点的指针域为NULL，如果使最后一个结点的指针返回指向头结点，则使整个链表形成一个环，成为单向循环链表。空单向循环链表是指链表的尾部指向该链表的头，采用单向循环链表在进行结点访问时，针对任意一个结点我们都可以访问到链表中的所有结点，循环链表的这一特性称为链表的可及性。在进行单向循环链表的插入、删除等操作时，其差别仅在于算法中判断表尾结点的条件不再是该节点的后继节点是否为空，而是它是否等于头指针。下面我们看一下单向循环链表的应用。

1、已知单链表表示的线性表中包含3类字符数据：字母字符，数字字符和其他字符。试设计一个算法构造3个单向循环链表来表示这个线性表，使得每个表类只包含同一类字符，且利用原表中的结点空间作为这3个表的结点空间，头结点可另辟空间。摘自：<<数据结构.杨薇薇 张胜利等>>

解析：（1）分别建立字母字符与数字字符的单向循环链表的表头结点，并形成两个空的单向循环链表，其他字符的头结点可以利用原链表的结点。

（2）从表头开始扫描链表，到表尾结束，对遇到的数据分别添加到相应的链表中。

算法如下所示：

/* head 为单链表的头指针，d,c,r分别是数字字符、字母字符和其他字符的循环链表的头指针,
        注意此处传递的是指针的引用，防止在传递指针是进行拷贝*/
    void separate(node* head,node* &d,node* &c,node* r)
    {
    	//首先创建单向循环链表；
    	d=(node*)malloc(sizeof(node));
    	d->next=d;
    	
    	c=(node*)malloc(sizeof(node));
    	c->next=c;
    	
    	node* q=head;
    	node* p=q->next;	
    
    	while(p!=NULL)
    	{
    		if(p->data>='0'&&p->data<='9')           //处理数字字符的单链表；
    		{
    			q->next=p->next;		
    			p->next=d->next;			
    			d->next=p;
    			p=q->next;
    			
    		}
    		else if(p->data>='a'&&p->data<='z'||p->data>='A'&&p->data<='Z') //处理字母字符的单链表；
    		{
    			q->next=p->next;		
    			p->next=d->next;			
    			d->next=p;
    			p=q->next;
    		}
    		else                                    //处理其他字符的单链表;
    		{
    			q=p;
    			p=q->next;	
    		}		
    	}
    	q->next=head;
    	r=q;
    }

2、假设有一个单向链表，表中无头结点也无头指针，已知p为指向其中一个结点的指针，编写算法删除p的前趋结点。

<span style="font-size:18px;">node* del(node* &p)
    {
    	node* q=p;
    	node* r;
    	while(q->next!=p)
    	{	
    		r=q;			//r为q的前驱节点；
    		q=q->next;	
    	}
    	r->next=p;
    	free(q);
    	return p;
    }</span>