C/C++数据结构->单链表，顺序表

时间复杂度：

空间复杂度

线性表的基本操作

顺序表

顺序表的实现

#include <cstdio>
#define MaxSize 10

typedef struct  
{
	int data[MaxSize]; //静态数组存放数据元素
	int length; //顺序表的长度
}SqList; //顺序表的类型定义

// 基本操作--初始化一个顺序表
void InitList(SqList &L)
{
	for (int i =0; i < MaxSize; i++) L.data[i] = 0; //设置默认初始值为0

	L.length = 0; //初始长度为 0
}

int main()
{
	SqList L; //定义一个顺序表
	InitList(L); //初始化顺序表
	L.length = 10;
	for (int i = 0; i< L.length; i++)
	{
		printf("%d\n", L.data[i]);
	} 
	
	return 0;
}

顺序表的动态分配数组

#include <cstdio>

#define InitSize 10

typedef struct 
{
	int *data; //动态分配数组的指针
	int maxSize;
	int length;
}sxbList;
void InitList(sxbList &L)
{
	L.data = new int[InitSize]; //动态分配数组
	// L.data = (int *) malloc (InitSize *sizeof(int));
	L.maxSize = InitSize;
	L.length = 0;
}

//  增加动态数组的长度
void IncreaseSize(sxbList &L, int len)
{
	int *p = L.data;
	L.data = new int[L.maxSize + len];
	for (int i = 0; i < L.length; i++)
	{
		L.data[i] = p[i];
	}
	L.maxSize = L.maxSize + len;
	delete []p;
}
int main()
{
	sxbList L;
	InitList(L);
	for (int i = 0; i < 5; i++)
	{
		L.data[i] = i;
		L.length++;
		printf("%d\n", L.data[i]);
	}
	IncreaseSize(L, 5);
	return 0;

}

顺序表插入

bool ListInsert(SqList &L, int i, int e)
{
	if (i < 1 || i >L.length + 1) return false; //判断插入位置是否合法
	if (L.length >= MaxSize) return false; //判断顺序表是否已满
	for (int j = L.length; j >= i; j--) //将第 i 个元素及之后的元素后移 
	{
		L.data[j] = L.data[j - 1];
	}

	L.data[i - 1] = e; //将 e 插入到第 i 个位置
	L.length++; //顺序表长度加 1
	return true;

}

时间复杂度

单链表

完整代码

#include <stdio.h>
#include <stdlib.h>

typedef struct LNode
{
	int data;			//每个节点存放数据
	struct LNode *next; // 指针指向下一个节点
} LNode, *LinkList;

// 初始化单链表
bool InitList(LinkList &L)
{
	L = (LNode *)malloc(sizeof(LNode)); // 生成头结点
	// L = new LNode;

	if (L == NULL)
		return false;
	L->next = NULL;
	return true;
}

// 后插操作： 在p节点之后插入元素e
bool ListNextInsert(LNode *p, int e)
{
	if (!p)
		return false;
	LNode *s = new LNode;
	if (!s)
		return false;
	s->data = e;
	s->next = p->next; // 将p指向的给s，
	p->next = s; // 将p重新指向s
	return true;
}
// 前插操作： 在p节点之前插入元素e
bool InsertPriorNode(LNode *p, int e)
{
	if (!p)
		return false;
	LNode *s = new LNode;
	if (!s)
		return false;

	s->data = p->data;
	s->next = p->next;
	p->data = e;
	p->next = s; // p连接到新节点s
	return true;
}
// 在i的位置插入e
bool ListInsert(LinkList &L, int i, int e)
{
	if (i < 1)
		return false; //判断插入位置是否合法
	LNode *p = L;
	int j = 0;
	while (p && j < i - 1) //寻找第i-1个结点
	{
		p = p->next;
		j++;
	}
	ListNextInsert(p, e);

	return true;
}
// 删除操作
bool ListDelete(LinkList &L, int i, int &e)
{
	if (i < 1)
		return false;
	LNode *p = L;
	int j = 0;
	while (p && j < i - 1)
	{
		// 循环找到第i-1个节点
		p = p->next;
		j++;
	}
	if (!p || !p->next)
		return false; //超出单链表的界限，i值不合法;i-1节点后无节点

	LNode *q = p->next;
	e = q->data;
	printf("delete：%d\n", e);
	p->next = q->next;
	delete (q);
	return true;
}

// 删除指定的节点,  无法删除最后一个节点
bool DeleteNode(LNode *p)
{
	if (!p)
		return false;
	LNode *q = p->next;
	p->data = q->data;
	p->next = q->next;
	delete (q);
	return true;
}

