c语言数据结构复习

1)线性表

//顺序存储下线性表的操作实现

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
/*线性表的顺序存储(静态)
struct List
{
    ElemType list[MaxSize];
    int size;
};
*/

//线性表的顺序存储(动态分配)
struct List
{
       ElemType *list;   /*存线性表元素的动态存储空间的指针*/
     int size;         /*存线性表长度*/
     int MaxSize;     /*存list数组长度，亦即所能存储线性表的最大长度*/
};

void againMalloc(struct List *L)
{
    ElemType *p=realloc(L->list, *L->MaxSize*sizeof(ElemType));
    //空间扩展为原来的2倍，并由p指针所指向，原内容被
    //自动拷贝到p所指向的存储空间中
    if(!p) {  //分配失败退出运行
        printf("存储空间用完!\n");
        exit();
           }
     L->list=p;               //使list指向新线性表空间
     L->MaxSize=*L->MaxSize; //把线性表空间大小修改为新的长度
}

/**********************************************************************************
1. 初始化线性表L，即进行动态存储空间分配并置L为一个空表
**********************************************************************************/
void InitList(struct List *L,int ms)
{
    /*检查ms是否有效，若无效则退出运行*/
    if(ms<=) {printf("ms值非法!\n"); exit();}
    /*置线性表空间大小为ms*/
    L->MaxSize=ms;
    /*动态存储空间分配，若分配失败则退出运行*/
    L->list=malloc(ms*sizeof(ElemType));
    if(!L->list) {
       printf("动态存储分配失败!\n");
       exit(); /*执行此函数则中止程序运行，此函数在stdlib.h中有定义*/
          }
    /*初始置线性表为空*/
    L->size=;
}

/**********************************************************************************
2. 清除线性表L中的所有元素，释放动态存储空间，使之成为一个空表
**********************************************************************************/
void ClearList(struct List *L)
{
   if(L->list!=NULL) {
      free(L->list);  /*释放存储空间*/
      L->list=;
      L->size=L->MaxSize=;
        }
}

/**********************************************************************************
3. 返回线性表L的长度，若L为空则返回0
**********************************************************************************/
int SizeList(struct List *L)
{
    return L->size;
}

/**********************************************************************************
4. 判断线性表L是否为空，若为空则返回1，否则返回0
**********************************************************************************/
int EmptyList(struct List *L)
{
    if(L->size==) return ; else return ;
}

/**********************************************************************************
5. 返回线性表L中第pos个元素的值，若pos超出范围，则停止程序运行
**********************************************************************************/
ElemType GetElem(struct List *L,int pos)
{
    if(pos<||pos>L->size) { /*若pos越界则退出运行*/
        printf("元素序号越界!\n");
        exit();
    }
    return L->list[pos-];  /*返回线性表中序号为pos值的元素值*/
}

/**********************************************************************************
6. 顺序扫描（即遍历）输出线性表L中的每个元素
**********************************************************************************/
void TraverseList(struct List *L)
{
    int i;
    for(i=;i<L->size;i++)
        printf("%d",L->list[i]);
    printf("\n");
}

/**********************************************************************************
7. 从线性表L中查找其值与x相等的元素，若查找成功则返回其位置，否则返回-1
**********************************************************************************/
int FindList(struct List *L,ElemType x)
{   int i;
    for(i=;i<L->size;i++)
        if(L->list[i]==x) return i;
    return -;
}
//当ElemType为字符串类型时，if条件表达式应该为(strcmp(L->list[i],x)==0)

/**********************************************************************************
8. 把线性表L中第pos个元素的值修改为x的值，若修改成功返回1，否则返回0
**********************************************************************************/
int UpdatePosList(struct List *L,int pos, ElemType x)
{
    if(pos< || pos>L->size+)  /*若pos越界则修改失败*/
          return ;
    L->list[pos-]=x;
    return ;
}

