/**********单链表存储结构**************/

#include <stdio.h>
#include <malloc.h>

typedef char ElemType;

typedef struct node
{
	ElemType data; //数据域
	struct node *next; //指针域
}Slink;


//初始化
void initList(Slink *&L){
	//L作为引用型参数
	L=(Slink *)malloc(sizeof(Slink)); //创建头结点L
	L->next=NULL;
}

//求长度
int getLength(Slink *L){
	int i=0;
	Slink *p=L->next;
	while(p!=NULL){
		i++;
		p=p->next;
	}
	return i;
}

//按位查找
int getElem(Slink *L,int i,ElemType &e){
	int j=1;
	Slink *p=L->next;
	if (i<1||i>getLength(L)) //参数不正确
		return 0;
	while(j<i){
		//从第1一个结点开始找,查找第i个结点
		p=p->next;
		j++;
	}
	e=p->data;
	return 1;
}

//按值查找
int locate(Slink *L,ElemType x){
	int i=1;
	Slink *p=L->next;
	while(p!NULL&&p->data!=x){
		p=p->next;
		i++;
	}
	if (p==NULL){
		return 0;
	}else{
		return i;
	}
}

//插入结点
int insElem(Slink *L,ElemType x,int i){
	int j=1;
	Slink *p=L,*s;
	s=(Slink *)malloc(sizeof(Slink)); 
	//创建data域为x的结点
	s->data=x;
	s->next=NULL;	
	if (i<1||i>getLength(L)+1) //无效位置
		return 0;
	while(j<i){
		//从头结点开始找,查找第i-1个结点,由p指向它
		p=p->next;
		j++;
	}
	s->next=p->next; //将*s的next域指向*p的下一个结点(即第i个结点)
	p->next=s; //将*p的next域指向*s的next域指向这样*s变成了第i个结点
	return 1;
}

//删除结点
int delElem(Slink *L,int i){
	int j=1;
	Slink *p=L,*q;
	if(i<1||i>getLength(L)) //无效位置
		return 0;
	while(j<i){
		//从头结点开始,查找第i个结点,由p指向它
		p=p->next;
		j++;
	}
	q=p->next; //由q指向第i个结点
	p->next=q->next; //将*p的next指向*q之后的结点,即从连表中删除第i个结点
	free(q); //释放第i个结点占用的空间
	return 1;
}

//输出单链表
void dispList(Slink *L){
	Slink *p=L->next;
	while(p!=NULL){
		printf("%c\n",p->data);
		p=p->next;
	}
}

//main
void main(int argc, char const *argv[])
{
	int i;
    ElemType e;
    SLink *L;
    InitList(L);        /*初始化单链表L*/
    InsElem(L,'a',1);    /*插入元素*/
    InsElem(L,'c',2);
    InsElem(L,'a',3);
    InsElem(L,'e',4);
    InsElem(L,'d',5);
    InsElem(L,'b',6);
    printf("线性表:");DispList(L);
    printf("长度:%d\n",GetLength(L));
    i=3;GetElem(L,i,e);
    printf("第%d个元素:%c\n",i,e);
    e='a';
    printf("元素%c是第%d个元素\n",e,Locate(L,e));
    i=4;printf("删除第%d个元素\n",i);
    DelElem(L,i);
    printf("线性表:");DispList(L);
}	

 

最后修改于 2019-11-12 18:51:24
如果觉得我的文章对你有用,请随意赞赏
扫一扫支付
上一篇