数据结构-线性表

时间:2022-05-05 09:53:33

线性表分为:顺序表链表

查找算法:顺序查找和二分查找(效率都很低,但是可满足一般要求)。二分查找要求关键字有序

下面给出线性表及相关算法。

 

1.顺序表

顺序表结构如下:

typedef struct{

       DataType data[MAXSIZE];

       int last;    //最后一个元素的位置,即该顺序表的实际长度-1

}SeqList;

各种操作如下:

//置空

void Initial(SeqList *L){

       L->last = -1;

}

 

//查找:顺序查找值=x的元素的位置

int LocateX(SeqList *L, DataType x)

{

       int i = 1;

       while ((x != L->data[i-1]) && (i <= L->last)){

              i++;

       }

       if (i <= L->last+1){

              return i; //i代表的位置是从1算起的

       }

       else{

              printf("此元素不在表中");

              exit(1);

       }

}

 

//二分查找值=x的元素的位置

int bLocateX(SeqList *L, DataType x)

{

       int low, mid ,high;

       low=0;

       high=L->last;

       while( low<=high )

       {

              mid=(low+high)/2;

              if( x==L->data[mid] )

                     return mid;  //查找成功

              if( x<L->data[mid] )

                     high=mid-1;

              else

                     low=mid+1;

       }

       printf("此元素不在表中");

       return -1; //查找失败

}

 

//在第i位插入元素,节点后移

void InsertX(SeqList *L, int i, DataType x)

{

       int j;

 

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

       {

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

              exit(1);

       }

 

         //情况1

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

       {

              printf("超出范围");

              exit(1);

       }

         //情况2

       else if (i == L->last+2)

       {

              L->data[i] = x;  //直接插入到队尾

              L->last++;

       }

         //情况3

       else

       {

              for (j = L->last+2; j >= i; j--)

              {

                     L->data[j] = L->data[j-1];     //腾出第i位

              }

              L->data[j] = x;

              L->last++;  //last增加1

       }

}

 

//删除第i个元素

void DeleteIst(SeqList *L, int i)

{/*与插入类似,要考虑3种特殊情况*/}

 

//表的遍历

void Traverse(SeqList *L)

{/*略*/}

 

2.(单)链表

单链表结构如下:

typedef struct node{

       DataType data;

       struct node *next;

}LinkList;

各种操作如下:

/*按序号查找,返回指针p*/

LinkList *GetIst(LinkList *head,int i)  //注意必须用*GetIst,有*,因为该函数有指针类型的返回值p;

{

       LinkList *p=head;

       int j=0;

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

              p=p->next;

              j++;

       }

       if(j==i)

              return p;

       else{

              printf("找不到该节点!");

              exit(1);

       }

}

 

/*顺序查找值=x元素的位置,注意:链表上不能用二分法,仅能顺序查找*/

int LocateX(LinkList *head,DataType x)  //LocateX前面加不加*都可以

{

       LinkList *p=head->next;

       int i=1;

       while(p!=NULL)

              if(p->data!=x){  //注意前面的while,控制范围

                     p=p->next;

                     i++;

              }

              else break;

       if(p==NULL) {  //即p已经指向了队尾

              printf("找不到该节点!");

              exit(1);

       }

       else return i;

}

 

/*在p后插入元素*/

void InsertAfter(LinkList *p,DataType x)

{

       LinkList *s;

       s=malloc(sizeof(LinkList));

       s->data=x;

      

       //修改p后继,注意:链表和树中经常用下面这段代码

       s->next=p->next;

       p->next=s;

}

 

/*在p前插入元素[交换法](推荐),另外还有[查找前驱法](不推荐)*/

void InsertBefore2(LinkList *p,DataType x)

{

       LinkList *s;

       s=malloc(sizeof(LinkList));

      

       //将p复制给s

       s->data=p->data;

       s->next=p->next;

      

       //给p赋新值,并修改其后继为s

       p->data=x;

       p->next=s;

}

 

/*在第i位插入元素x*/

void Insert(LinkList *head, DataType x, int i)

{

       LinkList *p;

       p=GetIst(head,i-1); //因为用后插法,所以要找i的前一位指针

       InsertAfter(p,x);

}

 

/*删除p的后一个元素*/

void DeleteAfter(LinkList *p)

{     //修改p的后继,使其后移一位,并释放原来的后继

       LinkList *r;

       r=p->next;

       p->next=r->next;

       free(r);

}

 

/*删除第i个元素*/

void Delete(LinkList *head, int i)

{

       LinkList *p;

       p=GetIst(head,i-1); //因为用后删法,所以要找i的前一位指针

       DeleteAfter(p);

}

 

/*头插法特点:无头结点,head指针始终指向最后插入的那个元素*/

LinkList *CreListTou()

{

       int x; LinkList *head,*s;

       head=NULL;

       scanf("%d",&x);

       while(x!=-1)    //输入-1代表结束

       {

              s=malloc(sizeof(LinkList));

              s->data=x;

 

              //修改head指向

              s->next=head;

              head=s;

              scanf("%d",&x);

       }

       return head;

}

 

/*尾插法特点:生成头结点,head固定指向头结点,r指向尾节点*/

LinkList *CreListWei()

{

       int x; LinkList *head,*s,*r;

       head=malloc(sizeof(LinkList));

       r=head;

       scanf("%d",&x);

       while(x!=-1)   //输入-1代表结束

       {

              s=malloc(sizeof(LinkList));

              s->data=x;

 

              //修改r指向

              r->next=s;

              r=s;

              scanf("%d",&x);

       }

       r->next=NULL;

       return head;

}

 

/*单链表的遍历*/

void Traverse(LinkList *head)

{/*略*/}

 

注意上面列出的只是算法的关键部分,并不完整,删减了一些无碍算法逻辑的内容。