代码如下:
/*
* Stack.h
*
* Created on: May 30, 2011
* Author: 小E QQ592646022
*/
#ifndef STACK_H_
#define STACK_H_
#include <iostream>
using namespace std;
typedef int type;
typedef struct Node
{
type data;
struct Node * next;
}Stack,*pStack; //堆栈的基本结构
void StackInit(pStack &S) //堆栈初始化
{
S=new Stack;
S->data=0;
S->next=NULL;
}
type StackGetLenth(pStack S) //堆栈取长度
{
return S->data;
}
bool StackEmpty(pStack S)
{
if(S->next==NULL)
return true;
return false;
}
void StackPush(pStack S,type e) //入栈
{
pStack t;
t=new Stack;
t->data=e;
if(StackEmpty(S))
{
t->next=NULL;
S->next=t;
}
else
{
t->next=S->next;
S->next=t;
}
S->data++;
}
type StackPop(pStack S) //出栈
{
type p;pStack t;
if(StackEmpty(S))
{
cout<<"堆栈为空"<<endl;
return -1;
}
t=S->next;
p=t->data;
S->next=t->next;
delete[] t;
S->data--;
return p;
}
type StackGetTop(pStack S) //取栈顶元素 不弹出
{
if(StackEmpty(S))
{
cout<<"堆栈为空"<<endl;
return -1;
}
return S->next->data;
}
#endif /* STACK_H_ */
测试代码:
功能:实现括号匹配。
输入案例: 正确 (()()()) ,错误 )()(()
#include <iostream.h>
#include "Stack.h"
bool match(char* str)
{
pStack s;
StackInit(s);
while(*str!='/0')
{
if(*str=='(')
StackPush(s,'(');
else if(*str==')')
{
if(StackGetLenth(s)==0)
return false;
StackPop(s);
}
str++;
}
if(StackGetLenth(s)==0)
return true;
return false;
}
void brackets_match_stack_test(){ //括号匹配测试,测试堆栈正确性
char* str;
str=new char[100];
cin>>str;
if(match(str))
cout<<"匹配"<<endl;
else
cout<<"不匹配"<<endl;
}
int main()
{
brackets_match_stack_test();
return 0;
}
截图:
二、Queue 篇
1.实现基本的入队、出队操作以及取队头元素等等
2.可以动态增加元素
3.没什么好说的,看代码
代码如下:
/*
* Queue.h
*
* Created on: May 30, 2011
* Author: 小E qq592646022
*/
#ifndef QUEUE_H_
#define QUEUE_H_
#include <iostream>
using namespace std;
#define SIZE 100
#define INCRESIZE 10
typedef int type;
typedef struct
{
int size,len;
int fron,rear;
type* data;
}* pQueue,Queue;
void QueueInit(pQueue Q) //队列初始化
{
Q->data=new type[SIZE];
Q->fron=-1;
Q->rear=-1;
Q->size=SIZE;
Q->len=0;
}
bool QueueEmpty(pQueue Q) //判断是否为空
{
if((Q->fron==-1)||(Q->fron==Q->rear+1&&Q->len==0))
return true;
return false;
}
int QueueGetLenth(pQueue Q)
{
return Q->len;
}
void QueueIncre(pQueue Q) //增加长度
{
int len;
type* t;
t=new type[Q->size+INCRESIZE];
for(len=0;len<QueueGetLenth(Q);len++)
{
t[len]=Q->data[Q->fron%(Q->size)];
Q->fron++;
}
delete Q->data;
Q->data=t;
Q->fron=0;
Q->rear=len-1;
Q->size+=INCRESIZE;
}
bool QueueIn(pQueue Q,type e) //入队列
{
if(Q->len>=Q->size)
QueueIncre(Q);
if(QueueEmpty(Q))
{
Q->fron=0;
Q->rear=0;
Q->data[Q->fron]=e;
Q->len++;
}
else
{
Q->rear++;
Q->data[Q->rear%(Q->size)]=e;
Q->len++;
}
return true;
}
type QueueOut(pQueue Q) //入队列
{
type tmp;
if(QueueEmpty(Q))
{
tmp=-1;
cout<<"队列为空操作失败"<<endl;
return tmp;
}
else
{
tmp=Q->data[Q->fron];
Q->fron++;
Q->len--;
}
return tmp;
}
void QueueTrav(pQueue Q) //遍历队列显示结果
{
int i=1,p;
p=Q->fron;
while(i<=Q->len)
{
cout<<Q->data[p%(Q->size)]<<" ";
p++;
i++;
}
}
type QueueGetHead(pQueue Q) //取队头元素
{
type a=-1;
if(QueueEmpty(Q))
return a;
return Q->data[Q->fron];
}
#endif /* QUEUE_H_ */
测试代码:
功能:实现杨辉三角输出
void pascal_triangle_queue_test(){ //杨辉三角测试,测试队列正确性
Queue a;
QueueInit(&a);
int i;
for(i=0;i<300;i++)
QueueIn(&a,rand()%300);
QueueTrav(&a);
cout<<endl;
cout<<"out="<<QueueOut(&a)<<endl;
cout<<"out="<<QueueOut(&a)<<endl;
QueueTrav(&a);cout<<endl;
QueueIn(&a,34);
QueueIn(&a,21);
QueueIn(&a,2);
QueueTrav(&a);cout<<endl;
QueueIn(&a,2);
cout<<"out="<<QueueOut(&a)<<endl;
QueueIn(&a,12);
QueueTrav(&a);cout<<endl;
}
int main()
{
//brackets_match_stack_test();
pascal_triangle_queue_test();
return 0;
}
截图:
由于太长看不到结果,所以请自己实验。
三、List 篇
1.目标实现基本的插入,删除,获取等等
代码:
/*
* List.h
*
* Created on: May 30, 2011
* Author: 小E qq592646022
*/
#ifndef LIST_H_
#define LIST_H_
#include <iostream>
using namespace std;
typedef int type;
typedef struct Node1 {
type data;
struct Node1* next;
} List, *pList;
void ListInit(pList L) { //List 初始化
L->data = 0;
L->next = NULL;
}
bool ListEmpty(pList L) { //List判断是否为空
if (L->data == 0)
return true;
return false;
}
type ListGetLength(pList L) {
return L->data;
}
bool ListInsert(pList L, int pos, type e) { //List 插入元素
pList p = L;
int i = 1;
pList t = new List;
t->data = e;
if (pos < 1 || pos > ListGetLength(L) + 1) {
cout << "位置不合理" << endl;
return false;
}
if (ListEmpty(L)) {
t->next = NULL;
L->next = t;
}
while (i < pos) {
p = p->next;
i++;
}
t->next = p->next;
p->next = t;
L->data++;
return true;
}
type ListDelet(pList L, int pos) { //删除元素
pList p = L, t;
type e;
int i = 1;
if (pos < 1 || pos > ListGetLength(L)) {
cout << "位置不合理" << endl;
return -1;
}
if (ListEmpty(L)) {
cout << "链表为空,删除失败" << endl;
return -1;
}
while (i < pos) {
p = p->next;
i++;
}
t = p->next;
e = t->data;
p->next = p->next->next;
delete t;
L->data--;
return e;
}
type ListGetElem(pList L, int pos) { //获取元素
int i = 1;
pList p = L;
if (pos < 1 || pos > ListGetLength(L) + 1) {
cout << "位置不合理" << endl;
return -1;
}
if (ListEmpty(L)) {
cout << "链表为空,取元素失败" << endl;
return -1;
}
while (i <= pos) {
p = p->next;
i++;
}
return p->data;
}
int ListLocate(pList L, type e) { //获取位置
int i = 1;
pList p = L->next;
if (ListEmpty(L)) {
cout << "链表为空,操作失败" << endl;
return -1;
}
while (p->data != e && i <= ListGetLength(L)) {
p = p->next;
i++;
}
if (p->data == e)
return i;
return -1;
}
void ListTrav(pList L) { //遍历
pList p;
int i = ListGetLength(L);
p = L->next;
while (i != 0) {
cout << p->data << " ";
p = p->next;
i--;
}
}
/*void ListTrav(pList L)
{
pList p;
p=L->next;
while(p->next!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
}
*/
#endif /* LIST_H_ */
测试代码:
void list_test(){ //测试 链表
List l;
ListInit(&l);
for(int i=1;i<20;i++)
{
ListInsert(&l,1,i);
}
ListTrav(&l);
cout<<endl;
ListInsert(&l,5,1111);
ListTrav(&l);
cout<<endl;
cout<<ListGetElem(&l,3)<<endl;
}
int main()
{
//brackets_match_stack_test();
//pascal_triangle_queue_test();
list_test();
return 0;
}
截图:
四、String 篇
1.目标实现基本操作如
/*
* String.h
*
* Created on: May 30, 2011
* Author: 小E qq592646022
*/
#ifndef STRING_H_
#define STRING_H_
#include <iostream>
using namespace std;
#define MAX 20
#define INCRESIZE 10
typedef struct string
{
char *s;
int length;
}String,* pString;
void StringInit(String &S) //初始化
{
S.length=0;
char *s=new char[MAX];
S.s=s;
}
bool StringEmpty(pString S) //判断是否为空
{
if(S->length==0)
return true;
return false;
}
int StringGetLength(pString S) //取长度
{
return S->length;
}
void StringIncre(pString S) //增加
{
char* t=new char[S->length+INCRESIZE];
int i=0;
while(i<StringGetLength(S))
{
t[i]=S->s[i];
i++;
}
delete[] S->s;
S->s=t;
}
void StringInsert(pString S,int pos,char* str) //插入
{
if(pos>=1&&pos<=StringGetLength(S)+1)
{
if(StringEmpty(S))
{
S->s[0]=*str;
S->length++;
}
else if(StringGetLength(S)>S->length+INCRESIZE-1)
{
StringIncre(S);
}
else
{
pos--;
for(int i=StringGetLength(S);i>pos;i--)
S->s[i]=S->s[i-1];
S->s[pos]=*str;
S->length++;
}
}
else
cout<<"位置不合理0"<<endl;
}
void StringTrav(pString S) //遍历
{
int i=0;
while(i<StringGetLength(S))
{
cout<<S->s[i];
i++;
}
}
void StringInserts(pString S,int start,char* T) //插入多个
{
int i=1;
while((*T)!='/0')
{
StringInsert(S,i+start-1,T);
T++;
i++;
}
}
bool StringDelete(pString S,int pos) //删除
{
if(pos>=1&&pos<=StringGetLength(S)+1)
{
if(StringEmpty(S))
{
cout<<"字符串为空,删除失败"<<endl;
return false;
}
pos--;
for(int i=pos;i<StringGetLength(S);i++)
{
S->s[i]=S->s[i+1];
}
S->length--;
return true;
}
cout<<"位置不合理1"<<endl;
return false;
}
bool StringDeletes(pString S,int pos,int length) //删除多个
{
if(length>(StringGetLength(S)-pos))
{
cout<<"要删除的字符长度超过了字符末尾,删除到没有为止"<<endl;
length=(StringGetLength(S)-pos+1);
}
if(length<1)
{
cout<<"删除失败,传入长度不正确"<<endl;
return false;
}
while(length>0)
{
if(StringDelete(S,pos)==0)
return false;
length--;
}
return true;
}
int StringIndex(pString S,pString T) //取位置
{
int i=0,j=0,count=0;
while(i<=(S->length)&&j<=(T->length))
{
if(T->s[j]==S->s[i])
{
i++;j++;
count++;
if(count>=T->length)
return i-count+1;
}
else
{
i-=count;;j=0;count=0;
i++;
}
}
return 0;
}
#endif /* STRING_H_ */
测试代码:
void string_test(){ //测试string
String s;
StringInit(s);
char a[]="abeacabeaabcd";
StringInserts(&s,1,a);
StringTrav(&s);cout<<endl;
String t;
StringInit(t);
char b[]="eac";
StringInserts(&t,1,b);
StringTrav(&t);cout<<endl;
//StringDeletes(&s,7,3);
cout<<"index="<<StringIndex(&s,&t)<<endl;
}
int main()
{
//brackets_match_stack_test();
//pascal_triangle_queue_test();
//list_test();
string_test();
return 0;
}
截图:
好了,就这样,实现了基本操作。至于效率有的还有待改进。 数据结构实现doc