线性表

「爱情、让人受尽委屈。」 2022-06-16 01:08 254阅读 0赞

# **1.基本概念** #

n个数据元素的有限序列

# **2 抽象数据类型（ADT）** #

数据对象：\{a1,a2,.....,an\}，每个元素类型为DataType。

数据关系：除第一个元素外，每一个元素有且只有一个直接前驱元素；除最后一个元素外，每个元素有且只有一个直接后驱。一对一的对应关系。

基本操作：

InitList(\*L): 初始化操作，建立一个空列表L。

ListEmpty(L): 若列表为空，返回True，否则返回False。

ClearList(\*L): 将线性表清空。

GetElem(L,i,\*e): 将线性表L中第i个位置的元素值返回给e。

LocateElme(L,e): 查找线性表L中与给定值e相等元素的位置，如果查找成功，返回序号，否则返回0。

ListInsert(\*L,i,e): 在线性表L第i个位置插入元素e，长度加1。

ListDelete(\*L,i,\*e): 删除线性表L第i元素，并将其值通过e返回，长度减1。

ListLength(L): 返回线性表L的元素个数。

# **3 线性表的顺序存储** #

用一段地址连续的存储单元依次存储线性表的数据元素

#define ERROR 0
    #define OK 1
    #define TRUE 1
    #define FALSE 0
    #include <stdlib.h>
    #include <stdio.h> 
    //线性表的顺序存储结构定义 
    #define LIST_INIT_SIZE 100    //线性表初始分配的存储空间容量，可以存储100个元素 
    #define INCREMENT 10          //当存储空间不足时，每次新增的存储空间容量 
    typedef int ElemType;         //元素的数据类型根据实际情况而定，这里假设为int 
    typedef struct
    {
    	ElemType *elem;          //线性表的基地址 
    	int length;              //线性表中元素的个数 
    	int listsize;            //线性表中存储空间容量 
    }SqList;
    
    //线性表的顺序存储操作
    
    int InitList(SqList*L)   //建立空表 
    {
    	L->elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    	if (!(L->elem)) return ERROR;
    	L->length=0;
    	L->listsize=LIST_INIT_SIZE;
    	return OK;
    }
    
    int ListEmpty(SqList L)   //表是否为空 
    {
    	if (L.length) return FALSE;
    	else return TRUE;
    }
    
    int ClearList(SqList*L)   //清空 
    {
    	if (L->length) 
    	{
    		L->length=0;
    	}
    	return OK;
    }
    
    int GetElem(SqList L,int i,ElemType*e)  //获取第i个元素的值 
    {
    	if (L.length==0||(i<1)||(i>L.length)) return ERROR;
    	*e=*(L.elem+i-1);
    	return OK;
    }
    
    int LocateElme(SqList L,ElemType e)   //查找与e值相等元素在表中的位置 
    {
    	int i;
    	if (L.length==0) return FALSE;
    	for (i=0;i<L.length;i++)
    	{
    		if (e==*(L.elem+i))
    		{
    			return i+1;
    		}
    	}
    	return FALSE;
    }
    
    int ListInsert(SqList*L,int i,ElemType e)   //将e插入表中第i个元素 
    {
    	int j;
    	if (i<1||i>(L->length+1)) return ERROR;
    	if (L->length>=L->listsize)
    	{
    		L->elem=(ElemType*)realloc(L->elem,(L->listsize+INCREMENT)*sizeof(ElemType));
    		if (!L->elem) return ERROR;
    		L->listsize+=INCREMENT;
    	}
    	for (j=L->length;j>=i;j--)
    	{
    		*(L->elem+j)=*(L->elem+j-1);
    	}
    	*(L->elem+j)=e;
    	L->length++;
    	return OK;
    }
    
    int ListDelete(SqList*L,int i,ElemType*e)  //删除第i个元素，并将值返回给e 
    {
    	if (i<1||i>(L->length)||L->length==0) return ERROR;
    	*e=*(L->elem+i-1);
    	for (i--;i<L->length-1;i++)
    	{
    		*(L->elem+i)=*(L->elem+i+1);
    	}
    	L->length--;
    	return OK;
    	 
    }
    
    int ListLength(SqList L)   //获取表的长度 
    {
    	return L.length;
    }
    
    int main()
    {
    	SqList L;
    	int e,choice,i; 
    	do{
    		e=0;
    		printf("输入操作: 0.退出 1.返回表长度 2.插入 3.删除 4.获取元素值 5.验证表是否为空 6.清空表 7.创建表 8.查找元素位置\n");
    		scanf("%d",&choice);
    		switch (choice)
    		{
    			case 1:
    			{
    				e=ListLength(L);
    				printf("%d\n",e);
    				break;
    			}
    			case 2:
    			{
    				printf("输入插入元素值\n");
    				scanf("%d",&e);
    				printf("输入插入位置\n");
    				scanf("%d",&i); 
    				ListInsert(&L,i,e);
    				break;
    			}
    			case 3:
    			{
    				printf("输入删除位置\n");
    				scanf("%d",&i); 
    				ListDelete(&L,i,&e);
    				printf("%d\n",e);
    				break;
    			}
    			case 4:
    			{
    				printf("输入元素位置\n");
    				scanf("%d",&i); 
    				GetElem(L,i,&e);
    				printf("%d\n",e);
    				break;
    			}
    			case 5:
    			{
    				printf("%d\n",ListEmpty(L));
    				break;
    			}
    			case 6:
    			{
    				ClearList(&L);
    				break;
    			}
    			case 7:
    			{
    				InitList(&L);
    				break;
    			}
    			case 8:
    			{
    				printf("输入查找元素值\n");
    				scanf("%d",&e);
    				printf("%d\n",LocateElme(L,e));
    				break;
    			}
    		}
    		printf("[");
    		for (i=0;i<L.length;i++) printf("%d ",*(L.elem+i));
    		printf("]\n");
    	}while(choice!=0); 
    	return 0;
    }