/**********************************************************************************
9.  向线性表L的表头插入元素x
**********************************************************************************/
void InsertFirstList(struct List *L, ElemType x)
{
     int i;
     if(L->size==L->MaxSize)
     againMalloc(L);   /*调用此函数重新分配更大的存储空间*/
      for(i=L->size-; i>=; i--)
     L->list[i+]=L->list[i];
     L->list[]=x;
     L->size++;
}
/*
下面给出againMalloc的函数定义：
void againMalloc(struct List *L)
{
    ElemType *p=realloc(L->list, 2*L->MaxSize*sizeof(ElemType));
    //空间扩展为原来的2倍，并由p指针所指向，原内容被
    //自动拷贝到p所指向的存储空间中
    if(!p) {  //分配失败退出运行
        printf("存储空间用完!\n");
        exit(1);
           }
     L->list=p;               //使list指向新线性表空间
     L->MaxSize=2*L->MaxSize; //把线性表空间大小修改为新的长度
}
//向顺序存储的线性表的表头插入一个元素时，需要移动线性表中的所有元素，所有算法的时间复杂度为O(n)，n表示线性表长度。
*/

/**********************************************************************************
10. 向线性表L的表尾插入元素x
**********************************************************************************/
void InsertLastList(struct List *L, ElemType x)
{
    if(L->size==L->MaxSize)
    againMalloc(L);   /*调用此函数重新分配更大的存储空间*/
    L->list[L->size]=x;
    L->size++;
}

/**********************************************************************************
11. 向线性表L中第pos个元素位置插入元素x，若插入成功返回1，否则返回0
**********************************************************************************/
        int InsertPosList(struct List *L, int pos, ElemType x)
        {
            int i;
            if(pos< || pos>L->size+)  /*若pos越界则插入失败*/
                return ;
            if(L->size==L->MaxSize)  /*重新分配更大的存储空间*/
                againMalloc(L);
            for(i=L->size-; i>=pos-; i--)
                L->list[i+]=L->list[i];
            L->list[pos-]=x;
            L->size++;
            return ;
        }

/**********************************************************************************
12. 向有序线性表L中插入元素x，使得插入后仍然有序
**********************************************************************************/
        void InsertOrderList(struct List *L, ElemType x)
        {
            int i,j;
          /*若数组空间用完则重新分配更大的存储空间*/
            if(L->size==L->MaxSize)
                againMalloc(L);
          /*顺序查找出x的插入位置*/
            for(i=; i<L->size; i++)
                if(x<L->list[i]) break;
          /*从表尾到下标i元素依次后移一个位置，把i位置空出*/
            for(j=L->size-; j>=i; j--)
                L->list[j+]=L->list[j];
          /*把x值赋给下标为i的元素*/
            L->list[i]=x;
          /*线性表长度增1*/
            L->size++;
        }

/**********************************************************************************
13. 从线性表L中删除表头元素并返回它，若删除失败则停止程序运行
**********************************************************************************/
ElemType DeleteFirstList(struct List *L)
{
    ElemType temp;
    int i;
    if(L->size==)
    {
        printf("线性表为空，不能删除!\n");
        exit();
    }
    temp=L->list[];
    for(i=; i<L->size; i++)
        L->list[i-]=L->list[i];
    L->size--;
    return temp;
}

/**********************************************************************************
14. 从线性表L中删除表尾元素并返回它，若删除失败则停止程序运行
**********************************************************************************/
ElemType DeleteLastList(struct List *L)
{
    if(L->size==)
    {
        printf("线性表为空，不能删除!\n");
        exit();
    }
    L->size--;
    return L->list[L->size];
}

