线性表
- 数据结构之线性表
- 一、基本定义
- 1、线性表的概念、定义,特点,线性表抽象数据类型定义
- 2、其他
- 二、线性表的顺序表示与实现
-
- 三、线性表的链式表示与实现
- 1、单链表包含了指针的知识,是第一部分的重难点
- 2、特点
- 3、代码实现
数据结构之线性表
一、基本定义
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;
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);
}
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;
}
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;
}
ElemType GetElem(SeqList L, int i) {if (i > L.length || i < 1)return 0;return L.data[i-1];
}
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;
}
三、线性表的链式表示与实现
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 = (LNode *) malloc(sizeof(LNode));if (L == NULL)return false;L->next = NULL;return true;
}
LNode *GetElem(LinkList L, int i) {if (i < 0)return NULL;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;s -> data = p -> data;p -> data = e;return true;
}
bool ListInsert(LinkList &L, int i, ElemType e) {LNode *p = GetElem(L, i - 1); if (p == NULL)return false;LNode *s = (LNode *) malloc(sizeof(LNode));s -> data = e;s -> next = p -> next;p -> next = s;return true;
}
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;List_TailInsert(L);PrintAll(L); ListInsert(L, 3, 4);p = LocateElem(L, 2);cout<<p -> data<<endl; InsertBeforeNode(p, 5);PrintAll(L); ListDelete(L, 1, e);cout<<e<<endl; PrintAll(L); ReverseList(L); PrintAll(L);cout<<Length(L);
}