# **4 线性表的链式存储** #

用一组任意的存储单元来存储线性表中的数据元素，利用存储地址信息来指示下一个元素所在地址。

单链表：

#define ERROR 0
    #define OK 1
    #define TRUE 1
    #define FALSE 0
    #include <stdlib.h>
    #include <stdio.h> 
    //线性表的链式存储结构定义  
    typedef int ElemType;         //元素的数据类型根据实际情况而定，这里假设为int 
    typedef struct Node 
    {
    	ElemType data;            //数据域，用于存储结点数据 
    	struct Node *next;        //指针域，存储下一个结点的地址信息              
    }Node,*LinkList;
    
    //线性表的链式存储操作
    //	int InitList(LinkList *L,int n)  //建立单链表，其中L为链表头指针的地址，n为元素个数（头插法）                  
    //	{
    //		int i;
    //		Node*p;
    //		(*L)=(LinkList)malloc(sizeof(Node));  
    //		if (!(*L)) return ERROR;
    //		(*L)->next=NULL;           //建立一个带头结点的单链表
    //		for (i=0;i<n;i++)           
    //		{
    //			p=(Node*)malloc(sizeof(Node));
    //			scanf("%d",&p->data); 
    //			p->next=(*L)->next;    //将新节点的指针指向原来头结点的指针所指向的那个结点 
    //			(*L)->next=p;          //将头结点的指针指向新节点 
    //		} 
    //		return OK;
    //	}
    
    int InitList(LinkList *L,int n)  //建立单链表，其中L为链表头指针的地址，n为元素个数（尾插法）                  
    {
    	int i;
    	Node*p,*r;
    	(*L)=(LinkList)malloc(sizeof(Node));  
    	if (!(*L)) return ERROR;
    	(*L)->next=NULL;           //建立一个带头结点的单链表
    	r=(Node*)malloc(sizeof(Node));
    	(*L)->next=r;              //建立第一个元素结点，将头结点的指针指向它 
    	r->next=NULL;               
    	scanf("%d",&r->data);
    	for (i=1;i<n;i++)           
    	{
    		p=(Node*)malloc(sizeof(Node));
    		scanf("%d",&p->data); 
    		r->next=p;            //将最后一个结点的指针指向新结点 
    		r=p;                  //将新节点定义为最后一个结点 
    	} 
    	r->next=NULL;            //将最后一个结点的指针指向空 
    	return OK;
    }
    
    int GetElem(LinkList L,int i,ElemType *e)     //获取链表的第i个元素的值，并返回给e 
    {
    	int j=1;
    	Node*p; 
    	p=L->next;
    	while (p && j<i)            //寻找第i个元素的位置 
    	{
    		p=p->next;
    		j++;
    	}
    	if (!p || j>i) return ERROR;   //若i小于1或i大于表长，则返回错误 
    	*e=p->data;
    	return OK; 
    }
    
    int LocateElme(LinkList L,ElemType e)
    {
    	int i=1;
    	Node*p;
    	p=L->next;
    	while(p)           //遍历整个表 
    	{
    		if (e==p->data) return i;
    		i++;
    		p=p->next;
    	}
    	return FALSE;     //查找失败 
    }
    
    int ListInsert(LinkList L,int i,ElemType e)
    {
    	int j=1;
    	Node*p,*s;
    	p=L;
    	while(p && j<i)
    	{
    		p=p->next;
    		j++;
    	}
    	if (j>i||!p) return ERROR;
    	s=(Node*)malloc(sizeof(Node));       //申请新结点的空间 
    	s->data=e;                          //载入数据 
    	s->next=p->next;                   //使新节点的指针指向后一个结点 
    	p->next=s;                         //使前一个结点的指针指向新节点 
    }
    
    int ListDelete(LinkList L,int i, ElemType*e)
    {
    	int j=1;
    	Node*p,*q;
    	p=L;
    	while(p && j<i)
    	{
    		p=p->next;
    		j++;
    	}
    	if (!p || j>i) return ERROR;
    	q=p->next;              //定义当前结点 
    	*e=q->data;             //返回将要删除的当前结点数据 
    	p->next=q->next;        //使当前结点的前结点指针指向当前结点的后结点 
    	free(q);                //释放当前结点 
    	return OK;
    }
    
    int ClearList(LinkList*L)
    {
    	Node*p,*q;
    	p=(*L)->next;
    	while(p)
    	{
    		q=p->next;         //记录当前结点的后结点 
    		free(p);           //释放当前结点 
    		p=q;               //将记录的后结点定义为当前结点 
    	}
    	(*L)->next=NULL;
    	return OK;
    }
    
    int ListLength(LinkList L)
    {
    	int i=0;
    	Node*p;
    	p=L->next;
    	while(p)       //遍历整表 
    	{
    		p=p->next;       
    		i++;
    	}
    	return i;
    	
    }
    
    
    int main()
    {
    	LinkList L;
    	Node*p;
    	int e,choice,i; 
    	do{
    		e=0;
    		printf("输入操作: 0.退出 1.返回表长度 2.插入 3.删除 4.获取元素值 5.清空表 6.创建表 7.查找元素位置\n");
    		scanf("%d",&choice);
    		switch (choice)
    		{
    			case 1:
    			{
    				e=ListLength(L);
    				printf("%d\n",e);
    				break;
    			}
    			case 2:
    			{
    				printf("输入插入元素值\n");
    				scanf("%d",&e);
    				printf("输入插入位置\n");
    				scanf("%d",&i); 
    				ListInsert(L,i,e);
    				break;
    			}
    			case 3:
    			{
    				printf("输入删除位置\n");
    				scanf("%d",&i); 
    				ListDelete(L,i,&e);
    				printf("%d\n",e);
    				break;
    			}
    			case 4:
    			{
    				printf("输入元素位置\n");
    				scanf("%d",&i); 
    				GetElem(L,i,&e);
    				printf("%d\n",e);
    				break;
    			}
    			case 5:
    			{
    				ClearList(&L);
    				break;
    			}
    			case 6:
    			{
    				printf("输入初始元素个数\n");
    				scanf("%d",&i);
    				InitList(&L,i);
    				break;
    			}
    			case 7:
    			{
    				printf("输入查找元素值\n");
    				scanf("%d",&e);
    				printf("%d\n",LocateElme(L,e));
    				break;
    			}
    		}
    		printf("[");
    		p=L->next;
    		while (p)            
    		{
    			printf("%d ",p->data);
    			p=p->next;
    		}
    		printf("]\n");
    	}while(choice!=0); 
    	return 0;
    }