/**********************************************************************************
15. 从线性表L中删除第pos个元素并返回它，若删除失败则停止程序运行
**********************************************************************************/
        ElemType DeletePosList(struct List *L, int pos)
        {
            ElemType temp;
            int i;
            if(pos< || pos>L->size) { /*pos越界则删除失败*/
                printf("pos值越界，不能删除!\n");
                exit();
            }
            temp=L->list[pos-];
            for(i=pos; i<L->size; i++)
                L->list[i-]=L->list[i];
            L->size--;
            return temp;
        }
    //在这个算法中，运行时间主要花费在第(3)步前移n-pos个元素的操作上。若删除任一位置上元素的概率都相同，即均为1/n，则每次删除一个元素的平均移动元素次数为，所以该算法的时间复杂度为O(n)。

/**********************************************************************************
16. 从线性表L中删除值为x的第一个元素，若删除成功返回1否则返回0
**********************************************************************************/
int DeleteValueList(struct List *L, ElemType x)
{
        int i,j;
        /*从线性表中顺序查找出值为x的第一个元素*/
        for(i=; i<L->size; i++)
        if(L->list[i]==x) break;
        /*若查找失败,表明不存在值为x的元素,应返回0*/
        if(i==L->size) return ;
        /*删除值为x的元素L->list[i]*/
        for(j=i+; j<L->size; j++)
        L->list[j-]=L->list[j];
        /*线性表长度减1*/
        L->size--;
        /*删除成功返回1*/
        return ;
}

void main()
    {
    int a[]={,,,,,,,,,};
    int i;
    struct List  L;
    InitList(&L,);
    for(i=;i<;i++)
    InsertLastList(&L, a[i]);
    InsertPosList(&L,,);
    InsertPosList(&L,,);
    printf("%d\n",GetElem(&L,));
    TraverseList(&L);
    printf("%d\n",FindList(&L,));
    UpdatePosList(&L,,);
    DeleteFirstList(&L);
    DeleteFirstList(&L);
    DeleteLastList(&L);
    DeleteLastList(&L);
    DeletePosList(&L, );
    DeletePosList(&L, );

    printf("%d\n",SizeList(&L));
    printf("%d\n",EmptyList(&L));
    TraverseList(&L);
/*
    ClearList(&L);
*/
}

2) 单链表

//单链表的C语言描述

#include <stdio.h>
#include <stdlib.h>

#define NN 12
#define MM 20

//链表结构体定义
typedef int ElemType;

struct sNode {
    ElemType data;         /*值域*/
    struct sNode* next;    /*链接指针域*/
};

//1、初始化线性表，即置单链表表头指针为空
void InitList(struct sNode** HL)
{
    *HL=NULL;
}

//2、清除线性表中所有元素，即释放单链表中所有结点，使之成为一个空表
void ClearList(struct sNode** HL)
{
    /*用cp和np分别作为指向两个相邻结点的指针*/
    struct sNode *cp, *np;
    /*单链表的表头指针赋给*cp*/
    cp=*HL;
    /*遍历单链表，依次释放每个结点*/
    while(cp!=NULL)
    {
        np=cp->next;
        free(cp);
        cp=np;
    }
    /*置单链表的表头指针为空*/
    *HL=NULL;
}

//3、返回线性表L的长度，即单链表的长度
int SizeList(struct sNode* HL)
{
    int i;     /*用来统计结点个数*/
    while(HL!=NULL)
    {
        i++;
        HL=HL->next;
    }
    return i;
}

//4、检查单链表是否为空
int EmptyList(struct sNode* HL)
{
    if(HL==NULL) return ;else return ;
}

//5. 返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行
ElemType GetElem(struct sNode* HL, int pos)
{
    int i=;  /*统计已遍历的结点数*/
    if(pos<)
    {
        printf("pos值非法，退出运行!\n");
        exit();
     }
    while(HL!=NULL)
    {
        i++;
        if(i==pos) break;
        HL=HL->next;
    }
    if(HL!=NULL)
        return HL->data;
    else
    {
        printf("pos值非法，退出运行!\n");
        exit();
    }
}

//6、遍历一个单链表
void TraverseList(struct sNode* HL)
{
    while(HL!=NULL)
    {
        printf("%5d",HL->data);
        HL=HL->next;
    }
    printf("\n");
}

