1、线性表（List）

顺序表及链表

一、线性表的抽象数据类型描述

类型名：线性表（List） 数据对象集：线性表示n(>=0)个元素构成的有序序列(a1,a2,……,an) 操作集：线性表L∈List, 整数i表示位置,元素X∈ElementType

二、顺序表

1.定义

struct LNode {
    ElementType Data[MAXSIZE];//存了一个数组，其最多能存MAXSIZE个元素
    int Last;//最后一个元素的下标！
};
typedef struct LNode *List;

访问下标为i的元素:L.Data[i]或PtrL->Data[i] 线性表的长度: L.Last+1 或 PtrL->Last+1;

2.操作

其基本操作有

1.List MakeEmpty();//初始化一个空线性表 2.ElementType FindKth(int K, List Ptrl);//返回下标为K的相应元素 3.int Find(ElementType X, List Ptrl);//在线性表L中查找X的第一次出现位置 4.void Insert(ElementType X, int i, List Ptrl);//在位序i前插入一个新元素X 5.void Delete(int i, List Ptrl);//删除指定位序i的元素 6.int Length(List Ptrl);//返回线性表的长度n**

下面我们来一一过一遍

(1)创建空表

List MakeEmpty() {
    List PtrL;
    PtrL = (List)malloc(sizeof(struct LNode));
    PtrL -> Last = -1;
    return PtrL;
}

(2)查找下标为K的元素

返回下标K的相应元素。

ElementType FindKth(int K, List Ptrl) {
    return Ptrl->Data[K];
}

(3)查找元素X

返回下标，未找到返回-1。

int Find(ElementType X, List Ptrl) {
    int i = 0;
    while(i <= PtrL->Last && PtrL->Data[i] != X)
        i++;
    if(i > PtrL->Last) return -1;//如果没找到返回-1
    else return i;//找到后返回的是存储位置 即下标
}

(4)插入

在第i(1 ≤ i ≤ n+1)个位置上插入一个值为X的新元素

void Insert(ElementType X, int i, List Ptrl) {
    int j;
    if(Ptrl->Last == MAXSIZE-1) {//表空间已满，则不能插入
        printf("表满");
        return;
    }
    if(i < 1 || i > Ptrl->Last+2) {//检查输入是否合法
        printf("位置不合法");
        return;
    }
    for(j = Ptrl->Last; j >= i-1; j--) //注意这里顺序不能从前往后
        Ptrl->Data[j+1] = Ptrl->Data[j];
    Ptrl->Data[i-1] = X;
    Ptrl->Last++;//last仍指向最后元素！
    return;
}

(5)删除

删除第i个元素（下标为i-1）

void Delete(int i, List Ptrl) {
    int j;
    if(i < 1 || i > Ptrl->Last+1) {//检查输入是否合法
        printf("不存在第%d个元素",i);
        return;
    }
    for (j = i; j <= Ptrl->Last; j++) //删除操作就必须从前往后了
        Ptrl->Data[j-1] = Ptrl->Data[j];
    Ptrl->Last--;
    return;
}

(6)返回线性表的长度n

删除第i个元素（下标为i-1）

int Length(List Ptrl){
    return Ptrl->Last + 1;
}

3.完整代码演示

//顺序表
#include <iostream>
using namespace std;
typedef int ElementType;
const int MAXSIZE = 1000;
// 1.定义部分
struct LNode {
	ElementType Data[MAXSIZE];  //存了一个数组，其最多能存MAXSIZE个元素
	int Last;					//最后一个元素的下标！
};
typedef LNode *List;
// 2.操作函数
//(1) 建立空线性表
List MakeEmpty() {
	List Ptrl;									//建立
	Ptrl = new struct LNode;  //为其分配第一个结点的空间
	Ptrl->Last = -1;  //还未存数据，下边设为-1
	return Ptrl;	  //返回该指针
}
//(2) 查找下标为K的元素 返回下标K的相应元素
ElementType FindKth(int K, List Ptrl) {
    return Ptrl->Data[K];
}
//(3) 查找元素X 返回下标 未找到返回-1
int Find(ElementType X, List Ptrl) {
	int i = 0;
	while (i <= Ptrl->Last && Ptrl->Data[i] != X) {
		i++;
	}
	if (i > Ptrl->Last)
		return -1;
	else
		return i;
}
//(4) 插入元素X 在第i(1 ≤ i ≤ n+1)个位置上插入一个值为X的新元素
void Insert(ElementType X, int i, List Ptrl) {
	if (Ptrl->Last == MAXSIZE - 1) {  //表空间已满，则不能插入
		printf("表满");
		return;
	}
	if (i < 1 || i > Ptrl->Last + 2) {  //检查输入是否合法
		printf("位置不合法");
		return;
	}
	int j;
	for (j = Ptrl->Last; j >= i - 1; j--)  //注意这里顺序不能从前往后
		Ptrl->Data[j + 1] = Ptrl->Data[j];
	Ptrl->Data[i - 1] = X;
	Ptrl->Last++;  // last仍指向最后元素！
	return;
}
//(5) 删除 删除第i个元素（下标为i-1）
void Delete(int i, List Ptrl) {
	int j;
	if (i < 1 || i > Ptrl->Last + 1) {  //检查输入是否合法
		printf("不存在第%d个元素", i);
		return;
	}
	for (j = i; j <= Ptrl->Last; j++)  //删除操作就必须从前往后了
		Ptrl->Data[j - 1] = Ptrl->Data[j];
	Ptrl->Last--;
	return;
}
//(6) 返回线性表的长度n
int Length(List Ptrl){
    return Ptrl->Last + 1;
}
int main() {
    List P;
    P = MakeEmpty();
    for(int i = 0; i < 10; i++){
        Insert(i,i+1,P);
    }
    cout << "该顺序表长度为：" << Length(P) << endl;
    cout << "第5个元素为：" << FindKth(4,P) << endl;
    cout << "--删除第4个元素--" << endl;
    Delete(4,P);
    cout << "删除后第5个元素为：" << FindKth(4,P) << endl;
    cout << "表中是否有元素3(有则显示其下标无则显示-1)：" << Find(3,P) << endl;
    cout << "表中是否有元素5(有则显示其下标无则显示-1)：" << Find(5,P) << endl;
    delete [] P;
    return 0;
}

