线性表
线性表的定义:
由n(n≥0)==类型相同==的数据元素构成的==有限==序列,称为线性表
一、线性表的顺序存储表示
线性表的顺序存储表示是指用一组地址连续的存储空间依次存放线性表中的数据元素,称这种存储结构的线性表为顺序表
1.存储结构
#define MAXSIZE 20
typedef int ElemType
typedef struct{
ElemType data[MAXSIZE]; //数组,存储数据元素
int length; //当前长度
}SqList; //顺序表
2.获得元素操作
#define OK 1
#define ERROR 0
typedef int Status;
/* 初始条件:顺序线性表L已存在, 1<=i<=Listlength(L)
* 操作结果:用e返回L中第i个数据元素的值,注意i是指位置,第1个位置的数组是从0开始
*/
Status GetElem(SqList L, int i,ElemType *e){
if(L.length == 0 || i < 1 || i > L.length)
return ERROR;
*e = L.data[i - 1];
return OK;
}
3.插入操作
/* 初始条件:顺序线性表L已存在, 1<=i<=Listlength(L)
* 操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1
*/
Status ListInsert(SqList *L,int i,ElemType e){
int k;
if(L->length == MAXSIZE) //顺序线性表已经满
return ERROR;
if(i < 1 || i > L->length + 1) //当i比第一位置小或者比最后一位置还要大时
return ERROR;
if(i <= L->length){ //若插入位置不在表尾
for(k = L->length - 1; k >= i - 1;k--) //将要插入位置后的元素向后移一位
L->data[k+1] = L->data[k];
}
L->data[i - 1] = e; //将新元素插入
L->length++;
return OK;
}
4.删除操作
/* 初始条件:顺序线性表L已存在, 1<=i<=Listlength(L)
* 操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1
*/
Status ListInsert(SqList *L,int i,ElemType *e){
int k;
if(L->length == 0) //顺序线性表为空
return ERROR;
if(i < 1 || i > L->length) //删除位置不正确
return ERROR;
*e = L->data[i - 1];
if(i < L->length){ //若删除不是最后位置
for(k = i; k < L->length;k++) //将删除位置后继元素前移
L->data[k-1] = L->data[k];
}
L->length--;
return OK;
}
二、线性表链式存储结构表示
1.存储结构
typedef struct Node{
ElemType data;
struct Node * next;
}Node,*Linklist;
单链表的读取
/* 初始条件:链式线性表L已存在, 1<=i<=Listlength(L)
* 操作结果:用e返回L中第i个数据元素的值
*/
Status GetElem(Linklist L, int i, ElemType *e){
int j;
Linklist p; //声明一个结点p
p = L -> next; //让p指向链表L的第一个结点
j = 1; //j为计数器
while(p && j < 1){ //p不为空或者计数器j还没有等于i时,循环继续
p = p->next; // 让p指向下一个结点
++j;
}
if(!p || j > i)
return ERROR; //第i个元素不存在
*e = p->data; //取第i个元素的数据
return OK;
}
单链表的插入
/* 初始条件:链式线性表L已存在, 1<=i<=Listlength(L)
* 操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1
*/
Status ListInsert(Linklist *L,int i,ElemType e){
int j;
LinkList p,s;
p = *L;
j = 1;
while(p && j < i){ //寻找第i个结点
p = p->next;
++j;
}
if(!p || j > i){
return ERROR; //第i个结点不存在
}
s = (LinkList)malloc(sizeof(Node)); //生成新结点
s->data = e;
s->next = p->next; //将p的后继结点赋值给s的后继
p->next = s; //将s赋值给p的后继
return OK;
}
单链表的删除
/* 初始条件:链式线性表L已存在, 1<=i<=Listlength(L)
* 操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1
*/
Status ListDelete(LinkList *L,ElemType *e){
int j;
LinkList p,q;
p = *L;
j = 1;
while(p->next && j < i){ //遍历寻找第i个元素
p = p->next;
++j;
}
if(!(p->next) || j > i)
return ERROR; //第i个元素不存在
q = p->next;
p->next = q->next; //将q的后续赋值给p的后续
*e = q->data; //将q结点中的数据给e
free(q); //释放内存
return OK;
}
单链表的整表创建
头插法
void HeadInsert(linklist* head, int n)
{
int i;
linklist p;
*head = (linklist)malloc(sizeof( LNode));
(*head)->next = NULL;/*建立头结点*/
linklist p2 = *head;
printf("input %d numbers:\n", n);
for (i = 0; i < n; i++)
{
p = (linklist)malloc(sizeof( LNode));
scanf("%d", &(p->data));
p->next = (*head)->next;
(*head)->next = p;
}
/*for (i = 0; i < n; i++)
{
printf("%d", p2->next->data);
p2 = p2->next;
}
*/
}
尾插法
void TailInsert(linklist* head, int n)
{
int i;
linklist p;
*head = (linklist)malloc(sizeof( LNode));
(*head)->next = NULL;/*建立头结点*/
linklist p2 = *head;
printf("input %d numbers:\n", n);
for (i = 0; i < n; i++)
{
p = (linklist)malloc(sizeof( LNode));
scanf("%d", &(p->data));
p2->next = p;
p2 = p;
}
/*for (i = 0; i < n; i++)
{
printf("%d", p2->next->data);
p2 = p2->next;
}
*/
}
单链表的整表删除
/* 初始条件:链式线性表L已存在。 操作结果:将L重置为空表 */
Status ClearList(LinkList *L){
LinkList p,q;
p = (*L)->next;
while(p){
q = p->next;
free(p);
p = q;
}
(*L)->next = NULL;
return OK;
}
静态链表
0号单元相当于头节点,最后一个单元下标存放0
存储结构
#define MAXSIZE 1000
typedef struct{
ElemType data;
int cur; //游标,为0时表示无指向
}Component,StaticLineList[MAXSIZE];
初始化
/* 将一维数组space中各分量链成一个备用链表,space[0].cur为头指针,"0"表示空指针 */
Status InitList(StaticLinkList space){
int i;
for(i = 0; i < MAXSIZE - 1; i++){
space[i].cur = i + 1;
}
space[MAXSIZE - 1].cur = 0;
return OK;
}
静态链表的插入操作
/* 若备用空间链表非空,则返回分配的结点下标,否则返回0 */
int Malloc_SSL(StaticLinkList space){ //获取空闲分量的下标
int i = space[0].cur;
if(space[0].cur)
space[0].cur = space[i].cur;
return i;
}
Status ListInsert(StaticLinkList L, int i,ElemType e){
int j,k,l;
k = MAXSIZE - 1;
if(i < 1 || i > ListLength(L) + 1)
return ERROR;
j = Malloc_SSL(L);
if(j){
L[j].data = e; //将数据赋值给此分量的data
for(l = 1; l <= i - 1;l++) //找到第i个元素之前的位置
k = L[k].cur;
L[j].cur = L[k].cur; //把第i个元素之前的cur赋值给新元素的cur
L[k].cur = j; //把新元素的下标赋值给第i个元素之前元素的cur
return OK;
}
return ERROR;
}
静态链表的删除操作
/* 将下标为k的空闲结点回收到备用链表 */
void Free_SSL(StaticLinkList space, int k){
space[k].cur = space[0].cur; //把第一个元素的cur赋值给要删除的分量cur
space[0].cur = k; //把要删除的分量下标赋值给第一个元素的cur
}
/*删除在L中第i个数据元素*/
Status ListDelete(StaticLinkList L, int i){
int i,k;
if(i < 1 || i > ListLength(L))
return ERROR;
k = MAXSIZE - 1;
for(j = 1; j <= i-1;j++)
k = L[k].cur;
j = L[k].cur;
L[k].cur = L[j].cur;
Free_SSL(L,j);
return OK;
}
获取静态链表元素个数
/* 初始条件:静态链表L已存在。 操作结果:返回L中数据元素的个数 */
int ListLength(StaticLinkList L){
int j = 0;
int i = L[MAXSIZE - 1].cur;
while(i){
i = L[i].cur;
j++;
}
return j;
}
练习题
实现一个单链表,链表初始为空,支持三种操作:
- 向链表头插入一个数;
- 删除第 k个插入的数后面的数;
- 在第 k个插入的数后插入一个数。
现在要对该链表进行 M次操作,进行完所有操作后,从头到尾输出整个链表。
注意:题目中第 k个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n个数,则按照插入的时间顺序,这 n个数依次为:第 11 个插入的数,第 22 个插入的数,…第 n个插入的数。
输入格式
第一行包含整数 M,表示操作次数。
接下来 M行,每行包含一个操作命令,操作命令可能为以下几种:
H x
,表示向链表头插入一个数 x。D k
,表示删除第 k 个插入的数后面的数(当 k为 00 时,表示删除头结点)。I k x
,表示在第 k个插入的数后面插入一个数 x(此操作中 k均大于 00)。
输出格式
共一行,将整个链表从头到尾输出。
数据范围
1≤M≤100000
所有操作保证合法。
输入样例:
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6
输出样例
6 4 6 5
#include <iostream>
using namespace std;
const int N = 100010;
//head表示头结点的下标
//e[i]表示结点i的值
//ne[i]表示结点i的next的指针是多少
//idx 存储当前已经用到哪个点
int head,e[N],ne[N],idx;
//初始化
void init(){
head = -1;
idx = 0;
}
//头插
void add_to_head(int x){
e[idx] = x;
ne[idx] = head;
head = idx;
idx ++;
}
// 一般的插入操作,将x点插入到下标是k的后面
void add(int k , int x){
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx ++;
}
//将下标是k的后面的结点删除
void remove(int k){
ne[k] = ne[ne[k]];
}
int main(){
int m;
cin >> m;
init();
while(m--)
{
int k , x;
char op;
cin >> op;
if(op == 'H'){
cin >> x;
add_to_head(x);
}
else if(op == 'D'){
cin >> k;
if(!k){
head = ne[head];
}
remove(k-1);
}
else
{
cin >> k >> x;
add(k-1,x);
}
}
for(int i = head; i != -1;i = ne[i]) cout << e[i] << ' ' ;
cout << endl;
return 0;
}
双向循环链表
存储结构
typedef struct DulNode{
ElemType data;
struct DuLNode *prior;
struct DuLNode *next;
}DuLNode,*DuLinkList;
插入操作
s->prior = p;
s->next = p->next;
p->next->prior = s;
p-> next = s;
//注意第二行和第三四行语句的顺序即可
删除操作
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
习题
实现一个双链表,双链表初始为空,支持 55 种操作:
- 在最左侧插入一个数;
- 在最右侧插入一个数;
- 将第 k 个插入的数删除;
- 在第 k个插入的数左侧插入一个数;
- 在第 k个插入的数右侧插入一个数
现在要对该链表进行 M次操作,进行完所有操作后,从左到右输出整个链表。
注意:题目中第 k个插入的数并不是指当前链表的第 k个数。例如操作过程中一共插入了 n个数,则按照插入的时间顺序,这 n个数依次为:第 11 个插入的数,第 22 个插入的数,…第 n个插入的数。
输入格式
第一行包含整数 M,表示操作次数。
接下来 M行,每行包含一个操作命令,操作命令可能为以下几种:
L x
,表示在链表的最左端插入数 x。R x
,表示在链表的最右端插入数 x。D k
,表示将第 k个插入的数删除。IL k x
,表示在第 k个插入的数左侧插入一个数。IR k x
,表示在第 k个插入的数右侧插入一个数。
输出格式
共一行,将整个链表从左到右输出。
数据范围
1≤M≤100000
所有操作保证合法。
输入样例:
10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2
输出样例:
8 7 7 3 2 9
#include<iostream>
using namespace std;
const int N = 100010;
int m;
int e[N], l[N], r[N];
int idx;
//! 初始化
void init()
{
l[1] = 0, r[0] = 1;//* 初始化 第一个点的右边是 1 第二个点的左边是 0
idx = 2;//! idx 此时已经用掉两个点了
}
//* 在第 K 个点右边插入一个 X
void add(int k, int x)
{
e[idx] = x;
l[idx] = k;
r[idx] = r[k]; //todo 这边的 k 不加 1 , 输入的时候 k+1 就好
l[r[k]] = idx;
r[k] = idx;
idx++;
}//! 当然在 K 的左边插入一个数 可以再写一个 , 也可以直接调用我们这个函数,在 k 的左边插入一个 数 等价于在 l[k] 的右边插入一个数 add(l[k],x)
//*删除第 k个 点
void remove(int k)
{
r[l[k]] = r[k];
l[r[k]] = l[k];
}
int main(void)
{
ios::sync_with_stdio(false);
cin >> m;
init();
while(m--)
{
string op;
cin >> op;
int k, x;
if(op=="R")
{
cin >> x;
add(l[1], x); //! 0和 1 只是代表 头和尾 所以 最右边插入 只要在 指向 1的 那个点的右边插入就可以了
}
else if(op=="L")//! 同理 最左边插入就是 在指向 0的数的左边插入就可以了 也就是可以直接在 0的 有右边插入
{
cin >> x;
add(0, x);
}
else if(op=="D")
{
cin >> k;
remove(k + 1);
}
else if(op=="IL")
{
cin >> k >> x;
add(l[k + 1], x);
}
else
{
cin >> k >> x;
add(k + 1, x);
}
}
for(int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
return 0;
}