// 循环链表，删除指定节点
bool DeleteNodeList(LinkList &L, LNode *p)
{

	if (!p)
		return false;
	int j = 0;
	LNode *q = L;
	while (q->next != p)
	{
		q = q->next;
	}
	q->next = q->next->next;
	delete (p);
	return true;
}
// 找到i元素
LNode *GetElem(LinkList &L, int i)
{
	if (i < 0)
		return NULL;
	LNode *p = L;
	int j = 0;
	while (p && j < i)
	{
		p = p->next;
		j++;
	}
	return p;
}

// 查找数据域为e的	节点
LNode *LocateElem(LinkList L, int e)
{
	LNode *p = L->next;
	while (p && p->data != e)
		p = p->next;
	return p;
}

// 求表的长度
int length(LinkList &L)
{
	int len = 0;
	LNode *p = L;
	while (p->next)
	{
		len++;
		p = p->next;
	}
	return len;
}

// 建立单链表
LinkList ListInit(LinkList &L)
{
	L = (LinkList)malloc(sizeof(LNode));
	int x; //输入
	// 定义两个指针, 指向头结点
	LNode *l, *r = L;
	scanf("%d", &x);
	while (x != 666)
	{
		l = new LNode;
		l->data = x;
		r->next = l;
		r = l; // r指向插入节点x
		scanf("%d", &x);
	}
	r->next = NULL;
	return L;
}

// 头插法
LinkList BackInsert(LinkList &L)
{
	int i = 0;
	L = new LNode;
	L->next =NULL;// 指向空，否则指向其它区域
	while (i < 4)
	{
		ListNextInsert(L, i);
		i++;
	}
	return L;
}
int main()
{
	LinkList L;
	// ListInit(L); //初始化
	BackInsert(L);

	// InsertPriorNode(L->next->next, 10);
	// InsertPriorNode(L->next->next, 11);

	ListNextInsert(L->next->next, 100);
	// ListNextInsert(L->next->next, 101);

	int a;
	// ListDelete(L, 1, a);
	// DeleteNodeList(L, L1);
	// printf("%d\n",GetElem(L, 0)->next->data);
	// printf("%d\n", LocateElem(L, 32)->data);
	printf("%d\n", length(L));

	while (L->next)
	{
		printf("%d ", L->next->data);
		L = L->next;
	}

	return 0;
}

单链表初始化

// 初始化单链表
LinkList ListInit(LinkList &L)
{
	L = new LNode;
	int x; //输入
	// 定义两个指针, 指向头结点
	LNode *l, *r = L;
	scanf("%d",&x);
	while(x != 666)
	{
		l = new LNode;
		l->data = x;
		r->next = l;
		r = l; // r指向插入节点x
		scanf("%d", &x);
	}
	r->next = NULL;
	return L;
}

插入操作

// 后插操作： 在p节点之后插入元素e
bool ListNextInsert(LNode *p, int e)
{
	if (!p) return false;
	LNode *s = new LNode;
	if (!s) return false;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}
// 前插操作： 在p节点之前插入元素e
bool InsertPriorNode(LNode *p, int e)
{
	if (!p) return false;
	LNode *s = new LNode;
	if (!s) return false;

	s->data = p->data;
	s->next = p->next;
	p->data = e;
	p->next = s; //p连接到新节点s
	return true;
}

// 在i的位置插入e
bool ListInsert(LinkList &L, int i, int e)
{
	if (i < 1) return false; //判断插入位置是否合法
	LNode* p = L;
	int j = 0;
	while (p && j < i - 1) //寻找第i-1个结点
	{
		p = p->next;
		j++;
	}
	ListNextInsert(p, e);

	return true;
}

删除操作

// 删除操作
bool ListDelete(LinkList &L, int i, int &e)
{
	if (i < 1) return false;
	LNode *p = L;
	int j =0;
	while( p && j <i - 1)
	{
		// 循环找到第i-1个节点
		p = p->next;
		j ++;
	}
	if (!p || !p->next) return false; //超出单链表的界限，i值不合法;i-1节点后无节点

	LNode *q = p->next;
	e = q->data;
	printf("%d\n", e);
	p->next = q->next;
	delete(q);
	return true;
}

删除指定的节点

// 删除指定的节点,  无法删除最后一个节点
bool DeleteNode(LNode *p)
{
	if (!p) return false;
	LNode *q = p->next;
	p->data = q->data;
	p->next = q->next;
	delete(q);
	return true;
}

// 循环链表，删除指定节点
bool DeleteNodeList(LinkList &L, int i)
{

	int j = 0;
	LNode *p = L;
	while (p && j < i - 1)
	{
		p = p->next;
		j ++;
	}
	LNode *q = p->next;
	p->next = q->next;
	delete(q);
	return true;
}