静态链表：用数组描述的链表，数组元素由两个数据域组成，data和cur。data用于存放数据元素，cur相当于单链表的next指针，叫做游标。

#define ERROR 0
    #define OK 1
    #define TRUE 1
    #define FALSE 0
    #include <stdlib.h>
    #include <stdio.h> 
    //静态链表结构定义
    #define MAXSIZE 1000  
    typedef int ElemType;         //元素的数据类型根据实际情况而定，这里假设为int 
    typedef struct
    {
    	ElemType data;            //数据域，用于存储结点数据 
    	int cur;                 //游标，存储下一个结点的下标信息              
    }Component,SLinkList[MAXSIZE];
    
    //线性表的链式存储操作
    int InitList(SLinkList L)       //初始化静态链表         
    {
    	int i;
    	for (i=0;i<MAXSIZE-1;i++)    //除第一和最后一个结点，每个结点的游标都为后结点的下标 ，第一个结点的游标为备用链表的第一个结点下标 
    	{
    		L[i].cur=i+1;
    	}
    	L[MAXSIZE-1].cur=0;         //最后一个结点的游标为指向第一个有元素的结点，相当于头结点,由于此时没有元素，用0表达空指针。 
    	return OK;
    }
    
    int GetElem(SLinkList L,int i,ElemType *e)   //获取第i个元素的值 
    {
    	int j,num=1;
    	j=L[MAXSIZE-1].cur;
    	while (j && num<i)                //查找第i个元素的下标 
    	{
    		j=L[j].cur;
    		num++;
    	}
    	if ((num>i)||!j) return ERROR;      //若i小于1或第i个位置元素不存在，返回错误 
    	*e=L[j].data;                      //返回值 
    	return OK;
    }
    
    int LocateElme(SLinkList L,ElemType e)   //查找与e相等元素的下标 
    {
    	int i,num=1;
    	i=L[MAXSIZE-1].cur;
    	while(i)
    	{
    		if (L[i].data==e)    //若下标i的元素值与e相等，则返回下标 
    		{
    			return num;
    		}else
    		{
    			i=L[i].cur;
    			num++;
    		}
    	}
    	return FALSE;          //查找失败 
    }
    
    int Malloc_SL(SLinkList L)       //向备用链表申请一个存储空间 
    {
    	int i=L[0].cur;
    	if (i) L[0].cur=L[i].cur;
    	return i; 
    }
    
    int free_SL(SLinkList L,int k)  //释放一个存储空间到备用链表 
    {
    	L[k].cur =L[0].cur;
    	L[0].cur =k;
    	return OK;
    }
    
    int ListInsert(SLinkList L,int i,ElemType e)    //插入一个值为e的元素到第i个位置之前 
    {
    	int j,num,s;
    	if (i<1||(i>ListLength(L)+1)) return ERROR;
    	j=MAXSIZE-1;
    	for (num=1;num<i;num++) 
    	{
    		j=L[j].cur;
    	}
    	s=Malloc_SL(L);
    	L[s].data=e;
    	L[s].cur=L[j].cur;            //使新结点的游标指向原来第i个结点 
    	L[j].cur=s;                  //使第i-1个结点的游标指向新节点 
    	return OK;
    }
    
    int ListDelete(SLinkList L,int i, ElemType*e)  //删除第i个元素，并将元素值返回给e 
    {
    	int j,num=1,k;
    	if (i<1||i>ListLength(L)) return ERROR;
    	j=MAXSIZE-1;
    	for (num=1;num<i;num++) 
    	{
    		j=L[j].cur;
    	}
    	k=L[j].cur;             
    	L[j].cur=L[k].cur;    //将第i-1个结点的游标指向第i+1个结点 
    	*e=L[k].data;         //将第i个结点值返回 
    	free_SL(L,k);         //释放第i个结点 
    	return OK;
    }
    
    int ClearList(SLinkList L)      //静态链表的清空操作和初始化操作相同 
    {
    	int i;
    	for (i=0;i<MAXSIZE-1;i++)     
    	{
    		L[i].cur=i+1;
    	}
    	L[MAXSIZE-1].cur=0;         
    	return OK;
    
    }
    
    int ListLength(SLinkList L)   //返回链表的长度 
    {
    	int num=0,j;
    	j=L[MAXSIZE-1].cur;
    	while(j)
    	{
    		j=L[j].cur;
    		num++;
    	}
    	return num;
    }
    
    int main()
    {
    	SLinkList L;
    	int e,choice,i; 
    	do{
    		e=0;
    		printf("输入操作: 0.退出 1.返回表长度 2.插入 3.删除 4.获取元素值 5.清空表 6.创建表 7.查找元素位置\n");
    		scanf("%d",&choice);
    		switch (choice)
    		{
    			case 1:
    			{
    				e=ListLength(L);
    				printf("%d\n",e);
    				break;
    			}
    			case 2:
    			{
    				printf("输入插入元素值\n");
    				scanf("%d",&e);
    				printf("输入插入位置\n");
    				scanf("%d",&i); 
    				ListInsert(L,i,e);
    				break;
    			}
    			case 3:
    			{
    				printf("输入删除位置\n");
    				scanf("%d",&i); 
    				ListDelete(L,i,&e);
    				printf("%d\n",e);
    				break;
    			}
    			case 4:
    			{
    				printf("输入元素位置\n");
    				scanf("%d",&i); 
    				GetElem(L,i,&e);
    				printf("%d\n",e);
    				break;
    			}
    			case 5:
    			{
    				ClearList(L);
    				break;
    			}
    			case 6:
    			{
    				InitList(L);
    				break;
    			}
    			case 7:
    			{
    				printf("输入查找元素值\n");
    				scanf("%d",&e);
    				printf("%d\n",LocateElme(L,e));
    				break;
    			}
    		}
    		i=L[MAXSIZE-1].cur;
    		printf("[");
    		while(L[i].data)
    		{
    			printf("%d ",L[i].data);
    			i=L[i].cur;
    		}
    		printf("]\n");
    	}while(choice!=0); 
    	return 0;
    }

