算法基礎部分
算法是對特定問題求解步驟的一種描述嫡锌，算法是指令的有限序列伪冰，其中每一條指令表示一個或多個操作繁疤。
算法具有以下5個屬性：
- 有窮性：一個算法必須總是在執(zhí)行有窮步之后結束钠惩，且每一步都在有窮時間內完成。
- 確定性：算法中每一條指令必須有確切的含義苞笨。不存在二義性债朵。只有一個入口和一個出口
- 可行性：一個算法是可行的就是算法描述的操作是可以通過已經實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。
- 輸入：一個算法有零個或多個輸入，這些輸入取自于某個特定對象的集合。
- 輸出：一個算法有一個或多個輸出丁恭，這些輸出同輸入有著某些特定關系的量。
所以對應的算法設計的要求：
- 正確性：算法應滿足具體問題的需求谚中；
- 可讀性：算法應該好讀，以有利于讀者對程序的理解寥枝；
- 健壯性：算法應具有容錯處理宪塔，當輸入為非法數(shù)據(jù)時，算法應對- 其作出反應囊拜，而不是產生莫名其妙的輸出結果某筐。
- 效率與存儲量需求：效率指的是算法執(zhí)行的時間；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間艾疟。一般這兩者與問題的規(guī)模有關来吩。
順序表：
- 線性表（a1敢辩，a2…蔽莱，an）有唯一的第一個和最后一個元素（n≥0）。其余的有唯一的前驅和后繼戚长。
- 順序表定義：用一組地址連續(xù)的存儲單元依次存放的數(shù)據(jù)元素盗冷。
在順序表的第i個位置前插入一個數(shù)據(jù)元素，需要向后移動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);
}
- 鏈表
鏈表是一種物理存儲單元上非連續(xù)柑司、非順序的存儲結構，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序實現(xiàn)的.
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;//定點數(shù)和邊數(shù)
}MGraph;
void createMGraph(MGraph &G)
{
int i,j,k;
char ch1,ch2;
cout<<"請輸入頂點數(shù)和邊數(shù):"<<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("深度優(yōu)先遍歷結點: 結點%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;
}
}
}
