线性表的链式存储方式之链表

线性表的基本操作

初始化表。构造一个只包含头结点的链表

bool InitList(LinkList *L);

求表长，返回线性表L的长度，即L中数据元素的个数

int Length(LinkList L);

按值查找操作，在表L中查找具有给定关键字值的元素

int LocateElem(LinkList L,ElemType e);

按位查找操作，获取表L中第i个位置的元素

LNode* GetElem(LinkList L,int i);

插入操作,在表L中的第i个位置上插入指定元素e

bool ListInsert(LinkList *L,int i,ElemType e);

删除操作，在删除表L中第i个位置的元素，并用e返回删除元素的值

bool ListDelete(LinkList *L,int i,ElemType *e);

后插操作，在p结点之后插入元素e

bool InsertNextNode(LNode *p,ElemType e);

输出操作，按前后顺序输出线性表L的所有元素值

void PrintList(LinkList L);

判空操作，若L为空表，则返回true，否则返回false

bool Empty(LinkList L);

销魂操作，销毁线性表，并释放线性表L所占用的内存空间

void DestroyList(LinkList *L);

对于链表，又增加了包括逆转链表在内的几个额外操作

头插法建立长度为len的单链表

bool List_HeadInsert(LinkList *L,int len);

尾插法建立长度为len的单链表

bool List_TailInsert(LinkList *L,int len);

原地逆转链表

bool List_Reverse(LinkList *L);

逆转链表到一个新的链表中

LinkList List_ReverseToList(LinkList L);

有头结点链表的实现

//线性表的链式存储

//链表的实现(有头结点)
//by Ingran

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ElemType int
typedef struct LNode{
	ElemType data; 
	struct LNode *next;
}LNode,*LinkList;


// 初始化表。构造一个只包含头结点的链表 
bool InitList(LinkList *L);

// 求表长，返回线性表L的长度，即L中数据元素的个数
int Length(LinkList L);

// 按值查找操作，在表L中查找具有给定关键字值的元素
int LocateElem(LinkList L,ElemType e);

// 按位查找操作，获取表L中第i个位置的元素
LNode* GetElem(LinkList L,int i);

// 插入操作,在表L中的第i个位置上插入指定元素e
bool ListInsert(LinkList *L,int i,ElemType e);

// 删除操作，在删除表L中第i个位置的元素，并用e返回删除元素的值
bool ListDelete(LinkList *L,int i,ElemType *e);

//后插操作，在p结点之后插入元素e
bool InsertNextNode(LNode *p,ElemType e); 

// 输出操作，按前后顺序输出线性表L的所有元素值
void PrintList(LinkList L);

// 判空操作，若L为空表，则返回true，否则返回false
bool Empty(LinkList L);

// 销魂操作，销毁线性表，并释放线性表L所占用的内存空间
void DestroyList(LinkList *L); 

// 头插法建立长度为len的单链表
bool List_HeadInsert(LinkList *L,int len);

// 尾插法建立长度为len的单链表
bool List_TailInsert(LinkList *L,int len);

// 原地逆转链表
bool List_Reverse(LinkList *L); 

// 逆转链表到一个新的链表中
LinkList List_ReverseToList(LinkList L);


int main()
{
	LinkList pHead;
	InitList(&pHead);
	ListInsert(&pHead,1,11);
	ListInsert(&pHead,2,22);
	ListInsert(&pHead,3,33);
	ListInsert(&pHead,4,44);
	PrintList(pHead);
	
	ElemType e=0;
	ListDelete(&pHead,4,&e);
	PrintList(pHead);
	ListDelete(&pHead,4,&e);
	PrintList(pHead);
	
	int n = LocateElem(pHead,6);
	printf("%d\n",n);
	
	LinkList L;
	List_HeadInsert(&L,3);
	PrintList(L);
	
	LinkList L1;
	List_TailInsert(&L1,3);
	PrintList(L1);
	
	List_Reverse(&L1);
	PrintList(L1);
	
	LinkList L2;
	L2 = List_ReverseToList(L1);
	PrintList(L2);
	
	return 0;
} 

