整理--数据结构--线性表

                                  顺序表:

//查找运算

int  Locate(SeqList L, ElemType e)

{     int i=0;       // i为扫描计数器，初值为0，即从第一个元素开始比较

       while ((i<=L.last)&&(L.elem[i]!=e))

                    //顺序扫描表，直到找到值为key的元素, 或扫描到表尾而没找到

                    i++;

          if  (i<=L.last)

                    return(i+1);  //若找到值为e的元素，则返回其序号

          else

                    return(-1);  //若没找到，则返回空序号    }

//插入运算

/*在顺序表L中第i个数据元素之前插入一个元素e。 插入前表长n=L->last+1，

i的合法取值范围是 1≤i≤L->last+2  */

int  InsList(SeqList *L,int i,ElemType e)//插入运算

{         int k;

          if((i<1) || (i>L->last+2)) /*首先判断插入位置是否合法*/

          {         printf("插入位置i值不合法");

                    return(ERROR);      }

          if(L->last>= MAXSIZE-1)

          {        printf("表已满无法插入");

                    return(ERROR);      }

          for(k=L->last;k>=i-1;k--)   /*为插入元素而移动位置*/

                    L->elem[k+1]=L->elem[k];

          L->elem[i-1]=e;   /*在C语言数组中，第i个元素的下标为i-1*/

          L->last++;

          return(OK);         }

//删除运算

int  DelList(SeqList *L,int i,ElemType *e)

/*在顺序表L中删除第i个数据元素，并用指针参数e返回其值。i的合法取值为1≤i≤L.last+1 */   

{         int k;

          if((i<1)||(i>L->last+1))  

          {         printf("删除位置不合法!");

                    return(ERROR);      }

          *e = L->elem[i-1];  /* 将删除的元素存放到e所指向的变量中*/

          for(k=i; i<=L->last; k++)

                    L->elem[k-1] = L->elem[k];  /*将后面的元素依次前移*/

          L->last--;

          return(OK);         }

void      merge(SeqList *LA,  SeqList *LB,  SeqList *LC)

{         int i,j,k;

          i=0;j=0;k=0;

          while(i<=LA->last&&j<=LB->last)

                    if(LA->elem[i]<=LB->elem[j])

                    {         LC->elem[k]= LA->elem[i];

                               i++;

                               k++;}

                    else

                    {         LC->elem[k]=LB->elem[j];

                               j++;

                               k++;      }

          while(i<=LA->last)  /*当表LA有剩余元素时，则将表LA余下的元素赋给表LC*/

          {         LC->elem[k]= LA->elem[i];

                    i++;

                    k++;      }

          while(j<=LB->last)  /*当表LB有剩余元素时，则将表LB余下的元素赋给表LC*/        

          {         LC->elem[k]= LB->elem[j];

                    j++;

                    k++;      }

          LC->last=LA->last+LB->last+1;}

 

                                   单链表:

//对单链表进行初始化

void init_linklist(LinkList *l)

{         *l=(LinkList)malloc(sizeof(Node)); /*申请结点空间*/

          (*l)->next=NULL;                   /*置为空表*/    }

//头插法建立链表

void CreateFromHead(LinkList   L)

{         Node   *s;

          char      c;

          int       flag=1;

         while(flag)   /* flag初值为1，当输入"$"时，置flag为0，建表结束*/

          {         c=getchar();  

                    if(c!='$')

                    {         s=(Node*)malloc(sizeof(Node)); /*建立新结点s*/

                               s->data=c;

                               s->next=L->next;/*将s结点插入表头*/

                               L->next=s;                     }

                    else

                               flag=0;   }}

//尾插法建立链表

void CreateFromTail(LinkList L) {

          Node *r, *s;

          char c;

          int   flag =1; /*设置一个标志，初值为1，当输入"$"时，flag为0，建表结束*/

          r=L;           /*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/

          while(flag)         /*循环输入表中元素值，将建立新结点s插入表尾*/

          {         c=getchar();

                    if(c!='$')

                    {         s=(Node*)malloc(sizeof(Node));

                               s->data=c;

                               r->next=s;

                               r=s;      }

                    else

                    {flag=0;

                               r->next=NULL;   /*将最后一个结点的next链域置为空，表示链表的结束*/}   }   }

//单链表按序号查找

Node * Get (LinkList  L, int i)

/*在带头结点的单链表L中查找第i个结点，若找到(1≤i≤n)，则返回该结点的存储位置; 否则返回NULL*/

{         int j;

          Node  *p;

          p=L;

          j=0;   /*从头结点开始扫描*/

          while ((p->next!=NULL)&&(j<i))

          {         p=p->next;    /* 扫描下一结点*/

                    j++;   /* 已扫描结点计数器 */            }

          if(i == j)

                    return p;   /* 找到了第i个结点 */

          else

                    return NULL;   /* 找不到，i≤0或i>n */  }

//单链表按值查找

Node * Get (LinkList  L, int i)

/*在带头结点的单链表L中查找第i个结点，若找到(1≤i≤n)，则返回该结点的存储位置; 否则返回NULL*/

{         int j;

          Node  *p;

          p=L;

          j=0;   /*从头结点开始扫描*/

          while ((p->next!=NULL)&&(j<i))

          {         p=p->next;    /* 扫描下一结点*/

                    j++;   /* 已扫描结点计数器 */  }

          if(i == j)

                    return p;   /* 找到了第i个结点 */

          else

                    return NULL;   /* 找不到，i≤0或i>n */            }

//求表长

int       ListLength(LinkList L)

/*求带头结点的单链表L的长度*/

{         Node *p;

          int j;

          p=L->next;

          j=0;   /*用来存放单链表的长度*/

          while(p!=NULL)

          {         p=p->next;

                    j++;      }

          return j; /*j为求得的单链表长度*/       }

//单链表的插入运算

int InsList(LinkList L,int i,ElemType e)

/*在带头结点的单链表L中第i个位置插入值为e的新结点s*/

{         Node *pre,*s;

          int k;

          pre=L; 

          k=0;                     /*从"头"开始，查找第i-1个结点*/

          while(pre!=NULL&&k<i-1)  /*表未查完且未查到第i-1个时重复，找到pre指向第i-1个*/

          {         pre=pre->next;

                    k=k+1;    }                                                                                          /*查找第i-1结点*/

          if(!pre)      /*如当前位置pre为空表已找完还未数到第i个，说明插入位置不合理*/

          {         printf("插入位置不合理!");

                    return ERROR;       }

          s=(Node*)malloc(sizeof(Node));   /*申请一个新的结点S */

          s->data=e;                       /*值e置入s的数据域*/

          s->next=pre->next;                                 /*修改指针，完成插入操作*/

          pre->next=s;

          return OK;                     }

//单链表的删除运算

int DelList(LinkList L,int i,ElemType *e)

/*在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量*e中*/

{         Node *pre,*r;

          int k;

          pre=L;

          k=0;

          while(pre->next!=NULL && k<i-1)       /*寻找被删除结点i的前驱结点i-1使p指向它*/

          {         pre=pre->next;

                    k=k+1;    }                  

/*查找第i-1个结点*/

          if(!(pre->next))     /* 即while循环是因为p->next=NULL或i<1而跳出的,而是因为没有找到合法的前驱位置，说明删除位置i不合法。*/

          {         printf("删除结点的位置i不合理!");

                    return ERROR;       }

          r=pre->next;

          pre->next=pre->next->next;    /*修改指针，删除结点r*/

          *e = r->data;

          free(r);    /*释放被删除的结点所占的内存空间*/

          printf("成功删除结点!");

          return OK;          }

//单链表有序合并

LinkList MergeLinkList(LinkList LA, LinkList LB)

/*将递增有序的单链表LA和LB合并成一个递增有序的单链表LC*/

{         Node *pa,*pb;

          Node *r;

          LinkList LC;

/*将LC初始置空表。pa和pb分别指向两个单链表LA和LB中的第一个结点,r初值为LC*/

          pa=LA->next;

          pb=LB->next;

          LC=LA;

          LC->next=NULL;

          r=LC;

/*当两个表中均未处理完时，比较选择将较小值结点插入到新表LC中。*/

          while(pa!=NULL && pb!=NULL)

          {         if(pa->data <= pb->data)

                    {         r->next=pa;

                               r=pa;

                               pa=pa->next;        }

                    else

                    {         r->next=pb;

                               r=pb;

                               pb=pb->next;        }}

          if(pa) /*若表LA未完，将表LA中后续元素链到新表LC表尾*/

                    r->next=pa;

          else      /*否则将表LB中后续元素链到新表LC表尾*/

                    r->next=pb;

          free(LB);

          return(LC);         }

//循环链表合并算法1

LinkList   merge_1(LinkList LA,LinkList LB)

{  /*此算法将两个采用头指针的循环单链表的首尾连接起来*/

          Node *p, *q;

          p=LA;

          q=LB;

          while (p->next!=LA) p=p->next;          /*找到表LA的表尾，用p指向它*/

          while (q->next!=LB) q=q->next;          /*找到表LB的表尾，用q指向它*/

          q->next=LA;         /*修改表LB 的尾指针，使之指向表LA 的头结点*/

          p->next=LB->next; /*修改表LA的尾指针，使之指向表LB 中的第一个结点*/

          free(LB);

          return(LA);         }

//循环链表合并算法2

LinkList  merge_2(LinkList RA,LinkList RB)

{  /*此算法将两个采用尾指针的循环链表首尾连接起来*/

          Node *p;

          p=RA->next; /*保存链表RA的头结点地址*/

          RA->next=RB->next->next;/*链表RB的开始结点链到链表RA的终端结点之后*/

          free(RB->next);/*释放链表RB的头结点*/

          RB->next=p;/*链表RA的头结点链到链表RB的终端结点之后*/

    return  RB;/*返回新循环链表的尾指针*/          }

//双向链表单插入运算

int DlinkIns(DoubleList L,int i,ElemType e)

{         DNode  *s,*p;

          int k;

          p=L; 

          k=0;                     /*从"头"开始，查找第i-1个结点*/

          while(p->next!=L&&k<i)  /*表未查完且未查到第i-1个时重复，找到p指向第i个*/

          {         p=p->next;

                    k=k+1; }                                       /*查找第i-1结点*/

          if(p->next == L)      /*如当前位置p为空表已找完还未数到第i个，说明插入位置不合*/

          {         printf("插入位置不合理!");

                    return ERROR;                  }

          s=(DNode*)malloc(sizeof(DNode));

         if (s)

          {         s->data=e;

                    s->prior=p->prior;            

                    p->prior->next=s;  

                    s->next=p;                              

                    p->prior=s;                             

                    return OK;          }

          else

                    return ERROR;       }

//双向链表单删除运算

int       DlinkDel(DoubleList L,int i,ElemType *e)

{         DNode  *p;

          int k;

          p=L; 

          k=0;                     /*从"头"开始，查找第i个结点*/

          while(p->next!=L && k<i)  /*表未查完且未查到第i个时重复，找到p指向第i个*/

          {         p=p->next;

                    k=k+1;              }                                                                                

          if(p->next == L)      

          {         return ERROR;       }

          else

          {         *e=p->data;

                    p->prior->next=p->next;

                    p->next->prior=p->prior;

                    free(p);

                    return OK;}}