//11. 向单链表中第pos个结点位置插入元素为x的结点，若插入成功返回1，否则返回
int InsertPosList(struct sNode** HL, int pos, ElemType x)
{
    int i=;
    struct sNode *newp;
    struct sNode* cp=*HL, *ap=NULL;
    /*对pos值小于等于0的情况进行处理*/
    if(pos<=)
    {
        printf("pos值不正确,返回0表示插入失败!\n");
        return ;
    }
    /*查找第pos个结点*/
    while(cp!=NULL)
    {
        i++;
        if(pos==i) break;
        else {ap=cp; cp=cp->next;}
    }
    /*产生新结点，若分配失败，则停止插入*/
    newp=malloc(sizeof(struct sNode));
    if(newp==NULL)
    {
        printf("内存动态空间用完，无法插入!\n");
        return ;
    }
    /*把x的值赋给新结点的data域*/
    newp->data=x;
    /*把新结点插入到表头*/
    if(ap==NULL)
    {
        newp->next=cp;  /*或改为newp->next=*HL*/
        *HL=newp;
    }
    /*把新结点插入到ap和cp之间*/
    else
    {
        newp->next=cp;
        ap->next=newp;
    }
    /*插入成功返回1*/
    return ;
}

//12. 向有序单链表中插入元素x结点，使得插入后仍然有序
void InsertOrderList(struct sNode** HL, ElemType x)
{
    /*把单链表的表头指针赋给cp，把空赋给ap*/
    struct sNode* cp=*HL, *ap=NULL;
    /*建立新结点*/
    struct sNode *newp;
    newp=malloc(sizeof(struct sNode));
    if(newp==NULL)
    {
        printf("内存动态空间用完，退出运行!\n");
        exit();
    }
    newp->data=x;    /*把x的值赋给新结点的data域*/
    /*把新结点插入到表头*/
    if(cp==NULL || x<cp->data)
    {
    newp->next=cp;
    *HL=newp;
    return;
    }
    /*顺序查找出x结点的插入位置*/
    while(cp!=NULL)
    {
        if(x<cp->data) break;
        else {ap=cp; cp=cp->next;}
    }
    /*把x结点插入到ap和cp之间*/
    newp->next=cp;
    ap->next=newp;
}

//16. 从单链表中删除值为x的第一个结点，若删除成功则返回1否则返回0
int DeleteValueList(struct sNode** HL, ElemType x)
{
    /*初始化cp和ap指针，使cp指向表头结点，使ap为空*/
    struct sNode* cp=*HL;
    struct sNode* ap=NULL;
    /*从单链表中查找值为x的结点，找到后由cp指向该结点，由
    ap指向其前驱结点*/
    while(cp!=NULL)
    {
        if(cp->data==x) break;
        ap=cp; cp=cp->next;
    }
    /*若查找失败，即单链表中不存在值为x的结点,则返回0*/
    if(cp==NULL) return ;
    /*对删除的是表头或非表头分别进行处理*/
    if(ap==NULL)
        *HL=(*HL)->next; /*或改为*HL=cp->next*/
    else
        ap->next=cp->next;
        /*回收被删除的结点*/
    free(cp);
    /*返回1表示删除成功*/
    return ;
}

void main()
{
    int a[NN];
    int i;
    struct sNode *p;//*h,*s,
    InitList(&p);
    for(i=;i<NN;i++) a[i]=rand()%MM;
    printf("随机数序列:");
    for(i=;i<NN;i++) printf("%5d",a[i]);
    printf("\n");
    printf("向链表中插入结点\n");
    InsertPosList(&p, , );
    InsertPosList(&p, , );
    InsertPosList(&p, , );

    TraverseList(p);
    printf("单链表长度：%5d\n",SizeList(p));
    ClearList(&p);

}

