线性表(三)

 

线性表(一) 

 

线性表(二)

线性表的链式表示和实现

线性表的顺序存储可以随机存取表中任一元素，缺点是在做插入或删除操作时，需要移动大量的元素。

线性表的链式存储不要求逻辑上相邻的元素在物理位置上也相邻，在做插入或删除操作时，不需要移动元素，但也失去了随机存取的特点。

1 线性链表

用一组任意的存储单元存储线性表的数据元素。整个链表的存取必须从头指针开始，头指针指向链表的第一个结点（即第一个数据元素的存储映像）的存储位置，最后一个元素没有直接后继，则线性链表中最后一个结点的指针为NULL。

上图为带头结点的非空单链表

/*带有头指针的单链表*/
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0

typedef int elemType;

typedef struct LNode{
	elemType data;
	struct LNode *next;
}LNode,*linkNode;

typedef struct{
	linkNode head;
	int length;
} linkList;
/*创建结点，分配内存*/
void makeNode(linkNode *p,elemType e){
	*p = (linkNode)malloc(sizeof(LNode));
	if(!(*p)){
		printf("空间分配失败!");
		exit(0);
	}
	(*p)->data = e;
	return;
}
/*释放结点空间*/
void freeNode(linkNode *p){
	free(*p);
	*p = NULL;
}
/*取头结点*/
linkNode getHead(linkList *L){
	return L->head;
}
/*取当前结点p的后继结点*/
linkNode getNext(linkNode p){
	return p->next;
}
/*判断当前链表是否为空链表*/
int listEmpty(linkList *L){
	return getHead(L)->next == NULL ? 1: 0;
}
/*根据序号，获得对应的结点元素*/
linkNode getElem(linkList *L,int i){
	if(i<0||i>L->length+1){
		printf("查找的结点不存在!");
		exit(0);
	}else{
		int j = 1;
		linkNode e = getHead(L);
		while(j< i && e){
			e = e->next;
			j++;
		}
		return e;
	}
}
/*初始化链表*/
void initList(linkList *L){
	linkNode p = (linkNode)malloc(sizeof(LNode));
	if(p){
		p->next=NULL;
		L->length = 0;
		L->head = p;
		printf("空间分配成功!\n");	
	}else{
		printf("空间分配失败!\n");	
	}
}
/*清空链表*/
void clearList(linkList *L){
	linkNode p = getHead(L);
	linkNode q;
	while(p->next == NULL){
		q = p;
		p = p->next;	
		freeNode(&q);
	}
	p->next = NULL;
	L->length = 0;
	return;
}
/*销毁链表*/
void destroyList(linkList *L){
	clearList(L);
	freeNode(&L->head);
	return;
}
/*在指定位置插入元素*/
void listInsert(linkList *L,int i,elemType e){
	linkNode p = getElem(L,i);
	linkNode s;
	makeNode(&s,e);
	s->next = p->next;
	p->next = s;
	L->length++;
	return;
}
/*删除指定位置的元素*/
void listDelete(linkList *L,int i,elemType e){
	linkNode p = getElem(L,i);
	linkNode q = p->next;
	p->next = q->next;
	e = q->data;
	freeNode(&q);
	L->length--;
	return;
}
/*遍历链表*/
void listTraverse(linkList *L,void(*visit)(elemType)){
	linkNode p = L->head->next;
	int j;
	while(p != NULL){
		visit(p->data);
		p = p->next;
	}
	printf("\n");
	return;
}

void visit(elemType e){
	printf("%d ",e);
}

int compare(elemType a,elemType b){
	return a-b;
}
int main(){
	linkList LA;
	initList(&LA);
	int i=1;
	for(i;i<=5;i++){
		listInsert(&LA,i,i*3);
	}
	listTraverse(&LA,visit);
	elemType e;
	listDelete(&LA,2,e);
	listTraverse(&LA,visit);
	clearList(&LA);
	listTraverse(&LA,visit);
	return 0;	
}