标题: [原创+整理]数据结构的一些笔记 [打印本页]
作者: 风灵风之子 时间: 2004-12-25 03:31 标题: [原创+整理]数据结构的一些笔记
[这个贴子最后由风灵风之子在 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
作者: 风灵风之子 时间: 2004-12-25 03:34 标题: [原创+整理]数据结构的一些笔记
//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<
作者: 风灵风之子 时间: 2004-12-25 03:40 标题: [原创+整理]数据结构的一些笔记
//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
作者: 风灵风之子 时间: 2004-12-25 03:44 标题: [原创+整理]数据结构的一些笔记
//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-25 04:01 标题: [原创+整理]数据结构的一些笔记
现在只写到队列。。。
我会继续写的。
作者: 风灵风之子 时间: 2004-12-25 15:25 标题: [原创+整理]数据结构的一些笔记
楼上说得对
我只是起抛砖引玉的作用而已。。。
作者: x86 时间: 2004-12-25 20:39 标题: [原创+整理]数据结构的一些笔记
马上就要考试了，数据结构。
偶只打算再把所有的算法伪代码一下了，不过做实验借鉴一下楼主的代码，到是挺好的，支持楼主继续！！！！！！！！！
作者: x86 时间: 2004-12-25 21:27 标题: [原创+整理]数据结构的一些笔记
算法知道，也要动手撒，呵呵，许多编程技巧和注意点都要实践才知道的，支持楼主！！！
作者: 风灵风之子 时间: 2004-12-27 16:39 标题: [原创+整理]数据结构的一些笔记
[这个贴子最后由风灵风之子在 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
作者: x86 时间: 2004-12-28 19:04 标题: [原创+整理]数据结构的一些笔记
请问在cmd下有 实现对 注册表得 读写得 方法不 ？？即不会发出任何提示自动读写？？？？？？？？
编程得 时候一定要 用api吗 ？？？
作者: 风灵风之子 时间: 2004-12-30 20:34 标题: [原创+整理]数据结构的一些笔记
你的问题我在另外一个帖子回答了，请不要在这个帖子上提问，好吗？这个帖子我作为笔记的整理。
你要的答案：
http://www.thysea.com/lb/cgi-bin/topic.cgi?forum=127&topic=955&show=0
作者: 风灵风之子 时间: 2004-12-30 22:12 标题: [原创+整理]数据结构的一些笔记
//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
作者: x86 时间: 2004-12-31 01:15 标题: [原创+整理]数据结构的一些笔记
谢了！！！
作者: 风灵风之子 时间: 2004-12-31 18:03 标题: [原创+整理]数据结构的一些笔记
//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