循环链表：将单链表的终端结点的指针由空指针改为指向头结点，使整个单链表形成一个环。与单链表的区别在于算法中的循坏条件不是判断p->next是否为空，而是他们是否指向头结点。为了操作方便，有时候不用头指针，而用尾指针，这样可以快速的访问到第一个结点和最后一个结点。还可以方便的将两个循坏链表合并为一个循坏链表：

双向链表：在单链表的每个结点中，再设置一个指向其前驱结点的指针域。

#define ERROR 0
    #define OK 1
    #define TRUE 1
    #define FALSE 0
    #include <stdlib.h>
    #include <stdio.h> 
    //双向链表的存储结构定义  
    typedef int ElemType;         //元素的数据类型根据实际情况而定，这里假设为int 
    typedef struct Node 
    {
    	ElemType data;            //数据域，用于存储结点数据 
    	struct Node *prior;       //指针域，存储前一个结点的地址信息 
    	struct Node *next;        //指针域，存储后一个结点的地址信息              
    }Node,*DLinkList;
    
    //双向链表的查找元素GetElme、获取元素位置LocateElme、返回长度ListLength操作与单链表类似
    
    int ListInsert(DLinkList L,int i,ElemType e) //在第i个位置前插入元素e 
    {
    	Node*p,*s;
    	int j=1;
    	p=L->next;
    	while(p&&j<i)      //查找第i个位置 
    	{
    		p=p->next;
    		j++;
    	}
    	if (!p||j>i) return ERROR;
    	if (!(s=(Node*)malloc(sizeof(Node)))) return ERROR;
    	s->data=e;     
    	s->next=p;               //使新节点的后指针指向第i个结点 
    	s->prior=p->prior;       //使新节点的前指针指向第i-1个结点 
    	p->prior->next=s;        //使第i-1个结点的后指针指向新节点 
    	p->prior=s;              //使第i个结点的前指针指向新节点 
    	return OK;
    } 
    
    int ListDelete(DLinkList L,int i,ElemType *e)   //删除第i个元素，并将其值返回给 
    {
    	Node*p;
    	int j=1;
    	p=L->next;
    	while(p&&j<i)            //找到第i个元素结点的位置 
    	{
    		p=p->next;
    		j++;
    	}
    	if (!p||j>i) return ERROR;
    	*e=p->data;
    	p->prior->next=p->next;        //使当前结点的前一个结点的后指针指向当前结点的后一个结点 
    	p->next->prior=p->prior;       //使当前结点的后一个结点的前指针指向当前结点的前一个结点 
    	free(p);                       //释放当前结点 
    	return OK;
    }
    
    int InitList(DLinkList*L,int n)     //尾插法建立双向循坏链表 
    {
    	int i;
    	Node*p,*q;
    	if(!((*L)=(DLinkList)malloc(sizeof(Node)))) return ERROR;      //建立头结点 
    	(*L)->next=NULL;
    	(*L)->prior=NULL;
    	q=(Node*)malloc(sizeof(Node));         //第一个元素结点 
    	(*L)->next=q;                        //头结点后指针指向第一个元素结点 
    	q->prior=(*L);                      //第一个结点的前指针指向头结点 
    	q->next=NULL;                       //第一个结点的后指针指向空 
    	scanf("%d",&q->data);
    	for (i=1;i<n;i++)
    	{
    		p=(Node*)malloc(sizeof(Node));
    		scanf("%d",&p->data);
    		q->next=p;                      //前一个结点的后指针指向新节点 
    		p->prior=q;                     //新节点的前指针指向前一个结点 
    		q=p;                             
    	}
    	q->next=(*L);                      //使最后一个结点的后指针指向头结点，形成环 
    	(*L)->prior=q;                     //使头结点的前指针指向最后一个结点，形成环 
    	return OK;
    }
    
    int main()
    {
    	DLinkList L;
    	Node*p;
    	int e,choice,i; 
    	do{
    		e=0;
    		printf("输入操作: 0.退出 1.插入 2.删除 3.创建表\n");
    		scanf("%d",&choice);
    		switch (choice)
    		{
    			case 1:
    			{
    				printf("输入插入元素值\n");
    				scanf("%d",&e);
    				printf("输入插入位置\n");
    				scanf("%d",&i); 
    				ListInsert(L,i,e);
    				break;
    			}
    			case 2:
    			{
    				printf("输入删除位置\n");
    				scanf("%d",&i); 
    				ListDelete(L,i,&e);
    				printf("%d\n",e);
    				break;
    			}
    			case 3:
    			{
    				printf("输入初始元素个数\n");
    				scanf("%d",&i);
    				InitList(&L,i);
    				break;
    			}
    		}
    		printf("[");
    		p=L->next;
    		while (p!=L)   
    		{
    			printf("%d ",p->data);
    			p=p->next;
    		}
    		printf("]\n");
    	}while(choice!=0); 
    	return 0;
    }

# 5 总结    #

线性表有顺序存储和链式存储两种方式。顺序存储的优点在于存取元素快，时间复杂度为O(1)，但其缺点在于长度往往固定，对存储空间利用率不高，且插入和删除操作慢，时间复杂度为O(n)。链式存储的优点在于其可以动态分配存储空间，且插入和删除操作快，时间复杂度为O(1)，但其存取操作较慢，时间复杂度为O(n)。