数据结构之线性表

数据结构之线性表

一、基本定义

1、线性表的概念、定义，特点，线性表抽象数据类型定义

1、定义：具有相同数据类型的n（n≥0）个数据元素的有限序列(线性表是逻辑结构)
2、特点：个数有限、顺序性、每个元素所占存储空间相同

2、其他

顺序表有序的时候，折半查找时间复杂度为O(log2(n))
线性表顺序存储结构是一个随机存取的存储结构(随机存取指的是读写)

二、线性表的顺序表示与实现

1、静态顺序表

#include <bits/stdc++.h>
#define MaxSize 10
#define ElemType intusing namespace std;// 静态顺序表
typedef struct {ElemType data[MaxSize];int length;
}Sqlist;// Initiate List
void InitList(Sqlist &L) {for(int i = 0; i < MaxSize; i++)L.data[i] = 0;L.length = 0;
}int main() {Sqlist L;InitList(L);
}

2、静态表

静态表是动态存储的，其实简单来讲就是动态数组，后面的栈和队列就是以此为基础的

// 动态顺序表
#include <bits/stdc++.h>
#include <stdlib.h>#define InitSize 10
#define AddSize 10
#define ElemType intusing namespace std;typedef struct {ElemType *data;	int MaxSize;int length;
}SeqList;// 初始化顺序表 
void InitList(SeqList &L) {L.data = (int *) malloc(InitSize * sizeof(ElemType));L.MaxSize = InitSize;L.length = 0;
}// 动态增加顺序表长度
void IncreaseSize(SeqList &L, int len) {ElemType *p = L.data;L.data = (int *) malloc((L.MaxSize + len) * sizeof(ElemType));for(int i = 0; i < L.length; i++)L.data[i] = p[i];L.MaxSize += len;free(p);
}// 增, O(n)
bool ListInsert(SeqList &L, int i, ElemType e) {if (i < 1 || i > L.length + 1)return false;if (L.length >= L.MaxSize)IncreaseSize(L, AddSize);for(int j = L.length; j >= i; j--)L.data[j] = L.data[j-1];L.data[i-1] = e;L.length++;return true;
}// 删, O(n)
bool ListDelete(SeqList &L, int i, ElemType &e) {if(i > L.length || i < 1)return false;e = L.data[i-1];for(int j = i; j < L.length; j++)L.data[j-1] = L.data[j];L.length--;return true;
}// 按位查找, O(1)
ElemType GetElem(SeqList L, int i) {if (i > L.length || i < 1)return 0;return L.data[i-1];
}// 按值查找, O(n)
int LocateElem(SeqList L, ElemType e) {for (int i = 0; i < L.length; i++){if (L.data[i] == e)return i + 1;}return 0;	// 查找失败 
} void PrintAll(SeqList L) {for (int i = 0; i < L.length; i++)cout<<L.data[i]<<" ";cout<<endl;
}// 测试信息
//int main() {
//	SeqList L;
//	InitList(L);
//	ListInsert(L, 1, 1);
//	ListInsert(L, 2, 2);
//	ListInsert(L, 3, 3);
//	PrintAll(L);
//	int e = -1;
//	ListDelete(L, 2, e);
//	cout<<"删除的数为:"<<e<<endl;
//	cout<<"3在第"<<LocateElem(L, 3)<<"个位置"<<endl;
//	PrintAll(L);
//	return 0; 
//}

三、线性表的链式表示与实现

1、单链表包含了指针的知识，是第一部分的重难点

2、特点

单链表便于插入删除，但是查找需要遍历整个链表才可以

3、代码实现

