数据结构学习笔记二 线性表的链式存储结构1

单链表中链表中结点的结构：分为数据域和指针域两个部分，指针域指示下一个结点的地址
首先设一个head指针指向开始结点，终端结点的指针域为NULL。由于单链表的头指针是唯一的，
所以可以用作链表的名字。

用到的几个函数：
①：void * malloc(unsigned int size);//在内存的动态存储区中分配一个长度为size的连续空间
②：void * calloc(unsigned n,unsigned size); //分配长度为n长度的空间
③：void free(void * p) // 释放p所指向的内存区

建立单链表的方法（将字符放入链表中）

一：头插法建表
在一个空表中，生成新的结点，将读入的数据放到新的结点数据域中，然后将新的结点插入到链表的表头位置
缺点：输入的顺序与链表的顺序相反

二：尾插入法建表
链表结构中有一个尾指针，并始终指向尾结点。操作方法是在空表中，将新的结点存放到头指针中，其余的结点放在其前驱结点的指针域中。
缺点：需要对头结点单独处理。

三。带头结点的尾插法（常规建表法）

开始的结点的位置存放在头结点的指针域中，无论链表是否为空，其头指针是指向头结点的非空指针。
一般在头结点的数据域中存放长度等信息

下面是示例代码

#include "stdlib.h"
#include "stdio.h"

typedef char DataType;

typedef struct node {
	DataType data;       //链表的数据域
	struct node *next;   //链表的指针域
} ListNode;

typedef ListNode *LinkList;


void Error(char * message) 
{
	fprintf(stderr,"Error:%s\n",message);
	exit(1);
}

// 头插法建表--生成链表节点的次序和输入相反
LinkList CreateListF(void) 
{
	char ch;
	LinkList head;		//头指针
    ListNode *s;		//工作指针
	head = NULL;		//链表开始为空
	ch = getchar();
	while(ch!='\n') {
		s=(LinkList)malloc(sizeof(ListNode));//生成新的节点
		s->data=ch;
		s->next=head; //将节点*s插到单链表head的头上
		head = s;     //重新定义头指针
		ch=getchar();
	}
	return head;
}

// 尾插法建表
LinkList CreateListR(void) 
{
	char ch;
	LinkList head;
	ListNode *s, *r;	//r为尾指针
	head=NULL; r=NULL;	// 链表初始值为空
	ch = getchar();
	while(ch!='\n') {
		s=(LinkList)malloc(sizeof(ListNode));	//生成新的节点
		s->data=ch;
		if(head==NULL) {
			head=s;		//开始的节点的位置存在head中
		}else{
			r->next=s;  // 其余的节点在其前驱节点的指针域中。
		}
		r=s;			//尾指针指向新的表尾
		ch = getchar();
	}

	if(r!=NULL) {
		r->next=NULL;     //将尾节点置为空
	}
	return head;
}

// 有头结点的单链表(通常用法)
LinkList CreateListR1(void) 
{
	char ch;
	LinkList head = (LinkList)malloc(sizeof(ListNode));//生成一个头结点
	ListNode *s,*r;
	r=head;					//尾结点初始值指向头结点
	while((ch=getchar())!='\n') {
		s=(LinkList)malloc(sizeof(ListNode));	//生成一个新结点
		if(s==NULL)
			printf("Error!");
		s->data=ch;		//新结点数据域赋值
		r->next=s;		//尾结点指针域((*r).next)指向新结点
		r=s;			//尾指针指向新结点
	}
	r->next=NULL;
	return head;
}
// 按序号查找
ListNode * GetNode(LinkList head,int i)
{
	int j;
	ListNode *p;
	p=head;j=0;
	while(p->next&&j<i) {
		p=p->next;
		j++;
	}
	if(i==j) {
		return p;
	}else {
		return NULL;
	}
}
// 按值查找
ListNode * LocateNode(LinkList head,DataType val) {
	ListNode *p=head->next;
	while(p&&p->data!=val) {
		p=p->next;
	}
	return p;
}
// 插入运算(将x插入到第i个结点上)
void InsertList(LinkList head,DataType x,int i) {
	ListNode *s;			// 工作指针
	ListNode *p;
	p=GetNode(head,i-1);	// 找到第i-1个结点
	if(p==NULL) {
		Error("position error");
	}
	s=(LinkList)malloc(sizeof(ListNode));	//生成一个新结点
	s->data =x;			// 将x赋值于新结点的数据域
	s->next = p->next;	// 新结点的指针域指向原来的指针域
	p->next = s;			// 原来的指针域指向新的结点
}

// 删除运算(删除第i个结点)
void DeleteList(LinkList head,int i) {
	ListNode *p,*r;
	p=GetNode(head,i-1);	// 找到第i-1个结点
	if(p==NULL||p->next==NULL) {
		Error("position error");
	}
	r=p->next;			// r指向要删除的结点
	p->next=r->next;	// 第i-1个结点的指针域指向要删除结点的后继结点
	free(r);			// 释放删除的结点
}

// 打印链表
void PrintAll(LinkList head) {
	ListNode *p;
	p=head;
	printf("链表元素一览：\n");
	while(p!=NULL) {
		printf("%c\n",p->data);
		p=p->next;
	}
}

main() {
	//ListNode *L1=CreateListF();
    //ListNode *L2 = CreateListR();

	ListNode *L3 = CreateListR1();
	ListNode *p;
	int i=2;
	//PrintAll(L1);
	//PrintAll(L2);
	PrintAll(L3);
	p=GetNode(L3,i);
	printf("第%d个元素为：%c\n",i,p->data);
	printf("添加一个结点后：");
	InsertList(L3,'P',3);
	PrintAll(L3);
	printf("删除后：");
	DeleteList(L3,3);
	PrintAll(L3);
}