数据结构【清华严蔚敏】——单链表的基本运算

    单链表的基本运算如下:
  (1)初始化单链表head
  (2)依次采用尾插法插入a,b,c,d,e元素
  (3)输出单链表head:a b c d e
  (4)单链表head长度:5
  (5)单链表head为非空
  (6)单链表head的第3个元素:c
  (7)元素a的位置:1
  (8)在第4个元素位置上插入f元素
  (9)输出单链表head:a b c f d e
  (10)删除head的第3个元素
  (11)输出单链表head:a b f d e
  (12)释放单链表head
 

#include <stdio.h>
#include <stdlib.h>
#define OK 1;

typedef char elemtype;
typedef int Status ;
typedef struct LNode {
	elemtype data;
	struct LNode *next;

} LNode,*LinkList;

//初始化链表
Status InitList(LinkList &L)
{
	L=(LinkList)malloc(sizeof(LNode));
	if(!L)  return -1;//分配空间失败
	L->next=NULL;
	return OK;
}

//算法2.9  插入
Status ListInsert_L(LinkList &L,int i,int e)
{
	LinkList p=L,q;
	int j=0;
	while(p&&j<i-1) { //找到插入位置在前一个指针
		p=p->next;
		j++;
	}
	if(!p||j>i-1) return -1;//i值不合法，if(!p||i<1)
	q=(LinkList)malloc(sizeof(LNode));
	q->data=e;
	q->next=p->next;
	p->next=q;
}

//algorithm2.10 删除
Status ListDelete_L(LinkList &L,int i)
{
	LinkList p=L,q;
	int j=0;
	while(p&&j<i-1) {
		p=p->next;
		j++;
	}
	if(!p->next||j>i-1)
		return -1;//i值不合法
	q=p->next;
	p->next=p->next->next;
	free(q);
}

Status DestroyList_L(LinkList&L)
{
	LinkList p=L;
	if(L) {
		p=L->next;
		free(L);
		L=p;
	}
	return OK;
}

Status ListEmpty(LinkList &L)
{
	if(L->next)
		return 1;
	else
		return 0;
}

Status Listprint(LinkList &L)
{
	LinkList p=L->next;
	while(p) {
		printf("%c ",p->data);
		p=p->next;
	}
}

int main()
{
	LinkList head;
	InitList(head);
	char A[5] = {'a','b','c','d','e'},temp='f';
	//temp用来存放插入的字符
	int	i;

	for(i=1; i<=5; i++)
		ListInsert_L(head,i,A[i-1]);

	if(!ListEmpty(head))
		printf("链表非空
");

	printf("开始时元素序列为：
");
	Listprint(head)	;

	i=4;
	ListInsert_L(head,i,temp);
	printf("
插入后的元素序列为：
");
	Listprint(head);

	i=3;
	ListDelete_L(head,i) ;
	printf("
删除后的元素序列为：
");
	Listprint(head);

	if(DestroyList_L(head))
		printf("
成功释放链表");

	getchar();

}