用c++語言實現基本的數據結構(1)

以下是用c++實現的鏈表的數據結構。

筆者還做了棧,隊列,循環隊列,串等數據結構,如有需要者請

E-mail:cangzhu@163.com

#include"iostream.h"

#include"stdio.h"

#include"stdlib.h"

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

#define OVERFLOAT -2

#define MAXSIZE 100

typedef int status;

typedef int ElemType;

typedef strUCt LNode{

ElemType data;

struct LNode *next;

} *Link,*Position;

class LinkList

{

private:

Link head;

int len;

public:

status InitList(LinkList &L);

status DestroyList(LinkList &L);

void FreeNode(Link p);

status ClearList(LinkList &L);

status InsFirst(LinkList &L,Link s);

status Remove(LinkList &L,Link p);

status InsBefore(LinkList &L,Link p,Link s);

status InsAfter(LinkList &L,Link p,Link s);

status SetCurElem(Link p,ElemType &e);

ElemType GetElem(Link p);

int ListLength(LinkList L);

Position GetHead(LinkList L);

Position GetLast(LinkList L);

status PriorPos(LinkList L,Link p,Position &q);

status NextPos(LinkList L,Link p,Position &q);

status Search(LinkList L,ElemType e,Position &p);

};

status LinkList::InitList(LinkList &L)

{

Link L1;

L1=(LNode *)malloc (sizeof(LinkList)*MAXSIZE);

L.head=L1;

L.head->next=NULL;

L.len=0;

if(L1==NULL)

return OVERFLOAT;

else

return OK;

}

status LinkList::DestroyList(LinkList &L)

{

return OK;

}

void LinkList::FreeNode(Link p)

status LinkList::ClearList(LinkList &L)

{

L.head->next=NULL;

len=0;

return OK;

}

status LinkList::InsFirst(LinkList &L, Link s)

{

s->next=L.head->next;

L.head->next=s;

len++;

return OK;

}

status LinkList::Remove(LinkList &L,Link p)

{

Link q=L.GetHead(L);

while(q->next!=p)

q=q->next;

q->next=q->next->next;

L.len--;

return OK;

}

status LinkList::InsBefore(LinkList &L,Link p,Link s)

{

Link q=L.head;

while(q->next!=p)

q=q->next;

s->next=q->next;

q->next=s;

len++;

return OK;

}

status LinkList::InsAfter(LinkList &L,Link p,Link s)

{

s->next=p->next;

p->next=s;

len++;

return OK;

}

status LinkList::SetCurElem(Link p,ElemType &e)

{

p->data=e;

return OK;

}

ElemType LinkList::GetElem(Link p)

{

return p->data;

}

int LinkList::ListLength(LinkList L)

{

return L.len;

}

Position LinkList::GetHead(LinkList L)

{

return L.head;

}

Position LinkList::GetLast(LinkList L)

{

Link q=head;

while(q->next!=NULL)

q=q->next;

return q;

}

status LinkList::PriorPos(LinkList L,Link p,Position &q)

{

Link QQ=L.GetHead(L);

if(p==qqp==qq->next)

return FALSE;

while(qq->next!=p)

qq=qq->next;

q=qq;

return OK;

}

status LinkList::NextPos(LinkList L,Link p,Position &q)

{

if(p->next==NULL)

return FALSE;

q=p->next;

return OK;

}

status LinkList::Search(LinkList L,ElemType e,Position &p)

{

Link q=L.GetHead(L);

int i=0;

do

{

i++;

q=q->next;

if(i>L.len)

return FALSE;

}

while(q->data!=e);

p=q;

return OK;

}

//下面是測試程序,讀者可以按自己的要求,修改並測試!

void main()

{

/*LinkList LL;

LL.InitList(LL);

LNode node[5];

int i;

for(i=0;i<5;i++)

node[i].next=NULL;

for(i=0;i<5;i++)

node[i].data=10*i;

LNode node2[5];

int j;

for(j=0;j<5;j++)

node2[j].next=NULL;

for(j=0;j<5;j++)

node2[j].data=100+10*j;

for(i=0;i<5;i++)

LL.InsFirst(LL,&node[i]);

for(i=0;i<5;i++)

LL.InsAfter(LL,&node[i],&node2[i]);

for(i=0;i<5;i++)

cout<<LL.GetElem(&node[i])<<endl;

for(i=0;i<5;i++)

cout<<LL.GetElem(&node2[i])<<endl;

int e=22222;

LL.SetCurElem(&node2[3],e);

cout<<"changed:"<<LL.GetElem(&node2[3])<<endl;

cout<<"先面遍曆整個線性表:"<<endl;

for(Link q=LL.GetHead(LL)->next;q!=NULL;q=q->next)

cout<<q->data<<endl;

cout<<"last:"<<LL.GetLast(LL)->data<<endl;

cout<<node[4].data<<"的前一個元素:"<<endl;

if(LL.PriorPos(LL,&node[4],q))

cout<<q->data<<endl;

else

cout<<node[4].data<<"是最前一個元素"<<endl;

cout<<node2[4].data<<"的前一個元素:"<<endl;

LL.PriorPos(LL,&node2[4],q);

cout<<q->data<<endl;

cout<<node2[3].data<<"的下一個元素:"<<endl;

LL.NextPos(LL,&node2[3],q);

cout<<q->data<<endl;

cout<<"remove :"<<node[3].data<<endl;

LL.Remove(LL,&node[3]);

cout<<"先面遍曆整個線性表:"<<endl;

for(i=0,q=LL.GetHead(LL)->next;i<LL.ListLength(LL);i++)

cout<<"last:"<<LL.GetLast(LL)->data<<endl;

q=LL.GetLast(LL);

Link qq;

if(LL.NextPos(LL,q,qq))

cout<<qq->data<<endl;

else

cout<<q->data<<"是最後一個元素!"<<endl;

cout<<"先面遍曆整個線性表:"<<endl;

for(q=LL.GetHead(LL)->next;q!=NULL;q=q->next)

cout<<q->data<<endl;

cout<<"remove :"<<node[3].data<<endl;

Link temp;

if(LL.Search(LL,120,q))

cout<<LL.Search(LL,22222,temp)<<endl;

LL.ClearList(LL);

LNode test;

test.data=10;

LL.InsFirst(LL,&test);

cout<<"先面遍曆整個線性表:"<<endl;

for(q=LL.GetHead(LL)->next;q!=NULL;q=q->next)

cout<<q->data<<endl;

if(LL.Search(LL,10,temp))

cout<<temp->data;

LNode no[10];

for(i=0;i<10;i++)

no[i].next=NULL;

for(i=0;i<10;i++)

no[i].data=100*i;

LL.InsFirst(LL,&no[9]);

for(i=8;i>=0;i--)

LL.InsBefore(LL,&no[i+1],&no[i]);

cout<<"測試——先面遍曆整個線性表:"<<endl;

for(q=LL.GetHead(LL);q->next!=NULL;q=q->next)

cout<<q->next->data<<endl;*/

int i;

LinkList stu;

stu.InitList(stu);

LNode stu_node[6];

for(i=0;i<6;i++)

stu_node[i].data=i*6;

for(i=0;i<6;i++)

stu.InsFirst(stu,&stu_node[i]);

cout<<stu.GetHead(stu)->next->data<<endl;

}

