//顺序存储下线性表的操作实现#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, 2*L->MaxSize*sizeof(ElemType));    //空间扩展为原来的2倍，并由p指针所指向，原内容被    //自动拷贝到p所指向的存储空间中    if(!p) {  //分配失败退出运行        printf("存储空间用完!\n");        exit(1);           }     L->list=p;               //使list指向新线性表空间     L->MaxSize=2*L->MaxSize; //把线性表空间大小修改为新的长度}/**********************************************************************************1. 初始化线性表L，即进行动态存储空间分配并置L为一个空表**********************************************************************************/void InitList(struct List *L,int ms){    /*检查ms是否有效，若无效则退出运行*/    if(ms<=0) {printf("ms值非法!\n"); exit(1);}    /*置线性表空间大小为ms*/    L->MaxSize=ms;      /*动态存储空间分配，若分配失败则退出运行*/    L->list=malloc(ms*sizeof(ElemType));    if(!L->list) {       printf("动态存储分配失败!\n");       exit(1); /*执行此函数则中止程序运行，此函数在stdlib.h中有定义*/          }    /*初始置线性表为空*/    L->size=0;  }/**********************************************************************************2. 清除线性表L中的所有元素，释放动态存储空间，使之成为一个空表**********************************************************************************/void ClearList(struct List *L){   if(L->list!=NULL) {      free(L->list);  /*释放存储空间*/      L->list=0;            L->size=L->MaxSize=0;        }}/**********************************************************************************3. 返回线性表L的长度，若L为空则返回0**********************************************************************************/int SizeList(struct List *L){    return L->size;}/**********************************************************************************4. 判断线性表L是否为空，若为空则返回1，否则返回0**********************************************************************************/int EmptyList(struct List *L){    if(L->size==0) return 1; else return 0;}/**********************************************************************************5. 返回线性表L中第pos个元素的值，若pos超出范围，则停止程序运行**********************************************************************************/ElemType GetElem(struct List *L,int pos){    if(pos<1||pos>L->size) { /*若pos越界则退出运行*/        printf("元素序号越界!\n");        exit(1);    }    return L->list[pos-1];  /*返回线性表中序号为pos值的元素值*/}/**********************************************************************************6. 顺序扫描（即遍历）输出线性表L中的每个元素**********************************************************************************/void TraverseList(struct List *L){    int i;    for(i=0;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=0;i<L->size;i++)         if(L->list[i]==x) return i;    return -1;}//当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<1 || pos>L->size+1)  /*若pos越界则修改失败*/          return 0;    L->list[pos-1]=x;    return 1;}/**********************************************************************************9.  向线性表L的表头插入元素x    **********************************************************************************/    void InsertFirstList(struct List *L, ElemType x){     int i;     if(L->size==L->MaxSize)       againMalloc(L);   /*调用此函数重新分配更大的存储空间*/        for(i=L->size-1; i>=0; i--)     L->list[i+1]=L->list[i];     L->list[0]=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<1 || pos>L->size+1)  /*若pos越界则插入失败*/                return 0;            if(L->size==L->MaxSize)  /*重新分配更大的存储空间*/                  againMalloc(L);            for(i=L->size-1; i>=pos-1; i--)                L->list[i+1]=L->list[i];            L->list[pos-1]=x;            L->size++;            return 1;        }/**********************************************************************************12. 向有序线性表L中插入元素x，使得插入后仍然有序 **********************************************************************************/        void InsertOrderList(struct List *L, ElemType x)        {            int i,j;          /*若数组空间用完则重新分配更大的存储空间*/              if(L->size==L->MaxSize)                  againMalloc(L);          /*顺序查找出x的插入位置*/                for(i=0; i<L->size; i++)                if(x<L->list[i]) break;          /*从表尾到下标i元素依次后移一个位置，把i位置空出*/              for(j=L->size-1; j>=i; j--)                L->list[j+1]=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==0)    {        printf("线性表为空，不能删除!\n");        exit(1);    }    temp=L->list[0];    for(i=0; i<L->size; i++)        L->list[i-1]=L->list[i];    L->size--;    return temp;}/**********************************************************************************14. 从线性表L中删除表尾元素并返回它，若删除失败则停止程序运行**********************************************************************************/ElemType DeleteLastList(struct List *L){    if(L->size==0)    {        printf("线性表为空，不能删除!\n");        exit(1);    }    L->size--;    return L->list[L->size];}/**********************************************************************************15. 从线性表L中删除第pos个元素并返回它，若删除失败则停止程序运行**********************************************************************************/        ElemType DeletePosList(struct List *L, int pos)        {            ElemType temp;            int i;            if(pos<1 || pos>L->size) { /*pos越界则删除失败*/                printf("pos值越界，不能删除!\n");                exit(1);            }            temp=L->list[pos-1];            for(i=pos; i<L->size; i++)                L->list[i-1]=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=0; i<L->size; i++)        if(L->list[i]==x) break;        /*若查找失败,表明不存在值为x的元素,应返回0*/        if(i==L->size) return 0;        /*删除值为x的元素L->list[i]*/        for(j=i+1; j<L->size; j++)        L->list[j-1]=L->list[j];            /*线性表长度减1*/        L->size--;        /*删除成功返回1*/        return 1;}void main()    {    int a[10]={2,4,6,8,10,12,14,16,18,20};    int i;    struct List  L;    InitList(&L,5);    for(i=0;i<10;i++)     InsertLastList(&L, a[i]);    InsertPosList(&L,11,48);    InsertPosList(&L,1,64);    printf("%d\n",GetElem(&L,4));    TraverseList(&L);    printf("%d\n",FindList(&L,10));    UpdatePosList(&L,3,20);    DeleteFirstList(&L);    DeleteFirstList(&L);    DeleteLastList(&L);    DeleteLastList(&L);    DeletePosList(&L, 5);    DeletePosList(&L, 7);    printf("%d\n",SizeList(&L));    printf("%d\n",EmptyList(&L));    TraverseList(&L);/*    ClearList(&L);*/}

