数据结构与算法

#include <stdio.h>
#include <time.h> 
clock_t tart,stop;
double duration;
int main(){
start=clock();
MyFunction();
 stop=clock();
 duration = ((double)(stop-start))/CLK_TCK;
 return 0;
 }

List MakeEmpty()//初始化（建立空的顺序表）
{
    List Ptrl;
    Ptrl = (List)malloc(sizeof(struct LNode));
    Ptrl->Last=-1;
    return Ptrl;
}
int Find(ElementType x,List Ptrl)//查找
{
    int i=0;
    while(i<=Ptrl->Last && Ptrl->Data[i]!=x)
    i++;
    if(i>Ptrl->Last) return -1;
    else return i;
}
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];
    Ptrl->Date[i-1]=x;
    Ptrl->Last++;
    return;
}
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->Date[j];
    Ptrl->Last--;
    return;    
}

Typedef Struct LNode*List;//初始化定义
struct LNode{
    ElementType Data;
    List Next;
};
struct Lnode L;
List Ptrl;


int Length(List Ptrl)//求表长（链表遍历）
{
    List p=Ptrl;
    int j=0;
    while(p){
        p=p->Next;
        j++;
    }
    return j;
}
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;
}
List Find(ElementType x,List Ptrl)//按值查找
{
    List p=Ptrl;
    while(p!=NULL && p->Data!=x)
        p=p->Next;
    return p;
}
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个位置，查找第i-1个结点
    if(p==NULL){//不存在，不能插入
        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;
    }
}
List Delete(int i,List Ptrl)//删除操作
{
    List p,s;
    if(i==1){//如果删除头结点
        s=Ptrl;
        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 uf(p->Next == NULL){
        printf("第%d个结点不存在",i); return NULL;
    } else {
        s=p->Next;
        P->Next = s->Next;
        free(s);
        return Ptrl;
    }
}

#define MaxSize <储存数据元素的最大个数>
typedef struct SNode *Stack;
struct SNode{
    ElementType Data[MaxSize];
    int Top;
};
//入栈
void Push(Stack Ptrs，ElementType item)
{
    if(Ptrs->Top == MaxSize-1){
        printf("堆栈满"); return ;
    } else {
        Ptrs->Data[++(Ptrs->Top)]=item;
        return ;
    }
}
//出栈
ElementType(Stack Ptrs)
{
    if(Ptrs->Top == -1){
        printf("堆栈空");
        return RTTOR;
    } else return(Ptrs->Data[(Ptrs->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)//判断堆栈是否为空?1:0
{
    return (s->Next == NULL);
}
void Push (ElementType item,Stack s)//将元素item压入堆栈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)){
        pintf("堆栈空"); return NULL;
    } else {
        FirstCell=s->Next;
        s->Next=FirstCell->Next;
        TopElem=FirstCell->Element;
        free(FirstCell);
        return TopElem;
    }
}

#define MaxSize <储存数据元素的最大个数>
struct QNode{
    ElementType Data[MaxSize];
    int rear;
    int front;
};
typedef struct QNode *Queue;
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;
}
ElementType DeleteQ(Queue Ptrq)//出队列
{
    if(Ptrq->front == Ptrq->rear){
        printf("队列空");
        return ERROR;
    } else {
        Ptrq->front=(Ptrq->front+1)%MaxSize;
        return Ptrq->Data[Ptrq->front];
    }
}

struct Node{
    ElementType Data;
    strct Node *Next;
};
struct QNode{
    struct Node *rear;
    struct Node *front;
};
typedef struct QNode *Queue;
Queue Ptrq;
//出队操作
ElementType DeleteQ(Queue Ptrq)
{
    struct Node *FrontCell;//要弄出队列的变量
    ElementTye *fromtElem;
    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;
}

int BinarySearch(List Tbl,RlementType k)
{
    int left,right,mid,NoFound=-1;
    left = 2;
    right=Tbl->Length;
    while(left <= right)
    {
        mid=(left+right)/2;
        if(k<Tbl->Element[mid]) right=mid-1;
        else if(k>Tbl->Element[mid]) left=mid+1;
        else return mid;
    }
    return NotFound;
}