数据结构-线性表

  线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

一、线性表

1、线性表定义

   ADT List
{
    数据对象：
    数据关系：
    基本操作：
   InitLIst(&L)  //构造空链表
   DestroyList(&L)  //销毁链表
   ClearList(&L)  //清空为空表
   ListEmpty(&L)  //判断空表
   LIstLenth(&L)  //返回数据元素个数
   GetElem(L, i, &e)  //返回第i个数据元素存入e
   LocateElem(L, e, compare())  //返回第一个满足函数的数据元素，若没有则返回0
   PriorElem(L, cur_e, &pre_e)  //返回cur_e的前驱
   NextElem(L, cur_e, &next_e)  //返回cur_e的后继
   ListInsert(&L, i, e)  //在位置i插入数据元素e
   ListDelete(&L, i, &e)  //删除第i个元素，并用e返回
   ListTraverse(L, visit())  //对L的每个元素调用visit()
}ADT List

2、顺序表示和实现

(1)、定义

   线性表的顺序表示：用一组连续的储存单元依次储存线性表的数据元素。

(2)、算法

//------动态分配顺序表的储存结构----------
#define INIT_ELEM 100
#define SIZE_ADD 10
typedef struct {
	Elemtype *elem;
	int length;
	int listsize;
}List;

//------构建一个空顺序表------------------
void InitList(List &L){
	L.p=(Elemtype*)malloc(listsize*sizeof(List));
	if(!L.p) exit(error);//储存空间分配失败
	L.length=0;
	L.listsize=INIT_ELEM;
}

//----在顺序表中第i个位置之前插入新的元素e-----
void ListInsert(List &L, int j,ElemType e){
	if(i < 1 || i > L.length + 1) return ERROR; 
	if(L.length＞= L.listsize){(
		newbase =(ElemType *)realloc(L.elem,
			(L.listsize + SIZE_ADD) * sizeof(ElemType));		//当前存储空间已满，增加分配

	if(!newbase) exit(error); // 存储分配失败
	L.elem = newbase; 
	L.listsize += SIZE_ADD;
	}// 增加存储容量
	q=&(L.elem[i-1]);
	for(p =&(L.elen[L.length-1]); p>= q;  p--)
		*(p+1)=*p;		// 插入位置及之后的元素右移
	*q=e;
	++L. length;
}

//-----------删除第i个元素--------------------
void ListDelete(List &L,int i;ElemType &e){
	if((i<1)||(i>L.length))return error;
	p=&(L.elem[i-1]);
	e=*p;
	q=L.elem+L.length-1;
	for(++p;p<=q;++q) *(p-1)=*p;
	--L.length;
}

3、链表

(1)、单链表

typedef struct LNode{
	ElemType date;
	struct LNode *next;
}LNode,*Linklist;

初始化

//non-leading nodes
bool InitLIst(LinkList &L){
	L=NULL;
	return true;
}

//leading nodes
bool InitList(LinkList &L){
	L=(LNode*)malloc(sizeof(LNode));  //head node has no date;
	if(L=NULL)return false;
	L->next=NULL;
	return true;
}

  按位插入(leading node)

bool ListInsert(LinkList &L,int i,ElemType e){
	if(i<1)return false;
	LNode *p;
	int j=0;
	p=L;
	while(p&&j<i-1){
		p=p->next;
		j++;
	}
	if(!p)return false;
	LNode *s=(LNode*)malloc(sizeof(LNode));
	s->date=e;
	s->next=p->next;
	p->next=s;
	return true;
}

  指定节点前插操作(不传入头节点)

bool InsertPriorNode(LNode *p,ElemType e){
	if(p==NULL)return false;
	LNode *s=(LNode*)malloc(sizeof(LNode));
	s->next=p->next;
	p->next=s;
	s->date=p->date;
	p->date=e;
	return true;
}

  删除指定节点

bool DeleteNode(LNode *p){
	LNode *q=p->next;
	p->date=p->next->dete;       //use q->date replace p->date-------dalete p
	p->next=q->next;
	free(q);
	return true;
}

  尾插法(leading node)

初始化单链表
设置length记录链表长度
while循环{
    每次读取一个元素e；
    List Insert（L，length+1，e）插到尾部；
    length++；
}

  头插法(leading node)

初始化单链表
while循环{
    每次读取一个数据元素e；
    InsertNextNode（L，e）；
}

(2)、双链表

typedef struct DNode{
ElemType data;
struct DNode *prior,*next;
}Dnode,*DLinklist;
//init list
bool InitDLinkList(DLinkList &L){
	L=(DNode*)malloc(sizeof(DNode));
	L->prior=NULL;   //The priority of the header node always points to null
	L-.next=NULL;
	return true;
}

(3)、循环链表

循环单链表

L->next=L;

//判空
bool Empty(LinkList L){
	if(l->next==L)return true;
	else return false;
}

循环双链表

bool InitDLinkList(DLinkList &L){
	L=(DNode*)malloc(sizeof(DNode));
	if(L==NULL)return false;
	L->next=L;
	L->prior=L;
}

(4)静态链表

typedef struct Node{
	ElemType data;
	int next;    //储存下个节点的下标，若为最后一个则设为-1；
}Node;

打赏