~~顺序表~~

1.线性结构的特点是：

在数据元素的非空有限集中：

(1).存在唯一的一个被称为“第一个”的数据元素

(2).存在唯一的一个被称为“最后一个”的数据元素

(3).除第一个之外，集合中的每个数据元素都只有一个前驱

(4).除第一个之外，集合中每个集合数据元素都只有一个后继

线性表中数据元素必须是连续

2.线性表的定义

线性表是最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。至于每个元素的具体含义，在不同的情况下各不相同，它可以是一个整数或一个字符，也可以是更复杂的信息。

在稍复杂的线性表中，一个数据元素可以由若干个数据项组成。在这种情况下，常把数据元素称为记录，含有大量记录的线性表又称文件。

线性表中数据元素的个数n(n>=0)定义为线性表的长度，n=0时又称空表。在非空表中的每个数据元素都有一个确定的位置，如a1是第一个数据元素，an是最后一个数据元素，ai是第i个数据元素，称i为数据元素ai在线性表中的位序。

位序也可从0开始。

3.线性表的顺序--表示和实现

线性表的顺序--表示指的是用一组地址连续的存储单元(内存)依次存储线性表的数据元素。

整型数组arr的存储表示

线性表的这种在计算机内存中表示称做线性表的顺序存储结构或者顺序映像，这种存储结构的线性表为顺序表

特点：

1.数据元素在计算机内存"物理位置相邻"来表示线性表中数据元素之间的逻辑关系

2.只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取结构

C语言语言中的数组类型，具有连续存储空间和随机存取数据元素的特性，因此，通常都用数组来描述数据结构中的顺序存储结构

4.顺序表的设计

Seq_list.h

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <iostream>using namespace std;typedef int Elem_Type;   //表中元素类型#define INIT_CAP   10      //表的初始容量typedef struct Seq_list
{Elem_Type *data;     //指向表内存空间的指针int capacity;        //表的容量int Curr_Cap;        //表的当前容量
}Seq_list;void Init_Seq_List(Seq_list *p_list);              //初始化表void Dest_Seq_List(Seq_list *p_list);              //摧毁表void Clear_Seq_List(Seq_list *p_list);             //清空表static int Get_Seq_List_Data_Count(const Seq_list *p_list);     //获取表中元素的个数static int Get_Seq_List_capacity(const Seq_list *p_list);       //获取表的容量bool Is_Empty_Seq_List(const Seq_list *p_list);          //判空bool Is_Full_Seq_List(const Seq_list *p_list);           //判满void Inc_Cap(Seq_list *p_list);                          //扩容void Print_Seq_List(const Seq_list *p_list);             //打印表中元素void Head_Insert(Seq_list *p_list, Elem_Type val); //头插void Tail_Insert(Seq_list *p_list, Elem_Type val); //尾插void Head_Delete(Seq_list *p_list);                //头删void Tail_Delete(Seq_list *p_list);                //尾删void Insert_Locat(Seq_list *p_list, int locat, Elem_Type val);    //指定位置插入void Delete_Locat(Seq_list *p_list, int locat);    //指定位置删除Elem_Type Get_Pos_Data(const Seq_list *p_list, int pos); //获取指定位置的元素static int Find_Val(const Seq_list *p_list, Elem_Type val);     //查询元素返回下标,第一次出现得该元素的下标bool Judge_Data(const Seq_list *p_list, Elem_Type val);  //判断元素是否在表中bool Delete_Data_Fir_Appear(Seq_list *p_list, Elem_Type val); //删除数据元素（首次出现）void Delete_Data_All_Req_Val(Seq_list *p_list, Elem_Type val); //删除所有与val相等的数据元素void Bubble_Sort(Seq_list *p_list);                //冒泡排序int Half_Query(Seq_list *p_list, Elem_Type val);   //折半查询

Seq_List_test.cpp