3)双向链表

 #include<string.h>
 #include<ctype.h>
 #include<malloc.h>
 #include<limits.h>
 #include<stdio.h>
 #include<stdint.h>
 #include<stdlib.h>
 #include<stdbool.h>
 #include<math.h> 

typedef struct DuLNode
{
    int data;
    struct DuLNode *prev,*next;
}DuLNode,*DuLinkList;

bool InitList(DuLinkList *L)
{
    *L=(DuLinkList)malloc(sizeof(DuLNode));
    if(*L)
    {
        (*L)->next=(*L)->prev=*L;
        return true;
    }
    else
    return false;
}

bool DestroyList(DuLinkList *L)
{
    DuLinkList q,p=(*L)->next;
    while(p!=*L)
    {
        q=p->next;
        free(p);
        p=q;
    }
    free(*L);
    *L=NULL;
    return true;
}

bool ClearList(DuLinkList L)
{
    DuLinkList q,p=L->next;
    while(p!=L)
    {
        q=p->next;
        free(p);
        p=q;
    }
    L->next=L->prev=L;
    return true;
}

bool ListEmpty(DuLinkList L)
{
    if(L->next==L&&L->prev==L)
        return true;
    else
        return false;
}

int ListLength(DuLinkList L)
{
    int i=;
    DuLinkList p=L->next;
    while(p!=L)
    {
        i++;
        p=p->next;
    }
    return i;
}

bool GetElem(DuLinkList L,int i,int *e)
{
    int j=;
    DuLinkList p=L->next;
    while(p!=L&&j<i)
    {
        p=p->next;
        j++;
    }
    if(p==L||j>i)
    return false;
    *e=p->data;
    return true;
}

int LocateElem(DuLinkList L,int e)
{
    int i=;
    DuLinkList p=L->next;
    while(p!=L)
    {
        i++;
        if(p->data==e)
        return i;
        p=p->next;
    }
    return ;
}

bool PriorElem(DuLinkList L,int cur_e,int *pre_e)
{
    DuLinkList p=L->next->next;
    while(p!=L)
    {
        if(p->data==cur_e)
        {
            *pre_e=p->prev->data;
            return true;
        }
        p=p->next;
    }
    return false;
}

bool NextElem(DuLinkList L,int cur_e,int *next_e)
{
    DuLinkList p=L->next->next;
    while(p!=L)
    {
        if(p->prev->data==cur_e)
        {
            *next_e=p->data;
            return true;
        }
        p=p->next;
    }
    return false;
}

DuLinkList GetElemP(DuLinkList L,int i)
{
    int j;
    DuLinkList p=L;
    for(j=;j<=i;j++)
        p=p->next;
    return p;
}

bool ListInsert(DuLinkList L,int i,int e)
{
    DuLinkList p,s;
    if(i<||i>ListLength(L)+)
        return false;
    p=GetElemP(L,i-);
    if(!p)
        return false;
    s=(DuLinkList)malloc(sizeof(DuLNode));
    if(!s)
        return false;
    s->data=e;
    s->prev=p;
    s->next=p->next;
    p->next->prev=s;
    p->next=s;
    return true;
}

bool ListDelete(DuLinkList L,int i,int *e)
{
    DuLinkList p;
    if(i<||i>ListLength(L))
        return false;
    p=GetElemP(L,i);
    if(!p)
        return false;
    *e=p->data;
    p->prev->next=p->next;
    p->next->prev=p->prev;
    free(p);
    return true;
}

void ListTraverse(DuLinkList L)
{
    DuLinkList p=L->next;
    while(p!=L)
    {
        printf("%d ",(p->data));
        p=p->next;
    }
    printf("\n");
}