bool InitList(LinkList *L)
{
	*L = (LNode*)malloc(sizeof(LNode));
	if(L==NULL)
		return false;
	(*L)->data = -1;
	(*L)->next = NULL;
	return true;
}

int Length(LinkList L)
{
	int n=0;
	LNode *p = L->next;
	while(p!=NULL)
	{
		n++;
		p=p->next;
	}
	return n;	
}

bool ListInsert(LinkList *L,int i,ElemType e)
{
	if(i<1){
		return false;
	}
	int k=1;
	LNode *p=(*L);
	while(p!=NULL && k<i)
	{
		p=p->next;
		k++;
	}
	
	return InsertNextNode(p,e);
}

bool ListDelete(LinkList *L,int i,ElemType *e)
{
	if(i<1)
		return false;
	
	int k=1;
	LNode *p = (*L);
	//p为要删除结点的上一个结点 
	while(p!=NULL && k<i)
	{
		p=p->next;
		k++;
	}
	
	//i值不存在 
	if(p==NULL)
		return false;
	//要删除的结点为空 
	if(p->next==NULL)
		return false;
	LNode *q = p->next;
	*e = q->data;
	p->next = q->next;
	free(q);
	
	
	return true;
}

bool InsertNextNode(LNode *p,ElemType e)
{
	if(p==NULL)
		return false;
	LNode *s = (LNode*)malloc(sizeof(LNode));
	if(s==NULL)
		return false;
	s->data=e;
	s->next = p->next;
	p->next = s;
	
	return true;
}
 
int LocateElem(LinkList L,ElemType e)
{
	int n = 1;
	LNode *p = L->next;
	while(p!=NULL && p->data!=e)
	{
		p=p->next;
		n++;
	}
	if(p==NULL)
		return -1;
	return n;
}

LNode* GetElem(LinkList L,int i)
{
	if(i<0)
		return NULL;
	if(i==0)
		return L;
	
	//排除头结点 
	int j=1;
	LNode *p = L->next;
	while(p!=NULL && j!=i)
	{
		p = p->next;
		j++;
	}
	return p;
}

bool Empty(LinkList L)
{
	return (L->next==NULL);
}

void DestroyList(LinkList *L)
{
	LNode *p = (*L);
	while(p!=NULL)
	{
		LNode *q = p;
		p=p->next;
		free(q);
	}
}