输出结果为：

该顺序表长度为：10 第5个元素为：4 --删除第4个元素-- 删除后第5个元素为：5 表中是否有元素3(有则显示其下标无则显示-1)：-1 表中是否有元素5(有则显示其下标无则显示-1)：4

三、线性表的链式存储

重要！！链表即不要求逻辑上相邻的两个元素物理上也相邻，通过"链"建立起数据元素之间的逻辑关系。 其插入和删除不需要移动数据元素，只需要修改链。

1.定义

typedef struct LNode *List;
struct LNode {
    ElementType Data;
    List Next;//存放指向下一个结点的指针
}L;
List PtrL;

2.操作

其基本操作有

1.List Insert(ElementType X, int i, List PtrL) ;//插入(在第i-1(1<=i<=n+1)个结点后插入一个值为X的新结点) 2.List FindKth(int K, List PtrL) ;//按序号查找查找 查找链表中第K个元素 List Find(ElementType X, List PtrL) ; //按值查找: 查找元素K 3.List Delete(int i, List PtrL);//删除操作(删除链表第i个位置上的结点) 4.int Length(List PtrL)//求表长

(1)插入操作

在第i-1(1 ≤ i ≤ n+1)个结点后插入一个值为X的新结点 (1)先构造一个新结点，用s指向 //malloc分配空间 将s的数据Data赋值为X (2)再找到链表的第i-1个结点，用p指向 (3)然后修改指针，插入结点(p之后插入新结点是s) // 先将p原先的指向next给s的next指针，再将p的next指针指向s

List Insert(ElementType X, int i, List PtrL) {
    List p, s;
    if(i == 1) {//新节点插入到表头
        s = (List)malloc(sizeof(struct LNode));//申请、填装节点
        s->Data = X;
        s->Next = PtrL;
        return s;       //返回新表头指针
    }
    p = Find(i-1,PtrL);         //查找第i-1个结点
    if(p == NULL) {             //第i-1个不存在 无法插入
        printf("参数i错");
        return NULL;
    } else {
        s = (List)malloc(sizeof(struct LNode)); //申请、填装结点
        s->Data = X;
        s->Next = p->Next;          //新节点插入在第i-1个节点的后面
        p->Next = s;
        return PtrL;
    }
}

(2)查找

找到则返回指向该结点的指针，找不到返回NULL

1.按值查找:Find

按值查找: 查找元素K

List Find(ElementType X, List PtrL) {
    List p = PtrL;
    while(p != NULL && p->Data != X) 
        p = p->Next;
    if(p == NULL) {          
        cout << "找不到该元素" << endl;
        return NULL;
    } else  return p;
}

2.按序号查找：FindKth

按序号查找查找 查找链表中第K个元素

List FindKth(int K, List PtrL) {
    List p = PtrL;
    int i = 1;
    while (p != NULL && i < K) {
        p = p->Next;
        i++;
    }
    if(i == K) return p;//找到第K个返回指针
    else {              //否则返回空指针
        cout << "找不到该元素" << endl;
        return NULL;
    }
}

(3)删除操作

删除链表第i个位置上的结点 (1)先找到链表的第i-1个结点，用p指向;//Find(i-1,PtrL); (2)再用指针s指向要被删除的结点(p的下一个结点)//s = p->Next; (3)然后修改指针，删除s所指向的结点//p->Next = s->Next; (4)最后释放s所指结点的空间！ //free(s)

