前段时间被大佬虐菜,内心是拔凉拔凉的,决定再次拿出封存2年的程序员教程第五版,恶补下数据结构和算法;首先从较简单的线性表入手,治疗下那颗脆弱的心.
数据结构的基本概念和术语
【数据元素】
【数据项】是元素的最小单位
【数据对象】具有相同性质元素的集合，数据对象包含数据元素 数据元素包含数据项
【数据结构】= D + S 顾名思义 就是数据对象的关系
1 线性表的基本定义
线性表是n个元素构成的有限序列,可以表示为{a1,a2,...an}.
线性表的抽象数据类型(数据结构+ 操作)为:
image.png
2 线性表的存储结构(重点)
线性表存储结构分为顺序存储和链式存储
2.1 顺序存储
线性表的顺序存储是指同一地址连续存储单元依次存储线性表,从而使得两个相邻元素在物理位置上相邻.通过物理结构表示元素的逻辑结构.
线性表中某个元素的存储位置为:
LOC(ai) = LOC(a1) + (i-1)d 其中 LOC(a1)是第一个元素的存储位置,d表示某个元素所占存储单元的个数.
顺序存储优点是可以随机取出元素,而且速度快,缺点是删除和插入元素需要移动元素.
线性表使用顺序存储插入一个新元素,需要平均移动n/2个元素;删除一个元素,需要平均移动(n - 1)/2个元素.
2.2 链式存储
使用链式存储,数据元素是用结点来存储,链表中结点的基本结构为:
结点的结构
数据域:用来存储数据结构的值.
指针域:用来存储当前元素的直接前驱或直接后续的位置信息,里面信息是个指针或者叫做
链.如果节点中只有一个指针域,则称为线性链表或者叫做
单链表(这里只介绍单链表存储线性表,其他链表存储不再介绍)
线性表的单链表存储
在链式存储中,一般只要得到指向第一个节点的指针(图中的Head)就可以顺序的访问到表中的任意一个元素(一般头结点的数据域用来存储链表的长度信息或者不用);所以在链式存储下进行插入和删除,其实质就是对指针进行修改.
如果线性表的数据是字符型,那么单链表的结点类型为:
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
// 数据域
char data;
// 指针域
struct node *next;
}NODE, *LinkList;
- 初始化链表
LinkList linkListInit(){
NODE *link;
// 申请空间
link =(NODE *)malloc(sizeof(NODE));
if(!link)
printf("空间申请失败");
// 长度为0的单链表
link->next = NULL;
return link;
}
2.创建一个单链表
头插法:
尾插法:
int main(int argv, char *argc[]){
char array[] = {'d','c','b','a'};
// 初始化一个头结点
LinkList link = linkListInit(); //{a,b,c,d}
link->next = NULL;
LinkList r;
// 指向 表尾结点
r = L;
//通过结点生成链表
int count = sizeof(array)/sizeof(char);
for(int i = 0; i < count;i++){
// 申请结点
NODE *p;
p = (NODE *)malloc(sizeof(NODE));
p->data = array[i];
// p的指针域指向头指针的后继结点,开始的时候后续节点的指针指向NULL
p->next = link->next;
// 把头结点的指针改成指向p的结点
//尾插法
link->next = p;
/** 头插法
p-next = NULL;
r->next = p;
r = r->next// r指向当前的表尾
*/
}
//link ->next = NULL;
printInfLink(link);
}
3.单链表的插入操作
// 查询位置k的结点
LinkList FindList(LinkList p,int k){
LinkList temp = p;
int i = 0;
while(temp ->next && i < k){
temp = temp ->next;
i++;
}
if(i == k && p)
return temp;
return NULL;
}
// 单链表插入一个元素
/**
L 头指针
将elem插入到k个元素之前
*/
void InsetList(LinkList L,int k,char elem)
{
// 执行第k-1元素的结点
LinkList p;
// 创建一个新的节点
LinkList newList;
if(k == 1){
p = L;
}else{
// 查询k前面的一个节点
p = FindList(L,k-1);
}
if(!p) return ;
newList = (NODE *)malloc(sizeof(NODE));
if(!newList) return ;
newList ->data = elem;
newList ->next = p -> next;
p->next = newList;
}
4.单链表的删除操作
image.png
// 删除第k个元素
void Delect_List(LinkList L ,int k){
// p是删除元素的前驱结点
// s是要删除的结点
LinkList p,s;
if(k == 1) p = L;
else p = FindList(L,k-1);
if(!p || !p ->next) return;
//删除节点
p->next = p->next->next;
// 或者 s = p->next;p->next = s->next
free(s);
}
网友评论