第二章线性表

第二章线性表 线性表的定义和基本 *** 作 知识框架

定义

1、相同数据类型，有限序列

2、除第一个元素外每个元素有且仅有一个直接前驱

3、除最后一个元素外，每个元素有且仅有一个后继

4、位序从1开始，线性表下标从0开始

5、线性表逻辑结构，表示元素直接一对一的相邻关系

6、顺序表和链表是指存储结构

基本 *** 作

线性表的顺序表示 顺序表的定义

逻辑上相邻的两个元素在物理位置上也相邻

• 动态分配和静态分配：

  • C的初始动态分配语句：

  L.data = (类型*) malloc(sizeof(类型*)*表长度);//malloc的头文件是#include 
  

  • C++的初始动态分配语句：

  L.data = new 数据类型[表长];
  

  注意：动态分配不是链式存储，属于顺序存储结构，物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时动态决定

• 顺序表特点：

  • 随机访问
  • 存储密度高，每个节点只存储数据元素
  • 逻辑上相邻的元素物理上也相邻
  • 插入和删除需移动大量元素

• 基本 *** 作代码

#include 
#include 
#define InitSize 100
#define MaxSize 50 //数组长度及顺序表的初始化长度 
typedef struct SeqList{
	int data[MaxSize];
	int len;
} SeqList;
//初始化表 
void InitList(SeqList *L){
	for(int i = 0;i<MaxSize ; i++)
		L->data[i] = 0;
	L->len = 0;
}
//插入 *** 作
/*
	在顺序表L的第i个位置插入新元素e （1<=i<=L.length+1） 
	若输入的I不合法，返回false
	否则，将顺序表的第i个元素及其后的所有元素右移一个位置，腾出一个空位置，插入e，插入成功返回ture 

*/ 
bool ListInsert(SeqList *L,int i ,int e)//这里的i是表中位置，不是下标，e是要插入的元素 
{
	if(i<1|| i>L->len +1)//i的位置不在1-len之间 
		return false;
	if(L->len>=MaxSize)//表满了 
		return false;
	for (int j = L->len;j>=i;j--)
		L->data[j] = L->data[j-1];
	L->data[i-1] = e;
	L->len++;
	return true;
}
//遍历
bool OutPutList(SeqList *L){
	if(L->len == 0)
	{
		printf("表空");
		return false;
	}
	for (int i=0;i<L->len;i++)
		printf("%d\n",L->data[i]);
	printf("此时的表长为%d\n",L->len);
	return true;
} 
//删除
bool ListDlete(SeqList *L,int i,int &e){
	if( i > L->len || i<1)
		return false;
	e = L->data[i-1];
	for(int j= i-1; j < L->len ;j++)//这里的i是表长的i ,从1开始数 
		L->data[j] = L->data[j+1];
	L->len--;
	return true;
}
//按位查找
bool GetElem(SeqList *L,int i){
	if(i<1 || i>L->len)
		return false;
	printf("第%d位的元素是%d\n",i,L->data[i-1]);
	return true;
		
} 
//按值查找
bool LocateElem(SeqList *L,int e){
	for(int j = 0;j<=L->len;j++)
	{
		if (j == L->len){
			printf("无此数据，查找失败\n");
			return false;
		}
		if(L->data[j] == e)
		{
			printf("查找成功，您要找的数据在第%d位\n",j+1);
			return true;			
			}
	}
} 
//判空 *** 作
bool Empty(SeqList *L){
	if(L == NULL)
		return true;
	else
		return false;
} 
//销毁表
bool DestroyList(SeqList *L){
	
} 
int main(){
	SeqList *L = NULL,l;//生成静态顺序表实体l，指向该实体的指针'L' 
	L = &l;
	InitList(L);
	ListInsert(L,1,1);
	ListInsert(L,2,3123);
	ListInsert(L,3,123);
	OutPutList(L);
	int e=3123;
	ListDlete(L,2,e);
	OutPutList(L); 
	GetElem(L,2);
	LocateElem(L,1);
	return 0;
}