线性表的链式存储结构

1、定义：数据域（存数据元素信息）、指针域（存后继结点地址）、合在一起叫结点，每个结点只包含一个指针域所以叫单链表

头指针（第一个结点的存储位置，指向第一个结点的指针）、最后一个结点指针为空（NULL） 、头结点的数据域不存储任何信息/存放链表长度

链表为空也必须有头指针，可以没有头结点

2、结构指针表示单链表

typedef struct Node
{
	ElemType data; //数据域
	struct Node* Next; //指针域
}Node;
typedef struct Node* LinkList;

p是指向第i个元素的指针，p->data是ai数据域，p->next是指向ai+1的指针，p->next->data=ai+1

3、单链表的读取GetElem.c          O（n）

思路：声明一个结点p指向第一个结点，j++计数到i，p指针向后移动（从头开始找直到第i个元素

//用e返回L中第i个数据元素的值
Status GetElem(LinkList L, int i,ElemType* e)
{
	int j;
	LinkList p;

	p = L->next;//P指向第一个结点
    j=1;

	while(p&&jnext;//p指针向后移动
		++j;
	}
	
	if (!p||j>i) return ERROR;
	*e = p->data;

	return OK;
}

4、单链表的插入          O（n）

思路：先找到第i个元素位置，如果查找成功生成一个空结点，插入

插入语句：s->data=e; s->next = p->next; p->next = s;

//在L中第i个位置之前插入新的数据元素e，L长度加1
Status ListInsert(LinkList *L, int i,ElemType e)
{
	int j;
	LinkList p,s;

	p = *L;//P指向头结点
	j = 1;

	while(p&&jnext;
		j++;
	}
	
	if (!p||j>i) return ERROR;
	s = (LinkList)malloc(sizeof(Node));//为s分配一个空间
	s->data=e;
	s->next = p->next;
	p->next = s;

	return OK;
}

5、单链表的删除           O（n）

删除语句：q = p->next;  p->next = q->next;

//删除L中的第i个数据元素，并用e饭返回其值，L长度-1
Status ListDelet(LinkList *L, int i,ElemType *e)
{
	int j;
	LinkList p,q;

	p = *L;//P指向头结点
	j = 1;

	while(p&&jnext;
		++j;
	}
	
	if (!（p->next)||j>i) return ERROR;
	q = p->next;
	p->next = q->next;//或p->next=p->next->next

	*e = q->data;//记录删除的值
	free(q);//释放空间

	return OK;
}

6、头插法建立单链表

//头插法建立单链表
void createListHead(LinkList* L, int n)
{
	srand(time(0));//随机生成数字

	*L = (LinkList)malloc(sizeof(Node));
	(*L)->next = NULL;

	for (i = 0; i < n; i++)
	{
		p = (LinkList)malloc(sizeof(Node));//临时中介结点
		p->data = rand() % 100 + 1;//1-100的随机数
		p->next = (*L)->next;//把新生成的p放到头结点，p的next指向头
		(*L)->next = p;//让p这个新结点成为头结点
	}
}

rand()%100 是取余得到两位数，+1是0-100的数

7、尾插法建立单链表

//尾插法建立单链表
void createListTail(LinkList* L, int n)
{
	LinkList p, r;
	int i;

	srand(time(0));
	*L = (LinkList)malloc(sizeof(Node));
	r = *L;

	for (i = 0; i < n; i++)
	{
		p = (LinkList)malloc(sizeof(Node));
		p->data = rand() % 100 + 1;
		r->next = p;//r的next指向p
		r = p;//把p命名为r,p是临时结点，r存放尾结点
	}
	r->next = NULL;
}

8、单链表的整表删除

//清空链表
Status ClearList(LinkList *L)
{
	LinkList p, q;
	p = (*L)->next;//p指向第一个结点

	while (p)//链表不为空
	{
		q = p->next;//q指向下一个结点
		free(p);//把上一个结点释放
		p = q;//下一个结点仍命名为p，p继承下一个结点
	}
	(*L)->next = NULL;

	return OK;
}