数据结构（1）线性表之顺序表的表示和实现

怼烎@ 2021-11-05 08:42 370阅读 0赞

### 数据结构（1）线性表之顺序表的表示和实现 ###

*   *   *  前言
         *  线性表
         *  线性表的顺序表示
         *  实现的操作
         *  注
         *  全部代码
         *   *  工程图
             *  SeqList.h头文件存放顺序表有关数据的定义和操作函数的声明
             *  SeqList.cpp文件存放操作函数的实现
             *  Main.cpp文件用于做测试

### 前言 ###

这几天复习数据结构有关的东西，光看课本真是很枯燥了，于是找了些资料搭配来看。一个是程杰老师的《大话数据结构》，很有名的一本书（老师给我们上数据结构的时候就推荐过，不过当时没看），这几天看了的确很通俗易懂，比课本讲得生动些。另一个是在51CTO学院里找的鲍松山老师的视频课程，讲得也很不错，我有一些代码的实现跟课本上有区别，因为主要是跟着他的视频写的。  
附：课程地址[数据结构严蔚敏C语言版-手把手教你实现数据结构视频课程][C_-]

### 线性表 ###

*  概念：由n(n>=0)个数据特性相同的元素构成的有限序列，其中线性表中元素的个数n(n>=0)定义为线性表的长度，n=0时称线性表为空表
 *  特点:
    
    1.  存在唯一的一个被称作“第一个”的数据元素
    2.  存在唯一的一个被称作“最后一个”的数据元素
    3.  除第一个外，结构中的每个数据元素均只有一个前驱
    4.  除最后一个外，结构中的每个数据元素均只有一个后继

### 线性表的顺序表示 ###

*  概念：用一组地址连续的存储单元依次存储线性表的数据元素（也称为线性表的顺序存储结构或顺序映像）
 *  特点：逻辑上相邻的数据元素，其物理次序也是相邻的

### 实现的操作 ###

*  初始化顺序表
 *  为顺序表增配空间
 *  展示顺序表
 *  从尾部插入
 *  从头部插入
 *  按位置插入
 *  从尾部删除
 *  从头部删除
 *  按位置删除
 *  按值删除
 *  按值查找数据
 *  排序
 *  倒换表的顺序
 *  提供顺序表的长度
 *  清除所有数据
 *  摧毁

### 注 ###

概念都是课本上的，代码都是自己敲的，因为写的时候注释写得比较详细，加上这部分内容算比较简单，就没有额外分析什么。所有代码均在vc++6.0环境下编译通过并可成功运行。  
附:运行时截图  
![截图1][1]  
![j截图2][j_2]

### 全部代码 ###

#### 工程图 ####

![工程图][2019080821530278.png]

#### SeqList.h头文件存放顺序表有关数据的定义和操作函数的声明 ####

#ifndef __SEQLIST_H__
    #define __SEQLIST_H__
    
    #include<stdio.h>
    #include<malloc.h>
    #include<assert.h>
    
    //初始化时定义的顺序表大小
    #define SEQLIST_INIT_SIZE 8
    //新增配的顺序表空间的大小
    #define INC_SIZE 3
    
    //顺序表内的数据类型
    typedef int ElemType;
    
    typedef struct SeqList{ 
       //指向顺序表的真实空间
       ElemType *base;
       //容量
       int capacity;
       //大小
       int size;
    }SeqList;
    
    //增加顺序表空间
    bool Inc(SeqList *list);
    
    //初始化顺序表
    void InitSeqList(SeqList *list);
    //1.尾部插入
    void push_back(SeqList *list, ElemType x);
    //2.头部插入
    void push_front(SeqList *list, ElemType x);
    //3.展示顺序表
    void show_list(SeqList *list);
    //4.从尾部删除
    void pop_back(SeqList *list);
    //5.从头部删除
    void pop_front(SeqList *list);
    //6.按位置插入
    void insert_pos(SeqList *list, int pos,ElemType x);
    //7.按值查找数据
    int find(SeqList *list,ElemType key);
    //8.提供顺序表的长度
    int get_length(SeqList *list);
    //9.按位置删除数据
    void delete_pos(SeqList *list, int pos);
    //10.按值删除数据
    void delete_val(SeqList *list, ElemType x);
    //11.排序
    void sort(SeqList *list);
    //12.倒换表的顺序
    void resver(SeqList *list);
    //13.清除
    void clear(SeqList *list);
    //14.摧毁
    void destroy(SeqList *list);
    #endif //__SEQLIST_H__

#### SeqList.cpp文件存放操作函数的实现 ####