void ListTraverseBack(DuLinkList L)
{
    DuLinkList p=L->prev;
    while(p!=L)
    {
        printf("%d ",(p->data));
        p=p->prev;
    }
    printf("\n");
}

 int main(void)
 {
   DuLinkList L;
   int i,n;
   bool j;
   int e;
   InitList(&L);
   for(i=;i<=;i++)
     ListInsert(L,i,i);
   printf("正序输出链表：");
   ListTraverse(L);
   printf("逆序输出链表：");
   ListTraverseBack(L);
   n=;
   ListDelete(L,n,&e);
   printf("删除第%d个结点，值为%d，其余结点为：",n,e);
   ListTraverse(L);
   printf("链表的元素个数为%d\n",ListLength(L));
   printf("链表是否空：%d(1:是 0:否)\n",ListEmpty(L));
   ClearList(L);
   printf("清空后，链表是否空：%d(1:是 0:否)\n",ListEmpty(L));
   for(i=;i<=;i++)
     ListInsert(L,i,i);
   ListTraverse(L);
   n=;
   j=GetElem(L,n,&e);
   if(j)
     printf("链表的第%d个元素值为%d\n",n,e);
   else
     printf("不存在第%d个元素\n",n);
   n=;
   i=LocateElem(L,n);
   if(i)
     printf("等于%d的元素是第%d个\n",n,i);
   else
     printf("没有等于%d的元素\n",n);
   j=PriorElem(L,n,&e);
   if(j)
     printf("%d的前驱是%d\n",n,e);
   else
     printf("不存在%d的前驱\n",n);
   j=NextElem(L,n,&e);
   if(j)
     printf("%d的后继是%d\n",n,e);
   else
     printf("不存在%d的后继\n",n);
   DestroyList(&L);
   return ;
 }

4) 队列

//队列的C语言描述

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

//队列的顺序存储结构同样可以被定义在一个记录类型中，假定该记录类型用QueueSq表示，则定义为：
/*
struct QueueSq {
    ElemType queue[MaxSize];
    int front, rear, len;
};
*/
//若要对存储队列的数组空间采用动态分配，则QueueSq结构类型可定义为：
struct QueueSq {
    ElemType *queue;       /*指向存储队列的数组空间*/
    int front, rear, len;  /*队首指针、队尾指针、队列长度变量*/
    int MaxSize;           /*queue数组长度*/
};

void againMalloc(struct QueueSq* Q)
{
/*空间扩展为原来的2倍，并由p所指向，原内容被自动
拷贝到p所指向的存储空间中*/
    ElemType *p;
    p=realloc(Q->queue, *Q->MaxSize*sizeof(ElemType));
    if(!p) {  /*分配失败退出运行*/
        printf("存储空间用完!\n");
        exit();
        }
    /*使queue指向新的队列空间*/
    Q->queue=p;
    /*把原队列的尾部内容向后移动MaxSize个位置*/
    if(Q->rear!=Q->MaxSize-) {
        int i;
        for(i=; i<=Q->rear; i++)
        Q->queue[i+Q->MaxSize]=Q->queue[i];
        Q->rear+=Q->MaxSize;  /*队尾指针后移MaxSize个位置*/
        }
    /*把队列空间大小修改为新的长度*/
    Q->MaxSize=*Q->MaxSize;
}

//1. 初始化队列
//第一种情况是隐含分配用于存储队列的固定大小的动态存储空间，假定动态存储空间的大小为10。
/*
void InitQueue(struct QueueSq* Q)
{
    //置队列空间初始最大长度为10
    Q->MaxSize=10;
    //动态存储空间分配
    Q->queue=malloc(10*sizeof(ElemType));
    //置队列为空
    Q->front=Q->rear=0;
}
*/

//第二种情况是分配由参数指定大小的动态存储空间。实用中使用任一种初始化算法均可。
void InitQueue(struct QueueSq* Q, int ms)
{
    /*检查ms是否有效，若无效则退出运行*/
    if(ms<=) {printf("ms值非法!\n"); exit();}
    /*置队列空间大小为ms*/
    Q->MaxSize=ms;
    /*动态存储空间分配，若分配失败则退出运行*/
    Q->queue=malloc(ms*sizeof(ElemType));
    if(!Q->queue) {
    printf("内存空间用完!\n");
       exit();
    }
    /*初始置队列为空*/
    Q->front=Q->rear=;
}

