[原创+整理]数据结构的一些笔记

[这个贴子最后由风灵风之子在 2004/12/24 07:57pm 第 1 次编辑] 以下代码通过VC6.0和Dev-C++测试，都只是以头文件形式给出。 //Header File:linkedlist.h 链表的头文件 #ifndef H_linkedlistType #define H_linkedlistType #include using namespace std; template struct nodeType { Type info; nodeType *link; }; template class linkedListType { public: const linkedListType& operator=(const linkedListType&); void initializeList(); bool isEmptyList(); bool isFullList(); void print(); int length(); void destroyList(); void retrieveFirst(Type& firstElement); void search(const Type&searchItem); void insertFirst(const Type& newItem); void insertLast(const Type& newItem); void deleteNode(const Type& deleteItem); linkedListType(); linkedListType(const linkedListType& otherList); ~linkedListType(); protected: nodeType *first; nodeType *last; }; template bool linkedListType::isEmptyList() { return(first==NULL); } template bool linkedListType::isFullList() { return false; } template linkedListType::linkedListType() { first=NULL; last=NULL; } template void linkedListType::destroyList() { nodeType *temp; while(first !=NULL) { temp=first; first=first->link; delete temp; } last=NULL; } template void linkedListType::initializeList() { destroyList(); } template void linkedListType::print() { nodeType *current; current=first; while(current !=NULL) { cout<info<<" "; current=current->link; } } template int linkedListType::length() { int count=0; nodeType *current; current=first; while(current !=NULL) { count++; current=current->link; } return count; } template void linkedListType::retrieveFirst(Type& firstElement) { firstElement=first->info; } template void linkedListType::search(const Type& item) { nodeType *current; bool found; if(first==NULL) cout<<"Cannot search an empty list."<info==item) found=true; else current=current->link; } if(found) cout<<"Item is found in the list."< void linkedListType::insertFirst(const Type& newItem) { nodeType *newNode; newNode=new nodeType; newNode->info=newItem; newNode->link=first; first=newNode; if (last==NULL) last=newNode; } template void linkedListType::insertLast(const Type& newItem) { nodeType *newNode; newNode=new nodeType; newNode->info=newItem; newNode->link=NULL; if (first==NULL) { first=NULL; last=NULL; } else { last->link=newNode; last=newNode; } } template void linkedListType::deleteNode(const Type& deleteItem) { nodeType *current; nodeType *trailCurrent; bool found; if (first==NULL) cout<<"Cannot delete from an empty list.\n"; else { if (first->info==deleteItem) { current=first; first=first->link; if (first==NULL) last=NULL; delete current; } else { found=false; trailCurrent=first; current=first->link; while((!found) && (current!=NULL)) { if (current->info !=deleteItem) { trailCurrent=current; current=current->link; } else found=true; } if (found) { trailCurrent->link=current->link; if(last==current) last=trailCurrent; delete current; } else count<<"Item to be deleted is not in the list."< linkedListType::~linkedListType() { nodeType *temp; while(first!=NULL) { temp=first; first=first->link; delete temp; } last=NULL; } template linkedListType::linkedListType(const linkedListType& otherList) { nodeType *newNode; nodeType *current; if (otherList.first==NULL) { first=NULL; last=NULL; } else { current=otherList.first; first=new nodeType; first->info=current->info; first->link=NULL; last=first; current=current->link; while(current!=NULL) { newNode=new nodeType; newNode->info=current->info; newNode->link=NULL; last->link=newNode; last=newNode; current=current->link; } } } template const linkedListType& linkedListType::operator=(const linkedListType& otherList) { nodeType *newNode; nodeType *current; if(this != &otherList) { if (first !=NULL) destroyList(); if(otherList.first==NULL) { first=NULL; last=NULL; } else { current=otherList.first; first=new nodeType; first->info=current->info; first->link=NULL; last=first; current=current->link; while(current !=NULL) { newNode=new nodeType; newNode->info=current->info; newNode->link=NULL; last->link=newNode; last=newNode; current=current->link; } } } return *this; } #endif

