全部博文（26）
2011年（26）
分类： C/C++
2011-10-15 18:30:45
线性表分为：顺序表和链表。
查找算法：顺序查找和二分查找（效率都很低，但是可满足一般要求）。二分查找要求关键字有序。
下面给出线性表及相关算法。
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
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
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)
{/*略*/}
注意上面列出的只是算法的关键部分，并不完整，删减了一些无碍算法逻辑的内容。
