2022.1.23

线性表

1.零个或者多个数据元素的有限序列。

2.序列中每一个元素的关系都是一对一的。

3.当传递一个参数给函数的时候，这个参数会不会在函数内被改动决定了使用什么参数形式。

        3.1 如果需要被改动，则需要传递指向这个参数的指针，

        3.2 如果不用被改动，可以直接传递这个参数。

4.线性表有顺序存储结构（数组）和链式存储结构（链表）。

主要说链表

链表

1.链表与数组的区别：

数组查找数据方便，O(1),删除和添加数据复杂，O(n);

链表查找数据复杂，O(N),删除和添加数据简单，O(1);

2.链表必须要有头指针。

3.单向链表有一个数据域，一个指针域

struct node{
	int data;
	struct node *next;
}linklist; 

双向链表有一个数据域，两个指针域

struct node{
	int data;
	struct node *next;
	struct node *pre;
}linklist; 

4.链表的插入

int insert(linklist j,int i,int t)//i为要插入的位置，t为要插入的数
{
	int j;
	linklist p,t;
	p=j;
	j=1;
	while(p!=NULL&&jnext;
		j++;	
	} 
	if(p==NULL||j>i)//第i个元素不存在
	return 0;
	t=(linklist *)malloc(sizeof(struct node));
	t->data=e;
	t->next=p->next;//向后再前 
	p->next=t;
    return 1;
} 

头插法

void creat(linklist p)
{
	int n,i,m;
	scanf("%d",&n);
	linklist t;
	p=(linklist *)malloc(sizeof(struct node));//申请空间
	p->next=NULL;//建立一个带头结点的单链表
	for(i=0;idata=m;
		t->next=p->next;
		p->next=t;//插入到表头
	}
}

尾插法

void creat(linklist p)
{
	int n,i,m;
	scanf("%d",&n);
	linklist t,r;
	p=(linklist *)malloc(sizeof(struct node));
	r=p;//r指向整个链表 
	for(i=0;inext=t;
		r=t;//连接链表 
	}
	r->next=NULL;//链表结束，最后一个点的下一个点要为NULL 
}

5.链表的删除

int insert(linklist j,int i)//i为要插入的位置
{
	int j;
	linklist p,t;
	p=j;
	j=1;
	while(p->next!=NULL&&jnext;
		j++;	
	} 
	if(p->next==NULL||j>i)//第i个元素不存在
	return 0;
	t=p->next;
	p->next=t->next;
	free(t);
	return 1;
}