//Header File:orderedList.h 有序链表的头文件 #ifndef H_orderedListType #define H_orderedListType #include #include"linkedList.h" using namespace std; template class orderedLinkedListType:public linkedListType { public: void search(const Type& item); void insertNode(const Type& newItem); void deleteNode(const Type& deleteItem); void printListReverse() const; private: void reversePrint(nodeType *current) const; }; template void orderedLinkedListType::search(const Type& item) { bool found; nodeType *current; found=false; current=first; if(first==NULL) cout<<"Cannot serach an empty list."<info >=item) found=true; else current=current->link; } if(current==NULL) cout<<"Item is not in the list"<info==item) cout<<"Item is found in the list"< void orderedLinkedListType::insertNode(const Type& newitem) { nodeType *current; nodeType *trailCurrent; nodeType *newNode; bool found; newNode=new nodeType; newNode->info=newitem; newNode->link=NULL; if (first==NULL) first=newNode; else { current=first; found=false; while(current!=NULL && !found) { if(current->info>=newitem) found=true; else { trailCurrent=current; current=current->link; } } if(current==first) { newNode->link=first; first=newNode; } else { trailCurrent->link=newNode; newNode->link=current; } } } template void orderedLinkedListType::deleteNode(const Type&deleteItem) { nodeType *current; nodeType *trailCurrent; bool found; if (first==NULL) cout<<"Cannot delete from an empty list."<info >=deleteItem) found=true; else { trailCurrent=current; current=current->link; } } if (current==NULL) cout<<"Item to be deleted is not in the list."<info==deleteItem) { if (first==current) { first=first->link; delete current; } else { trailCurrent->link=current->link; delete current; } } else cout<<"Item to be deleted is not in the list."< void orderedLinkedListType::reversePrint(nodeType *current) const { if (current!=NULL) { reversePrint(current->link); cout<info<<" "; } } template void orderedLinkedListType::printListReverse() const { reversePrint(first); cout<

//Header file:stackType #ifndef H_StackType #define H_StackType template class stackType { public: const stackType& operator=(const stackType&); void initializeStack(); bool isEmptyStack(); bool isFullStack(); void destroyStack(); void push(const Type& newItem); void pop(Type& poppedItem); stackType(int stackSize=100); stackType(const stackType& otherStack); ~stackType(); private: int maxStackSize; int top; Type *list; }; template void stackType::initializeStack() { top=0; } template bool stackType::isEmptyStack() { return(top==0); } template bool stackType::isFullStack() { return(top==maxStackSize); } template void stackType::destroyStack() { top=0; } template void stackType::push(const Type& newItem) { list[top]=newItem; top++; } template void stackType::pop(Type& poppedItem) { top--; poppedItem=list[top]; } template stackType::stackType(int stackSize) { if(stackSize <=0) { cout<<"The size of the array to hold the stack must be positive."< stackType::~stackType() { top=0; delete [] list; } template const stackType& stackType::operator=(const stackType& otherStack) { int j; if(this !=&otherStack) { if(maxStackSize != otherStack.maxStackSize) cout<<"Cannot copy the two stacks are of different sizes."< stackType::stackType(const stackType& otherStack) { int j; maxStackSize=otherStack.maxStackSize; top=otherStack.top; list=new Type[maxStackSize]; if(top!=0) for(j=0;j

