数据结构 知识回顾 2017-12-27 拥抱被我冷落在角落的数据结构吧! 结合小玉老师的博客总结。 顺序表基本操作123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167#include <iostream>using namespace std;#define Maxsize 100 //最大空间typedef struct{ int *elem; int length; // 顺序表的长度}SqList;bool InitList(SqList &L) //构造一个空的顺序表L{ //L加&表示引用类型参数,函数内部的改变跳出函数仍然有效//不加&内部改变,跳出函数后无效 L.elem=new int[Maxsize]; //为顺序表分配Maxsize个空间 if(!L.elem) return false; //存储分配失败 L.length=0; //空表长度为0 return true;}bool CreateList(SqList &L) //创建一个顺序表L{ //L加&表示引用类型参数,函数内部的改变跳出函数仍然有效//不加&内部改变,跳出函数后无效 int a,i=0; cin>>a; while(a!=-1) { if(L.length==Maxsize) { cout<<"顺序表已满!"; return false; } L.elem[i++]=a; L.length++; cin>>a; } return true;}bool GetElem(SqList L,int i,int &e){ if (i<1||i>L.length) return false; //判断i值是否合理,若不合理,返回false e=L.elem[i-1]; //第i-1的单元存储着第i个数据 return true;}int LocateELem(SqList L,int x){ for (int i=0;i<L.length;i++) if (L.elem[i]==x) return i+1;//第几个元素,例如第5个元素,下标其实为4 return -1;}bool ListInsert_Sq(SqList &L,int i ,int e){ if(i<1 || i>L.length+1)return false; //i值不合法 if(L.length==Maxsize) return false; //存储空间已满 for(int j=L.length-1;j>=i-1;j--) L.elem[j+1]=L.elem[j]; //从最后一个元素开始后移,直到第i个元素后移 L.elem[i-1]=e; //将新元素e放入第i个位置 L.length++; //表长增1 return true;}bool ListDelete_Sq(SqList &L,int i,int &e){ if((i<1)||(i>L.length))return false; //i值不合法 e=L.elem[i-1]; //将欲删除的元素保留在e中 for (int j=i; j<=L.length-1; j++) L.elem[j-1] =L.elem[j]; //被删除元素之后的元素前移 L.length--; //表长减1 return true;}void print(SqList L){ cout << "输出顺序表" <<endl; for(int j=0;j<=L.length-1;j++) cout<<L.elem[j]<<" "; cout<<endl;}void DestroyList(SqList &L){ if (L.elem) delete []L.elem; //释放存储空间}int main(){ SqList myL; int i,e,x; cout << "1. 初始化\n"; cout << "2. 创建\n"; cout << "3. 取值\n"; cout << "4. 查找\n"; cout << "5. 插入\n"; cout << "6. 删除\n"; cout << "7. 输出\n"; cout << "8. 销毁\n"; cout << "0. 退出\n"; int choose = -1; while (choose != 0) { cout << "请选择:"; cin >> choose; switch (choose) { case 1://初始化顺序表 cout << "顺序表初始化..." <<endl; if(InitList(myL)) cout <<"顺序表初始化成功!" << endl; else cout <<"顺序表初始化失败!" << endl; break; case 2://创建顺序表 cout << "顺序表创建..." <<endl; cout << "输入整型数,输入-1结束" <<endl; if(CreateList(myL)) cout <<"顺序表创建成功!" << endl; else cout <<"顺序表创建失败!" << endl; break; case 3://取值 cout << "输入整型数i,取第i个元素输出" <<endl; cin>>i; if(GetElem(myL,i,e)) cout <<"第i个元素是: " <<e<< endl; else cout <<"顺序表取值失败!" << endl;; cout << "第i个元素是: "<<e<< endl; break; case 4://查找 cout << "请输入要查找的数x:"; cin>>x; if(LocateELem(myL,x)==-1) cout <<"查找失败!" << endl; else cout <<"查找成功!" << endl; break; case 5://插入 cout << "请输入要插入的位置和要插入的数据元素e:"; cin>>i>>e; if(ListInsert_Sq(myL,i,e)) cout <<"插入成功!" << endl; else cout <<"插入失败!" << endl; break; case 6://删除 cout << "请输入要删除的位置i:"; cin>>i; if(ListDelete_Sq(myL,i,e)) cout <<" 删除成功!" << endl; else cout <<"删除失败!" << endl; break; case 7://输出 print(myL); break; case 8://销毁 cout << "顺序表销毁..."<<endl; DestroyList(myL); break; } } return 0;} 单链表基本操作123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225#include<iostream>#include<string>#include<iomanip>#include<stdlib.h>using namespace std;typedef struct LNode { int data; //结点的数据域 struct LNode *next; //结点的指针域}LNode, *LinkList; //LinkList为指向结构体LNode的指针类型bool InitList_L(LinkList &L)//构造一个空的单链表L{ L=new LNode; //生成新结点作为头结点,用头指针L指向头结点 if(!L) return false; //生成结点失败 L->next=NULL; //头结点的指针域置空 return true;}void CreateList_H(LinkList &L)//前插法创建单链表{ //输入n个元素的值,建立到头结点的单链表L int n; LinkList s; //定义一个指针变量 L=new LNode; L->next=NULL; //先建立一个带头结点的空链表 cout <<"请输入元素个数n:" <<endl; cin>>n; cout <<"请依次输入n个元素:" <<endl; cout <<"前插法创建单链表..." <<endl; while(n--){ s=new LNode; //生成新结点s cin>>s->data; //输入元素值赋给新结点的数据域 s->next=L->next; L->next=s; //将新结点s插入到头结点之后 }}void CreateList_R(LinkList &L)//尾插法创建单链表{ //输入n个元素的值,建立带表头结点的单链表L int n; LinkList s, r; L=new LNode; L->next=NULL; //先建立一个带头结点的空链表 r=L; //尾指针r指向头结点 cout <<"请输入元素个数n:" <<endl; cin>>n; cout <<"请依次输入n个元素:" <<endl; cout <<"尾插法创建单链表..." <<endl; while(n--){ s=new LNode;//生成新结点 cin>>s->data; //输入元素值赋给新结点的数据域 s->next=NULL; r->next=s;//将新结点s插入尾结点r之后 r=s;//r指向新的尾结点s }}bool GetElem_L(LinkList L, int i, int &e)//单链表的取值{ //在带头结点的单链表L中查找第i个元素 //用e记录L中第i个数据元素的值 int j; LinkList p; p=L->next;//p指向第一个结点, j=1; //j为计数器 while (j<i && p) //顺链域向后扫描,直到p指向第i个元素或p为空{ p=p->next; //p指向下一个结点 j++; //计数器j相应加1 } if (!p || j>i) return false; //i值不合法i>n或i<=0 e=p->data; //取第i个结点的数据域 return true;}bool LocateElem_L(LinkList L, int e) //按值查找{ //在带头结点的单链表L中查找值为e的元素 LinkList p; p=L->next; while (p && p->data!=e)//顺链域向后扫描,直到p为空或p所指结点的数据域等于e p=p->next; //p指向下一个结点 if(!p)return false; //查找失败p为NULLreturn true;}bool ListInsert_L(LinkList &L, int i, int &e)//单链表的插入{ //在带头结点的单链表L中第i个位置插入值为e的新结点 int j; LinkList p, s; p=L; j=0; while (p&&j<i-1) //查找第i-1个结点,p指向该结点{ p=p->next; j++; } if (!p || j>i-1)//i>n+1或者i<1 return false; s=new LNode; //生成新结点 s->data=e; //将新结点的数据域置为e s->next=p->next; //将新结点的指针域指向结点ai p->next=s; //将结点p的指针域指向结点s return true;}bool ListDelete_L(LinkList &L, int i) //单链表的删除{ //在带头结点的单链表L中,删除第i个位置 LinkList p, q; int j; p=L; j=0; while((p->next)&&(j<i-1)) //查找第i-1个结点,p指向该结点 { p=p->next; j++; } if (!(p->next)||(j>i-1))//当i>n或i<1时,删除位置不合理 return false; q=p->next; //临时保存被删结点的地址以备释放空间 p->next=q->next; //改变删除结点前驱结点的指针域 delete q; //释放被删除结点的空间 return true;}void Listprint_L(LinkList L) //单链表的输出{LinkList p;p=L->next;while (p){ cout <<p->data <<"\t"; p=p->next;}cout<<endl;}int main(){ int i,x,e,choose; LinkList L; cout << "1. 初始化\n"; cout << "2. 创建单链表(前插法)\n"; cout << "3. 创建单链表(尾插法)\n"; cout << "4. 取值\n"; cout << "5. 查找\n"; cout << "6. 插入\n"; cout << "7. 删除\n"; cout << "8. 输出\n"; cout << "0. 退出\n"; choose=-1; while (choose!=0){ cout<<"请输入数字选择:"; cin>>choose; switch (choose) { case 1: //初始化一个空的单链表 if (InitList_L(L)) cout << "初始化一个空的单链表!\n"; break; case 2: //创建单链表(前插法) CreateList_H(L); cout << "前插法创建单链表输出结果:\n"; Listprint_L(L); break; case 3: //创建单链表(尾插法) CreateList_R(L); cout << "尾插法创建单链表输出结果:\n"; Listprint_L(L); break; case 4: //单链表的按序号取值 cout << "请输入一个位置i用来取值:"; cin >> i; if (GetElem_L(L,i,e)){ cout << "查找成功\n"; cout << "第" << i << "个元素是:"<<e<< endl; } else cout << "查找失败\n\n"; break; case 5: //单链表的按值查找 cout<<"请输入所要查找元素x:"; cin>>x; if (LocateElem_L(L,x)) cout << "查找成功\n"; else cout << "查找失败! " <<endl; break; case 6: //单链表的插入 cout << "请输入插入的位置和元素(用空格隔开):"; cin >> i; cin >> x; if (ListInsert_L(L, i, x)) cout << "插入成功.\n\n"; else cout << "插入失败!\n\n"; break; case 7: //单链表的删除 cout<<"请输入所要删除的元素位置i:"; cin>>i; if (ListDelete_L(L, i)) cout<<"删除成功!\n"; else cout<<"删除失败!\n"; break; case 8: //单链表的输出 cout << "当前单链表的数据元素分别为:\n"; Listprint_L(L); cout << endl; break; } } return 0;} 顺序栈基本操作123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include<iostream>using namespace std;#define Maxsize 100 //预先分配空间,这个数值根据实际需要预估确定;typedef struct SqStack { int *base; //栈底指针 int *top; //栈顶指针}SqStack;bool InitStack(SqStack &S) //构造一个空栈S{ S.base = new int[Maxsize];//为顺序栈分配一个最大容量为Maxsize的空间 if (!S.base) //空间分配失败 return false; S.top=S.base; //top初始为base,空栈 return true;}bool Push(SqStack &S, int e) // 插入元素e为新的栈顶元素{ if (S.top-S.base == Maxsize) //栈满 return false; *(S.top++) = e; //元素e压入栈顶,然后栈顶指针加1,等价于*S.top=e; S.top++; return true;}bool Pop(SqStack &S, int &e) //删除S的栈顶元素,暂存在变量e中{ if (S.base == S.top) //栈空 return false; e = *(--S.top); //栈顶指针减1,将栈顶元素赋给e 等价于S.top--; e=*S.top; return true;}int GetTop(SqStack S) //返回S的栈顶元素,栈顶指针不变{ if (S.top != S.base) //栈非空 return *(S.top - 1); //返回栈顶元素的值,栈顶指针不变 else return -1;}int main(){ int n,x; SqStack S; InitStack(S);//初始化一个顺序栈S cout <<"请输入元素个数n:" <<endl; cin>>n; cout <<"请依次输入n个元素,依次入栈:" <<endl; while(n--) { cin>>x; //输入元素 Push(S, x); } cout <<"元素依次出栈:" <<endl; while(S.top!=S.base)//如果栈不空,则依次出栈 { cout<<GetTop(S)<<"\t";//输出栈顶元素 Pop(S, x); //栈顶元素出栈 } return 0;} 链栈基本操作1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include<iostream>using namespace std;typedef struct Snode { int data; //数据域 struct Snode *next; //指针域}Snode,*LinkStack;bool InitStack(LinkStack &S) //构造一个空栈S{ S=NULL; return true;}bool Push(LinkStack &S, int e) //在栈顶插入元素e{ LinkStack p; p = new Snode; //生成新结点 p->data = e; //将e放在新结点数据域 p->next = S; //将新结点的指针域指向S,即将S的地址赋值给新结点的指针域 S = p; //修改栈顶指针为p return true;}bool Pop(LinkStack &S, int &e) //删除S的栈顶元素,用e保存其值{ LinkStack p; if (S==NULL) //栈空 return false; e=S->data; //将栈顶元素赋给e p=S; //用p保存栈顶元素地址,以备释放 S=S->next; //修改栈顶指针,指向下一个结点 delete p; //释放原栈顶元素的空间 return true;}int GetTop(LinkStack S) //返回S的栈顶元素,不修改栈顶指针{ if (S!=NULL) //栈非空 return S->data; //返回栈顶元素的值,栈顶指针不变elsereturn -1;}int main(){ int n,x; LinkStack S; InitStack(S);//初始化一个顺序栈S cout <<"请输入元素个数n:" <<endl; cin>>n; cout <<"请依次输入n个元素,依次入栈:" <<endl; while(n--){ cin>>x; //输入元素 Push(S, x); } cout <<"元素依次出栈:" <<endl; while(S!=NULL)//如果栈不空,则依次出栈{cout<<GetTop(S)<<"\t";//输出栈顶元素Pop(S, x); //栈顶元素出栈} return 0;} 二叉树的创建123456789101112131415161718192021222324252627282930313233343536#include <iostream>using namespace std;typedef struct Bnode /*定义二叉树存储结构*/{ char data; struct Bnode *lchild,*rchild;}Bnode,*Btree;void createtree(Btree &T) /*创建二叉树函数*/{ char check; /*判断是否创建左右孩子*/ T=new Bnode; cout<<"请输入结点信息:"<<endl; /*输入根结点数据*/ cin>>T->data; cout<<"是否添加 "<<T->data<<"的左孩子? (Y/N)"<<endl; /*询问是否创建T的左子树*/ cin>>check; if(check=='Y') createtree(T->lchild); else T->lchild=NULL; cout<<"是否添加"<<T->data<<"的右孩子? (Y/N)"<<endl; /*询问是否创建T的右子树*/ cin>>check; if(check=='Y') createtree(T->rchild); else T->rchild=NULL; return;}int main(){ Btree mytree; createtree(mytree);/*创建二叉树*/ return 0;} 二叉树的层次遍历123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include <iostream>#include <queue> //引入队列头文件using namespace std;typedef struct Bnode /*定义二叉树存储结构*/{ char data; struct Bnode *lchild,*rchild;}Bnode,*Btree;void Createtree(Btree &T) /*创建二叉树函数*/{ //按先序次序输入二叉树中结点的值(一个字符),创建二叉链表表示的二叉树T char ch; cin >> ch; if(ch=='#') T=NULL; //递归结束,建空树 else { T=new Bnode; T->data=ch; //生成根结点 Createtree(T->lchild); //递归创建左子树 Createtree(T->rchild); //递归创建右子树 } return;}bool Leveltraverse(Btree T) //层次遍历{ Btree p; if(!T) return false; queue<Btree>Q; //创建一个普通队列(先进先出),里面存放指针类型 Q.push(T); //根指针入队 while(!Q.empty()) //如果队列不空 { p=Q.front();//取出队头元素 Q.pop(); //队头元素出队 cout<<p->data<<"\t"; if(p->lchild) Q.push(p->lchild); //左孩子指针入队 if(p->rchild) Q.push(p->rchild); //右孩子指针入队 } return true;}int main(){ Btree mytree; cout<<"按先序次序输入二叉树中结点的值(孩子为空时输入#),创建一棵二叉树"<<endl; Createtree(mytree);//创建二叉树 cout<<endl; cout<<"二叉树的层次遍历结果:"<<endl; Leveltraverse(mytree);//层次遍历二叉树 return 0;} 赏 谢谢你请Leo吃糖果哦 支付宝 微信 数据结构与算法 扫一扫,分享到微信