数据结构-线性表

线性表分为：顺序表和链表。

查找算法：顺序查找和二分查找（效率都很低，但是可满足一般要求）。二分查找要求关键字有序。

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

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)

{/*略*/}

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