//Header file:linkedStackType.h 链堆栈头文件 #ifndef H_linkedStackType #define H_linkedStackType #include using namespace std; template struct nodeType { Type info; nodeType *link; }; template class linkedStackType { public: const linkedStackType& operator=(const linkedStackType&); void initializeStack(); bool isEmptyStack(); bool isFullStack(); void push(const Type& newItem); void pop(Type& poppedElement); void destroyStack(); linkedStackType(); linkedStackType(const linkedStackType& otherstack); ~linkedStackType(); private: nodeType *top; }; template linkedStackType::linkedStackType() { top=NULL; } template void linkedStackType::destroyStack() { nodeType *temp; while(top!=NULL) { temp=top; top=top->link; delete temp; } } template void linkedStackType::initializeStack() { destroyStack(); } template bool linkedStackType::isEmptyStack() { return(top==NULL); } template bool linkedStackType::isFullStack() { return false; } template void linkedStackType::push(const Type& newElement) { nodeType *newNode; newNode=new nodeType; newNode->info=newElement; newNode->link=top; top=newNode; } template void linkedStackType::pop(Type& poppedElement) { nodeType *temp; poppedElement=top->info; temp=top; top=top->link; delete temp; } template linkedStackType::linkedStackType(const linkedStackType& otherStack) { nodeType *newNode,*current,*last; if(otherStack.top==NULL) top=NULL; else { current=otherStack.top; top=new nodeType; top->info=current->info; top->link=NULL; last=top; current=current->link; while(current!=NULL) { newNode=new nodeType; newNode->info=current->info; newNode->link=NULL; last->link=newNode; last=newNode; current=current->link; } } } template linkedStackType::~linkedStackType() { nodeType *temp; while(top!=NULL) { temp=top; top=top->link; delete temp; } } template const linkedStackType& linkedStackType::operator=(const linkedStackType& otherStack) { nodeType *newNode,*current,*last; if(this!=&otherStack) { if(top!=NULL) destroyStack(); if(otherStack.top==NULL) top=NULL; else { current=otherStack.top; top=new nodeType; top->info=current->info; top->link=NULL; last=top; current=current->link; while(current!=NULL) { newNode=new nodeType; newNode->info=current->info; newNode->link=NULL; last->link=newNode; last=newNode; current=current->link; } } } return *this; } #endif

现在只写到队列。。。
我会继续写的。

楼上说得对
我只是起抛砖引玉的作用而已。。。

马上就要考试了，数据结构。
偶只打算再把所有的算法伪代码一下了，不过做实验借鉴一下楼主的代码，到是挺好的，支持楼主继续！！！！！！！！！

算法知道，也要动手撒，呵呵，许多编程技巧和注意点都要实践才知道的，支持楼主！！！

[这个贴子最后由风灵风之子在 2004/12/28 05:01pm 第 1 次编辑] 链队列 //Header file:linkedQueue.h #ifndef H_QueueType #define H_QueueType #include using namespace std; template struct nodeType { Type info; nodeType *link; }; template class linkedQueueType { public: const linkedQueueType& operator=(const linkedQueueType&); bool isEmptyQueue(); bool isFullQueue(); void destroyQueue(); void initializeQueue(); void addQueue(const Type& newElement); void deQueue(Type& deqElement); linkedQueueType(); linkedQueueType(const linkedQueueType& otherQueue); ~linkedQueueType(); private: nodeType *front; nodeType *rear; }; template bool linkedQueueType::isEmptyQueue() { return (front==NULL); } template bool linkedQueueType::isFullQueue() { return false; } template void linkedQueueType::destroyQueue() { nodeType *temp; while(front!=NULL) { temp=front; front=front->link; delete temp; } rear=NULL; } template void linkedQueueType::initializeQueue() { destroyQueue(); } template void linkedQueueType::addQueue(const Type& newElement) { nodeType *newNode; newNode=new nodeType; newNode->info=newElement; newNode->link=NULL; if(front==NULL) { front=newNode; rear=newNode; } else { rear->link=newNode; rear=rear->link; } } template void linkedQueueType::deQueue(Type& deqElement) { nodeType *temp; deqElement=front->info; temp=front; front=front->link; delete temp; if(front==NULL) rear=NULL; } template linkedQueueType::linkedQueueType() { front=0; } template linkedQueueType::~linkedQueueType() { nodeType *temp; while(front!=NULL) { temp=front; front=front->link; delete temp; } rear=NULL; } template linkedQueueType::linkedQueueType(const linkedQueueType& otherQueue) { nodeType *newNode,*current,*last; if(otherQueue.front==NULL) front=NULL; else { current=otherQueue.front; front=new nodeType; front->info=current->info; front->link=NULL; last=front; current=current->link; while(current!=NULL) { newNode=new nodeType; newNode->info=current->info; newNode->link=NULL; last->link=newNode; last=newNode; current=current->link; } } } template const linkedQueueType& linkedQueueType::operator=(const linkedQueueType& otherQueue) { nodeType *newNode,*current,*last; if(this!=&otherQueue) { if(front!=NULL) destroyQueue(); if(otherQueue.front==NULL) front=NULL; else { current=otherQueue.front; front=new nodeType; front->info=current->info; front->link=NULL; last=front; current=current->link; while(current!=NULL) { newNode=new nodeType; newNode->info=current->info; newNode->link=NULL; last->link=newNode; last=newNode; current=current->link; } } } return *this; } #endif