#include"SeqList.h"
    
    //初始化顺序表
    void InitSeqList(SeqList *list){ 
    
    	list->base = (ElemType *)malloc(sizeof(ElemType) * SEQLIST_INIT_SIZE);
    	assert(list->base !=NULL);
    	list->capacity = SEQLIST_INIT_SIZE;
    	list->size = 0;
    }
    
    //增加顺序表空间
    bool Inc(SeqList *list){ 
    
    	ElemType *newBase = (ElemType *)realloc( list->base,sizeof(ElemType) * (list->capacity + INC_SIZE));
    	//判断是否分配失败
    	if(newBase == NULL){ 
    		//失败，返回false
    		return false;
    	}
    
    	//成功
    	list->base = newBase;
    	list->capacity += INC_SIZE;
    	return true;
    }
    
    
    //1.尾部插入
    void push_back(SeqList *list, ElemType x){ 
    
    	/* //判断表是否已满 if(list->size >= list->capacity && !Inc(list) ){ printf("顺序表空间已满，不能再插入数据\n"); return; } list ->base[list->size] = x; list ->size ++; */
    	
    	
    	//判断是否到表的尾部
    	if(list->size >= list->capacity){ 
    		//已经到尾部，增配空间
    		bool ifSuccess = Inc(list);
    		//判断空间是否增配成功
    		if( ifSuccess == false ){ 
    			//增配失败
    			printf("增配空间失败，系统内存已满\n");
    		}else{ 
    			list ->base[list->size] = x;
    			list ->size ++;
    		}
    	}else{ 
    		list ->base[list->size] = x;
    		list ->size ++;
    	}
    	
    }
    
    //2.头部插入
    void push_front(SeqList *list, ElemType x){ 
    	//判断表是否已满
    	if(list->size >= list->capacity  && !Inc(list) ){ 
    		printf("顺序表空间已满，不能再插入数据\n");
    		return;
    	}
    	for(int i = list->size; i > 0; i--){ 
    		list ->base[i] = list ->base[i - 1];
    	}
    	list ->base[0] = x;
    	list ->size ++;
    }
    
    //3.显示顺序表
    void show_list(SeqList *list){ 
    
    	for(int i = 0; i < list->size; i++){ 
    
    		printf("%4d",list->base[i]);
    	}
    	printf("\n");
    }
    
    //4.从尾部删除数据
    void pop_back(SeqList *list){ 
    	//判断顺序表是否为空
    	if(list->size == 0){ 
    		printf("顺序表已空，不能删除数据\n");
    		return;
    	}
    	list->size --;  // list->size 的数据已经为无效数据
    }
    
    //5.从头部删除数据
    void pop_front(SeqList *list){ 
    	//判断顺序表是否为空
    	if(list->size == 0){ 
    		printf("顺序表已空，不能删除数据\n");
    		return;
    	}
    	for(int i = 0; i < list->size - 1; i++){ 
    		list ->base[i] = list->base[i + 1];
    	}
    	list ->size --;
    }
    
    //6.按位置插入数据
    void insert_pos(SeqList *list,int pos,ElemType x){ 
    	//判断输入的位置是否能插入
    	if(pos < 0 || pos > list ->size){ 
    		printf("输入的位置非法，不能插入\n");
    		return;
    	}
    
    	if(list->size >= list->capacity && !Inc(list))
    	{ 
    		printf("顺序表空间已满，不能按位置插入数据\n");
    		return;
    	}
    	//从该位置起的数据都往后挪一位
    	for(int i = list->size; i > pos; i--){ 
    		list ->base[i] = list ->base[i -1];
    	}
    	list->base[pos] = x;
    	list ->size ++;	
    }
    
    //7.按值查找数据
    int find(SeqList *list, ElemType key){ 
    	int pos = -1;
    	//遍历整个顺序表，查找有没有该值
    	for(int i = 0;i < list->size; i ++){ 
    		if( key == list->base[i]){ 
    			pos = i;
    			break;
    		}
    	}
    	return pos;
    }
    
    //8.提供顺序表的长度
    int get_length(SeqList *list){ 
    	return list->size;
    }
    
    //9.按位置删除数据
    void delete_pos(SeqList *list, int pos){ 
    	//判断输入的位置是否能删除
    	if(pos < 0 || pos > list->size){ 
    		printf("输入的位置非法，不能删除\n");
    		return;
    	}
    	//从该位置起的后面数据都往前挪一位
    	for(int i = pos; i < list->size; i ++){ 
    		list ->base[i] = list ->base[i +1];
    	}
    	list ->size --;
    }
    
    //10.按值删除数据
    void delete_val(SeqList *list, ElemType x){ 
    	
    	int temp = -1;
    	for(int i = 0;i < list->size; i ++){ 
    		//判断输入的值是否在表内
    		if(x == list ->base[i]){ 
    			//在，删除
    			for(int j = i; j < list->size; j ++){ 
    				list ->base[j] = list ->base[j + 1];
    			}
    			list ->size --;
    			temp = 0;
    		}
    	}
    	if(temp == -1){ 
    		printf("输入的数据不存在\n");
    	}
    }
    
    //11.排序
    void sort(SeqList *list){ 
    	for(int i = 0; i < list->size; i ++){ 
    		for(int j = 0; j < i; j ++){ 
    			if(list ->base[i] < list ->base[j]){ 
    				int temp = 0;
    				temp = list ->base[j];
    				list ->base[j] = list ->base[i];
    				list ->base[i] = temp;
    			}
    		}
    	}
    }
    
    //12.倒换表的循序
    void resver(SeqList *list){ 
    	int temp[8];
    	for(int i = 0; i < list->size; i++){ 
    		temp[i] = list->base[i];
    	}
    	for(int j = 0; j < list->size; j ++){ 
    		list->base[list->size - j - 1] = temp[j];
    	}
    }
    
    //13.清除
    void clear(SeqList *list){ 
    	list ->size = 0;
    }
    
    //14.摧毁
    void destroy(SeqList *list){ 
    	free(list->base);
    	list->base = NULL;
    	list->capacity = 0;
    	list->size = 0;
    }