#include <bits/stdc++.h>#define ElemType intusing namespace std;typedef struct LNode {ElemType data;LNode *next;
}LNode, *LinkList; 初始化:不带头指针的单链表 
//bool InitList(LinkList &L) {
//	L = NULL;
//	return true;
//}// 初始化: 带头指针的单链表
// LinkList和LNode * 其实代指一样，只是前面强调为链表，后面强调为一个节点 
bool InitList(LinkList &L) {L = (LNode *) malloc(sizeof(LNode));if (L == NULL)return false;L->next = NULL;return true;
}// 按位查找, 返回第i个元素
LNode *GetElem(LinkList L, int i) {if (i < 0)return NULL;// 如果i == 0, 返回的是头结点 LNode *p = L;int j = 0;while(p != NULL && j < i) {p = p -> next;j++;}return p;
}// 按值查找
LNode *LocateElem(LinkList L, ElemType e) {LNode *p = L -> next;while (p != NULL && p -> data != e)p = p -> next;return p;
} // 指定节点后插操作
bool InsertNextNode(LNode *p, ElemType e) {if (p == NULL)return false;LNode *s = (LNode *) malloc(sizeof(LNode));s -> data = e;s -> next = p -> next;p -> next = s;return true; 
}// 指定节点的前插操作
bool InsertBeforeNode(LNode *p, ElemType e) {if (p == NULL)return false;LNode *s = (LNode *) malloc(sizeof(LNode));s -> next = p -> next;p -> next = s;// 换一下数据即可, 复杂度为O(1) s -> data = p -> data;p -> data = e;return true; 
}// 按照位序插入, O(n) 
bool ListInsert(LinkList &L, int i, ElemType e) {// 找到要插入位置的前一個LNode *p = GetElem(L, i - 1);  if (p == NULL)return false;// 下面全部代码可以换成// return InsertNextNode(p, e); LNode *s = (LNode *) malloc(sizeof(LNode));s -> data = e;s -> next = p -> next;p -> next = s;return true;
}// 按位序删除, O(n)
bool ListDelete(LinkList &L, int i, ElemType &e) {LNode *p = GetElem(L, i - 1);if (p == NULL)return false;LNode *q = p -> next;e = q -> data;p -> next = q -> next;free(q);return true;
}// 求表的长度 
int Length(LinkList L) {int len = 0;LNode *p = L;while(p -> next != NULL){p = p-> next;len++;}return len;
}// 建立单链表(尾插法)
LinkList List_TailInsert(LinkList &L) {ElemType input;L = (LinkList) malloc(sizeof(LNode));L -> next = NULL;LNode *r = L;cin>>input;while(input != -1) {LNode *s = (LNode *) malloc(sizeof(LNode));s -> data = input;s -> next = r -> next;r -> next = s;r = r -> next;cin>>input;}return L;
}// 建立单链表(头插法)
LinkList List_HeadInsert(LinkList &L) {L = (LinkList) malloc(sizeof(LNode));L -> next = NULL;ElemType input;cin>>input;while(input != -1) {LNode *s = (LNode *) malloc(sizeof(LNode));s -> data = input;s -> next = L -> next;L -> next = s;cin>>input;}return L;
}// 链表逆置
LinkList ReverseList(LinkList &L) {if(L -> next == NULL || L -> next -> next == NULL)return L;LNode *p = L -> next, *s;while(p -> next != NULL) {// 刪除了后面节点 s = p -> next;p -> next = s -> next;// 头插法s -> next = L -> next;L -> next = s;}
}// 打印所有 
bool PrintAll(LinkList L) {LNode *p = L;while(p -> next != NULL) {p = p -> next;cout<<p -> data<<" ";}cout<<endl;
} // 测试用
int main() {LinkList L;int e;LNode *p;// 输入1, 2, 3, -1 List_TailInsert(L);PrintAll(L);			// 1, 2, 3ListInsert(L, 3, 4);p = LocateElem(L, 2);cout<<p -> data<<endl;	// 2InsertBeforeNode(p, 5);PrintAll(L);			// 1, 5, 2, 4, 3ListDelete(L, 1, e);cout<<e<<endl;			// 1PrintAll(L);			// 5, 2, 4, 3ReverseList(L);			// 3, 4, 2, 5PrintAll(L);cout<<Length(L);		// 4
}