请问在cmd下有 实现对 注册表得 读写得 方法不 ？？即不会发出任何提示自动读写？？？？？？？？
编程得 时候一定要 用api吗 ？？？

你的问题我在另外一个帖子回答了，请不要在这个帖子上提问，好吗？这个帖子我作为笔记的整理。
你要的答案：
http://www.thysea.com/lb/cgi-bin/topic.cgi?forum=127&topic=955&show=0

//Header file:queueType.h 数组队列 #ifndef H_QueueType #define H_QueueType #include using namespace std; template class queueType { public: const queueType& operator=(const queueType&); void initializeQueue(); void destroyQueue(); int isEmptyQueue(); int isFullQueue(); void addQueue(Type queueElement); void deQueue(Type& deqElement); queueType(int queueSize=100); queueType(const queueType& otherQueue); ~queueType(); private: int maxQueueSize; int count; int front; int rear; Type *list; }; template void queueType::initializeQueue() { front=0; rear=maxQueueSize-1; cout=0; } template void queueType::destroyQueue() { front=0; rear=maxQueueSize-1; cout=0; } template int queueType::isEmptyQueue() { return(count==0); } template int queueType::isFullQueue() { return(count==maxQueueSize); } template void queueType::addQueue(Type newElement) { rear=(rear+1)%maxQueueSize; count++; list[rear]=newElement; } template void queueType::deQueue(Type& deqElement) { deqElement=list[front]; count--; front=(front+1)%maxQueueSize; } template queueType::queueType(int queueSize) { if(queueSize<=0) { cout<<"The size of array to hold the queue must be positive."< queueType::~queueType() { delete [] list; } template const queueType& queueType::operator=(const queueType& otherQueue) { int j; if(this !=&otherQueue) { if(maxQueueSize != otherQueue.maxQueueSize) cout<<"Cannot copy the two Queue are of different sizes."< queueType::queueType(const queueType& otherQueue) { int j; maxQueueSize=otherQueue.maxQueueSize; front=otherQueue.front; list=new Type[maxQueueSize]; if(front!=0) for(j=0;j

谢了！！！

//Header file:binaryTreeType.h 二叉树 #ifndef H_BinaryTreeType #define H_BinaryTreeType #include #include using namespace std; template struct nodeType { elemType info; nodeType *llink; nodeType *rlink; }; template class binaryTreeType { public: const binaryTreeType& operator=(const binaryTreeType&); bool isEmpty(); void inorderTraversal(); void preorderTraversal(); void postorderTraversal(); void inorderTraversal(void (*vist) (elemType&)); int treeHeight(); void destroyTree(); binaryTreeType(const binaryTreeType& otherTree); binaryTreeType(); ~binaryTreeType(); protected: nodeType *root; private: void copyTree(nodeType* &copiedTreeRoot,nodeType* otherTreeRoot); void destroy(nodeType* &p); void inorder(nodeType *p); void preorder(nodeType *p); void postorder(nodeType *p); void inorder(nodeType *p,void (*vist) (elemType&)); int height(nodeType *p); int max(int x,int y); }; template bool binaryTreeType::isEmpty() { return (root==NULL); } template binaryTreeType::binaryTreeType() { root=NULL; } template void binaryTreeType::inorderTraversal() { inorder(root); } template void binaryTreeType::preorderTraversal() { preorder(root); } template void binaryTreeType::postorderTraversal() { postorder(root); } template void binaryTreeType::inorderTraversal(void (*vist) (elemType& item)) { inorder(root,*vist); } template int binaryTreeType::treeHeight() { return height(root); } template void binaryTreeType::inorder(nodeType *p) { if (p!=NULL) { inorder(p->link); cout<info<<" "; inorder(p->rlink); } } template void binaryTreeType::preorder(nodeType *p) { if(p!=NULL) { cout<info<<" "; preorder(p->llink); preorder(p->rlink); } } template void binaryTreeType::postorder(nodeType *p) { if(p!=NULL) { postorder(p->llink); postorder(p->rlink); cout<info<<" "; } } template void binaryTreeType::inorder(nodeType* p,void (*vist) (elemType& item)) { if (p!=NULL) { inorder(p->llink,*vist); (*vist)(p->info); inorder(p->rlink,*vist); } } template int binaryTreeType::height(nodeType *p) { if (p==NULL) return 0; else return 1+max(height(p->llink),height(p->rlink)); } template int binaryTreeType::max(int x,int y) { if (x>=y) return x; else return y; } template void binaryTreeType::copyTree(nodeType* &copiedTreeRoot, nodeType* otherTreeRoot) { if (otherTreeRoot==NULL) copiedTreeRoot=NULL; else { copiedTreeRoot=new nodeType; copiedTreeRoot->info=otherTreeRoot->info; copyTree(copiedTreeRoot->llink,otherTreeRoot->llink); copyTree(copiedTreeRoot->rlink,otherTreeRoot->rlink); } } template void binaryTreeType::destroy(nodeType* &p) { if (p!=NULL) { destroy(p->llink); destroy(p->rlink); delete p; p=NULL; } } template void binaryTreeType::destroyTree() { destroy(root); } template binaryTreeType::binaryTreeType(const binaryTreeType& otherTree) { if (otherTree.root==NULL) root=NULL; else copyTree(root,otherTree.root); } template binaryTreeType::~binaryTreeType() { destroy(root); } template const binaryTreeType& binaryTreeType::operator=(const binaryTreeType& otherTree) { if (this!=&otherTree) { if(root!=NULL) destroy(root); if (otherTree.root==NULL) root=NULL; else copyTree(root,otherTree.root); } return *this; } #endif

