算法基础部分
算法是对特定问题求解步骤的一种描述，算法是指令的有限序列，其中每一条指令表示一个或多个操作。
算法具有以下5个属性：
- 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
- 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口
- 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。
- 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。
- 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。
所以对应的算法设计的要求：
- 正确性：算法应满足具体问题的需求；
- 可读性：算法应该好读，以有利于读者对程序的理解；
- 健壮性：算法应具有容错处理，当输入为非法数据时，算法应对- 其作出反应，而不是产生莫名其妙的输出结果。
- 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。
顺序表：
- 线性表（a1，a2…，an）有唯一的第一个和最后一个元素（n≥0）。其余的有唯一的前驱和后继。
- 顺序表定义：用一组地址连续的存储单元依次存放的数据元素。
在顺序表的第i个位置前插入一个数据元素，需要向后移动n － i ＋1个元素，删除第i个位置的元素需要向前移动n－ i个元素。
#include <stdio.h>
#include <malloc.h>
typedef char ElemType;
typedef struct
{
ElemType data[MAX_SIZE];
int len;
}SqList;
//初始化顺序表
void initList(SqList *&L)
{
L=(SqList *)malloc(sizeof(SqList));
L->len=0;
}
//插入元素
void insertList(SqList *&L,int i,ElemType e)
{
i--;
int j;
for(j=L->len;j>i;j--)
L->data[j]=L->data[j-1];
L->data[i]=e;
L->len++;
}
//删除第i个位置的元素
void deleteList(SqList *&L,int i)
{
i--;
ElemType e=L->data[i];
for(int j=i;j<L->len-1;j++)
L->data[j]=L->data[j+1];
L->len--;
printf("%c",e);
}
//输出元素
void disPlay(SqList *L)
{
int i;
for(i=0;i<;L->len;i++)
printf("%c ",L->data[i]);
}
//释放顺序表
void freeList(SqList *L)
{
free(L);
}
- 链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的.
typedef char ElemType;
typedef struct Node
{
ElemType data;
struct Node *next;
}LinkList;
//初始化链表
void initLink(LinkList *&L)
{
L=(LinkList *)malloc(sizeof(LinkList));
L->next=NULL;
}
//链表插入
int insertLink(LinkList *&L,int i,ElemType e)
{
LinkList *p=L,*s;
int j=0;
while(j<i-1 && p!=NULL)
{
j++;
p=p->next;
}
if(p==NULL) return 0;
else
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=e;
s->next=p->next;
p->next=s;
}
return 1;
}
//删除链表中元素
void deleteList(LinkList *L)
{
LinkList *p=L,*q=p->next;
while(q!=NULL)
{
free(p);
p=q;
q=p->next;
}
}
//输出链表
void disPlsy(LinkList *L)
{
LinkList *p=L->next;
while(p!=NULL)
{
printf("%c ",p->data);
p=p->next;
}
}
- 栈
#define MAX_SIZE 100
typedef char ElemType;
typedef struct
{
ElemType data[MAX_SIZE];
int top;
}Stack;
//初始化栈
void initStack(Stack *&S)
{
S=(Stack *)malloc(sizeof(Stack));
S->top=-1;
}
//元素进栈
int push(Stack *&S,ElemType e)
{
if(S->top==MAX_SIZE-1) return 0;
S->top++;
S->data[S->top]=e;
return 1;
}
//出栈
int pop(Stack *&S)
{
if(S->top==-1) return 0;
ElemType e=S->data[S->top];
S->top--;
return e;
}
//输出栈表
void disPlay(Stack *S)
{
int i;
for(i=S->top;i>=0;i--)
printf("%c ",S->data[i]);
}
- 队列
#define MAXSIZE 10
typedef char ElemType;
typedef struct
{
ElemType data[MAXSIZE];
int font,rear;
}Queue;
//初始化队列
void initQueue(Queue *&Q)
{
Q=(Queue *)malloc(sizeof(Queue));
Q->font=Q->rear=0;
}
//入队
int enQueue(Queue *&Q,ElemType e)
{
if((Q->rear+1)%MAXSIZE==Q->font) return 0;
Q->rear=(Q->rear+1)%MAXSIZE;
Q->data[Q->rear]=e;
return 1;
}
//出队
void deQueue(Queue *&Q)
{
ElemType e;
// if(Q->font==Q->rear) ;
Q->font=(Q->font+1)%MAXSIZE;
e=Q->data[Q->font];
printf("%c ",e);
}
- 二叉树
typedef char ElemType;
typedef struct node
{
ElemType data;
struct node *left,*right;
}BTNode;
//建立二叉树
void createBTNode(BTNode *&b,char *str)
{
BTNode *St[MAX_SIZE],*p=NULL;
int top=-1,k,i=0;
char ch=str[i];
b=NULL;
while(ch!='\0')
{
switch(ch)
{
case '(':
top++;
St[top]=p;
k=1;
break;
case ',':
k=2;
break;
case ')':
top--;
break;
default:
p=(BTNode *)malloc(sizeof(BTNode));
p->data=ch;
p->left=p->right=NULL;
if(b==NULL) b=p;
else
{
switch(k)
{
case 1:
St[top]->left=p;
break;
case 2:
St[top]->right=p;
break;
}
}
}
i++;
ch=str[i];
}
}
//先序遍历
void disPlay(BTNode *&b)
{
if(b!=NULL)
{
printf("%c ",b->data);
disPlay(b->left);
disPlay(b->right);
}
}
//先序遍历的非递归方法
void preOrder(BTNode *b)
{
BTNode *St[MAX_SIZE];
BTNode *p;
int top=-1;
if(b!=NULL)
{
top++;
St[top]=b;
while(top>-1)
{
p=St[top];
top--;
printf("%c ",p->data);
if(p->right!=NULL)
{
top++;
St[top]=p->right;
}
if(p->left!=NULL)
{
top++;
St[top]=p->left;
}
}
}
}
- 图
#define MAX_SIZE 100
#include "queue"
typedef char VertexType;
typedef int EdgeType;
typedef enum {FALSE,TRUE} Boolean;
Boolean visited[MAX_SIZE];
typedef struct
{
VertexType verx[MAX_SIZE]; //顶点表
EdgeType edges[MAX_SIZE][MAX_SIZE];//邻接矩阵
int n,e;//定点数和边数
}MGraph;
void createMGraph(MGraph &G)
{
int i,j,k;
char ch1,ch2;
cout<<"请输入顶点数和边数:"<<endl;
cin>>G.n;
cin>>G.e;
for(i=0;i<G.n;i++)
for(j=0;j<G.n;j++)
G.edges[i][j]=0;
cout<<"请输入顶点信息";
for(i=0;i<G.n;i++)
cin>>G.verx[i];
cout<<"请输入变的信息:"<<endl;
for(k=0;k<G.e;k++)
{
cin>>ch1>>ch2;
for(i=0;ch1!=G.verx[i];i++);
for(j=0;ch2!=G.verx[j];j++);
G.edges[i][j]=1;
}
}
void DFSM(MGraph &G,int i)
{
int j;
printf("深度优先遍历结点: 结点%c/n",G.verx[i]); //访问顶点vi
visited[i]=TRUE;
for(j=0;j<G.n;j++) //依次搜索vi邻接点
if(G.edges[i][j]==1 && !visited[j])
DFSM(G,j);
}
void DFSTraverseM(MGraph &G)
{
int i;
for(i=0;i<G.n;i++)
visited[i]=FALSE;
for(i=0;i<G.n;i++)
if(!visited[i])
DFSM(G,i);
}
void BFSM(MGraph &G,int i)
{
queue<char> charqueue;
visited[i]=TRUE;
int j;
printf("%c ",G.verx[i]);
charqueue.push(i);
while(!charqueue.empty())
{
charqueue.pop();
j=G.verx[i];
for(int k=0;k<G.n;k++)
if(G.edges[j][k]==1 && !visited[k])
{
printf("%c ",G.verx[k]);
visited[i]=TRUE;
charqueue.push(G.verx[k]);
}
}
}
void BFSTraverseM(MGraph &G)
{
int i;
for(i=0;i<G.n;i++)
visited[i]=FALSE;
for(i=0;i<G.n;i++)
if(!visited[i])
BFSM(G,i);
}
查找
排序
//插入排序
void insertSort(int *num,int n)
{
int i,j,temp;
for(i=1;i<n;i++)
{
j=i;
temp=num[j];
while(j>0 && num[j-1]>temp)
{
num[j]=num[j-1];
j--;
}
num[j]=temp;
}
}
//冒泡排序
void bollSort(int * num,int n)
{
int i,j,temp;
for(i=0;i<n-1;i++)
for(j=n-1;j>=i;j--)
{
if(num[j]<num[j-1])
{
temp=num[j];
num[j]=num[j-1];
num[j-1]=temp;
}
}
}