List Delete(int i, List PtrL) {
    List p, s;
    if( i == 1) {   //若要删除的是表的第一个结点
        s = PtrL;           //s指向第1个结点
        if (PtrL != NULL)   PtrL = PtrL->Next;  //从链表中删除
        else return NULL;
        free(s);                            //释放被删除结点
        return PtrL;
    }
    p = FindKth(i-1, PtrL);     //查找第i-1个结点
    if (p == NULL) {
        printf("第%d个结点不存在", i-1);
        return NULL;
    } else if (p->Next == NULL) {
        printf("第%d个结点不存在",i);
        return NULL;
    } else {
        s = p->Next;            //s指向第i个结点
        p->Next = s->Next;      //从链表中删除
        free(s);                //释放被删除结点的空间
        return PtrL;
    }
}

(4)求表长

int Length(List PtrL) {
    List p = PtrL;//p指向表的第一个节点
    int j = 0;
    while(p) {
        p = p->Next;
        j++;
    }
    return j;
}

3.完整代码演示

//链表
#include <iostream>
using namespace std;
typedef int ElementType;
const int MAXSIZE = 1000;
// 1.定义部分
struct LNode;
typedef LNode *List;
struct LNode {
	ElementType Data;
	List Next;  //存放指向下一个结点的指针
};
List Insert(ElementType X,int i,List PtrL);  
//插入(在第i-1(1<=i<=n+1)个结点后插入一个值为X的新结点)
List FindKth(int K, List PtrL);  //按序号查找查找 查找链表中第K个元素
List Find(ElementType X, List PtrL);  //按值查找: 查找元素K
List Delete(int i, List PtrL);  //删除操作(删除链表第i个位置上的结点)
int Length(List PtrL);			//求表长
// 2.操作函数
//(1) 插入操作 在第i-1(1 ≤ i ≤ n+1)个结点后插入一个值为X的新结点
List Insert(ElementType X, int i, List PtrL) {
	List p, s;
	if (i == 1) {			   //新节点插入到表头
		s = new struct LNode;  //申请、填装节点
		s->Data = X;
		s->Next = PtrL;
		return s;  //返回新表头指针
	}
	p = Find(i - 1, PtrL);  //查找第i-1个结点
	if (p == NULL) {		//第i-1个不存在 无法插入
		printf("参数i错");
		return NULL;
	} else {
		s = new struct LNode;  //申请、填装结点
		s->Data = X;
		s->Next = p->Next;  //新节点插入在第i-1个节点的后面
		p->Next = s;
		return PtrL;
	}
}
//(2) 查找 找到则返回指向该结点的指针，找不到返回NULL
List Find(ElementType X, List PtrL) {//按值查找 查找元素X
    List p = PtrL;
    while(p != NULL && p->Data != X) 
        p = p->Next;
    if(p == NULL) {          
        cout << "找不到该元素" << endl;
        return NULL;
    } else  return p;
}
List FindKth(int K, List PtrL) {//按序号查找 查找第K个元素
    List p = PtrL;
    int i = 1;
    while (p != NULL && i < K) {
        p = p->Next;
        i++;
    }
    if(i == K) return p;//找到第K个返回指针
    else {              //否则返回空指针
        cout << "找不到该元素" << endl;
        return NULL;
    }
}
//(3) 删除 删除链表第i个位置上的结点
List Delete(int i, List PtrL) {
    List p, s;
    if( i == 1) {   //若要删除的是表的第一个结点
        s = PtrL;           //s指向第1个结点
        if (PtrL != NULL)   PtrL = PtrL->Next;  //从链表中删除
        else return NULL;
        delete [] s;                           //释放被删除结点
        return PtrL;
    }
    p = FindKth(i-1, PtrL);     //查找第i-1个结点
    if (p == NULL) {
        printf("第%d个结点不存在", i-1);
        return NULL;
    } else if (p->Next == NULL) {
        printf("第%d个结点不存在",i);
        return NULL;
    } else {
        s = p->Next;            //s指向第i个结点
        p->Next = s->Next;      //从链表中删除
        delete [] s;                //释放被删除结点的空间
        return PtrL;
    }
}
//(4) 求表长
int Length(List PtrL) {
    List p = PtrL;//p指向表的第一个节点
    int j = 0;
    while(p) {
        p = p->Next;
        j++;
    }
    return j;
}
int main() {
	List P = NULL;
	for (int i = 0; i < 10; i++) {
		P = Insert(i, 1, P);// 头插法 插入元素在表头
	}
    List s;
	cout << "该链表长度为：" << Length(P) << endl;
	cout << "第4个元素为：";
    s = FindKth(4, P);
    if(s) cout << s->Data << endl;
	cout << "--删除第4个元素--" << endl;
	Delete(4, P);
	cout << "删除后第4个元素为：" ;
    s = FindKth(4, P);
    if (s) cout << s->Data << endl;
	cout << "表中是否有元素6：";
    s = Find(6, P);
    if (s) cout << s->Data << endl;
	cout << "表中是否有元素5：";
    s = Find(5, P);
    if (s) cout << s->Data << endl;
	delete[] P;
	return 0;
}

输出结果为：

该链表长度为：10 第4个元素为：6 --删除第4个元素-- 删除后第4个元素为：5 表中是否有元素6：找不到该元素 表中是否有元素5：5