//单链表的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 1;else return 0;}//5. 返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行ElemType GetElem(struct sNode* HL, int pos){    int i=0;  /*统计已遍历的结点数*/    if(pos<1)     {        printf("pos值非法，退出运行!\n");        exit(1);     }    while(HL!=NULL)     {        i++;        if(i==pos) break;        HL=HL->next;    }    if(HL!=NULL)         return HL->data;    else    {        printf("pos值非法，退出运行!\n");        exit(1);    }}//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=0;    struct sNode *newp;    struct sNode* cp=*HL, *ap=NULL;    /*对pos值小于等于0的情况进行处理*/    if(pos<=0)     {        printf("pos值不正确,返回0表示插入失败!\n");              return 0;    }    /*查找第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 0;    }    /*把x的值赋给新结点的data域*/    newp->data=http://www.mamicode.com/x;    /*把新结点插入到表头*/    if(ap==NULL)     {        newp->next=cp;  /*或改为newp->next=*HL*/        *HL=newp;    }    /*把新结点插入到ap和cp之间*/    else     {        newp->next=cp;        ap->next=newp;    }    /*插入成功返回1*/    return 1;}//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(1);    }    newp->data=http://www.mamicode.com/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否则返回0int 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=http://www.mamicode.com/=x) break;        ap=cp; cp=cp->next;    }    /*若查找失败，即单链表中不存在值为x的结点,则返回0*/    if(cp==NULL) return 0;     /*对删除的是表头或非表头分别进行处理*/    if(ap==NULL)         *HL=(*HL)->next; /*或改为*HL=cp->next*/    else         ap->next=cp->next;        /*回收被删除的结点*/    free(cp);                   /*返回1表示删除成功*/    return 1;}void main(){    int a[NN];    int i;    struct sNode *p;//*h,*s,    InitList(&p);    for(i=0;i<NN;i++) a[i]=rand()%MM;    printf("随机数序列:");    for(i=0;i<NN;i++) printf("%5d",a[i]);    printf("\n");    printf("随机数序列");    TraverseList(p);    printf("单链表长度：%5d\n",SizeList(p));    ClearList(&p);}

