链表的元素插入

1.链表中间的元素s插入(与带头结点链表第一元素插入相同)

s->next = p->next;
p->next = s;

2.（不带头结点）链表第一元素插入

p->next = head->next;
head = p;

链表的元素删除

1.删除链表的第一个元素无头节点

head = head->next;
free(p);

2.删除链表中间的元素

q = p->next;
p->next = q->next;
free(q);

双链链表的插入

链表中插入s

q = p->next;
s->next = q;
q->prior = s;
p->next = s;
s->prior = p;

双链链表的删除

链表中删除s

s->prior->next = s->next;
s->next->prior = s->prior;
free(s);

顺序表的插入

原则：
可插入下标位置p的取值范围：0到length
当表长length等于数组长度maxsize时，不可以在插入元素
移动元素从后往前进行

int   sqlist[maxsize] = {1,2,...,n};
int  length = n;
//参数列表为数组相当于传入了地址
int insertElem(int sqlist[], int *length, int p, int e)
{
	if(p<0 || p>*length || *length==maxsize)
		return 0;
	for(int i = *length-1; i>=p; i--)
	{
		sqlist[i+1]=sqlist[i];
	}
	sqlist[p] = e;
	++(*length);
	return 1;
}

顺序表删除

原则：
可删除元素下标p的取值：0到length-1
当表长length为0时，不可再删除元素
移动元素从前往后

int deleteElem(int sqlist[], int *length, int p, int *e)
{
	if(p<0 || p>length-1)
		return 0;
		*e = sqlist[p]
	for(int i = p; i<*length-1; i++)
	{
		sqlist[i]=sqlist[i+1];
	}
	--(*length);
	return 1;
}

学习小记

1.带头结点的单链表，删除单链表的最后一个结点的时间复杂度为O(n)
删除最后一个结点，需要遍历链表，找到最后一个结点的前驱，将它的next设置为NULL
2.从一定的顺序表L中删除下标i-j的所有元素

int del(int arr[], int *length, int i, int j)
{
	int k, delta;
	delta = j-i+1;
	for(k=j+1; k < *length;++k)
	{
		arr[k-delta]=arr[k];
	}
	length -= delta; 
}

3.递增链表删除相同元素

void del(LNode *L)
{
	LNode *p = L->next,*p;
	while(p->next != NULL)
	{
		if(p->data == p->next->data)
		{
			q=p->next;
			p->next=q->next;
			free(q);
		}
		else
			p=p->next;
	} 
}

4.将一个链表的数据域中的奇数结点保留，偶数结点提取到另一个链表

void split(LNode *A, LNode *B)
{
	LNode *p,*q,*r;
	B = (LNode *)malloc(sizeof(LNode));
	B->next = NULL;
	r = B;
	p = A;
	while(p->next != NULL){
		if(p->next->data%2 == 0)
		{
			q = p->next;
			p->next = q->next;
			q->next = NULL:
			r->next = q;
			r=q;
		}
		else
			p = p->next;
		
	}
}