#### Main.cpp文件用于做测试 ####

#include"SeqList.h"
    
    int main(void){ 
    
    	SeqList myList;
        
    	//初始化顺序表
    	InitSeqList(&myList);
    
    	ElemType Item;
    	int pos;
    	int select = 1;
    
    	while(select){ 
    
         printf("***************************************************\n");
    
         printf("* [1] push_back [2] push_front * \n");   //从尾部插入 从头部插入
    	 printf("* [3] show_list [4] pop_back * \n");   //显示链表 从尾部删除
    	 printf("* [5] pop_front [6] insert_pos * \n");   //从头部删除 按输入位置插入
    	 printf("* [7] find [8] get_lengh * \n");   //查找数据 求表的长度
         printf("* [9] delete_pos [10] delete_val * \n");   //按位置删除 按值删除
    	 printf("* [11] sort [12] resver * \n");   //排序 前后转换
    	 printf("* [13] clear [14] destroy * \n");   //清除 摧毁
    	 printf("* [0] quit_system * \n");   //退出系统
    
    	 printf("***************************************************\n");
    	 printf("请选择：\n");
    	 scanf("%d",&select);
    
    	 if(select == 0){ 
    		break;
    	 }
    
    	 switch(select){ 
    	 case 1:
    		 printf("请输入要插入的数据(-1结束)：");
    		 scanf("%d",&Item);
    		 while(Item != -1){ 
    			push_back(&myList,Item);
    			scanf("%d",&Item);
    		 }	 
    		 break;
    	 case 2:
    		 printf("请输入要插入的数据(-1结束)：");
    		 scanf("%d",&Item);
    		 while(Item != -1){ 
    			push_front(&myList,Item);
    			scanf("%d",&Item);
    		 }
    		 break;
    	 case 3:
    		 show_list(&myList);
    		 break;
    	 case 4:
    		 pop_back(&myList);
    		 break;
    	 case 5:
    		 pop_front(&myList);
    		 break;
    	 case 6:
    		 printf("请输入要插入的数据：");
    		 scanf("%d",&Item);
    		 printf("\n");
    		 printf("请输入插入的位置下标：");
    		 scanf("%d",&pos);
    		 insert_pos(&myList,pos,Item);
    		 break;
    	 case 7:
    		 printf("请输入要查找的数据：");
    		 scanf("%d",&Item);
    		 pos = find(&myList,Item);
    		 if(pos == -1){ 
    			 printf("要查找的数据%d不存在\n",Item);
    		 }else{ 
    			 printf("要查找的数据%d位置下标为%d\n",Item,pos);
    		 }
    		 break;
    	 case 8:
    		 /* { int length = get_length(&myList); //在switch...case结构中不能定义新变量 printf("顺序表的长度为%d\n",length); //除非将定义新变量的语句用{}包住，或者将新变量提到switch前（明确变量的作用域） } */
             printf("顺序表的长度为:%d\n",get_length(&myList));
    		 break;
    	 case 9:
    		 printf("请输入要删除的位置下标：");
    		 scanf("%d",&pos);
    		 delete_pos(&myList,pos);
    		 break;
    	 case 10:
    		 printf("请输入要删除的值：");
    		 scanf("%d",&Item);
    		 delete_val(&myList,Item);
    		 break;
    	 case 11:
    		 sort(&myList);
    		 break;
    	 case 12:
    		 resver(&myList);
    		 break;
    	 case 13:
    		 clear(&myList);
    		 break;
    	 case 14:
    		 destroy(&myList);
    		 break;
    	 default:
    		 printf("输入的选择有误，请重新输入\n");
    		 break;
    	 getchar();
    	 }
    	}
    
    	return 0;
    }

[C_-]: http://e-learning.51cto.com/course/4725
[1]: /images/20211104/67a79e8b17f84c4493a961739b269c5e.png
[j_2]: /images/20211104/0099b49edfbc4eb38086b5c6f5e19b86.png
[2019080821530278.png]: /images/20211104/f27a612b7b78438196f0f5e26545dbea.png