数据结构之单链表基本操作(C++)

迷南。 2022-01-12 08:55 278阅读 0赞

#include<iostream>
    using namespace std;
    typedef int elemType;
    
    template <typename elemType>
    class linkList { 
    
    private:
    	struct Node                //结点类型
    	{ 
    		elemType data;         //结点数据域
    		Node* next;            //结点指针域
    		Node(const elemType value, Node* p = NULL) { 
    			data = value;
    			next = p;
    		}
    		Node(Node* p = NULL) { 
    			next = p;
    		}
    	};
    	Node* head;             //链表头结点
    	Node* tail;             //链表尾结点
    	int curLength;          //单链表当前长度，
    	Node* getPosition(int i) const;  //返回指向位序为i的结点的指针
    
    public:
    	linkList();
    	~linkList();
    
    	void clear();                 //清空单链表,使之成为空表
    	bool empty() const {           //带有头结点的单链表，判空
    		return head->next == NULL; 
    	} 
    	int size() const {             //返回单链表的当前实际长度
    		return curLength;
    	}
    	void insert(int i, const elemType& value);  //位序i处插入值为value的结点，表长加1
    	void remove(int i);           //移除位序为i处的结点，表长减1
    	int search(const elemType& value) const;			 //查找值为value的结点第一次出现的位序
    	int prior(const elemType& value)  const;             //查找值为value的结点的前驱的位序
    	void traverse() const;        //遍历单链表
    	void headCreate();            //头插法建立单链表
    	void tailCreate();            //尾插法建立单链表
    	void inverse();               //逆置单链表
    	linkList<elemType>* Union(linkList<elemType>* lb);  //合并单链表
    };
    
    
    /* 查找位序为i的结点的内存地址(思想): 1.首先检查要查找位序的合法性，若非法返回NULL，i==0表示查找首元结点，i==-1表示查找头结点 2.设置工作指针，指向头结点,设置计数器，进行计数，知道p指向位序为i的结点 */
    template<class elemType>
    typename linkList<elemType>::Node* linkList<elemType>::getPosition(int i) const
    { 
    	if (i <-1 || i > curLength-1) {          //合法检查范围为[-1...curLength-1]
    		return NULL;
    	}
    	Node* p = head;           //工作指针指向头结点
    	int count = 0;
    	while (count <= i) { 
    		p = p->next;
    		count++;
    	}
    	return p;                 //返回指向位序为i结点的指针
    }
    
    /* 单链表初始化: 创建一个带有头结点的空链表,即： 申请一个新的节点作为头结点,不设置节点数据域，只设置其指针域为空即可 */
    template<typename elemType>
    linkList<elemType>::linkList()
    { 
    	head = tail =new Node();  //创建带有头结点的单链表
    	curLength = 0;
    }
    
    template<typename elemType>
    linkList<elemType>::~linkList()
    { 
    	clear();              //清空单链表
    	delete head;          //释放头结点
    }
    
    /* 清空单链表: 将工作指针从头结点移动到表尾，边移动指针，边删除结点。 不修改头指针head的指向，而是引入一个工作指针完成单链表的遍历 */
    template<typename elemType>
    void linkList<elemType>::clear()
    { 
    	Node* p, * tmp;   //声明p为工作指针，指向首元结点
    	p = head->next;   //引入工作指针，是为了防止随意修改头指针
    	while (p != NULL) { 
    		tmp = p;         
    		p = p->next;    //指针后移
    		delete tmp;     //释放结点
    	}
    	head->next = NULL;  //最后头结点的指针域置空
    	tail = head;        //头尾指针均指向头结点
    	curLength = 0;
    
    }
    
    /* 插入结点(思想): 位序为i处插入值为value的结点q: 1. 先找到位序为i的结点的前驱结点p 2. q的后继指向p原来的后继，修改p的后继为q 3. 合法的插入范围[0,curLength],其中0表示插入点为首元结点处，curLength为表尾。 4. 插入算法主要是移动指针查找结点，所以时间复杂度为O(n). */
    template<typename elemType>
    void linkList<elemType>::insert(int i, const elemType& value) 
    { 
    	Node* p, * q;				//q为要插入的新节点,p为q的前驱结点
    	if (i<-1 || i>curLength) { 
    		throw out_of_range("Out of Range");   //插入位置非法，抛出异常
    	}
    	p = getPosition(i - 1);     //定位到i结点的前驱
    	q = new Node(value,p->next);    //申请新节点q,数据域为value，指针域为p结点的下一个结点
    	p->next = q;                    //q结点插入到p结点后边
    	if (p == tail) tail = q;        //若插入点在表尾，则q结点为新的表尾
    	curLength++;                    //表长+1
    
    }
    
    /* 删除指定位序的结点(思想）： 1. 检验删除范围是否合法，合法范围为[0,curLength-1]，0表示删除首元结点，curLength-1表示删除表尾结点 2. 找到位序为i-1 的结点，修改指针的指向关系，时间复杂度为O(n) */
    template<typename elemType>
    void linkList<elemType>::remove(int i)
    { 
    	if (i<0 || i>curLength - 1) { 
    		throw out_of_range("Out of Range");
    	}
    	Node* pre, * p;
    	pre= getPosition(i - 1);      //待删除结点的前驱结点
    	p = pre->next;                       //待删除结点
    	if (p == tail) {                      //要删除的结点为表尾结点
    		tail = pre;                      //修改表尾指针
    		p->next = NULL;				     //表尾指针置NULL
    		delete p;						 //删除当前结点
    	}
    	else { 							     //修改指针并删除结点p
    		pre->next = p->next;
    		delete p;
    	}
    	curLength--;
    }
    
    /* 查找值为value的元素的位序（思想）： 1. 设置计数器count，从链表开头遍历进行判断， 2. 查找成功，返回count，否则直到单链表结束（p==NULL)，返回-1. 3. 时间复杂度O(n). */
    template<typename elemType>
    int linkList<elemType>::search(const elemType& value) const
    { 
    	int count = 0;					  //位序0 为首元结点
    	Node* p = head->next;
    	while (p!=NULL && p->data != value) { 
    		p = p->next;
    		count++;
    	}
    	if (p == NULL) return -1;         //查找失败，返回-1，此-1并非头结点
    	else return count;            //查找成功，返回结点位序
    
    }
    
    /* 查找值为value的结点 的前驱位序(思想）： 1.设置计数器，两个指针p和pre,分别指向当前访问的结点和它的前驱。 1. 若p==NULL，则查找失败，返回-1 2. 若找到值为value的结点，且该结点是首元结点，则无前驱，返回-1 3. 若找到值为value的结点，且该结点不是首元结点，则返回前驱的位序 */
    template<typename elemType>
    int linkList<elemType>::prior(const elemType& value) const
    { 
    	Node* p = head->next;     //p为工作指针，指向首元结点
    	Node* pre = nullptr;      //pre指向p的前驱
    	int count = -1;           //-1表示没有前驱结点
    
    	while (p != nullptr && p->data != value) { 
    		pre = p;              //前驱指针后移一位
    		p = p->next;		  //当前指针后移，指向下一个待处理结点
    		count++;
    	}
    	if (p == NULL) return -1; //查找失败，返回-1
    	else return count;        //成功，返回位序
    	return 0;
    }
    
    /* 遍历单链表(思想): 从头到尾遍历链表中的每个结点，一次输出 时间复杂度为O(n) */
    template<typename elemType>
    void linkList<elemType>::traverse() const
    { 
    	Node* tmp = head->next;    //工作指针指向首元结点
    	while (tmp != NULL) { 
    		cout << tmp->data << " ";  
    		tmp = tmp->next;       //向后移动
    	}
    	cout << endl;
    }
    
    /* 头插法建立单链表(思想）： 头插法即指在链表的头部插入结点建立单链表：每次插入将新增结点置于头结点之后，首元结点之前 因为是在单链表的头部插入，所以读入数据的顺序会是相反的（与线性表中的逻辑结构相反) 时间复杂度为O(n) */
    template<typename elemType>
    void linkList<elemType>::headCreate()
    { 
    	Node* p;
    	elemType value, flag;
    	cout << "Input elements,ends with:" << endl;
    	cin >> flag;               //输入结束标志
    	while (cin >> value, value != flag) { 
    		//创建新的节点p->data=value; p->next=head->next;
    		p = new Node(value, head->next);
    		head->next = p;					//节点p插入在头结点的后面
    		if (head == tail) tail == p;    //原链表为空，新节点p称为尾结点
    		curLength++;
    	}
    }
    
    /* 尾插入建立单链表(思想): 在单链表的尾部插入结点建立单链表， 初始时，创建一个带有头结点的空链表，头指针和尾指针均指向头结点 按顺序表中的元素顺序读入元素并申请结点,将新节点插入tail指针的后边，修改tail指向为新节点 */
    template<typename elemType>
    void linkList<elemType>::tailCreate()
    { 
    	Node* p;
    	elemType value, flag;
    	cout << "Input elements,ended with: " << endl;
    	cin >> flag;
    	while (cin >> value, value != flag) { 
    		p = new Node(value, NULL);
    		tail->next = p;             //节点p插入在尾结点之后
    		tail = p;					//移动尾指针，使其指向新的结点
    		curLength++;
    	}
    }
    
    /* 逆置单链表: 利用头插法建立的单链表,对于元素的顺序与读入的顺序时相反的。 1. 用工作指针p依次访问单链表中的每个结点，每访问一个节点，将它插入在头结点之后， 2. 向后移动工作指针，知道所有结点全部重新插入到单链表之中，即完成了单链表的逆置。 3. 时间复杂度为O(n) */
    template<typename elemType>
    void linkList<elemType>::inverse()
    { 
    	Node* p, * tmp;
    	p = head->next;            //工作指针，指向首元结点
    	head->next = nullptr;      //头结点指针域为空，构成空链表
    	if (p) tail = p;		   //逆置后，原来的首元结点变成尾结点
    	while (p) { 
    		tmp = p->next;         //暂存p的后继
    		p->next = head->next;  //
    		head->next = p;        //结点p插入在头结点后边
    		p = tmp;			   //移动到下一个结点
    	}
    }
    
    /* 合并单链表（思想）： 将非递减有序单链表la和lb合并为新的非递减有序单链表lc，要求利用原来表空间 1. 因为新创建的单链表lc仍是非递减有序，所以使用尾插法创建lc 2. 设立三个工作指针，指针pa和pb分别指向单链表la和lb的首元结点,指针pc指向链表lc的头结点 3. 比较pa，pb的数据域大小，将小者插入到lc的表尾,移动指针，直至其中一个链表为空 4. 将剩余一个链表结点链接到lc的表尾 */
    
    template<typename elemType>
    linkList<elemType>* linkList<elemType>::Union(linkList<elemType>* lb)
    { 
    	Node* pa, * pb, * pc;       //分别是指向la,lb,lc的工作指针
    	linkList<elemType>* lc = this;       //lc利用la的空间
    	pa = head->next;		    //la头结点的指针域置为NULL，构成空链表
    	head->next = NULL; 
    	pb = (lb->next)->next;      //pb指向lb链表的首元结点
    	(lb->head)->next = NULL;	//lb头结点的指针域置为NULL，构成空链表
    
    	pc = lc->head;              //pc直接利用la的头结点
    	while (pa && pb) { 
    		if (pa->data <= pb->data) {   //pa所指向的结点用尾插法插入到lc链表中
    			pc->next = pa;
    			pc = pa;
    			pa = pa->next;
    		}
    		else {                   //pb所指向的结点尾插法插入到lc中
    			pc->next = pb;
    			pc = pb;
    			pb = pb->next;
    		}
    	}
    	if (pa) {                    //pa未到表尾,则将pc指向pa
    		pc->next = pa;
    		lc->next = tail;        //修改表尾指针，lc的表尾即为la的表尾
    	}
    	else { 						//若pb未到表尾,则将pc指向pb
    		pc->next = pb;
    		lc->next = lb->tail;    //修改表尾指针，
    	}
    	lc->curLength = curLength + lb->curLength;
    	delete lb;
    	return lc;
    
    	return nullptr;
    }
    
    int main() { 
    	//单链表初始化
    	linkList<elemType>::linkList();
    	linkList<elemType> list;
    
    	//头插法建立链表
    	list.headCreate();
    	cout << "头插法建立链表: ";
    	list.traverse();
    
    	cout << "链表逆置: ";
    	list.inverse();
    	list.traverse();
    
    	list.insert(2, 1999);
    	cout << "插入1999后的单链表: ";
    	list.traverse();
    	cout << "1999的位序= " << list.search(1999) << endl;
    
    	cout << "查找元素10的前驱" << list.prior(10) << endl;
    	cout << "删除元素指定位序元素";
    	list.remove(3);
    	list.traverse();
    
    	//尾插法建立链表
    	list.tailCreate();
    	list.traverse();
    	return 0;
    }