//2. 向队列插入元素
void EnQueue(struct QueueSq* Q, ElemType x)
{
    /*当队列满时进行动态重分配*/
    if((Q->rear+)%Q->MaxSize==Q->front) againMalloc(Q);
     /*求出队尾的下一个位置*/
    Q->rear=(Q->rear+)%Q->MaxSize;
    /*把item的值赋给新的队尾位置*/
    Q->queue[Q->rear]=x;
}//againMalloc()算法的具体定义如上：

//3. 从队列中删除元素并返回
ElemType OutQueue(struct QueueSq* Q)
{
    /*若队列为空则终止运行*/
    if(Q->front==Q->rear) {
    printf("队列已空，无法删除!\n");
    exit();
    }
    /*使队首指针指向下一个位置*/
    Q->front=(Q->front+)%Q->MaxSize;
    /*返回队首元素*/
    return Q->queue[Q->front];
}

//4.读取队列首元素，不改变队列状态
ElemType PeekQueue(struct QueueSq* Q)
{
    /*若队列为空则退出运行*/
    /*若队列为空则终止运行*/
    if(Q->front==Q->rear) {
    printf("队列已空，无法读取!\n");
    exit();
    }
    /*对首元素是队列指针的下一个位置中的元素*/
    return Q->queue[(Q->front+)%Q->MaxSize];
}

//5.检查一个队列是否为空，若是则返回1，否则返回0
int EmptyQueue(struct QueueSq* Q)
{
    if(Q->front==Q->rear) return ; else return ;
}

//6.清空一个队列，并释放动态存储空间
void ClearQueue(struct QueueSq* Q)
{
    if(Q->queue!=NULL){
        free(Q->queue);
        Q->queue=;
        Q->front=;
        Q->MaxSize=;
    }
}

void main()
{
    struct QueueSq q;
    int a[]={,,,,,,,};
    int i;
    InitQueue(&q, );
    for(i=;i<;i++) EnQueue(&q, a[i]);
    printf("%d",OutQueue(&q));printf("%d\n",OutQueue(&q));
    while(!EmptyQueue(&q)) printf("%d",OutQueue(&q));
    printf("\n");
    ClearQueue(&q);
}

5）队列的链接存储

//链队的C语言描述

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

//链表结构体定义
struct sNode {
    ElemType data;         /*值域*/
    struct sNode* next;    /*链接指针域*/
};

//链接队列结构体定义
struct QueueLk {
    struct sNode* front;  /*队首指针*/
    struct sNode* rear;   /*队尾指针*/
};

//1. 初始化链队
void InitQueue(struct QueueLk* HQ)
{
    HQ->front=HQ->rear=NULL;  /*把队首和队尾指针置为空*/
}

//2. 向链队中插入一个元素
void EnQueue(struct QueueLk* HQ, ElemType x)
{
    /*得到一个由newp指针所指向的新结点*/
    struct sNode* newp;
    newp=malloc(sizeof(struct sNode));
    if(newp==NULL) {
        printf("内存动态空间用完，退出运行!\n");
        exit();
        }
    /*把x的值赋给新结点的值域，把新结点的指针域置空*/
    newp->data=x;
    newp->next=NULL;
    /*若链队为空，则新结点既是队首结点又是队尾结点*/
    if(HQ->rear==NULL)
        HQ->front=HQ->rear=newp;
    /*若链队非空，则依次修改队尾结点的指针域和队尾指针，
    使之指向新的队尾结点*/
    else
        HQ->rear=HQ->rear->next=newp;
}