void PrintList(LinkList L)
{
	//排除头结点 
	LNode *p = L->next;
	while(p!=NULL)
	{
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
}

bool List_HeadInsert(LinkList *L,int len)
{
	*L = (LNode *)malloc(sizeof(LNode));
	if(*L==NULL)
		return false;
	
	//头结点
	(*L)->data = 0;
	(*L)->next = NULL;
	
	LNode *p = *L;
	
	printf("头插法建立链表\n",len);
	printf("请输入%d个整数:\n",len);
	while(len--)
	{
		LNode *s = (LNode*)malloc(sizeof(LNode));
		if(s==NULL)
			return false;
		int k=0;
		scanf("%d",&k);
		s->data = k;
		s->next = p->next;
		p->next = s;
	}
	return true;
} 
 
bool List_TailInsert(LinkList *L,int len)
{
	*L = (LNode*)malloc(sizeof(LNode));
	if(*L==NULL)
		return false;
	
	//头结点
	(*L)->data = 0;
	(*L)->next = NULL;
	
	LNode *p = *L;
	
	printf("尾插法建立链表\n");
	printf("请输入长度为%d的整数:\n",len);
	while(len--)
	{
		LNode *s = (LNode*)malloc(sizeof(LNode));
		if(s==NULL)
			return false;
		int k=0;
		scanf("%d",&k);
		s->data = k;
		s->next = NULL;
		p->next = s;
		p=p->next;
	}
	
	return true;
}
 
 
bool List_Reverse(LinkList *L)
{
	//空链表直接返回 
	if(*L==NULL || (*L)->next == NULL)
	{
		printf("kong");
		return false;
	}
		
	//跳过头结点 
	LNode *p = (*L)->next;	
	
	//逆转过程中,P指针位置不变化 
	while(p->next!=NULL)
	{
		LNode *s = p->next;
		p->next = s->next;
		s->next = (*L)->next;
		(*L)->next = s;
	}
	
	return true;
}
 
LinkList List_ReverseToList(LinkList L)
{
	//空链表直接返回 
	if(L==NULL || L->next==NULL)
		return NULL;
	
	//创建头结点 
	LNode *newlist = (LNode*)malloc(sizeof(LNode));
	newlist->data=-1;
	newlist->next=NULL;
	
	//指向原始链表的指针(跳过头结点) 
	LNode *p = L->next;
	
	while(p!=NULL)
	{
		LNode *s = (LNode *)malloc(sizeof(LNode));
		if(s==NULL)
			return NULL; 
		s->data = p->data;
		s->next = newlist->next;
		
		newlist->next = s;		
		p=p->next;
	}
	
	return newlist;
}

无头结点链表的实现

//线性表的链式存储

//链表的实现(无头结点)
//by Ingran

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ElemType int
typedef struct LNode{
	ElemType data; 
	struct LNode *next;
}LNode,*LinkList;


// 初始化表。构造空链表 
bool InitList(LinkList *L);

// 求表长，返回链表的长度 
int Length(LinkList L);

// 按值查找操作，在表L中查找具有给定关键字值的元素
int LocateElem(LinkList L,ElemType e);

// 按位查找操作，获取表L中第i个位置的元素
LNode* GetElem(LinkList L,int i);

// 插入操作,在表L中的第i个位置上插入指定元素e
bool ListInsert(LinkList *L,int i,ElemType e);

// 删除操作，在删除表L中第i个位置的元素，并用e返回删除元素的值
bool ListDelete(LinkList *L,int i,ElemType *e);

//后插操作，在p结点之后插入元素e
bool InsertNextNode(LNode *p,ElemType e); 

// 输出操作，按前后顺序输出线性表L的所有元素值
void PrintList(LinkList L);

// 判空操作，若L为空表，则返回true，否则返回false
bool Empty(LinkList L);

// 销毁操作，销毁线性表，并释放线性表L所占用的内存空间
void DestroyList(LinkList *L); 
 
// 头插法建立长度为len的单链表
bool List_HeadInsert(LinkList *L,int len);

// 尾插法建立长度为len的单链表
bool List_TailInsert(LinkList *L,int len);

// 原地逆转链表
bool List_Reverse(LinkList *L); 

// 逆转链表到一个新的链表中
LinkList List_ReverseToList(LinkList L);


int main()
{
	LinkList pHead;
	InitList(&pHead);
	ListInsert(&pHead,1,4);
	ListInsert(&pHead,1,3);
	ListInsert(&pHead,1,2);
	PrintList(pHead);
	
	LNode *p = GetElem(pHead,3);
	printf("%d\n",p->data);
	
	
	
	ElemType e=0;
	ListDelete(&pHead,1,&e);
	PrintList(pHead);
	
	int n = Length(pHead); 
	printf("%d\n",n);
	
	DestroyList(&pHead);
	
	LinkList L;
	List_HeadInsert(&L,3);
	PrintList(L);
	
	LinkList L1;
	List_TailInsert(&L1,1);
	//PrintList(L1);
	
	List_Reverse(&L1);
	PrintList(L1);
	
	LinkList L2 = List_ReverseToList(L1);
	PrintList(L2);
	
	return 0;
} 

bool InitList(LinkList *L)
{
	*L = NULL;
	return true;
}

int Length(LinkList L)
{
	int n=0;
	LNode *p = L;
	while(p!=NULL)
	{
		p=p->next;
		n++;
	}
	return n;	
}

bool ListInsert(LinkList *L,int i,ElemType e)
{
	if(i<1){
		return false;
	}
	
	//插到头结点需要特殊处理 
	if(i==1)
	{
		LNode *s = (LNode*)malloc(sizeof(LNode));
		if(s==NULL)
			return false;
		s->data = e;
		s->next = (*L);
		(*L) = s;
		
		return true;
	}
	
	LNode *p=(*L);
	int k=1;
	while(p!=NULL && k<i-1)
	{
		p=p->next;
		k++;
	}
	
	return InsertNextNode(p,e);
}

bool ListDelete(LinkList *L,int i,ElemType *e)
{
	if(i<1)
		return false;
	if(i==1)
	{
		LNode *q = (*L);
		(*L) = (*L)->next;
		free(q);
		return true;
	} 
	
	int n=1;
	LNode *p=(*L);
	while(p!=NULL && n<i-1)
	{
		p=p->next;
		n++;
	}
	
	if(p==NULL)
	{
		return false;
	}
	
	LNode *q = p->next;
	p->next = q->next;
	free(q);
	
	
	return true;
}

bool InsertNextNode(LNode *p,ElemType e)
{
	if(p==NULL)
		return false;
	LNode *s = (LNode*)malloc(sizeof(LNode));
	if(s==NULL)
		return false;
	s->data=e;
	s->next = p->next;
	p->next = s;
	
	return true;
}
 
int LocateElem(LinkList L,ElemType e)
{
	int n = 1;
	LNode *p = L;
	while(p!=NULL && p->data!=e)
	{
		p=p->next;
		n++;
	}
	if(p==NULL)
		return -1;
	return n;
}

LNode* GetElem(LinkList L,int i)
{
	if(i<0)
		return NULL;
	if(i==0)
		return L;
	
	int j=0;
	LNode *p = L;
	while(p!=NULL && j<i-1)
	{
		p = p->next;
		j++;
	}
	//i的值不合法 
	if(p==NULL)
		return p;
		
	return p;
}

bool Empty(LinkList L)
{
	return (L==NULL);
}

void DestroyList(LinkList *L)
{
	LNode *p = (*L);
	while(p!=NULL)
	{
		LNode *q = p;
		p=p->next;
		free(q);
	}
}

void PrintList(LinkList L)
{ 
	LNode *p = L;
	while(p!=NULL)
	{
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
}

bool List_HeadInsert(LinkList *L,int len)
{
	*L = (LNode *)malloc(sizeof(LNode));
	if(*L==NULL)
		return false;
	
	
	printf("请输入%d个整数:\n",len); 
	int k=0;
	scanf("%d",&k);
	(*L)->data = k; //第一个节点的值 
	(*L)->next = NULL;
	
	while(--len)
	{
		scanf("%d",&k);
		LNode *s = (LNode*)malloc(sizeof(LNode));
		if(s==NULL)
			return false;
		s->data = k;
		s->next = *L;
		*L = s;	
	}
	
	
	return true; 
}


bool List_TailInsert(LinkList *L,int len)
{
	*L = (LNode *)malloc(sizeof(LNode));
	if(*L==NULL)
		return false;
	
	printf("请输入%d个整数:\n",len);
	int k=0;
	scanf("%d",&k);		//先给第一个结点赋值 
	(*L)->data = k;
	(*L)->next = NULL;
	
	LNode *p = *L;
	while(--len)
	{
		scanf("%d",&k);
		LNode *s = (LNode*)malloc(sizeof(LNode));
		if(s==NULL)
			return false;
		s->data = k;
		s->next = NULL;
		p->next = s;
		p=p->next;
		
	}
	
	return true;
}


bool List_Reverse(LinkList *L)
{	
	//无头结点
	LNode *p = *L;
	//空链表直接返回 
	if(p==NULL)
		return false;

	while(p->next!=NULL)
	{
		LNode *s = p->next;
		p->next = s->next;
		s->next = (*L);
		(*L) = s;
	}
	
	return true;
}

LinkList List_ReverseToList(LinkList L)
{
	
	if(L==NULL)
		return NULL;

	//先添加第一个节点 
	LinkList newlist=(LNode *)malloc(sizeof(LNode));
	newlist->data = L->data;
	newlist->next = NULL;
	//从第二个结点开始
	LinkList p = L->next;
	
	while(p!=NULL)
	{
		LNode *s = (LNode*)malloc(sizeof(LNode));
		if(s==NULL)
			return NULL;
			
		s->data = p->data;
		s->next = newlist;
		
		p=p->next;
		newlist = s;
	}
	
	return newlist;
}