| 導購 | 订阅 | 在线投稿
分享
 
 
 

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

來源:互聯網網民  2008-06-01 01:21:02  評論

以下是用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++實現的鏈表的數據結構。 筆者還做了棧,隊列,循環隊列,串等數據結構,如有需要者請 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; }
󰈣󰈤
王朝萬家燈火計劃
期待原創作者加盟
 
 
 
>>返回首頁<<
 
 
 
 
 
 熱帖排行
 
 
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有