//Header filer:binarySearchTree.h 二叉搜索树 #ifndef H_BinarySearchTree #define H_BinarySearchTree #include #include"binaryTreeType.h" using namespace std; template class bSearchTreeType:public binaryTreeType { public: bool search(const elemType& searchItem); void insert(const elemType& insertItem); void deleteNode(const elemType& deleteItem); private: void deleteFromTree(nodeType* &p); }; template bool bSearchTreeType::search(const elemType& searchItem) { nodeType *current; bool found=false; if (root==NULL) cout<<"Cannot search the empty tree."<info==searchItem) found=true; else if (current->info > searchItem) current=current->llink; else current=current->rlink; } } return found; } template void bSearchTreeType::insert(const elemType& insertItem) { nodeType *current; nodeType *trailCurrent; nodeType *newNode; newNode=new nodeType; newNode->info=insertItem; newNode->llink=NULL; newNode->rlink=NULL; if (root==NULL) root=newNode; else { current=root; while (current!=NULL) { trailCurrent=current; if (current->info==insertItem) { cout<<"The insert item already is the list-"; cout<<"duplicates are not allowed."<info > insertItem) current=current->llink; else current=current->rlink; } } if (trailCurrent->info >insertItem) trailCurrent->llink=newNode; else trailCurrent->rlink=newNode; } } template void bSearchTreeType::deleteFromTree(nodeType* &p) { nodeType *current; nodeType *trailCurrent; nodeType *temp; if (p==NULL) cout<<"Error:The node to be deleted is NULL"<llink==NULL && p->rlink==NULL) { temp=p; p=NULL: delete temp; } else if (p->llink==NULL) { temp=p; p=temp->rlink; delete temp; } else if (p->rlink==NULL) { temp=p; p=temp->llink; delete temp; } else { current=p->llink; trailCurrent=NULL: while (current->rlink != NULL) { trailCurrent=current; current=current-rlink; } p->info=current->info; if (trailCurrent==NULL) p->llink=current->llink; else trailCurrent->rlink=current->llink; delete current; } } template void bSearchTreeType::deleteNode(const elemType& deleteItem) { nodeType *current; nodeType *trailCurrent; bool found=false; if (root==NULL) cout<<"Cannot delete from the empty tree."<info==deleteItem) found=true; else { trailCurrent=current; if (current->info >deleteItem) current=current->llink; else current=current->rlink; } } if (current==NULL) cout<<"The delete item is not in the list."<info >deleteItem) deleteFromTree(trailCurrent->llink); else deleteFromTree(trailCurrent->rlink); } } } #endif