//队列的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, 2*Q->MaxSize*sizeof(ElemType));    if(!p) {  /*分配失败退出运行*/        printf("存储空间用完!\n");        exit(1);        }    /*使queue指向新的队列空间*/    Q->queue=p;    /*把原队列的尾部内容向后移动MaxSize个位置*/    if(Q->rear!=Q->MaxSize-1) {        int i;        for(i=0; i<=Q->rear; i++)        Q->queue[i+Q->MaxSize]=Q->queue[i];        Q->rear+=Q->MaxSize;  /*队尾指针后移MaxSize个位置*/        }    /*把队列空间大小修改为新的长度*/    Q->MaxSize=2*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<=0) {printf("ms值非法!\n"); exit(1);}    /*置队列空间大小为ms*/    Q->MaxSize=ms;    /*动态存储空间分配，若分配失败则退出运行*/    Q->queue=malloc(ms*sizeof(ElemType));    if(!Q->queue) {    printf("内存空间用完!\n");       exit(1);    }    /*初始置队列为空*/    Q->front=Q->rear=0;}//2. 向队列插入元素void EnQueue(struct QueueSq* Q, ElemType x){    /*当队列满时进行动态重分配*/    if((Q->rear+1)%Q->MaxSize==Q->front) againMalloc(Q);     /*求出队尾的下一个位置*/    Q->rear=(Q->rear+1)%Q->MaxSize;    /*把item的值赋给新的队尾位置*/    Q->queue[Q->rear]=x;}//againMalloc()算法的具体定义如上：//3. 从队列中删除元素并返回ElemType OutQueue(struct QueueSq* Q){    /*若队列为空则终止运行*/    if(Q->front==Q->rear) {    printf("队列已空，无法删除!\n");    exit(1);    }    /*使队首指针指向下一个位置*/    Q->front=(Q->front+1)%Q->MaxSize;    /*返回队首元素*/    return Q->queue[Q->front];}//4.读取队列首元素，不改变队列状态ElemType PeekQueue(struct QueueSq* Q){    /*若队列为空则退出运行*/    /*若队列为空则终止运行*/    if(Q->front==Q->rear) {    printf("队列已空，无法读取!\n");    exit(1);    }    /*对首元素是队列指针的下一个位置中的元素*/    return Q->queue[(Q->front+1)%Q->MaxSize];}//5.检查一个队列是否为空，若是则返回1，否则返回0int EmptyQueue(struct QueueSq* Q){    if(Q->front==Q->rear) return 1; else return 0;}//6.清空一个队列，并释放动态存储空间void ClearQueue(struct QueueSq* Q){    if(Q->queue!=NULL){        free(Q->queue);        Q->queue=0;        Q->front=0;        Q->MaxSize=0;    }}void main(){    struct QueueSq q;    int a[8]={3,8,5,17,9,30,15,22};    int i;    InitQueue(&q, 5);    for(i=0;i<8;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);}

//链队的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(1);        }    /*把x的值赋给新结点的值域，把新结点的指针域置空*/    newp->data=http://www.mamicode.com/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(1);        }    /*暂存队首元素以便返回*/    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(1);        }    return HQ->front->data;}//5.检查队列是否为空int EmptyQueue(struct QueueLk* HQ){    /*判断对首或对尾任一个指针为空即可*/    if(HQ->front==NULL) return 1; else return 0;}//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[8]={3,8,5,17,9,30,15,22};    int i,temp;    InitQueue(&HQ);    for(i=0;i<8;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);}

/**********************************************************以下是顺序栈的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 = -1;  }  //判断是否为空  int StackEmpty(SqStack *S)  {  return S->top == -1;  }  //判断是否满栈  int StackFull(SqStack *S)  {  return S->top == StackSize-1;  }  //入栈  void push(SqStack *S,DataType d)  {  if (StackFull(S))  {   printf("Stack is full!");   exit(-1);  }  S->data[++S->top] = d;  }  //出栈  DataType pop(SqStack *S)  {  if (StackEmpty(S))  {   printf("Stack is empty!\n");   exit(-1);  }  return(S->data[S->top--]);  }  //显示  void disp(SqStack *S)  {  if (StackEmpty(S))  {   printf("Stack is empty!\n");   exit(-1);  }  int count = S->top;  printf("The elements of stack are:\n");  while(S->top != -1)  {   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 1;  }