Ps:只关心是什么,不关心怎么做到,
算法(Algorithm)
什么是好的算法
分析算法效率一般关心下面两种复杂度
复杂度的渐进表示方法
T(n)=O(f(n))表示存在常数C>0,n0>0使得当n>=n0时有T(n)<=C*f(n)上界(一般取最小上界)
T(n)=Ω(g(n))表示存在常数C>0,n0>0使得当n>=n0时有T(n)>=C*g(n)下界 (一般取最大下界)
表示同时有T(n)=O(h(o))和T(n)=Ω(h(n))
ps:一般遇到O(n2)算法想办法转换为O()
线性表的存储
顺序存储实现:利用数组的连续存储空间存放线性表的各元素
typedef struct LNode *List;
struct LNode{
ElementType Data[MAXSIZE];
int Last;//最后一个元素所在的位置
};
struct LNode L;
List PtrL;
L.Data[i]或Ptrl->Data[i]//访问下标为i的元素
L.Last+1或PtrL->Last+1//线性表的长度
1.初始化(建立空的顺序表)
List MakeEmpty( )
List PtrL;
PtrL = (List ) malloc( sizeof (struct LNode) ) ;
PtrL- >Last = -1;
return PtrL;
}
2.查找
/*平均比较次数(n+1)/2,平均性能O(n)*/
int Find( ElementType X,List PtrL )
int i=0;
while( i <= PtrL->Last && PtrL- >Data[i]!= X )
i++;
if (i > PtrL->Last) return -1; /*如果没找到,返回-1 */
else return i;/*找到后返回的是存储位置*/
3.插入(第个位置上插入一个值为X的新元素)
void Insert( ElementType X, int i, List PtrL )
{
int j;
if( PtrL->Last == MAXSIZE-1 ){/*表空间已满,不能插入*/
printf("表满" );
return;
}
if(i<1||i> PtrL->Last+2) {/*检查插入位置的合法性*/
printf("位置不合法" );
return;
}
for(j= PtrL->Last; j>= i-1;j--)
PtrL->Data[j+1] = PtrL->Data[j]; /*将 ai- an倒序向后移动*/
PtrL->Data[i-1] = X;/*新元素插入*/
PtrL->Last++;/*Last仍指向最后元素*/
return;
4.删除(删除表第i(l<=i<=n)个位置上的元素)
/*平均移动次数(n-1)/2,O(n)*/
void Delete( int i, List PtrL )
{ int j;
if(i<1 ||i> PtrL->Last+1 ) {/*检查空表及删除位置的合法性*/
printf (“不存在第%d个元素”, i);
return ;
for(j=i;j<= PtrL>Last; j++ )
PtrL->Data[j-1] = PtrL->Data[j];/*将 ai+1~ an顺序向前移动*/
PtrL->Last--;/*Last仍指向最后元素*/
return;
}
线性表的链式存储实现
不要求逻辑上相邻的两个元素物理上也相邻;通过“链”建立起数据元素之间的逻辑关系
typedef struct LNode *List;
struct LNode{
ElementType Data;
List Next;
};
struct Lnode L;
List PtrL;
主要操作的实现
//时间性能为O(n)
int Length ( List PtrL )
{ List p= PtrL;
/* p指向表的第-一个结点*/
int j= 0;
while (p){
p= p->Next;
j++;/*当前p指向的是第j个结点*/
return j;
2.查找
(1).按序号查找:FindKth;
List FindKth( int K, List PtrL )
{
List p= PtrL;
int i= 1;
while (p !=NULL &&i< K){
p = p->Next;
i++;
if(i== K) return p;/*找到第K个,返回指针*/
else return NULL;/*否则返回空*/
}
(2).按值查找:Find
List Find( ElementType X, List
PtrL )
{
List p= PtrL;
while ( p!=NULL && p->Data != X )
p= p->Next;
return p;
3.插入(在第i-1(1<=i<=n+1)个结点后插入一个值为X的新结点)
//平均时间复杂性,O(n/2)
List Insert( ElementType X, int i, List PtrL )
{
List p, s;
if(i==1){/*新结点插入在表头*/
s = (List)malloc(sizeof(struct LNode)); /*申请、 填装结点*/
s->Data = X;
s->Next= PtrL; .
return s;/*返回新表头指针*/
}
p = FindKth( i-1, PtrL );/*查找第i-1个结点*/
if(p== NULL){/*第i-1个不存在,不能插入*/
printf( "参数i错" );
return NULL;
}else {
s = (List)malloc(sizeof(struct LNode);/*申请、填装结点*/
s->Data= X;
s->Next = p->Next;
/*新结点插入在第i-1个结点的后面*/
p->Next= S;
return PtrL;
}
4.删除(删除链表的第i(l<=i<=n)个位置上的结点)
//平均时间复杂性 O(n/2)
List Delete( int i, List PtrL )
{ List p, s;
if(i==1){/*若要删除的是表的第一个结点*/
s= PtrL;/*s指向第1个结点*/
if (PtrL!=NULL) PtrL = PtrL->Next;/*从链表中删除*/
else return NULL;
free(s);/*释放被删除结点*/
return PtrL; .
}
p = FindKth( i-1, PtrL );/*查找第i-1个结点*/
if(p== NULL){
printf(“第%d个结点不存在”,i-1); return NULL;
} else if( p->Next == NULL ){
printf(“第%d个结点不存在”, i);
return NULL;
}else {
s = p->Next;/*s指向第i个结点*/
p->Next= s->Next;/*从链表中删除*/
free(s);/*释放被删除结点*/
return PtrL;
广义表
typedef struct GNode *GList;
struct GNode{
int Tag;/*标志域: 0表示结点是单元素,1表示结点是广义表*/
union {/*子表指针域Sublist与单元素数据域Data复用,即共用存储空间*/
ElementType Data;
GList SubList;
} URegion;
GList Next;/*指向后继结点*/
};
多重链表
堆栈的抽象数据类型描述
类型名称:堆栈(Stack)
数据对象集: 一个有0个或多个元素的有穷线性表。
操作集:长度为MaxSize的堆栈S ∈Stack,堆栈元素item∈ElementType
1、Stack CreateStack( int MaxSize ): 生成空堆栈,其最大长度
为MaxSize;
2、int IsFull( Stack S, int MaxSize ):判断堆栈S是否已满;
3、void Push( Stack s, ElementType item ):将元素item压入堆栈;
4、int IsEmpty ( StackS); 判断堆栈S是否为空;
5、ElementType Pop( StackS):删除并返回栈顶元素;
#define MaxSize <储存 数据元素的最大个数>
typedef struct SNode *Stack;
struct SNode{
ElementType Data[MaxSize];
int Top;
};
(1)入栈
void Push( Stack PtrS,ElementType item)
if ( PtrS->Top == MaxSize-1 ) {
printf(“堆栈满”): return:
}else {
PtrS->Data[++(PtrS- >Top)] = item;
return;
(2)出栈
ElementType Pop( Stack PtrS )
{
if(PtrS->Top==-1 ){
printf(“堆栈空");
return ERROR;/* ERROR是ElementType的特殊值,标志错误*/
} else
return ( PtrS->Data[(PtrS-> Top)--]);
}
[例]请用一个数组实现两个堆栈,要求最大地利用数组空间,使
数组只要有空间入栈操作就可以成功。
[分析]一种比较聪明的方法是使这两个栈分别从数组的两头开始
向中间生长;当两个栈的栈项指针相遇时,表示两个栈都满了。
#define MaxSize <存储数据元素的最大个数>
struct DStack {
ElementType Data[MaxSize];
int Top1; /* 堆栈1的栈项指针*/
int Top2;
/* 堆栈2的栈项指针*/
}S;
S.Top1 = -1;
S.Top2 = MaxSize;
void Push( struct DStack *PtrS, ElementType item, int Tag )
{ /* Tag作为区分两个堆栈的标志,取值为1和2 */
if ( PtrS->Top2 - PtrS->Top1 == 1) { /*堆栈满*/
printf ("堆栈满") ;return ;
}
if ( Tag == 1 )/*对第一个堆栈操作*/
PtrS->Data [++ (PtrS->Top1)] = item;
else
/*对第二个堆栈操作*/
PtrS->Data[--(PtrS->Top2)] = item;
}
ElementType Pop( struct DStack *PtrS, int Tag )
{ /* Tag作为区分两个堆栈的标志,取值为1和2 */
if( Tag==1){ /*对第一个堆栈操作 */
if ( Ptrs->Top1 == -1 ) { /*堆栈1空*/
printf (“堆栈1空") ;
return NULL;
} else return PtrS->Data [ (PtrS->Top1)--] ;
} else { /*对第二个堆栈操作*/
if ( PtrS->Top2 == MaxSize ) { /*堆栈2空*/
printf (“堆栈2空") ; return NUlL;
} else return PtrS->Data[ (PtrS->Top2)++] ;
}
栈的链式存储结构实际上就是一个单链表,叫做链栈。插入和删除操作只能在链栈的栈顶进行。
ps:链尾不能做Top,链头才会做Top
typedef struct SNode *Stack;
struct SNode{
ElementType Data;
struct SNode *Next;
};
Stack CreateStack ()
{ /*构建一个堆栈的头结点,返回指针*/
Stack S;
S = (Stack) malloc (sizeof (struct SNode) )
S->Next = NULL;
return S ;
int IsEmpty (Stack S)
{ /*判断堆栈s是否为空,若为空函数返回整数1,则返回0 */
return ( S->Next == NULL ) ;
void Push ( ElementType item, Stack S)
{ /*将元素item压入堆栈S */
//S是堆栈的头结点,链表实现不存在满的情况
struct SNode *TmpCell ;
TmpCell= (struct SNode *)malloc (sizeof (struct SNode)) ;
TmpCell->Element = item;
TmpCell->Next = S->Next;
s->Next = TmpCell;
}
ElementType Pop (Stack S)
{ /*删除并返回堆栈s的栈项元素*/
struct SNode *FirstCell ;
ElementType TopElem ;
if( IsEmpty( S ) ) {
printf("堆找空”) ; return NULL;
} else {
FirstCell = S->Next;
S->Next = FirstCell->Next;
TopElem = FirstCell ->Element ;
free (FirstCell) ;
re turn TopElem ;
}
➢从头到尾读取中缀表达式的每个对象,对不同对象按不同的情况处理。
①运算数:直接输出;
②左括号:压入堆栈;
③右括号:将栈项的运算符弹出并输出,直到遇到左括号(出栈,不输出) ;
④运算符:
⑤若各对象处理完毕,则把堆栈中存留的运算符一并输出。
队列顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素位置的变量rear组成
#define MaxSize <储存数据元素的最大个数>
struct QNode {
ElementType Data[ MaxSize ];
int rear;
int front;
};
typedef struct QNode *Queue;
无法区分空和满(rear和front相等无法区分空和满,)
//(1)入队列
void AddQ( Queue PtrQ, ElementType item)
if ( (PtrQ->rear+1) % MaxSize == PtrQ->front ) {
printf(“队列满");
return;
}
PtrQ->rear = (PtrQ->rear+1)% MaxSize;
PtrQ->Data[PtrQ->rear] = item;
//(2)出队列
ElementType DeleteQ ( Queue PtrQ )
{
if ( PtrQ->front == PtrQ->rear){
printf(“队列空");
return ERROR;
} else {
PtrQ->front = (PtrQ->front+1)% MaxSize;//front指向队列头的前一个
return PtrQ->Data[PtrQ->front];
}
队列的链式存储结构也可以用一个单链表实现。插入和删除操作分别在链表的两头进行:队列指针front(出队操作)和rear(进行插入操作)应该分别指向链表的头和尾(链表的末尾进行删除操作不行,链表的头进行插入和删除都可以)
struct Node{
ElementType Data;
struct Node *Next;
};
struct QNode{/*链队列结构*/
struct Node *rear;/*指向队尾结点*/
struct Node *front; /* 指向队头结点*/
};
typedef struct QNode *Queue;
Queue PtrQ;
//不带头结点的链表队列出队操作的一个示例
ElementType DeleteQ ( Queue PtrQ )
{ struct Node *FrontCell;
ElementType FrontElem;
if ( PtrQ->front == NULL) {
printf(“队列空"); return ERROR;
}
FrontCell = PtrQ->front;
if ( PtrQ->front == PtrQ->rear) /* 若队列只有一个元素*/
PtrQ->front = PtrQ->rear= NULL; /* 删除后队列置为空*/
else
PtrQ->front = PtrQ->front->Next;
FrontElem = FrontCell->Data;
free( FrontCell );/*释放被删除结点空间*/
return FrontElem;
算法思路:两个指针P1和P2分别指向这两个多项式第一~个结点, 不断循环:
Polynomial PolyAdd (Polynomial P1, Polynomial P2)
Polynomial front, rear, temp;
int sum;
rear = (Polynomial) malloc(sizeof(struct PolyNode));
front= rear; /*由front记录结果多项式链表头结点*/
while (P1 &&P2) /*当两个多项式都有非零项待处理时*/
switch ( Compare(P1->expon, P2->expon) ) {
case 1:
Attach( P1->coef, P1->expon, &rear);
P1 = P1->link;
break;
case -1:
Attach(P2->coef, P2->expon, &rear);
P2= P2->link;
break;
case 0:
sum = P1->coef+ P2->coef;
if ( sum ) Attach(sum, P1->expon, &rear);
P1 = P1->link;
P2 = P2->link;
break;
}
/*将未处理完的另一个多项式的所有节点依次复制到结果多项式中去*/
for(;P1; P1 = P1->link ) Attach(P1->coef, P1->expon, &rear);
for(;P2; P2 = P2->link )Attach(P2->coef, P2->expon, &rear);
rear->link = NULL;
temp = front;
front = front->link; /*令front指向結果多项式第一个非零项*/
free(temp); /* 释放临时空表头结点*/
return front;
void Attach( int C, int e, Polynomial *pRear )
Polynomial P;
P = (Polynomial)malloc(sizeof(struct PolyNode));
P->coef=c; /* 对新结点赋值*/
P->expon= e;
P->link= NULL;
(*pRear)->link= P;
*pRear= P; /* 修改pRear值*/
本文地址:https://blog.csdn.net/weixin_42117120/article/details/107318593
如对本文有疑问, 点击进行留言回复!!
mysql中如何实现 row_number分组求topN的功能
SQLSERVER中RANK OVER(PARTITION BY)的用法
Kaspersky Endpoint Security 10 for Windows version 10.2.6.3733 is no longer supported
网友评论