数据结构学习笔记＜1＞线性表

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

类型名：线性表（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 的元素.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. 按值查找#

按值查找：查找元素 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