/*
* 单链循环链表：终点的指针域改为指向头节点
* 采用尾指针表示单链循环表：查找开始节点和终端节点都很方便
*/
#include<iostream>
using namespace std;
class Chain;
class Node{
friend class Chain;
private:
char _data;
Node* _next;
};
class Chain{
public:
Chain();
bool Find(int i, Node*& x);
bool Insert(int i, char& x);
bool Delete(char x);
ostream& display( ostream &out );
friend ostream& operator << (ostream &out, const Chain &x);
private:
Node* _head;
int _length;
Node* _raear;
};
Chain::Chain()
{
_head = new Node;
_head->_next = _head;
_length=0;
}
bool Chain::Find(int i, Node*& x){
if(i<0 || i>_length) {cout << "out of index..." << endl; return false;}
Node* p = _head;
while(i--) p=p->_next;
x = p;
return true;
}
bool Chain::Insert(int i, char& x){
Node* pre_node; //store the address of node i-1
if(Find(i, pre_node)==false) return false;
Node* tmp = new Node;
tmp->_data = x;
tmp->_next = pre_node->_next;
pre_node->_next= tmp;
if(tmp->_next== _head) _raear = tmp; //updata _raear
_length++;
return true;
}
ostream& Chain::display(ostream &out){
//IsEmpty?
int i= _length;
if(i==0) return out;
Node* p = _head->_next;
while(--i){ cout << p->_data; p=p->_next;}
return out;
}
ostream& operator<< (ostream &out, Chain &chain){
chain.display(out);
return out;
}
int main(){
char str[] = "su fang";
Chain w;
for(int i=0; str[i] != 0; i++)
w.Insert(i, str[i]);
cout << "input: " << str << endl;
cout << w << endl;
return 0;
}
采用尾指针表示的单链表
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 一般来说，喜欢站立的人，比喜欢躺着或或坐着的人，身材更好。与躺着的姿势相比，站姿所消耗的能量要多出10%。而单腿站...
- 普通方法： 首先遍历一遍单链表得到链表长度L，再次从头结点循环L/2找到结点。算法复杂度（精确的复杂度）O(L+L...
