线性表---苦修内功篇

• 数据结构引言
• • • 数据结构定义
    • 逻辑结构
    • • 分类
    • 存储结构
    • • 分类
• 线性表
• • 顺序存储结构
  • • 顺序表基操
    • • 1.1顺序存储结构
      • 1.2顺序表初始化
      • 1.3按值查找
      • 1.4插入操作
      • 1.4顺序表删除
      • 1.5顺序表逆置
  • 顺序存储结构
  • • 单链表
    • 双向链表

既然要学习该门课程，自然要了解数据结构讲的是什么，我们学习目标是什么。

注：非官方定义，为笔者所理解给出的定义，望指正！

数据结构是研究数据元素之间关系的集合。
数据元素之间的关系也被称为结构。
根据数据之间的组织，存储和运算，将其分为逻辑结构，存储结构，和算法。

注意：在数据结构定义中的几个关键词：逻辑结构，存储结构，算法。
而我们学习数据结构就从这三个方面来学习。

描述数据之间的逻辑关系

1. 线性结构
2. 树形结构
3. 图状结构
4. 集合结构

数据在计算机物理结构中的存储

1. 顺序映象
2. 非顺序映象

注：一些概念性的定义说明在已忽略，如有疑问可自行查找或留言

特点：逻辑结构相邻的数据元素，其物理位置也相邻

#define MAXSIZE 20
typedef int ElemType;
typedef struct
{
	ElemType data[MAXSIZE];
	int length;
}SqList;

注意顺序表结构，在此定义的length是必要的，length用于表示线性表当前存储数据元素的个数，即线性表长度。（非数据长度，非数组长度，数组长度为MAXSIZE，为固定的）

void Init_SqList(SqList *L)
{
	L->length = 0;
}

int Location_SqList(SqList *L，ElemType x)
{
	int i = 1;
	while(i<=L->length && L->elem[i]!=x)
		i++;
	if(L->length+1 
1.4插入操作 
int Insert_SqList(SqList *L,int i,ElemType x)
{
	if(L->length == MAXSIZE) return FALSE;//表满
	if(i<1 || i> L->length+1) return FALSE;//位置非法
	int j;
	for(j=L->length; j>=i; j--)//移动
		L->elem[j+1] = L->elem[j];
	L->elem[i] = x;
	L=>length++;
	return TRUE;
} 
 
平均复杂度：
 
 
 
所有元素插入等可能，概率P=1/(n+1);
 i=1,循环n次；i=2,循环n-1次；…i=n,循环1次；i=n+1，循环0次；
 0=(n+(n-1)+(n-2)+(n-3)+…+1+0)*P=O(n/2)
 
 
1.4顺序表删除 
int Delet_SqList(SqList *L,int i,ElemType *e)
{
	if(L->length == 0) return FLASE;
	if(i<1 || i> L->length) return FALSE;
	*e = L->elem[i];
	int j;
	for(j = i; jlength; j++)
		L->elem[j] = L->elem[j+1];
	L->length--;
	return TRUE;
}
 
平均复杂度：
 
 
 
所有元素删除等可能，概率P = 1 / n;
 i = 1, 循环n - 1次；i = 2, 循环n - 2次；…i = n, 循环0次；
 0 = ((n - 1) + (n - 2) + (n - 3) + … + 1) *P = O((n - 1) / 2)
 
 
1.5顺序表逆置 
void Reverse_SqList(SqList *L)
{
	int i;
	ElemType t;
	for(i = 1;i< L->length/2;i++){
		t = L->elem[i];
		L->elem[i] = L->elem[L->length-i];
		L->elem[L->length-i] = t;
	}
}
 
顺序存储结构 
特点:链表中结点的逻辑次序与物理次序不一定相同
 
单链表 
1.1单链表结点定义
 
typedef struct Node
{
	ElemType data;
	struct Node* next;
}LNode,* linkList;
 
1.2.1头插法创建单链表
 
linkList Create_linkList1()
{
	linkList head = (linkList)malloc(sizeof(LNode);
	head->next = NULL;
	LNode * s;
	ElemType x;
	scanf("%d",&x);
	while(x!=-1)
	{
		s = (linkList)malloc(sizeof(LNode));
		s->data =x;
		s->next = head->next;
		head->next = s;
		scanf("%d",&x);
	}
	return head;
}
 
1.2.2尾插法创建单链表
 
linkList Create_linkList2()
{
	linkList head = (linkList)malloc(sizeof(LNode));
	head->next = NULL;
	LNode *s,*r = head;
	ElemType x;
	scanf("%d",&x);
	while(x!=-1)
	{
		s = (linkList)malloc(sizeof(LNode));
		s->data =x;
		r ->next = s;
		r = s;
		scanf("%d",&x);
	}
	r->next = NULL;
	return head;
}
 
1.3按序号查找
 
linkList Get_linkList（linkList head，int k）
{
	linkList p = head;
	int j = 0;
	while(p->next && jnext;
		j++;
	}	//查找到第k个结点
return p;
}
 
这里注意return p的用意，此时如果没有第k个结点，即p = NULL
 1.4单链表插入
 
int Insert_linkList（linkList head,int i,ElemType x）
{
	linkList p = head,s;
	int j = 0;
	while(p && jnext;
		j++;
	}
	if(p){
		s = (linkList)malloc(sizeof(LNode));
		s->data = x;
		s->next = p->next;
		p ->next = s;
		return TRUE;
	}
	return FALSE;
}
 
注意，单链表插入和删除都应该找到第 i - 1 个结点
 1.5单链表删除
 
int Delete_linkList(linkList head,int i,ElemType *x)
{
	linkList p = head,s;
	int j = 0;
	while(p && jnext;
		j++;
	}
	if(p)
	{
		s = p->next;
		*x = s->data;
		p->next = s->next;
		return TRUE;
	}
	return FALSE;
}
 
1.6 链表逆置
 
linkList Reverse_linkList(linkList head)
{
	linkList p = head->next,q;
	head->next = NULL;
	while(p)
	{
		q = p->next;
		p ->next = head->next;
		head->next = p;
		p = q; 
	}
	return head;
}
 
双向链表 
1.1双向链表的定义
 
typedef struct DLNode
{
	ELemType data;
	struct dlnode *prior,*next;
}DLNode,*DlinkList;
 
双向链表和单链表创建，查找，插入和删除操作基本类似，对插入操作的不同点展示如下：
 
int Insert_DlinkList（DlinkList head,int i,ElemType x）
{
	DlinkList p = head,s;
	int j = 0;
	while(p && jnext;
		j++;
	}//注意，此时p指向的是第i个结点，与单链表指向i-1不同
	if(p){
		s = (DlinkList)malloc(sizeof(DLNode));
		s->data = x;
		//核心连接代码
		s->prior = p->prior;
		p->prior->next = s;
		s->next = p;
		p->prior = s;
		
		return TRUE;
	}
	return FALSE;
}
 
插入操作中，最核心的是p->prior的指向不能在核心连接操作中丢失，应该在最后进行修改，其他步骤可以交换顺序。