数据结构--线性链表代码基础知识加练习题

啰嗦两句，之前学过一遍了，当时觉得很soso，现在应为考研要拿出来复习一遍，发现一件恐怖的事情。。。。。居然忘得差不多了，呃呃呃。。。谁让脑子不是U盘呢，那就写点博客重头再来吧。

这篇是数据结构线性链表入门，下面的代码粘贴到.cpp文件里可以直接用，习题来自严蔚敏版数据结构习题集，main函数在最下边。

#include<stdio.h>
#include<stdlib.h>
//宏定义
#define OVERFLOW -2
#define OK 1
#define ERROR -1
typedef int ElemType;
typedef int Status;
typedef  struct  LNode
{
    ElemType data ;
    struct LNode *next ;
} LNode , * LinkList ;

//初始化线性表
Status init_link(LinkList  &L)
{
    L = new LNode();
    L->next = NULL;
    return OK;
}
//在第i个位置插入元素e 
Status insert_link(LinkList &L,int i,ElemType e)
{
     LNode *p,*q;
     int j=0;
     p = L;
     while(p&&j<i-1){
     	j++;
     	p = p->next;
     }
     if(!p||j>i-1) return ERROR;
     LinkList S = (LinkList )malloc(sizeof(LNode));
     S->next = p->next;
     p->next = S;
     S->data = e;
     return OK;
}
//打印链表
Status print_link(LinkList L){
	LinkList p;
	p = L;
	while(p->next){
		p = p->next;
		printf("%d ",p->data);
	}
	printf("\n");
	return OK;
} 
//得到链表的长度
int length_link(LinkList L){
	LinkList p;
	p = L;
	int len = 0;
	while(p->next){
		p = p->next;len++;
	}
	return len;
} 
//删除第i个位置的元素，并且返回该元素的值
Status delete_Link(LinkList &L,int i,ElemType &e){
	LinkList p,q;
	p = L;
	int j = 0;
	if(i<=length_link(L)){
		while(p&&j<i-1){
			p = p->next;
			j++;
		}
		q = p->next;
		p->next = q->next;
		e = q->data;
		free(q);
		return OK;
	}else{
		return ERROR;
	}
	
} 
/*
练习题一
2.15 已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。
试写一算法将这两个链表连接在一起，假设指针hc指向连接后的链表的头结点，
并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。 
*/ 
//练习题一---自测(思路：将长的链表的头结点连接到短的链表的最后边)
Status MergeList_L(LinkList ha,LinkList hb,LinkList &hc){
	LinkList pa,pb;
	pa = ha;
	pb = hb;
	while(pa->next&&pb->next){
		pa = pa->next;
		pb = pb->next;
	}
	if(!pa->next){//pa短 
		pa->next = hb->next;
		hc = ha;
	}
	if(!pb->next){//pb短 
		pb->next = ha->next;
		hc = hb;
	}
	return OK;
}

//练习题一--- 答案 (我觉得答案错了，应该不是尽可能最短吧--如果我错的话还请大神们指正)
void MergeList_LL(LinkList &ha,LinkList &hb,LinkList &hc)
{
	LinkList pa,pb;
	pa=ha;
	pb=hb;
	while(pa->next&&pb->next){
		pa=pa->next;
		pb=pb->next;
	}
	if(!pa->next){
		hc=hb;
		while(pb->next) pb=pb->next;
		pb->next=ha->next;
	}
	else{
		hc=ha;
		while(pa->next) pa=pa->next;
		pa->next=hb->next;
	}
}
/*
练习题二 
2.19 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，
删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），
同时释放被删结点空间，并分析你的算法的时间复杂度
（注意，mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。
*/ 
//练习题一--- 自测(eeee,我承认看到答案后觉得自己的代码有一丢丢复杂了，但很容易想【\尴尬】)
Status ListDelete_L(LinkList &L,int mink,int maxk){
	LinkList p,q;
	p = L->next;
	while(p){
		if(p->data<mink){
			q = p->next;
			free(p);
			p = q;
			L->next = p;
		}else if(p->data>=mink&&p->data<=maxk){
			q = p;
			p = p->next;
		}else if(p->data>maxk){
			q->next = p->next;
			free(p);
			p = q->next;
		}
	} 
	return OK;
} 

//练习题一--- 答案 
Status ListDelete_L(LinkList &L,ElemType mink,ElemType maxk)
{
	LinkList p,q,prev=NULL;
	if(mink>maxk)return ERROR;
	p=L;
	prev=p;
	p=p->next;
	while(p&&p->data<maxk){
		if(p->data<=mink){
			prev=p;
			p=p->next;
		}
		else{
			prev->next=p->next;
			q=p;
			p=p->next;
			free(q);
		}
	}
	return OK;
}
int main()
{
	/*测试基础代码是否可以运行*/ 
	LinkList L;
	ElemType e;
	init_link(L);
	int arr[] = {10,12,14,54,34};
	for(int i=0;i<5;i++){
		insert_link(L,i+1,arr[i]);
	}
	print_link(L);
	delete_Link(L,3,e);
	print_link(L);
	printf("e = %d ",e);
	//int a = length_link(L);
	//printf("\n%d ",a);
	//---------------------------万能分割线-----------------------------
	/*测试练习题一*/
	printf("\n--------------\n");
	LinkList ha,hb,hc;
	init_link(ha);
	init_link(hb);
 	int a[] = {1,2,3,4,5,6,7,8,9};
 	int b[] = {4,5,6,7,8};
 	for(int i=0;i<9;i++){
		insert_link(ha,i+1,a[i]);
	}
	for(int i=0;i<5;i++){
		insert_link(hb,i+1,b[i]);
	}
	MergeList_LL(ha,hb,hc);
	print_link(hc);
	//---------------------------万能分割线-----------------------------
	/*测试练习题二*/
	printf("\n--------------\n");
	LinkList haa;
	init_link(haa);
 	int aa[] = {1,2,3,4,5,6,7,8,9};
	for(int i=0;i<9;i++){
		insert_link(haa,i+1,aa[i]);
	}
	ListDelete_L(haa,3,8); 
	print_link(haa);
    return 0;
}

           

明天写一篇循环链表的，待更新。。。