数据结构——线性表之顺序存储

以你之姓@ 2022-06-16 22:17 372阅读 0赞

# 数据结构——线性表之顺序存储 #

## 1、线性表的顺序存储结构特点 ##

>  *  第i个元素和i+1个元素的存储位置满足：LOC(ai+1)=LOC(ai)+m (其中m是指每个元素所占的存储单元）即顺序存储将线性表的元素放在一组连续的存储单元中。在线性表中相邻的两个元素在物理存储单元中也相邻
>  *  第i个元素与第一个元素的存储位置满足：LOC(ai)=LOC(a1)+(i-1)\*m

> > > > ![20170410130523030][]

## 2、线性表的优缺点 ##

*  优点：（1）顺序存储反应了线性表中元素的逻辑关系（2）任何一个元素都可以随机存取
 *  缺点：（1）删除、插入元素时需要移动大量数据（2）扩容问题，在C++中数组中的元素存放在连续的单元中，所以通常使用数组实现顺序存储，但是数组的长度会限制程序。

## 3、实现代码 ##

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #include <string.h>
    
    /**线性表的顺序存储**/
    #define Max_Size 100	//定义线性表最大长度 顺序存储的缺陷之一
    typedef struct{
    	char name[10];
    	int age;
    }Data;
    typedef struct{
    	Data list[Max_Size];
    	int length;
    }SqlList;
    
    /**初始化**/
    void InitList(SqlList *L){
    	//创建空线性表，将长度置为0
    	L->length = 0;
    }
    /**判断是否为空**/
    int ListEmpty(SqlList L){
    	//为空返回1，否则返回0
    	if(L.length==0) return 1;
    	else return 0;
    }
    /**返回线性表长度**/
    int ListLength(SqlList L){
    	return L.length;
    }
    /**清空线性表**/
    void ClearList(SqlList *L){
    	L->length = 0;
    }
    /**获得第i个元素**/
    int GetElem(SqlList L,int i,Data *e){
    	//找到返回1否则返回0
    	//看是否有第i个元素
    	if(0<i<L.length){
    		//将第i个元素放在e中
    		Data d = L.list[i];
    		strcpy(e->name,d.name);
    		e->age = d.age;
    	}else{
    		return 0;
    	}
    	return 1;
    }
    /**查找元素e的位置**/
    int LocateElem(SqlList L,Data e){
    	//找到返回位置否则返回-1
    	int len = ListLength(L);
    	Data d;
    	for(int i = 0;i<len;i++){
    		d = L.list[i];
    		if(strcmp(d.name,e.name)&&d.age==e.age){
    			return i;
    		}
    	}
    	return -1;
    }
    /**插入新元素**/
    void InsertList(SqlList *L,int i,Data e){
    	//判断线性表是否已经存满
    	int len = ListLength(*L);
    		while(len>i){
    			L->list[len+1] = L->list[len];
    			len--;
    		}
    		L->list[i] = e;
    		L->length++;
    }
    /**删除第i个位置上的元素**/
    void DeleteList(SqlList *L,int i,Data *e){
    	//将删除的元素放在e中
    	int len = ListLength(*L);
    		strcpy(e->name,L->list[i].name);
    		e->age = L->list[i].age;
    		for(int j = i;j<len;j++){
    			L->list[j] = L->list[j+1];
    		}
    		L->length--;
    }
    /**打印线性表**/
    void PrintList(SqlList L){
    	int len = ListLength(L);
    	Data d;
    	printf("name\tage\n");
    	for(int i = 0;i<len;i++){
    		d = L.list[i];
    		printf("%s\t%d\n",d.name,d.age);
    	}
    }
    void main(){
    	int i=1,position;
    	char name[10];
    	SqlList L;
    	Data d;
    	int code;
    	int len;
    	int age;
    	while(i){
    		printf("1、创建线性表\t");
    		printf("2、添加新元素\t");
    		printf("3、打印线性表\n");
    		printf("4、删除元素 \t");
    		printf("5、查找元素 \t");
    		printf("6、清空线性表\n");
    		printf("7、定位元素\t");
    		printf("8、是否为空\n");
    		scanf("%d",&i);
    		switch (i){
    			case 1:
    				InitList(&L);
    				break;
    			case 2:
    				printf("Input the position to insert: ");
    				scanf("%d",&position);
    				if(position<0||position>ListLength(L)){
    					printf("Error!Wrong position to insert!\n");
    					break;
    				}else if(ListLength(L)>=Max_Size){
    					printf("Error!No space to insert new element!\n");
    					break;
    				}else{
    					printf("Input the name :");
    					scanf("%s",&name);
    					printf("Input the age :");
    					scanf("%d",&age);
    					strcpy(d.name,name);
    					d.age = age;
    					InsertList(&L,position,d);
    				}
    				break;
    			case 3:
    				PrintList(L);
    				break;
    			case 4:
    				printf("Input the position to delete: ");
    				scanf("%d",&position);
    				len = ListLength(L);
    				if(position<0||position>len){
    					printf("Error!Wrong position to delete!\n");
    				}else if(len==0){
    					printf("Error!The list has been empty!\n");
    				}else{
    					DeleteList(&L,position,&d);
    					printf("Delted (%s,%d)\n",d.name,d.age);
    				}
    				break;
    			case 5:
    				printf("Input the position to find: ");
    				scanf("%d",&position);
    				code = GetElem(L,position,&d);
    				if(code==1){
    					printf("Find the %d element (%s,%d)\n",position,d.name,d.age);
    				}else{
    					printf("Can't find it!\n");
    				}
    				break;
    			case 6:
    				ClearList(&L);
    				break;
    			case 7:
    				printf("Input the name :");
    				scanf("%s",&name);
    				printf("Input the age :");
    				scanf("%d",&age);
    				strcpy(d.name,name);
    				d.age = age;
    				code = LocateElem(L,d);
    				if(code==-1){
    					printf("Not Find!\n");
    				}else{
    					printf("It's position is %d\n",code);
    				}
    				break;
    			case 8:
    				code = ListEmpty(L);
    				if(code==1){
    					printf("It's empty!\n");
    				}else{
    					printf("It's not empty!\n");
    					PrintList(L);
    				}
    				break;
    		}
    	}
    	system(0);
    }

[20170410130523030]: /images/20220617/20eb765f141c4db4a3c5122f2387fe72.png