考研复习（1）-线性表

还有5个月考研，代码还是得敲。

环境：Ubuntu10.10 ide：code：：blocks

线性表的基本操作，还有合并，比较算法

#include <stdio.h>
#include <stdlib.h>
#define LIST_INIT_SIZE 100
#define LIST_INCREASE 10


typedef char ElemType;
typedef struct
{
ElemType *elem;
int length;//Current Length of list
int listsize;//DataLength
}list;
//在表l中第i个位置插入x
void cutin(list *l,int i,ElemType x);
void initList(list *l);
ElemType del(list *l,int i);
void union1(list *A,list B);
void union2(list A,list B,list *C);
int main()
{
list Q;
list T;
list R;
initList(&Q);
initList(&T);


cutin(&Q,1,'g');
cutin(&Q,1,'c');
cutin(&T,1,'z');
cutin(&T,1,'x');
cutin(&T,1,'f');
cutin(&T,1,'a');
display(Q);
display(T);


printf("Union2 in turns:\n");
union2(Q,T,&R);
display(R);
printf("Union1:\n");
union1(&Q,T);
display(Q);
printf("Delet one element: %5c\n",del(&Q,2));
printf("Compare two list: %5d\n",compare(Q,T));
return 0;
}


void initList(list *l)
{
l->elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!l->elem)
{
printf("Over flow~\n");
exit(0);
}
l->listsize=LIST_INIT_SIZE;
l->length=0;
}
//在表l中第i个位置插入x
void cutin(list *l,int i,ElemType x)
{
ElemType *newbase;
ElemType *p,*q;
if(i<1||i>l->length+1)
{
printf("Wrong 'i'\n");
}
if(l->length>=l->listsize)//如果储存已满，调用realloc分配新内存
{
newbase=(ElemType *)realloc(l->elem,(l->listsize+LIST_INCREASE)*sizeof(ElemType));


if(!newbase)
{
printf("Over flow~\n");
exit(0);
}
l->elem=newbase;
l->listsize+=LIST_INCREASE;
}
p=&(l->elem[i-1]);
for(q=&(l->elem[l->length-1]);q>=p;q--)//p之后的元素往后移
{
*(q+1)=*q;
}
*p=x;
l->length++;
}
//删除表中第i个元素，返回删除值


ElemType del(list *l,int i)
{
ElemType *p,*q,e;
if(i<1||i>l->length+1)
{
printf("Wrong 'i'\n");
}
e=l->elem[i-1];
p=&(l->elem[i-1]);
for(q=&(l->elem[l->length]);q>=p;q--)//p之后的元素往后移
{
*(q-1)=*q;
}
l->length--;
return (e);


}
//在表中查找与e相等的元素
int locate(list *l,ElemType e)
{
ElemType *p=l->elem;
int i;
for(i=1;i<l->length;i++)
{
if(l->elem[i]==e)
return i;
}
if(i=l->length)
return 0;
}
void display(list l)
{
int i;
printf("The Element in the list:\n");
for(i=0;i<l.length;i++)
printf("%c",l.elem[i]);
printf("\n");


}
//归并A=A并B，算法1
void union1(list *A,list B)
{
int i;
ElemType j;
for(i=0;i<B.length;i++)
{
j=B.elem[i];
if(!locate(A,j))
{
cutin(A,A->length+1,j);
}
}
}
//归并算法2
void union2(list A,list B,list *C)
//A B C均按值非递减排列
{
ElemType *pa,*pb,*pc,*pa_last,*pb_last;
pa=A.elem;
pb=B.elem;
C->length=C->listsize=A.length+B.length;


C->elem=(ElemType *)malloc(C->length*sizeof(ElemType));
if(!C->elem)
{
printf("Over flow~\n");
exit(0);
}


pa_last=&(A.elem[A.length-1]);
pb_last=&(B.elem[B.length-1]);
pc= C->elem;
while(pa<pa_last&&pb<pb_last)
{
if(*pa<=*pb)
*pc++=*pa++;
else
*pc++=*pb++;


}


//搞定剩余部分
while(pa<=pa_last)
{
*pc++=*pa++;
}
while(pb<=pb_last)
{
*pc++=*pb++;
}
}


int compare(list la,list lb)//Compare two list
{
int i=0;
while(i<la.length&&i<lb.length)
{
if(la.elem[i]==lb.elem[i]) i++;
else if(la.elem[i]<lb.elem[i]) return -1;
else return 1;
}
}