//3. 从队列中删除一个元素
ElemType OutQueue(struct QueueLk* HQ)
{
    struct sNode* p;
    ElemType temp;
    /*若链队为空则中止运行*/
    if(HQ->front==NULL) {
        printf("队列为空无法删除!\n");
        exit();
        }
    /*暂存队首元素以便返回*/
    temp=HQ->front->data;
    /*暂存队首指针以便回收队首结点*/
    p=HQ->front;
    /*使队首指针指向下一个结点*/
    HQ->front=p->next;
    /*若删除后链队变为空，则需同时使队尾指针变为空*/
    if(HQ->front==NULL) HQ->rear=NULL;
    /*回收原队首结点，返回被删除的队首元素*/
    free(p);
    return temp;
}

//4.读取队列首元素
ElemType PeekQueue(struct QueueLk* HQ)
{
    /*若链队为空则中止运行*/
    if(HQ->front==NULL) {
        printf("队列为空无法读取!\n");
        exit();
        }
    return HQ->front->data;
}

//5.检查队列是否为空
int EmptyQueue(struct QueueLk* HQ)
{
    /*判断对首或对尾任一个指针为空即可*/
    if(HQ->front==NULL) return ; else return ;
}

//6.清空一个队列，并释放动态存储空间
void ClearQueue(struct QueueLk* HQ)
{
    /*对首指针赋给p*/
    struct sNode* p=HQ->front;
    while(p!=NULL){
    HQ->front=HQ->front->next;
    free(p);
    p=HQ->front;
    }/*循环结束后对首指针已经变为空*/
    /*置对尾指针为空*/
    HQ->rear=NULL;
}

void main()
{
    struct QueueLk HQ;
    int a[]={,,,,,,,};
    int i,temp;
    InitQueue(&HQ);
    for(i=;i<;i++)
    EnQueue(&HQ, a[i]);
    printf("%d",OutQueue(&HQ));  printf("%d\n",OutQueue(&HQ));
    temp=PeekQueue(&HQ);  printf("%d\n",temp);
    while(!EmptyQueue(&HQ)) printf("%d",OutQueue(&HQ));
    printf("\n");
    ClearQueue(&HQ);
}

6) 顺序栈

/**********************************************************

以下是顺序栈的C语言实现
**********************************************************/

#include <stdlib.h>
  //初始长度为100
  #define StackSize 100
  typedef char DataType;
  typedef struct stack{
  DataType data[StackSize];
  int top;
  }SqStack;
  //初始化栈
  void InitStack(SqStack *S)
  {
  S->top = -;
  }
  //判断是否为空
  int StackEmpty(SqStack *S)
  {
  return S->top == -;
  }
  //判断是否满栈
  int StackFull(SqStack *S)
  {
  return S->top == StackSize-;
  }
  //入栈
  void push(SqStack *S,DataType d)
  {
  if (StackFull(S))
  {
   printf("Stack is full!");
   exit(-);
  }
  S->data[++S->top] = d;
  }
  //出栈
  DataType pop(SqStack *S)
  {
  if (StackEmpty(S))
  {
   printf("Stack is empty!\n");
   exit(-);
  }
  return(S->data[S->top--]);
  }
  //显示
  void disp(SqStack *S)
  {
  if (StackEmpty(S))
  {
   printf("Stack is empty!\n");
   exit(-);
  }
  int count = S->top;
  printf("The elements of stack are:\n");
  while(S->top != -)
  {
   printf("%c\n",S->data[S->top--]);
  }
  S->top = count;
  }
  int main()
  {
  SqStack *S;
  S = (SqStack *)malloc(sizeof(SqStack));
  printf("Initialize the stack.\n");
  InitStack(S);
  push(S,'a');
  push(S,'b');
  push(S,'c');
  push(S,'d');
  disp(S);
  printf("pop a element\n");
  DataType aa = pop(S);
  disp(S);
  DataType bb = pop(S);
  disp(S);
  DataType cc = pop(S);
  disp(S);
  DataType dd = pop(S);
  disp(S);
  DataType ee = pop(S);
  disp(S);
  return ;
  }

…