數據結構算法集---C++語言實現
這是我學數據結構編寫的算法,我把他整理出來,都是基本算法,供大家學習。我使用c++面向對象形式編寫,各種算法都封裝在各自的類裏,假如想增加功能,在相應的類裏增加函數即可。我對樹和圖的構造也做了一些人性化設...查看完整版>>數據結構算法集---C++語言實現
 
數據結構學習(C++)——圖【1】(基本儲存方法)
首先告訴大家一個好消息,數據結構到這裏就要結束了!然後再來一個壞消息,這裏是數據結構中“最沒有意義”的部分和最難的部分。圖的應用恐怕是所有結構中最寬泛的了,但這也注定了在講“數據結構的圖”的時候沒什麽...查看完整版>>數據結構學習(C++)——圖【1】(基本儲存方法)
 
《數據結構的C++僞碼實現》(《DATA STRUCTURES A Pseudocode Approach with C++》)讀書筆記(四)
第二章 Searching我覺得既然是僅僅爲自己總結,就只抓裏面的概要吧,太多了反而不好。主要講了三種查找的方法:1,list search:順序查找(sequence search),二分法查找(binary search)2,hashed list search:哈希查找(ha...查看完整版>>《數據結構的C++僞碼實現》(《DATA STRUCTURES A Pseudocode Approach with C++》)讀書筆記(四)
 
《數據結構的C++僞碼實現》(《DATA STRUCTURES A Pseudocode Approach with C++》)讀書筆記(三)
算法效率(Algorithm efficency) 首先提出來算法效率的學習是建立在循環上面的。(The study of algorithm efficency focuses on loops) 1,線形循環(linear loops) 先看一段代碼: 1 i=1 2 loop ...查看完整版>>《數據結構的C++僞碼實現》(《DATA STRUCTURES A Pseudocode Approach with C++》)讀書筆記(三)
 
《數據結構的C++僞碼實現》(《DATA STRUCTURES A Pseudocode Approach with C++》)讀書筆記(二)
第一章 簡介主要講述僞碼(pseudocode)、抽象數據類型(ADT)、算法效率(efficiency)僞碼(pseudocode):一種類英語結構描述碼。舉例:algorithm sample(ref pageNumber <integer>)This algorithm reads a file an...查看完整版>>《數據結構的C++僞碼實現》(《DATA STRUCTURES A Pseudocode Approach with C++》)讀書筆記(二)
 
《數據結構的C++僞碼實現》(《DATA STRUCTURES A Pseudocode Approach with C++》)讀書筆記(一)
首先寫一下書評吧,我覺得我對語言的學習有兩個階段的跨越比較重要。第一個階段是在細讀譚浩強的《c語言程序設計》的時候理解了指針的概念,讓我跳躍了一大步;第二個階段是在攻讀《數據結構(c語言版)》(嚴蔚敏)...查看完整版>>《數據結構的C++僞碼實現》(《DATA STRUCTURES A Pseudocode Approach with C++》)讀書筆記(一)
 
數據結構學習(C++)——棧和隊列(定義和實現)
棧和隊列是操作受限的線性表,好像每本講數據結構的數都是這麽說的。有些書按照這個思路給出了定義和實現;但是很遺憾,這本書沒有這樣做,所以,原書中的做法是重複建設,這或許可以用不是一個人寫的這樣的理由來開...查看完整版>>數據結構學習(C++)——棧和隊列(定義和實現)
 
數據結構學習(C++)——單鏈表(定義與實現)
節點類#ifndef Node_H#define Node_H template <class Type> class Node //單鏈節點類{public: Type data; Node<Type> *link; Node() : data(Type()), link(NULL) {} ...查看完整版>>數據結構學習(C++)——單鏈表(定義與實現)
 
數據結構C語言實現系列——二叉樹
Word-BREAK: break-all; PADDING-TOP: 4px; BORDER-BOTTOM: windowtext 0.5pt solid"#include <stdio.h>#include <stdlib.h>#define STACK_MAX_SIZE 30#define QUEUE_MAX_SIZE 30#ifndef elemType typed...查看完整版>>數據結構C語言實現系列——二叉樹
 
 
回到王朝網路移動版首頁