#include "Seq_list.h"void Init_Seq_List(Seq_list *p_list)    //初始化
{assert(p_list != NULL);p_list->capacity = INIT_CAP;p_list->Curr_Cap = 0;p_list->data = (Elem_Type*)malloc(sizeof(Elem_Type)*INIT_CAP);if (p_list->data == NULL){printf("malloc申请失败！");return;}memset(p_list->data, 0, sizeof(Elem_Type)*INIT_CAP);
}void Dest_Seq_List(Seq_list *p_list)
{assert(p_list != NULL);p_list->Curr_Cap = 0;p_list->capacity = 0;free(p_list->data);p_list->data = NULL;
}void Clear_Seq_List(Seq_list *p_list)
{assert(p_list != NULL);p_list->Curr_Cap = 0;       //逻辑清空
}static int Get_Seq_List_Data_Count(const Seq_list *p_list)
{assert(p_list != NULL);return p_list->Curr_Cap;
}static int Get_Seq_List_capacity(const Seq_list *p_list)
{assert(p_list != NULL);return p_list->capacity;
}bool Is_Empty_Seq_List(const Seq_list *p_list)
{assert(p_list != NULL);return !(p_list->Curr_Cap);
}bool Is_Full_Seq_List(const Seq_list *p_list)
{assert(p_list != NULL);if (p_list->Curr_Cap == p_list->capacity){return true;}else{return false;}
}void Print_Seq_List(const Seq_list *p_list)
{assert(p_list != NULL);if (Is_Empty_Seq_List(p_list)){printf("表中无元素！\n");return;}printf("capacity:%d\n", p_list->capacity);printf("Curr_Cap:%d\n", p_list->Curr_Cap);for (int i = 0; i < p_list->Curr_Cap; i++){cout << p_list->data[i] << " ";}cout<<endl;
}void Head_Insert(Seq_list *p_list, Elem_Type val)
{assert(p_list != NULL);Insert_Locat(p_list, 0, val);
}void Tail_Insert(Seq_list *p_list, Elem_Type val)
{assert(p_list != NULL);int Cur_cap = Get_Seq_List_Data_Count(p_list);Insert_Locat(p_list, p_list->Curr_Cap, val);
}void Head_Delete(Seq_list *p_list)
{assert(p_list != NULL);Delete_Locat(p_list, 0);
}void Tail_Delete(Seq_list *p_list)
{assert(p_list != NULL);int Delete_Pos = Get_Seq_List_Data_Count(p_list) - 1;Delete_Locat(p_list, Delete_Pos);
}void Inc_Cap(Seq_list *p_list)
{assert(p_list != NULL);Elem_Type *tmp = (Elem_Type *)realloc(p_list->data, sizeof(Elem_Type)*p_list->capacity * 2);if (tmp == NULL){printf("扩容失败!");return;}p_list->data = tmp;p_list->capacity *= 2;
}void Insert_Locat(Seq_list *p_list, int locat, Elem_Type val)
{assert(p_list != NULL);if (Is_Full_Seq_List(p_list)){Inc_Cap(p_list);}if (locat<0 || locat>p_list->Curr_Cap){cout << "输入位置有误！\n";return;}int Currt_capa = Get_Seq_List_Data_Count(p_list);for (int i = Currt_capa; i > locat; i--){p_list->data[i] = p_list->data[i-1];}p_list->data[locat] = val;p_list->Curr_Cap++;
}void Delete_Locat(Seq_list *p_list, int locat)
{assert(p_list != NULL);if (Is_Empty_Seq_List(p_list)){printf("表中无元素！\n");return;}if (locat<0 || locat>=p_list->Curr_Cap){cout << "输入位置有误！\n";return;}for (int i = locat; i < p_list->Curr_Cap; i++){p_list->data[i] = p_list->data[i + 1];}p_list->Curr_Cap--;
}Elem_Type Get_Pos_Data(const Seq_list *p_list, int pos)
{assert(p_list != NULL);return p_list->data[pos];
}int Find_Val(const Seq_list *p_list, Elem_Type val)
{assert(p_list != NULL);if (Is_Empty_Seq_List(p_list)){printf("表中无元素！\n");return -1;}for (int i = 0; i < p_list->Curr_Cap; i++){if (p_list->data[i] == val){return i;}}printf("表中无该元素!\n");return -1;
}bool Judge_Data(const Seq_list *p_list, Elem_Type val)
{assert(p_list != NULL);int tag = Find_Val(p_list, val);return !(tag == -1);
}bool Delete_Data_Fir_Appear(Seq_list *p_list, Elem_Type val)
{assert(p_list != NULL);int pos = Find_Val(p_list, val);if (pos == -1){return false;}Delete_Locat(p_list,pos);return true;
}void Delete_Data_All_Req_Val(Seq_list *p_list, Elem_Type val)
{assert(p_list != NULL);
/** *********************************************  效率太低*  int judge = Find_Val(p_list, val);*	if (judge == -1)*	{printf("找不到此元素！\n");*		return;*	}*	for (int i = 0; i < p_list->Curr_Cap; i++)*	{*		if (p_list->data[i] == val)*		{*			Delete_Locat(p_list, i); *		}*	}* ** *********************************************/int j = -1;for (int i = 0; i < p_list->Curr_Cap; i++){if (p_list->data[i] != val){j += 1;p_list->data[j] = p_list->data[i];}}if (j == -1){printf("找不到此元素！\n");}else{p_list->Curr_Cap = j + 1;}
}void Bubble_Sort(Seq_list *p_list)
{assert(p_list != NULL);if (Is_Empty_Seq_List(p_list)){printf("表中无元素！\n");return;}for (int i = p_list->Curr_Cap - 1; i > 0; i--) //躺数{int tag = 1;for (int j = 0; j < i; j++){if (p_list->data[j + 1] < p_list->data[j]){Elem_Type tmp = p_list->data[j];p_list->data[j] = p_list->data[j + 1];p_list->data[j + 1] = tmp;tag = 0;}}if (tag){break;}}
}int Half_Query(Seq_list *p_list, Elem_Type val)       //二分查询第一次出现此元素的下标
{assert(p_list != NULL);Bubble_Sort(p_list);if (Is_Empty_Seq_List(p_list)){printf("表中无元素！\n");return -1;}int len = p_list->Curr_Cap;int left = 0;int right = len - 1;int mid = (right + left) / 2;while (left <= right){mid = (right + left) / 2;if (p_list->data[mid] == val){if (mid > left&&p_list->data[mid - 1] == val){right = mid - 1;}else{return mid;}}if (p_list->data[mid] < val){left = mid + 1;}if (p_list->data[mid] > val){right = mid - 1;}}printf("表中无此元素！\n");return -1;
}

main.cpp

#include "Seq_list.h"int main()
{Seq_list My_list;Init_Seq_List(&My_list);int arr[] = { 69, 12, 12, 34, 56, 12, 12, 89, 87,13,46 };int len= sizeof(arr) / sizeof(arr[0]);for (int i = 0; i < len; i++){Tail_Insert(&My_list, arr[i]);}Print_Seq_List(&My_list);Delete_Data_All_Req_Val(&My_list, 12);Print_Seq_List(&My_list);Delete_Data_All_Req_Val(&My_list, 55);Bubble_Sort(&My_list);Print_Seq_List(&My_list);Tail_Delete(&My_list);Print_Seq_List(&My_list);Dest_Seq_List(&My_list);system("pause");return 0;
}