数据结构——链表例题1

1.在递增有序链表L中插入值为x的元素，使L依旧保持递增

void Insert(LinkList *L,DataType x){ 
	LinkList p=L,q=p->next,s;
	while(x>q->data&&q!=NULL){   //q可能为空，插入到表尾 
		p=p->next;
		q=p->next;
	}
	s=(LinkList*)malloc(sizeof(LinkList));
	s->data=x;
	s->next=p->next;
	p->next=s;
} 

 2.假设顺序表L中的元素从小到大排列，设计算法删除重复元素 

void del_list(SeqList *L){
	int i,j;
	for(i=0;i<L.length-1;i++){
		if(L->data[i]==L->data[i+1]){   //在i+1处找到相同的值 
			for(j=i+1;j<L.length-1;j++){     //将i+1后的元素全部前移一位 
				L->data[j]=L->data[j+1];
			}
			L->length--;    //顺序表长度减一 
		}
	}	
}

 3.设计算法将带头结点单链表L就地逆置

void Reserve(LinkList *L){
	LinkList p=L->next，q;
	L->next=NULL;          //将头结点断开 
	while(p!=NULL){     //头插法 
		q=p; 
		p=p->next;      //p移向下一个结点，防止断链 
		q->next=L->next;
		L->next=q;
	}
} 

4.链表L1，L2表示两个集合，设计算法判断L1是否为L2的子集，若是则返回1，不是返回0 

int IsSubset(LinkList *L1,LinkList *L2){  //以带头结点的链表为例 
	LinkList p=L1->next；
	LinkList q; 
	while(p!=NULL){
		q=L2->next;
		while(p->data!=q->data&&q!=NULL){   //在L2中查找与p所指结点值相同的结点 
			q=q->next;
		}
		if(q==NULL)		return 0;     //未找到 
		else                    //已找到，p指针后移 
			p=p->next;
	}
	reutrn 1;             //在L2中找到L1中的全部结点，L1是L2的子集 
}

5.递增有序链表A、B分别表示一个集合，设计算法实现C=A∩B

LinkList insert_Link(LinkList *A,LinkList *B){  // 以带头结点的链表为例 
	LinkList p=A->next;
	LinkList q=B->next;
	Linklist s; 
	LinkList C=(LinkList)malloc(sizeof(LNode));
	C->next==NULL;
	while(p!=NULL&&q!=NULL){
		if(q->data>p->data){     //q所指结点更大，让p向后移 
			p=p->next;
		}
		else if(q->data<p->data){    //p所指结点更大，让q向后移 
			q=q->next;
		}
		else{   //qp所指结点值相同，插入链表C 
			s=p;           //s=q也行 
			p=p->next;         //pq全部向后移 
			q=q->next;
			s->next=C->next;   //头插法 
			C->next=s; 
		}
	}
	return C; 
}